Adaptive Bound Optimization for Online Convex Optimization

Abstract

We introduce a new online convex optimization algorithm that adaptively chooses its regularization function based on the loss functions observed so far. This is in contrast to previous algorithms that use a fixed regularization function such as L2-squared, and modify it only via a single time-dependent parameter. Our algorithm's regret bounds are worst-case optimal, and for certain realistic classes of loss functions they are much better than existing bounds. These bounds are problem-dependent, which means they can exploit the structure of the actual problem instance. Critically, however, our algorithm does not need to know this structure in advance. Rather, we prove competitive guarantees that show the algorithm provides a bound within a constant factor of the best possible bound (of a certain functional form) in hindsight.

Updates to match final COLT version

References in corpus (1)

• Less Regret via Online Conditioning

Cited by in corpus (60)

• A Reliable Effective Terascale Linear Learning System
• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Adaptive Federated Optimization
• Online Learning: A Modern Introduction Using Convex Optimization
• On the Convergence Proof of AMSGrad and a New Version
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data
• Is Local SGD Better than Minibatch SGD?
• A Deep Learning Algorithm for High-Dimensional Exploratory Item Factor Analysis
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• A Simple Convergence Proof of Adam and Adagrad
• Scalable Second Order Optimization for Deep Learning
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Classifying Antimicrobial and Multifunctional Peptides with Bayesian Network Models
• AdaX: Adaptive Gradient Descent with Exponential Long Term Memory
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Adaptive Gradient-Based Meta-Learning Methods
• Second-Order Non-Stationary Online Learning for Regression
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Adaptive Gradient Descent without Descent
• A generalization of regularized dual averaging and its dynamics
• Lipschitz and Comparator-Norm Adaptivity in Online Learning
• Learning to Search for Dependencies
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Large-Scale Learning with Less RAM via Randomization
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• Adaptive Temporal Difference Learning with Linear Function Approximation
• A Generalized Online Mirror Descent with Applications to Classification and Regression
• On the fast convergence of minibatch heavy ball momentum
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Temporal Variability in Implicit Online Learning
• A Last-Step Regression Algorithm for Non-Stationary Online Learning
• Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
• Online Variance Reduction for Stochastic Optimization
• Projection-Free Adaptive Gradients for Large-Scale Optimization
• Scalable Nonlinear Learning with Adaptive Polynomial Expansions
• Stagewise Enlargement of Batch Size for SGD-based Learning
• Accelerating Optimization via Adaptive Prediction
• On Large-Cohort Training for Federated Learning
• Combining Online Learning Guarantees
• Online Convex Optimization with Continuous Switching Constraint
• Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces
• Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements
• The Minimax Complexity of Distributed Optimization
• Adaptive Differentially Private Empirical Risk Minimization
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• Online Strongly Convex Optimization with Unknown Delays
• Lipschitz Adaptivity with Multiple Learning Rates in Online Learning
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Stochastic Gradient Methods with Block Diagonal Matrix Adaptation
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Similarity Function Tracking using Pairwise Comparisons
• On the Last Iterate Convergence of Momentum Methods
• Adaptive Online Learning with Varying Norms
• Online AUC Optimization for Sparse High-Dimensional Datasets
• Adaptive Gradient Descent for Optimal Control of Parabolic Equations with Random Parameters