Pith. sign in

REVIEW 2 major objections 5 minor 79 references

Adaptive Bayes exactly tracks information over intrinsic time

T0 review · 2 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Bayesian and multiplicative-weights updates pay an exact information ledger: excess loss equals a round’s uncertainty cost plus a drop in distance to the comparator, measured on a pathwise clock called intrinsic time.

desk verdict Exact pathwise ledger for variable-temperature Bayes/Hedge is real and carefully bookkept; breadth claims and luckiness rest on stated premises, not on a broken core. read the letter →

arxiv 2607.08789 v1 pith:KDUNRKBG submitted 2026-06-26 cs.LG cs.ITmath.ITmath.STstat.MLstat.TH

Akshay Balsubramani This is my paper · ORCID
classification cs.LGcs.ITmath.ITmath.STstat.MLstat.TH MSC 68T0568Q3262F15
keywords onlinelearningmultiplicativeweightsBayesianupdatingregretdecompositionintrinsictimePAC-BayesadaptiveratesHedge
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the regret of Bayes-style and multiplicative-weights updates is not merely bounded by information quantities, but equals an exact accounting identity on every realized path. On each round, the learner’s excess loss against any chosen benchmark splits into an immediate payment for the uncertainty the round exposes and a reduction in relative entropy to that benchmark. Summing those balances produces two exact cumulative decompositions, depending on whether the update is recomputed from the original prior at a new temperature or applied only from the current weights. The cumulative payments define intrinsic time: a difficulty clock revealed by the sequence itself rather than imposed by the horizon. Because the identities are exact, easy stochastic or low-noise regimes show up as the clock self-bounding, not as slack in a worst-case proof. The same ledger covers Hedge, optimistic side information, boosting, continuous-action optimization, bandits, and repeated games.

What carries the argument

The one-step information balance: excess composite loss equals the centered mixability gap plus a scaled drop in KL divergence to the comparator. Composed two ways, it yields the retempered identity with drift and terminal free-energy terms, and the local identity with cumulative normalization and terminal mass.

What would settle it

On a fixed synthetic loss path, recompute the three terms of the retempered decomposition and check whether their sum equals composite-loss regret to machine precision for several comparators and schedules; a systematic residual larger than numerical noise would refute the identity.

Watch

Extended reading notes

Core claim

For any predictable positive learning-rate schedule and any comparator distribution, the composite-loss regret of a prior-retempered Bayes update equals temperature-change drift plus terminal comparator information plus the sum of learning-rate times per-round intrinsic-time increments; a parallel exact three-piece identity holds for the local pressure-target update. The per-round increment is the nonnegative finite-temperature cumulant of the played distribution, not a proxy variance.

Load-bearing premise

Each round’s exponential normalizer must be finite at the chosen temperature; for the fast expected-rate claims, a strong low-noise condition around the comparator must also hold, and the paper notes that condition is usually empty for diffuse mixtures.

Editorial extensions

If this is right

  • Favorable stochastic or low-noise sequences appear as self-bounding intrinsic time inside the same pathwise identity, without separate algorithms or proofs.
  • Side information, optimism, and compensators only change the residual sequence fed to the same Bayes update; improved regret is reduced unexplained information.
  • Schedules can be designed from the revealed clock (square-root on cumulative intrinsic time, or pressure targets that hit a one-step free-energy level) rather than from a known horizon.
  • The same exact ledger transfers unchanged to boosting margins, continuous-action online convex optimization, contextual bandits with estimated losses, and repeated-game regret matching.
  • Classical first- and second-order regret bounds are successive relaxations of one exact cumulant term, so the order is an analyst choice, not a different algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the ledger is truly schedule- and geometry-agnostic once composite losses are fixed, many “new” adaptive experts algorithms may amount to different controllers on the same two update cells rather than new proof objects.
  • The pressure-target view suggests treating one-step free-energy calibration as a thermostat: non-equilibrium exchange relations could give exact fluctuation identities for local updates.
  • A practical diagnostic for deployed sequential reweighting (including preference and post-training pipelines) is to plot the three share terms over time; equal terminal regret can hide very different pay/drift/info mixes.
  • Extending simultaneous single-copy quantile adaptation while keeping the exact cumulant under the played distribution would close the remaining gap between fixed-budget PAC-Bayes control and fully parameter-free scaling-time results.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper develops an exact pathwise information-accounting identity for Bayesian and multiplicative-weights updates. On each round, excess composite loss to any comparator ρ equals an immediate centered cumulant payment δ_t(c) (or η_t Q_t(c)) plus a KL transport term. Composing these one-step balances yields two exact three-piece cumulative decompositions: for the prior-retempered update, R_T^c(ρ) = D_T + B_T(ρ) + Σ_t η_t Q_t(c) (Theorem 2.10 / Eq. 18), with intrinsic time V_T(c) := Σ Q_t(c), temperature-change drift D_T, and terminal comparator information B_T(ρ); and a parallel identity for the local pressure-target recursion (Proposition 3.13 / Corollary 3.10). The same calculus is applied to side information, shifting/quantile comparators, stochastic luckiness, continuous OCO, boosting, bandits/feedback graphs, and repeated games. Empirical diagnostics in §7 and Appendix C report machine-precision residual checks of the prefix identities and envelope tightness.

