# Variance-based regularization with convex objectives

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

## Key facts

- Cited by 155 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2016.

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

- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Correct-N-Contrast: A Contrastive Approach for Improving Robustness to Spurious Correlations](https://mlsanity.com/paper/2203.01517/) (2022)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Risk-Averse Offline Reinforcement Learning](https://mlsanity.com/paper/2102.05371/) (2021)
- [Tapered Off-Policy REINFORCE: Stable and efficient reinforcement learning for LLMs](https://mlsanity.com/paper/2503.14286/) (2025)
- [Towards Robust Alignment of Language Models: Distributionally Robustifying Direct Preference Optimization](https://mlsanity.com/paper/2407.07880/) (2024)
- [Model Agnostic Sample Reweighting for Out-of-Distribution Learning](https://mlsanity.com/paper/2301.09819/) (2023)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Learning Fair Classifiers with Partially Annotated Group Labels](https://mlsanity.com/paper/2111.14581/) (2021)
- [Robust Learning with Progressive Data Expansion Against Spurious Correlation](https://mlsanity.com/paper/2306.04949/) (2023)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2202.09667/) (2022)
- [Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2209.06620/) (2022)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Learning to Solve Routing Problems via Distributionally Robust Optimization](https://mlsanity.com/paper/2202.07241/) (2022)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [C-RAG: Certified Generation Risks for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2402.03181/) (2024)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [Freeze then Train: Towards Provable Representation Learning under Spurious Correlations and Feature Noise](https://mlsanity.com/paper/2210.11075/) (2022)
- [Understanding Contrastive Learning via Distributionally Robust Optimization](https://mlsanity.com/paper/2310.11048/) (2023)
- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Learning from Heterogeneity: Generalizing Dynamic Facial Expression Recognition via Distributionally Robust Optimization](https://mlsanity.com/paper/2507.15765/) (2025)
- [Distributionally Robust Multilingual Machine Translation](https://mlsanity.com/paper/2109.04020/) (2021)
- [Holistic Robust Data-Driven Decisions](https://mlsanity.com/paper/2207.09560/) (2022)
- [Auxiliary Task Update Decomposition: The Good, The Bad and The Neutral](https://mlsanity.com/paper/2108.11346/) (2021)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)

## Abstract (arXiv)

We develop an approach to risk minimization and stochastic optimization that provides a convex surrogate for variance, allowing near-optimal and computationally efficient trading between approximation and estimation error. Our approach builds off of techniques for distributionally robust optimization and Owen's empirical likelihood, and we provide a number of finite-sample and asymptotic results characterizing the theoretical performance of the estimator. In particular, we show that our procedure comes with certificates of optimality, achieving (in some scenarios) faster rates of convergence than empirical risk minimization by virtue of automatically balancing bias and variance. We give corroborating empirical evidence showing that in practice, the estimator indeed trades between variance and absolute performance on a training sample, improving out-of-sample (test) performance over standard empirical risk minimization for a number of classification problems.