On the convergence of gradient-like flows with noisy gradient input

Abstract : In view of solving convex optimization problems with noisy gradient input, we analyze the asymptotic behavior of gradient-like flows that are subject to stochastic disturbances. Specifically, we focus on the widely studied class of mirror descent methods for constrained convex programming and we examine the dynamics' convergence and concentration properties in the presence of noise. In the small noise limit, we show that the dynamics converge to the solution set of the underlying problem (a.s.). Otherwise, if the noise is persistent, we estimate the measure of the dynamics' long-run concentration around interior solutions and their convergence to boundary solutions that are sufficiently "robust". 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-01404586
Contributor : Panayotis Mertikopoulos <>
Submitted on : Monday, November 28, 2016 - 11:32:26 PM
Last modification on : Thursday, November 8, 2018 - 2:28:02 PM

Identifiers

  • HAL Id : hal-01404586, version 1

Citation

Panayotis Mertikopoulos, Mathias Staudigl. On the convergence of gradient-like flows with noisy gradient input. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2018, 28 (1), pp.163-197. ⟨hal-01404586⟩

Share

Metrics

Record views

359

Files downloads

281