PaperlayerView exact revision on arXiv

Source-linked AI summary

Does Distributionally Robust Supervised Learning Give Robust Classifiers?

Weihua Hu, Gang Niu, Issei Sato, Masashi Sugiyama

arXiv:1611.02041v6stat.MLcs.LG

TL;DR

Distribution shift can undermine supervised learning, while f-divergence DRSL is intended to address it through adversarial reweighting. This paper analyzes that approach in classification, finds that it can remain optimal for the training distribution, and proposes a structurally constrained DRSL alternative.

  • Problem

    In classification, f-divergence DRSL is studied despite a mismatch between 0-1 test loss and surrogate training loss, and its behavior under this setting needs analysis.

    Source: §1 · p. 1

  • Method

    The paper analyzes f-divergence DRSL in classification and proposes simple DRSL that incorporates structural assumptions on distribution shift.

    Source: §1 · p. 1

  • Results

    The analysis shows f-divergence DRSL can yield a classifier optimal for the training distribution, while experiments demonstrate the proposed DRSL's effectiveness.

    Source: §1 · p. 1, §7 · p. 8

  • Takeaways & Limitations

    The paper concludes that robust classification with DRSL can be based on structural assumptions about distribution shift, with efficient algorithms and empirical evidence presented.

    Source: §7 · p. 8

    For regression with f-divergence DRSL and the same loss at training and testing, steeper losses may make learning sensitive to outliers, so datasets need extra scrutiny for outliers.

    Source: §3 · p. 5

Abstract

from arXiv · show

Distributionally Robust Supervised Learning (DRSL) is necessary for building reliable machine learning systems. When machine learning is deployed in the real world, its performance can be significantly degraded because test data may follow a different distribution from training data. DRSL with f-divergences explicitly considers the worst-case distribution shift by minimizing the adversarially reweighted training loss. In this paper, we analyze this DRSL, focusing on the classification scenario. Since the DRSL is explicitly formulated for a distribution shift scenario, we naturally expect it to give a robust classifier that can aggressively handle shifted distributions. However, surprisingly, we prove that the DRSL just ends up giving a classifier that exactly fits the given training distribution, which is too pessimistic. This pessimism comes from two sources: the particular losses used in classification and the fact that the variety of distributions to which the DRSL tries to be robust is too wide. Motivated by our analysis, we propose simple DRSL that overcomes this pessimism and empirically demonstrate its effectiveness.

1. Introduction

Distribution shift can degrade supervised learning because standard ERM assumes training and test distributions match. The paper analyzes f-divergence DRSL for classification, identifies why it can be too pessimistic, and proposes a structurally constrained alternative.

1. Introduction

  • Distribution shift from sample selection bias or environmental non-stationarity can significantly degrade traditional supervised learning performance.ERM assumes test and training distributions are the same.Source: §1 · p. 1
  • DRSL models shift through a minimax game: an adversary changes the test distribution within a specified uncertainty set, then the learner minimizes expected loss.Source: §1 · p. 1
  • Classification uses 0-1 loss at test time but surrogate loss during training, unlike the same-continuous-loss assumption common in f-divergence DRSL studies.Source: §1 · p. 1
  • f-divergence DRSL applied to classification yields a classifier optimal for the training distribution, a pessimistic outcome attributed to classification losses and an overly flexible uncertainty set.The paper proposes simple DRSL using structural assumptions on distribution shift to address this pessimism.Source: §1 · p. 1
  • The proposed simple DRSL incorporates structural assumptions on distribution shift; the paper also establishes convergence properties, derives efficient algorithms, and reports experiments.Source: §1 · p. 1
  • Other DRSL uncertainty sets include feature deletion, unknown conditional-label properties, and Wasserstein balls; Wasserstein DRSL can address adversarial examples, while f-divergence DRSL reweights data points.Source: §1 · pp. 1–2

2. Review of ERM and DRSL

The section reviews ERM's training-distribution objective and contrasts it with DRSL's worst-case objective over a set of possible test distributions. For f-divergences, the adversary reweights losses, with both population and empirical formulations described.

