Learning Models with Uniform Performance via Distributionally Robust Optimization

John Duchi; Hongseok Namkoong

Source-linked AI summary

Learning Models with Uniform Performance via Distributionally Robust Optimization

John Duchi, Hongseok Namkoong

arXiv:1810.08750v6Oct 20, 2018stat.MLcs.LG

TL;DR

The paper addresses the challenge of achieving uniformly good model performance across hard instances, heterogeneous subpopulations, and distributional shifts. It develops a distributionally robust optimization framework with theoretical guarantees and empirical procedures, finding that robustness controls tail performance but can incur convergence-rate costs.

Problem
Average-optimized models can perform poorly on hard instances, minority subpopulations, and data domains that differ from training conditions.
Method
The paper formulates distributional robustness through a worst-case risk over distributions within a divergence radius and develops a dual, efficiently minimizable plug-in estimator with tuning heuristics.
Results
The framework controls tail performance and provides convergence guarantees, minimax upper and lower bounds, and empirical performance on latent worst-case subpopulations and rare events.
Takeaways & Limitations
Distributional robustness can provide uniform performance against sufficiently close distributional shifts, while larger robustness regions impose statistical costs through slower minimax convergence rates.
Takeaways & Limitations
Choosing the robustness divergence f and radius ρ lacks principled guidance and may be unrealistic for users to justify, despite proposed heuristics.

Abstract

from arXiv · show

A common goal in statistics and machine learning is to learn models that can perform well against distributional shifts, such as latent heterogeneous subpopulations, unknown covariate shifts, or unmodeled temporal effects. We develop and analyze a distributionally robust stochastic optimization (DRO) framework that learns a model providing good performance against perturbations to the data-generating distribution. We give a convex formulation for the problem, providing several convergence guarantees. We prove finite-sample minimax upper and lower bounds, showing that distributional robustness sometimes comes at a cost in convergence rates. We give limit theorems for the learned parameters, where we fully specify the limiting distribution so that confidence intervals can be computed. On real tasks including generalizing to unknown subpopulations, fine-grained recognition, and providing good tail performance, the distributionally robust approach often exhibits improved performance.

1 Introduction

The paper develops distributionally robust optimization for models that maintain performance under unknown distributional shifts and across difficult or underrepresented inputs. It combines a convex, computationally efficient formulation with statistical guarantees and empirical evidence, while identifying costs and open choices in robustness design.

Motivation: Models optimized for average loss can perform poorly on hard instances, minority subpopulations, and shifted domains, creating risks in safety- and fairness-critical applications.Motivating examples include medical diagnosis, autonomous vehicles, criminal justice, credit evaluations, and speech recognition.
Scope: The framework targets unknown shifts without requiring latent subgroup information, unlike methods that rely on identified target domains or explicit mixture structure.Its joint-distribution robustness is more conservative than approaches addressing covariate shifts alone.
Approach: The proposed worst-case risk upweights high-loss regions, providing uniform performance when alternative distributions remain within a specified f-divergence radius of the data-generating distribution.The robustness radius ρ controls the allowed distributional shift.
Empirical findings: Experiments find that robust estimation sacrifices some average-case performance for lower losses on difficult subpopulations, including settings with unknown rare groups.The paper proposes validation heuristics that use non-exchangeable data splits to choose f and ρ.
Approach: The empirical plug-in estimator is computationally efficient through a finite-dimensional dual formulation and retains convexity for convex losses.The formulation can be solved as a single convex minimization problem rather than a minimax problem.
Theory: Distributional robustness can degrade minimax convergence rates because protecting against gross shifts requires estimating high moments of losses.For f-divergences growing as t^k, the paper derives matching minimax lower bounds up to logarithmic factors.
Theory: The estimator is consistent under mild regularity conditions and asymptotically normal at the typical √n-rate, enabling calibrated confidence intervals.These asymptotic results characterize typical estimator behavior beyond minimax guarantees.

