PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness to Adversarial Perturbations in Learning from Incomplete Data

Amir Najafi, Shin-ichi Maeda, Masanori Koyama, Takeru Miyato

arXiv:1905.13021v1stat.MLcs.ITcs.LGmath.IT

TL;DR

The paper asks how unlabeled data can help when the underlying distribution is adversarially perturbed, a setting with little semi-supervised DRL research. It combines DRL and self-learning and develops generalization analysis. SSDRL outperforms PL and DRL across three benchmarks, with results versus VAT varying by dataset.

  • Problem

    Semi-supervised approaches to DRL are scarce, leaving the role of unlabeled data under adversarial distribution shifts an open question.

    Source: §1 · p. 1

  • Method

    SSDRL combines DRL with self-learning by inferring soft labels for unlabeled data and seeking classification rules insensitive to perturbations around those distributions.

    Source: §1 · p. 2

  • Results

    SSDRL outperforms PL and DRL on MNIST, SVHN, and CIFAR-10, is comparable to VAT on MNIST and CIFAR-10, and outperforms VAT on SVHN.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis bounds true adversarial risk when the labeled-sample ratio exceeds MSR, and says MSR can be lowered at the cost of a larger generalization bound.

    Source: §1 · p. 2

    For very large label sets, heuristic reduction of candidate labels can improve efficiency at the expense of performance.

    Source: §2.2 · p. 7

Abstract

from arXiv · show

What is the role of unlabeled data in an inference problem, when the presumed underlying distribution is adversarially perturbed? To provide a concrete answer to this question, this paper unifies two major learning frameworks: Semi-Supervised Learning (SSL) and Distributionally Robust Learning (DRL). We develop a generalization theory for our framework based on a number of novel complexity measures, such as an adversarial extension of Rademacher complexity and its semi-supervised analogue. Moreover, our analysis is able to quantify the role of unlabeled data in the generalization under a more general condition compared to the existing theoretical works in SSL. Based on our framework, we also present a hybrid of DRL and EM algorithms that has a guaranteed convergence rate. When implemented with deep neural networks, our method shows a comparable performance to those of the state-of-the-art on a number of real-world benchmark datasets.

1 Introduction

The paper addresses the scarcity of semi-supervised approaches to distributionally robust learning by combining DRL with self-learning. It develops guarantees for generalization and reports benchmark performance for the resulting method, SSDRL.

1 Introduction

  • The introduction positions distribution-shifting adversaries as more detrimental to learning than point-wise adversaries, motivating DRL as a robustness framework.The paper cites for the comparison and describes DRL as targeting distributional perturbations.Source: §1 · p. 1
  • The framework combines DRL with self-learning: it infers soft labels for unlabeled data and seeks classification rules with low sensitivity to perturbations around those distributions.The paper describes the method as an extension of self-learning that can handle SSL scenarios.Source: §1 · pp. 1–2
  • The analysis introduces adversarial complexity measures and MSR; when the labeled-sample ratio exceeds MSR, true adversarial risk can be bounded.The paper says MSR can be decreased by tuning model parameters, at the cost of increasing the generalization bound.Source: §1 · p. 2
  • SSDRL outperforms PL and DRL on MNIST, SVHN, and CIFAR-10; it is comparable to VAT on MNIST and CIFAR-10 and outperforms VAT on SVHN.The introduction identifies SSDRL as the proposed method and reports these comparisons across the three datasets.Source: §1 · p. 2

1.1 Notations

  • DRL is formulated as minimizing worst-case risk over distributions altered within a Wasserstein-cost ambiguity set.The Wasserstein distance measures the minimal cost of moving probability mass between distributions.Source: §1.2 · p. 3, §1.1 · p. 3

1.2 Background and Related Works

  • Prior SSL generalization guarantees require assumptions about the hypothesis set and data distribution, while the paper proposes a compatibility function for a more general setting.The paper also notes that prior DRL-and-SSL work [12] restricts adversarially altered distributions to delta-spikes over labeled and augmented unlabeled samples.Source: §1.2 · p. 4

2 Proposed Framework

The framework extends distributionally robust learning to partially labeled data by selecting label distributions for unlabeled examples, then develops an SGD solver and generalization analysis.

2 Proposed Framework

  • Because standard DRL requires complete feature-label pairs, the framework represents unlabeled labels as conditional distributions and selects a consistent measure for robust training.The selected measure can assign soft labels to unlabeled samples.Source: §2 · pp. 4–5

