Second-order Quantile Methods for Experts and Combinatorial Games

1 Introduction

• The introduction frames adversarial regret as a worst-case benchmark and describes prior work that improves it through second-order bounds or quantile guarantees.Second-order approaches exploit variance; quantile approaches reduce dependence on the number of experts when multiple experts perform well.Source: §1 · pp. 1–2
• Second-order bounds improve with small cumulative variance, while quantile bounds replace dependence on K with the reciprocal prior mass of a well-performing expert subset.The two gains are complementary, but prior approaches used incompatible techniques.Source: §1 · pp. 1–2
• Squint combines second-order, variance-sensitive regret guarantees with quantile guarantees for every subset of experts.The bound can imply small regret when weights concentrate, as when one expert is clearly better than the others.Source: §1 · p. 2
• The log-uniform prior yields an efficient Squint algorithm with a learning-rate overhead of ln ln T and only K operations per round.The CV prior achieves an overhead of ln ln V^K_T but does not have an efficient implementation.Source: §1 · p. 2
• Component iProd extends second-order quantile regret bounds to combinatorial games, relating an average concept's coordinate-wise regret to averaged variance and prior entropy.The method is collapsed: it maintains coordinate-wise first- and second-order statistics rather than statistics for each concept, avoiding the range-factor problem.Source: §1 · p. 3

1.1 Related work

• Earlier online-learning work either tuned learning rates over time or aggregated multiple rates using varied schemes, including defensive forecasting and budgeted timesharing.The paper situates its approach among methods for choosing or aggregating learning rates.Source: §1.1 · p. 3

• Squint averages over priors on experts and learning rates in a potential over instantaneous-regret sequences, choosing predictions to keep it non-positive.The potential decreases as the algorithm proceeds.Source: §2 · pp. 3–4
• Squint’s potential yields a variance-with-quantiles regret bound for every reference subset of experts.The guarantee holds for any loss sequence.Source: §2 · p. 4
• Useful learning-rate priors must place mass near the relevant rate and permit efficient closed-form integrals for computing the weights.Source: §2 · p. 4
• Squint tracks cumulative regrets and their squared values, supporting second-order bounds; it is anytime and its predictions are unaffected by inserted zero-loss rounds.It has no built-in dependence on an eventual horizon.Source: §2 · p. 4
• Squint’s weights can be viewed as exponential weights under a modified prior, and its closed-form evaluation is an advantage over iProd except at fixed learning rates.With a point-mass prior on the learning rate, that computational advantage disappears.Source: §2 · p. 4

3 Three Choices of the Prior on Learning Rates

• The prior choices are evaluated by how much probability mass they place near the optimized learning rate; the expert prior π remains unrestricted.The proofs develop each regret bound by assessing prior mass around that rate.Source: §3 · p. 5

3.1 Conjugate Prior

• For constant conjugate-prior parameters, Squint’s learning-rate overhead is of order ln V^K_T because the prior lacks sufficient mass near the optimal rate.The bound has the desired second-order form, but V^K_T is not known in advance.Source: §3.1 · p. 5, §3.2 · p. 5

3.2 A Good Prior in Theory

• The CV prior achieves the desired quantile and variance guarantees with overhead proportional to ln ln V^K_T, which the authors regard as essentially constant.Its analysis retains the optimal multiplicative constant apart from the prior’s additional 1/ln2(η) factor.Source: §3.2 · p. 6

3.3 Improper Prior

• The improper 1/η prior cancels with the η in Squint’s rule, keeping predictions well-defined and restoring a closed-form weight integral.Its regret bound has learning-rate overhead 2 + ln(T + 1).Source: §3.3 · p. 6

4 Component iProd: a Second-order Quantile Method for Combinatorial Games

• The combinatorial method targets second-order and quantile improvements without the suboptimal loss-range dependence of treating each concept as an expert.That separate-expert application can make the variance term as large as K²T, although KT suffices.Source: §4 · p. 7

4.1 Component Bayes

• Component Bayes supplies a combinatorial mix-loss subroutine, enabling Component iProd to aggregate it over learning rates and obtain second-order quantile regret.Its practicality depends on computing a binary relative-entropy projection onto U; compact polytope representations can support off-the-shelf optimization.Source: §4 · pp. 7–8, §4.1 · p. 9

4.2 Component iProd

