Skip to yearly menu bar Skip to main content


Poster

Robust Optimization for Non-Convex Objectives

Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis

Pacific Ballroom #158

Keywords: [ Optimization for Deep Networks ] [ Non-Convex Optimization ] [ Submodular Optimization ] [ Convex Optimization ] [ Learning Theory ]


Abstract: 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.

Live content is unavailable. Log in and register to view live content