Timezone: »
In this paper, we consider the problem of Gaussian process (GP) optimization with an added robustness requirement: The returned point may be perturbed by an adversary, and we require the function value to remain as high as possible even after this perturbation. This problem is motivated by settings in which the underlying functions during optimization and implementation stages are different, or when one is interested in finding an entire region of good inputs rather than only a single point. We show that standard GP optimization algorithms do not exhibit the desired robustness properties, and provide a novel confidence-bound based algorithm StableOpt for this purpose. We rigorously establish the required number of samples for StableOpt to find a near-optimal point, and we complement this guarantee with an algorithm-independent lower bound. We experimentally demonstrate several potential applications of interest using real-world data sets, and we show that StableOpt consistently succeeds in finding a stable maximizer where several baseline methods fail.
Author Information
Ilija Bogunovic (EPFL Lausanne)
Jonathan Scarlett (National University of Singapore)
Stefanie Jegelka (MIT)
Stefanie Jegelka is an X-Consortium Career Development Assistant Professor in the Department of EECS at MIT. She is a member of the Computer Science and AI Lab (CSAIL), the Center for Statistics and an affiliate of the Institute for Data, Systems and Society and the Operations Research Center. Before joining MIT, she was a postdoctoral researcher at UC Berkeley, and obtained her PhD from ETH Zurich and the Max Planck Institute for Intelligent Systems. Stefanie has received a Sloan Research Fellowship, an NSF CAREER Award, a DARPA Young Faculty Award, the German Pattern Recognition Award and a Best Paper Award at the International Conference for Machine Learning (ICML). Her research interests span the theory and practice of algorithmic machine learning.
Volkan Cevher (EPFL)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Adversarially Robust Optimization with Gaussian Processes »
Wed Dec 5th through Thu the 6th Room Room 210
More from the Same Authors
-
2020 Poster: Testing Determinantal Point Processes »
Khashayar Gatmiry · Maryam Aliakbarpour · Stefanie Jegelka -
2020 Spotlight: Testing Determinantal Point Processes »
Khashayar Gatmiry · Maryam Aliakbarpour · Stefanie Jegelka -
2020 Poster: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method »
Yossi Arjevani · Joan Bruna · Bugra Can · Mert Gurbuzbalaban · Stefanie Jegelka · Hongzhou Lin -
2020 Poster: On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems »
Panayotis Mertikopoulos · Nadav Hallak · Ali Kavis · Volkan Cevher -
2020 Spotlight: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method »
Yossi Arjevani · Joan Bruna · Bugra Can · Mert Gurbuzbalaban · Stefanie Jegelka · Hongzhou Lin -
2020 Poster: Robust Reinforcement Learning via Adversarial training with Langevin Dynamics »
Parameswaran Kamalaruban · Yu-Ting Huang · Ya-Ping Hsieh · Paul Rolland · Cheng Shi · Volkan Cevher -
2020 Poster: The Generalized Lasso with Nonlinear Observations and Generative Priors »
Zhaoqiang Liu · Jonathan Scarlett -
2019 Poster: Distributionally Robust Optimization and Generalization in Kernel Methods »
Matthew Staib · Stefanie Jegelka -
2019 Poster: An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints »
Mehmet Fatih Sahin · Armin eftekhari · Ahmet Alacaoglu · Fabian Latorre · Volkan Cevher -
2019 Poster: Flexible Modeling of Diversity with Strongly Log-Concave Distributions »
Joshua Robinson · Suvrit Sra · Stefanie Jegelka -
2019 Poster: Stochastic Frank-Wolfe for Composite Convex Minimization »
Francesco Locatello · Alp Yurtsever · Olivier Fercoq · Volkan Cevher -
2019 Poster: Learning Erdos-Renyi Random Graphs via Edge Detecting Queries »
Zihan Li · Matthias Fresacher · Jonathan Scarlett -
2019 Poster: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Poster: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2019 Spotlight: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Spotlight: Fast and Provable ADMM for Learning with Generative Priors »
Fabian Latorre · Armin eftekhari · Volkan Cevher -
2018 Poster: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2018 Poster: Online Adaptive Methods, Universality and Acceleration »
Kfir Y. Levy · Alp Yurtsever · Volkan Cevher -
2018 Spotlight: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2018 Poster: Provable Variational Inference for Constrained Log-Submodular Models »
Josip Djolonga · Stefanie Jegelka · Andreas Krause -
2018 Poster: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Spotlight: Mirrored Langevin Dynamics »
Ya-Ping Hsieh · Ali Kavis · Paul Rolland · Volkan Cevher -
2018 Poster: Exponentiated Strongly Rayleigh Distributions »
Zelda Mariet · Suvrit Sra · Stefanie Jegelka -
2018 Tutorial: Negative Dependence, Stable Polynomials, and All That »
Suvrit Sra · Stefanie Jegelka -
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi -
2017 Poster: Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach »
Slobodan Mitrovic · Ilija Bogunovic · Ashkan Norouzi-Fard · Jakub M Tarnawski · Volkan Cevher -
2017 Poster: Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data »
Joel A Tropp · Alp Yurtsever · Madeleine Udell · Volkan Cevher -
2017 Poster: Parallel Streaming Wasserstein Barycenters »
Matthew Staib · Sebastian Claici · Justin M Solomon · Stefanie Jegelka -
2017 Poster: Phase Transitions in the Pooled Data Problem »
Jonathan Scarlett · Volkan Cevher -
2017 Poster: Polynomial time algorithms for dual volume sampling »
Chengtao Li · Stefanie Jegelka · Suvrit Sra -
2017 Poster: Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization »
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher -
2016 Workshop: Nonconvex Optimization for Machine Learning: Theory and Practice »
Hossein Mobahi · Anima Anandkumar · Percy Liang · Stefanie Jegelka · Anna Choromanska -
2016 Poster: Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling »
Chengtao Li · Suvrit Sra · Stefanie Jegelka -
2016 Poster: An Efficient Streaming Algorithm for the Submodular Cover Problem »
Ashkan Norouzi-Fard · Abbas Bazzi · Ilija Bogunovic · Marwa El Halabi · Ya-Ping Hsieh · Volkan Cevher -
2016 Poster: Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation »
Ilija Bogunovic · Jonathan Scarlett · Andreas Krause · Volkan Cevher -
2016 Poster: Cooperative Graphical Models »
Josip Djolonga · Stefanie Jegelka · Sebastian Tschiatschek · Andreas Krause -
2016 Poster: Stochastic Three-Composite Convex Minimization »
Alp Yurtsever · Bang Cong Vu · Volkan Cevher -
2015 Poster: Preconditioned Spectral Descent for Deep Learning »
David Carlson · Edo Collins · Ya-Ping Hsieh · Lawrence Carin · Volkan Cevher -
2015 Poster: A Universal Primal-Dual Convex Optimization Framework »
Alp Yurtsever · Quoc Tran Dinh · Volkan Cevher -
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 -
2014 Poster: Constrained convex minimization via model-based excessive gap »
Quoc Tran-Dinh · Volkan Cevher -
2014 Poster: Parallel Double Greedy Submodular Maximization »
Xinghao Pan · Stefanie Jegelka · Joseph Gonzalez · Joseph K Bradley · Michael Jordan -
2014 Poster: Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets »
Adarsh Prasad · Stefanie Jegelka · Dhruv Batra -
2014 Spotlight: Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets »
Adarsh Prasad · Stefanie Jegelka · Dhruv Batra -
2014 Poster: On the Convergence Rate of Decomposable Submodular Function Minimization »
Robert Nishihara · Stefanie Jegelka · Michael Jordan -
2014 Poster: Time--Data Tradeoffs by Aggressive Smoothing »
John J Bruer · Joel A Tropp · Volkan Cevher · Stephen Becker -
2014 Poster: Weakly-supervised Discovery of Visual Pattern Configurations »
Hyun Oh Song · Yong Jae Lee · Stefanie Jegelka · Trevor Darrell -
2013 Workshop: Discrete Optimization in Machine Learning: Connecting Theory and Practice »
Stefanie Jegelka · Andreas Krause · Pradeep Ravikumar · Kazuo Murota · Jeffrey A Bilmes · Yisong Yue · Michael Jordan -
2013 Poster: High-Dimensional Gaussian Process Bandits »
Josip Djolonga · Andreas Krause · Volkan Cevher -
2013 Poster: Optimistic Concurrency Control for Distributed Unsupervised Learning »
Xinghao Pan · Joseph Gonzalez · Stefanie Jegelka · Tamara Broderick · Michael Jordan -
2013 Poster: Reflection methods for user-friendly submodular optimization »
Stefanie Jegelka · Francis Bach · Suvrit Sra -
2013 Poster: Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions »
Rishabh K Iyer · Stefanie Jegelka · Jeffrey A Bilmes -
2012 Workshop: Discrete Optimization in Machine Learning (DISCML): Structure and Scalability »
Stefanie Jegelka · Andreas Krause · Jeffrey A Bilmes · Pradeep Ravikumar -
2012 Poster: Active Learning of Multi-Index Function Models »
Hemant Tyagi · Volkan Cevher -
2011 Poster: Fast approximate submodular minimization »
Stefanie Jegelka · Hui Lin · Jeffrey A Bilmes -
2010 Workshop: Discrete Optimization in Machine Learning: Structures, Algorithms and Applications »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes · Stefanie Jegelka -
2009 Workshop: Manifolds, sparsity, and structured models: When can low-dimensional geometry really help? »
Richard Baraniuk · Volkan Cevher · Mark A Davenport · Piotr Indyk · Bruno Olshausen · Michael B Wakin -
2009 Poster: Learning with Compressible Priors »
Volkan Cevher -
2008 Poster: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk -
2008 Spotlight: Sparse Signal Recovery Using Markov Random Fields »
Volkan Cevher · Marco F Duarte · Chinmay Hegde · Richard Baraniuk