Timezone: »
Oral
Robust Optimization for Non-Convex Objectives
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis
We consider robust optimization problems, where the goal is to optimize in the worst case over a class of objective functions. We develop a reduction from robust improper optimization to Bayesian optimization: given an oracle that returns $\alpha$-approximate solutions for distributions over objectives, we compute a distribution over solutions that is $\alpha$-approximate in the worst case. We show that derandomizing this solution is NP-hard in general, but can be done for a broad class of statistical learning tasks. We apply our results to robust neural network training and submodular optimization. We evaluate our approach experimentally on a character classification task subject to adversarial distortion, and robust influence maximization on large networks.
Author Information
Robert S Chen (Harvard University)
Brendan Lucier (Microsoft Research)
Yaron Singer (Harvard University)
Vasilis Syrgkanis (Microsoft Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Robust Optimization for Non-Convex Objectives »
Wed. Dec 6th 02:30 -- 06:30 AM Room Pacific Ballroom #158
More from the Same Authors
-
2021 : Double/Debiased Machine Learning for Dynamic Treatment Effects via $g$-Estimation »
Greg Lewis · Vasilis Syrgkanis -
2021 : Estimating the Long-Term Effects of Novel Treatments »
Keith Battocchi · Maggie Hei · Greg Lewis · Miruna Oprescu · Vasilis Syrgkanis -
2021 Poster: Double/Debiased Machine Learning for Dynamic Treatment Effects »
Greg Lewis · Vasilis Syrgkanis -
2021 Poster: Asymptotics of the Bootstrap via Stability with Applications to Inference with Model Selection »
Morgane Austern · Vasilis Syrgkanis -
2021 Poster: Estimating the Long-Term Effects of Novel Treatments »
Keith Battocchi · Eleanor Dillon · Maggie Hei · Greg Lewis · Miruna Oprescu · Vasilis Syrgkanis -
2020 Poster: Minimax Estimation of Conditional Moment Models »
Nishanth Dikkala · Greg Lewis · Lester Mackey · Vasilis Syrgkanis -
2020 Poster: ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool »
Gellert Weisz · András György · Wei-I Lin · Devon Graham · Kevin Leyton-Brown · Csaba Szepesvari · Brendan Lucier -
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 : Coffee break, posters, and 1-on-1 discussions »
Julius von Kügelgen · David Rohde · Candice Schumann · Grace Charles · Victor Veitch · Vira Semenova · Mert Demirer · Vasilis Syrgkanis · Suraj Nair · Aahlad Puli · Masatoshi Uehara · Aditya Gopalan · Yi Ding · Ignavier Ng · Khashayar Khosravi · Eli Sherman · Shuxi Zeng · Aleksander Wieczorek · Hao Liu · Kyra Gan · Jason Hartford · Miruna Oprescu · Alexander D'Amour · Jörn Boehnke · Yuta Saito · Théophile Griveau-Billion · Chirag Modi · Shyngys Karimov · Jeroen Berrevoets · Logan Graham · Imke Mayer · Dhanya Sridhar · Issa Dahabreh · Alan Mishler · Duncan Wadsworth · Khizar Qureshi · Rahul Ladhania · Gota Morishita · Paul Welle -
2019 : Lunch + Poster Session »
Frederik Gerzer · Bill Yang Cai · Pieter-Jan Hoedt · Kelly Kochanski · Soo Kyung Kim · Yunsung Lee · Sunghyun Park · Sharon Zhou · Martin Gauch · Jonathan Wilson · Joyjit Chatterjee · Shamindra Shrotriya · Dimitri Papadimitriou · Christian Schön · Valentina Zantedeschi · Gabriella Baasch · Willem Waegeman · Gautier Cosne · Dara Farrell · Brendan Lucier · Letif Mones · Caleb Robinson · Tafara Chitsiga · Victor Kristof · Hari Prasanna Das · Yimeng Min · Alexandra Puchko · Alexandra Luccioni · Kyle Story · Jason Hickey · Yue Hu · Björn Lütjens · Zhecheng Wang · Renzhi Jing · Genevieve Flaspohler · Jingfan Wang · Saumya Sinha · Qinghu Tang · Armi Tiihonen · Ruben Glatt · Muge Komurcu · Jan Drgona · Juan Gomez-Romero · Ashish Kapoor · Dylan J Fitzpatrick · Alireza Rezvanifar · Adrian Albert · Olya (Olga) Irzak · Kara Lamb · Ankur Mahesh · Kiwan Maeng · Frederik Kratzert · Sorelle Friedler · Niccolo Dalmasso · Alex Robson · Lindiwe Malobola · Lucas Maystre · Yu-wen Lin · Surya Karthik Mukkavili · Brian Hutchinson · Alexandre Lacoste · Yanbing Wang · Zhengcheng Wang · Yinda Zhang · Victoria Preston · Jacob Pettit · Draguna Vrabie · Miguel Molina-Solana · Tonio Buonassisi · Andrew Annex · Tunai P Marques · Catalin Voss · Johannes Rausch · Max Evans -
2019 Poster: Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration »
Robert Kleinberg · Kevin Leyton-Brown · Brendan Lucier · Devon Graham -
2019 Poster: Semi-Parametric Efficient Policy Learning with Continuous Actions »
Victor Chernozhukov · Mert Demirer · Greg Lewis · Vasilis Syrgkanis -
2019 Poster: Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing »
Jonas Mueller · Vasilis Syrgkanis · Matt Taddy -
2019 Poster: Fast Parallel Algorithms for Statistical Subset Selection Problems »
Sharon Qian · Yaron Singer -
2019 Poster: Machine Learning Estimation of Heterogeneous Treatment Effects with Instruments »
Vasilis Syrgkanis · Victor Lei · Miruna Oprescu · Maggie Hei · Keith Battocchi · Greg Lewis -
2019 Spotlight: Machine Learning Estimation of Heterogeneous Treatment Effects with Instruments »
Vasilis Syrgkanis · Victor Lei · Miruna Oprescu · Maggie Hei · Keith Battocchi · Greg Lewis -
2018 Workshop: Smooth Games Optimization and Machine Learning »
Simon Lacoste-Julien · Ioannis Mitliagkas · Gauthier Gidel · Vasilis Syrgkanis · Eva Tardos · Leon Bottou · Sebastian Nowozin -
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: Learning in the Presence of Strategic Behavior »
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan -
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: Welfare Guarantees from Data »
Darrell Hoy · Denis Nekipelov · Vasilis Syrgkanis -
2017 Poster: A Sample Complexity Measure with Applications to Learning Optimal Auctions »
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 -
2016 Poster: Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits »
Vasilis Syrgkanis · Haipeng Luo · Akshay Krishnamurthy · Robert Schapire -
2015 Poster: No-Regret Learning in Bayesian Games »
Jason Hartline · Vasilis Syrgkanis · Eva Tardos -
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 -
2015 Spotlight: Information-theoretic lower bounds for convex optimization with erroneous oracles »
Yaron Singer · Jan Vondrak -
2015 Poster: Fast Convergence of Regularized Learning in Games »
Vasilis Syrgkanis · Alekh Agarwal · Haipeng Luo · Robert Schapire -
2015 Oral: Fast Convergence of Regularized Learning in Games »
Vasilis Syrgkanis · Alekh Agarwal · Haipeng Luo · Robert Schapire -
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