Adaptive and Efficient Algorithms for Tracking the Best Expert

Lijun Zhang; Shiyin Lu

Adaptive and Efficient Algorithms for Tracking the Best Expert

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

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

Pith's one-line read This paper proves that tracking a switching best expert can be done with the first second-order tracking regret bound, while remaining efficient and extending to matrix prediction.

desk verdict A genuinely new second-order tracking regret bound with complete proofs; the only real caveat is the unstated S <= T feasibility condition and the hindsight-tuned learning rate, neither of which breaks the main claims. read the letter →

arxiv 1909.02187 v2 pith:FY465V4P submitted 2019-09-05 cs.LG stat.ML

Shiyin Lu , Lijun Zhang This is my paper · ORCID

classification cs.LGstat.ML

keywords predictionwithexpertadvicetrackingregretsecond-orderboundclippedsimplexonlinemirrordescentpath-lengthmatrixadaptivelearning

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 prediction with expert advice, the standard benchmark competes with a single fixed expert, but in changing environments the best expert can switch. This paper studies tracking regret, where the learner is compared with the best sequence of experts that switches at most $S-1$ times, and it proposes two efficient algorithms. The first, PCS, attains the first second-order tracking regret bound, scaling with the sum of squared losses of the best expert sequence instead of the sum of losses. The second, OCS, attains a path-length bound that improves when loss vectors move slowly, and a doubling-trick variant removes the need to know the path length in advance. The same clipped-simplex idea is carried over to online matrix prediction, giving the first data-dependent tracking regret bound for that problem.

What carries the argument

The central object is the clipped simplex $\widetilde{\Delta}_K=\{w\in\Delta_K: w[i]\ge S/(TK)\ \forall i\}$, used in place of the simplex in the online mirror descent update. The lower bound $S/(TK)$ is the switching mechanism: every expert always retains a small amount of mass, so the learner can move toward a new best expert after each switch, and the analysis splits the horizon into $S$ segments, charging $\log(KT/S)$ to each segment via Bregman telescoping. PCS couples the clipped simplex with the Prod/multilinear surrogate $-\log(1-\eta\ell_t)$; OCS couples it with two nested optimistic mirror steps that use the previous loss vector as a hint. In the matrix extension, the simplex becomes the spectraplex with a floor on the minimum eigenvalue.

What would settle it

Take $K=2$, $T=3$, $S=4$: the clipped simplex would require each weight to be at least $S/(TK)=2/3$, so the two weights sum to at least $4/3>1$ and the projection in the PCS update has no solution, showing that the theorems silently presuppose $S\le T$. For the regret bound itself, simulate PCS on every loss sequence for a small case such as $K=3$, $T=6$, $S=2$ and compare the worst observed tracking regret against the claimed $\eta L_2+S\log(KT/S)/\eta+3S/2$; a single violating sequence would refute Theorem 2.

Watch

Extended reading notes

Core claim

This paper's central claim is Theorem 2: for $\eta \in (0,1/2]$, the Prod-on-clipped-simplex algorithm PCS has tracking regret $$TR(T,S) \leq \eta L_2 + \frac{S \log(KT/S)}{\eta} + \frac{3S}{2},$$ where $L_2=\sum_{t=1}^T (\ell_t[E_t^*])^2$ is the sum of squared losses of the best switching expert sequence. With the optimal choice of $\eta$, this yields $O(\sqrt{S L_2 \log(KT/S)} + S \log(KT/S))$. Because all losses lie in $[0,1]$, $L_2 \leq L_1$, so this bound is never worse than the earlier first-order bound $O(\sqrt{S L_1 \log(KT/S)} + S \log(KT/S))$, and it is much smaller when the best expert has small losses. The paper also proves an optimistic variant OCS with path-length bound $O(\sqrt{S P_\infty \log(KT/S)}+S)$, where $P_\infty=\sum_{t=1}^T \|\ell_t-\ell_{t-1}\|_\infty^2$, and, for online matrix prediction, a bound $O(\sqrt{S M_2 \log(KT/S)}+S \log(KT/S))$ with $M_2=\sum_{t=1}^T \operatorname{Tr}(U_t^* Z_t^2)$.

Load-bearing premise

Every algorithm and theorem assumes that the clipped simplex is nonempty, which requires $S\le T$, but the paper never states this condition; if $S>T$, the update steps have no feasible solution and the proofs have no constrained minimizer to reason about.