2 Formulation

The formulation represents distributional robustness as risk-averse loss minimization over an f-divergence uncertainty set. Its dual form is convex and computationally tractable, while examples connect divergence choices to tail losses, worst-case subpopulations, and latent-group interventions.

2 Formulation: The worst-case objective replaces average loss with the largest expected loss over distributions within an f-divergence radius of the reference distribution.The likelihood-ratio representation rewrites the shift as reweighting relative to the reference distribution.
2 Formulation: For convex losses, the dual formulation is jointly convex in the model parameter and auxiliary variables, enabling a single convex optimization problem.Direct primal methods such as gradient descent are also possible for large-scale settings.
Divergence families: The Cressie-Read family is parameterized by k and includes χ2-divergence, empirical likelihood, and KL-divergence as special cases or limits.The paper focuses on k ∈(1, ∞) for its finite-sample guarantees.
Divergence families: For the Cressie-Read family, the simplified dual penalizes losses above the optimal threshold η⋆ and emphasizes them through an L_k∗(P)-norm.This establishes the paper’s equivalence between distributional robustness and tail-performance control.
2.1 Examples: For latent-group models, the robustness set represents distributional interventions on the unobserved variable, but the precise intervention form remains an open question.The examples use latent mixtures to connect robustness with heterogeneous subpopulations.
2.1 Examples: In well-specified linear models with stochastically smallest residual loss, the robust population parameter can coincide with the true or ordinary least-squares parameter.The plug-in robust estimator may nevertheless be less efficient than ordinary least squares.
2.1 Examples: The robust objective can be interpreted as a mixture of worst-case CVaR risks over subpopulation sizes, although precisely matching subpopulation size to the robustness set is challenging.CVaR_α corresponds to the expected loss of the worst subpopulation containing at least α mass.
2.1 Examples: As robustness increases, the estimator interpolates from an average-risk parameter toward one minimizing the worst subpopulation expected loss.The examples describe this transition using α ↓0 and the relationship between α and robustness.

3 Empirical analysis, validation, and choice of uncertainty set

The empirical analysis evaluates distributional robustness across domain shifts, tail losses, and heterogeneous subpopulations, while examining how divergence choices and tuning heuristics trade average performance for more uniform tail performance.

Experimental scope: The experiments cover domain adaptation, tail-loss performance, and heterogeneous subpopulations using the Cressie-Read divergence family.The study also evaluates real-world handwritten-to-typewritten digit recognition, crime prediction, and fine-grained recognition tasks.
Choice of uncertainty set: Increasing robustness enlarges protection against difficult or shifted inputs but can sacrifice average-case empirical performance.The trade-off is controlled by the divergence parameter k and radius ρ.
3.1.1 Domain adaptation and distributional shifts: Under distributional shifts, robust solutions can outperform ERM as perturbations grow, reversing the mean-performance ordering observed without perturbation.ERM performs best at s = 0, whereas the most robust method performs best under large perturbations.
3.1.3 Performance on different subpopulations: In two-group simulations, robust methods interpolate between ERM's best average loss and worst minority loss and the maximin estimator.The tuning heuristic YSplit improves minority performance while sacrificing very little average-case performance.
3.1.3 Performance on different subpopulations: For infinitely many groups, YSplit balances average and minority performance, while G = .5 performs well on a rare minority group despite tuning on a distant auxiliary group.The auxiliary intervention is G = 0.5, while the evaluated minority group is G = 0.
3.2 Domain generalization for classification and digit recognition: In digit recognition, robust estimators consistently perform well on latent typewritten-digit minorities by upweighting hard training instances.The robust classifier's hardest-class accuracy is .17 versus .03 for the non-robust classifier, while overall accuracy is .38 versus .28.
3.3 Tail performance in a regression problem: Robust regression produces similar or slightly higher median losses but much smaller tail losses, with maximal loss decreasing as ρ grows.Median loss increases slowly as robustness increases.
Fine-grained recognition: In fine-grained recognition, increasing ρ moderately improves overall accuracy, reduces across-class variation, and improves performance on classes where ERM performs poorly.Tail performance improves monotonically up to ρ = 10, while higher values may become overly conservative.

