pith. sign in

arxiv: 2605.21107 · v1 · pith:2GGJN3HNnew · submitted 2026-05-20 · 💻 cs.LG · stat.ML

Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction

Dhruv Sarkar , Abhishek Sinha This is my paper

Pith reviewed 2026-05-21 06:20 UTC · model grok-4.3

classification 💻 cs.LG stat.ML
keywords constrained online convex optimizationcumulative constraint violationself-contracted curvesregret boundsprojection algorithmsadversarial constraints
0
0 comments X

The pith

A projection-based algorithm for constrained online convex optimization achieves O(log T) cumulative constraint violation for strongly convex losses.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper presents a simple projection-based algorithm for Constrained Online Convex Optimization with adversarially chosen constraints. The algorithm achieves O(log T) regret and O(log T) cumulative constraint violation for strongly convex losses, an exponential improvement over prior O(sqrt(T log T)) CCV bounds. For convex losses it maintains the optimal O(sqrt(T)) regret while improving CCV to O(sqrt(T)). The central improvement comes from applying geometric properties of self-contracted curves to the sequence of projections generated by the algorithm.

Core claim

The paper claims that a projection-based algorithm simultaneously achieves O(log T) regret and O(log T) CCV for strongly convex losses and O(sqrt(T)) regret and O(sqrt(T)) CCV for convex losses in the setting of adversarially chosen constraints. These bounds are obtained by showing that the algorithm's projection sequence forms a self-contracted curve, which by a recent geometric result yields the improved control on cumulative constraint violation while preserving standard regret guarantees.

What carries the argument

Self-contracted curves, geometric objects where distance to any fixed point decreases monotonically along the curve, applied directly to the sequence of projections generated under adversarial constraints.

If this is right

  • Both regret and cumulative constraint violation remain logarithmic for strongly convex losses, enabling sustained operation over long horizons without accumulating violations.
  • The same algorithm recovers optimal sqrt(T) regret for convex losses while tightening the CCV bound from sqrt(T) log T to sqrt(T).
  • The method relies only on standard projections and does not require additional machinery beyond the geometric property of the projection sequence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same geometric argument on self-contracted projection sequences could apply to other online algorithms that repeatedly project onto changing feasible sets.
  • The improvement suggests that cumulative constraint violation can be controlled at the same rate as regret in many convex settings without trading one off against the other.
  • If self-contracted curves appear in other iterative methods, similar logarithmic bounds might be obtainable in related problems such as online linear programming with changing constraints.

Load-bearing premise

The sequence of projections produced by the algorithm forms a self-contracted curve even when constraints are chosen adversarially each round.

What would settle it

An adversarial sequence of loss and constraint functions where the algorithm's projection points fail to satisfy the self-contracted property and cumulative constraint violation grows faster than O(log T) for strongly convex losses.

read the original abstract

We consider Constrained Online Convex Optimization (COCO) with adversarially chosen constraints. At each round, the learner chooses an action before observing the loss and constraint function for that round. The goal is to achieve small static regret against the best point satisfying all constraints while also controlling cumulative constraint violation ($\mathsf{CCV}$). For strongly convex losses, state-of-the-art algorithms achieve $O(\log T)$ regret and $O(\sqrt{T \log T})$ $\mathsf{CCV}.$ The corresponding best-known bounds for convex losses is $O(\sqrt{T})$ regret and $O(\sqrt{T} \log T)$ $\mathsf{CCV}$. In this paper, we give a simple projection-based algorithm that simultaneously achieves $O(\log T)$ regret and $O(\log T)$ $\mathsf{CCV}$ for strongly-convex losses, yielding an exponential improvement in the $\mathsf{CCV}$. For the convex losses, our algorithm improves the $\mathsf{CCV}$ to $O(\sqrt{T})$ while maintaining the optimal $O(\sqrt{T})$ regret. The key to our improvement is a recent geometric result for self-contracted curves, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proposes a simple projection-based algorithm for Constrained Online Convex Optimization (COCO) under adversarial constraints. For strongly convex losses it claims O(log T) static regret and O(log T) cumulative constraint violation (CCV); for convex losses it claims the optimal O(sqrt(T)) regret together with an improved O(sqrt(T)) CCV. The improvement is obtained by invoking a recent geometric result on self-contracted curves and asserting that the sequence of projections generated by the algorithm satisfies the requisite contraction property.

