Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization

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

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

Pith's one-line read This paper claims that projecting each online gradient step onto the latest feasible set keeps regret optimal and makes cumulative constraint violations constant for structured constraint sets, with an instance-dependent bound in general.

desk verdict The OCS and sphere/box O(1) CCV results are the real advance; the general instance-dependent bound is trajectory-dependent and has an unproven key lemma. read the letter →

arxiv 2502.05019 v1 pith:NKNT5KEW submitted 2025-02-07 cs.LG cs.DS

Rahul Vaze , Abhishek Sinha This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q3268W2790C2552A20
keywords constrainedonlineconvexoptimizationcumulativeconstraintviolationstaticregretnestedsetsmeanwidthprojectionalgorithmsatisfactionself-expandedcurves
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

Constrained online convex optimization (COCO) asks a learner to choose actions online when both a loss function and a constraint function are revealed after each action; the two goals are low static regret and low cumulative constraint violation (CCV). Prior algorithms achieved O(√T) regret and O(√T log T) CCV universally, but this paper argues that this CCV rate is needlessly pessimistic because it ignores the geometry of the nested feasible sets $S_t$. The proposed Algorithm 2, an online projected-gradient rule that projects each step onto the most recent feasible set, achieves O(√T) regret and, for 'nice' sets such as spheres and axis-parallel cuboids, CCV = O(1), independent of $T$. For arbitrary convex sets, the CCV is bounded by an instance-dependent quantity $\mathcal{V}$ that couples the distance between consecutive feasible sets, their shapes, and the dimension. A switching algorithm then guarantees the best of the two bounds, $\min\{\mathcal{V}, O(\sqrt{T}\log T)\}$. If correct, this shows that constraint geometry, not just constraint functions, controls how quickly violations can be driven to a constant.

What carries the argument

The machinery is the nested convex body $S_t$ together with the projection curve traced by the algorithm's action sequence. Algorithm 2's update is $x_{t+1} = P_{S_t}(P_{S_{t-1}}(x_t - \eta_t \nabla f_t(x_t)))$, so every violation is bounded by the segment from $x_t$ to its projection onto $S_t$. The total movement cost of these projection segments is bounded in two complementary ways. For well-shaped sets, a direct diameter-shrinkage argument gives $O(d^{3/2}D)$. In general, the paper introduces a cone $C_{w_t}(c_t)$ that contains the convex hull of the midpoint between $x_t$ and its projection and the whole body $S_t$; the scalar $c^\star_t$ measures the angular half-width of that cone. Lemma 21 shows that each projection decreases the mean width $W(S_t)$ by at least $\frac{V_{d-1}}{2V_d(d-1)} \|x_t - b_t\| (c^\star_t)^d$, and because mean width is bounded between $0$ and the diameter, summing telescopes to the bound on total movement. For OCS and the $d=2$ monotone case, the reverse projection curve is self-expanded, and a classical length bound for such curves gives constant CCV.

What would settle it

Take $d=2$, let $S_t$ be the unit disk, place $x_t$ at distance $1+\delta$ from the center with $\delta=0.1$, and let $b_t$ be its projection on the boundary. Compute the cone parameter $c^\star_t$ from Definition 10 and the exact mean-width difference $W(\mathrm{conv}(m_t \cup S_t)) - W(\mathrm{conv}(x_t \cup S_t))$ using $W(K) = \mathrm{Perimeter}(K)/\pi$; if this difference violates the lemma's claimed lower bound $\frac{V_{d-1}}{2V_d(d-1)} \delta (c^\star_t)^d$, then Theorem 12's bound on total movement cost is void. Repeating this computation across a range of $\delta$ values and, more generally, on a sequence of nested ellipses of growing eccentricity, would settle whether the geometric argument is correct.

Watch

Extended reading notes

Core claim

