Source-linked AI summary
A Second-order Bound with Excess Losses
Pierre Gaillard, Gilles Stoltz, Tim Van Erven
TL;DR
The paper addresses the difficulty of obtaining expert-dependent second-order regret bounds online without hindsight tuning. It develops multiple-learning-rate versions of Prod and related methods, obtaining bounds in excess losses and applying them to confidence-weighted experts and additional standard settings. The applications include optimal confidence scaling, improved small-excess-loss bounds, and constant regret for i.i.d. losses.
Problem
Existing improved second-order bounds can require hindsight-dependent tuning, while uniform bounds do not reflect differences in how difficult it is to compete with individual experts.
Method
The paper develops Prod and polynomially weighted average algorithms with multiple, time-varying expert-specific learning rates, plus a generic reduction for confidence-reporting experts.
Results
The resulting bounds use excess losses, scale optimally with experts’ confidences, improve bounds for small excess losses, and imply constant regret for i.i.d. losses.
Takeaways & Limitations
Excess-loss second-order bounds provide expert-dependent guarantees and support applications beyond the basic standard setting, including confidence-weighted prediction and stochastic losses.
Takeaways & Limitations
Earlier improved bounds, including related bounds discussed in the introduction, suffer from the impossible-tuning issue when the desired tuning depends on hindsight quantities.
Abstract
from arXiv · showhide
We study online aggregation of the predictions of experts, and first show new second-order regret bounds in the standard setting, which are obtained via a version of the Prod algorithm (and also a version of the polynomially weighted average algorithm) with multiple learning rates. These bounds are in terms of excess losses, the differences between the instantaneous losses suffered by the algorithm and the ones of a given expert. We then demonstrate the interest of these bounds in the context of experts that report their confidences as a number in the interval [0,1] using a generic reduction to the standard setting. We conclude by two other applications in the standard setting, which improve the known bounds in case of small excess losses and show a bounded regret against i.i.d. sequences of losses.
1. Introduction
The paper develops expert-dependent second-order regret bounds based on instantaneous excess losses, addressing limitations of uniform variance bounds and hindsight-dependent tuning. It extends Prod with multiple learning rates and reduces their tuning cost to O(ln ln T), then applies the bounds to confidence-weighted experts and other settings.
- Tuning challenge: Optimizing the desired bound requires hindsight because the optimal η depends on cumulative loss quantities, creating the impossible-tuning problem.Earlier improved bounds suffer from the same sequential-tuning issue.
- Second-order bounds: Second-order bounds can use variance-like quantities, but uniformity fails to reflect that competing with some experts is harder than with others.The cited variance bound is achieved with a time-varying learning rate, yet its uniform form is a central drawback.
- Excess losses: The paper targets expert-dependent regret bounds based on instantaneous excess losses ℓk,t − bℓt rather than uniform bounds.These quantities measure the difference between an expert’s instantaneous loss and the learner’s loss.
- Method: The proposed Prod variant assigns one learning rate ηk to each expert and reduces the resulting multiplicative cost from O(K ln T) to O(ln ln T).The second innovation uses new techniques for sequentially tuning multiple learning rates.
- Applications: The bounds extend to experts reporting confidences in [0, 1], yielding a confidence-regret bound that scales optimally with each expert’s confidence.The paper also reports improved bounds for small excess losses and constant regret for i.i.d. losses.
2. A new regret bound in the standard setting
This section develops ML-Prod and related adaptive analyses for second-order regret bounds, while addressing the difficulty of sequentially tuning multiple expert-specific learning rates. The resulting bounds support an empirical-variance formulation in terms of excess losses.
- Algorithm: The paper extends the Prod algorithm to use multiple learning rates, one associated with each expert.The algorithm is presented as ML-Prod with an initialization of nonnegative weights summing to one.
- Fixed-rate bound: For losses in [0, 1] and learning rates ηk ≤ 1/2, Theorem 1 bounds the cumulative loss of ML-Prod for every loss sequence.The theorem provides the fixed-learning-rate starting point for the subsequent adaptive analysis.
- Adaptive tuning: Optimizing the theorem’s bound is not directly sequential because K cumulative quantities must be controlled simultaneously.A doubling-trick approach would trigger new regimes whenever one quantity crosses a dyadic threshold, adding overhead.
- Empirical variance: A consequence of the new bound is a formulation in terms of the empirical variance of the excess losses ℓk,t − bℓt.For losses in [0, 1], Proposition 2 derives this consequence from the preceding bound.
3. Algorithms and bound for parameters varying over time
The paper removes the need for preliminary knowledge of expert-specific excess-loss sums by using time-varying learning rates, incurring only an O(ln ln T) factor. It develops adaptive multiplicative and polynomially weighted algorithms with multiple learning rates.
- Adaptive learning rates: The optimized bound requires tuning each expert’s learning rate using preliminary knowledge of its excess-loss sum.The paper identifies this requirement as the obstacle to a fully sequential procedure.
- Adaptive learning rates: Time-varying learning rates ηk,t remove this requirement at a cost of only an O(ln ln T) multiplicative factor.The rates are chosen sequentially and vary separately for each expert.
- Multiplicative updates: Algorithm 2, Adapt-ML-Prod, generalizes the multiple-learning-rate Prod method to nonincreasing expert-specific learning-rate sequences.Its analysis handles powers ηk,t/ηk,t−1 that differ across experts.
- Multiplicative updates: The adaptive analysis pays an additional price determined by how much the time-varying learning rates change.This term is explicitly attributed to using different time-varying rates.
- Polynomial potentials: A polynomially weighted-average algorithm with multiple learning rates offers an alternative whose analysis is simpler, though its dependencies on K and T remain poor.The construction uses polynomial potentials of order p = 2.
4. First application: bounds with experts that report their confidences
The paper reduces confidence-based prediction to standard prediction with modified losses, transferring second-order regret bounds to experts whose confidences vary by expert. This yields bounds that scale optimally with individual confidences rather than with other experts’ confidences.
- Confidence regret: Confidence regret accounts for each expert’s confidence and reduces to regular expert-advice regret when all confidences equal 1.Binary confidences recover the setting of sleeping or specialized experts.
- Motivation: Existing confidence-regret bounds scale as √λk when expert k’s confidences are multiplied by λk, rather than scaling linearly with λk.This is the stated shortcoming of the available bound for expert-dependent confidences.
- Result: The resulting bound scales optimally with the confidences of each expert.The paper presents this as the first bound with that confidence dependence.
- Scope: The treatment considers linear losses, with extension to convex losses described as immediate via the gradient trick.The paper notes that the same extension applies to experts reporting confidences.
- Generic reduction: A generic reduction runs a standard expert-advice algorithm on modified losses and converts its weights into a distribution supported on active experts.The induced confidence regret equals the standard regret on the modified losses.
5. Other applications: bounds in the standard setting
The paper applies its second-order excess-loss bound to improve guarantees in the standard setting, including small-excess-loss regimes and i.i.d. losses. Under an i.i.d. assumption, the bound yields constant-order regret.
- Improvement for small excess losses: Excess-loss bounds improve the standard small-loss guarantee by using ℓk,t − bℓt instead of plain expert losses.The resulting improvement remains meaningful even when the loss range has a < 0.
- Improvement for small excess losses: Translations of losses do not affect the new bound because excess losses are invariant under common shifts.Specifically, (ℓk,t − a) − (bℓt − a) = ℓk,t − bℓt.
- Analysis of time-varying bounds: The analysis also develops peeling techniques whose overhead is reduced to terms of order ln ln T or less than a constant in the relevant case.These techniques address the analysis of time-varying learning rates.
- Stochastic (i.i.d.) losses: Under the stated i.i.d. loss assumption, any algorithm satisfying the new second-order bound achieves expected regret of order O(ln K).A corresponding high-probability regret bound is also established.
- Stochastic (i.i.d.) losses: The i.i.d. result relies on martingale concentration using conditional variance rather than only a deterministic cumulative-variance bound.The proof uses a Bernstein-Freedman-type result and develops techniques for predictable, time-varying learning parameters.
A.1. Proof of Lemma 10
The supplied passage contains only the fragment “a, which was to be shown,” and does not state the proof’s argument or conclusion.
- The passage is an isolated proof-ending fragment rather than a complete proof step.It begins with “a, which was to be shown.”
- No lemma statement, intermediate reasoning, or mathematical result is present in the passage.
- The excerpt therefore provides no substantive information about Lemma 10’s proof.
A.2. Proof of Theorem 3
The proof of Theorem 3 uses an induction argument, a learning-rate inequality, and upper and lower bounds on ln WT to derive the theorem’s regret inequality.
- Proof of Theorem 3: The auxiliary inequality x ≤ x^α + (α − 1)/e is proved using convexity when x < 1.The proof bounds x ln x below by −1/e on (0,1).
- Proof of Theorem 3: The proof begins by establishing the theorem’s target through induction over time.The induction step uses the weight update and instantaneous regret quantities rk,s = bℓs − ℓk,s.
- Proof of Theorem 3: The induction step applies the auxiliary inequality with α = ηk,t/ηk,t+1, relying on nonincreasing learning rates.This relation controls the changing expert-specific learning rates.
- Proof of Theorem 3: Combining the upper and lower bounds on ln WT and rearranging yields Theorem 3’s inequality.The supplied proof passage identifies this as the final step.
A.3. Proof of Corollary 4
The proof of Corollary 4 controls the regret using nonincreasing expert-specific learning rates and bounds the resulting rate-change terms.
- Proof of Corollary 4: The analysis bounds learning-rate changes using concavity of the square root and an auxiliary lemma for sums involving a nonincreasing function.The proof also treats the second term in the displayed bound separately before substitution.
- Proof of Corollary 4: The proof introduces a positive constant γk as part of the regret analysis.Its value is defined by the subsequent analysis.
- Proof of Corollary 4: Nonincreasing learning rates allow the theorem’s first inequality to be applied to upper-bound Rk,t.The proof then separates terms according to the behavior of each expert’s learning-rate sequence.
A.4. Proof of Theorem 5
The proof uses a geometric projection argument with time-varying, expert-specific learning rates. A diagonal norm and projection properties control the cumulative instantaneous regrets and yield the theorem’s bound.
- Geometric setup: The proof equips R^K with a diagonal-matrix inner product and norm, then uses a projection onto the nonnegative orthant.The projection is independent of the admissible diagonal matrix and equals the vector of componentwise positive parts.
- Regret control: The projection and norm inequalities bound the squared norm of the cumulative regret vector through inner-product identities tied to the algorithm’s update.The argument expands the squared norm and invokes the update rule to simplify the inner product.
- Adaptive rates: For each round, the proof forms D_t from the expert-specific learning rates η_k,t, which are non-increasing over time for each expert.This monotonicity supplies the comparison needed in the norm inequalities.
- Conclusion: Substituting the terminal learning rates completes the proof for every expert k.The final steps apply the derived inequalities and then substitute η_k,T.
A.5. Proof of Theorem 12 (variation on the Bernstein–Freedman inequality)
The proof establishes a variation of the Bernstein–Freedman inequality using a monotone predictable sequence and exponential-moment control. It then applies this machinery to reductions from convex aggregation and confidence-weighted experts to linear losses.
- Bernstein–Freedman inequality: The proof uses the increasing function ϕ to control conditional exponential moments of bounded, conditionally centered random variables by their conditional variance.The argument relies on ϕ(ΛX) ≤ ϕ(Λ), conditional integration, and 1 + u ≤ e^u.
- Bernstein–Freedman inequality: A non-increasing sequence of predictable random variables Λ_t defines exponential-process terms H_t whose expectations are bounded before applying Markov’s inequality.The proof initializes H_0 = 1 and proceeds inductively through the resulting bounds.
- Bernstein–Freedman inequality: The resulting inequality is completed by choosing x appropriately and bounding x/Λ_T using the definition of Λ_T as a minimum.These steps establish the stated theorem after combining the intermediate inequalities.
- Reduction to linear losses: Convex aggregation is reduced to linear losses through the gradient trick, so linear regret bounds also apply to convex combinations and confidence-reporting experts.The reduction uses convexity to relate the original losses to pseudo-losses.
- Reduction to linear losses: The reduction recovers confidence regret for point-mass combinations and transfers linear prediction bounds to the original convex setting.The construction defines pseudo-losses from ∇f_t and uses the convexity inequality.
B.2. Hedge with multiple learning rates for experts that report their confidences
This section presents Hedge with one learning rate per expert for experts reporting confidences. Its bound is optimized separately by expert, while sequential tuning is possible with only a small O(ln ln T) cost.
- Relation to prior formulation: The analysis relates the confidence setting to Blum and Mansour’s time-selection formulation, with the effective expert count changing from K to KM under duplicated experts.The two settings are described as essentially equivalent, while the coupling of experts and selection functions changes the logarithmic factor.
- Algorithm: MLC-Hedge assigns each expert its own positive learning rate and updates weights after observing the loss vector and incurring the aggregated loss.The algorithm starts from nonnegative weights summing to one and processes rounds sequentially.
- Guarantee: The confidence-regret theorem holds for arbitrary positive learning rates in [0,1] and all sequences of losses and confidences.The guarantee is stated simultaneously for every expert k.
- Guarantee: Optimizing the theorem’s bound with respect to each η_k yields the displayed expert-specific bound.The optimized expression is identified with the corresponding earlier result.
- Tuning and scope: Although hindsight optimization of η_k is unavailable in practice, the parameters can be tuned sequentially at an additional O(ln ln T) cost.The paper notes that this online tuning is not worked out in the cited Blum–Mansour bound.
- Tuning and scope: The paper argues that the MLC-Hedge bound likely cannot be obtained by first analyzing a standard-setting algorithm and then applying the generic confidence reduction.This is presented as evidence that the main-body approach is more general.