• Component iProd applies Component Bayes to each learning rate and combines the resulting predictions, with a regret guarantee for every η on the grid and comparator v.The regret vector is extended to usages and coordinate losses in the combinatorial setting.Source: §4.2 · pp. 9–10
• The algorithm uses a discrete learning-rate prior, trading lower mistuning overhead from more grid points against computation that grows linearly with grid size.The analysis shows that exponential spacing suffices.Source: §4.2 · p. 10
• Component iProd’s final theorem bounds regret against any comparator v in a closed convex U using a uniform prior on an exponentially spaced grid and an arbitrary prior vector π.The bound includes a term 4△2(v∥π) and a grid-dependent term K max{4 ln⌈1 + log2 T⌉, 1}.Source: §4.2 · p. 10
• The learning-rate cost in Lemma 7 is multiplied by ambient dimension K, a factor the authors could not reduce to one.Removing division by K from the potential makes its loss dependence polynomial and prevents it from remaining nonpositive even for K = 2.Source: §4.2 · p. 10

5 Conclusion and Future Work

• Squint and Component iProd both use potentials that integrate over learning rates to learn an appropriate rate.The authors identify a unifying account of when learning rates can be learned as a question for future work.Source: §5 · p. 10
• The authors report no known variance-based lower bounds for these adaptive methods and call for matching lower bounds.Existing lower bounds described here do not apply to methods that adaptively tune their learning rate.Source: §5 · p. 10
• The analysis assumes losses are normalized to [0, 1]; incorporating techniques that adapt automatically to loss range remains open.The cited second-order methods that avoid this normalization do not themselves resolve how to incorporate such adaptation into this paper’s methods.Source: §5 · p. 11

A Proofs

• The appendix section collects proofs omitted from Sections 3 and 4.Source: A Proofs · p. 13

A.1 Theorem 2

• The proof uses Jensen’s inequality to obtain an intermediate bound.Source: §A.1 · p. 13
• For η̂ ≤ 1/2, the proof chooses v = η̂ and u = η̂ − 1/(2V).Source: §A.1 · p. 13
• For η̂ > 1/2, equivalent here to R > V, the proof uses a separate case argument to derive the bound.Source: §A.1 · p. 13

A.2 Theorem 3

• The proof also separates the case R ≥ 2V, reducing the other cases to V ≤ 4 or V ≥ 4.Source: §A.2 · p. 14
• For η̂ ≤ 1/2, the proof chooses v = η̂ and u = η̂ − 1/(2V).Source: §A.2 · p. 14
• For η̂ > 1/2, equivalent to R > V, the proof sets v = 1/2 and applies the resulting inequality.Source: §A.2 · p. 14

A.3 Theorem 4

• With the improper prior, the proof cannot pull the constant 1 out of the potential’s integral over η.Source: §A.3 · p. 14
• For experts outside K, the proof establishes a bound using an arbitrary ε in [0, 1/2].Source: §A.3 · pp. 14–15
• For experts in K, the proof uses η̂ = R/(2V) and considers separate cases around η̂ = 1/2.Source: §A.3 · p. 15
• The proof then combines the bounds, using V ≤ T, to conclude the stated result.Source: §A.3 · p. 15

A.4 Lemma 5

• The cumulative mix loss regret is bounded using the nonnegativity and generalized Pythagorean property of the Bregman divergence Δ².Source: §A.4 · p. 16

A.5 Lemma 6

• The last equality in the preceding derivation follows from the design of the weights in (23).Source: §A.5 · p. 16

A.6 Lemma 7

• Component iProd ensures Φ(r₁:T) ≤ 0, which the proof uses to establish the result for any η.Source: §A.6 · p. 17

A.7 Theorem 8

• An exponentially spaced learning-rate grid ensures a grid point for the relevant αη.The proof uses this grid in establishing its bound.Source: §A.7 · p. 17
• 4V^v_T ≤ Δ²(v∥π) + K ln⌈1 + log2 T⌉.The proof also relates R^v_T and V^v_T in its cases and says this yields (27).Source: §A.7 · p. 17

B Numerical stability

• When both erf arguments are extreme on the same side, Taylor expansion around R = ±∞ provides an alternative to direct evaluation.Within the stated stable range, the expression can be evaluated directly; the zeroth-order expansion is negative for R ∈ [0, V/2], which lies in that range.Source: B Numerical stability · p. 17