The central claim is that the cumulative constraint violation of a natural projected-gradient algorithm is governed by the geometry of the nested bodies $S_t = \cap_{\tau \leq t} G_\tau$, not by the difficulty of optimizing the constraint functions. Each round, Algorithm 2 takes one gradient step from the previous action, projects onto $S_{t-1}$ to form an intermediate point, and then projects onto $S_t$; the per-round violation is at most $G$ times the distance from $x_t$ to its projection on $S_t$. Bounding these distances is equivalent to bounding the total movement cost $M_T$ of the projection sequence. For nested spheres and axis-parallel cuboids this cost is $O(d^{3/2}D)$ (Lemmas 8 and 9). For general convex sets, the cost is bounded through a mean-width argument: each projection reduces the mean width of the constraint set by an amount controlled by a cone parameter $c^\star_t$, and summing these reductions gives $M_T \le \frac{2V_d(d-1)}{V_{d-1}} \left(\frac{1}{c^\star}\right)^d D$ (Lemma 11, Theorem 12). The paper then combines this algorithm with the prior universal algorithm in a switching rule, obtaining CCV $= \min\{ \text{that geometric bound}, O(\sqrt{T}\log T) \}$ while preserving $O(\sqrt{T})$ regret (Theorem 13). For the special cases where all costs vanish (OCS) and for the two-dimensional monotone-rotation case, the projection curve is shown to be a 'self-expanded curve', yielding CCV $= O(d^{d/2}D)$ and $O(GD)$, respectively (Theorems 16 and 17).

Load-bearing premise

The general CCV bound holds only if the geometric parameter $c^\star$, which is defined from the algorithm's own successive actions and is not guaranteed by the problem, stays bounded away from zero; if it can be driven small, the claimed instance-dependent improvement collapses to the old $O(\sqrt{T}\log T)$ bound.

Editorial extensions

If this is right

  • For nested feasible sets that are spheres or axis-parallel cuboids, Algorithm 2 achieves O(√T) regret and O(1) CCV for arbitrary convex losses, a qualitative jump from the previous O(√T log T) violation bound.
  • For the online constraint satisfaction problem (zero costs), the same algorithm yields CCV = O(d^{d/2} D), independent of the horizon, and the projection curve length is O(D).
  • In two dimensions, when the projection hyperplanes rotate monotonically, the CCV is O(GD), again independent of T.
  • For arbitrary convex sets, the switching algorithm ensures that the CCV is never worse than O(√T log T), while retaining the smaller instance-dependent bound whenever the geometry is favorable.
  • The instance-dependent bound makes explicit that the hardness of constraint violation scales like (1/c^\star)^d, so constraint sets that are 'pointy' in the direction of the algorithm's movement are inherently harder.

Reading between the lines

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

  • The instance-dependent bound $\mathcal{V}$ is defined through the algorithm's own action sequence, so an adversary who can steer the trajectory so that $c^\star_t \to 0$ will make the geometric bound vacuous; the paper's 'min' then defaults to the universal $O(\sqrt{T}\log T)$ bound, meaning the real improvement over prior work is confined to constraint sets whose geometry stays stable along the a
  • A natural extension is to replace Euclidean projection with Bregman-type projections relative to a self-concordant barrier of $S_t$; the same mean-width telescope would then bound CCV in terms of the geometry of the chosen barrier, potentially yielding constant violations for a wider class of sets such as ellipsoids.
  • The $d=2$ phase construction suggests a generic 'bounded angle covering' condition: if the projection hyperplanes $F_t$ can be covered by a constant number of cones of aperture $\pi/4$, the total movement stays $O(D)$; verifying this in higher dimensions is a concrete next step.
  • The OCS result (zero costs) is a clean testbed: because the projection curve is exactly self-expanded, the constant $d^{d/2}D$ is likely tight, and computing the worst-case projection curve for nested ellipses would show whether the constant can be improved.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper studies constrained online convex optimization (COCO) with time-varying convex constraints and proposes Algorithm 2, an online projected gradient method that first takes an OGD step and then projects onto the most recently revealed feasible set S_t. It claims O(sqrt(T)) static regret and a cumulative constraint violation bounded by min{V, O(sqrt(T) log T)}, where V is an instance-dependent quantity expressed through a geometric parameter c* defined by cones containing the convex hull of the current set and the projection of the current action. For spheres and axis-parallel cuboids, and for the OCS problem (no costs), the paper claims O(1) CCV; for d=2 under a monotonicity condition on projection hyperplanes, it claims O(GD) CCV. The paper also gives a lower bound showing that the prior algorithm of Sinha and Vaze (2024) has Omega(sqrt(T) log T) CCV even for a fixed one-dimensional instance.

