REVIEW 4 major objections 5 minor 15 references
Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Online learning with long-term adversarial budgets is tractable for alpha-approximately convex costs, giving O(sqrt T) alpha-regret and a log-factor overrun.
desk verdict The Lyapunov+AdaGrad reduction is sound and the results are new, but the paper claims more for the whole class L_alpha than the uniform-subgradient assumption actually proves. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the class of $\alpha$-approximately convex functions, equivalently upper-linearizable functions: $f(x)\le \alpha f(u)+\langle H(x),x-u\rangle$. Theorem 3 characterizes this class by sandwiching $f$ between a convex function $g$ and $\alpha g$, by an approximate Jensen inequality, and by the biconjugate bound $f(x)\le \alpha f^{**}(x)$. The argument's engine is the regret-decomposition inequality $\Phi(Q(T))-\Phi(Q(0))+V\,\mathrm{Regret}_T(\alpha)\le \mathrm{Regret}'_T+\alpha\Phi'(Q(T))B_T$, which reduces the constrained problem to an unconstrained online linear optimization problem with surrogate gradients $H_{\hat f_t}(x_t)=V H_{f_t}(x_t)+\Phi'(Q(t))H_{g_t}(x_t)$. Choosing the exponential Lyapunov function and AdaGrad's self-tuning step sizes converts this inequality into the stated regret and consumption bounds; the bandit version replaces AdaGrad with a scale-free multi-armed bandit learner.
What would settle it
Find a function in $\mathcal{L}_\alpha$ whose generalized subgradient selections can be chosen at every point but whose minimal-norm selections have unbounded norm along a sequence in $\mathcal{X}$; then Eq. (19), which needs $\|H_{g_t}(x_t)\le \alpha G$ for the AdaGrad regret bound, is violated, so Theorem 4's rate for Algorithm 1 does not follow for that function.
Extended reading notes
Core claim
The central discovery is that long-term budget constraints do not break online learning when the cost and resource functions are $\alpha$-approximately convex, i.e. they satisfy $f(x)\le \alpha f(u)+\langle H(x),x-u\rangle$ for some generalized subgradient $H(x)$. Theorem 4 states that Algorithm 1, which feeds the surrogate costs $\hat f_t=V f_t+\Phi'(Q(t))g_t$ into AdaGrad with an exponential Lyapunov function $\Phi(x)=\exp(\lambda x)$, achieves $\mathrm{Regret}_T(\alpha)=O(\alpha\sqrt{T})$ against the best fixed action feasible over the whole horizon, and $\mathrm{CC}_T=\tilde{O}(\alpha B_T+GD\sqrt{T})$. The proof routes the constrained problem through a regret-decomposition inequality: the Lyapunov drift plus $V$ times the original $\alpha$-regret is controlled by the standard regret of an online linear optimization problem on the surrogate gradients. In the bandit setting the same decomposition, with a power-law Lyapunov function and a scale-free adversarial bandit algorithm, yields $\tilde{O}(K\sqrt{T})$ regret and $\tilde{O}(K\sqrt{T})+O(B_T\log T)$ expected consumption, and the paper proves matching lower bounds showing the $\log T$ multiplier on the budget is unavoidable.
Load-bearing premise
The proof assumes a uniform a priori bound $\|H_f(x)\|,\|H_g(x)\|\le \alpha G$ on every generalized subgradient at every round and every point of the decision set; if no such global $G$ is known, the AdaGrad and exponential-Lyapunov calculations in Eqs. (19)--(22) do not produce the stated rates.
Editorial extensions
If this is right
- For any budget $B_T\ge 0$, including $B_T=0$, the algorithm returns an $O(\sqrt{T})$ $\alpha$-regret and a cumulative overconsumption of $\tilde{O}(\sqrt{T})$; setting $B_T=0$ recovers the per-round feasibility setting.
- The algorithm needs no Slater condition, no NULL arm, and no prior guess at the optimal benchmark value; the benchmark must only be feasible in aggregate over the horizon.
- For adversarial Bandits with Knapsacks, the bandit version achieves $\tilde{O}(K\sqrt{T})$ regret with $O(B_T\log T)+\tilde{O}(K\sqrt{T})$ expected consumption, improving on primal-dual methods whose guarantees can be vacuous when $B_T$ is small.
- The lower bound shows that any online policy with sublinear regret must exceed the budget by a factor $\Omega(\log T)$ in the worst case, even for linear costs and consumptions, so the $O(\log T)$ multiplier is not an artifact of the algorithm.
- The same Lyapunov-plus-OLO decomposition extends to multiple resources, bounding each resource's cumulative consumption by $O(\alpha B_T+GD\sqrt{T})\log T$.
Reading between the lines
- If the bounds are correct, the exponential Lyapunov derivative acts as an online dual price for the resource: the algorithm never estimates the optimal dual variable explicitly but discovers it through the surrogate linear cost, which suggests the reduction may extend to nonconvex losses beyond $\alpha$-approximate convexity whenever a linear surrogate with bounded subgradients exists.
- The $\log T$ factor is proved necessary against a worst-case adversary; a natural next step is to test whether stochastic or slowly drifting constraints allow a constant-factor overrun, since the lower-bound construction selects the good phase adversarially.
- For DR-submodular maximization, the membership result rests on the non-oblivious gradient being an integral (Eq. 29); whether that integral can be evaluated efficiently for a given submodular oracle is a structural question the paper does not settle, and it determines whether the bounds are implementable in practice.
- The lower-bound proof rescales the adversarial BwK construction, so the $\log T$ in budget overrun appears to be inherited from the need to identify a good stationary policy; comparing instead to a time-varying feasible benchmark might sidestep the factor, at the cost of a different performance measure.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online learning with a long-term budget constraint in the adversarial setting, where each round the learner chooses an action from a convex set and then pays an α-approximately convex cost and consumes an α-approximately convex resource. The benchmark is the best fixed action that satisfies the long-term budget constraint. The authors propose Algorithm 1, which combines an exponential Lyapunov function with AdaGrad on a surrogate linearized cost, and prove guarantees of the form Regret_T(α)=O(α√T) and CC_T=Õ(αB_T+GD√T). They also give a bandit version (Algorithm 2) with Õ(K√T) regret and Õ(K√T+B_T log T) consumption, a characterization theorem for the class L_α, and a lower bound (Theorem 5) asserting that the multiplicative log factor in the consumption bound is necessary. The main analysis in Section 5.2 is a regret-decomposition inequality reducing the constrained problem to unconstrained OLO with AdaGrad.
Significance. If the caveats below are resolved, the paper is a substantial contribution: it appears to give the first sublinear-regret and near-budget-consumption guarantees for online learning with α-approximately convex costs and constraints against a long-term-feasible fixed benchmark, and the bandit corollary offers an improved, first-order adversarial BwK guarantee relative to prior primal-dual methods. The regret-decomposition argument in Section 5.2 is clean, the use of AdaGrad avoids requiring a priori knowledge of the surrogate gradient scale, and the derivation is parameter-free in the sense of relying on standard external regret bounds rather than fitted constants. The characterization Theorem 3 is also useful, connecting L_α to convex minorants and approximate Jensen inequalities. However, the central applicability claim is currently narrower than advertised because the main theorem requires a uniform bound on generalized subgradients that is not part of Definition 1 and is not verified for the stated applications.
major comments (4)
- [§4 Definition 1; §5.2 Eq. (19); Theorem 4] The abstract, introduction, and Theorem 4 claim guarantees for the class of α-approximately convex functions, but the proof of Theorem 4 relies on the additional hypothesis that all generalized subgradients satisfy ||H_f(x)||, ||H_g(x)||≤αG for every round and every x∈X (Eq. (19)). This uniform norm bound is not a consequence of Definition 1, which only requires a vector H(x) at each point, nor of Theorem 3(3), which provides a convex minorant g≤f≤αg without any subgradient bound. Lemma 8 transfers a uniform bound only when the convex minorant already has uniformly bounded subgradients, and no argument shows such a minorant exists for every f∈L_α. Moreover, the advertised applications are not checked against this condition: for DR-submodular functions the proposed generalized subgradient in Eq. (29) is an integral whose uniform norm boundedness and oracle computability are not established, and for phase retrieval (Appendix A.4) no Lipschitz or subgradient bound for the constructed convex minorant is derived. Since the paper presents these results as valid for the whole class L_α, the scope of the central applicability claim is narrower than proven. Please either add the uniform-bound condition to the class definition and verify it for all listed applications, or qualify the abstract and introduction accordingly.
- [Theorem 3; Appendix A.2] The proof of part (4)=>(1) in Theorem 3 explicitly states 'Assuming f to be a closed function', but closedness is not listed as a hypothesis in the theorem statement. Without closedness (or an equivalent lower-semicontinuity assumption), the step f(x)=lim_k f(x_k) in the proof is unjustified, so the equivalence as stated is not established. Please add the closedness assumption to the theorem or supply an argument that avoids it.
- [Theorem 4; §5.2 after Eq. (21)] The displayed choice of λ in the proof and the final cumulative-consumption bound Q(T)≤λ^{-1}O(logT)=(αB_T+GD√T)O(logT) are inconsistent. With λ chosen so that λα(GD√2T+B_T)=1/2, one has λ^{-1}=2α(GD√2T+B_T), which gives Q(T)=O(αGD√T+αB_T)logT; if instead λ is read as (2(αGD√2T+αB_T))^{-1}, the resulting bound is again O(αGD√T+αB_T). In either reading the theorem's stated CC_T=Õ(αB_T+GD√T) drops a factor α in front of GD√T, and the proof's final equality is not justified. Please correct the parameter choice, the calculation, or the theorem statement so they are mutually consistent.
- [Theorem 5; Appendix B] The lower-bound result is presented as a proof outline and is not a complete proof. The rescaling argument converting the online policy π into a feasible policy π′ needs a careful treatment of the comparison between a randomized benchmark (π⋆ 'samples actions from a fixed distribution') and the optimal policy in the Immorlica et al. construction, and the displayed budget choice 'B_T=√2 max(√T h(T), s(T))' is not consistent with the later use of B_T≥√(2Th(T)) and B_T≥√(2s(T)). Since the paper claims matching lower bounds, please either complete the proof or clearly state the result as contingent on the cited construction.
minor comments (5)
- [§5.1, after Eq. (16)] The text says 'Combining Eqns. (13) and (47)', but Eq. (47) appears only later in Appendix C; the intended reference is presumably to the AdaGrad regret bound in Theorem 9 or Eq. (20). Please fix the cross-reference.
- [§4 Definition 1] The phrase 'uniformly for any x,u∈X' is ambiguous. Please state the quantifier explicitly: for every x∈X there exists H(x) such that the inequality (9) holds for all u∈X.
- [Appendix A.3, Eq. (30)] The proof of Theorem 6 relies on w(z) and θ(w) from Zhang et al. without defining them; the argument is not self-contained. Please state the needed expressions or give a direct proof.
- [Appendix D, Eq. (58)] In the reproduced regret bound of Putta and Agrawal, the square-root expression contains 'N' where the context indicates the number of arms K. Please check and correct the notation.
- [General notation] The symbol F is used both for the maximum value of the cost function in §5.2 and for the DR-submodular function in Appendix A.3; please disambiguate these uses.
Circularity Check
No circularity: the main bound is a direct reduction to AdaGrad-based OLO with explicit hypotheses, and self-citations are not load-bearing.
full rationale
The derivation chain is self-contained as an upper-bound proof. Definition 1 gives the α-approximate convexity inequality; Proposition 2 closes the surrogate class under non-negative combinations; the surrogate f_hat_t = V f_t + Phi'(Q(t)) g_t is therefore α-approximately convex with generalized subgradient H_fhat_t = V H_f_t + Phi'(Q(t)) H_g_t. Inequality (15) converts the surrogate α-regret into standard OLO regret, and Theorem 9 (a standard AdaGrad bound) bounds that OLO regret under the explicitly stated uniform bound ||H_f||, ||H_g|| ≤ αG. The parameters V and lambda are closed-form functions of (α, G, D, T, B_T), not fitted to data, and no 'prediction' is a renamed input. The only self-citations are to Sinha and Vaze for the B_T = 0 lower-bound baseline and as related work; these are not used to prove Theorem 4 or Theorem 10, so they are not load-bearing. The uniform generalized-subgradient bound is a stated extra hypothesis rather than a consequence of Definition 1; if this condition is not verified for the advertised applications, that is a scope or correctness caveat, not a circular reduction. The bandit proof similarly relies on the external scale-free MAB regret bound of Putta and Agrawal. No step in the paper reduces by construction to its own input.
Assumptions & free parameters
assumptions (6)
- domain assumption The cost and constraint functions f_t and g_t belong to the class L_alpha with generalized subgradients uniformly bounded by alpha G.
- domain assumption The feasible set X* = {x : sum_t g_t(x) <= B_T} is non-empty.
- standard math AdaGrad satisfies the adaptive regret bound of Theorem 9 from Orabona (2019).
- standard math The scale-free MAB algorithm of Putta and Agrawal satisfies the regret bound in Theorem 11.
- standard math The Immorlica et al. adversarial BwK lower bound (their Theorem 8.1 and Lemma 8.9) is valid.
- ad hoc to paper In Theorem 3, part (4) implies (1), the function f is assumed closed, although closedness is not stated in the theorem.
Cite this review
Pith. "Pith review of Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints." pith.science (2026). https://pith.science/paper/EPEC5X6P
@misc{pith2026250816992,
author = {Pith},
title = {Pith review of: Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/EPEC5X6P}},
note = {Machine review of arXiv:2508.16992}
}
abstract
We study an online learning problem with long-term budget constraints in the adversarial setting. In this problem, at each round $t$, the learner selects an action from a convex decision set, after which the adversary reveals a cost function $f_t$ and a resource consumption function $g_t$. The cost and consumption functions are assumed to be $\alpha$-approximately convex - a broad class that generalizes convexity and encompasses many common non-convex optimization problems, including DR-submodular maximization, Online Vertex Cover, and Regularized Phase Retrieval. The goal is to design an online algorithm that minimizes cumulative cost over a horizon of length $T$ while approximately satisfying a long-term budget constraint of $B_T$. We propose an efficient first-order online algorithm that guarantees $O(\sqrt{T})$ $\alpha$-regret against the optimal fixed feasible benchmark while consuming at most $O(B_T \log T)+ \tilde{O}(\sqrt{T})$ resources in both full-information and bandit feedback settings. In the bandit feedback setting, our approach yields an efficient solution for the $\texttt{Adversarial Bandits with Knapsacks}$ problem with improved guarantees. We also prove matching lower bounds, demonstrating the tightness of our results. Finally, we characterize the class of $\alpha$-approximately convex functions and show that our results apply to a broad family of problems.
Reference graph
Works this paper leans on
-
[1]
We now modify the policy π to obtain a new online policy π′ which is feasible
Note that the policy π is not necessarily feasible as its cumulative consumption after T rounds may exceed the budget BT. We now modify the policy π to obtain a new online policy π′ which is feasible. The modified policy π′ pulls armA1 with probability xt/η(T ) and armA0 with probability 1−xt/η(T ) on round t, where η(T ) = κ + s(T) BT . Due to the linear...
work page 2022
-
[2]
In phase σ∈ [τ], armA1 has reward σBT/T in each round
Next, we define T/BT problem instances: for instance Iτ,τ ∈ [T B ], armA1 has positive rewards up to and including phase τ; rewards for all subsequent phases are zero. In phase σ∈ [τ], armA1 has reward σBT/T in each round. Arm A1 consumes unit resource in each round. On the other hand, arm A0 has zero rewards and zero consumptions on all rounds for all in...
work page 2022
-
[3]
7: Estimation Scheme: ˜ℓt(i) = ˆℓt(it) p′ t(it)1(it =i),∀i
Algorithm 3 Scale-Free Multi Armed Bandit 1: Parameter inititalization: η0 =K, γ0 = 1/2 2: Regularizer: F (q) =PK i=1 (f(q(i))−f(1/K)), where f(x) =− log(x) 3: Initialization: p1 = (1/K,..., 1/K) 4: for t = 1 to T do 5: Sampling Scheme: p′ t = (1−γt−1)pt + γt−1 K 6: Sample arm it∼p′ t and see loss ˆℓt(it). 7: Estimation Scheme: ˜ℓt(i) = ˆℓt(it) p′ t(it)1(...
work page 2022
-
[7]
A.2 Proof of Theorem 3 (1) =⇒ (2): Since f is α−approximately convex, for a given x∈X , ∃g′∈ Rn s.t
Then for Hh =c1Hf +c2Hg the following holds h(x)−αh(u)≤⟨Hh(x),x−u⟩ (25) Thush∈L α. A.2 Proof of Theorem 3 (1) =⇒ (2): Since f is α−approximately convex, for a given x∈X , ∃g′∈ Rn s.t. f(x)≤αf(u) +⟨g′,x−u⟩, ∀u∈X ⇔∃g∈ Rn s.t. f(x) α ≤f(u) +⟨g,x−u⟩, ∀u∈X ⇔ f(x) α ≤ sup g∈Rn inf u∈X (f(u) +⟨g,x−u⟩) ⇔ f(x) α (a) ≤ sup g∈Rn (⟨g,x⟩− f⋆(g)) ⇔f(x) (b) ≤ αf⋆⋆(x), (...
work page 2003
-
[8]
Then from Theorem 3, part 3, there exists a convex function g such that g(x)≤ f(x)≤ αg(x),∀x∈X
Let f be an α-approximately convex function with domain X. Then from Theorem 3, part 3, there exists a convex function g such that g(x)≤ f(x)≤ αg(x),∀x∈X . If h(x) is a sub-gradient of g at the point x∈X then αh(x) is a generalized sub-gradient of f at x∈X . As a corollary, if ||h(x)||2≤ G,∀x∈X , then the ℓ2-norms of the generalized subgradients of f as c...
work page 2019
-
[9]
[Orabona, 2019, Theorem 4.14] The AdaGrad policy, with the above step size sequence, achieves the following regret bound for the standard OCO problem: RegretT≤ √ 2D vuut TX t=1 G2 t. (41) B Proof of Theorem 5 Consider an ensemble of constrained learning problems defined in Section 3 with linear rewards, where each instance consists of two arms A0,A1 and a...
work page 2019
-
[12]
Adding V (lt(at)−lt(a⋆)) to both sides of the above inequality, we obtain: Φ(Q(t))− Φ(Q(t− 1)) +V (lt(at)−lt(a⋆)) ≤ Vlt(at) +eΦ′(Q(t− 1)ct(at) − Vft(x⋆) +eΦ′(Q(t− 1))ct(a⋆) +eΦ′(Q(t− 1))ct(a⋆), (53) where the comparator a⋆ is taken to be a fixed randomized benchmark action that minimizes the expected cumulative costs subject to that it satisfies the budge...
work page 2022
-
[13]
and its analysis can be extended to the setting where the learner receives bandit feedback, i.e., only the losses and consumption of the selected actions are revealed to the learner. The setting we consider here is the same as the Bandits with Knapsacks (BwK) problem, considered by Immorlica et al. [2022], with the key difference that, in our case, the in...
work page 2022
Show all 15 references
-
[2004]
Online learning with knapsacks: the best of both worlds
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767–2783. PMLR, 2022a. Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A...
1905
-
[2013]
No-regret learning under adversarial resource con- straints: A spending plan is all you need! arXiv preprint arXiv:2506.13244,
Francesco Emanuele Stradi, Matteo Castiglioni, Al- berto Marchesi, Nicola Gatti, and Christian Kroer. No-regret learning under adversarial resource con- straints: A spending plan is all you need! arXiv preprint arXiv:2506.13244,
-
[2017]
A modern introduction to online learning
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213 ,
1912 arXiv
-
[2022]
states that, for any two vectors x,y∈X , we have D y−x,∇eF (x) E ≥γ Z 1 0 w(z)dz (F (y)−θ(w)F (x)), (30) where the expressions w(z) and θ(w) have been defined in Zhang et al. [2022]. Using expressions of w(z) and θ(w) from Theorem 1 of Zhang et al. [2022], we obtain the desire...
2022
-
[2023]
Online convex optimiza- tion with time-varying constraints
Michael J Neely and Hao Yu. Online convex optimiza- tion with time-varying constraints. arXiv preprint arXiv:1702.04783,
-
[2024]
Aleksandrs Slivkins
URL https://openreview.net/forum?id=TxffvJMnBy. Aleksandrs Slivkins. Dynamic ad allocation: Bandits with budgets. arXiv preprint arXiv:1306.0155,
-
[2025]
BanditQ - Fair Multi-Armed Bandits with Guaranteed Rewards per Arm
Abhishek Sinha. BanditQ - Fair Multi-Armed Bandits with Guaranteed Rewards per Arm. arXiv preprint arXiv:2304.05219,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.