2. Review of ERM and DRSL

  • ERM begins with i.i.d. training samples and a prediction function, with empirical risk approximating the population risk.Source: §2 · p. 2
  • DRSL minimizes risk under the worst-case test distribution in an uncertainty set, whereas ERM approximates expected risk using the training data.Source: §2 · p. 2
  • In f-divergence DRSL, the uncertainty set is an f-divergence ball around the training distribution, and δ controls the allowed shift.The density ratio r(x, y) = q(x, y)/p(x, y) acts as an adversarial weight on each data loss.Source: §2 · p. 2
  • The adversary chooses density-ratio weights to maximize expected loss, then the learner minimizes that reweighted loss in adversarial risk minimization.Source: §2 · p. 2
  • The cited formulations differ in purpose: prior work decays δ with sample size and sets δ = 0 in the population objective, while this paper uses the same δ > 0 to address actual train-test distribution change.Source: §2 · p. 2
  • For empirical adversarial risk minimization, the adversary reweights training-data losses, and a regularizer may be added to prevent overfitting.Source: §2 · pp. 2–3

3. Analysis of DRSL with f-divergences in classification

In classification, f-divergence DRSL can still select classifiers optimal for the training distribution, despite targeting worst-case shifted losses. The analysis ties this pessimism to classification losses and overly flexible uncertainty sets.

The 0-1 loss case

  • With 0-1 loss, adversarial and ordinary risks have the same global minima when adversarial risk is below 1, so hyperparameter selection minimizes training misclassification.The same monotonic relationship holds for their empirical approximations.Source: §3 · p. 3

The surrogate loss case

  • Under the stated assumptions, ARM can yield the Bayes-optimal decision boundary for the training distribution, as ordinary risk minimization does.The result assumes a differentiable density function and a hypothesis class of all measurable functions.Source: §3 · pp. 3–4

Implication for classification

  • Under a mild condition, AERM with a convex classification-calibrated margin loss reduces to ERM with a convex classification-calibrated loss, targeting the training-optimal classifier.The analyzed loss classes include binary margin-based and multiclass permutation-invariant losses, including logistic, hinge, exponential, and softmax cross-entropy losses.Source: §3 · pp. 3–4
  • A steeper surrogate may improve robustness for that surrogate loss, but it does not generally make classifiers robust to distribution changes under test-time 0-1 loss.The paper notes that steeper losses can make classifiers more sensitive to outliers.Source: §3 · pp. 4–5

Implication for ordinary regression

  • In ordinary regression with the same loss at training and test time, a steeper loss may improve robustness in that loss while increasing sensitivity to outliers.The paper advises extra attention to outliers in real-world regression datasets.Source: §3 · p. 5

4. DRSL with Latent Prior Probability Change

The proposed structural DRSL limits distribution shifts to changes in latent-category priors, addressing the excessive flexibility behind classification DRSL’s pessimism. Its structural adversarial risk combines ordinary risk with sensitivity to those shifts.

Theoretical motivation

  • ARM’s independently adjustable pointwise weights let its adversary emphasize higher-loss examples, contributing to pessimistic classification results alongside the different training and test losses.The authors identify both the over-flexible uncertainty set and the use of different losses for training and testing as sources of pessimism.Source: §4 · p. 5

Structural assumptions

  • The latent prior probability change assumption lets the test distribution change category priors while keeping each category’s conditional data distribution intact.The model treats data generation as first sampling a latent category, then sampling data conditional on that category.Source: §4 · p. 5
  • Users specify structural assumptions by grouping training examples, such as by class, sub-category, or available meta-information like time and place.The assumptions are supplied externally based on users’ knowledge of potential shifts, rather than inferred from data.Source: §4 · pp. 5–7

Structural adversarial risk

  • Structural ARM restricts adversarial reweighting to latent categories, rather than allowing independent non-parametric weights for each data point.This limited freedom means Theorems 1–3 do not hold for structural ARM, and supports learning classifiers robust to structurally constrained shifts.Source: §4 · p. 5
  • Structural adversarial risk captures both ordinary misclassification risk and sensitivity to shifts in latent-category priors.The sensitivity term is risk variance across categories; large variance indicates vulnerability when test density concentrates on poorly performing categories. The stated decomposition holds for Pearson divergence when δ is not too large, with analogous decompositions for other f-divergences.Source: §4 · p. 6

Convergence and estimation error

  • Under mild conditions, structural AERM’s parameter and structural-risk estimation errors are O(N^-1/4), assuming a linear-in-parameter prediction function and λ decreasing at O(N^-1/2).The rate is slower than the optimal parametric O(N^-1/2) rate because the inner maximization converges at O(N^-1/4); knowing the f-divergence may improve the result to the optimal rate.Source: §4 · p. 6

5. Efficient Learning Algorithms

The section derives gradient-based algorithms for structural AERM and efficient solutions to its inner maximization for KL and Pearson divergences.

Gradient-based learning

  • Danskin’s theorem gives the structural AERM gradient using the solution of its inner maximization.The section derives gradient-based learning algorithms for the structural AERM objective.Source: §5 · p. 7

