PaperlayerView exact revision on arXiv

Source-linked AI summary

Tracking a Small Set of Experts in Online Convex Optimization

Angelos Assos, Anand Brahmbhatt, Elad Hazan

arXiv:2610.20416v1cs.LGmath.OCstat.ML

TL;DR

The paper asks what regret an efficient algorithm can achieve when continuous OCO comparators repeatedly reuse a small set of decisions. It analyzes discretization and establishes a conditional computational lower bound under hypergraphic planted-clique hardness.

  • Problem

    In continuous OCO, the best regret rate achievable by a computationally efficient algorithm against a comparator that switches among a small set of decisions remains open.

    Source: §1 · pp. 1–2

  • Method

    The paper studies a discretization-based tracking algorithm and reduces hypergraphic planted-clique detection to online convex optimization.

    Source: §1.2 · p. 3, §1.3 · p. 3, §5 · p. 8

  • Results

    eO(k^a d^b) expected regret is ruled out uniformly for k = Θ(d^θ) when θa + b < θ + 1/2, assuming r-HPC for every fixed r ≥ 4, even for m = 2.

    Source: §6 · p. 11

  • Takeaways & Limitations

    The results establish a conditional separation between unrestricted and polynomial-time regret for tracking comparators that use only a small number of decisions.

    Source: §6 · p. 11

    The computational lower bound depends on the hypergraphic planted-clique conjecture.

    Source: §5 · p. 8

Abstract

from arXiv · show

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.

1 Introduction

The paper asks whether an efficient learner in continuous online convex optimization can compete with a comparator that reuses a small set of decisions. It presents a conditional computational separation, explains the discretization route and its cost, and outlines a planted-clique hardness reduction.

1 Introduction

  • Dynamic regret can be impossible with unrestricted comparator changes, while a small-pool comparator captures recurrence by switching among a limited set of experts.Bousquet and Warmuth (2002) studied this tracking benchmark for finite expert sets.Source: §1 · pp. 1–2
  • The central question is the best regret rate achievable efficiently in continuous OCO, where discretization yields eO(md + k) but can require exponentially many points in d.Existing polynomial-time methods achieve eO(dk) regret.Source: §1 · p. 2

1.1 Overview of Our Results

  • Under hypergraphic planted-clique hardness, polynomial-time algorithms cannot guarantee eO(k^a d^b) expected regret uniformly when θa + b < θ + 1/2 along k = Θ(d^θ), even for m = 2.The result applies to bounded 1-exp-concave rank-one quadratics on the Euclidean unit ball with T = poly(d).Source: §1.1 · p. 2
  • For convex and strongly convex losses, efficient algorithms match the information-theoretic dependence on k, whereas exp-concave losses retain a gap between information-theoretic and efficient regret rates.The table summarizes regret bounds across the three curvature regimes for constant m and k ≥ 1.Source: Table 1 · p. 2, §1.1 · p. 2

1.2 From Mixable Experts to Exp-Concave OCO

  • A finite net of the continuous domain lets the Bousquet–Warmuth method achieve eO(md + k) regret, but the net can be exponentially large in d.For Lipschitz losses on a bounded domain, approximation preserves the comparator's number of distinct points and switches, with at most constant additional loss.Source: §1.2 · p. 3

1.3 Overview of the Hardness Reduction

  • The hardness reduction maps hypergraphic planted-clique instances to bounded exp-concave losses, where a clique yields a two-decision comparator with a large advantage over the origin.If learner regret were sufficiently small, its observable gain would distinguish the planted model from the null model.Source: §1.3 · p. 4

2 Related Work

Related work spans tracking experts with long-term memory, shifting and adaptive regret in continuous decision spaces, and average-case hardness reductions based on planted clique.

Tracking and long-term memory

  • Tracking-expert work developed Fixed Share and methods that reuse information about previously successful experts, with extensions to stateful experts, bandits, and structured classes.The literature also includes Bayesian formulations and multitask learning.Source: §2 · p. 4

Shifting and adaptive regret in OCO

  • OCO shifting-regret methods measure changing comparators without exploiting recurrence, while adaptive-regret guarantees can be summed across segments at the cost of relearning on each one.Static regret costs are dimension-free for strongly convex losses but dimension-dependent for exp-concave losses.Source: §2 · p. 4

Planted clique and average-case hardness

  • Planted-clique variants underpin average-case hardness evidence, including hypergraphic conjectures used for statistical-computational gaps in tensor estimation and clustering.Prior work also applied planted-clique hardness to approximate Nash equilibrium and social-welfare problems.Source: §2 · pp. 4–5

3 Preliminaries

The preliminaries specify the OCO protocol, the curvature assumptions, and the tracking benchmark that separates switch count from the number of recurring decisions. They also define adaptive regret and the paper's notation.

Notation

  • The notation eO and eΩ suppresses polylogarithmic factors, and Bd_2 denotes the Euclidean unit ball.The text also defines [n], event indicators, inner products, and Euclidean norms.Source: §3 · p. 5

