Robust Optimization for Non-Convex Objectives
Robert S. Chen, Brendan Lucier, Yaron Singer, Vasilis Syrgkanis
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.
BibTeX
@inproceedings{NIPS2017_10c66082,
author = {Chen, Robert S. and Lucier, Brendan and Singer, Yaron and Syrgkanis, Vasilis},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Robust Optimization for Non-Convex Objectives},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/10c66082c124f8afe3df4886f5e516e0-Paper.pdf},
volume = {30},
year = {2017}
}