Significance. If the identities hold as stated, the contribution is a genuine unifying ledger rather than another family of upper bounds: favorable regimes appear as self-bounding of realized intrinsic time, and many standard dichotomies (first- vs second-order, hard vs easy sequences, full vs partial feedback) become different readings of the same exact split. The manuscript supplies the main algebraic proofs in Appendix B, machine-precision residual checks of the prefix identities across (K,T) grids, and a clear 2×2 design space (RET/LOC × SQRT/PRESS). That combination of exact bookkeeping, schedule design from the same clock, and empirical verification of the identities is a real advance over variance-proxy analyses that introduce Q_t only after inequalities. The breadth of applications is secondary to the core ledger claim, which is load-bearing and carefully scoped to finite one-step log-normalizers.

major comments (2)
  1. §4.5, Condition (74) and Theorem 4.9 / Corollary 4.11: the comparator-centered low-noise condition is load-bearing for the constant expected-regret claims, yet the paper itself notes it is practically vacuous for most non-degenerate diffuse posteriors (forcing near-deterministic losses on the support of ρ). The fixed-rate and predictable-rate luckiness theorems therefore deliver meaningful constant rates primarily for point-mass comparators. The abstract and §1.5 still present “favorable stochastic or low-noise regimes appear as self-bounding properties of the realized intrinsic time” as a general selling point of the exact decompositions. Either restrict the fast-rate claims explicitly to point comparators (or highly degenerate environments) in the abstract/contributions, or supply a non-vacuous condition that covers diffuse ρ without collapsing to the point-mass case.
  2. §1.5 item 4 and §5–6: the claim that “the same calculus covers … continuous priors, boosting, online convex optimization, contextual bandits, and repeated games” is true at the level of formal transfer of the one-step balance, but several extensions are thin. Continuous-action OCO (Theorem 5.11 / Corollary 5.12) relies on an expensive density update and barycenter whose computational cost is acknowledged but not quantified; the bandit section (Theorems 6.1–6.6) correctly isolates martingale and bias terms yet does not report numerical residual checks of the estimated-loss identity comparable to the full-information checks in §7/Appendix C. For a paper whose central selling point is exact pathwise accounting, either add residual diagnostics for the bandit/EXP4-IX and continuous-OCO identities or soften the “same in every case” language so that the load-bearing claim remains the finite-exp
minor comments (5)
  1. Algorithm 1 and §3.1: the crossed cells RET-PRESS and LOC-SQRT are defined but only lightly analyzed; a short remark on when a practitioner would prefer them over the main pairings would help.
  2. Notation: pt (played), qt (generic one-step), qt,η (temperature-indexed) is introduced late; a one-line glossary near the start of §2 would reduce friction.
  3. §7 / Appendix C: the paper reports extensive numerical residual checks and baseline comparisons, but the main text does not state whether code is released; a reproducibility note would strengthen the empirical claims.
  4. Table 1 is a useful reading guide but is long; consider moving part of it to the appendix or tightening the “Conventional manifestation” column.
  5. Typos and polish: occasional double spaces and long sentences in §1 and §8; a light copy-edit pass would improve readability without changing content.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: central identities are algebraic bookkeeping from standard Gibbs/one-step balances, not fitted or self-referential predictions.

full rationale

The paper's strongest claims (Theorem 2.10 / Eq. 18 for the prior-retempered update; Proposition 3.13 and Corollary 3.10 for the local pressure-target update) are exact pathwise equalities obtained by composing the one-step mixed-coincidence identity (Corollary 2.3) with the Gibbs variational identity (Lemma 2.6) and terminal potential (Lemma 2.7). Q_t(c) is defined directly as the scaled one-round mixability gap φ_t(η_t)/η_t under the played distribution; the cumulative sum η_t Q_t plus explicit drift D_T and terminal B_T(ρ) is then shown by telescoping algebra to equal composite-loss regret. This is definitional accounting, not a free-parameter fit that is later called a prediction. Schedule constants (C, Γ, a_t) are explicit controller choices whose consequences are derived, not hidden parameters that force the identity. Empirical checks confirm the algebra to machine precision (as expected for identities) and do not fit coefficients to data. There are no load-bearing self-citations, uniqueness theorems imported from the author, or ansatzes smuggled via citation that close the derivation. The work is self-contained against its stated domain (finite one-step log-normalizer). Minor renaming of the cumulative cumulant as 'intrinsic time' is presentational, not circular. Score 0 is therefore appropriate.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

The central identities rest on standard relative-entropy and log-partition calculus for exponential reweighting, plus the modeling choice that side information is folded into composite losses before the Bayes update. Free parameters appear only in schedule controllers (budget Γ, constant C, pressure targets), not inside the identity itself. Intrinsic time and the two update geometries are definitional constructs, not new physical entities requiring external evidence.

free parameters (3)
  • comparator budget Γ = problem-dependent; dyadic grid Γ_j = 2^j in Thm. 4.7
    User-chosen complexity budget for the square-root schedule and simultaneous quantile controller; anchors η_t and the terminal KL allowance.
  • square-root schedule constant C = 1/√2 (default)
    Tunes the balance Γ/η + ηV; default C = 1/√2 minimizes the leading coefficient 2C + C^{-1} in the upper envelope.
  • pressure target a_t (or information quota β_t) = instance-dependent; unit-potential a_t=0 is a special case
    Per-round free-energy/pressure level for LOC-PRESS / RET-PRESS; chosen by the analyst or an information-fraction rule, not identified by the identity.
assumptions (4)
  • standard math Relative entropy and Gibbs variational identities for finite (or continuum) exponential families / softmax posteriors.
    Lemmas 2.6–2.7 and the one-step mixed-coincidence identity are standard KL/log-partition algebra.
  • domain assumption Predictable positive learning rates η_t and finite one-step log-normalizers at those rates.
    Required for the update and for Q_t to be well-defined; stated throughout §2–3 and Table 1.
  • domain assumption Side information, optimism, and partial feedback enter only through composite or estimated losses fed to the same Bayes update.
    Composite-loss reduction (Thm. 2.1–2.2) is the modeling gateway for all extensions.
  • ad hoc to paper Comparator-centered low-noise condition E[(c_t(i)-⟨ρ,c_t⟩)^2] ≤ κ_ρ (μ(i)-⟨ρ,μ⟩) for stochastic luckiness.
    Definition (74) is the paper’s PAC-Bayes analogue of pointwise low noise; needed for constant expected regret, and admitted to be restrictive for diffuse ρ.
invented entities (2)
  • Intrinsic time V_T(c) := Σ_t Q_t(c) independent evidence
    purpose: Pathwise uncertainty clock equal to the cumulative exact finite-temperature cumulant paid by the update.
    Defined from the algorithm’s own log-mgf; not a new physical object, but the paper’s central accounting construct. Independent evidence is the algebraic identity and numerical residual checks, not an external measurement.
  • 2×2 adaptive Bayes design space (RET/LOC × SQRT/PRESS)
    purpose: Organizes update geometry versus rate controller into four named algorithms.
    Taxonomy of existing and proposed schedule pairings; useful but not an ontological claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Bayes exactly tracks information over intrinsic time." pith.science (2026). https://pith.science/paper/KDUNRKBG

@misc{pith2026260708789,
  author       = {Pith},
  title        = {Pith review of: Adaptive Bayes exactly tracks information over intrinsic time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KDUNRKBG}},
  note         = {Machine review of arXiv:2607.08789}
}
read the original abstract

Bayesian and multiplicative-weights updates reweight experts, models, or actions from sequential feedback. We show that the regret of any such update obeys an exact information-accounting identity. On each round, the learner's excess loss to any chosen comparator is the sum of an immediate payment for the uncertainty exposed by the round and a reduction in the information distance from the learner's current weights to the comparator. The cumulative payment defines a pathwise uncertainty clock, the \emph{intrinsic time} of the realized sequence. Summing one-step balances yields two exact adaptive decompositions of cumulative regret, one for each natural way of composing the update across rounds. Because the decompositions are exact rather than upper bounds, favorable stochastic or low-noise regimes appear as self-bounding properties of the realized intrinsic time, not as slack in worst-case analyses. The same calculus covers Hedge, optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games: the pathwise account is the same in every case.

Figures

Figures reproduced from arXiv: 2607.08789 by the authors.

