Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Vaze, Rahul, Sinha, Abhishek
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint
by: Vaze, Rahul, et al.
Published: (2025)

Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost
by: Vaze, Rahul, et al.
Published: (2024)

Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
by: Shah, Harsh, et al.
Published: (2025)

Convex Optimization with Nested Evolving Feasible Sets
by: M., Karthick Krishna, et al.
Published: (2026)

Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2025)

Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
by: Balasundaram, Haricharan, et al.
Published: (2026)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
by: Oki, Taihei, et al.
Published: (2026)

Optimal Bounds for Adversarial Constrained Online Convex Optimization
by: Ferreira, Ricardo N., et al.
Published: (2025)

Online facility location with weights and congestion
by: Chakraborty, Arghya, et al.
Published: (2022)

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
by: Tarzanagh, Davoud Ataee, et al.
Published: (2022)

Chasing Convex Functions with Long-term Constraints
by: Lechowicz, Adam, et al.
Published: (2024)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
by: Xu, Haoran, et al.
Published: (2026)

Optimal Decentralized Smoothed Online Convex Optimization
by: Bhuyan, Neelkamal, et al.
Published: (2024)

Scheduling Multi-Server Jobs is Not Easy
by: Vaze, Rahul
Published: (2024)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
by: Ye, Zichun, et al.
Published: (2025)

Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2023)

Tight Bounds for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2024)

Towards Optimal Differentially Private Regret Bounds in Linear MDPs
by: Sahu, Sharan
Published: (2025)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
by: Ye, Zichun, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
by: Davoodi, Mansoor, et al.
Published: (2025)

Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
by: Laber, Eduardo S., et al.
Published: (2024)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
by: Nath, Ankur, et al.
Published: (2024)

Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy
by: Wu, Ruihan, et al.
Published: (2025)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
by: He, Yuchen, et al.
Published: (2024)

Fast and Efficient Matching Algorithm with Deadline Instances
by: Song, Zhao, et al.
Published: (2023)

An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration
by: Arunachaleswaran, Eshwar Ram, et al.
Published: (2024)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

Online Resource Allocation with Convex-set Machine-Learned Advice
by: Golrezaei, Negin, et al.
Published: (2023)

Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
by: Supantha, Subhamon, et al.
Published: (2025)

On Convex Optimization with Semi-Sensitive Features
by: Ghazi, Badih, et al.
Published: (2024)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach
by: Nguyen, Tuan-Anh, et al.
Published: (2024)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
by: Grigorescu, Elena, et al.
Published: (2024)