{"id":"8ee64d49-7cb6-4a89-b2e4-14377175152d","arxiv_id":"2508.16992","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An adaptive first-order algorithm achieves O(sqrt(T)) alpha-regret and O(B_T log T) + O-tilde(sqrt(T)) resource consumption for online learning with long-term adversarial constraints on alpha-approximately convex functions.","lead":"This paper designs an online learning algorithm that keeps long-term resource budgets even when costs and resource use are non-convex, as long as they belong to a broad 'approximately convex' class. It proves near-optimal regret and budget-consumption guarantees, together with a matching lower bound, in both full-feedback and bandit settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's guarantees require uniformly bounded generalized subgradients, a hypothesis not implied by the definition of Lα and not verified for the advertised applications.","rationale":"I read the proof of Theorem 4 carefully: the Lyapunov decomposition (13), the reduction of the surrogate α-regret to an OLO regret (16), the AdaGrad bound (20), and the parameter choice leading to (22) are coherent conditional on the stated uniform bound on generalized subgradients. The algebra checks out, and I found no internal contradiction that would invalidate the algorithm. The load-bearing gap is that Theorem 4's hypothesis is stronger than the class definition: Definition 1 only asserts existence of a pointwise generalized subgradient, while the proof needs a uniform bound αG to control the surrogate gradient norms in Eq. (19) and to set λ and V. Lemma 8 provides a sufficient but not necessary route to such a bound via a convex minorant, and the paper does not verify that route for any of the named applications. In particular, for DR-submodular functions the natural H is the non-oblivious gradient in Eq. (29), whose uniform boundedness and computability are not established. Because this is exactly the assumption identified by the reader as the weakest point, and because the same concern calls for additional verification rather than a rejection of the central derivation, I agree with the CONDITIONAL verdict and recommend no change. The unflagged closedness in Theorem 3 and the apparent α inconsistency in the statement of the CC bound are secondary: Theorem 4 can be read with its explicit hypothesis, and the CC bound is order-consistent up to constants. The proposed concrete test directly checks whether the bounded-subgradient hypothesis is satisfiable for a flagship claimed application, which is the condition on which the applicability of the central theorem rests.","tokens_in":24198,"tokens_out":40291,"duration_ms":450025,"concrete_test":"Fix the DR-submodular example advertised by the paper: the multilinear extension F of a submodular function over X=[0,1]^n with ||∇F||∞ ≤ L and parameter γ > 0. Evaluate G_n = sup_{x∈X} ||∫_0^1 e^{γ(z−1)}∇F(zx) dz|| for n=2 and n=32, symbolically or numerically, and check whether G_n is finite and the integral can be computed in poly(n) time from marginal-oracle evaluations of F. If G_n is finite and efficiently computable, Theorem 4's bounded-subgradient hypothesis is satisfiable for this application; if the supremum is unbounded or the integral has no polynomial-time oracle, the claimed application of Theorem 4 fails at Eq. (19).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Eq. (19) is the hinge of Theorem 4. It requires the uniform bound ||H_f||, ||H_g|| ≤ αG to write ||H_hat_f_t(x_t)|| ≤ αG(V + Φ'(Q(T))); this bound is then fed into the AdaGrad regret bound (20) and determines the Lyapunov parameter λ and the multiplier V. The paper states this uniform bound as a hypothesis, but it is not a consequence of Definition 1 or of Theorem 3(3). Theorem 3(3) only gives a convex minorant g with g ≤ f ≤ αg, and Lemma 8 transfers a uniform bound only when a subgradient of g is already uniformly bounded; no argument shows such a g exists for every f ∈ Lα, and the definition itself requires only an H(x) ∈ R^d at each point, with no uniform norm control. The advertised applications are not checked against this condition: for DR-submodular functions the proposed generalized subgradient is the integral (29), and the paper neither proves a uniform norm bound for it nor explains how to evaluate it in the oracle model; for phase retrieval, a Lipschitz or subgradient bound for the constructed g is not derived. Since the abstract and introduction claim guarantees for the whole class of α-approximately convex functions, the central applicability claim is narrower than proven. The proof itself is coherent once the bound is granted, so this is a scope gap rather than a detected contradiction in the main derivation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24491,"tokens_out":11343,"duration_ms":111156,"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":[{"comment":"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.","section":"§4 Definition 1; §5.2 Eq. (19); Theorem 4"},{"comment":"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.","section":"Theorem 3; Appendix A.2"},{"comment":"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.","section":"Theorem 4; §5.2 after Eq. (21)"},{"comment":"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.","section":"Theorem 5; Appendix B"}],"minor_comments":[{"comment":"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.","section":"§5.1, after Eq. (16)"},{"comment":"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.","section":"§4 Definition 1"},{"comment":"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.","section":"Appendix A.3, Eq. (30)"},{"comment":"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.","section":"Appendix D, Eq. (58)"},{"comment":"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.","section":"General notation"}],"recommendation":"major_revision","confidential_remarks":"The paper's main idea is sound and the upper-bound proof is coherent once the uniform-subgradient hypothesis is granted. The key issue is scope: the abstract and introduction promise results for the entire L_α class, while the theorem requires an extra uniform bound that is neither implied by the definition nor verified for the listed applications. This is fixable by a careful revision, but it is load-bearing. The lower-bound appendix is also too sketchy for a journal. I would recommend asking for a revision that reconciles the theorem statement with the proof, verifies or restricts the applications, and completes the lower-bound argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it carefully. The central reduction—Lyapunov drift plus reducing surrogate alpha-regret to OLO with AdaGrad—is real, and I didn't find a fatal flaw in the main proof. The constrained-learning analysis for alpha-approximately convex functions is new, and the equivalence characterization in Theorem 3 is a useful addition. The bandit extension with the scale-free MAB is also a genuine step beyond Immorlica et al., giving non-vacuous bounds for arbitrary budgets. Credit where due: the algebra in Section 5.2 checks out, the paper is upfront about many of its assumptions, and there's no circularity—the Sinha-Vaze result is used only for the B_T=0 baseline.\n\nThe soft spots are real but not fatal. The load-bearing assumption is the uniform bound ||H_f||,||H_g|| <= alpha G in Theorem 4. The stress-test note is right: this is not a consequence of Definition 1 or Theorem 3. Lemma 8 only transfers a bound if a convex minorant with bounded subgradients already exists, and the paper never checks that for DR-submodular functions (the non-oblivious gradient in (29) is an integral with no norm bound or oracle-evaluation argument) or for the regularized phase-retrieval objective. So the abstract's promise of guarantees for the whole class is narrower than what is proven. This is a scope gap, not a contradiction—grant the bound and the proof goes through.\n\nOther issues are minor: Theorem 3(4)=>(1) silently assumes f is closed; Theorem 4's CC statement writes O~(alpha B_T + GD sqrt(T)) while the proof gives alpha B_T + GD sqrt(T) without the alpha on the second term; the lower bound in Theorem 5 is a sketch borrowing Immorlica et al.'s construction and needs the details filled in; and the phase-retrieval appendix has a typo around (36). None of these undermine the main result.\n\nWho should read this: anyone working on constrained online learning, adversarial BwK, or non-convex online optimization. The paper deserves a serious referee. I'd send it to review, with the clear expectation that the authors either verify the uniform-subgradient bound for the advertised applications or reframe the main theorem as applying to functions satisfying that bound.","headline":"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.","tokens_in":25003,"tokens_out":2802,"would_cite":true,"duration_ms":28341,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["approximately convex functions","online convex optimization","long-term budget constraints","alpha-regret","AdaGrad","bandits with knapsacks","DR-submodular maximization","adversarial online learning"],"falsifier":"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.","tokens_in":2152,"feed_emoji":"🎯","tokens_out":3525,"duration_ms":140506,"temperature":0.7,"pith_summary":"This paper asks whether an online learner can keep cumulative cost close to the best fixed action that satisfies a long-term budget, when the per-round cost and resource-consumption functions are non-convex but only mildly so. The answer is yes for the class of $\\alpha$-approximately convex functions: Algorithm 1, a projected AdaGrad method on surrogate linear costs, attains $O(\\alpha\\sqrt{T})$ $\\alpha$-regret while consuming at most $O(B_T\\log T)+\\tilde{O}(\\sqrt{T})$ resources. The benchmark needs to be feasible only over the whole horizon, not in every round, which avoids a common vacuous-case problem. The same idea, with a power-law Lyapunov function and an adaptive bandit subroutine, covers bandit feedback and improves on the existing adversarial Bandits-with-Knapsacks guarantees. A matching lower bound shows the multiplicative $\\log T$ factor on $B_T$ cannot be removed while keeping sublinear regret, even for linear costs and constraints.","feed_headline":"Near-convex online costs: sublinear regret, log-factor budget overuse","feed_subtitle":"A first-order algorithm keeps regret near optimal while exceeding the budget by only a log factor, even with bandit feedback.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Introduces the upper-linearizable class with which $\\alpha$-approximately convex functions coincide, supplying the function class studied here.","marker":"Pedramfar and Aggarwal [2025]"},{"why":"Defines the $\\alpha$-regret performance metric used throughout the paper.","marker":"[Chen et al., 2018]"},{"why":"Provides the closest convex baseline with optimal regret and CCV bounds, and its Theorem 3 gives the additive $\\tilde{O}(\\sqrt{T})$ CCV lower bound for $B_T=0$.","marker":"Sinha and Vaze [2024]"},{"why":"Studies adversarial hard constraints without Slater's condition, giving the per-round-feasible benchmark that the paper's long-horizon benchmark improves upon.","marker":"Guo et al. [2022]"},{"why":"Supplies the adversarial Bandits-with-Knapsacks setting and the lower-bound construction that Theorem 5 adapts to prove the $\\Omega(\\log T)$ budget-factor lower bound.","marker":"Immorlica et al. [2022]"},{"why":"Provides the AdaGrad algorithm whose adaptive step sizes are used in Algorithm 1.","marker":"Duchi et al. [2011]"},{"why":"Supplies the AdaGrad regret bound (Theorem 9) used to control the surrogate online linear optimization regret.","marker":"Orabona [2019]"},{"why":"Provides the scale-free multi-armed bandit algorithm whose regret bound drives the bandit version of the main result.","marker":"Putta and Agrawal [2022]"},{"why":"Supplies the non-oblivious gradient identity for weakly DR-submodular functions used to prove that such functions are approximately concave.","marker":"Zhang et al. [2022]"}],"fun_headline_variants":["Near-convex online: sublinear regret, log-factor budget slip","Budget-constrained learning: tight regret for approximately convex","Online learning with budgets: a log factor is all it costs","Bandit or full info: near-convex budgets solved tightly"],"cache_read_input_tokens":27136,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near-convex online: sublinear regret, log-factor budget slip","Budget-constrained learning: tight regret for approximately convex","Online learning with budgets: a log factor is all it costs","Bandit or full info: near-convex budgets solved tightly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000713,"raw_usage":{"total_tokens":3269,"prompt_tokens":1071,"completion_tokens":2198,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":2128}},"tokens_in":687,"tokens_out":2198,"duration_ms":15618,"temperature":1.0,"reasoning_tokens":2128,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:12:21.958198+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the AdaGrad regret bound (Theorem 9) used to control the surrogate online linear optimization regret."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the non-oblivious gradient identity for weakly DR-submodular functions used to prove that such functions are approximately concave."}],"review_version":1}