Local Minimax Complexity of Stochastic Convex Optimization
We extend the traditional worst-case, minimax analysis of stochastic convex optimization by introducing a localized form of minimax complexity for individual functions. Our main result gives function-specific lower and upper bounds on the number of stochastic subgradient evaluations needed to optimize either the function or its "hardest local alternative" to a given numerical precision. The bounds are expressed in terms of a localized and computational analogue of the modulus of continuity that is central to statistical minimax analysis. We show how the computational modulus of continuity can be explicitly calculated in concrete cases, and relates to the curvature of the function at the optimum. We also prove a superefficiency result that demonstrates it is a meaningful benchmark, acting as a computational analogue of the Fisher information in statistical estimation. The nature and practical implications of the results are demonstrated in simulations.
The paper introduces the notion of local minimax complexity for stochastic convex optimization (SCO). The setting they consider is very similar to the classical notion of (first order) SCO: one wishes to minimize a unknown function f from some family F, and one may repeatedly query an oracle with a point x, and the oracle returns a subgradient of f at x with Gaussian noise (they have an additional assumption that the oracle always returns the same subgradient, but this is not a big deal).   The traditional goal in this setting is then to approximately minimize f using as few oracle calls as possible. The traditional minimax risk is max over f in F of min over algorithms A of the expected error that A makes on f. That is, the algorithm needs to work to minimize all f in the class. In contrast, in this paper, they fix a function f and they define the local minimax complexity of optimizing f the max over g in F of min over algorithms A of the expected error A makes on either g or f. That is, the algorithm needs only differentiate between f and g (and these are known to the algorithm). In some sense, this captures a notion of "instance-by-instance" optimality for SCO.  The paper then shows that when F is the set of Lipschitz convex functions, the local minimax risk is exactly captured by a notion of modulus of continuity that they define. However, the algorithm which achieves the upper bound here is not actually useful for optimization. They also show a "superefficiency" result: that any algorithm which outperforms the local minimax risk of a function at some function must perform substantially worse on some nearby function. Finally, they give an algorithm which achieves local minimax risk for SCO in 1D.
This is a very interesting paper, and a novel attempt to capture a notion of per-instance optimal rates for SCO. The tight connection to the modulus of continuity they define is very nice, and so is the super-efficiency result. I think this is a very interesting new direction which may yield some nice algorithmic ideas in the future.  The paper does have some drawbacks. In my opinion, the algorithms presented are not strong, although the framework is very interesting. The 1D algorithm is in my opinion not vey satisfying, and neither is the information theoretic upper bound presented. The latter is particularly worrisome because it suggests to me that perhaps this notion of local minimax complexity is not quite the right thing to do, since it allows these algorithms which cheat so much. The minimax setting itself is a bit strange, because the noise is assumed to be Gaussian, whereas usually it suffices to have a second moment condition on the gradient oracle.