Asymptotic optimality in stochastic optimization
From MaRDI portal
Publication:2656586
Abstract: We study local complexity measures for stochastic convex optimization problems, providing a local minimax theory analogous to that of H'{a}jek and Le Cam for classical statistical problems. We give complementary optimality results, developing fully online methods that adaptively achieve optimal convergence guarantees. Our results provide function-specific lower bounds and convergence results that make precise a correspondence between statistical difficulty and the geometric notion of tilt-stability from optimization. As part of this development, we show how variants of Nesterov's dual averaging---a stochastic gradient-based procedure---guarantee finite time identification of constraints in optimization problems, while stochastic gradient procedures fail. Additionally, we highlight a gap between problems with linear and nonlinear constraints: standard stochastic-gradient-based procedures are suboptimal even for the simplest nonlinear constraints, necessitating the development of asymptotically optimal Riemannian stochastic gradient methods.
The authors develop asymptotic theory for stochastic optimization problems. They show a local asymptotic minimax lower bound and make precise connections between tilt stability in optimization and the (statistical) difficulty of solving risk minimization problems. Finally, the authors indicate the best algorithms for solving the given optimization task. A few original theorems are proved. All proofs are correct.
Recommendations
- Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
- Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
- Lower bounds for non-convex stochastic optimization
- New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
- Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema
Cites work
- A Stochastic Approximation Method
- Acceleration of Stochastic Approximation by Averaging
- Adaptive subgradient methods for online learning and stochastic optimization
- An Extension of the Robbins-Monro Procedure
- Approximation dans les espaces m�triques et th�orie de l'estimation
- Asymptotic properties of statistical estimators in stochastic programming
- Asymptotic Statistics
- Asymptotically efficient stochastic approximation; the RM case
- Asymptotics in statistics. Some basic concepts.
- Dual averaging methods for regularized stochastic learning and online optimization
- Exposing Constraints
- Geometrizing rates of convergence. II
- Geometrizing rates of convergence. III
- scientific article; zbMATH DE number 3124347 (Why is no real title available?)
- scientific article; zbMATH DE number 3733065 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 477581 (Why is no real title available?)
- scientific article; zbMATH DE number 1064665 (Why is no real title available?)
- scientific article; zbMATH DE number 1181283 (Why is no real title available?)
- scientific article; zbMATH DE number 2155014 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3252891 (Why is no real title available?)
- scientific article; zbMATH DE number 3322635 (Why is no real title available?)
- Identifiable Surfaces in Constrained Optimization
- Implicit Functions and Solution Mappings
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- Lectures on Stochastic Programming
- Manifold identification in dual averaging for regularized stochastic online learning
- Optimization Problems with Perturbations: A Guided Tour
- Primal-dual subgradient methods for convex problems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sensitivity Analysis of Nonlinear Programs and Differentiability Properties of Metric Projections
- Stochastic approximation algorithms for constrained optimization problems
- Stochastic Gradient Descent on Riemannian Manifolds
- Stochastic iteration for a constrained optimization problem
- stochastic quasigradient methods and their application to system optimization†
- Tilt Stability of a Local Minimum
- Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential
- Trust-region methods on Riemannian manifolds
- Weak convergence and empirical processes. With applications to statistics
Cited in
(26)- Asymptotic bias of stochastic gradient search
- Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
- Asymptotics of minimax stochastic programs
- Price of correlations in stochastic optimization
- scientific article; zbMATH DE number 996467 (Why is no real title available?)
- scientific article; zbMATH DE number 5577556 (Why is no real title available?)
- scientific article; zbMATH DE number 3920243 (Why is no real title available?)
- Stochastic recursive algorithms for optimization. Simultaneous perturbation methods
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- The importance of better models in stochastic optimization
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Informational inequalities in the problem of gradient stochastic optimization and optimal realizable algorithms
- Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization
- Unifying mirror descent and dual averaging
- The right complexity measure in locally private estimation: it is not the Fisher information
- Stability and Sample-Based Approximations of Composite Stochastic Optimization Problems
- Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
- Asymptotic normality and optimality in nonsmooth stochastic approximation
- Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
- Asymptotics of the optimal value of SAA with AMIS on minimax stochastic programs
- High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance
- Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming
- Stochastic approximation based confidence regions for stochastic variational inequalities
- Statistical inference for online decision making with Lasso loss function: in a contextual multi-armed bandit setting
- Online covariance matrix estimation in sketched Newton methods
- A normal map-based proximal stochastic gradient method: convergence and identification properties
This page was built for publication: Asymptotic optimality in stochastic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656586)
