betaFeedback

WorksMathematics

An Ω(T3/4)Ω(T^{3/4}) lower bound for projection-free online learning with linear minimization oracles

Abstract

This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank–Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as T3/4T^{3/4} (where TT is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as T3/4T^{3/4}. We answer that question, proving a universal worst-case regret lower bound Ω(T3/4m−1/4)Ω(T^{3/4} m^{-1/4}) for any projection-free algorithm that makes at most mm linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound O(max⁡{T3/4m−1/4,T})O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \}).

Introduction

We consider online convex optimization (OCO) over a convex compact decision set K⊂RnK \subset\mathbb{R}^{n} (also called, for brevity, a body) of diameter at most DD, where a learner and an adversary play for TT rounds. At round tt, the learner plays xt∈Kx_t \in K, the adversary reveals a convex LL-Lipschitz loss ftf_t, and the learner suffers ft(xt)f_t(x_t) and observes a subgradient gt∈∂ft(xt)g_t \in\partial f_t(x_t). The quality of the sequence x0,x1,…,xT−1x_0,x_1,\ldots,x_{T-1} is then quantified by its regret against the best fixed point in hindsight,

Reg⁡T=∑t<Tft(xt)−min⁡u∈K∑t<Tft(u).\operatorname{Reg}_{T} = \sum_{t<T} f_t(x_t) - \min_{u\in K} \sum_{t<T} f_t(u).

OCO is detailed in [8, 18]. Online gradient descent [23] guarantees the minimax rate Reg⁡T=O(LDT)\operatorname{Reg}_{T} = O(LD\sqrt{T}) but requires a Euclidean projection onto KK at every round. For many sets of interest, such as nuclear-norm balls and flow, matching or matroid polytopes, the projection is the bottleneck, while a linear minimization oracle (LMO) over KK is cheap, e.g., via a leading singular pair or a combinatorial subroutine. Projection-free methods replace the projection by an LMO, which returns a minimizer of ⟨d,⋅⟩\langle d,\cdot\rangle over KK for a given direction dd. In offline convex optimization, this yields the classical Frank–Wolfe method [4]. The Online Frank–Wolfe (OFW), introduced by Hazan and Kale [9], calls the LMO once per round using the gradient of a regularized cumulative loss, and moves a fraction of the way towards the returned vertex. OFW guarantees Reg⁡T=O(LDT3/4)\operatorname{Reg}_{T} = O(LD T^{3/4}) for convex Lipschitz losses [9, 8].

The central question of this paper is whether the gap between the O(T)O(\sqrt{T}) and the O(T3/4)O(T^{3/4}) can be bridged. In particular, is the O(T3/4)O(T^{3/4}) precisely the price to pay for accessing KK only through m=O(1)m=O(1) linear optimization calls per round, or is it an artifact of the current analysis and parameter choices in OFW? The question is stated as open by Mhammedi [15] and by Weibel et al. [20]. The latter reports an optimized variant of the OFW obtained through performance estimation problems [7], along with strong numerical evidence that no method within the class of OFW, that performs no more than mm LMO calls per round beats O(T3/4)O(T^{3/4}). This work answers positively: in high dimension (n≥Tn \ge T), Ω(T3/4m−1/4)\Omega(T^{3/4}m^{-1/4}) is the price of the LMO model.

Related work

In projection-free online learning, beating the O(T3/4)O(T^{3/4}) rate with m=1m = 1 requires either stronger oracles than LMOs or extra assumptions on the decision set KK or on the losses. Membership oracles (Levy and Krause, [12]; Mhammedi, [14]) and separation oracles (Garber and Kretzu, [6]; Mhammedi, [15]) lead to T\sqrt{T} rates. Here, we assume that the learner only has access to an LMO. With one LMO call per round, strongly convex decision sets allow T2/3T^{2/3} for convex losses (Wan and Zhang, [19]), and curvature of the set can be exploited further (Mhammedi, [13]). On polytopes, local LMOs give T\sqrt{T} with constants depending on the dimension and geometry (Garber and Hazan, [5]).

