On the Universality of Online Mirror Descent
arXiv:1107.4080
Abstract
We show that for a general class of convex online learning problems, Mirror Descent can always achieve a (nearly) optimal regret guarantee.
Cited by in corpus (20)
- Path-SGD: Path-Normalized Optimization in Deep Neural Networks
- Stochastic Optimization of PCA with Capped MSG
- Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
- Online Linear Optimization via Smoothing
- On the Adaptivity of Stochastic Gradient-Based Optimization
- Learning From An Optimization Viewpoint
- Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
- Parameter-Free Online Convex Optimization with Sub-Exponential Noise
- Online Deep Learning from Doubly-Streaming Data
- Curvature of Feasible Sets in Offline and Online Optimization
- A Generalized Online Mirror Descent with Applications to Classification and Regression
- Relax and Localize: From Value to Algorithms
- Local and Global Uniform Convexity Conditions
- Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
- Linear Bandits on Uniformly Convex Sets
- Stochastic Optimization under Distributional Drift
- An Optimal Affine Invariant Smooth Minimization Algorithm
- Learning Sparse Low-Threshold Linear Classifiers
- Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
- Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers