Oral
Robust Optimization for Non-Convex Objectives
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis

Tue Dec 5th 10:55 -- 11:10 AM @ Hall C
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)

More from the Same Authors