Convergence of online mirror descent

DOI10.1016/J.ACHA.2018.05.005zbMATH Open1494.68219arXiv1802.06357OpenAlexW2803423166WikidataQ129764098 ScholiaQ129764098MaRDI QIDQ2278461FDOQ2278461

Authors: Yunwen Lei, Ding-Xuan Zhou 

Publication date: 5 December 2019

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: In this paper we consider online mirror descent (OMD) algorithms, a class of scalable online learning algorithms exploiting data geometric structures through mirror maps. Necessary and sufficient conditions are presented in terms of the step size sequence ${et{a}_t}_t$ for the convergence of an OMD algorithm with respect to the expected Bregman distance induced by the mirror map. The condition is $li{m}_{toinfty}et{a}_t=0,su{m}_{t=1}^{infty}et{a}_t=infty$ in the case of positive variances. It is reduced to $su{m}_{t=1}^{infty}et{a}_t=infty$ in the case of zero variances for which the linear convergence may be achieved by taking a constant step size sequence. A sufficient condition on the almost sure convergence is also given. We establish tight error bounds under mild conditions on the mirror map, the loss function, and the regularizer. Our results are achieved by some novel analysis on the one-step progress of the OMD algorithm using smoothness and strong convexity of the mirror map and the loss function.

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

Recommendations

• Analysis of Online Composite Mirror Descent Algorithm
• A generalized online mirror descent with applications to classification and regression
• Convergence of unregularized online learning algorithms
• On the convergence of mirror descent beyond stochastic convex programming
• Convergence analysis of online algorithms

zbMATH Keywords

learning theoryconvergence analysisBregman distanceonline learningmirror descent

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Online algorithms; streaming algorithms (68W27) Stochastic approximation (62L20) Stochastic programming (90C15)

Cites Work

• A randomized Kaczmarz algorithm with exponential convergence
• Robust Estimation of a Location Parameter
• Online learning algorithms
• A Stochastic Approximation Method
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Robust Stochastic Approximation Approach to Stochastic Programming
• AIR tools -- a MATLAB package of algebraic iterative reconstruction methods
• Linearized Bregman iterations for compressed sensing
• Support vector machine soft margin classifiers: error analysis
• Title not available (Why is that?)
• Sharp uniform convexity and smoothness inequalities for trace norms
• Incremental subgradient methods for nondifferentiable optimization
• Multi-kernel regularized classifiers
• Online gradient descent learning algorithms
• Title not available (Why is that?)
• Regularization schemes for minimum error entropy principle
• Regularization techniques for learning with matrices
• On Complexity Issues of Online Learning Algorithms
• Online Regularized Classification Algorithms
• Online regularized learning with pairwise loss functions
• Almost sure convergence of the Kaczmarz algorithm with random measurements
• Unregularized online learning algorithms with general loss functions
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Distributed learning with regularized least squares
• Learning theory of randomized Kaczmarz algorithm
• Optimization methods for large-scale machine learning
• Learning theory of distributed spectral algorithms
• Thresholded spectral algorithms for sparse approximations
• Analysis of Online Composite Mirror Descent Algorithm

Cited In (11)

• Conformal mirror descent with logarithmic divergences
• Error analysis of the kernel regularized regression based on refined convex losses and RKBSs
• Analysis of singular value thresholding algorithm for matrix completion
• Fast and strong convergence of online learning algorithms
• Analysis of Online Composite Mirror Descent Algorithm
• The information geometry of mirror descent
• Block coordinate type methods for optimization and learning
• Analogues of switching subgradient schemes for relatively Lipschitz-continuous convex programming problems
• High probability bounds on AdaGrad for constrained weakly convex optimization
• Distributed learning and distribution regression of coefficient regularization
• Federated learning for minimizing nonsmooth convex loss functions

Uses Software

• AIR tools

This page was built for publication: Convergence of online mirror descent

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