Significance. If correct, the OCS and structured-set results would be a clear improvement over the universal O(sqrt(T) log T) CCV bound and would provide the first constant CCV for important special cases. The regret proof is standard, and the use of mean-width and Manselli-Pucci self-expanded curves is technically interesting and appropriate. The main caveat is that the general instance-dependent bound in Theorem 12 is not as advertised: c* is a function of the algorithm's own realized trajectory, so the bound does not depend only on the constraint sequence. This weakens the central general claim, although the independent special-case results remain valuable; in particular, the OCS bound and the d=2 monotone result appear to be sound contributions.

major comments (4)
  1. [Definition 10, Theorem 12, Theorem 13] The parameter c* is defined as min_t c*_t, where c*_t is computed from the realized points x_t and b_t = P_{S_t}(x_t). Consequently c*, and hence the bound in Theorem 12, is not a property of the constraint sets S_1,...,S_T alone: two runs of Algorithm 2 on the same constraint sequence but different cost functions can have very different c*. The abstract's statement that V depends only on inter-set distances, shape, dimension, and diameter is therefore not supported by the definition. This is a load-bearing issue because Theorem 13's min{V, O(sqrt(T) log T)} guarantee is only an improvement over prior work when V is a meaningful instance-dependent quantity of the constraint sequence.
  2. [Remark 2 and Theorem 12] No lower bound on c* is established along the realized trajectory, and Remark 2's assertion that a bound on ||x_t - b_t|| makes c* 'inherently' positive is not a proof. The quantity c*_t can be arbitrarily small even for very simple sets: for nested disks in d=2 with S_{t-1} the unit disk and S_t the disk of radius 1-delta, taking x_t on the boundary of S_{t-1} gives c*_t = Theta(sqrt(delta)). With delta = 1/T, the bound (1/c*)^d in Theorem 12 becomes Theta(T^{d/2}), which is worse than the universal O(sqrt(T) log T) bound; thus the min in Theorem 13 degenerates to the pre-existing guarantee. The authors should either prove a positive lower bound for the classes of sets for which they claim O(1) CCV, or clearly state that the general bound is a trajectory-dependent quantity that may be vacuous.
  3. [Lemma 21, Eq. (13)-(15)] The proof of Lemma 21, which is the only quantitative link between the mean-width decrease and the movement cost in Theorem 12, is under-derived at the key parametrization step. The measure change du = lambda^{d-2}(1-lambda^2)^{-1/2} dlambda du_perp in Eq. (15) is stated without derivation, and the restriction of the lambda-integral to [0,c*_t] relies on the geometry of the cone C_{w*_t}(c*_t) in a way that is not spelled out. In addition, the displayed Eq. (15) has a factor 1/V_d while the following line uses 1/(2V_d); this factor-of-two inconsistency must be resolved. Because Lemma 21 is the only bridge from W(S_t) decreases to ||x_t - b_t||, the proof of Theorem 12 is not complete until this is fixed.
  4. [Section 14 and Theorem 17] The proof of Theorem 17 relies on Lemma 23, which uses the Manselli-Pucci self-expanded curve result. The step where the reverse projection curve is shown to be self-expanded is plausible but is argued in a few sentences without a formal verification of the separating-hyperplane property for all t. Since this is the core of the OCS guarantee, a more detailed proof of Lemma 23 would strengthen the paper; the statement itself, however, appears correct.