2.1 Self-Learning: Optimism vs. Pessimism

  • Self-learning assigns pseudo-labels to unlabeled features, while λ controls label assignment, allowing optimism (λ≤0) or pessimism (λ>0).Smaller |λ| promotes softer labels; the learner’s compatibility with the true distribution guides the choice between optimism and pessimism.Source: §2.1 · pp. 5–6

2.2 Numerical Optimization

  • Algorithm 1 uses mini-batch SGD, costs at most η + |Y|(1−η) times the supervised method in, and is guaranteed to converge to a local minimizer.The algorithm reduces to for fully supervised data and coincides with Pseudo-Labeling and EM at specified parameter settings.Source: §2.2 · p. 7

2.3 Generalization Guarantees

  • The analysis bounds true adversarial risk using an adversarial complexity measure and a compatibility condition linking the loss class, data distribution, and supervision ratio.The compatibility condition specifies when unlabeled data can support the bound.Source: §2.3 · p. 8

2.3.1 Adversarial Complexity Measures

  • The SSM Rademacher complexity vanishes with sample size for function classes with bounded VC dimension, regardless of adversarial strength.A distribution-free classical Rademacher bound also bounds the SSM complexity for any supervision ratio and perturbation level.Source: §2.3.1 · pp. 9–10

2.3.2 Minimum Supervision Ratio

  • The bound requires η≥MSR(F,P0)(λ, margin); weak compatibility can raise MSR toward 1, while increasing λ lowers MSR but can loosen the bound.MSR increases with the safety margin; λ=+∞ satisfies the condition regardless of sample size or supervision ratio.Source: §2.3.2 · pp. 10–11

3 Experimental Results

The experiments compare SSDRL and its faster variant with VAT, PL, and DRL on clean and adversarial examples. SSDRL generally leads DRL and PL in adversarial tests, while its comparison with VAT varies by dataset and test conditions.

3 Experimental Results

  • F-SSDRL runs much faster than SSDRL with little performance degradation, and it often performs better in practice.For each unlabeled sample, F-SSDRL considers only a limited number of favorable labels in Algorithm 1.Source: §3 · p. 11
  • SSDRL beats DRL and PL across adversarial tests, beats VAT on SVHN, and is comparable to VAT on MNIST and CIFAR-10, though attack-order reversal changes the comparison.Figures 1 and 2 show error rates under the attack and PGM; γ^-1 and ε index attack strength, respectively.Source: §3 · pp. 11–12, Figure 1 · p. 12, Figure 2 · p. 12
  • On MNIST, SSDRL outperforms DRL for most γ ≥ 0.05, while changing λ's sign causes a sharp error-rate jump and its magnitude has less effect once the sign is fixed.The authors associate the recommendation to use negative λ with sufficiently reliable labels in the labeled data.Source: §3 · pp. 13–14
  • On clean examples, F-SSDRL beats PL and DRL in almost all settings and VAT on SVHN, while trailing VAT slightly on MNIST and CIFAR-10.Table 2 reports test error rates across the three datasets.Source: Table 2 · p. 13, §3 · p. 14
  • Across attacks, SSDRL and F-SSDRL are among the methods with the smallest adversarial losses, supporting robustness certificates via Theorem 3; VAT has no theoretical guarantees.The comparisons include average adversarial loss and PGM losses at varying attack strengths.Source: Figure 4 · p. 14, Figure 5 · p. 14, §3 · p. 15

4 Conclusions

The paper extends distributionally robust learning to partially labeled data through a self-learning framework, with convergence and generalization guarantees. Its analysis introduces new complexity measures, and benchmark experiments show comparable-to-superior performance against state-of-the-art methods.

4 Conclusions

  • SSDRL extends supervised distributionally robust learning to partially labeled data and encompasses Pseudo-Labeling and EM as special cases.Its computational complexity is only slightly higher than that of its supervised counterparts.Source: §4 · p. 15
  • The paper derives convergence and generalization guarantees, including an adversarial extension of Rademacher complexity bounded for broad learning frameworks with finite VC-dimension.Source: §4 · p. 15
  • Minimum Supervision Ratio (MSR) quantifies the role of unlabeled data in generalization under less restrictive conditions than the cluster assumption used by many existing works.Source: §4 · p. 15
  • Real-world benchmark simulations show comparable-to-superior performance against state-of-the-art methods.Future directions include empirical estimation of MSR functions and fitting a broader range of SSL methods into the framework.Source: §4 · p. 15