For decision sets of finite dimension nn, Follow-the-Perturbed-Leader (FTPL) achieves O(n1/4T)O(n^{1/4}\sqrt{T}) (Kalai and Vempala, [11]; Abernethy et al., [1]) and O(nT2/3)O(\sqrt{n}T^{2/3}) (Hazan and Minasyan, [10]) on linear and smooth losses respectively, but with dimension-dependent multiplicative constants that blow up with nn. In particular, FTPL may achieve o(T3/4)o(T^{3/4}) regret when n=o(T)n = o(T). So no lower bound of order T3/4T^{3/4} can hold for randomized learners on bodies of dimension o(T)o(T), and the dimension of a hard instance must grow with TT. In fixed dimension, polynomially many oracle calls also simulate a separation oracle by cutting-plane methods. Our lower bounds are therefore valid under a classical large-scale assumption: the dimension must be larger than 2mT2mT for span methods (see definition in § 1.3) and ≳(mT)7/2\gtrsim(mT)^{7/2} for arbitrary learners.

Our lower-bound hard instance for span methods adapts the chain principle of the classical lower bounds for first-order methods restricted to the span of past gradients (Nemirovski and Yudin, [16]; Nesterov, [17]): the oracle reveals the instance one element at a time, so that after kk queries a span method knows nothing beyond the kk-th element while the comparator sits at the end of the chain. Our extension to all learners follows Woodworth and Srebro [21] and Carmon et al. [3]: a random rotation hides the chain in a high-dimensional space, so that, with high probability, no query of the learner has a significant component along the directions not yet revealed, and the oracle answers as it would to a span method.

Setting

We consider the following online learning framework: a learner plays against an adversary over TT rounds, and the goal of the learner is to minimize its regret. At the start of the game, the adversary chooses an instance of the game.

Instance, oracle and learner. An instance of the game is given by a triple (K,LMO,(gt)t<T)(K,\mathrm{LMO},(g_t)_{t<T}), fixed before the game (oblivious adversary), where:

– KK is a convex compact decision set in Rn\mathbb{R}^n;

– LMO:Rn→K\mathrm{LMO} : \mathbb{R}^n \to K is a linear minimization oracle, that solves LMO(d)∈arg min⁡x∈K⟨d,x⟩\mathrm{LMO}(d) \in\operatorname*{arg\,min}_{x\in K}\langle d,x\rangle. When the minimizer is not unique, the oracle may return any minimizer, and our instances fix a tie-breaking rule that the learner may know.

– (gt)t<T(g_t)_{t<T} is a sequence of loss vectors in Rn\mathbb{R}^n.

The starting point x0∈Kx_0 \in K is part of the instance, hence chosen by the adversary. Since the problem is invariant under translations, we fix x0=0x_0 = 0.

In each round t=0,…,T−1t = 0,\ldots,T - 1, the learner:

  1. makes (if t≥1t \ge1) at most mm oracle calls, taking the form: for 1≤k≤m1 \le k \le m, it chooses a query dt,k∈Rnd_{t,k} \in\mathbb{R}^n and receives LMO(dt,k)∈K\mathrm{LMO}(d_{t,k}) \in K,

  2. plays a point xtx_t that is certified to lie in KK,

  3. observes the loss vector gtg_t.

The goal of the learner is to minimize its regret

Reg⁡T=∑t<T⟨gt,xt⟩−min⁡u∈K∑t<T⟨gt,u⟩.(1)\operatorname{Reg}_T = \sum_{t<T}\langle g_t,x_t\rangle- \min_{u\in K}\sum_{t<T}\langle g_t,u\rangle. \tag*{(1)}

It is worth emphasizing that the learner cannot project onto KK. We nevertheless make the learner slightly more powerful by granting it two extra abilities: in our lower bound (recall we fixed x0=0x_0 = 0) it knows a radius r>0r > 0 such that Br={x∈Rn:∥x∥≤r}⊆KB_r = \{x \in\mathbb{R}^n : \lVert x\rVert\le r\} \subseteq K, and it may use internal randomness ξ\xi, independent of the instance. Queries and plays may be arbitrary measurable functions of ξ\xi and of everything observed so far. A point is certified if it lies in KK for every instance consistent with information collected so far: for example, any point of the convex hull of BrB_r and of the oracle’s answers so far is certified.

