Robust Optimization for Non-Convex Objectives

By Robert S. Chen, Brendan Lucier, Yaron Singer, Vasilis Syrgkanis. 2017

130 citations recorded by the source corpus.

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 $\alpha$-approximate solutions for distributions over objectives, we compute a distribution over solutions that is $\alpha$-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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Agnostic Federated Learning (2019, methodology): “We note that similar algorithms have been proposed for solving minimax objectives (Namkoong & Duchi, 2016; Chen et al., 2017).”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, methodology): “The most related work addressing non-convex robust optimization is Chen et al. (2017).”
Two-Player Games for Efficient Non-Convex Constrained Optimization (2018, methodology): “We report two variants: (i) the “Uniform Distribution Baseline” of Chen et al. [2017] is a stochastic classifier, uniformly sampled over the θs (like our θ̄ classifier), and (ii) a non-stochastic classifier taking its parameters from the last iterate θ .”
Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints (2018, methodology): “The set of allowed λ s is exactly the covering centers, while, following Chen et al. [2017], Agarwal et al. [2018] and Cotter et al. [2018], the associated θ s are found using an approximate Bayesian optimization oracle: Deﬁnition 3.”
Pairwise Fairness for Ranking and Regression (2019, background): “1 ), or (ii) only requiring the minimum pairwise accuracy A G i >G j to be as big as possible (i.e. maximize min i (cid:54) = j A G i >G j ), in the style of robust optimization [e.g. Chen et al., 2017].”
Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective (2019, background): “This strikes a balance between the computation efﬁciency and the convergence accuracy [ Chen et al. , 2017; Qian et al. , 2018 ] .”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “There has been a recent surge in research on solving minimax optimization beyond the convex-concave regime [Sinha et al., 2017, Chen et al., 2017, Qian et al., 2019, Thekumparampil et al., 2019, Lin et al., 2018, Nouiehed et al., 2019, Abernethy et al., 2019], but they diﬀer from our work from…”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “For example, [13, 66, 18] assume the maximization problem can be solved exactly, which is either unrealistic or is very expensive.”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, background): “Finding the global minmax point even with access to these oracles is NP hard [Chen et al., 2017].”