A Additional Simulations and Experimental Settings

This appendix section presents additional experiments, further comparisons with rival methods, and a description of the simulation settings.

A Additional Simulations and Experimental Settings

A.1 Additional Simulations

The additional simulations examine adversarial and clean-example error rates, including parameter variation and a PGM attack comparison. The reported text describes parameter stability and dataset-specific clean-example results.

A.1 Additional Simulations

  • Across additional hyperparameter variations, DRL, SSDRL, and VAT show no significant performance sensitivity to slight parameter changes, indicating stability up to certain levels.Figure A.1 covers three benchmark datasets and Figure A.2 replaces the attack strategy with PGM, plotting error rates against attack strength.Source: §A.1 · p. 18
  • On clean examples, SSDRL or F-SSDRL overfits on MNIST for a particular parameter range and performs worse than DRL, but outperforms DRL on SVHN and CIFAR-10.SSDRL and VAT have comparable clean-example performance on SVHN and CIFAR-10.Source: §A.1 · p. 18
  • Figure A.1 compares test error rates for SSDRL, DRL, PL, and VAT on adversarial examples generated via [9] across different datasets, with λ set to −1.Source: Figure A.1 · p. 19
  • Figure A.2 compares test error rates on adversarial examples generated by Projected-Gradient Method (PGM) [34] under an ℓ2 norm constraint.Source: Figure A.2 · p. 19

A.2 Experimental Settings

The section describes the experimental settings used in Section 3, noting that most SVHN and CIFAR-10 settings follow a procedure described in.

A.2 Experimental Settings

  • The appendix gives a detailed description of the experimental settings used for Section 3.Source: §A.2 · p. 19
  • Most settings for the SVHN and CIFAR-10 datasets follow the procedure described in.Source: §A.2 · p. 19
  • The stated connection to applies to the majority, rather than necessarily all, settings for those datasets.Source: §A.2 · p. 19

A.2.1 Real-world Datasets

The experiments use MNIST, SVHN, and CIFAR-10, with dataset-specific sample counts and preprocessing. The appendix figures report clean-example test error rates for distributionally robust methods and VAT.

A.2.1 Real-world Datasets

  • Experiments use MNIST handwritten digits, SVHN street-view house numbers, and CIFAR-10 categorized objects.CIFAR-10 is preprocessed with Zero-phase Component Analysis (ZCA).Source: §A.2.1 · pp. 19–20
  • Figures A.3 and A.4 plot clean-example test error rates for distributionally robust methods and VAT, respectively, showing means and standard deviations across random seeds.Source: Figure A.3 · p. 20, Figure A.4 · p. 20
  • MNIST has 60, 000 training/10, 000 test examples; SVHN 73, 257/26, 032; CIFAR-10 50, 000/10, 000.The datasets comprise 28×28 grayscale MNIST images and 32 × 32 × 3 RGB images for SVHN and CIFAR-10.Source: §A.2.1 · p. 20

A.2.2 Supervision Ratio and Training Data-points

The experiments use small labeled subsets and treat remaining training samples as unlabeled, repeating data selection three times. They also specify training settings, the transportation cost choice, and an optimism parameter.

A.2.2 Supervision Ratio and Training Data-points

  • Labeled subsets contain 1, 000 examples for MNIST and SVHN and 4, 000 for CIFAR-10; remaining training samples are unlabeled.Data-point selections are repeated three times on each dataset.Source: §A.2.2 · p. 20
  • Training uses ADAM at an initial learning rate of 0.001, with 50, 000 updates for MNIST and 48, 000 for SVHN and CIFAR-10.The learning rate is linearly decayed over the final 10, 000 MNIST updates and final 16, 000 updates for SVHN and CIFAR-10.Source: §A.2.2 · p. 21
  • The transportation cost follows for simplicity, although any valid lower semi-continuous function is permitted; λ is set to −1 to encourage optimism and soft pseudo-labeling.λ is otherwise set to −1 except when stated otherwise.Source: §A.2.2 · p. 21

A.2.3 Creating Adversarial Examples

Adversarial examples are generated through gradient ascent for the inner maximization and projected-gradient updates. The update counts and step settings differ between training and evaluation.

