# Oracle-Based Robust Optimization via Online Learning

arXiv: https://arxiv.org/abs/1402.6361 · HTML: https://mlsanity.com/paper/1402.6361/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2014.

## Built on by (most cited first, 9 of 9)

- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [Learning Deterministic Surrogates for Robust Convex QCQPs](https://mlsanity.com/paper/2312.12485/) (2023)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)
- [Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training](https://mlsanity.com/paper/2101.11443/) (2021)
- [Robust Regression over Averaged Uncertainty](https://mlsanity.com/paper/2311.06960/) (2023)
- [Risk-Averse Wasserstein Distributionally Robust Online Learning](https://mlsanity.com/paper/2602.20403/) (2026)

## Abstract (arXiv)

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.