Editorial extensions

If this is right

Since $L_2 \le L_1$ for losses in $[0,1]$, the PCS bound is never worse than the previous first-order tracking bound, and it becomes much smaller when the best expert sequence has small losses.
OCS reaches the same order as existing path-length tracking bounds while operating on the $K$ real experts, so its per-round time and space costs do not grow with the horizon.
The doubling-trick variant OCS+ achieves the path-length bound without knowing $P_\infty$ in advance, paying only a constant factor; the learner adapts to how slowly the environment moves.
PCSP carries the clipped-simplex guarantee to online matrix prediction and yields the first data-dependent tracking regret bound for that problem.
The second-order and path-length bounds are complementary: PCS is preferred for small losses, OCS for slowly moving losses, and together they cover different benign environments.

Reading between the lines

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

The paper's own obstacle discussion implies a concrete next step: a sleeping-expert algorithm with the same kind of second-order guarantee would, through the two-layer construction, immediately yield a parameter-free second-order tracking regret algorithm.
The uniform floor $S/(TK)$ could be replaced by per-expert floors to encode expert-specific switch budgets or time-varying switching costs, a direct generalization of the same proof technique.
The clipped-simplex mechanism may transfer to non-stationary bandits, where keeping every arm's sampling weight above a floor would preserve exploration; the paper only lists bandits as future work.
One could try to merge the PCS and OCS analyses into a single bound depending on both $L_2$ and $P_\infty$, analogous to the static-regret bound the paper cites as motivation, and the paper explicitly leaves this open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The paper is worth your time. It delivers the first second-order tracking regret bound for prediction with expert advice (Theorem 2, PCS), plus an efficient path-length bound (Theorem 3, OCS) and the first data-dependent tracking regret bound for online matrix prediction (Theorem 5, PCSP). The central claims are new relative to the cited literature: Cesa-Bianchi et al. give first-order bounds, and Wei et al.'s path-length algorithm is inefficient. The clipped-simplex idea is simple and does real work: it gives a clean OMD proof without the intermediate distribution of projection update.

The proofs hold up. I checked the key steps in Appendices C, D, and F: the decomposition in (40), the x + log(1-x) <= 0 and -x - log(1-x) <= x^2 inequalities, the telescoping sums, and the Golden-Thompson use in Lemma 6 all check out. Lemma 8's bound on trace(log-difference) is fine. The matrix extension is a faithful generalization, not a token one—the von Neumann entropy and clipped spectraplex are the right objects.

Soft spots, in proportion. First, the clipped simplex (11) is empty when S > T, and the paper never states the S <= T condition. It matters because every update step projects onto this set. The fix is trivial—cap S at T, since C(T,S) = C(T,T) for S > T—and the proof is unchanged, but leaving it implicit is sloppy in a theory paper. Second, the learning rates for PCS and OCS depend on L2 and P_infty in hindsight. The paper acknowledges this and gives a parameter-free OCS+ via doubling, but PCS itself is not parameter-free. That is a real limitation, though it does not invalidate the bounds as mathematical statements. The reader's worry about the proof of Lemma 8 being thin is minor: the argument is short but correct.

Citation pattern looks honest; they compare against the right prior work and note where their bound is not comparable to existing ones. No circularity, no fitted constants. This is a solid subfield result, not a paradigm shift: it improves known bounds in a well-studied setting, and the improvements are meaningful for small-loss and slowly-varying environments.

Who this is for: anyone working on tracking regret, adaptive online learning, or matrix online learning. It deserves a serious referee. My recommendation: send it to review. It is exactly the kind of paper that should get a thorough but favorable referee report, with the S <= T condition and parameter-free gaps flagged as revisions rather than rejections.

Referee Report

0 major / 5 minor

Summary. This paper studies prediction with expert advice under tracking regret. The authors propose PCS, a Prod-type method run on a clipped simplex, and prove (Theorem 2) that for eta in (0,1/2] its tracking regret is at most eta*L2 + (S/eta)*log(KT/S) + 3S/2, where L2 is the sum of squared losses of the best expert sequence; with tuned eta this gives the first second-order tracking regret bound. They then propose OCS, an optimistic mirror-descent variant on the same clipped simplex, with the path-length bound eta*P_inf + (S/eta)*log(KT/S) + S (Theorem 3), and OCS+ (Theorem 4), a doubling-trick version that avoids hindsight tuning of eta while preserving the path-length bound up to constants. The construction is extended to online matrix prediction by replacing the clipped simplex with a clipped spectraplex, yielding Theorem 5, the first data-dependent tracking regret bound for that setting. All theorems are proved in appendices.