4 Convergence Guarantees

The paper establishes finite-sample convergence guarantees for the distributionally robust plug-in estimator, including rate-optimal minimax bounds under Cressie-Read divergences. It also identifies assumptions and open directions for extending these guarantees.

Finite-sample guarantees: Finite-sample convergence guarantees are developed for the distributionally robust estimator under f-divergences with f(t) ≍ t^k.The analysis studies the plug-in estimator’s finite-sample and asymptotic properties and provides minimax bounds.
Finite-sample guarantees: n^-1/(k*∨2) is a high-probability excess-risk rate for the empirical minimizer, where k* = k/(k−1).This rate is optimal in n up to logarithmic factors and worsens as the robustness set becomes larger.
Assumptions and open problems: The finite-sample theory assumes bounded losses, while extending guarantees to sub-Gaussian or sub-exponential tails and general f-divergences remains future work.The authors also identify scale-sensitive complexity measures such as Rademacher complexity as an open direction.
Uniform guarantees: Uniform guarantees are obtained through covering numbers for the loss-function class and concentration arguments.The paper defines covering numbers and uses a covering argument to pass from pointwise to uniform concentration.

5 Lower Bounds

The paper establishes minimax lower bounds for estimating and optimizing distributionally robust risks, showing that robustness can impose slower convergence rates. The rates depend on the asymptotic growth of the divergence function and quantify costs of protecting against large distributional shifts.

Rate trade-offs: Matching minimax lower bounds show that the finite-sample upper rates are rate optimal up to logarithmic factors.The paper notes that optimal dimension-dependent bounds remain open.
Rate trade-offs: The lower bounds include a necessary transition from parametric √n-type rates to n^-1/k* rates when protection against large distributional shifts is sought.This transition occurs when k is small, corresponding to k* being large.
Lower-bound framework: The lower bounds are divided between estimating the robust-risk value and optimizing the distributionally robust objective.The optimization bounds build on the risk-estimation results.
Estimation rates: Slow growth of f makes the robust formulation more conservative and produces slower convergence rates.The growth of the function defining the divergence fundamentally determines worst-case rates.

6 Asymptotics

The paper analyzes pointwise asymptotics of the empirical distributionally robust optimizer, establishing consistency and, under regularity conditions, standard-rate asymptotic normality. These results support confidence regions while retaining explicit assumptions on smoothness, growth, and identifiability.

Asymptotic normality: Under appropriate regularity conditions, the empirical optimizer can achieve the usual √n convergence rate and asymptotic normality.The analysis is pointwise in a fixed data-generating distribution, contrasting with the slower uniform minimax rates.
Consistency: The empirical robust risk is pointwise consistent for its population counterpart under an integrability condition involving the convex conjugate f*.For each fixed θ, Rf(θ; P̂n) converges almost surely to Rf(θ; P0) when E[f*(|ℓ(θ;X)|)] is finite.
Consistency: Under coercivity and convexity assumptions, approximate empirical optimizers eventually lie near the population optimizer set.Coercivity also guarantees existence and compactness of the population optima.
Asymptotic normality: The asymptotic-normality analysis assumes a unique optimizer, local smoothness and growth conditions, and strong identifiability of the dual nuisance variables.The strong-identifiability assumption requires a positive-definite Hessian for the dual objective and positive probability of positive excess loss.
Inference: Consistent plug-in covariance estimators yield an asymptotically pivotal confidence region for the population optimizer.This follows by combining consistent estimators with the asymptotic-normality result.
Limitations: The paper notes that relaxing the identifiability assumption through direct analysis of the primal formulation remains open.This is stated as an unresolved question for the asymptotic-normality theory.

