Online convex optimization in the bandit setting: gradient descent without a gradient

Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan

Type: Preprint

Publication Date: 2004-01-01

Citations: 12

DOI: https://doi.org/10.48550/arxiv.cs/0408007

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Minimizing Regret in Bandit Online Optimization in Unconstrained and Constrained Action Spaces.	2018	Tatiana Tatarenko Maryam Kamgarpour
+	(Bandit) Convex Optimization with Biased Noisy Gradient Oracles	2016	Xiaowei Hu L. A. Prashanth András György Csaba Szepesvári
+ PDF Chat	Comparator-adaptive Convex Bandits	2020	Dirk van der Hoeven Ashok Cutkosky Haipeng Luo
+	Comparator-adaptive Convex Bandits	2020	Dirk van der Hoeven Ashok Cutkosky Haipeng Luo
+	Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces	2018	Tatiana Tatarenko Maryam Kamgarpour
+	Bandit) Convex Optimization with Biased Noisy Gradient Oracles	2016	Xiaowei Hu L. A. Prashanth András György Csaba Szepesvári
+	A Modern Introduction to Online Learning	2019	Francesco Orabona
+	A Modern Introduction to Online Learning.	2019	Francesco Orabona
+	Bandit Optimization with Upper-Confidence Frank-Wolfe.	2017	Quentin Berthet Vianney Perchet
+	Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization	2021	Aadirupa Saha Nagarajan Natarajan Praneeth Netrapalli Prateek Jain
+	Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints	2011	Mehrdad Mahdavi Rong Jin Tianbao Yang
+	Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints	2011	Mehrdad Mahdavi Rong Jin Tianbao Yang
+	On the Complexity of Bandit Linear Optimization	2014	Ohad Shamir
+	An optimal algorithm for bandit convex optimization	2016	Elad Hazan Yuanzhi Li
+	An optimal algorithm for bandit convex optimization	2016	Elad Hazan Yuanzhi Li
+	Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization	2021	Aadirupa Saha Nagarajan Natarajan Praneeth Netrapalli Prateek Jain
+	Bandit Convex Optimisation Revisited: FTRL Achieves $\tilde{O}(t^{1/2})$ Regret	2023	D. R. Young Douglas J. Leith George Iosifidis
+ PDF Chat	Second Order Methods for Bandit Optimization and Control	2024	Arun Sai Suggala Y. Jennifer Sun Praneeth Netrapalli Elad Hazan
+	Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe	2017	Quentin Berthet Vianney Perchet
+	Regret in Online Combinatorial Optimization	2012	Jean-Yves Audibert Sébastien Bubeck Gábor Lugosi

Works That Cite This (7)

Action	Title	Year	Authors
+	Optimality of the Subgradient Algorithm in the Stochastic Setting	2019	Daron Anderson Douglas J. Leith
+	Distributionally Constrained Black-Box Stochastic Gradient Estimation and Optimization	2021	Henry Lam Junhui Zhang
+	Non-Stochastic Control with Bandit Feedback	2020	Paula Gradu John Hallman Elad Hazan
+ PDF Chat	Small Errors in Random Zeroth-Order Optimization Are Imaginary	2024	Wouter Jongeneel Man–Chung Yue Daniel Kühn
+	Projection-Free Bandit Optimization with Privacy Guarantees	2020	Alina Ene Huy L. Nguyễn Adrian Vladu
+	Utility-based Dueling Bandits as a Partial Monitoring Game	2015	Pratik Gajane Tanguy Urvoy
+ PDF Chat	Convergence analysis for a nonlocal gradient descent method via directional Gaussian smoothing	2025	Hoang Tran Qiang Du Guannan Zhang

Works Cited by This (6)

Action	Title	Year	Authors
+	Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space	2006	Vitali Milman Alain Pajor
+	Solving convex programs by random walks	2002	Dimitris Bertsimas Santosh Vempala
+	Random walks and anO*(n5) volume algorithm for convex bodies	1997	Ravi Kannan L�szl� Lov�sz Mikl�s Simonovits
+ PDF Chat	Log-Sobolev inequalities and sampling from log-concave distributions	1999	Alan Frieze Ravi Kannan
+	Simulated annealing in convex bodies and an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msup><mml:mrow><mml:mi>O</mml:mi></mml:mrow><mml:mrow><mml:mo>*</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> volume algorithm	2005	László Lovász Santosh Vempala
+	Online convex programming and generalized infinitesimal gradient ascent	2003	Martin Zinkevich