A.2.3 Creating Adversarial Examples

  • For each (X, y), gradient ascent updates X to maximize the loss minus γ times transportation cost in the inner maximization.The update starts at X and uses ascent rate κ/[γ(t+1)].Source: §A.2.3 · p. 21
  • The inner-maximization update is repeated 5 times during DRL and SSDRL training and 15 times during evaluation.κ is 1.0 for MNIST and CIFAR-10 and 0.5 for SVHN.Source: §A.2.3 · p. 21
  • Projected-gradient adversarial examples are constrained to an ℓ2 ε-ball around X, with normalized update directions and T = 15 iterations.The step-length parameter is ξ = ε/log(T).Source: §A.2.3 · p. 21

A.2.4 Architecture of Deep Neural Networks

The experiments use convolutional neural networks, with activation choices varying by dataset. The SVHN and CIFAR-10 structures differ from MNIST, and normalization is applied with a stated exception.

A.2.4 Architecture of Deep Neural Networks

  • The loss class consists of CNNs; MNIST uses ELU, while SVHN and CIFAR-10 use leakyReLU (lReLU).The CNN models are listed in Table 3.Source: §A.2.4 · p. 21, Table 3
  • SVHN and CIFAR-10 use structures different from MNIST, with specifications inspired by.Table 3 presents the CNN models used in the experiments.Source: §A.2.4 · p. 22, Table 3
  • For SVHN and CIFAR-10, convolutional and dense layers are followed by batch normalization except for CIFAR-10’s dense layer; lReLU slopes are 0.1.Source: §A.2.4 · p. 22

B Minimum Supervision Ratio: Definition and Implications

This section asks when unlabeled data can contribute to bounding true adversarial risk, and develops a compatibility condition linking the hypothesis set, data distribution, supervision ratio, and pessimism parameter. Under that condition, the proposed risk has a minimizer near the true-risk minimizer and upper-bounds true expected loss in that neighborhood.

B Minimum Supervision Ratio: Definition and Implications

  • Choosing smaller λ can reduce empirical semi-supervised adversarial risk, while λ = +∞ always ensures the non-negativity condition used to upper-bound true risk.The section frames this as a trade-off between lower empirical risk and sufficient pessimism for a valid true-risk bound.Source: B Minimum Supervision Ratio:… · pp. 23–24
  • MSR(Φ,P0) measures compatibility between the hypothesis set and data distribution and is a central ingredient in the conditions for generalization bounds.The section introduces it to identify when unlabeled data can help under the paper's semi-supervised, distributionally robust setting.Source: B Minimum Supervision Ratio:… · pp. 22–25
  • The theory also covers finite or negative λ when the minimizer lies in a subset where ρλ remains non-negative, allowing lower empirical loss and an improved generalization bound.Without that subset condition, minimizing the semi-supervised empirical risk need not upper-bound true risk.Source: B Minimum Supervision Ratio:… · pp. 24–25
  • The condition η ≥ MSR(Φ,P0)(λ, ζ) supplies the supervision requirement used to obtain the theorem's risk guarantees.MSR increases with ζ and decreases with λ; for every Φ and P0, some λ and ζ give MSR equal to zero.Source: B Minimum Supervision Ratio:… · pp. 25–26
  • With suitable supervision and compatibility conditions, the proposed risk has a minimizer near the true adversarial-risk minimizer and upper-bounds true expected loss throughout that neighborhood.The upper bound requires at least a minimum level of pessimism, λ ≥ Λ(ψ), over the relevant neighborhood.Source: B Minimum Supervision Ratio:… · p. 27

C Auxiliary Theorems and Proofs

This appendix develops proof tools and guarantees for the semi-supervised adversarial-risk framework, relating its expected complexity to classical Rademacher complexity. It also establishes duality and convexity conditions, uniform convergence, empirical-to-expected convergence, and a local true-risk guarantee for RSSAR.

Proof of Theorem 1

  • The proof of Theorem 1 uses a dual form to facilitate maximization over the ambiguity set, and notes that γ can generally be tuned like ϵ by cross-validation.The dual formulation is introduced under continuity and lower-semicontinuity assumptions on the loss and transportation cost.Source: C Auxiliary Theorems and Proofs · pp. 28–29

