On the efficiency of a randomized mirror descent algorithm in online optimization problems

DOI10.1134/S0965542515040041zbMath1350.90027OpenAlexW1816993330MaRDI QIDQ2354481

Yu. E. Nesterov, Alexander V. Gasnikov, Vladimir Spokoiny

Publication date: 13 July 2015

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0965542515040041

zbMATH Keywords

stochastic optimizationrandomizationonline optimizationmulti-armed banditsexponential weightingmirror descent methoddual averaging methodweighting of experts

Mathematics Subject Classification ID

Stochastic programming (90C15) 2-person games (91A05)

Related Items

Efficient numerical methods to solve sparse linear equations with application to PageRank, Gaussian two-armed bandit and optimization of batch data processing, Unnamed Item, Two-armed bandit problem and batch version of the mirror descent algorithm, On efficient randomized algorithms for finding the PageRank vector

Cites Work

• Primal-dual subgradient methods for convex problems
• Smooth minimization of non-smooth functions
• Subgradient methods for huge-scale optimization problems
• Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
• Validation analysis of mirror descent stochastic approximation method
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• A sublinear-time randomized approximation algorithm for matrix games
• On efficient randomized algorithms for finding the PageRank vector
• Recursive aggregation of estimators by the mirror descent algorithm with averaging
• Concentration Inequalities
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Accelerated, Parallel, and Proximal Coordinate Descent
• Smoothed analysis of algorithms
• Robust Stochastic Approximation Approach to Stochastic Programming
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• On the three-stage version of stable dynamic model
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Prediction, Learning, and Games
• Concentration of Measure for the Analysis of Randomized Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item