On the convergence of gradient-like flows with noisy gradient input
From MaRDI portal
Abstract: In view of solving convex optimization problems with noisy gradient input, we analyze the asymptotic behavior of gradient-like flows under stochastic disturbances. Specifically, we focus on the widely studied class of mirror descent schemes for convex programs with compact feasible regions, and we examine the dynamics' convergence and concentration properties in the presence of noise. In the vanishing noise limit, we show that the dynamics converge to the solution set of the underlying problem (a.s.). Otherwise, when the noise is persistent, we show that the dynamics are concentrated around interior solutions in the long run, and they converge to boundary solutions that are sufficiently "sharp". Finally, we show that a suitably rectified variant of the method converges irrespective of the magnitude of the noise (or the structure of the underlying convex program), and we derive an explicit estimate for its rate of convergence.
Recommendations
- Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
- The effect of deterministic noise in subgradient methods
- On the convergence of mirror descent beyond stochastic convex programming
- On the fast convergence of random perturbations of the gradient flow
- Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
Cites work
- A continuous-time approach to online optimization
- A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
- A variational perspective on accelerated methods in optimization
- Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems
- Asymptotic pseudotrajectories and chain recurrent flows, with applications
- Barrier Operators and Associated Gradient-Like Dynamical Systems for Constrained Minimization Problems
- Central Paths, Generalized Proximal Point Methods, and Cauchy Trajectories in Riemannian Manifolds
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convex Analysis
- Criteria for recurrence and existence of invariant measures for multidimensional diffusions
- Distributed Stochastic Optimization via Matrix Exponential Learning
- Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators
- Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator
- Ergodic mirror descent
- Evolutionary Games and Population Dynamics
- Free-Steering Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
- Hessian Riemannian Gradient Flows in Convex Programming
- scientific article; zbMATH DE number 1667417 (Why is no real title available?)
- scientific article; zbMATH DE number 4215340 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 54145 (Why is no real title available?)
- scientific article; zbMATH DE number 192908 (Why is no real title available?)
- scientific article; zbMATH DE number 918596 (Why is no real title available?)
- scientific article; zbMATH DE number 1405930 (Why is no real title available?)
- scientific article; zbMATH DE number 4197739 (Why is no real title available?)
- Imitation dynamics with payoff shocks
- Introductory lectures on convex optimization. A basic course.
- Learning in games via reinforcement and regularization
- Learning in games with continuous action sets and unknown payoff functions
- Long time behaviour and stationary regime of memory gradient diffusions
- On damped second-order gradient systems
- On the long time behavior of second order differential equations with asymptotically small dissipation
- On the robustness of learning in games with stochastically perturbed payoff observations
- Online learning and online convex optimization
- Optimization and dynamical systems
- Primal-dual subgradient methods for convex problems
- Regularization techniques for learning with matrices
- Robust Stochastic Approximation Approach to Stochastic Programming
- Singular Riemannian barrier methods and gradient-projection dynamical systems for constrained optimization
- Stability of regime-switching stochastic differential equations
- Stochastic differential equations, backward SDEs, partial differential equations
- The emergence of rational behavior in the presence of stochastic perturbations
- THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
- The long-run behavior of the stochastic replicator dynamics
- The role of relative entropy in quantum information theory
- Variational Analysis
Cited in
(21)- Convergence properties of gradient descent noise reduction
- Riemannian game dynamics
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Stochastic heavy ball
- On stochastic mirror descent with interacting particles: convergence properties and variance reduction
- Learning in nonatomic games. I: Finite action spaces and population games
- Large deviations and stochastic stability in population games
- scientific article; zbMATH DE number 2051048 (Why is no real title available?)
- Total variation flow perturbed by gradient linear multiplicative noise
- On gradient-based learning in continuous games
- Hessian barrier algorithms for linearly constrained optimization problems
- On the convergence of mirror descent beyond stochastic convex programming
- First-order methods for convex optimization
- Stochastic differential equations for modeling first order optimization methods
- Stochastic mirror descent for convex optimization with consensus constraints
- Compact formulation of the augmented evolution equation for optimal control computation
- CV@R-penalised portfolio optimisation with biased stochastic mirror descent
- Optimal control of SPDEs driven by time-space Brownian motion
- Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case
- SPDE games driven by a Brownian sheet with applications to pollution minimization
- Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure
This page was built for publication: On the convergence of gradient-like flows with noisy gradient input
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4602552)