Why linear losses? A linear loss x↦⟨gt,x⟩x \mapsto\langle g_t,x\rangle with ∥gt∥≤L\lVert g_t\rVert\le L is convex and LL-Lipschitz, and observing gtg_t is equivalent to observing the whole loss ftf_t. So, a lower bound proved with linear losses and full information also holds for convex LL-Lipschitz losses under every feedback model that includes a subgradient at the played point. Hence, we assume linear losses.

Contributions

Lower bound for span methods (Section 2). Our first contribution (Theorem 2.2) is a single fixed instance, (K,LMO,(gt)t<T)(K,\mathrm{LMO},(g_t)_{t<T}), that may be known beforehand by the learner, and that is hard for a large subclass of learners called span methods. This subclass restrict the learner to query LMOs in the span of past observations and play points xtx_t in the convex hull of the starting point and the past LMOs’ outputs (see Theorem 2.1). In particular, this subclass contains all OFW tunings considered by Weibel et al. [20], thereby answering their open question.

More precisely, the hard instance is defined by a set KK of dimension 2mT2mT with diameter 11, and gradients gtg_t with norms bounded by 11, such that any span method suffers a regret

Reg⁡T≥T3/4(4m)−1/4.\operatorname{Reg}_T \ge T^{3/4}(4m)^{-1/4}.

We restrict only the span of its queries and plays, which excludes randomized algorithms such as FTPL.

Lower bound for all learners (Section 3). Our second result and main contribution removes the span restriction on the learner, at the price of a random instance and a larger dimension nn. More precisely, Theorem 3.1 states that there exists a fixed distribution of instances with KK of dimension n≳(mT)7/2n \gtrsim(mT)^{7/2} and L=D=1L=D=1 such that every learner that makes at most mm oracle calls per round satisfies

E[Reg⁡T]≥0.23T3/4m−1/4,\mathbb{E}[\operatorname{Reg}_T] \ge0.23T^{3/4}m^{-1/4},

where the expectation is over both the instance and the learner’s randomness.

Upper bound for OFW with mm LMO calls per round (Section 4). Weibel et al. [20] gave numerical evidence that no OFW tuning making m=O(1)m=O(1) LMO calls per round beats the T3/4T^{3/4} regret, but left open how the regret depends on mm. Our third result shows that the right dependence is m−1/4m^{-1/4}. We introduce mm-step OFW (Algorithm 1), which generalizes OFW to mm LMO calls per round, and prove that its regret matches the lower bound of Theorem 2.2 for m≤Tm \le T up to a multiplicative constant. Adapting the potential-based proof of Weibel et al. [20], we show

Reg⁡T≤4.8LDmax⁡{T3/4m−1/4,T}.(2)\operatorname{Reg}_T \le4.8LD\max\left\{T^{3/4}m^{-1/4},\sqrt{T}\right\}. \tag*{(2)}

for well-chosen hyperparameters. When m=1m=1, it recovers the rate of Weibel et al. [20], while when m≥Tm \ge T, it recovers the O(T)O(\sqrt{T}) minimax rate of OCO. We also show that (2) holds, with a larger constant, for an anytime tuning of mm-step OFW, which does not need to know the horizon TT.

Lower bound for span methods

In this section, we prove the lower bound for the specific subclass of learners called span methods. The latter is large enough to contain OFW (Hazan and Kale [9]) with any number of LMO calls per round, its variants with adaptive step sizes or line search, away-step and pairwise variants, and the generalized OFW tunings of Weibel et al. [20], whose queries combine past gradients and vertices with arbitrary fixed coefficients. However, it excludes methods that compute projections, such as online gradient descent, or that randomly perturb their queries, such as FTPL.

Definition 2.1 (Span methods). A learner is a span method if:

  • its LMO queries dt,kd_{t,k} are linear combination of the starting point x0x_0, past LMO answers vs,jv_{s,j} and observed loss vectors gsg_s: for all t≥1t \ge1 and 1≤k≤m1 \le k \le m,

dt,k∈span⁡(x0,v1,1,…,v1,m,…,vt,k−1,g0,…,gt−1)d_{t,k} \in\operatorname{span}(x_0,v_{1,1},\ldots,v_{1,m},\ldots,v_{t,k-1},g_0,\ldots,g_{t-1})
vt,k=LMO⁡(dt,k);v_{t,k}=\operatorname{LMO}(d_{t,k});
  • its play points xtx_t are convex combination of past LMO answers: for all rounds t≥0t \ge0,

