Pith. sign in

REVIEW 4 minor 53 references

Sparsity-Based Interpolation of External, Internal and Swap Regret

T0 review · 0 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read The paper claims a single, computationally efficient learning-from-expert-advice algorithm whose regret against any action modification rule scales with how simple that rule is, recovering the optimal external, internal and swap regret…

desk verdict A genuinely new instance-adaptive phi-regret bound with a solid proof; the caveats are minor and mostly presentation. read the letter →

arxiv 2502.04543 v2 pith:RB57GRH2 submitted 2025-02-06 stat.ML cs.LG

Zhou Lu , Y. Jennifer Sun , Zhiyu Zhang This is my paper · ORCID
classification stat.MLcs.LG
keywords φ-regretlearningfromexpertadviceexternalregretinternalswapHaarwaveletsparsity-adaptiveonlinequantile
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

In the expert advice problem, an algorithm's regret is measured against a set of action modification rules that transform its distribution over experts. This paper claims that one algorithm, without knowing the rule in advance, can guarantee a $\phi$-regret bound that adapts to two complexity measures of the comparator: how many experts the rule maps to a common image, and how many experts it leaves unchanged. In the worst cases of these measures the bound recovers the classical optimal rates for external, internal and swap regret at once, and in intermediate regimes it improves on every known specialized algorithm. The practical consequence is that a single computationally efficient method replaces the usual need to choose or aggregate separate regret-minimizing algorithms.

What carries the argument

The carrying mechanism is a chain of reductions. First, $\phi$-regret is turned into external regret over the space $S(d)$ of right-stochastic matrices, with loss gradients $g_t=p_t\otimes \ell_t$ (the $\phi$-to-external reduction). The paper then represents every matrix in an overcomplete basis built from Haar-wavelet row features $h\otimes e$ together with the identity matrix, converting the matrix learning problem into online linear regression on the feature coefficients. Each coefficient is learned by a comparator-adaptive one-dimensional FTRL routine with first-order gradient adaptivity, so the total regret is a sum in which a comparator contributes through the sparsity of its representation in this basis. The Haar basis makes the number of adjacent-row switches of the augmented comparator control which coefficients are nonzero, and a two-stage projection oracle maps unconstrained predictions back to $S(d)$ while preserving a regret inequality. The identity feature is included so that comparators with many fixed experts are also sparse, which yields the $\min\{d-d^{\mathrm{unif}}, d-d^{\mathrm{self}}\}$ form of the final bound.

What would settle it

Fix $d=4$ and let $\phi^*$ be the constant map to expert 1, so $d^{\mathrm{unif}}_{\phi^*}=4$ and the theorem predicts regret at most $c\sqrt{(T+d)}\,(\log d)^{3/2}$. Run Algorithm 1 with exact arithmetic fixed points against an adversary that always assigns loss 1 to every expert except expert 1; if the measured regret exceeds that bound by a factor growing with $T$, the claim is false. Alternatively, replace the exact fixed point by a power-iteration approximation with tolerance $\delta>0$: if the regret then exceeds the predicted bound by an amount that grows with $\delta$, the exact-fixed-point assumption is load-bearing.

Watch

Extended reading notes

Core claim

The central result is an instance-adaptive $\phi$-regret guarantee for the distributional expert problem. For any action modification rule $\phi^*\in S(d)$, Algorithm 1 ensures that after $T$ rounds with $T\gg d$, $$\mathrm{Regret}_T(\phi^*)\;\le\; c\,\sqrt{\min\{d-$d^{{\mathrm{unif}}$}_{\phi^*}+1,\ d-$d^{{\mathrm{self}}$}_{\phi^*}\}(T+d)}\,(\log d)^{3/2},$$ where $d^{\mathrm{unif}}_{\phi^*}$ is the largest number of experts $\phi^*$ sends to the same image and $d^{\mathrm{self}}_{\phi^*}$ is the number of experts it fixes pointwise. When $d^{\mathrm{unif}}_{\phi^*}=d$ the comparator class is the constant map behind external regret and the bound is $\tilde O(\sqrt T)$; when $d^{\mathrm{self}}_{\phi^*}=d-1$ it is the internal regret regime and the bound is again $\tilde O(\sqrt T)$; in the worst case the bound becomes $\tilde O(\sqrt{dT})$, matching the optimal swap regret rate. The same algorithm also achieves the optimal quantile regret $O\bigl(\sqrt{T\log\varepsilon^{-1}}\bigr)$. Its per-round cost is $O(d^2)$ plus one fixed-point computation of a $d\times d$ stochastic matrix, the same order as the standard swap-regret algorithm, so the adaptivity is obtained without a computational penalty.

