Timezone: »
Poster
Bandit Convex Optimization: Towards Tight Bounds
Elad Hazan · Kfir Y. Levy
Bandit Convex Optimization (BCO) is a fundamental framework for decision making under uncertainty, which generalizes many problems from the realm of online and statistical learning. While the special case of linear cost functions is well understood, a gap on the attainable regret for BCO with nonlinear losses remains an important open question. In this paper we take a step towards understanding the best attainable regret bounds for BCO: we give an efficient and near-optimal regret algorithm for BCO with strongly-convex and smooth loss functions. In contrast to previous works on BCO that use time invariant exploration schemes, our method employs an exploration scheme that shrinks with time.
Author Information
Elad Hazan (Technion)
Kfir Y. Levy (Technion)
More from the Same Authors
-
2021 Poster: Faster Neural Network Training with Approximate Tensor Operations »
Menachem Adelman · Kfir Levy · Ido Hakimi · Mark Silberstein -
2021 Poster: STORM+: Fully Adaptive SGD with Recursive Momentum for Nonconvex Optimization »
Kfir Levy · Ali Kavis · Volkan Cevher -
2020 Poster: Adaptive Sampling for Stochastic Risk-Averse Learning »
Sebastian Curi · Kfir Y. Levy · Stefanie Jegelka · Andreas Krause -
2019 Poster: A Domain Agnostic Measure for Monitoring and Evaluating GANs »
Paulina Grnarova · Kfir Y. Levy · Aurelien Lucchi · Nathanael Perraudin · Ian Goodfellow · Thomas Hofmann · Andreas Krause -
2019 Poster: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Spotlight: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2018 Poster: Online Adaptive Methods, Universality and Acceleration »
Kfir Y. Levy · Alp Yurtsever · Volkan Cevher -
2017 Poster: Online to Offline Conversions, Universality and Adaptive Minibatch Sizes »
Kfir Levy -
2017 Poster: Non-monotone Continuous DR-submodular Maximization: Structure and Algorithms »
Yatao Bian · Kfir Levy · Andreas Krause · Joachim M Buhmann -
2016 Poster: k*-Nearest Neighbors: From Global to Local »
Oren Anava · Kfir Y. Levy -
2015 Poster: Fast Rates for Exp-concave Empirical Risk Minimization »
Tomer Koren · Kfir Y. Levy -
2015 Poster: Beyond Convexity: Stochastic Quasi-Convex Optimization »
Elad Hazan · Kfir Y. Levy · Shai Shalev-Shwartz -
2014 Poster: The Blinded Bandit: Learning with Adaptive Feedback »
Ofer Dekel · Elad Hazan · Tomer Koren -
2012 Poster: A Polylog Pivot Steps Simplex Algorithm for Classification »
Elad Hazan · Zohar S Karnin -
2011 Poster: Approximating Semidefinite Programs in Sublinear Time »
Dan Garber · Elad Hazan -
2011 Poster: Beating SGD: Learning SVMs in Sublinear Time »
Elad Hazan · Tomer Koren · Nati Srebro -
2011 Poster: Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction »
Elad Hazan · Satyen Kale