# Geometry, Computation, and Optimality in Stochastic Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2019.

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

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2209.00809/) (2022)
- [Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks](https://mlsanity.com/paper/2306.00342/) (2023)
- [FOSI: Hybrid First and Second Order Optimization](https://mlsanity.com/paper/2302.08484/) (2023)
- [Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?](https://mlsanity.com/paper/2603.25657/) (2026)
- [Accelerated Gradient Flow: Risk, Stability, and Implicit Regularization](https://mlsanity.com/paper/2201.08311/) (2022)
- [Block-Norm Geometries for Online Mirror Descent with Sparse Losses](https://mlsanity.com/paper/2602.13177/) (2026)

## Abstract (arXiv)

We study computational and statistical consequences of problem geometry in stochastic and online optimization. By focusing on constraint set and gradient geometry, we characterize the problem families for which stochastic- and adaptive-gradient methods are (minimax) optimal and, conversely, when nonlinear updates -- such as those mirror descent employs -- are necessary for optimal convergence. When the constraint set is quadratically convex, diagonally pre-conditioned stochastic gradient methods are minimax optimal. We provide quantitative converses showing that the ``distance'' of the underlying constraints from quadratic convexity determines the sub-optimality of subgradient methods. These results apply, for example, to any ℓp-ball for p < 2, and the computation/accuracy tradeoffs they demonstrate exhibit a striking analogy to those in Gaussian sequence models.