minor comments (5)
  1. [Section 11 heading] The section is headed 'Proof of Theorem 11' but it proves Lemma 11; please correct the heading.
  2. [Definition 10] The notation c*_{w_t,t} = arg min_{c_t} C_{w_t}(c_t) is a type error: C_{w_t}(c_t) is a set, so the intended meaning is presumably the infimum c_t such that C_{w_t}(c_t) contains C_t; please rewrite the definition accordingly.
  3. [Eq. (15)] The text says 'Let du_perp be the (n-2)-dimensional Lebesgue measure of S_perp' although the ambient dimension is d; please use d-2 consistently.
  4. [Definition 18] The notation S_d^1 for the unit sphere is unconventional and is easy to confuse with a two-point set; please use S^{d-1} throughout.
  5. [Algorithm 1, step 8] In the definition of grad_t, the term Phi'(CCV(t)) should likely be Phi'(CCV(t-1)) because CCV(t) is updated after observing g_t; please check the intended timing.

Circularity Check

1 steps flagged · score 3.0 of 10

The general instance-dependent CCV bound is parameterized by c*, which is defined from Algorithm 2's own iterates x_t and b_t rather than from the constraint sets alone, making the advertised V partially self-referential; the special-case O(1) results are independent.

  1. self definitional [Definition 10, Remark 2, Eqs. (7)-(9), Theorem 12]
    "Let the convex hull of mt ∪ St be Ct ... Let c⋆t = minwt c⋆wt,t ... Moreover, let c⋆ = mint c⋆t ... Note that c⋆t is only a function of the distance ||xt − bt|| and the shape of St’s ... [Theorem 12] CCV[1:T ] = O(√d (1/c⋆)^d D)."

    The abstract claims that the CCV bound depends on the distance between consecutively revealed constraint sets, but the quantity c* that defines V is not a property of the constraint sets alone: in Definition 10, c*_t is built from m_t=(x_t+b_t)/2, where x_t is Algorithm 2's action and b_t=P_{S_t}(x_t). Since CCV ≤ GΣ||x_t−b_t|| via Eqs. (7)-(9), the right-hand side of Theorem 12 is a function of the very per-round distances whose sum is the left-hand side. Thus the general bound is an a-posteriori statement about the algorithm's trajectory, and for fixed constraint sets different cost sequences can make c* arbitrarily small, degenerating the guarantee to the universal O(√T log T) fallback.

full rationale

The special-case results are genuinely independent: Lemma 8 (spheres), Lemma 9 (axis-parallel cuboids), Theorem 17 (OCS), and the d=2 monotonic-angle result are derived from geometry and the classical Manselli-Pucci theorem, not from fitted parameters. The self-citation to Sinha and Vaze (2024) provides the universal O(√T log T) fallback in Algorithm 3; that prior result is a published, proof-based external benchmark and is not itself circular. The main circularity-adjacent issue is confined to the general Theorem 12/13 parameterization: c* is defined through Algorithm 2's own iterates, so the bound's 'instance dependence' is partly self-referential. The paper itself concedes in Section 6 that c* may be small or T-dependent, which confirms that the general bound can be vacuous. Weighing these, the central general claim is partially self-definitional, but the independent special-case contributions keep the paper from being wholly circular.

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

The central claim relies on standard convex geometry and the feasibility assumption. The only added geometric object is the cone Cwt(ct) and the quantity c⋆, which is not an invented physical entity but a trajectory-dependent shape parameter; its uniform positivity is not assured.

assumptions (4)
  • domain assumption Assumptions 1-3: X is closed convex with diameter D; all ft and gt are G-Lipschitz and convex; the intersection of constraint sets X⋆ is non-empty.
    These are the standard COCO feasibility and regularity assumptions from the prior literature, stated in Section 2.
  • standard math Mean width properties including W(K) ≤ diameter(K) and Eggleston's perimeter formula for d=2.
    Used in Lemma 11 and Lemma 19, cited from Eggleston (1966).
  • standard math Manselli-Pucci theorem on self-expanded curves: any self-expanded curve in a closed bounded convex set of diameter D in R^d has length O(d^{d/2} D).
    Used to prove Lemma 23, cited from Manselli and Pucci (1991).
  • domain assumption For each t, there exists a unit vector wt and constant ct > 0 such that the cone Cwt(ct) contains conv(mt ∪ St).
    Definition 10; the paper argues this follows from convexity of St and mt ∉ St, but the positivity and uniformity of c⋆ = min_t c⋆_t are not guaranteed a priori.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization." pith.science (2026). https://pith.science/paper/NKNT5KEW

