The importance of better models in stochastic optimization

By Hilal Asi, John C. Duchi. 2019

83 citations recorded by the source corpus.

Significance Sensitivity of optimization algorithms to problem and algorithmic parameters leads to tremendous waste in time and energy, especially in applications with millions of parameters, such as deep learning. We address this by developing stochastic optimization methods demonstrably—both by theory and by experimental evidence—more robust, enjoying optimal convergence guarantees for a variety of stochastic optimization problems. Additionally, we highlight the importance of method sensitivity to problem difficulty and algorithmic parameters. Standard stochastic optimization methods are brittle, sensitive to stepsize choice and other algorithmic parameters, and they exhibit instability outside of well-behaved families of objectives. To address these challenges, we investigate models for stochastic optimization 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. We highlight the importance of robustness and accurate modeling with experimental evaluation of convergence time and algorithm sensitivity.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “Other possible extensions of our work include using the proposed new variants of SPS with accelerated methods, studying further the effect of mini-batching and non-uniform sampling of DecSPS, and extensions to the distributed and decentralized settings.”
Repurposing Pretrained Models for Robust Out-of-domain Few-Shot Learning (2021, background): “A desirable feature for an optimizer is to maintain good performance in a broad range of stepsizes (Asi & Duchi, 2019).”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “A similar observation has been used to construct a “truncated” model for improving the robustness of gradient descent in [1].”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “or their relaxations to use approximate models [6, 5].”
Coresets for Data-efficient Training of Machine Learning Models (2019, background): “Signiﬁcantly decreasing these costs without decreasing the learnt system’s resulting accuracy is one of the grand challenges of machine learning and artiﬁcial intelligence today (Asi & Duchi, 2019).”
Second-order Conditional Gradients (2020, background): “A similar assumption is made in Asi & Duchi (2019), to build optimization algorithms that have a robust performance with respect to different step sizes and algorithm parameters.”
Optimizer Benchmarking Needs to Account for Hyperparameter Tuning (2019, background): “There has been recent interest in optimizers that are provably robust to hyperparameter choices, termed the A P ROX family (Asi & Duchi, 2019a;b).”