Oracle-based robust optimization via online learning
From MaRDI portal
Publication:3450465
DOI10.1287/OPRE.2015.1374zbMATH Open1327.90379arXiv1402.6361OpenAlexW2104212779MaRDI QIDQ3450465FDOQ3450465
Authors: Aharon Ben-Tal, Elad Hazan, Tomer Koren, Shie Mannor 
Publication date: 6 November 2015
Published in: Operations Research (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1402.6361
Recommendations
- Online first-order framework for robust convex optimization
- Robust convex optimization
- Robust and distributionally robust optimization models for linear support vector machine
- Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
- Cutting-set methods for robust convex optimization with pessimizing oracles
Cites Work
- Computing a Trust Region Step
- Prediction, Learning, and Games
- Robustness and regularization of support vector machines
- Theory and applications of robust optimization
- Robust discrete optimization and network flows
- Uncertain convex programs: randomized solutions and confidence levels
- Online learning and online convex optimization
- 10.1162/153244303321897726
- Robust optimization-methodology and applications
- Robust convex optimization
- Robust Control of Markov Decision Processes with Uncertain Transition Matrices
- Efficient algorithms for online decision problems
- The multiplicative weights update method: a meta-algorithm and applications
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- A linear-time algorithm for trust region problems
- Second order cone programming approaches for handling missing and uncertain data
- Robust support vector machines for classification and computational issues
- Robust Regression and Lasso
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Cutting-set methods for robust convex optimization with pessimizing oracles
Cited In (23)
- Statistics of robust optimization: a generalized empirical likelihood approach
- Online first-order framework for robust convex optimization
- A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
- Oracle-efficient Online Learning and Auction Design
- Cutting-set methods for robust convex optimization with pessimizing oracles
- Title not available (Why is that?)
- Proximal-ACCPM: a versatile oracle based optimisation method
- Multiple kernel learning-aided robust optimization: learning algorithm, computational tractability, and usage in multi-stage decision-making
- Derivative-free robust optimization by outer approximations
- Robust randomized optimization with \(k\) nearest neighbors
- Specifying and solving robust empirical risk minimization problems using CVXPY
- Wald's mighty maximin: a tutorial
- Title not available (Why is that?)
- Statistical optimization in high dimensions
- Characterization of the equivalence of robustification and regularization in linear and matrix regression
- Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets
- Distributionally robust optimization. A review on theory and applications
- Adversarial classification via distributional robustness with Wasserstein ambiguity
- Decision making in multiobjective optimization problems under uncertainty: balancing between robustness and quality
- A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
- Variance-based regularization with convex objectives
- Data-driven robust optimization
- Exploiting problem structure in optimization under uncertainty via online convex optimization
Uses Software
This page was built for publication: Oracle-based robust optimization via online learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450465)