Load-bearing premise

Each round the algorithm must compute an exact fixed point of its predicted stochastic matrix; if only an approximate fixed point is available, the per-round identity $p_t=\phi_t(p_t)$ and the proof's projection inequality can fail, so the stated regret bound is not justified.

Editorial extensions

If this is right

  • One implementation now replaces three separate algorithms: it attains the optimal external regret rate, the standard internal regret rate, and the optimal worst-case swap regret rate in their respective regimes.
  • For comparators close to constant maps or close to the identity map, the regret improves from the generic $\tilde O(\sqrt{dT})$ swap regret to roughly $\tilde O(\sqrt{kT})$, where $k$ is the number of experts the rule moves away from being identical or fixed.
  • The quantile regret bound $O(\sqrt{T\log\varepsilon^{-1}})$ is optimal up to constants and sharpens the external regret result by restoring the correct $\log d$ factor.
  • The per-round computational cost matches that of the standard swap-regret algorithm, so instance adaptivity is achieved at no extra computational expense.
  • An order-dependent refinement of the analysis gives an even stronger guarantee when the experts carry a natural ordering and the comparator has few row switches, automatically improving the bound toward $\tilde O(\sqrt T)$.

Reading between the lines

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

  • Going beyond the paper, the Haar-sparsity viewpoint suggests designing feature families for other structured comparator classes, such as hierarchical or graph-structured experts, to obtain analogous interpolating regret bounds.
  • The reliance on an exact fixed point each round likely makes finite-precision robustness the main practical question that an implementation would need to resolve before the theoretical bound holds in floating-point arithmetic.
  • The relabeling function acts as a user-supplied ordering prior; learning or permuting expert orderings online to reduce row-switch counts would be a natural extension of the order-dependent bound.
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

0 major / 4 minor

Summary. The manuscript studies φ-regret in the prediction-with-expert-advice problem. It proposes Algorithm 1, which combines the Gordon-Greenwald-Marks reduction from φ-regret to online linear optimization over stochastic matrices, an overcomplete collection of Haar-wavelet matrix features, per-feature comparator-adaptive one-dimensional FTRL, and a two-stage projection wrapper. Theorem 1 states that for every action modification rule φ* ∈ S(d), the algorithm guarantees regret O( sqrt( min{ d − d_unif(φ*) + 1, d − d_self(φ*) } · (T+d) ) · (log d)^{3/2} ), where d_unif and d_self measure how close φ* is to a constant map and to the identity, respectively. This recovers the external, internal, and swap regret regimes and, via Theorem 2, gives the optimal quantile regret bound O(√(T log ε^{-1})). The appendices contain complete proofs of the main technical lemmas.

Significance. If correct, the paper is a meaningful contribution: a single computationally efficient algorithm interpolates external, internal, and swap regret and improves on existing algorithms in intermediate regimes. The main technical novelty, Haar-wavelet matrix features that are compatible with the rank-one gradient structure of the swap-to-external reduction, is well motivated, and the proofs in the appendix are detailed and internally consistent. The parameter choices are explicit and the bound is instance-adaptive without fitting to the comparator. The main caveat is that the regret decomposition requires an exact fixed point of the predicted stochastic matrix every round; this is a standard idealization in the literature, but it means the advertised practical implementation via a generic linear-system solver is outside the theorem's formal scope unless finite-precision issues are addressed.

