# Robust Optimization for Non-Convex Objectives

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2017.

## Built on by (most cited first, 30 of 35)

- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Minimax Demographic Group Fairness in Federated Learning](https://mlsanity.com/paper/2201.08304/) (2022)
- [Net benefit, calibration, threshold selection, and training objectives for algorithmic fairness in healthcare](https://mlsanity.com/paper/2202.01906/) (2022)
- [Investigating the Limitation of CLIP Models: The Worst-Performing Categories](https://mlsanity.com/paper/2310.03324/) (2023)
- [Training Over-parameterized Models with Non-decomposable Objectives](https://mlsanity.com/paper/2107.04641/) (2021)
- [A Simple Yet Effective Strategy to Robustify the Meta Learning Paradigm](https://mlsanity.com/paper/2310.00708/) (2023)
- [Federating for Learning Group Fair Models](https://mlsanity.com/paper/2110.01999/) (2021)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Demystifying Swarm Learning: A New Paradigm of Blockchain-based Decentralized Federated Learning](https://mlsanity.com/paper/2201.05286/) (2022)
- [Best-Effort Adaptation](https://mlsanity.com/paper/2305.05816/) (2023)
- [DRoP: Distributionally Robust Data Pruning](https://mlsanity.com/paper/2404.05579/) (2024)
- [Robust Distillation for Worst-class Performance](https://mlsanity.com/paper/2206.06479/) (2022)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [Lexicographically Fair Learning: Algorithms and Generalization](https://mlsanity.com/paper/2102.08454/) (2021)
- [REDUCR: Robust Data Downsampling Using Class Priority Reweighting](https://mlsanity.com/paper/2312.00486/) (2023)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)
- [Taking a Moment for Distributional Robustness](https://mlsanity.com/paper/2405.05461/) (2024)
- [Predicting Cascading Failures with a Hyperparametric Diffusion Model](https://mlsanity.com/paper/2406.08522/) (2024)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)
- [Private Rate-Constrained Optimization with Applications to Fair Learning](https://mlsanity.com/paper/2505.22703/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Simple Optimizers for Convex Aligned Multi-Objective Optimization](https://mlsanity.com/paper/2509.05811/) (2025)
- [Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training](https://mlsanity.com/paper/2101.11443/) (2021)
- [Fair Graph Machine Learning under Adversarial Missingness Processes](https://mlsanity.com/paper/2311.01591/) (2023)

## Abstract (arXiv)

We consider robust optimization problems, where the goal is to optimize in the worst case over a class of objective functions. We develop a reduction from robust improper optimization to Bayesian optimization: given an oracle that returns α-approximate solutions for distributions over objectives, we compute a distribution over solutions that is α-approximate in the worst case. We show that de-randomizing this solution is NP-hard in general, but can be done for a broad class of statistical learning tasks. We apply our results to robust neural network training and submodular optimization. We evaluate our approach experimentally on corrupted character classification, and robust influence maximization in networks.