Significance. The main contribution is the second-order tracking regret bound, which improves the first-order bound of Cesa-Bianchi et al. (2012) in small-loss dynamic environments and is obtained with an algorithm whose per-round cost depends on K rather than on KT virtual experts. The path-length bound from OCS is already known from Wei et al. (2016), but the efficient OMD formulation is new. The matrix extension is a genuine novelty. The vector proofs are coherent: the decomposition in Eq. (40), the bounds on At and Bt via x+log(1-x)<=0 and -x-log(1-x)<=x^2, and the telescoping bound (44) are all valid. If the statement-level fixes below are made, the paper meets the standard for publication.

minor comments (5)

[Section 3.1, Eq. (11); Theorems 1-5] The paper never states the feasibility condition S <= T. The clipped simplex ~Delta_K and the clipped spectraplex ~Omega_K in Eq. (19) are empty when S > T, and the updates (12), (14), (17), (18), and Algorithm 5 are then undefined. Since C(T,S)=C(T,T) for S > T and the tracking regret is unchanged, the clean fix is to state "assume S <= T; otherwise replace S by T" in the definitions and in each theorem; all proofs remain valid after this capping.
[Appendix G.8, Lemma 8] The proof asserts that "the eigenvalues of X logY are all non-positive" from the fact that X is PSD and logY is NSD; for non-commuting symmetric matrices this does not follow without an argument. A one-line justification is obtained by writing X=A A^T and using the fact that AB and BA have the same nonzero eigenvalues (or by conjugating A^T(logY)A). Please add this justification.
[Appendix C and Appendix G.7] The inequality -x-log(1-x) <= x^2 is stated for x in (-infinity,1/2], and the variant -x-log(1-x) <= |x|/2 in Lemma 7 is used for x in [-1/2,1/2]; both ranges are sufficient here, but the second is not stated in the lemma. State the range explicitly to avoid confusion.
[Appendix G.1] The final line of the proof of Lemma 1 says "the last inequality holds" where the step is actually an equality; fix this wording.
[Section 3.3, after Eq. (50)] The sentence "the condition in Line 10 can be violated only at the last round of the epoch" is ambiguous; more precisely, the condition is checked at the end of each round and the epoch ends at the first round for which the condition holds.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret bounds are derived from the OMD update and are not fitted to the target quantities.

full rationale

The central claims are Theorems 2, 3, 4 and 5, and each proof is a direct regret decomposition rather than a reduction of the conclusion to its inputs. In Theorem 2, the tracking regret is decomposed via Eq. (40) into A_t, B_t, and C_t; A_t ≤ 0 follows from x + log(1 - x) ≤ 0 after the clipped-simplex optimality condition, B_t ≤ η^2(ℓ_t[E*_t])^2 + ηS/(2T) follows from -x - log(1 - x) ≤ x^2 on [0, 1/2], and the C_t term telescopes to log(KT/S) per segment by Eq. (38). The occurrence of L2 in the final bound is a data-dependent small-loss quantity, not a parameter fitted to make the inequality hold; the comparison sequence E*_t is the benchmark appearing in the definition of tracking regret, so using it in the bound is standard hindsight analysis rather than circularity. Likewise, Theorem 3's P∞ bound is obtained by Lemma 4 and the optimality conditions of Eqs. (17)-(18), and Theorem 4's parameter-free extension uses a doubling trick with the same path-length quantity. The authors explicitly state in Section 3.3 that PCS and OCS require prior knowledge of L2 and P∞ for tuning; this is an acknowledged oracle-tuning limitation, not a disguised fit: the theorems are asserted for arbitrary η in the stated ranges and the bounds hold with the chosen η as a consequence of the proof. The one notable defect, that the clipped simplex ~Δ_K is nonempty only when S ≤ T, is an unstated precondition and a correctness risk, but it does not make any derivation circular. There are no load-bearing self-citations, and no known result is renamed as a new contribution: the second-order bound is compared with, not reduced to, Cesa-Bianchi et al. (2012).

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

