# Local Minimax Complexity of Stochastic Convex Optimization

arXiv: https://arxiv.org/abs/1605.07596 · HTML: https://mlsanity.com/paper/1605.07596/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2016.

## Built on by (most cited first, 6 of 6)

- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Contrastive Domain Adaptation for Time-Series via Temporal Mixup](https://mlsanity.com/paper/2212.01555/) (2022)
- [Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis](https://mlsanity.com/paper/2404.00042/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Distribution free M-estimation](https://mlsanity.com/paper/2505.22807/) (2025)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)

## Abstract (arXiv)

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.