Asymptotic optimality in stochastic optimization

DOI10.1214/19-AOS1831zbMATH Open1461.62146arXiv1612.05612OpenAlexW3128015591MaRDI QIDQ2656586FDOQ2656586

Authors: Feng Ruan, John C. Duchi 

Publication date: 11 March 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1612.05612

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

zbMATH Keywords

convex analysisstochastic gradientslocal asymptotic minimax theorymanifold identification

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Minimax procedures in statistical decision theory (62C20) Stochastic approximation (62L20) Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15)

Cites Work

• Adaptive subgradient methods for online learning and stochastic optimization
• Weak convergence and empirical processes. With applications to statistics
• Trust-region methods on Riemannian manifolds
• Asymptotic Statistics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotics in statistics. Some basic concepts.
• Acceleration of Stochastic Approximation by Averaging
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Primal-dual subgradient methods for convex problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometrizing rates of convergence. II
• Geometrizing rates of convergence. III
• Approximation dans les espaces m�triques et th�orie de l'estimation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implicit Functions and Solution Mappings
• Dual averaging methods for regularized stochastic learning and online optimization
• Lectures on Stochastic Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic properties of statistical estimators in stochastic programming
• Identifiable Surfaces in Constrained Optimization
• stochastic quasigradient methods and their application to system optimization^†
• Title not available (Why is that?)
• Tilt Stability of a Local Minimum
• Stochastic Gradient Descent on Riemannian Manifolds
• Exposing Constraints
• Sensitivity Analysis of Nonlinear Programs and Differentiability Properties of Metric Projections
• Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential
• An Extension of the Robbins-Monro Procedure
• Asymptotically efficient stochastic approximation; the RM case
• Title not available (Why is that?)
• Manifold identification in dual averaging for regularized stochastic online learning
• Optimization Problems with Perturbations: A Guided Tour
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Stochastic approximation algorithms for constrained optimization problems
• Stochastic iteration for a constrained optimization problem

Cited In (20)

• Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
• 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
• Title not available (Why is that?)
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Stochastic recursive algorithms for optimization. Simultaneous perturbation methods
• Asymptotic normality and optimality in nonsmooth stochastic approximation
• Asymptotics of minimax stochastic programs
• Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
• The importance of better models in stochastic optimization
• Stability and Sample-Based Approximations of Composite Stochastic Optimization Problems
• Title not available (Why is that?)
• Price of correlations in stochastic optimization
• Title not available (Why is that?)
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Asymptotics of the optimal value of SAA with AMIS on minimax stochastic programs
• Asymptotic bias of stochastic gradient search
• Informational inequalities in the problem of gradient stochastic optimization and optimal realizable algorithms
• Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
• Unifying mirror descent and dual averaging

Uses Software

• ElemStatLearn
• AdaGrad
• Saga

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)