The central claims rest on standard online-learning assumptions (bounded losses), standard convex-analysis facts (strong convexity of entropy, Fenchel conjugate properties, Golden-Thompson), and an unstated feasibility condition S <= T. No invented entities are introduced.

free parameters (3)

Learning rate eta for PCS = min{sqrt(S log(KT/S)/L2), 1/2}
Chosen in hindsight based on L2; the algorithm is not parameter-free for the second-order bound (Section 3.3).
Learning rate eta for OCS = sqrt(S log(KT/S)/P_infty)
Chosen in hindsight based on P_infty; OCS+ removes this need via a doubling trick.
Clipping lower bound alpha = S/(TK) = S/(TK)
Defines the clipped simplex; must satisfy S <= T for nonemptiness, which the paper does not state explicitly.

assumptions (4)

domain assumption Loss vectors are bounded: l_t in [0,1]^K for all t, and ||Z_t||_* <= 1 in the matrix case.
Used throughout all proofs, e.g., Lemma 2, Lemma 3, and the bound eta*||l_t||_infty^2 <= eta.
standard math The negative entropy function is 1-strongly convex over the clipped simplex with respect to the l1 norm.
Needed for the Fenchel conjugate Lipschitz property used in Lemmas 3 and 4 (Appendix G.3, G.4).
standard math Golden-Thompson inequality for symmetric matrices.
Used in Lemma 6 to bound the matrix Prod update (Appendix G.6).
domain assumption The clipped simplex is nonempty, i.e., S <= T.
Required for the projection steps to be well-defined; not stated in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Adaptive and Efficient Algorithms for Tracking the Best Expert." pith.science (2026). https://pith.science/paper/FY465V4P

@misc{pith2026190902187,
  author       = {Pith},
  title        = {Pith review of: Adaptive and Efficient Algorithms for Tracking the Best Expert},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FY465V4P}},
  note         = {Machine review of arXiv:1909.02187}
}

read the original abstract

In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and develop two adaptive and efficient algorithms with data-dependent tracking regret bounds. The first algorithm achieves a second-order tracking regret bound, which improves existing first-order bounds. The second algorithm enjoys a path-length bound, which is generally not comparable to the second-order bound but offers advantages in slowly moving environments. Both algorithms are developed under the online mirror descent framework and draw inspiration from existing algorithms that attain data-dependent bounds of static regret. The key idea is to use a clipped simplex in the updating step of online mirror descent. Finally, we extend our algorithms and analysis to online matrix prediction and provide the first data-dependent tracking regret bound for this problem.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization
cs.LG 2025-09 conditional novelty 6.0 of 10

A modular algorithm for online convex-concave optimization achieves near-optimal dynamic duality gap bounds by combining adaptive experts with a multi-predictor aggregator.

Reference graph

Works this paper leans on

34 extracted references · 29 canonical work pages · cited by 1 Pith paper

[1]

A closer look at adaptive regret

Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17 0 (1): 0 706--726, 2016

work page 2016
[2]

Tracking a small set of experts by mixing past posteriors

Olivier Bousquet and Manfred K Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3 0 (Nov): 0 363--396, 2002

work page 2002
[3]

Convex Optimization

Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004

2004
[4]

Improved path-length regret bounds for bandits

S \'e bastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. Improved path-length regret bounds for bandits. In Proceedings of the 32nd Conference on Learning Theory, pages 508--528, 2019

work page 2019
[5]

Prediction, Learning, and Games