Online learning protocol

  • The learner acts in a compact convex set, observes each differentiable convex loss after choosing, and is studied under exp-concavity and bounded-gradient strong convexity.Exp-concavity means e^(-αf) is concave; strong convexity is defined through the standard differentiable loss inequality.Source: §3 · p. 5

Comparator paths

  • The comparator benchmark separately counts switches and distinct decisions, allowing paths that reuse at most m points across at most k switches.The resulting comparator class consists of paths with those two constraints.Source: §3 · p. 5

Tracking regret

  • Tracking regret compares learner loss with the best admissible comparator in hindsight, although its points and switch times are not revealed to the learner.For randomized learners, expected regret is taken over internal randomness on each fixed loss sequence; efficiency means polynomial total running time in T, m, k, and d.Source: §3 · pp. 5–6

Adaptive regret

  • Adaptive regret measures performance against the best fixed decision on every time interval.The paper uses this benchmark in its analysis.Source: §3 · p. 6

4 Upper Bounds

The section derives efficient switching bounds from adaptive-regret guarantees. It gives dimension-free bounds for strongly convex losses and dimension-dependent bounds for exp-concave losses.

Adaptive regret and switching

  • Pruned FLH combines restarted copies of a base learner and plays their weighted-average decision, maintaining O(log T) active copies.Adaptive regret bounds performance on each constant comparator segment, and summing across segments yields a switching guarantee.Source: §4 · p. 6

Switching guarantee

  • The switching bound is independent of m, and the algorithm requires neither m nor k nor the switch times.Source: §4 · p. 6

Strongly convex losses

  • Strongly convex losses admit a dimension-free switching bound from a deterministic oracle-efficient algorithm.The theorem assumes twice-differentiable, λ-strongly convex, G-Lipschitz losses; strong convexity makes relearning after switches inexpensive.Source: §4 · pp. 6–7

Exp-concave losses

  • O(dk log^2 T) regret is achieved for exp-concave losses when α, G, and D are constant.The theorem assumes losses are α-exp-concave and G-Lipschitz on a set of Euclidean diameter at most D, and gives a deterministic oracle-efficient algorithm.Source: §4 · p. 7

Scope

  • Recurring comparator values do not reduce the learning cost, because each constant segment is learned separately.Source: §4 · p. 7

5 Computational Hardness for Exp-Concave Functions

The section establishes a conditional computational separation for tracking regret in online convex optimization, even when the comparator uses only two decisions. A reduction from hypergraphic planted clique yields a lower bound for polynomial-time algorithms on bounded exp-concave quadratic losses.

Computational lower bound

  • Assuming Conjecture 5.1 for every fixed r ≥ 4, the theorem rules out uniform eO(k^a d^b) guarantees over all (k,d) whenever a < 1 or b < 1/2.This holds for bounded 1-exp-concave rank-one quadratic losses with T = poly(d).Source: §5 · p. 8

Reduction construction

  • The reduction maps distinct four-vertex hyperedges to quadratic-loss rounds, with two indices setting active blocks, one indexing coordinates, and one providing repeated observations.It partitions vertices into four sets and identifies the OCO coordinates with V3.Source: §5 · pp. 8–9

Comparator and gain

  • With high probability, the planted comparator uses O(q^2) switches and has advantage at least Ω(q^7/N^2) over always playing the origin.It plays one fixed nonzero point on planted active blocks and the origin elsewhere; the forced-edge contribution outweighs the quadratic penalties.Source: §5 · pp. 9–10

Null-model control

  • Under the null model, a learner’s large positive gain over the origin is exponentially unlikely, with a bound independent of the horizon.The bound applies when each loss uses a coordinate fixed before a fresh unbiased sign is observed.Source: §5 · pp. 10–11

From regret to detection

  • A learner with expected regret at most S_N/4 on planted instances with comparator advantage at least S_N would yield a polynomial-time test distinguishing the planted and null models.The reduction has polynomial length and running time for fixed parameters; the resulting test contradicts the assumed 4-HPC hardness.Source: §5 · p. 11

6 Conclusion and Future Work

The conclusion restates the regret separation and identifies the remaining open questions. In particular, the optimal polynomial-time rate remains unresolved, as does when recurrence can be exploited efficiently.

Conclusion

  • Assuming r-HPC for every fixed r ≥ 4, the paper rules out randomized polynomial-time eO(k^a d^b) expected-regret guarantees for k = Θ(d^θ) when θa + b < θ + 1/2, even for m = 2.Unrestricted algorithms achieve eO(md + k), while existing efficient methods achieve eO(kd).Source: §6 · p. 11

Future work

  • The optimal polynomial-time regret rate remains open, as does which curvature and structural assumptions let recurrence improve efficient guarantees.Strongly convex losses already admit dimension-free guarantees without exploiting recurrence.Source: §6 · p. 11

AI Disclosure

The disclosure describes AI assistance in developing the lower-bound argument and revising the paper’s exposition. The authors state that they verified the final result and take responsibility for the paper.

AI Disclosure

  • GPT-6 Astra proposed a reduction from hypergraphic planted clique; the authors refined the argument, strengthened the bound, and verified the final result.OpenAI Codex also helped revise proof exposition and presentation.Source: AI Disclosure · p. 12