KL divergence

  • For KL divergence, the inner maximization uses a normalizing constant and obtains its parameter γ by binary search.The KL case uses f(x) = x log x.Source: §5 · p. 7

Pearson divergence and complexity

  • For small δ, the Pearson-divergence inner maximization has an analytic solution after the nonnegativity constraint is dropped; its weight computation costs O(S), versus O(mS) for KL.Here m is the number of binary-search iterations for γ; the added weight computation is described as negligible relative to computing losses and gradients.Source: §5 · p. 7

6. Experiments

The experiments compare ERM, AERM, and structural AERM on classification tasks under specified class-prior and sub-category-prior shifts. Structural AERM achieves significantly lower estimated structural adversarial risks, while AERM performs poorly on both reported metrics.

Datasets and models

  • The evaluation uses six UCI classification datasets, MNIST, and 20newsgroups, with linear softmax models and cross-validated ℓ2 regularization.The regularization parameter is selected by 5-fold cross-validation.Source: §6 · pp. 7–8

Evaluation metrics

  • The experiments evaluate ordinary, adversarial, and structural adversarial risk with 0-1 loss, estimating the risks using held-out test data.The adversarial risk is not explicitly reported because of Theorem 1.Source: §6 · p. 7

Experimental protocols

  • Structural AERM tests robustness to class-prior and sub-category-prior shifts by grouping data by class or sub-category.Because benchmark sub-category labels were unavailable, some original classes were integrated and their labels treated as sub-categories.Source: §6 · pp. 7–8

Results

  • Structural AERM achieved significantly lower estimated structural adversarial risks, while AERM performed poorly on both evaluation metrics.The comparison reports estimated ordinary and structural adversarial 0-1 risks for class-prior and sub-category-prior shifts; the table summarizes 50 random train-test splits.Source: §6 · p. 8, Table 1 · p. 8

Choosing δ

  • δ trades off ordinary risk against sensitivity to distribution shift, and users can tune it using cross-validation estimates of both terms.Increasing δ during training can decrease sensitivity at the expense of a slight increase in ordinary risk.Source: §6 · p. 8

7. Conclusion

The paper concludes that f-divergence DRSL can be pessimistic in classification, and presents structural DRSL as a response. Experiments report that each method performs best on the risk metric it optimizes.

Conclusion

  • The analysis finds that classification DRSL with f-divergences gives a classifier optimal for the training distribution, motivating structural assumptions for robustness to distribution shift.The paper also reports efficient optimization algorithms and empirical effectiveness for the proposed DRSL.Source: §7 · p. 8
  • ERM, AERM, and structural AERM each achieved the best performance on ordinary, adversarial, and structural adversarial risk, respectively.The comparison is reported for the metrics each method optimized.Source: §7 · p. 8

A. Proof of Theorem 1

The proof reduces the adversary’s reweighting problem to the correctly and incorrectly classified regions, then establishes a monotonic relationship between ordinary and adversarial risk. It also extends the argument to empirical approximations.

A. Proof of Theorem 1

  • The proof establishes a monotonic relationship between adversarial risk and the incorrect-classification proportion.It analyzes the two-class reweighting optimization, including cases where the nonnegativity constraint on the correct-class weight is active.Source: A. Proof of Theorem 1 · pp. 10, 12
  • The adversarial risk depends on the model parameters only through ordinary risk, so equal ordinary risks imply equal adversarial risks.The proof constructs an optimal reweighting that is constant within the correctly and incorrectly classified regions.Source: A. Proof of Theorem 1 · pp. 10, 12
  • The same argument applies to empirical approximations by replacing expectations with empirical averages.Source: A. Proof of Theorem 1 · p. 12

B. Proof of Theorem 2

The proof shows that, under its classification-calibration and hypothesis-class assumptions, an adversarial-risk minimizer is Bayes optimal. It extends this conclusion from the adversarial distribution’s support to the training distribution’s support.

B. Proof of Theorem 2

  • The proof assumes a classification-calibrated loss and, for its main multi-class argument, a prediction function ranging over all measurable functions.Source: B. Proof of Theorem 2 · p. 12
  • An adversarial-risk minimizer is Bayes optimal almost surely over the training density under the proof’s assumptions.The proof first establishes Bayes optimality over the adversarial density’s support, then handles training-support points outside that support.Source: B. Proof of Theorem 2 · p. 16
  • The argument also covers binary classification by replacing argmax with sign and adapting the construction used in the multi-class proof.Source: B. Proof of Theorem 2 · p. 16

C. Proof of Lemma 1

The proof establishes that the steeper loss remains convex and classification-calibrated under the stated condition. It also notes that the condition holds when the KL divergence is used.

