Oracle-Based Robust Optimization via Online Learning

By Aharon Ben-Tal, Elad Hazan, Tomer Koren, Shie Mannor. 2014

79 citations recorded by the source corpus.

Robust optimization is a common optimization framework under uncertainty when problem parameters are unknown, but it is known that they belong to some given uncertainty set. In the robust optimization framework, a min-max problem is solved wherein a solution is evaluated according to its performance on the worst possible realization of the parameters. In many cases, a straightforward solution to a robust optimization problem of a certain type requires solving an optimization problem of a more complicated type, which might be NP-hard in some cases. For example, solving a robust conic quadratic program, such as those arising in a robust support vector machine (SVM) with an ellipsoidal uncertainty set, leads in general to a semidefinite program. In this paper, we develop a method for approximately solving a robust optimization problem using tools from online convex optimization, where at every stage a standard (nonrobust) optimization program is solved. Our algorithms find an approximate robust solution usin...

Subfields: Management Science and Operations Research, Numerical Analysis

How researchers see this paper

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

In Management Science and Operations Research

In Numerical Analysis

Citations in the corpus

Variance-based Regularization with Convex Objectives (2016, methodology): “procedures that minimize the variance-corrected empirical risk (3). In this paper, we develop an approach based on Owen’s empirical likelihood [38] and ideas from distributionally robust optimization [5, 8, 7] that—whenever the loss ℓis convex—provides a tractable convex formulation that very closel”
Curvature of Feasible Sets in Offline and Online Optimization (2020, background): “This problem, and its generalization with convex objective functions, has a vast literature with applications to a host of areas, from online shortest paths and dynamic search trees [30], to portfolio optimization [33], to robust optimization [6], and many others.”
Data-driven robust optimization (2013, unknown): “An alternative to solving (3) directly is to use cutting-plane, bundle, or online optimization methods (see [7, 12, 37] for details).”
Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization (2015, background): “Two works [15, 6] nicely demonstrate that classiﬁers can achieve very high test accuracy without actually learning the true concepts of the classes they predict.”
Understanding adversarial training: Increasing local stability of supervised models through robust optimization (2015, background): “ssible instances of the problem parameters within the uncertainty set. The robust counterpart of an optimization problem can sometimes be more complicated to solve than the original problem. [13] and [2] propose algorithms for approximately solving the robust problem, which are based only on the alg”
Robust Optimization for Non-Convex Objectives (2017, background): “[3], but where the approximation is multiplicative rather than additive.”
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach (2016, methodology): “imation and stochastic gradient methods [54, 48, 26, 22, 36, 30], there are fewer established and computationally eﬃcient solution methods for minimax problems of the form (4a) (though see the papers [48, 17, 6, 60, 47] for work in this direction). Eﬃcient solution methods need to be developed to sc”
Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences (2016, background): “In Section 4, we give efﬁcient computational schemes for the case that f � , presenting experiments in Section 5.”