Timezone: »

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

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #158
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 stochastic 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 corrupted character classification, and robust influence maximization in 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