minor comments (4)
  1. [Section 2, first paragraph; Algorithm 1, Step 6] The exact fixed-point oracle is an explicit assumption, so Theorem 1 is established in the real-arithmetic model. The footnote citing approximate fixed-point methods (power iteration) is potentially misleading because no error analysis is given. Please add a sentence clarifying that the regret bound is not established for approximate or finite-precision solvers; with a per-round residual δ_t, the identity in Eq. (2) gains an additive term bounded by T · max_t ||δ_t||_1, and preserving the O~(√T) rate would require ||δ_t||_1 = O(1/√T) uniformly.
  2. [Abstract and Theorem 1] The abstract says the algorithm recovers the optimal O(√(T log d)) external regret when d_unif(φ*)=d, but Theorem 1 alone gives O(√((T+d)) (log d)^{3/2}) in that case; the sharper log d factor is supplied by Theorem 2's quantile regret bound, not by Theorem 1. Please clarify this logical dependency in Section 3 so the reader does not attribute the sharper external-regret rate to the general bound.
  3. [Theorem 2 statement] The interval notation 'ε∈[d^{-1}:1]' should be 'ε∈[1/d,1]' (or 'ε∈[d^{-1},1]') to avoid confusion with the integer-interval notation used elsewhere in the paper.
  4. [Section 2.1, Remark 3.1] The role of the relabeling function I is clear, but it would help to state explicitly in Remark 3.1 that Theorem 1 holds uniformly for all valid I, while the sharper order-dependent bound in Theorem 3 is the only place where the choice of I matters; this would preempt confusion about whether the main result depends on the user-supplied prior.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main regret bound is derived from a genuine reduction chain and external prior results, with no fitted parameter renamed as a prediction and no load-bearing self-citation chain.

full rationale

The paper's central claim, Theorem 1, is derived through a real chain of reductions rather than by definitional equivalence or fitted inputs. The complexity measures d_unif and d_self are new definitions, not quantities fitted to data, and the theorem's bound is obtained by constructing an augmented comparator (Lemmas B.1 and B.2), representing it sparsely over Haar-wavelet matrix features, applying a black-box comparator-adaptive one-dimensional OLO algorithm (Lemma 2.1, combining Cutkosky 2018 and ZCP22), and transferring the surrogate regret to true regret via the projection inequality (Lemma B.5) and gradient magnitude bound (Lemma B.6). None of these steps assumes the target regret bound as an input. The only self-citations by co-author Zhang are ZCP22, used as a stated external one-dimensional OLO theorem, and ZCP23, used as conceptual inspiration for feature-based dynamic regret; the paper explicitly identifies the new technical challenges (Section 1.1, 'Technical challenges') and does not import its conclusion from those citations. The fixed-point oracle issue raised by the skeptical reader is a real correctness/robustness assumption, but it is an assumption about exact arithmetic and oracle availability, not a circularity: the proof goes through conditional on that stated assumption, and the paper does not secretly assume the regret bound it claims to prove. The abstract's O(sqrt(T) log d) phrasing versus the theorem's (log d)^{3/2} factor is a presentation inconsistency, not circularity. Overall, the derivation is self-contained given standard and external prior results, so the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No data-fitted constants are used. The per-feature hyperparameters epsilon_b are set by explicit formulas from d and the relabeling function, not learned from data. The central claim rests on standard mathematical facts (Brouwer, Haar basis, comparator-adaptive OLO) and on the paper's own lemmas, which are proved in the appendix. The Haar-wavelet matrix features are mathematical basis elements, not new physical or model entities.

assumptions (4)
  • standard math Brouwer's fixed-point theorem guarantees a fixed point p_t for every stochastic matrix phi_t, and the algorithm computes it exactly each round (O(d^3) time).
    Invoked in the reduction of Section 2 and Algorithm 1 step 6. The identity p_t = phi_t(p_t) is required for Eq.(2) and for Lemma B.5; approximate fixed points are not analyzed.
  • domain assumption Loss vectors are bounded as l_t in [-1,1]^d.
    Setting of Section 1; Lemma B.6 uses this to bound |<g_t, h tensor e_j>| by 2 * sum_{i in I(h)} p_{t,i}.
  • standard math The one-dimensional comparator-adaptive OLO bound of Lemma 2.1 (combining ZCP22 Theorem 4 and Cut18 Theorem 5.8) is valid for all comparators u and all gradient sequences.
    Imported without proof; the paper's per-feature regret bound and hence the final theorem rely on it.
  • domain assumption A user-specified relabeling I satisfying the three conditions in Section 2.1 exists.
    The augmentation argument and Lemmas B.1 and B.2 require such an I; existence is argued but the exact choice is left to the user.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparsity-Based Interpolation of External, Internal and Swap Regret." pith.science (2026). https://pith.science/paper/RB57GRH2

