Source-linked AI summary
Online Learning with Predictable Sequences
Alexander Rakhlin, Karthik Sridharan
TL;DR
The paper addresses how online learners can obtain less pessimistic regret bounds on predictable sequences while remaining protected against worst-case sequences. It develops algorithms that incorporate a known or learned predictable process, extends the framework to partial and side information, and shows that accurate predictions yield low regret while inaccurate ones preserve standard guarantees.
Problem
Worst-case no-regret bounds are naturally pessimistic, motivating tighter guarantees for more regular sequences without losing protection against arbitrary sequences.
Method
The paper incorporates a predictable process into online linear-optimization algorithms and extends the approach to partial information and competing predictable-process models.
Results
Accurate predictable processes yield tighter, low-regret bounds, while inaccurate processes retain usual worst-case protection up to a constant factor.
Takeaways & Limitations
Predictable processes provide a way to incorporate prior knowledge into online learning, with path-length and variance bounds appearing as special cases.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops online-learning methods that exploit predictable structure in sequences while retaining worst-case regret protection. Predictable processes incorporate prior knowledge, encompass partial-information settings, and recover path-length and variance bounds as special cases.
- Motivation: No-regret guarantees protect against arbitrary sequences, but their worst-case bounds can be pessimistic for regular sequences.The paper seeks tighter bounds for benign sequences without sacrificing worst-case protection.
- Contributions: The paper develops computational algorithms, partial-information methods, and model-selection procedures for learning the predictable process under different feedback assumptions.The full-information methods use optimistic predictions, while later sections address missing information and delayed feedback.
- Predictable processes: A predictable process models Nature’s next move as a function of the preceding sequence, with the observed sequence treated as prediction plus adversarial noise.The goal is to pay primarily for deviations from the predictable trend.
- Examples: Path-length bounds arise when the previous move predicts the next move, while variance bounds and other statistics provide additional predictable-process choices.The paper also mentions fading-memory, autoregressive, and phase-based predictors.
- Bounds: Algorithms obtain tighter regret bounds when the predictable process tracks the sequence, while retaining standard protection when prediction is poor.The predictable process may be an arbitrary function of the past.
- Feedback: The framework extends beyond full information to bandit, delayed-feedback, and state-information settings by defining predictions from the information available to the learner.In bandit feedback, the learner may observe only the scalar loss rather than Nature’s move.
2 Full Information Methods
The full-information section presents optimistic FTRL and Mirror Descent methods that incorporate a known predictable process into online decisions. These methods retain standard regret guarantees when predictions fail and can exploit small deviations when predictions are accurate.
- Setup: The full-information methods assume the predictable value M_t is known at the beginning of round t.It may be computed by the learner or conveyed by an external source.
- FTRL: Optimistic FTRL modifies Follow the Regularized Leader with a self-concordant regularizer and incorporates M_t+1 as a guess of the next move.When M_t+1 = 0, it reduces to standard FTRL.
- Mirror Descent: Optimistic Mirror Descent modifies Mirror Descent using a 1-strongly convex regularizer and dual-norm geometry.The method generalizes a prior two-projection algorithm for M_t = x_t−1.
- Guarantees: Both optimistic methods achieve their predictable-process bounds for arbitrary strategies of Nature and retain standard Mirror Descent or FTRL bounds up to a constant when predictions are inaccurate.The learning-rate parameter need not know the total variation in advance because the doubling trick can be used.
- Simplex case: On the probability simplex, optimistic Mirror Descent specializes to an Exponential Weights method with regret expressed through local norms.The stated result requires η∥x_t−M_t∥∞ ≤ 1/4 at every step.
3 Methods for Partial and Bandit Information
The paper extends predictable-process regret methods to partial feedback, using estimated moves and self-concordant regularization. It also identifies limits on estimating more general full-information statistics.
- Partial-information framework: Partial-feedback learning uses the observed scalar loss together with an accessible or learner-constructed predictable process.The framework allows the predictable statistic to be computed from available information or supplied externally.
- SCRiBLe: SCRiBLe for a Predictable Process combines Follow the Regularized Leader on estimated moves with randomized Hessian-based exploration.The learner samples eigenvectors of the regularizer’s Hessian and perturbs the current decision in a random signed direction.
- Analysis: The analysis of the predictable-process method reuses earlier full-information bounds, simplifying and generalizing the analysis of Hazan and Kale.The paper explicitly bases the method’s analysis on the previously developed full-information predictable-process results.
- Estimating predictable statistics: Reservoir sampling can estimate the running full-information mean in bandit settings, using roughly O(log T) rounds.For more general statistics, however, the estimation error need not track the relevant variation term.
- Estimating predictable statistics: For more general functions, determining which statistics can be well estimated remains an open direction for further research.The paper identifies this as a limitation of extending the method beyond the running mean.
4 Learning The Predictable Processes
The paper learns which predictable process best describes the sequence while simultaneously minimizing decision regret. It develops full- and partial-information algorithms for this model-selection problem.
- Motivation: Model selection is needed because the learner cannot know the hindsight-optimal predictable process at the game’s outset.The goal is to approach the regret obtainable if the best model had been known in advance.
- Full information: The learner can combine models by maintaining a distribution over a set Π of predictable processes.The Optimistic Mirror Descent algorithm initializes this distribution uniformly and uses its weighted process as the prediction.
- Full information: With full information, the paper gives an Optimistic Mirror Descent method whose regret is bounded for any strategy of Nature.The method operates over convex subsets of Banach and dual spaces with a strongly convex regularizer.
- Full information: The model-learning layer minimizes squared prediction error relative to the best process, while the primary learner minimizes regret using the learned process.This separates learning the predictable process from decision optimization.
- Partial information: Under partial information, the paper presents SCRiBLe-based variants for access to all processes, one selected process, or only the selected process and scalar loss.These variants cover progressively weaker feedback settings and provide corresponding expected-regret lemmas.
- Partial information: The partial-feedback algorithm combines randomized exploration with a multi-armed-bandit update over the predictable-process models.Its regret analysis relies on an improved bandit bound expressed through the loss of the best arm.
5 Randomized Methods and the Follow the Perturbed Leader Algorithm
The paper develops randomized relaxation and random-playout methods that incorporate predictable processes into Follow the Perturbed Leader-style updates. Their regret depends on deviations from the predictable trend, but requires advance knowledge of individual deviation scales.
- Randomized methods: Randomized FPL-style methods use a relaxation to obtain regret bounds for sequences constrained around a predictable process.The construction extends random-playout ideas from unconstrained adversaries to deviations around a trend.
- Regret bounds: A limitation is that the randomized methods require the individual deviations σt to be known in advance.The paper notes that relaxing this requirement is left for future work.
- Randomized methods: The relaxation is admissible when it satisfies the recursive constraint inequality, which yields regret guarantees against every adversary strategy.For unconstrained adversaries, taking each future constraint set as X recovers the earlier setting.
- Randomized methods: The method approximates conditional sequential Rademacher complexity by sampling independent perturbations from suitable symmetric distributions.The sampled deviations are combined with the predictable process in the randomized update.
- Regret bounds: The expected regret is bounded by a classical Rademacher complexity and can be further bounded for smooth norms.The perturbation variables follow the distributions specified by the deviation scales.
- FPL specialization: For ℓ1 and ℓ∞ unit balls, the update selects the maximum coordinate of a perturbed cumulative vector; with zero prediction, it becomes an FPL update.The simplex case is obtained through a converse reduction from the ℓ1-ball construction.
6 Other Examples
The paper shows that predictable-process methods recover useful bounds in delayed-feedback and i.i.d. settings. These examples connect predictable sequences to variance-type guarantees and vanishing-noise behavior.
- Delayed feedback: In delayed-feedback bandit learning, the running average of previously revealed losses serves as a full-information statistic.The statistic uses the move observed k rounds earlier and the available history before that delay.
- Delayed feedback: Variance-type bounds follow immediately for bandit problems that provide delayed full-information feedback.This example demonstrates how side information can create a predictable process even when current losses remain bandit feedback.
- I.I.D. data: For i.i.d. data, choosing the empirical mean as the predictable process makes the leading expected term equal to the distribution variance under the chosen norm.The third term vanishes in expectation after the quadratic expansion.
- I.I.D. data: The resulting regret is ˜O(σ√T), with a natural transition from noisy to deterministically predictable behavior as σ approaches zero.The same idea can extend to bandit information when the predictable process is estimated well.
7 Auxiliary Results: Improved Bounds for Small Losses
The paper develops auxiliary bounds in terms of the loss of the optimal decision, including a non-stochastic multi-armed-bandit result. These bounds are useful when the best decision incurs small loss and support predictable-process guarantees.
- Small-loss bounds: Bounds in terms of the best decision’s loss become tighter when the optimal decision incurs small loss.The paper identifies this form of bound as a building block for predictable-process results.
- Auxiliary lemmas: Lemma 12 gives SCRiBLe a regret bound when losses satisfy ⟨f,x⟩∈[0,s] and η < 1/(2sn^2).The result assumes a self-concordant barrier over F.
- Multi-armed bandits: The paper combines SCRiBLe with a self-concordant barrier for the probability simplex to analyze non-stochastic multi-armed bandits.The authors report that the same result was not obtained using the entropy function, even with local-norm bounds.
- Multi-armed bandits: In the bandit setting, Nature supplies x1,...,xT ∈[0,s]d, while the learner selects an arm and observes only its incurred loss.This is the feedback model used for the multi-armed-bandit analysis.
- Auxiliary lemmas: Lemma 13 applies the auxiliary analysis to multi-armed bandits for sequences in [0,s]d under η < 1/(4sd^2).The supplied passage states an expected-regret bound but omits its displayed expression.
8 Standard Doubling Trick
The standard doubling trick removes the need to know certain bound-controlling quantities or the optimal learning rate in advance. Applied to full-information and bandit results, it preserves guarantees within constant factors.
- General construction: The doubling trick converts a fixed-learning-rate algorithm into one that operates without prior knowledge of the relevant quantity τ.Lemma 14 provides the black-box basis for this conversion through phase-based restarting.
- Costs and implementation: Starting a new phase can discard N time periods, adding regret bounded by sN because losses are bounded by s.The supplied analysis relates this cost to the chosen initial learning rate.
- Costs and implementation: Even when phases restart the algorithm, the predictable processes may retain information about all previous moves of Nature.Thus a phase restart need not erase the history available to the prediction process.
- Guarantees: For full-information bounds, doubling yields regret at most a factor 8 larger than the bound obtained with the optimal η.This applies directly to the paper’s full-information lemmas.
- Guarantees: For several bandit lemmas, doubling is applied to an intermediate computable quantity before replacing it with the corresponding unobserved quantity.The resulting bounds remain within a factor 8 of those obtained by optimizing η.
A Appendix
The appendix supplies proof details for the paper’s full-information, partial-information, and model-selection results. Its arguments use regularized updates, unbiased loss estimates, self-concordant geometry, and minimax or concentration reasoning.
- Geometric analysis: The appendix’s geometric arguments use self-concordance and Newton-decrement properties to control the relevant optimization steps.The proofs also analyze events separating the largest coordinates and bound the error outside those events.
- Partial information: For partial feedback, the appendix uses unbiased loss estimates so bandit observations can support updates designed for the simplex.Sampling from qt and constructing an unbiased estimate reproduces the relevant regret bound.
- Model selection: The model-selection proofs treat predictable processes as experts and update their distribution with an experts algorithm using pointwise prediction losses.The analysis bounds these prediction losses before applying the corresponding SCRiBLe results.
- Model selection: The appendix derives bandit guarantees by combining SCRiBLe with bounds on losses relative to each predictable process.For the cited constructions, the pointwise losses and their maxima are explicitly bounded before invoking Lemma 13.
- Random playout: The random-playout analysis establishes admissibility through minimax arguments and obtains regret bounds for randomized strategies.The strategy samples future auxiliary variables and Rademacher signs before selecting the current decision.