Online Learning with Predictable Sequences

Abstract

We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specifically if the sequence encountered by the learner is described well by a known "predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Additionally, the methods achieve the usual worst-case regret bounds if the sequence is not benign. Our approach can be seen as a way of adding prior knowledge about the sequence within the paradigm of online learning. The setting is shown to encompass partial and side information. Variance and path-length bounds can be seen as particular examples of online learning with simple predictable sequences. We further extend our methods and results to include competing with a set of possible predictable processes (models), that is "learning" the predictable process itself concurrently with using it to obtain better regret guarantees. We show that such model selection is possible under various assumptions on the available feedback. Our results suggest a promising direction of further research with potential applications to stock market and time series prediction.

References in corpus (1)

• Relax and Localize: From Value to Algorithms

Cited by in corpus (69)

• A Variational Inequality Perspective on Generative Adversarial Networks
• Online Learning: A Modern Introduction Using Convex Optimization
• Fast Convergence of Regularized Learning in Games
• Online Optimization : Competing with Dynamic Comparators
• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
• Refined Lower Bounds for Adversarial Bandits
• Competitive Gradient Descent
• Near-Optimal Algorithms for Minimax Optimization
• Efficient Algorithms for Adversarial Contextual Learning
• Second-order Online Nonconvex Optimization
• Provable Guarantees for Gradient-Based Meta-Learning
• Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
• Predictive Online Convex Optimization
• MetaGrad: Multiple Learning Rates in Online Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• GANGs: Generative Adversarial Network Games
• Stochastic Variance Reduction for Variational Inequality Methods
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• Improved Algorithms for Convex-Concave Minimax Optimization
• Revisiting Stochastic Extragradient
• The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
• First-order regret bounds for combinatorial semi-bandits
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• No-regret learning and mixed Nash equilibria: They do not mix
• Adaptive Online Learning
• Dynamic Regret of Convex and Smooth Functions
• Multi-level Traffic-Responsive Tilt Camera Surveillance through Predictive Correlated Online Learning
• Near-Optimal No-Regret Learning in General Games
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Convergence of Value Aggregation for Imitation Learning
• Improved Path-length Regret Bounds for Bandits
• Corralling a Band of Bandit Algorithms
• Online Learning with Continuous Variations: Dynamic Regret and Reductions
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Hedging in games: Faster convergence of external and swap regrets
• DIPPA: An improved Method for Bilinear Saddle Point Problems
• Prediction with Corrupted Expert Advice
• An automatic system to detect equivalence between iterative algorithms
• Taming GANs with Lookahead-Minmax
• Faster saddle-point optimization for solving large-scale Markov decision processes
• Accelerating Optimization via Adaptive Prediction
• Online Learning with Many Experts
• Online Learning with Imperfect Hints
• Combining Online Learning Guarantees
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems
• Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
• On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimization
• On the Regret Analysis of Online LQR Control with Predictions
• Optimistic and Adaptive Lagrangian Hedging
• Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
• Adaptive and Efficient Algorithms for Tracking the Best Expert
• Universal Online Convex Optimization Meets Second-order Bounds
• Stochastic Optimization under Distributional Drift
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Online Learning with Low Rank Experts
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Online Learning with Optimism and Delay
• Online Linear Optimization with Many Hints
• Low-Regret Active learning
• A Boosting Framework on Grounds of Online Learning
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• Distributed Charging Control of Electric Vehicles Using Online Learning
• Robust Bandit Learning with Imperfect Context
• Logarithmic Regret from Sublinear Hints