C. Proof of Lemma 1

  • The derivative of the constructed steeper margin loss is non-decreasing, establishing its convexity.Source: C. Proof of Lemma 1 · pp. 17–18
  • The steeper loss remains classification-calibrated when h(φ(0)) > 0.The proof uses the criterion that a convex margin loss is classification-calibrated when its derivative at zero is negative.Source: C. Proof of Lemma 1 · p. 18
  • For KL divergence, the adversary assigns positive weights to data with positive loss, so the lemma’s condition holds.Source: C. Proof of Lemma 1 · p. 18

D. Proof of Theorem 3

The proof characterizes adversarial reweighting at a stationary point and connects it to ERM with a steeper loss. The remaining subsections derive a PE-divergence decomposition, compare divergence choices, and state convergence results under assumptions.

D. Proof of Theorem 3

  • An optimal adversarial reweighting can be chosen to vary monotonically with the corresponding data losses.The proof rules out weight assignments that violate the required ordering by constructing a reweighting with a larger objective.Source: D. Proof of Theorem 3 · pp. 18–19
  • At an AERM stationary point, a steeper loss can make the same parameter a stationary point of ERM.The constructed loss is steeper because its weighting function is nonnegative and non-decreasing.Source: D. Proof of Theorem 3 · pp. 18–19

E. Derivation of the Decomposition of the Adversarial Risk

F. Comparison between the Use of Different f-divergences

  • The PE quadratic penalty resists concentrating large weights on few latent categories, whereas KL tends to concentrate weights there.The paper advises choosing between these divergences based on beliefs about how concentrated distribution shift is.Source: F. Comparison between the Use of… · p. 20

G. Formal Statement of the Convergence Rate

  • Under the stated assumptions, the paper gives a perturbation result for the model parameter and convergence-rate and estimation-error corollaries as sample size grows.The supplied theorem statements do not provide the rate expressions.Source: G. Formal Statement of the Convergence… · p. 21

H. Proof of the Convergence Rate

The appendix establishes perturbation bounds for the convergence-rate argument, then describes the datasets and class reductions used in experiments and reports surrogate-loss checks.

H. Proof of the Convergence Rate

  • D1 has a Lipschitz constant of order O(∥u′∥_2), while D2 has one of order O(∥u∥_2^(1/2)).These bounds concern the two components of the difference function defined in the proof.Source: H. Proof of the Convergence Rate · pp. 23, 28
  • The uncertainty sets satisfy dH(Φ(u), Φ(0)) = O(∥u∥_2), with the proof relying on a uniform cosine bound.The cosine bound holds for the specified feasible weights and perturbations.Source: H. Proof of the Convergence Rate · pp. 24, 26
  • The convergence-rate argument summarizes a second-order growth condition, uniform Lipschitz continuity of the perturbed objective, and a difference-function Lipschitz bound of O(∥u∥_2^(1/2) + ∥u′∥_2).The bound combines the perturbations in u and u′.Source: H. Proof of the Convergence Rate · p. 28

I. Datasets

  • The experiments use six UCI classification datasets, 20newsgroups, and MNIST, with feature processing tailored to each source.The UCI features are raw; 20newsgroups uses tf-idf followed by PCA to 50 dimensions, and MNIST uses PCA to 50 dimensions.Source: §I · p. 28, Table 2 · p. 28

J. Details of the Subcategory Shift Scenario

  • The class-reduction procedure groups UCI labels by sorted class size, uses odd-versus-even digits for MNIST, and maps 20newsgroups to seven high-level topics.For UCI, alternating sorted labels are assigned to positive and negative categories; original classes become subcategories for MNIST and 20newsgroups.Source: J. Details of the Subcategory Shift… · p. 29

K. Experimental Results measured by Surrogate Loss

L. Experimental Results with the PE divergence

The PE-divergence experiments report surrogate-loss and 0-1-loss comparisons across class-prior and sub-category-prior shifts.

L. Experimental Results with the PE divergence

  • Table 4 compares ordinary and structural adversarial risks using logistic surrogate loss under PE divergence.The table covers class-prior and sub-category-prior shifts and reports means and standard deviations over 50 random train-test splits.Source: Table 4 · p. 30
  • Table 5 reports ordinary and structural adversarial risks using 0-1 loss (%) for PE divergence with δ = 0.5.The comparisons cover class-prior and sub-category-prior shifts, with means and standard deviations over 50 random train-test splits.Source: L. Experimental Results with the PE… · p. 29, Table 5 · p. 30

Related papers

Loading 1611.02041v6…