Oracle-based robust optimization via online learning
From MaRDI portal
Publication:3450465
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.
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
- 10.1162/153244303321897726
- A linear-time algorithm for trust region problems
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Computing a Trust Region Step
- Cutting-set methods for robust convex optimization with pessimizing oracles
- Efficient algorithms for online decision problems
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Online learning and online convex optimization
- Prediction, Learning, and Games
- Robust Control of Markov Decision Processes with Uncertain Transition Matrices
- Robust Regression and Lasso
- Robust convex optimization
- Robust discrete optimization and network flows
- Robust optimization-methodology and applications
- Robust support vector machines for classification and computational issues
- Robustness and regularization of support vector machines
- Second order cone programming approaches for handling missing and uncertain data
- The multiplicative weights update method: a meta-algorithm and applications
- Theory and applications of robust optimization
- Uncertain convex programs: randomized solutions and confidence levels
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
- Cutting-set methods for robust convex optimization with pessimizing oracles
- Oracle-efficient Online Learning and Auction Design
- scientific article; zbMATH DE number 4064489 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 7075880 (Why is no real title available?)
- Statistical optimization in high dimensions
- Characterization of the equivalence of robustification and regularization in linear and matrix regression
- Distributionally robust optimization. A review on theory and applications
- Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets
- 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
- Data-driven robust optimization
- Variance-based regularization with convex objectives
- Exploiting problem structure in optimization under uncertainty via online convex optimization
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)
