Local Minimax Complexity of Stochastic Convex Optimization
This work addresses the problem of refining optimization complexity analysis for researchers in machine learning and optimization, offering a more nuanced benchmark, though it is incremental in extending existing minimax theory.
The paper introduces a localized minimax complexity framework for stochastic convex optimization, providing function-specific lower and upper bounds on stochastic subgradient evaluations needed for optimization, with explicit calculations and simulations to demonstrate practical implications.
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.