Improved rates for derivative free play in convex games
share
The influential work of Bravo et al. 2018 shows that derivative free play in strongly monotone games has complexity O(d^2/ε^3), where ε is the target accuracy on the expected squared distance to the solution. This note shows that the efficiency estimate is actually O(d^2/ε^2), which reduces to the known efficiency guarantee for the method in unconstrained optimization. The argument we present is elementary, simply interpreting the method as stochastic gradient play on a slightly perturbed strongly monotone game.
READ FULL TEXT