Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
This provides improved optimization methods for machine learning and data science applications, though it appears incremental as it builds on existing proximal point and bundle methods.
The paper tackles stochastic convex optimization by introducing the approximate-proximal point (aProx) family of model-based methods, which achieve stronger convergence guarantees (e.g., probability 1 convergence and optimal asymptotic normality) and adaptivity to easy problems with linear convergence, while adding minimal computational overhead compared to standard stochastic subgradient methods.
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.