@misc{pith2026250204543,
  author       = {Pith},
  title        = {Pith review of: Sparsity-Based Interpolation of External, Internal and Swap Regret},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RB57GRH2}},
  note         = {Machine review of arXiv:2502.04543}
}
abstract

Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via $\phi$-regret minimization, which measures the total loss of an algorithm by its regret with respect to an arbitrary action modification rule $\phi$. With $d$ experts and $T\gg d$ rounds in total, we present a single algorithm achieving the instance-adaptive $\phi$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_\phi+1},\sqrt{d-d^{\mathrm{self}}_\phi}\right\}\cdot\sqrt{T}\right), \end{equation*} where $d^{\mathrm{unif}}_\phi$ is the maximum amount of experts modified identically by $\phi$, and $d^{\mathrm{self}}_\phi$ is the amount of experts that $\phi$ trivially modifies to themselves. By recovering the optimal $O(\sqrt{T\log d})$ external regret bound when $d^{\mathrm{unif}}_\phi=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_\phi=d-1$ and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes. In addition, the computational complexity of our algorithm matches that of the standard swap-regret minimization algorithm due to (Blum and Mansour, 2007). Technically, building on the well-known reduction from $\phi$-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, by associating the complexity of each $\phi$ instance with its sparsity under the feature representation, we apply techniques from comparator-adaptive online learning to exploit the sparsity in this regression subroutine.

Figures

Figures reproduced from arXiv: 2502.04543 by the authors.

Figure 1
Figure 1. An illustration of Algorithm 1; see Appendix A for details. Assuming T ≫ d, Theorem 1 recovers the O˜( √ T) external regret in the case of d unif ϕ∗ = d, the O˜( √ T) internal regret in the case of d self ϕ∗ = d − 1 and the O˜( √ dT) swap regret in the worst case, matching the results achieved by specialized algorithms (modulo polylog factors). Although this basic requirement can also be achieved by simply aggregati… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 45 canonical work pages

  1. [1]

    Blackwell approachability and no-regret learning are equivalent

    Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Conference on Learning Theory , pages 27--46, 2011

    work page 2011

  2. [2]

    Constrained phi-equilibria

    Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Francesco Trovo, and Nicola Gatti. Constrained phi-equilibria. In International Conference on Machine Learning , pages 2184--2205. PMLR, 2023

    work page 2023

  3. [3]

    An analog of the minimax theorem for vector payoffs

    David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics , 6(1):1--8, 1956

    work page 1956

  4. [4]

    From external to internal regret

    Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research , 8(6), 2007

    work page 2007

  5. [5]

    Online forecasting of total-variation-bounded sequences

    Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation-bounded sequences. Advances in Neural Information Processing Systems , 32, 2019

    work page 2019

  6. [6]

    How to use expert advice

    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

    work page 1997

  7. [7]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and G \'a bor Lugosi. Prediction, learning, and games . Cambridge university press, 2006

    2006

  8. [8]

    On tractable -equilibria in non-concave games

    Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. On tractable -equilibria in non-concave games. Advances in Neural Information Processing Systems , 37, 2024

    work page 2024