Significance. If the claimed applicability of the self-contracted-curve lemma to the adversarially generated projection sequence is correct, the work would deliver an exponential improvement in CCV for the strongly convex case and a logarithmic-factor improvement for the convex case. Such bounds would be of clear interest to the online optimization community and the geometric lemma itself might find further use.

major comments (1)
  1. [Abstract / key-improvement paragraph] The central claim rests on the assertion that the discrete sequence x_{t+1} = proj_{K_t}(x_t) generated under adversarial convex sets K_t forms a self-contracted curve (i.e., satisfies the defining distance inequality used in the cited geometric lemma). The abstract and the paragraph describing the key improvement state this applicability without an explicit verification that the inequality holds for every possible sequence of convex constraint sets chosen by an adversary. A concrete check or counter-example analysis is required because failure of the contraction property would invalidate the telescoping argument that converts geometric decay into the stated O(log T) or O(sqrt(T)) CCV bounds.
minor comments (1)
  1. [Abstract] The abstract mentions “a recent geometric result” but does not give the precise statement or citation of the lemma that is being applied; adding the reference and a one-sentence restatement of the needed property would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for explicit verification of the self-contracted property. We address this concern directly below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / key-improvement paragraph] The central claim rests on the assertion that the discrete sequence x_{t+1} = proj_{K_t}(x_t) generated under adversarial convex sets K_t forms a self-contracted curve (i.e., satisfies the defining distance inequality used in the cited geometric lemma). The abstract and the paragraph describing the key improvement state this applicability without an explicit verification that the inequality holds for every possible sequence of convex constraint sets chosen by an adversary. A concrete check or counter-example analysis is required because failure of the contraction property would invalidate the telescoping argument that converts geometric decay into the stated O(log T) or O(sqrt(T)) CCV bounds.

    Authors: We agree that an explicit verification strengthens the presentation. In the revised manuscript we will add a self-contained lemma (placed immediately before the main regret/CCV analysis) that proves the required distance inequality holds for any sequence of convex sets K_t. The proof relies on the non-expansiveness of the Euclidean projection onto a convex set together with the triangle inequality applied to the intermediate points; it does not depend on the particular choice of the adversary. We will also update the abstract and the key-improvement paragraph to cite this lemma explicitly, thereby making the applicability of the geometric result fully rigorous and removing any ambiguity about the telescoping argument. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from external geometric property applied to algorithm outputs

full rationale

The paper derives O(log T) CCV for strongly convex losses and O(sqrt(T)) CCV for convex losses by combining a standard projection-based online algorithm with a cited geometric result on self-contracted curves. This result is described as recent and of independent interest rather than proven internally or via self-citation chain. No equations reduce the claimed bounds to fitted parameters, self-definitions, or renamings by construction. The derivation remains self-contained against external benchmarks once the geometric lemma is granted as an independent fact.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central improvement rests on an external geometric result about self-contracted curves whose precise statement and proof are not reproduced here.

axioms (1)
  • domain assumption Self-contracted curves possess geometric properties that bound the cumulative deviation of projected points under adversarial constraint sequences.
    Invoked as the key to the exponential CCV improvement in the abstract.