xt∈conv⁡({x0}∪{v1,1,…,v1,m,…,vt,m}).x_t \in\operatorname{conv}\left(\{x_0\}\cup\{v_{1,1},\ldots,v_{1,m},\ldots,v_{t,m}\}\right).

Note that only the sets of vectors from which dt,kd_{t,k} and xtx_t are formed are restricted; the linear and convex coefficients used to form dt,kd_{t,k} and xtx_t may be any functions of everything the learner knows, including its internal randomness, the decision set, the oracle’s rule, or even future losses.

Theorem 2.2 (Lower bound for span methods). Let m,T≥1m,T \ge1 and N=m(T−1)+1N=m(T-1)+1. There is a fixed instance with K⊂R2NK \subset\mathbb{R}^{2N}, D=1D=1, and ∥gt∥=1\lVert g_t\rVert=1, on which every span method making at most mm oracle calls per round has regret

Reg⁡T≥T(4N)−1/4≥T3/4(4m)−1/4.\operatorname{Reg}_T \ge T(4N)^{-1/4} \ge T^{3/4}(4m)^{-1/4}.

References

  1. [1]Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. In PMLR, editor, Proceedings of The 27th Conference on Learning Theory, volume 35, pages 807–823, 2014.arxiv.org/abs/1405.6076
  2. [2]Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
  3. [3]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184:71–120, 2020.arxiv.org/abs/1710.11606
  4. [4]Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95–110, 1956.DOI
  5. [5]Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3):1493–1528, 2016.
  6. [6]Dan Garber and Ben Kretzu. New projection-free algorithms for online convex optimization with adaptive regret guarantees. In PMLR, editor, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pages 2326–2359, 2022.
  7. [7]Baptiste Goujaud, Céline Moucer, François Glineur, Julien M. Hendrickx, Adrien B. Taylor, and Aymeric Dieuleveut. PEPit: Computer-assisted worst-case analyses of first-order optimization methods in Python. Mathematical Programming Computation, 16(3):337–367, 2024.arxiv.org/abs/2201.04040
  8. [8]Elad Hazan. Introduction to Online Convex Optimization. Foundations and Trends® in Optimization, 2 (3-4):157–325, 2016.
  9. [9]Elad Hazan and Satyen Kale. Projection-free online learning. In International Conference on Machine Learning (ICML), 2012.arxiv.org/abs/1206.4657
  10. [10]Elad Hazan and Edgar Minasyan. Faster projection-free online learning. In Conference on Learning Theory (COLT), 2020.arxiv.org/abs/2001.11568
  11. [11]Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005.
  12. [12]Kfir Levy and Andreas Krause. Projection free online learning over smooth sets. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
  13. [13]Zakaria Mhammedi. Exploiting the curvature of feasible sets for faster projection-free online learning. preprint arXiv:2205.11470, 2022a.arxiv.org/abs/2205.11470
  14. [14]Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory (COLT), 2022b.arxiv.org/abs/2111.05818
  15. [15]Zakaria Mhammedi. Online convex optimization with a separation oracle. preprint arXiv:2410.02476, 2024.arxiv.org/abs/2410.02476
  16. [16]Arkadi Nemirovski and David Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
  17. [17]Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2nd edition, 2018.DOI
  18. [18]Francesco Orabona. A modern introduction to online learning. preprint arXiv:1912.13213, 2019.
  19. [19]Yuanyu Wan and Lijun Zhang. Projection-free online learning over strongly convex sets. Proceedings of the AAAI Conference on Artificial Intelligence, 35 (11):10076–10084, May 2021.
  20. [20]Julien Weibel, Pierre Gaillard, Wouter M. Koolen, and Adrien Taylor. Optimized projection-free algorithms for online learning: construction and worst-case analysis. In PMLR, editor, Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, volume 300, pages 5122–5130, 2026.
  21. [21]Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems (NeurIPS), 2016.arxiv.org/abs/1605.08003
  22. [22]Andrew Chi-Chih Yao. Probabilistic computations: toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, pages 222–227, Providence, RI, USA, 1977.DOI
  23. [23]Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), 2003.

Paper details

vlnc:W_gfjvvqm7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Generative AI tools

View statement
Looking for related papers…
Contents