Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity

By Hilal Asi, John C. Duchi. 2018

148 citations recorded by the source corpus.

We develop model-based methods for solving stochastic convex optimization problems, introducing the approximate-proximal point, or aProx, family, which includes stochastic subgradient, proximal point, and bundle methods. When the modeling approaches we propose are appropriately accurate, the methods enjoy stronger convergence and robustness guarantees than classical approaches, even though the model-based methods typically add little to no computational overhead over stochastic subgradient methods. For example, we show that improved models converge with probability 1 and enjoy optimal asymptotic normality results under weak assumptions; these methods are also adaptive to a natural class of what we term easy optimization problems, achieving linear convergence under appropriate strong growth conditions on the objective. Our substantial experimental investigation shows the advantages of more accurate modeling over standard subgradient methods across many smooth and non-smooth optimization problems.

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): “We provided a practical variant of SPS [22], which converges to the true problem solution without the interpolation assumption in convex stochastic problems — matching the rate of AdaGrad.”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “An alternative is to use stochastic proximal-point-type updates [10, 46, 44, 15, 24], which update Transmission of privatized updates After completing the local update to θ i , we deﬁne the local diﬀerence ∆ i = θ i − θ and transmit this to the aggregator using a separated mechanism (Deﬁnition 2.2).”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, unknown): “In standard application of such methods [21, 15, 5, 6], given a datapoint x and stepsize αk, we update θk+1 = aprox ` αk (θk;x) = θk − αkgαk(θk;x).”
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).”
Stochastic Gradient Descent on Nonconvex Functions with General Noise Models (2021, background): “To our knowledge, this is the most general assumption for the noise under which convergence has been demonstrated, and the proof relies intimately on convexity [see Asi and Duchi, 2019, Lemma 3.7].”