7 Discussion and further work

The discussion identifies open questions around choosing robustness sets, understanding dimensional dependence and assumptions, and relating distributional robustness to other robustness frameworks.

Limitations: The main limitation is insufficient guidance for choosing the robustness set {Q : D_f(Q||P_0) ≤ ρ}.The paper offers heuristics for choosing f and ρ, but principled analysis of these adaptive procedures remains future work.
Limitations: Larger robustness sets make estimation and optimization more difficult, with matching minimax rates up to logarithmic factors but unresolved dimension dependence.The stated upper and lower rates are n^-1/k* up to logarithmic factors.
Future work: The asymptotic results require an identifiability assumption on the dual formulation, whose relaxation through direct primal analysis remains open.The paper also identifies scale-sensitive complexity bounds as a future research direction.
Connections: Distributionally robust estimation differs from classical Huber robustness by seeking parameters that perform well for all nearby contaminations rather than estimating under contamination by some Q.The comparison concerns the target of estimation and the way neighboring distributions are modeled.
Connections: For covariate-and-outcome problems, the formulation shifts the joint distribution, whereas traditional domain adaptation shifts only the covariate marginal while fixing the conditional outcome distribution.The paper notes that deeper connections with causal interventions and classical contamination models remain to be developed.

A Proof of Duality Results

The appendix derives duality results for Cressie–Read divergences and uses their asymptotic growth to characterize robust risk through high-order loss moments.

Fenchel conjugate: The proof begins by computing the Fenchel conjugate f_k^* of the Cressie–Read divergence family.It maximizes st − f_k(t) over t and analyzes the optimizer by the sign and magnitude of s.
Fenchel conjugate: For nonnegative s in the admissible range, differentiating the conjugate objective yields t = ((k−1)s + 1)^(1/(k−1)).For s < 0, the supremum is attained at t = 0.
Fenchel conjugate: The conjugate derivation uses the identity 1 − 1/k = 1/k*.This relation connects the Cressie–Read parameter k to its conjugate exponent k*.
Dual formulation: The dual formulation is further optimized by shifting η to η − λ/(k−1) and differentiating with respect to λ.Substitution of the optimizing value produces the closed-form supremum used in the robust-risk analysis.
Asymptotic growth: When f grows like t^k, its derivative and conjugate inherit corresponding power bounds, enabling asymptotic control of the dual objective.The argument assumes differentiability and bounds f(t)/t^k between positive finite limits.
Robust-risk characterization: The resulting dual expression depends on k*th moments of the loss, with the optimization over λ contributing a ρ^(1/k) dependence.Writing Z = ℓ(θ; X), the analysis applies the result beyond a threshold τ_f depending on f.

B.1 Proof of Example 4

The proof of Example 4 characterizes the minimax center through convex optimality and shows that sufficiently tail-focused risk selects it over other parameters.

Minimax center: The proof studies h(θ) = 1/2 max_v∈V ||θ − θ_v||_2^2 and applies strong convexity and subgradient optimality.At a point attaining the maximum distance, θ − θ_v provides a subgradient of h.
Gaussian objective: For fixed η > 0, the argument analyzes objectives h_v(·; η) and their derivatives using continuity of the Gaussian density.Rotational symmetry supplies a positive constant c(η; μ) for vectors μ.
Gaussian objective: The Gaussian comparison establishes that the relevant objective changes with the norm ordering ||μ_1||_2 > ||μ_2||_2.This norm comparison is the key intermediate claim used to derive the example's minimax result.
Tail-focused limit: For sufficiently large η, R′(0; η) < 0, so a non-minimax parameter cannot minimize the robust objective.The proof uses the farthest points V* characterized by the maximum distance from θ.
Tail-focused limit: As α decreases, the CVaR threshold η(θ, α) diverges uniformly, allowing the robust-objective comparison to rule out the same non-minimax parameter for small α.The CVaR threshold is the 1 − α quantile of the loss.
Asymptotic calculation: The Gaussian asymptotics used in the proof reduce to standard-normal and Marcum-Q-function behavior as t → ∞.These asymptotics establish the limiting comparison required by the example.

