Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints

Mehrdad Mahdavi, Rong Jin, Tianbao Yang

Type: Preprint

Publication Date: 2011-01-01

Citations: 167

DOI: https://doi.org/10.48550/arxiv.1111.6082

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints	2011	Mehrdad Mahdavi Rong Jin Tianbao Yang
+	Gradient-Variation Bound for Online Convex Optimization with Constraints	2020	Shuang Qiu Xiaohan Wei Mladen Kolar
+ PDF Chat	Gradient-Variation Bound for Online Convex Optimization with Constraints	2023	Shuang Qiu Xiaohan Wei Mladen Kolar
+	A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints	2016	Hao Yu Michael J. Neely
+	Adaptive Algorithms for Online Convex Optimization with Long-term Constraints	2015	Rodolphe Jenatton Jim Huang Cédric Archambeau
+	Online convex optimization in the bandit setting: gradient descent without a gradient	2004	Abraham D. Flaxman Adam Tauman Kalai H. Brendan McMahan
+	Online Convex Optimization with Long Term Constraints for Predictable Sequences	2022	Deepan Muthirayan Jianjun Yuan Pramod P. Khargonekar
+	A Unifying Framework for Online Optimization with Long-Term Constraints	2022	Matteo Castiglioni Andrea Celli Alberto Marchesi Giulia Romano Nicola Gatti
+ PDF Chat	An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints	2024	Jordan Lekeufack Michael I. Jordan
+	A Low Complexity Algorithm with O(√T) Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints	2020	Hao Yu Michael J. Neely
+	Online convex optimization for cumulative constraints	2018	Jianjun Yuan Andrew Lamperski
+	Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization	2019	Gautam Goel Yiheng Lin Haoyuan Sun Adam Wierman
+	Projection-Free Online Convex Optimization via Efficient Newton Iterations	2023	Khashayar Gatmiry Zakaria Mhammedi
+ PDF Chat	Online Convex Optimization With Long-Term Constraints for Predictable Sequences	2022	Deepan Muthirayan Jianjun Yuan Pramod P. Khargonekar
+	Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization	2019	Gautam Goel Yiheng Lin Haoyuan Sun Adam Wierman
+ PDF Chat	Online Convex Optimization with Memory and Limited Predictions	2024	Lintao Ye Z. Jane Wang Zhi‐Wei Liu 明政池 Xiaoling Wang Housheng Su
+	A Modern Introduction to Online Learning.	2019	Francesco Orabona
+	A Modern Introduction to Online Learning	2019	Francesco Orabona
+	Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning	2022	Zakaria Mhammedi
+ PDF Chat	Tight Bounds for Online Convex Optimization with Adversarial Constraints	2024	Abhishek Sinha Rahul Vaze

Works That Cite This (87)

Action	Title	Year	Authors
+	Decentralized multi-task stochastic optimization with compressed communications	2023	Navjot Singh Xuanyu Cao Suhas Diggavi Tamer Başar
+ PDF Chat	Adversarial Bandits with Knapsacks	2022	Nicole Immorlica Karthik Abinav Sankararaman Robert E. Schapire Aleksandrs Slivkins
+ PDF Chat	Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints	2021	Qingsong Liu Wenfei Wu Longbo Huang Zhixuan Fang
+	Conservative Multi-agent Online Kernel Learning in Heterogeneous Networks	2020	Hrusikesha Pradhan Amrit Singh Bedi Alec Koppel Ketan Rajawat
+	Approachability with constraints	2020	Gaëtan Fournier Eden Kuperwasser Orin Munk Eilon Solan Avishay Weinbaum
+	Bandit Convex Optimization for Scalable and Dynamic IoT Management	2018	Tianyi Chen Georgios B. Giannakis
+	Proximity Without Consensus in Online Multiagent Optimization	2017	Alec Koppel Brian M. Sadler Alejandro Ribeiro
+	Online convex optimization for cumulative constraints	2018	Jianjun Yuan Andrew Lamperski
+ PDF Chat	Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach	2022	Qinbo Bai Amrit Singh Bedi Mridul Agarwal Alec Koppel Vaneet Aggarwal
+	A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints	2016	Hao Yu Michael J. Neely

Works Cited by This (6)

Action	Title	Year	Authors
+	Convex Analysis and Optimization	2003	Dimitri P. Bertsekas Angelia Nedić Asuman Ozdaglar
+	A Stochastic View of Optimal Regret through Minimax Duality	2009	Jacob Abernethy Alekh Agarwal Peter L. Bartlett Alexander Rakhlin
+ PDF Chat	Prox-Method with Rate of Convergence <i>O</i>(1/<i>t</i>) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems	2004	Arkadi Nemirovski
+	Random Walk Approach to Regret Minimization	2010	Hariharan Narayanan Alexander Rakhlin
+	Online convex programming and generalized infinitesimal gradient ascent	2003	Martin Zinkevich
+	Convex Optimization	2004	Stephen Boyd Lieven Vandenberghe