On stochastic mirror descent with interacting particles: Convergence properties and variance reduction
File(s)
OA Location
Author(s)
Borovykh, A
Kantas, N
Parpas, P
Pavliotis, GA
Type
Journal Article
Abstract
An open problem in optimization with noisy information is the computation of an exact minimizer that is independent of the amount of noise. A standard practice in stochastic approximation algorithms is to use a decreasing step-size. This however leads to a slower convergence. A second alternative is to use a fixed step-size and run independent replicas of the algorithm and average these. A third option is to run replicas of the algorithm and allow them to interact. It is unclear which of these options works best. To address this question, we reduce the problem of the computation of an exact minimizer with noisy gradient information to the study of stochastic mirror descent with interacting particles. We study the convergence of stochastic mirror descent and make explicit the tradeoffs between communication and variance reduction. We provide theoretical and numerical evidence to suggest that interaction helps to improve convergence and reduce the variance of the estimate.
Date Issued
2021-04
Date Acceptance
2021-01-03
Citation
Physica D: Nonlinear Phenomena, 2021, 418, pp.1-21
ISSN
0167-2789
Publisher
Elsevier BV
Start Page
1
End Page
21
Journal / Book Title
Physica D: Nonlinear Phenomena
Volume
418
Copyright Statement
© 2021 Elsevier Ltd. All rights reserved. This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence http://creativecommons.org/licenses/by-nc-nd/4.0/
Identifier
https://www.sciencedirect.com/science/article/pii/S0167278921000026?via%3Dihub
Subjects
Science & Technology
Physical Sciences
Mathematics, Applied
Physics, Fluids & Plasmas
Physics, Multidisciplinary
Physics, Mathematical
Mathematics
Physics
Mirror descent
Interacting agents
Variance reduction
math.OC
math.OC
stat.ML
Fluids & Plasmas
0102 Applied Mathematics
Publication Status
Published
Article Number
132844
Date Publish Online
2021-01-13