B.2 Proof of Example 5

The proof of Example 5 analyzes mixture CVaR through quantiles and essential suprema, showing convergence toward the minimax parameter as the tail parameter grows.

Mixture CVaR: The proof introduces a technical lemma for Gaussian expectations over v ∼ μ and uses it to analyze mixture CVaR.The mixture setting jointly quantifies over v and (X, Y).
Quantile analysis: Mixture CVaR is analyzed using quantiles quant_p(g, μ) and the essential supremum of g over v.The lemma bounds the exponential integral in terms of the essential supremum.
Assumptions: Boundedness assumptions on Σ_v, σ_v, and θ_v support the asymptotic bounds used in the argument.These assumptions enter explicitly when controlling the quantities in the quantile analysis.
Minimax comparison: If θ differs from θ_minimax, the supremum of τ_v(θ) is strictly larger, yielding the comparison needed for the tail limit.Positive-definiteness of Σ_v ensures uniqueness of θ_minimax in this step.
Limit: Any minimizer θ_η of R(θ; η) converges to θ_minimax as η grows.This is the proof's stated limiting conclusion for Example 5.
CVaR limit: For sufficiently small α, the mixture-CVaR comparison favors θ_minimax over any competing θ.The proof obtains this after showing η_α(θ) diverges uniformly as α decreases.

B.2.1 Proof of Lemma 4

The proof establishes concentration for the robust empirical objective by combining Lipschitz concentration, expectation control, and a compact covering argument. A domain restriction enables uniform convergence over the optimization variable.

Pointwise concentration: gk(η; bPn) is Lipschitz in the data vector, allowing a convex Lipschitz concentration inequality to be applied.The Lipschitz property is established before invoking the concentration result.
Pointwise concentration: For bounded η, the proof separately controls fluctuations around the empirical expectation and the gap between empirical and population expectations.The two bounds are then combined to obtain pointwise concentration with probability at least 1 −2e^−2t.
Uniform concentration: The proof restricts η to [−(ck−1)−1M, M], a compact interval needed for the covering argument.Convexity and the behavior of g outside the interval justify this restriction.
Uniform concentration: A finite cover of the η-domain transfers pointwise concentration to a uniform bound using Lipschitzness in η and a union bound.The resulting bound controls the difference between the empirical and population infima over the restricted domain.

C.1.1 Proof of Lemma 8

The proof of Lemma 8 derives moment bounds by truncation and scaling, handling the cases q ≥2 and q <2 separately. These bounds support the expectation-control step used in the concentration analysis.

Moment control: The argument introduces γq = max{n^−α, σq} to separate small moments from sample-size-dependent truncation terms.Here σq denotes E[|Y|^q], and α is selected during the proof.
Moment control: The variance bound Var(|Y|^q) ≤ Cqσq controls the fluctuation of empirical q-th moments.The proof uses the assumed relation between the 2q-th and q-th moments.
Rates: Lemma 10 and Hölder’s inequality provide the interpolation bounds needed to control the remaining products in the proof.The proof applies the lemma with a = 2/q when q ∈[1,2].
Function-class extension: A covering argument extends the resulting pointwise control from finitely many losses to the full function class.The proof constructs an ε-cover in the L∞(X) norm and applies the pointwise theorem to its centers.

D.1 Proof of Theorem 3

Theorem 3 is proved with Le Cam’s two-point method: construct distributions that are close in total variation but separated in the robust objective or optimization distance. KL-divergence bounds keep the hypotheses statistically indistinguishable.

