Variance-based Regularization with Convex Objectives

By Hongseok Namkoong, John C. Duchi. 2016

378 citations recorded by the source corpus.

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.

Subfields: Management Science and Operations Research, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Measuring Robustness to Natural Distribution Shifts in Image Classification (2020, methodology): “Distributionally robust optimization (DRO) is another recently proposed technique to increase robustness to distribution shift [22, 23].”
Conservative Q-Learning for Offline Reinforcement Learning (2020, methodology): “In Appendix A, we discuss an additional variant of CQL, drawing connections to distributionally robust optimization [43].”
Fairness Without Demographics in Repeated Loss Minimization (2018, methodology): “We build on the distributionally robust formulation of Duchi et al. (2016) which will allow us to control the worst-case group risk R max ( θ ( t ) ) .”
Conditional variance penalties and domain shift robustness (2017, methodology): “The crucial difference of our approach to Namkoong and Duchi (2017) is that we penalize with the expected conditional variance or standard deviation.”
Distributionally Robust Optimization: A Review (2019, neutral): “[92], Namkoong and Duchi [209].”
Class-Weighted Classification: Trade-offs and Robust Approaches (2020, background): “A variant that has gained traction more recently is distributionally robust optimization (Ben-Tal et al., 2013; Bertsimas et al., 2014; Namkoong and Duchi, 2017).”
CAUSALITY FROM A DISTRIBUTIONAL ROBUSTNESS POINT OF VIEW (2018, background): “Some related examples of work in this direction include [3] and [4], where the class Q of distributions we would like the network to perform well under is typically chosen as an -ball around the empirical or true distribution in a Wasserstein or Kullback-Leibler metric to reflect the nature of allow”
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach (2016, methodology): “To address poor coverage in small sample or high-dimensional scenarios, two of the authors have extended the results of this paper (see [40]) to provide finite-sample guarantees for the upper bound un.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, neutral): “Other applications include robust optimization [Namkoong and Duchi, 2016, 2017], adversarial machine learning [Sinha et al., 2017, Madry et al., 2017], unsupervised learning [Xu et al., 2005], and so on.”
Robust estimation via robust gradient estimation (2018, methodology): “We also compare against the robust estimation techniques of Hsu and Sabato (2016) and Duchi and Namkoong (2016), which we refer respectively to as RobustHS and RobustDN, and two classical techniques namely the lasso (Tibshirani, 1996) and ridge regression.”
A Kernel Theory of Modern Data Augmentation (2018, background): “Moreover, we draw connections to recent work on invariant learning [24, 30] and robust optimization [28], illustrating that data augmentation not only affects the model by increasing invariance to specific transformations, but also by reducing the variance of the estimator.”
Certified Adversarial Robustness with Additive Noise (2018, background): “For example, [20] study robust optimization over a φ-divergence ball of a nominal distribution.”
Tilted Empirical Risk Minimization (2020, methodology): “…applications, such as learning in the presence of noisy/corrupted data or outliers [25, 30], performing classiﬁcation with imbalanced data [37, 38], ensuring that subgroups within a population are treated fairly [36, 42, 56], or developing solutions with favorable out-of-sample performance [43].”
Distributionally Robust Language Modeling (2019, background): “Optimizing on a ball of distributions around the empirical distribution has been considered in prior work (Ben-Tal et al., 2013; Namkoong and Duchi, 2017; Duchi and Namkoong, 2016; Sinha et al., 2018).”
Does Distributionally Robust Supervised Learning Give Robust Classifiers? (2016, background): “To better understand its property, inspired by Namkoong & Duchi (2017), we decompose it as 6 where ) is the risk of the classiﬁer on latent category z 2 Z .”
Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, positive): “Other robust risk minimization (RRM) methods utilize uncertainty sets determined by metrics such as Wasser-stein distances (Shaﬁeezadeh-Abadeh et al., 2019) and f-divergences (Namkoong & Duchi, 2017).”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “The idea of pessimism has appeared in the literature of risk minimization [48, 8].”