Proof of Theorem 2

  • Under smoothness and bounded-gradient assumptions, auxiliary lemmas establish Lipschitz properties for adversarial loss gradients and the softmin operator, and bound discrepancy from a δ-approximate inner maximizer.The adversarial-loss gradient result requires γ > Lzz.Source: C Auxiliary Theorems and Proofs · p. 30
  • Theorem 2’s proof analyzes stochastic-gradient updates by modeling each draw as labeled or unlabeled, then taking expectation over sampling and SGD randomness.The sampling probabilities are nl/n and nul/n for labeled and unlabeled observations, respectively.Source: C Auxiliary Theorems and Proofs · p. 31

Theorem C.1

  • For λ = ±∞, Algorithm 1 converges to a local minimizer with suitable step sizes and approximation intervals, while the λ = −∞ argument ensures the objective never increases.The convergence-rate analysis is out of scope; a trivial worst-case iteration bound grows exponentially with the number of unlabeled samples, and the self-training convergence rate remains open.Source: C Auxiliary Theorems and Proofs · pp. 31, 33

Theorem C.2

  • The optimization programs in (5) and (7) are convex when the loss is twice differentiable and strictly convex in θ and λ satisfies the stated condition.The softmin condition holds when λ is nonnegative or when its negative-curvature bound is smaller than the positive lower bound.Source: C Auxiliary Theorems and Proofs · pp. 33–34

Proof of Theorem 3

  • Theorem 3’s proof bounds the adversarial loss and applies McDiarmid’s inequality to obtain a uniform upper bound over θ with probability at least 1 − δ.The argument considers partially observed datasets differing in one data point.Source: C Auxiliary Theorems and Proofs · p. 35

C Auxiliary Theorems and Proofs

  • The non-data-random term EP0{J(D)} depends on the hypothesis set’s adversarial counterpart and P0, and plays the role of classical Rademacher complexity.The proof also introduces a function formulation to express this term more intuitively.Source: C Auxiliary Theorems and Proofs · p. 35
  • Lemma C.6 bounds the softmin-related Rademacher complexity using the component function-set complexities, extending the bound across d sets.Its proof uses a 1-Lipschitz function and Rademacher-complexity contraction and sum inequalities.Source: C Auxiliary Theorems and Proofs · pp. 36–37
  • With probability at least 1 − δ, empirical RSSAR is close to its expected value uniformly over θ, and the two converge asymptotically.The bound uses ε ≥ 0 as the dual counterpart of γ in (7).Source: C Auxiliary Theorems and Proofs · p. 38
  • Under the condition η ≥ MSR(Φ, P0)(λ, ζ), the empirical RSSAR minimizer lies near a minimizer of expected adversarial risk, whose expected value upper-bounds true risk.The proof establishes a gap outside a neighborhood of the true minimizer and combines this with the local bound.Source: C Auxiliary Theorems and Proofs · p. 38

D Auxiliary Lemmas and Proofs

These auxiliary proofs establish complexity bounds under distribution-independent assumptions and derive smoothness for the classifier gradient. They also connect the semi-supervised Rademacher complexity bound to a finite-label factor.

D Auxiliary Lemmas and Proofs

  • The softmin formulation expresses ∇θf through β_y(θ)-weighted gradients of φγ, with the weights summing to one over labels.The proof uses this formulation to derive inequalities for the gradient’s smoothness.Source: D Auxiliary Lemmas and Proofs · pp. 38–39
  • The proof derives a safe smoothness choice of ω = 2σ |λ|, yielding a Lipschitz bound for ∇θf.The derivation uses the Lipschitz constant of β_y(θ) and assumes ∥∇θφγ(X, y; θ)∥* ≤ σ.Source: D Auxiliary Lemmas and Proofs · p. 39
  • The semi-supervised complexity bound satisfies gul(n) ≤ |Y| ∆(n) under the stated distribution-independent Rademacher-complexity bound.The proof states this holds for any distribution P0, ϵ ≥ 0, and η ∈ [0, 1].Source: D Auxiliary Lemmas and Proofs · p. 40
  • For 0-1 loss and a finite-VC-dimension classifier class, Dudley’s entropy bound and Haussler’s upper bound provide a distribution-independent Rademacher-complexity bound.The passage states that a constant C exists for this upper bound.Source: D Auxiliary Lemmas and Proofs · pp. 40–41
  • The appendix states that the preceding argument also proves the SSM Rademacher-complexity claim from Section 2.3..Source: D Auxiliary Lemmas and Proofs · p. 41
Loading 1905.13021v1…