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.
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
- 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?)
- 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 Statistics
- Asymptotic properties of statistical estimators in stochastic programming
- 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
- 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 Gradient Descent on Riemannian Manifolds
- Stochastic approximation algorithms for constrained optimization problems
- Stochastic iteration for a constrained optimization problem
- 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
- stochastic quasigradient methods and their application to system optimization†
Cited in
(20)- scientific article; zbMATH DE number 996467 (Why is no real title available?)
- The right complexity measure in locally private estimation: it is not the Fisher information
- Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization
- scientific article; zbMATH DE number 3920243 (Why is no real title available?)
- Asymptotics of minimax stochastic programs
- Asymptotics of the optimal value of SAA with AMIS on minimax stochastic programs
- Informational inequalities in the problem of gradient stochastic optimization and optimal realizable algorithms
- Unifying mirror descent and dual averaging
- Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- scientific article; zbMATH DE number 5577556 (Why is no real title available?)
- Stability and Sample-Based Approximations of Composite Stochastic Optimization Problems
- Stochastic recursive algorithms for optimization. Simultaneous perturbation methods
- Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
- The importance of better models in stochastic optimization
- Price of correlations in stochastic optimization
- Asymptotic bias of stochastic gradient search
- Asymptotic normality and optimality in nonsmooth stochastic approximation
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)
