# The importance of better models in stochastic optimization

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

## Built on by (most cited first, 30 of 32)

- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Towards Sustainable Learning: Coresets for Data-efficient Deep Learning](https://mlsanity.com/paper/2306.01244/) (2023)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [An Exploration of Non-Euclidean Gradient Descent: Muon and its Many Variants](https://mlsanity.com/paper/2510.09827/) (2025)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [Data-Efficient Training of CNNs and Transformers with Coresets: A Stability Perspective](https://mlsanity.com/paper/2303.02095/) (2023)
- [A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction](https://mlsanity.com/paper/2204.00406/) (2022)
- [A Model-Based Method for Minimizing CVaR and Beyond](https://mlsanity.com/paper/2305.17498/) (2023)
- [MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters](https://mlsanity.com/paper/2402.02342/) (2024)
- [Repurposing Pretrained Models for Robust Out-of-domain Few-Shot Learning](https://mlsanity.com/paper/2103.09027/) (2021)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing](https://mlsanity.com/paper/2402.01599/) (2024)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions](https://mlsanity.com/paper/2308.16362/) (2023)
- [Finding a stationary point of a stochastic convex problem](https://mlsanity.com/paper/2607.06883/) (2026)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)
- [Laplace Sample Information: Data Informativeness Through a Bayesian Lens](https://mlsanity.com/paper/2505.15303/) (2025)
- [A Probabilistically Motivated Learning Rate Adaptation for Stochastic Optimization](https://mlsanity.com/paper/2102.10880/) (2021)
- [Bolstering Stochastic Gradient Descent with Model Building](https://mlsanity.com/paper/2111.07058/) (2021)
- [Learning distributed channel access policies for networked estimation: data-driven optimization in the mean-field regime](https://mlsanity.com/paper/2112.05837/) (2021)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)
- [Hyperparameter Optimization and Reproducibility in Deep Learning Model Training](https://mlsanity.com/paper/2510.15164/) (2025)

## Abstract (arXiv)

Standard stochastic optimization methods are brittle, sensitive to stepsize choices and other algorithmic parameters, and they exhibit instability outside of well-behaved families of objectives. To address these challenges, we investigate models for stochastic minimization and learning problems that exhibit better robustness to problem families and algorithmic parameters. With appropriately accurate models---which we call the aProx family---stochastic methods can be made stable, provably convergent and asymptotically optimal; even modeling that the objective is nonnegative is sufficient for this stability. We extend these results beyond convexity to weakly convex objectives, which include compositions of convex losses with smooth functions common in modern machine learning applications. We highlight the importance of robustness and accurate modeling with a careful experimental evaluation of convergence time and algorithm sensitivity.