A Proofs and Generalization of the Hardness Reduction

The appendix first supplies the proofs of Lemmas 5.4–5.6, then extends the construction to prove Theorem 5.2.

A Proofs and Generalization of the Hardness Reduction

A.1 Proof of Lemma 5.4

The proof constructs a comparator from planted-clique intersections and shows that it is feasible, switches only at active-block boundaries, and gains substantially in expectation with high probability.

A.1 Proof of Lemma 5.4

  • The comparator plays γ on clique coordinates in blocks indexed by C1 × C2 and plays the origin elsewhere, yielding O(q^2) active blocks.Its two decisions are the origin and γ1_C3; it is constant within each block.Source: §A.1 · pp. 15–16
  • The condition β > 1/3 ensures clique-intersection means diverge even for the smaller coordinate part V3, enabling concentration.The construction also uses β < 1/2 to ensure both comparator points are feasible for sufficiently large N.Source: §A.1 · pp. 15–16
  • The planted clique forces +1 labels on C3 × C4, while labels outside that forced set are unbiased signs conditional on the clique.The positive bias from forced hyperedges outweighs the quadratic penalty in the summed expected gain, although individual −1 labels can have negative gain.Source: §A.1 · p. 16
  • The comparator is feasible and has O(q²) switches; the q⁷/N² power comes from multiplying active blocks, clique coordinates, and expected gain per such pair.For β > 1/3, q⁷/N² = Θ(N^(7β−2)) → ∞; the bound is uniform over cliques satisfying E before averaging over them and accounting for Eᶜ.Source: §A.1 · pp. 16–17

A.2 Proof of Lemma 5.5

The proof bounds a learner’s gain under fresh unbiased labels despite adaptive decisions, then uses the bound to show that sufficiently small regret would yield a polynomial-time planted-model test.

A.2 Proof of Lemma 5.5

  • The exponential-moment argument conditions on each round’s history, so its bound remains valid even though gains may depend on earlier outcomes.The new label is an unbiased sign conditional on the history and current decision.Source: §A.2 · pp. 18–19
  • Under the null model, the probability that the learner gains at least log(1/δ) over the origin is at most δ, independently of the horizon.The gain bound holds for adaptive and randomized learners because each new label remains unbiased after the current decision is chosen.Source: §A.2 · pp. 18–19

A.3 Proof of Lemma 5.6

  • A learner with expected regret at most S_N/4 on planted instances would yield a randomized polynomial-time test distinguishing planted and null models with probability 1−o_N(1).The test averages independent runs and compares the resulting gain with S_N/2.Source: §A.3 · p. 19

A.4 Generalized construction and proof of Theorem 5.2

The generalized hypergraph construction maps planted instances to OCO losses and a switching comparator; combined with a regret guarantee, it would contradict the r-HPC conjecture. The proof also states a pruned FLH adaptive-regret bound.

A.4 Generalized construction and proof of Theorem 5.2

  • The reduction assigns p hyperedge indices to switching patterns, s to OCO coordinates, and h to repeated observations; it produces distinct queried hyperedges and polynomial length for fixed p, s, h.The coordinates are indexed by products of the sets D_j, giving dimension d=q^(2s).Source: §A.4 · pp. 20–21
  • With probability 1−o_N(1), the constructed comparator is feasible, makes O(q^p) switches, and has planted advantage on the order of q^(p+3s)/N^s.The proof establishes the advantage by counting active-block–planted-coordinate pairs and concentrating their gain.Source: §A.4 · p. 21
  • A polynomial-time learner with the assumed regret guarantee would give a randomized polynomial-time test for r-HPC, contradicting Conjecture 5.1.The assumed regret is o(S_N), and thus at most S_N/4 for sufficiently large N.Source: §A.4 · p. 22

B Follow-the-Leading-History and the Switching Bound

  • Pruned Follow-the-Leading-History keeps O(log T) active experts, with exp-concavity controlling aggregation cost and pruning providing interval coverage.The resulting adaptive-regret bound is stated in Theorem 4.1.Source: B Follow-the-Leading-History and the… · p. 22

B.1 Proof of the Switching Corollary

The switching-corollary proof divides a comparator path into maximal constant segments and sums adaptive-regret bounds over them. The accompanying figure illustrates how queried hyperedges become losses in active OCO blocks.

B.1 Proof of the Switching Corollary

  • Summing the adaptive-regret bounds over a comparator’s at most k+1 maximal constant segments yields the claimed switching bound.Each segment’s constant comparator value is a possible fixed decision on that interval.Source: §B.1 · p. 24

C From a Hypergraph to an OCO Block

  • Figure 3 traces a queried four-vertex hyperedge to its OCO-block cell; clique membership forces +1 labels on C3 × C4, while remaining labels are fair signs conditional on the clique.The comparator predicts γ on C3 rows throughout the block; the grouped grid is schematic.Source: Figure 3 · p. 25, C From a Hypergraph to an OCO Block · p. 25
Loading 2610.20416v1…