On stochastic mirror descent with interacting particles: convergence properties and variance reduction

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.

References in corpus (14)

• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Don't Decay the Learning Rate, Increase the Batch Size
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Sampling Can Be Faster Than Optimization
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations
• SGD: General Analysis and Improved Rates
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• On Learning Rates and Schrödinger Operators
• Large-Scale Stochastic Sampling from the Probability Simplex
• Acceleration and Averaging in Stochastic Mirror Descent Dynamics
• On Transformations in Stochastic Gradient MCMC
• Stochastic mirror descent dynamics and their convergence in monotone variational inequalities

Cited by in corpus (2)

• Dimension reduction of noisy interacting systems
• Response Theory Identifies Reaction Coordinates and Explains Critical Phenomena in Noisy Interacting Systems