Timezone: »
Spotlight
Information-theoretic lower bounds for convex optimization with erroneous oracles
Yaron Singer · Jan Vondrak
We consider the problem of optimizing convex and concave functions with access to an erroneous zeroth-order oracle. In particular, for a given function $x \to f(x)$ we consider optimization when one is given access to absolute error oracles that return values in [f(x) - \epsilon,f(x)+\epsilon] or relative error oracles that return value in [(1+\epsilon)f(x), (1 +\epsilon)f (x)], for some \epsilon larger than 0. We show stark information theoretic impossibility results for minimizing convex functions and maximizing concave functions over polytopes in this model.
Author Information
Yaron Singer (Harvard University)
Jan Vondrak (IBM Research)
More from the Same Authors
-
2020 Poster: The Adaptive Complexity of Maximizing a Gross Substitutes Valuation »
Ron Kupfer · Sharon Qian · Eric Balkanski · Yaron Singer -
2020 Poster: An Optimal Elimination Algorithm for Learning a Best Arm »
Avinatan Hassidim · Ron Kupfer · Yaron Singer -
2020 Spotlight: An Optimal Elimination Algorithm for Learning a Best Arm »
Avinatan Hassidim · Ron Kupfer · Yaron Singer -
2020 Spotlight: The Adaptive Complexity of Maximizing a Gross Substitutes Valuation »
Ron Kupfer · Sharon Qian · Eric Balkanski · Yaron Singer -
2020 Poster: Investigating Gender Bias in Language Models Using Causal Mediation Analysis »
Jesse Vig · Sebastian Gehrmann · Yonatan Belinkov · Sharon Qian · Daniel Nevo · Yaron Singer · Stuart Shieber -
2020 Spotlight: Investigating Gender Bias in Language Models Using Causal Mediation Analysis »
Jesse Vig · Sebastian Gehrmann · Yonatan Belinkov · Sharon Qian · Daniel Nevo · Yaron Singer · Stuart Shieber -
2019 Poster: Fast Parallel Algorithms for Statistical Subset Selection Problems »
Sharon Qian · Yaron Singer -
2018 Poster: Optimization for Approximate Submodularity »
Yaron Singer · Avinatan Hassidim -
2018 Poster: Non-monotone Submodular Maximization in Exponentially Fewer Iterations »
Eric Balkanski · Adam Breuer · Yaron Singer -
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi -
2017 Poster: Minimizing a Submodular Function from Samples »
Eric Balkanski · Yaron Singer -
2017 Poster: Robust Optimization for Non-Convex Objectives »
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis -
2017 Oral: Robust Optimization for Non-Convex Objectives »
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis -
2017 Poster: The Importance of Communities for Learning to Influence »
Eric Balkanski · Nicole Immorlica · Yaron Singer -
2016 Poster: Maximization of Approximately Submodular Functions »
Thibaut Horel · Yaron Singer -
2016 Poster: The Power of Optimization from Samples »
Eric Balkanski · Aviad Rubinstein · Yaron Singer -
2015 Poster: Learnability of Influence in Networks »
Harikrishna Narasimhan · David Parkes · Yaron Singer -
2015 Poster: Information-theoretic lower bounds for convex optimization with erroneous oracles »
Yaron Singer · Jan Vondrak -
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher