Robust Optimization for Non-Convex Objectives
This work addresses robust optimization challenges in machine learning, particularly for non-convex problems, with applications in neural networks and submodular optimization, though it is incremental as it builds on existing reduction and Bayesian optimization frameworks.
The paper tackles robust optimization for non-convex objectives by developing a reduction from robust improper optimization to Bayesian optimization, showing that de-randomizing solutions is NP-hard but feasible for learning tasks, and applies this to neural network training and submodular optimization with experimental validation on tasks like corrupted character classification and robust influence maximization.
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 $α$-approximate solutions for distributions over objectives, we compute a distribution over solutions that is $α$-approximate in the worst case. We show that de-randomizing 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.