Oracle-Based Robust Optimization via Online Learning
This work addresses a computational bottleneck for practitioners in optimization under uncertainty, offering a more efficient approach, though it is incremental as it builds on existing online learning techniques.
The paper tackles the computational challenge of robust optimization, which often leads to complex or NP-hard problems, by developing an approximate method using online convex optimization that solves standard non-robust problems iteratively, achieving an inverse square relationship between oracle calls and target accuracy.
Robust optimization is a common framework in optimization under uncertainty when the problem parameters are not known, but it is rather known that the parameters belong to some given uncertainty set. In the robust optimization framework the problem solved is a min-max problem where a solution is judged according to its performance on the worst possible realization of the parameters. In many cases, a straightforward solution of the robust optimization problem of a certain type requires solving an optimization problem of a more complicated type, and in some cases even NP-hard. For example, solving a robust conic quadratic program, such as those arising in robust SVM, ellipsoidal uncertainty 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 in every stage a standard (non-robust) optimization program is solved. Our algorithms find an approximate robust solution using a number of calls to an oracle that solves the original (non-robust) problem that is inversely proportional to the square of the target accuracy.