On stochastic subgradient mirror-descent algorithm with weighted averaging

DOI10.1137/120894464MaRDI QIDQ4979860zbMATH OpenOpenAlexFDO

Authors Angelia Nedić, Soomin Lee

Publication date 19 June 2014

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.1879

zbMATH Keywords

convex optimizationmirror-descent algorithmweighted averagingstochastic subgradient method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)

Abstract: This paper considers stochastic subgradient mirror-descent method for solving constrained convex minimization problems. In particular, a stochastic subgradient mirror-descent method with weighted iterate-averaging is investigated and its per-iterate convergence rate is analyzed. The novel part of the approach is in the choice of weights that are used to construct the averages. Through the use of these weighted averages, we show that the known optimal rates can be obtained with simpler algorithms than those currently existing in the literature. Specifically, by suitably choosing the stepsize values, one can obtain the rate of the order $1/k$ for strongly convex functions, and the rate $1/sqrtk$ for general convex functions (not necessarily differentiable). Furthermore, for the latter case, it is shown that a stochastic subgradient mirror-descent with iterate averaging converges (along a subsequence) to an optimal solution, almost surely, even with the stepsize of the form $1/sqrt1+k$, which was not previously known. The stepsize choices that achieve the best rates are those proposed by Paul Tseng for acceleration of proximal gradient methods.

Recommendations

• An incremental mirror descent subgradient algorithm with random sweeping and proximal step
• Optimal distributed stochastic mirror descent for strongly convex optimization
• On convergence of the stochastic subgradient method with on-line stepsize rules
• String-averaging incremental stochastic subgradient algorithms
• Algorithms of inertial mirror descent in convex problems of stochastic optimization

Cited in

(35)

• A family of subgradient-based methods for convex optimization problems in a unifying framework
• Stochastic approximation with discontinuous dynamics, differential inclusions, and applications
• Algorithms for stochastic optimization with function or expectation constraints
• Stochastic incremental mirror descent algorithms with Nesterov smoothing
• An incremental mirror descent subgradient algorithm with random sweeping and proximal step
• String-averaging incremental stochastic subgradient algorithms
• Fastest rates for stochastic mirror descent methods
• Stochastic mirror descent method for linear ill-posed problems in Banach spaces
• Performing linear convergence for distributed constrained optimisation over time-varying directed unbalanced networks
• Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• New results on subgradient methods for strongly convex optimization problems with a unified analysis
• Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learning
• On the convergence of mirror descent beyond stochastic convex programming
• Stochastic approximation method using diagonal positive-definite matrices for convex optimization with fixed point constraints
• On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: asymptotic convergence and rate analysis
• Stochastic mirror descent method for distributed multi-agent optimization
• A stochastic primal-dual method for optimization with conditional value at risk constraints
• Optimized convergence of stochastic gradient descent by weighted averaging
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Sequential sample average majorization-minimization
• Recursive aggregation of estimators by the mirror descent algorithm with averaging
• A framework of convergence analysis of mini-batch stochastic projected gradient methods
• SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Probabilistic robustness estimates for feed-forward neural networks
• Generalised gossip-based subgradient method for distributed optimisation
• Convergence rate bounds for the mirror descent method: IQCs, Popov criterion and Bregman divergence
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Distributed constrained optimization with periodic dynamic quantization
• Adaptive Schauder Stochastic Mirror Descent in Banach Spaces
• Optimal distributed stochastic mirror descent for strongly convex optimization
• On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
• Exploiting problem structure in optimization under uncertainty via online convex optimization
• Federated learning for minimizing nonsmooth convex loss functions
• Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures

This page was built for publication: On stochastic subgradient mirror-descent algorithm with weighted averaging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979860)