Testing reduction: Le Cam’s reduction converts separation in the robust objective into an estimation lower bound when the product distributions remain close in total variation.Pinsker’s inequality links the total variation distance to KL divergence.
Robust-risk lower bound: For two-point distributions, the robust risks are explicitly separated, including Rk(Z1) = M and Rk(Z2) ≤ Mck(pk −δ).The separation is obtained from the closed-form robust-risk calculations for the constructed distributions.
Optimization lower bound: The optimization lower bound constructs distributions whose optimal parameters are separated while their risks remain close enough for the testing reduction.The proof establishes dopt(P1, P2; fk) ≥ ϵ and controls the corresponding KL divergence.
Optimization lower bound: For the linear-loss construction, the robust objectives switch behavior across the perturbation, yielding dopt(P1, P2) ≥ M∆δ.The separation follows from explicit piecewise risk expressions and the identities involving ∆δ.
Optimization lower bound: The final lower-bound rates follow after bounding KL divergence, applying Pinsker’s inequality, and taking the asymptotic scaling limit.The proof explicitly multiplies by √n before taking n →∞.

E.1 Proof of Proposition 9

Proposition 9 uses epi-convergence of empirical dual objectives, together with coercivity and compact-uniform convergence, to establish convergence of robust risks and minimizers. Moment and lower-semicontinuity assumptions ensure the needed analytic properties.

Epi-convergence: The dual empirical objective converges pointwise almost surely on rational parameter pairs by the strong law of large numbers.The convergence is first established for λ, η ∈Q.
Epi-convergence: Lower semicontinuity of the dual objectives follows from conjugacy, Fatou’s lemma, and dominated convergence.The closure of the perspective function is used in the lower-semicontinuity argument.
Coercivity: Finite first moments imply coercivity of the dual objective as the optimization variables diverge.The proof then combines coercivity with epi-convergence to obtain eventual coercivity of the empirical objectives.
Risk and minimizer convergence: Epi-convergence yields uniform convergence on compact sets for the robust-risk functions and convergence of their empirical infima.Convexity is used to obtain eventual coercivity and bounded sublevel sets.
Risk and minimizer convergence: The distance from empirical ε-sublevel sets to the population solution set converges to zero.This uses compactness of the population solution set under the coercivity assumption.
Fixed-parameter structure: For fixed θ, the dual objective is convex and coercive in η, and it is strictly increasing beyond the essential supremum of the loss.Strict convexity below that supremum follows from the equality conditions in Minkowski’s inequality.

F.2 Proof of Theorem 11

The proof verifies the empirical minimizer’s regularity conditions and applies an asymptotic-normality lemma to establish its limiting distribution. Local envelopes, bracketing control, differentiability, and covariance convergence provide the required conditions.

Empirical-process conditions: Bracketing-number bounds for Lipschitz functions make the localized bracketing integral finite, while dominated convergence verifies the remaining local conditions.The proof separately controls the envelope tail, local increments, and covariance convergence.
Localized classes and envelopes: The proof analyzes localized criterion classes around the unique population minimizer and defines envelopes controlling their deviations.The localized class contains criterion differences within an ε-neighborhood, while the envelope bounds their pointwise magnitude.
Conditions for asymptotic normality: The asymptotic-normality lemma requires local C2 curvature, a uniformly bounded bracketing integral, and an envelope with second moment O(ε^2).Positive-definite Hessian curvature at the minimizer is included among the regularity assumptions.
Limit distribution: Under these conditions, any consistent near-minimizer satisfies √n(bv_n−v⋆) converging to the unique maximizer of a Gaussian process.The process has bounded, uniformly continuous sample paths on compact sets, and its covariance is obtained from the local criterion gradients.
Conclusion: The proof concludes by showing that the paper’s optimization problem meets Lemma 19’s assumptions, so the theorem follows immediately.The argument first establishes the technical envelope and conjugacy bounds needed for the verification.
Envelope verification: Gradient bounds establish an envelope M_ε(x)=M(x)·ε, using convexity and local Lipschitz control of the criterion.The proof obtains square-integrability from moment assumptions on the loss and its gradient.