Figure 1
Figure 1. Regret decomposition on a regime-switching mixed-character sequence (K = 8, T = 2000; four blocks of length 500 alternating i.i.d. stochastic / cycling-adversarial / i.i.d. stochastic / cycling-adversarial). Three rows correspond to the cumulative shares ω info t , ω pay t , ω drift t on a shared time axis. Within each row, color encodes the learning-rate schedule (RET-SQRT, fixed η = 0.1, fixed η = 1.0) and line st… view at source ↗
Figure 2
Figure 2. Same regret, different decomposition. Top: cumulative composite-loss prefix regret Rc t (ρ)for three schedules— RET-SQRT, the pressure-target line search, and fixed η = 0.43—on the martingale family with optimistic side information (K = 8, T = 2000, 12 seeds). All three reach terminal regret within 1.9% of each other (Rc T = +7.84, +7.99, +7.80). Bottom: stacked-share decomposition (ω pay, ωdrift, ωinfo) for each sc… view at source ↗
Figure 3
Figure 3. Regret-decomposition shares on the i.i.d. stochastic family (K = 8, T = 2000). Rows pair the three algorithm classes; columns pair their variants. Shared axes: round t on the bottom row, decomposition share on the left column. Comparator-information ω info (green) dominates the first ∼ 100 rounds while the algorithm concentrates mass on the leading expert; the intrinsic-time share ω pay (blue) and the drift share ω … view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Regret-decomposition shares on the martingale family with optimistic side information ut = −mt. The com￾posite loss ct = ℓt−mt is the noise residual, so the intrinsic-time share is uniformly small across schedules; the predictable component is absorbed into the off-dia…
Figure 5
Figure 5. Figure 5: Regret-decomposition shares on the cycling-adversarial family (best expert rotates every 50 rounds). The intrinsic-time share ω pay dominates throughout because VT (c) grows linearly in T; the comparator-information share ω info is non-negligible because the cumulative…
Figure 6
Figure 6. Figure 6: Regret-decomposition shares on the mixed-character sequence (i.i.d. / adversarial / i.i.d. / adversarial blocks, each of length 500). The dominant share switches at every block boundary even though the terminal regret number alone would average over the transitions. Wi…
Figure 7
Figure 7. Figure 7: Martingale family (T = 2000): cumulative composite-loss prefix regret Rc t (ρ) of ordinary Hedge versus the op￾timistic version with ut = −mt. The optimistic run goes deeply negative because the predictable component is absorbed into the side information. The martingal…
Figure 8
Figure 8. Figure 8: Matrix-game side-information recipe (K = 5, T = 1500, G ∈ [−1, 1]5×5 , 20-round moving-average fore￾cast). Left: predictable (sinusoidally drifting) opponent — side information shrinks ω pay t substantially. Right: Dirichlet￾i.i.d. opponent — the residual is as hard as…
Figure 9
Figure 9. Figure 9: Comparator-by-comparator check of Theorem 2.10. Top row: terminal Rc T (ρα), BT (ρα), and the ρ￾independent PT , DT , plotted against KL(ραkπ)/ηT . The two ρ-independent pieces appear as horizontal lines as re￾quired; the only piece that varies with α is BT , and Rc T …
Figure 10
Figure 10. Figure 10: Comparator-by-comparator check of the local-update prefix identity (150) on pressure-target runs (T = 1500, K = 8, eight seeds, twenty-five ρα values). Top row: terminal Rc T (ρα), Bloc T (ρα), and the ρ-independent P loc T as func￾tions of KL(ραkπ). The local drift D…
Figure 11
Figure 11. Figure 11: Exact Hoeffding slack across families (K = 8, retempered schedule). Left: log-count histogram of per-round Qt(c)/[(b − a) 2/8] = Qt(c)/(1/8) on the four families; dotted vertical line is the Hoeffding range bound. The cycling￾adversarial family has visibly heavier upp…
Figure 12
Figure 12. Figure 12: Forecast-accuracy ablation on a K = 5 matrix game with random payoff G ∈ [−1, 1]5×5 , T = 1500, and 10 seeds. Left: terminal intrinsic-time clock VT (c) = P t Qt(c); vanishes at σ = 0 as Theorem 2.10 forces, then grows monotonically as the forecast degrades. Middle: t…
Figure 13
Figure 13. Figure 13: Tightness of the second-order envelope (151) on cycling-adversarial paths. Top-left: realized Pt at T = 4000, cycle-50, six seeds; one representative envelope band overlaid. The realized payment hugs the lower bound max(0, 2C p ΓVt(c) − C 2Γ) on every seed. Top-right:…
Figure 14
Figure 14. Figure 14: Upper-side envelope of Theorem 3.2 on a single-spike construction: K = 2, π = (1/2, 1/2), Γ = log 2, C = 1/ √ 2, with ℓ1 = (0, B) and ℓt = 0 for t ≥ 2. Left: PT , upper bound, and lower bound versus Q1 on log-log axes. The realized payment PT = Q1 is exactly the domin…
Figure 15
Figure 15. Figure 15: Variance proxy is the leading-order term of Qt(c). Round-averaged residual |Qt(c) − 1 2Varpt (ct)| versus the temperature η at which Qt(c) is evaluated, on log-log axes; bands are inter-quartile ranges over eight seeds; dashed gray line is the O(η)reference. The empir…
Figure 16
Figure 16. Figure 16: Stochastic-luckiness verification (Theorem4.9 and Corollary 4.11). Left: per-expert Bernstein ratiosEb[(ct(i)− ct(k ∗ ))2 ]/(µbi − µbk∗ ) on a 20,000-round realization, log y-axis. Well-specified family (blue) sits uniformly below κbρ ≈ 0.63 (dashed blue) and below th…
Figure 17
Figure 17. Figure 17: Sleeping experts on a planted-change-point sequence with k = 4 segments of length 500 (T = 2000, K = 8). Left: cumulative regret to the best fixed expert; vertical dotted lines mark segment boundaries. Right: terminal regret to the best fixed expert. The pressure-targ…
Figure 18
Figure 18. Figure 18: Terminal regret to the best fixed expert (T = 2000, K = 8, 12 seeds, mean with IQR). Blue bars: paper schedules; orange bars: SOTA adaptive baselines. Broken y-axis where the FTRL-Tsallis / Squint outliers would otherwise compress the paper algorithms. 102 [PITH_FULL…
Figure 19
Figure 19. Figure 19: Left: cap-binding diagnostic. Solid lines are the capped Algorithm 1 rule ηt = min{1, Cp Γ/Vt−1}; dashed are the uncapped rule. Symmetric-log y-axis to keep the uncapped i.i.d. trajectory legible. Right: sensitivity of the retem￾pered schedule to Γ on three families. …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

79 extracted references · 12 canonical work pages

  1. [1]

    Schapire

    Amit Agarwal, Elad Hazan, Satyen Kale, and Robert E. Schapire. Algorithms for portfolio management based on the newton method. In International Conference on Machine Learning (ICML), 2006. doi: 10.1145/1143844.1143846

    work page doi:10.1145/1143844.1143846 2006

  2. [2]

    Online learning with feedback graphs: Beyond bandits

    Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and T omer Koren. Online learning with feedback graphs: Beyond bandits. Conference on Learning Theory (COLT), 2015

    2015

  3. [3]

    The multiplicative weights update method: a meta-algorithm and appli- cations

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and appli- cations. Theory of Computing, 8:121–164, 2012. doi: 10.4086/toc.2012.v008a006

    doi:10.4086/toc.2012.v008a006 2012

  4. [4]

    Uci machine learning repository, 2007

    Arthur Asuncion and David Newman. Uci machine learning repository, 2007. URL https://archive.ics.uci. edu/ml

    2007

  5. [5]

    P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. doi: 10.1137/S0097539701398375. Source-bbl-verified on 2026-05-24; lifted from source paper’s bbl at ingest (bibvac-lifted-from=ACBFS02)

    doi:10.1137/s0097539701398375 2002

  6. [6]

    Sharp finite-time iterated-logarithm martingale concentration

    Akshay Balsubramani. Sharp finite-time iterated-logarithm martingale concentration. arXiv preprint, 2014

    2014

  7. [7]

    From external to internal regret

    Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research , 8:1307– 1324, 2007. URL https://www.jmlr.org/papers/v8/blum07a.html

    2007

  8. [8]

    PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning , volume 56 of Institute of Mathematical Statistics Lecture Notes–Monograph Series

    Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning , volume 56 of Institute of Mathematical Statistics Lecture Notes–Monograph Series . Institute of Mathematical Statistics, Beachwood, OH, 2007. doi: 10.1214/074921707000000391

    doi:10.1214/074921707000000391 2007

Show all 79 references
  1. [9]

    On prediction of individual sequences

    Nicolo Cesa-Bianchi and Gábor Lugosi. On prediction of individual sequences. Annals of Statistics, 27(6):1865–1895,

  2. [10]

    doi: 10.1214/aos/1017939242

    doi

  3. [11]

    Prediction, Learning, and Games

    Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006. doi: 10.1017/CBO9780511546921

    2006 doi

  4. [12]

    Helmbold, Robert E

    Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, 1997. doi: 10.1145/258128.258179

    1997 doi

  5. [13]

    Improved second-order bounds for prediction with expert advice

    Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2–3):321–352, 2007

    2007

  6. [14]

    A parameter-free hedging algorithm

    Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2009

    2009

  7. [15]

    A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

    Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23(4):493–507, 1952. doi: 10.1214/aoms/1177729330

    1952 doi

  8. [16]

    Online optimization with gradual variations

    Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. InConference on Learning Theory (COLT), 2012. URL https://proceedings. mlr.press/v23/chiang12.html. 104

    2012

  9. [17]

    Thomas M. Cover. Universal portfolios. Mathematical Finance, 1(1):1–29, 1991. doi: 10.1111/j.1467-9965.1991. tb00002.x

    1991 doi

  10. [18]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of Information Theory . Wiley-Interscience, 1991. doi: 10.1002/ 0471200611

    1991

  11. [19]

    Combining online learning guarantees

    Ashok Cutkosky. Combining online learning guarantees. In Conference on Learning Theory (COLT), 2019

    2019

  12. [20]

    A. P. Dawid. Statistical theory: The prequential approach. Journal of the Royal Statistical Society. Series A , 147(2): 278–292, 1984. doi: 10.2307/2981683

    1984 doi

  13. [21]

    Grünwald, and Wouter M

    Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the leader if you can, hedge if you must. Journal of Machine Learning Research, 15:1281–1316, 2014

    2014

  14. [22]

    Forecasting electricity consumption by aggregating specialized experts

    Marie Devaine, Pierre Gaillard, Yannig Goude, and Gilles Stoltz. Forecasting electricity consumption by aggregating specialized experts. Machine Learning, 90(2):231–260, 2013. doi: 10.1007/s10994-012-5314-7

    2013 doi

  15. [23]

    Adaptive subgradient methods for online learning and stochastic op- timization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic op- timization. Journal of Machine Learning Research , 12:2121–2159, 2011. URL https://jmlr.org/papers/v12/ duchi11a.html

    2011

  16. [24]

    Foster and Rakesh V

    Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379–390, 1998. doi: 10.1093/biomet/ 85.2.379

    1998 doi

  17. [25]

    Foster and Alexander Rakhlin

    Dylan J. Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression ora- cles. In International Conference on Machine Learning (ICML), 2020

    2020

  18. [26]

    Open problem: Second order regret bounds based on scaling time

    Yoav Freund. Open problem: Second order regret bounds based on scaling time. In Conference on Learning Theory (COLT), 2016. URL https://proceedings.mlr.press/v49/freund16.html

    2016

  19. [27]

    Schapire

    Yoav Freund and Robert E. Schapire. Game theory, on-line prediction and boosting. Conference on Computational Learning Theory (COLT), 1996. doi: 10.1145/238061.238163

    1996 doi

  20. [28]

    Schapire

    Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences , 55(1):119–139, 1997. doi: 10.1006/jcss.1997.1504

    1997 doi

  21. [29]

    Schapire

    Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1–2):79–103, 1999. doi: 10.1006/game.1999.0738

    1999 doi

  22. [30]

    Schapire, Yoram Singer, and Manfred K

    Yoav Freund, Robert E. Schapire, Yoram Singer, and Manfred K. Warmuth. Using and combining predictors that specialize. In ACM Symposium on Theory of Computing (STOC), pages 334–343, 1997. doi: 10.1145/258533.258616

    1997 doi

  23. [31]

    Yoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, and Yu-Xiang Wang. A second order regret bound for NormalHedge. arXiv preprint arXiv:2602.08151, 2026

    2026

  24. [32]

    A second-order bound with excess losses

    Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. Conference on Learning Theory (COLT), 2014

    2014

  25. [33]

    The KL-UCB algorithm for bounded stochastic bandits and beyond

    Aurélien Garivier and Olivier Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Pro- ceedings of the 24th Annual Conference on Learning Theory (COLT), pages 359–376, 2011

    2011

  26. [34]

    Combining probability distributions: A critique and an annotated bibliography

    Christian Genest and James V Zidek. Combining probability distributions: A critique and an annotated bibliography. Statistical Science, 1(1):114–135, 1986. doi: 10.1214/ss/1177013825

    1986 doi

  27. [35]

    A continuous colonel blotto game

    Oliver Gross and Robert Wagner. A continuous colonel blotto game. RAND Research Memorandum RM-408 , 1950. URL https://www.rand.org/pubs/research_memoranda/RM408.html

    1950

  28. [36]

    Inconsistency of Bayesian inference for misspecified linear models, and a proposal for repairing it

    Peter Grünwald and Thijs van Ommen. Inconsistency of Bayesian inference for misspecified linear models, and a proposal for repairing it. Bayesian Analysis, 12(4):1069–1103, 2017. doi: 10.1214/17-BA1085. arXiv:1412.3730

    2017 doi arXiv

  29. [37]

    Grünwald

    Peter D. Grünwald. The Minimum Description Length Principle. MIT Press, 2007. URL https://direct.mit.edu/ books/monograph/3813/The-Minimum-Description-Length-Principle . 105

    2007

  30. [38]

    Grünwald

    Peter D. Grünwald. The safe bayesian: Learning the learning rate via the mixability gap. In Algorithmic Learning Theory (ALT 2012), volume 7568 of Lecture Notes in Computer Science , pages 169–183. Springer, 2012. doi: 10.1007/ 978-3-642-34106-9_16

    2012

  31. [39]

    David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Sequential prediction of individual sequences under general loss functions. In IEEE Transactions on Information Theory , volume 44, pages 1906–1925, 1998. doi: 10.1109/18.705569

    1906 doi

  32. [40]

    Extracting certainty from uncertainty: Regret bounded by variation in costs

    Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. In Con- ference on Learning Theory (COLT), 2010. doi: 10.1007/s10994-010-5175-x

    2010 doi

  33. [41]

    Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2):151–178, 1998. doi: 10.1023/A:1007424614876

    1998 doi

  34. [42]

    Selecting weighting factors in logarithmic opinion pools

    T om Heskes. Selecting weighting factors in logarithmic opinion pools. Advances in Neu- ral Information Processing Systems (NeurIPS) , 1997. URL https://papers.nips.cc/paper/ 1413-selecting-weighting-factors-in-logarithmic-opinion-pools

    1997

  35. [43]

    Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon

    Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymp- totic confidence sequences. The Annals of Statistics, 49(2), 2021. doi: 10.1214/20-AOS1991

    2021 doi

  36. [44]

    General linear relations between different types of predictive complexity

    Yuri Kalnishkan. General linear relations between different types of predictive complexity. Theoretical Computer Science , 271:181–200, 2002. URL https://pure.royalholloway.ac.uk/en/publications/ general-linear-relations-among-different-types-of-predictive-comp-2/

    2002

  37. [45]

    Efficient learning by im- plicit exploration in bandit problems with side observations

    T omáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by im- plicit exploration in bandit problems with side observations. In Advances in Neural In- formation Processing Systems (NeurIPS) , 2014. URL http://papers.nips.cc/paper/ 5462-efficient-learning-by...

    2014

  38. [46]

    Koolen and Tim van Erven

    Wouter M. Koolen and Tim van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory (COLT), 2015

    2015

  39. [47]

    Koolen, Dmitry Adamskiy, and Manfred K

    Wouter M. Koolen, Dmitry Adamskiy, and Manfred K. Warmuth. Putting bayes to sleep. In Ad- vances in Neural Information Processing Systems (NeurIPS) , 2012. URL https://papers.nips.cc/paper/ 4557-putting-bayes-to-sleep

    2012

  40. [48]

    Lattimore and A

    T. Lattimore and A. György. Mirror descent and the information ratio. In Conference on Learning Theory, 2021. Source-bbl-verified on 2026-05-24; lifted from source paper’s bbl at ingest (bibvac-lifted- from=LattimoreGyorgy21)

    2021

  41. [49]

    Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm.Inf. Comput., 108(2):212–261, February

  42. [50]

    doi: 10.1006/inco.1994.1009

    ISSN 0890-5401. doi: 10.1006/inco.1994.1009. URL http://dx.doi.org/10.1006/inco.1994.1009

    1994 doi

  43. [51]

    A short note on a variant of the squint algorithm

    Haipeng Luo. A short note on a variant of the squint algorithm. arXiv preprint arXiv:2603.03409, 2026

    2026

  44. [52]

    Schapire

    Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. Conference on Learning Theory (COLT), 2015

    2015

  45. [53]

    Marinov and Julian Zimmert

    T eodor V. Marinov and Julian Zimmert. The pareto frontier of model selection for general contextual bandits. In Advances in Neural Information Processing Systems (NeurIPS), 2021

    2021

  46. [54]

    Universal prediction.IEEE Transactions on Information Theory, 44(6):2124–2147, 1998

    Neri Merhav and Meir Feder. Universal prediction.IEEE Transactions on Information Theory, 44(6):2124–2147, 1998. doi: 10.1109/18.720534

    1998 doi

  47. [55]

    G. Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems, pages 3168–3176, 2015. Source-bbl-verified on 2026-05-24; lifted from source paper’s bbl at ingest (bibvac-lifted-from=Neu15). 106

    2015

  48. [56]

    No-regret learning with unbounded losses: The case of logarithmic pooling

    Eric Neyman and Tim Roughgarden. No-regret learning with unbounded losses: The case of logarithmic pooling. In Advances in Neural Information Processing Systems (NeurIPS), 2023

    2023

  49. [57]

    On the chi-square and higher-order chi distances for approximatingf -divergences

    Frank Nielsen and Richard Nock. On the chi-square and higher-order chi distances for approximatingf -divergences. IEEE Signal Processing Letters, 21(1):10–13, 2014

    2014

  50. [58]

    Coin betting and parameter-free online learning

    Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems (NeurIPS), 2016

    2016

  51. [59]

    Ortega and Daniel A

    Pedro A. Ortega and Daniel A. Braun. Generalized thompson sampling for sequential decision-making and causal inference. Complex Adaptive Systems Modeling, 2:2, 2014

    2014

  52. [60]

    Muriel Felipe Pérez-Ortiz and Wouter M. Koolen. Luckiness in multiscale online learning. In Advances in Neu- ral Information Processing Systems (NeurIPS) , 2022. URL https://proceedings.neurips.cc/paper_files/ paper/2022/hash/a0d2345b43e66fa946155c98899dc03b-Abstract-Conference.html

    2022

  53. [61]

    Manning, and Chelsea Finn

    Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. InAdvances in Neural Information Process- ing Systems (NeurIPS), 2023

    2023

  54. [62]

    On equivalence of martingale tail bounds and deterministic regret in- equalities

    Alexander Rakhlin and Karthik Sridharan. On equivalence of martingale tail bounds and deterministic regret in- equalities. In Conference on Learning Theory (COLT), 2017

    2017

  55. [63]

    Universal coding, information, prediction, and estimation

    Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions on Information Theory, 30(4):629–636, 1984. doi: 10.1109/TIT.1984.1056936

    1984 doi

  56. [64]

    A near-optimal best-of-both-worlds algorithm for online learning with feedback graphs

    Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi, and Yevgeny Seldin. A near-optimal best-of-both-worlds algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2022

    2022

  57. [65]

    Learning to optimize via posterior sampling

    Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. In Mathematics of Operations Research, volume 39, pages 1221–1243, 2014

    2014

  58. [66]

    Learning to optimize via information-directed sampling

    Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Advances in neural information processing systems, 27, 2014

    2014

  59. [67]

    A tutorial on thompson sampling

    Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1–96, 2018

    2018

  60. [68]

    Schapire and Yoav Freund

    Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012. doi: 10.7551/mitpress/ 8291.001.0001

    2012 doi

  61. [69]

    Game-Theoretic Foundations for Probability and Finance

    Glenn Shafer and Vladimir Vovk. Game-Theoretic Foundations for Probability and Finance. Wiley, 2019. doi: 10.1002/ 9781118548035

    2019

  62. [70]

    Yu. M. Shtarkov. Universal sequential coding of single messages. Problems of Information Transmission, 23(3):3–17,

  63. [71]

    URL https://www.mathnet.ru/eng/ppi811

  64. [72]

    On general minimax theorems

    Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171–176, 1958. doi: 10.2140/pjm. 1958.8.171

    1958 doi

  65. [73]

    Adaptivity and optimism: An improved exponentiated gradient algorithm

    Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In International Conference on Machine Learning (ICML) , 2014. URL https://proceedings.mlr.press/v32/ steinhardtb14.html

    2014

  66. [74]

    Syrgkanis, A

    V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems , pages 2989–2997, 2015. Source-bbl-verified on 2026-05-24; lifted from source paper’s bbl at ingest (bibvac-lifted-fro...

    2015

  67. [75]

    Tim van Erven and Wouter M. Koolen. MetaGrad: multiple learning rates in online learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 3666–3674, 2016. 107

    2016

  68. [76]

    A game of prediction with expert advice

    Vladimir Vovk. A game of prediction with expert advice. In Journal of Computer and System Sciences , volume 56, pages 153–173, 1998. doi: 10.1006/jcss.1997.1556

    1998 doi

  69. [77]

    Algorithmic Learning in a Random World

    Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World . Springer, 2005. doi: 10.1007/b106715

    2005 doi

  70. [78]

    Zimmert and Y

    J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1–49, 2021. Source-bbl-verified on 2026-05-24; lifted from source paper’s bbl at ingest (bibvac-lifted-from=ZimmertSeldin21)

    2021

  71. [79]

    Online convex programming and generalized infinitesimal gradient ascent

    Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Con- ference on Machine Learning (ICML), 2003. doi: 10.5555/3041838.3041955. 108

    2003 doi

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.