Almost Sure Convergence and Non-Asymptotic Concentration Bounds for Stochastic Mirror Descent Algorithm
- 16 October 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 8, 2397-2402
Abstract
This letter investigates the convergence and concentration properties of the Stochastic Mirror Descent (SMD) algorithm utilizing biased stochastic subgradients. We establish the almost sure convergence of the algorithm’s iterates under the assumption of diminishing bias. Furthermore, we derive concentration bounds for the discrepancy between the iterates’ function values and the optimal value, based on standard assumptions. Subsequently, leveraging the assumption of Sub-Gaussian noise in stochastic subgradients, we present refined concentration bounds for this discrepancy.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Robust Analysis of Almost Sure Convergence of Zeroth-Order Mirror Descent AlgorithmIEEE Control Systems Letters, 2023
- A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and ApplicationsIEEE Signal Processing Magazine, 2020
- High-Dimensional Statistics2019
- Convergence of the Iterates in Mirror Descent MethodsIEEE Control Systems Letters, 2018
- Stochastic mirror descent method for distributed multi-agent optimizationOptimization Letters, 2016
- Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsIEEE Transactions on Automatic Control, 2016
- Random Gradient-Free Minimization of Convex FunctionsFoundations of Computational Mathematics, 2015
- Mirror descent and nonlinear projected subgradient methods for convex optimizationOperations Research Letters, 2003
- Optimization flow control. I. Basic algorithm and convergenceIEEE/ACM Transactions on Networking, 1999
- A CONVERGENCE THEOREM FOR NON NEGATIVE ALMOST SUPERMARTINGALES AND SOME APPLICATIONS**Research supported by NIH Grant 5-R01-GM-16895-03 and ONR Grant N00014-67-A-0108-0018.1971