Show all 53 references
  1. [9]

    A parameter-free hedging algorithm

    Kamalika Chaudhuri, Yoav Freund, and Daniel J Hsu. A parameter-free hedging algorithm. Advances in Neural Information Processing Systems , 22, 2009

    2009

  2. [10]

    Impossible tuning made possible: A new expert algorithm and its applications

    Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory , pages 1216--1259. PMLR, 2021

    2021

  3. [11]

    Fully unconstrained online learning

    Ashok Cutkosky and Zak Mhammedi. Fully unconstrained online learning. Advances in Neural Information Processing Systems , 37:10148--10201, 2024

    2024

  4. [12]

    Black-box reductions for parameter-free online learning in banach spaces

    Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory , pages 1493--1529. PMLR, 2018

    2018

  5. [13]

    Algorithms and Lower Bounds for Parameter-free Online Learning

    Ashok Cutkosky. Algorithms and Lower Bounds for Parameter-free Online Learning . Stanford University, 2018

    2018

  6. [14]

    From external to swap regret 2.0: An efficient reduction for large action spaces

    Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1216--1222, 2024

    2024

  7. [15]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research , 12(7), 2011

    2011

  8. [16]

    Pseudonorm approachability and applications to regret minimization

    Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balubramanian Sivan. Pseudonorm approachability and applications to regret minimization. In International Conference on Algorithmic Learning Theory , pages 471--509. PMLR, 2023

    2023

  9. [17]

    Rate-preserving reductions for blackwell approachability

    Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Rate-preserving reductions for blackwell approachability. arXiv preprint arXiv:2406.07585 , 2024

    2024 arXiv

  10. [18]

    Parameter-free online learning via model selection

    Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. Advances in Neural Information Processing Systems , 30, 2017

    2017

  11. [19]

    Full swap regret and discretized calibration

    Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. In International Conference on Algorithmic Learning Theory , 2025

    2025

  12. [20]

    Adaptive online learning

    Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances in Neural Information Processing Systems , 28, 2015

    2015

  13. [21]

    Regret in the on-line decision problem

    Dean P Foster and Rakesh Vohra. Regret in the on-line decision problem. Games and Economic Behavior , 29(1-2):7--35, 1999

    1999

  14. [22]

    No-regret learning in convex games

    Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In International Conference on Machine Learning , pages 360--367, 2008

    2008

  15. [23]

    A general class of no-regret learning algorithms and game-theoretic equilibria

    Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop , pages 2--12. Springer, 2003

    2003

  16. [24]

    More efficient internal-regret-minimizing algorithms

    Amy Greenwald, Zheng Li, and Warren Schudy. More efficient internal-regret-minimizing algorithms. In Conference on Learning Theory , pages 239--250, 2008

    2008

  17. [25]

    Comparator-adaptive -regret: Improved bounds, simpler algorithms, and applications to games

    Soumita Hait, Ping Li, Haipeng Luo, and Mengxiao Zhang. Comparator-adaptive -regret: Improved bounds, simpler algorithms, and applications to games. arXiv preprint arXiv:2505.17277 , 2025

    2025

  18. [26]

    Calibrated stackelberg games: Learning optimal commitments against calibrated agents

    Nika Haghtalab, Chara Podimata, and Kunhe Yang. Calibrated stackelberg games: Learning optimal commitments against calibrated agents. Advances in Neural Information Processing Systems , 36, 2023

    2023

  19. [27]

    A tight lower bound and efficient reduction for swap regret

    Shinji Ito. A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems , 33:18550--18559, 2020

    2020

  20. [28]

    An equivalence between static and dynamic regret minimization

    Andrew Jacobsen and Francesco Orabona. An equivalence between static and dynamic regret minimization. Advances in Neural Information Processing Systems , 37, 2024

    2024

  21. [29]

    A wide range no-regret theorem

    Ehud Lehrer. A wide range no-regret theorem. Games and Economic Behavior , 42(1):101--115, 2003

    2003

  22. [30]

    Online minimax multiobjective optimization: Multicalibeating and other applications

    Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems , 35:29051--29063, 2022

    2022

  23. [31]

    Achieving all with no parameters: Ada N ormal H edge

    Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Ada N ormal H edge. In Conference on Learning Theory , pages 1286--1304. PMLR, 2015

    2015

  24. [32]

    The weighted majority algorithm

    Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation , 108(2):212--261, 1994

    1994

  25. [33]

    A Wavelet Tour of Signal Processing: The Sparse Way

    Stephane Mallat. A Wavelet Tour of Signal Processing: The Sparse Way . Academic Press, 2008

    2008

  26. [34]

    Lipschitz and comparator-norm adaptivity in online learning

    Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory , pages 2858--2887. PMLR, 2020

    2020

  27. [35]

    Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations

    H Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory , pages 1020--1039. PMLR, 2014

    2014

  28. [36]

    Online learning with transductive regret

    Mehryar Mohri and Scott Yang. Online learning with transductive regret. Advances in Neural Information Processing Systems , 30, 2017

    2017

  29. [37]

    Minimax optimal quantile and semi-adversarial regret via root-logarithmic regularizers

    Jeffrey Negrea, Blair Bilodeau, Nicol \`o Campolongo, Francesco Orabona, and Dan Roy. Minimax optimal quantile and semi-adversarial regret via root-logarithmic regularizers. Advances in Neural Information Processing Systems , 34:26237--26249, 2021

    2021

  30. [38]

    High-dimensional prediction for sequential decision making

    Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. arXiv preprint arXiv:2310.17651 , 2023

    2023 arXiv

  31. [39]

    Coin betting and parameter-free online learning

    Francesco Orabona and D \'a vid P \'a l. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems , 29, 2016

    2016

  32. [40]

    A modern introduction to online learning

    Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213v7 , 2025

    1912 arXiv

  33. [41]

    Exponential weight approachability, applications to calibration and regret minimization

    Vianney Perchet. Exponential weight approachability, applications to calibration and regret minimization. Dynamic Games and Applications , 5:136--153, 2015

    2015

  34. [42]

    Fast swap regret minimization and applications to approximate correlated equilibria

    Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1223--1234, 2024

    2024

  35. [43]

    Evolutionary dynamics and phi-regret minimization in games

    Georgios Piliouras, Mark Rowland, Shayegan Omidshafiei, Romuald Elie, Daniel Hennes, Jerome Connor, and Karl Tuyls. Evolutionary dynamics and phi-regret minimization in games. Journal of Artificial Intelligence Research , 74:1125--1158, 2022

    2022

  36. [44]

    Learning in games (and games in learning)

    Aaron Roth. Learning in games (and games in learning). Unpublished Lecture Note, https://www.cis.upenn.edu/ aaroth/GamesInLearning.pdf , 2023

    2023

  37. [45]

    Online learning: Beyond regret

    Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In Conference on Learning Theory , pages 559--594, 2011

    2011

  38. [46]

    An online convex optimization approach to blackwell's approachability

    Nahum Shimkin. An online convex optimization approach to blackwell's approachability. Journal of Machine Learning Research , 17(129):1--23, 2016

    2016

  39. [47]

    Internal regret in on-line portfolio selection

    Gilles Stoltz and G \'a bor Lugosi. Internal regret in on-line portfolio selection. Machine Learning , 59:125--159, 2005

    2005

  40. [48]

    Learning correlated equilibria in games with compact sets of strategies

    Gilles Stoltz and G \'a bor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior , 59(1):187--208, 2007

    2007

  41. [49]

    No-regret algorithms for unconstrained online convex optimization

    Matthew Streeter and Brendan Mcmahan. No-regret algorithms for unconstrained online convex optimization. Advances in Neural Information Processing Systems , 25, 2012

    2012

  42. [50]

    Efficient -regret minimization with low-degree swap deviations in extensive-form games

    Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Efficient -regret minimization with low-degree swap deviations in extensive-form games. Advances in Neural Information Processing Systems , 37, 2024

    2024

  43. [51]

    Paschalidis

    Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. PDE -based optimal strategy for unconstrained online learning. In International Conference on Machine Learning , pages 26085--26115. PMLR, 2022

    2022

  44. [52]

    Paschalidis

    Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Unconstrained dynamic regret via sparse coding. Advances in Neural Information Processing Systems , 36, 2023

    2023

  45. [53]

    Paschalidis

    Zhiyu Zhang, Heng Yang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Improving adaptive online learning using refined discretization. In International Conference on Algorithmic Learning Theory , pages 1208--1233. PMLR, 2024

    2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.