Robust Optimization for Non-Convex Objectives
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 ↵-approximate solutions for distributions over objectives, we compute a distribution over solutions that is ↵-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.
Summary:
This work provides a method to optimize the worst-case loss over a set of different class of non-convex objective functions. In the real world, observed signals may contain various source of noise, which requires the learning method to be robust enough to the noise. The author converted the robust improper optimization to a Bayesian optimization problem. The proposed learning procedure consists of two iterative steps: the learner tries to minimize the loss with an alpha-approximate Bayesian oracle; the adversary aims to find a distribution over losses that maximize the loss of the learner. The author provide detailed proofs for the convergence and the theoretical bounds of the algorithm. Specifically, a robust statistical learning and a robust submodular maximization cases were discussed. Supportive application experiments were performed to validate the method. The result shows that the proposed method has substantial improvements in the worst-case scores.
Quality:
The paper is well written with theoretical proofs and supportive experiments. The author compared the proposed method with many modifications to support their choice.
Clarity:
The paper is well organized. The experiment details are clearly written. 
Originality:
There are a lot of works in robust optimization in machine learning. This work focuses on more general setting of robust optimization where loss functions are non-convex. The application of alpha-approximate Bayesian oracle is a novel approach.
Significance:
This work provides a general approach for robust optimization of non-convex objective functions. The method is validated from both a neural network learning task and an influence maximization task and it substantially outperformed the baseline approaches. It leads the state-of-art in robust optimization for non-convex problems.