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

Abstract

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.

To appear in SIAM Journal on Optimization

References in corpus (3)

• Online Importance Weight Aware Updates
• An optimal algorithm for stochastic strongly-convex optimization
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization

Cited by in corpus (26)

• Protection Against Reconstruction and Its Applications in Private Federated Learning
• The importance of better models in stochastic optimization
• Nonlinear System Identification: Learning while respecting physical models using a sequential Monte Carlo method
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Optimizer Benchmarking Needs to Account for Hyperparameter Tuning
• Bellman filtering and smoothing for state-space models
• Element Level Differential Privacy: The Right Granularity of Privacy
• Stochastic quasi-Newton with line-search regularization
• From low probability to high confidence in stochastic convex optimization
• Temporal Variability in Implicit Online Learning
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Stochastic Gradient Descent on Nonconvex Functions with General Noise Models
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity
• On the computation of equilibria in monotone and potential stochastic hierarchical games
• Stochastic optimization over proximally smooth sets
• A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction
• Stochastic gradient-free descents
• Mitigating Divergence of Latent Factors via Dual Ascent for Low Latency Event Prediction Models
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models
• Practical Precoding via Asynchronous Stochastic Successive Convex Approximation
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• Elephant random walks with multiple extractions and general reinforcement functions
• Stochastic Polyak Stepsize with a Moving Target