pith-pipeline@v0.9.0 · 5740 in / 1191 out tokens · 25160 ms · 2026-05-21T06:20:07.502702+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 300 canonical work pages · 11 internal anchors

  1. [1]

    Journal of Applied Mathematics , volume=

    Bounding regions to plane steepest descent curves of quasiconvex families , author=. Journal of Applied Mathematics , volume=. 2016 , publisher=

    work page 2016

  2. [2]

    2015 , publisher=

    Convex optimization algorithms , author=. 2015 , publisher=

    work page 2015

  3. [3]

    Journal de math

    Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions , author=. Journal de math. 2010 , publisher=

    work page 2010

  4. [4]

    Journal of the London Mathematical Society , volume=

    Self-contracted curves have finite length , author=. Journal of the London Mathematical Society , volume=. 2017 , publisher=

    work page 2017

  5. [5]

    Rahul Vaze and Abhishek Sinha , year=. O(. 2502.05019 , archivePrefix=

    work page arXiv

  6. [6]

    Breaking the

    Balasundaram, Haricharan and Mahendran, Karthick Krishna and Vaze, Rahul , journal=. Breaking the

    work page

  7. [7]

    2026 , eprint=

    Convex Optimization with Nested Evolving Feasible Sets , author=. 2026 , eprint=

    work page 2026

  8. [8]

    Foundations and Trends in Optimization , volume=

    Introduction to online convex optimization , author=. Foundations and Trends in Optimization , volume=. 2016 , publisher=

    work page 2016

  9. [9]

    Geometriae Dedicata , volume=

    Maximum length of steepest descent curves for quasi-convex functions , author=. Geometriae Dedicata , volume=. 1991 , publisher=

    work page 1991

  10. [10]

    Advances in Neural Information Processing Systems , volume=

    A unifying framework for online optimization with long-term constraints , author=. Advances in Neural Information Processing Systems , volume=

    work page

  11. [11]

    Convex Optimization with Nested Evolving Feasible Sets

    Convex Optimization with Nested Evolving Feasible Sets , author=. arXiv preprint arXiv:2605.07386 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    2025 , eprint=

    Optimal Bounds for Adversarial Constrained Online Convex Optimization , author=. 2025 , eprint=

    work page 2025

  13. [13]

    arXiv preprint arXiv:2312.16730 , year=

    Foundations of reinforcement learning and interactive decision making , author=. arXiv preprint arXiv:2312.16730 , year=

    work page arXiv

  14. [14]

    Advances in neural information processing systems , volume=

    The epoch-greedy algorithm for contextual multi-armed bandits , author=. Advances in neural information processing systems , volume=. 2007 , publisher=

    work page 2007

  15. [15]

    Learning Safety Constraints for Large Language Models , author=

    work page

  16. [16]

    Forty-second International Conference on Machine Learning , year=

    Learning Safety Constraints for Large Language Models , author=. Forty-second International Conference on Machine Learning , year=

    work page

  17. [17]

    Certifying LLM Safety against Adversarial Prompting , author=

    work page

  18. [18]

    IEEE Access , year=

    Constraints driven safe reinforcement learning for autonomous driving decision-making , author=. IEEE Access , year=

    work page

  19. [19]

    Optical compressive imaging , pages=

    Phase retrieval: An overview of recent developments , author=. Optical compressive imaging , pages=. 2016 , publisher=

    work page 2016

  20. [20]

    Mathematics of Operations Research , volume=

    The online saddle point problem and online convex optimization with knapsacks , author=. Mathematics of Operations Research , volume=. 2025 , publisher=

    work page 2025

  21. [21]

    Foundations and Trends

    Learning with submodular functions: A convex optimization perspective , author=. Foundations and Trends. 2013 , publisher=

    work page 2013

  22. [22]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Online dr-submodular maximization: Minimizing regret and constraint violation , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  23. [23]

    2003 , publisher=

    Convex analysis and optimization , author=. 2003 , publisher=

    work page 2003

  24. [24]

    Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Fast algorithms for online stochastic convex programming , author=. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    work page 2014

  25. [25]

    Foundations and Trends

    Online matching and ad allocation , author=. Foundations and Trends. 2013 , publisher=

    work page 2013

  26. [26]

    Operations research , volume=

    Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms , author=. Operations research , volume=. 2009 , publisher=

    work page 2009

  27. [27]

    International Conference on Machine Learning , pages=

    Online learning with knapsacks: the best of both worlds , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    work page 2022

  28. [28]

    Dynamic Ad Allocation: Bandits with Budgets

    Dynamic ad allocation: Bandits with budgets , author=. arXiv preprint arXiv:1306.0155 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  29. [29]

    2002 , publisher=

    Computers and intractability , author=. 2002 , publisher=

    work page 2002

  30. [30]

    International Conference on Artificial Intelligence and Statistics , pages=

    Online continuous submodular maximization , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2018 , organization=

    work page 2018

  31. [31]

    International Conference on Machine Learning , pages=

    Stochastic continuous submodular maximization: Boosting via non-oblivious function , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    work page 2022

  32. [32]

    Dynamic Regret Bounds for Constrained Online Nonconvex Optimization Based on Polyak–Lojasiewicz Regions , year=

    Mulvaney-Kemp, Julie and Park, SangWoo and Jin, Ming and Lavaei, Javad , journal=. Dynamic Regret Bounds for Constrained Online Nonconvex Optimization Based on Polyak–Lojasiewicz Regions , year=

    work page

  33. [33]

    International Conference on Artificial Intelligence and Statistics , pages=

    Online learning with non-convex losses and non-stationary regret , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2018 , organization=

    work page 2018

  34. [34]

    Conference on Learning Theory , pages=

    Learning in non-convex games with an optimization oracle , author=. Conference on Learning Theory , pages=. 2019 , organization=

    work page 2019

  35. [35]

    IEEE Trans

    Phase retrieval via reweighted amplitude flow , author=. IEEE Trans. Signal Process. , volume=. 2018 , publisher=

    work page 2018

  36. [36]

    On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization , year=

    Vaze, Rahul , booktitle=. On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization , year=

    work page

  37. [37]

    Advances in Neural Information Processing Systems , volume=

    Adaptive hedge , author=. Advances in Neural Information Processing Systems , volume=

    work page

  38. [38]

    A low complexity algorithm with

    Yu, Hao and Neely, Michael J , journal=. A low complexity algorithm with

    work page

  39. [39]

    arXiv preprint arXiv:2501.16046 , year=

    Revisiting Projection-Free Online Learning with Time-Varying Constraints , author=. arXiv preprint arXiv:2501.16046 , year=

    work page arXiv

  40. [40]

    2023 , eprint=

    Playing in the Dark: No-regret Learning with Adversarial Constraints , author=. 2023 , eprint=

    work page 2023

  41. [41]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

    Optimal Algorithms for Online Convex Optimization with Adversarial Constraints , author=. The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

    work page

  42. [42]

    IEEE Transactions on automatic control , volume=

    Online convex optimization with time-varying constraints and bandit feedback , author=. IEEE Transactions on automatic control , volume=. 2018 , publisher=

    work page 2018

  43. [43]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=

    Minimizing queue length regret under adversarial network models , author=. Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=. 2018 , publisher=

    work page 2018

  44. [44]

    IEEE Internet of Things Journal , volume=

    Bandit convex optimization for scalable and dynamic IoT management , author=. IEEE Internet of Things Journal , volume=. 2018 , publisher=

    work page 2018

  45. [45]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Nested convex bodies are chaseable , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    work page 2018

  46. [46]

    Proceedings of the Symposium on the Mathematical Theory of Automata , volume=

    On convergence proofs on perceptrons , author=. Proceedings of the Symposium on the Mathematical Theory of Automata , volume=. 1962 , organization=

    work page 1962

  47. [47]

    Journal of optimization theory and applications , volume=

    Subgradient methods for saddle-point problems , author=. Journal of optimization theory and applications , volume=. 2009 , publisher=

    work page 2009

  48. [48]

    IEEE Transactions on Automatic Control , year=

    Regret and cumulative constraint violation analysis for distributed online constrained convex optimization , author=. IEEE Transactions on Automatic Control , year=

    work page

  49. [49]

    Nature , volume=

    Dense reinforcement learning for safety validation of autonomous vehicles , author=. Nature , volume=. 2023 , publisher=

    work page 2023

  50. [50]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    A nearly-linear bound for chasing nested convex bodies , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    work page 2019

  51. [51]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Chasing nested convex bodies nearly optimally , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    work page 2020

  52. [52]

    IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=

    Learning to Cache With No Regrets , author=. IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=. 2019 , organization=

    work page 2019

  53. [53]

    2012 , publisher=

    The Borel-Cantelli Lemma , author=. 2012 , publisher=

    work page 2012

  54. [54]

    Kingma and Jimmy Ba , editor =

    Diederik P. Kingma and Jimmy Ba , editor =. Adam:. 3rd International Conference on Learning Representations,. 2015 , url =

    work page 2015

  55. [55]

    2008 , publisher=

    Control techniques for complex networks , author=. 2008 , publisher=

    work page 2008

  56. [56]

    , author=

    Adaptive subgradient methods for online learning and stochastic optimization. , author=. Journal of machine learning research , volume=

    work page

  57. [57]

    International Conference on Machine Learning , pages=

    Regret and cumulative constraint violation analysis for online convex optimization with long term constraints , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    work page 2021

  58. [58]

    An Overview of Multi-Task Learning in Deep Neural Networks

    An overview of multi-task learning in deep neural networks , author=. arXiv preprint arXiv:1706.05098 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  59. [59]

    2015 , publisher=

    Random processes for engineers , author=. 2015 , publisher=

    work page 2015

  60. [60]

    Advances in Neural Information Processing Systems , volume=

    Online convex optimization with hard constraints: Towards the best of two worlds and beyond , author=. Advances in Neural Information Processing Systems , volume=

    work page

  61. [61]

    Advances in Neural Information Processing Systems , volume=

    Adaptive smoothed online multi-task learning , author=. Advances in Neural Information Processing Systems , volume=

    work page

  62. [62]

    International Conference on Computational Learning Theory , pages=

    Online multitask learning , author=. International Conference on Computational Learning Theory , pages=. 2006 , organization=

    work page 2006

  63. [63]

    Rockafellar, R. Tyrrel. Convex Analysis

    work page

  64. [64]

    Electronic colloquium on computational complexity (ECCC) , volume=

    Adaptive algorithms for online decision problems , author=. Electronic colloquium on computational complexity (ECCC) , volume=

    work page

  65. [65]

    Artificial Intelligence and Statistics , pages=

    Improved strongly adaptive online learning using coin betting , author=. Artificial Intelligence and Statistics , pages=. 2017 , organization=

    work page 2017

  66. [66]

    Theoretical Computer Science , volume=

    Scale-free online learning , author=. Theoretical Computer Science , volume=. 2018 , publisher=

    work page 2018

  67. [67]

    International Conference on Machine Learning , pages=

    A simple yet universal strategy for online convex optimization , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    work page 2022

  68. [68]

    Machine learning , volume=

    Regret bounded by gradual variation for online convex optimization , author=. Machine learning , volume=. 2014 , publisher=

    work page 2014

  69. [69]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  70. [70]

    International Conference on Machine Learning , pages=

    Adaptive regret of convex and smooth functions , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    work page 2019

  71. [71]

    Proceedings of the 36th International Conference on Machine Learning , pages =

    Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints , author =. Proceedings of the 36th International Conference on Machine Learning , pages =. 2019 , editor =

    work page 2019

  72. [72]

    2003 , publisher=

    Applied probability and queues , author=. 2003 , publisher=

    work page 2003

  73. [73]

    The Journal of Machine Learning Research , volume=

    Trading regret for efficiency: online convex optimization with long term constraints , author=. The Journal of Machine Learning Research , volume=. 2012 , publisher=

    work page 2012

  74. [74]

    Proceedings of the 34th International Conference on Machine Learning , pages =

    Safety-Aware Algorithms for Adversarial Contextual Bandit , author =. Proceedings of the 34th International Conference on Machine Learning , pages =. 2017 , editor =

    work page 2017

  75. [75]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2022 , publisher=

    work page 2022

  76. [76]

    arXiv preprint arXiv:2306.00149 , year=

    Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition , author=. arXiv preprint arXiv:2306.00149 , year=

    work page arXiv

  77. [77]

    A Low Complexity Algorithm with O (

    Yu, Hao and Neely, Michael J , journal=. A Low Complexity Algorithm with O (

    work page

  78. [78]

    29th IEEE Conference on Decision and Control , pages=

    Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks , author=. 29th IEEE Conference on Decision and Control , pages=. 1990 , organization=

    work page 1990

  79. [79]

    IEEE Transactions on Communications , volume=

    Achieving 100\ author=. IEEE Transactions on Communications , volume=. 1999 , publisher=

    work page 1999

  80. [80]

    1992 , publisher=

    Integral inequalities and applications , author=. 1992 , publisher=

    work page 1992

Showing first 80 references.