Nicol\` o Cesa-Bianchi and G \'a bor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006

2006
[6]

Improved second-order bounds for prediction with expert advice

Nicol \`o Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. In Proceedings of the 18th Annual Conference on Learning Theory, pages 217--232, 2005

work page 2005
[7]

Mirror descent meets fixed share (and feels no regret)

Nicol\` o Cesa-bianchi, Pierre Gaillard, Gabor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25, pages 980--988, 2012

work page 2012
[8]

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. In Proceedings of the 25th Annual Conference on Learning Theory, pages 6.1--6.20, 2012

work page 2012

Show all 34 references

[9]

A decision-theoretic generalization of on-line learning and an application to boosting

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 0 (1): 0 119 -- 139, 1997

1997
[10]

A second-order bound with excess losses

Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Proceedings of The 27th Conference on Learning Theory, pages 176--196, 2014

2014
[11]

Lower bounds for the helmholtz function

Sidney Golden. Lower bounds for the helmholtz function. Physical Review, 137 0 (4B): 0 B1127, 1965

1965
[12]

Shifting regret, mirror descent, and matrices

Andras Gyorgy and Csaba Szepesvari. Shifting regret, mirror descent, and matrices. In Proceedings of The 33rd International Conference on Machine Learning, pages 2943--2951, 2016

2016
[13]

Approximation to bayes risk in repeated play

James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3: 0 97--139, 1957

1957
[14]

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. Machine Learning, 80 0 (2-3): 0 165--188, 2010

2010
[15]

Adaptive algorithms for online decision problems

Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic Colloquium on Computational Complexity, volume 14, 2007

2007
[16]

Near-optimal algorithms for online matrix prediction

Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In Proceedings of the 25th Annual Conference on Learning Theory, pages 38--1, 2012

2012
[17]

Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32 0 (2): 0 151--178, 1998

1998
[18]

Mark Herbster and Manfred K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1: 0 281--309, 2001

2001
[19]

Efficient algorithms for online decision problems

Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. In Proceedings of the 16th Annual Conference on Learning Theory, pages 26--40. 2003

2003
[20]

Exponentiated gradient versus gradient descent for linear predictors

Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132 0 (1): 0 1--63, 1997

1997
[21]

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

1994
[22]

Schapire

Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. In Proceedings of The 28th Conference on Learning Theory, pages 1286--1304, 2015

2015
[23]

Online learning with predictable sequences

Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference on Learning Theory, pages 993--1019, 2013

2013
[24]

Online Learning: Theory, Algorithms, and Applications

Shai Shalev-Shwartz. Online Learning: Theory, Algorithms, and Applications. PhD thesis, The Hebrew University of Jerusalem, 2007

2007
[25]

Online learning and online convex optimization

Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4 0 (2): 0 107--194, 2011

2011
[26]

On the universality of online mirror descent

Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. In Advances in neural information processing systems 24, pages 2645--2653, 2011

2011
[27]

Adaptivity and optimism: An improved exponentiated gradient algorithm

Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In Proceedings of the 31st International Conference on Machine Learning, pages 1593--1601, 2014

2014
[28]

Inequality with applications in statistical mechanics

Colin J Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physics, 6 0 (11): 0 1812--1813, 1965

1965
[29]

Matrix exponentiated gradient updates for on-line learning and bregman projection

Koji Tsuda, Gunnar R \"a tsch, and Manfred K Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. Journal of Machine Learning Research, 6 0 (Jun): 0 995--1018, 2005

2005
[30]

V. Vovk. Derandomizing stochastic prediction strategies. Machine Learning, 35 0 (3): 0 247--282, 1999

1999
[31]

Volodimir G. Vovk. Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 371--386, 1990

1990
[32]

More adaptive algorithms for adversarial bandits

Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference On Learning Theory, pages 1263--1291, 2018

2018
[33]

Tracking the best expert in non-stationary stochastic environments

Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in non-stationary stochastic environments. In Advances in Neural Information Processing Systems 29, pages 3972--3980, 2016

2016
[34]

Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)

Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71 0 (4): 0 441--479, 1912

1912

Pith tools

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

[1] [1]

A closer look at adaptive regret

Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17 0 (1): 0 706--726, 2016

work page 2016

[2] [2]

Tracking a small set of experts by mixing past posteriors

Olivier Bousquet and Manfred K Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3 0 (Nov): 0 363--396, 2002

work page 2002

[3] [3]

Convex Optimization

Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004

2004

[4] [4]

Improved path-length regret bounds for bandits

S \'e bastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. Improved path-length regret bounds for bandits. In Proceedings of the 32nd Conference on Learning Theory, pages 508--528, 2019

work page 2019

[5] [5]

Prediction, Learning, and Games

Nicol\` o Cesa-Bianchi and G \'a bor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006

2006

[6] [6]

Improved second-order bounds for prediction with expert advice

Nicol \`o Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. In Proceedings of the 18th Annual Conference on Learning Theory, pages 217--232, 2005

work page 2005

[7] [7]

Mirror descent meets fixed share (and feels no regret)

Nicol\` o Cesa-bianchi, Pierre Gaillard, Gabor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25, pages 980--988, 2012

work page 2012

[8] [8]

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. In Proceedings of the 25th Annual Conference on Learning Theory, pages 6.1--6.20, 2012

work page 2012