@misc{pith2026250205019,
  author       = {Pith},
  title        = {Pith review of: $O(\sqrtT)$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NKNT5KEW}},
  note         = {Machine review of arXiv:2502.05019}
}
abstract

The constrained version of the standard online convex optimization (OCO) framework, called COCO is considered, where on every round, a convex cost function and a convex constraint function are revealed to the learner after it chooses the action for that round. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV). An algorithm is proposed that guarantees a static regret of $O(\sqrt{T})$ and a CCV of $\min\{\cV, O(\sqrt{T}\log T) \}$, where $\cV$ depends on the distance between the consecutively revealed constraint sets, the shape of constraint sets, dimension of action space and the diameter of the action space. For special cases of constraint sets, $\cV=O(1)$. Compared to the state of the art results, static regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T}\log T)$, that were universal, the new result on CCV is instance dependent, which is derived by exploiting the geometric properties of the constraint sets.

Figures

Figures reproduced from arXiv: 2502.05019 by the authors.

Figure 1
Figure 1. Figure representing the cone Cwt (ct) that contains the convex hull of mt and St with unit vector wt. Lemma 9 If all nested convex bodies S1 ⊇ S2 ⊇ · · · ⊇ ST are cuboids that are axis parallel to each other, then M ≤ d 3/2D. Proof is identical to Lemma 8. Note that similar results can be obtained when St’s are regular polygons that are axis parallel with each other. After exhausting the universal results for an upp… view at source ↗
Figure 2
Figure 2. Definition of Ft’s. 1 was shown to have CCV of O( √ T log T). Next, we show that Algorithm 2 has CCV of O(1) for the OCS, a remarkable improvement. Theorem 17 For solving OCS, Algorithm 2 has CCV[1:T] = O [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure representing the cone Cwt (ct) that contains the convex hull of mt and St with respect to the unit vector wt. u is a unit vector perpendicular to Hu an hyperplane that is a supporting hyperplane Ct at mt such that Ct ∩ Hu = {mt} and u T (xt − mt) ≥ 0 where u T ⊥w ⋆ t = 0, |u⊥| = 1 and since u ∈ U1 0 ≤ λ = q 1 − (u T w⋆ t ) = u T u⊥ ≤ c ⋆ t . Let S⊥ = {u⊥ : |u⊥| = 1, uT ⊥w ⋆ t = 0}. Let du⊥ be the (n − 2)-dime… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Figure corresponding to Example 26. Example 26 To better understand the definition of phases, consider [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]
Figure 5
Figure 5. Figure 5: Illustration of definition of zt(κ) for t ∈ T (κ). In this example, for phase 1, t ⋆ (1) = 3 since the distance of y3 from c is the farthest for phase 1 that consists of time slots T (1) = {2, 3}. Hence zt ⋆(1)+1(1) = x4. For t ∈ T (1)\t ⋆ (1) + 1, zt(1) are such zt+1(…
Figure 6
Figure 6. Figure 6: Definition of St’s where Ut are the extra regions that are added to St to get S ′ t . Proof: Recall that for a non-empty phase κ, T (κ) = T −(κ) ∪ T +(κ). We first argue about t ∈ T −(κ). By definition, zt ⋆(κ)+1 = xt ⋆(κ)+1 and xt ⋆(κ)+1 ∈ St ⋆(κ) . Thus, zt ⋆(κ)+1 ∈ …

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

  1. Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

    cs.LG 2026-07 accept novelty 6.0 of 10

    OGD+Projection for constrained online convex optimization has cumulative constraint violation Ω(T^{(d-1)/(2d)}) in dimension d, the first lower bound of this form.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

    A nearly-linear bound for chasing nested convex bodies

    CJ Argue, S \'e bastien Bubeck, Michael B Cohen, Anupam Gupta, and Yin Tat Lee. A nearly-linear bound for chasing nested convex bodies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 117--122. SIAM, 2019

    work page 2019

  2. [2]

    Nested convex bodies are chaseable

    Nikhil Bansal, Martin B \"o hm, Marek Eli \'a s , Grigorios Koumoutsos, and Seeun William Umboh. Nested convex bodies are chaseable. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253--1260. SIAM, 2018

    work page 2018

  3. [3]

    Chasing nested convex bodies nearly optimally

    S \'e bastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1496--1508. SIAM, 2020

    work page 2020

  4. [4]

    Online convex optimization with time-varying constraints and bandit feedback

    Xuanyu Cao and KJ Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on automatic control, 64 0 (7): 0 2665--2680, 2018

    work page 2018

  5. [5]

    Bandit convex optimization for scalable and dynamic iot management

    Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic iot management. IEEE Internet of Things Journal, 6 0 (1): 0 1276--1286, 2018

    work page 2018

  6. [6]

    Convexity, 1966

    Harold Gordon Eggleston. Convexity, 1966

    work page 1966

  7. [7]

    Online convex optimization with hard constraints: Towards the best of two worlds and beyond

    Hengquan Guo, Xin Liu, Honghao Wei, and Lei Ying. Online convex optimization with hard constraints: Towards the best of two worlds and beyond. Advances in Neural Information Processing Systems, 35: 0 36426--36439, 2022

    work page 2022

  8. [8]

    The convex optimization approach to regret minimization

    Elad Hazan. The convex optimization approach to regret minimization. Optimization for machine learning, page 287, 2012

    work page 2012

Show all 23 references
  1. [9]

    Adaptive algorithms for online convex optimization with long-term constraints

    Rodolphe Jenatton, Jim Huang, and C \'e dric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pages 402--411. PMLR, 2016

    2016

  2. [10]

    Cautious regret minimization: Online optimization with long-term budget constraints

    Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference on Machine Learning, pages 3944--3952. PMLR, 2019

    2019

  3. [11]

    Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints

    Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints. ACM SIGMETRICS Performance Evaluation Review, 49 0 (3): 0 4--5, 2022

    2022

  4. [12]

    Trading regret for efficiency: online convex optimization with long term constraints

    Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13 0 (1): 0 2503--2528, 2012

    2012

  5. [13]

    Maximum length of steepest descent curves for quasi-convex functions

    Paolo Manselli and Carlo Pucci. Maximum length of steepest descent curves for quasi-convex functions. Geometriae Dedicata, 38 0 (2): 0 211--227, 1991

    1991

  6. [14]

    Stochastic network optimization with application to communication and queueing systems

    Michael J Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3 0 (1): 0 1--211, 2010

    2010

  7. [15]

    Online convex optimization with time-varying constraints

    Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv:1702.04783, 2017

    2017 arXiv

  8. [16]

    Optimal algorithms for online convex optimization with adversarial constraints

    Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=TxffvJMnBy

    2024

  9. [17]

    Safety-aware algorithms for adversarial contextual bandit

    Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In International Conference on Machine Learning, pages 3280--3288. PMLR, 2017

    2017

  10. [18]

    On dynamic regret and constraint violations in constrained online convex optimization

    Rahul Vaze. On dynamic regret and constraint violations in constrained online convex optimization. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pages 9--16, 2022. doi:10.23919/WiOpt56218.2022.9930613

    2022

  11. [19]

    Regret and cumulative constraint violation analysis for online convex optimization with long term constraints

    Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pages 11998--12008. PMLR, 2021

    2021

  12. [20]

    Distributed online convex optimization with adversarial constraints: Reduced cumulative constraint violation bounds under slater's condition

    Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, and Karl H Johansson. Distributed online convex optimization with adversarial constraints: Reduced cumulative constraint violation bounds under slater's condition. arXiv preprint arXiv:2306.00149, 2023

    2023 arXiv

  13. [21]

    A low complexity algorithm with o ( T ) regret and o (1) constraint violations for online convex optimization with long term constraints

    Hao Yu and Michael J Neely. A low complexity algorithm with o ( T ) regret and o (1) constraint violations for online convex optimization with long term constraints. arXiv preprint arXiv:1604.02218, 2016

    2016 arXiv

  14. [22]

    Online convex optimization with stochastic constraints

    Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017

    2017

  15. [23]

    Online convex optimization for cumulative constraints

    Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018

    2018

Pith tools

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