PaperlayerView exact revision on arXiv

Source-linked AI summary

VC Classes are Adversarially Robustly Learnable, but Only Improperly

Omar Montasser, Steve Hanneke, Nathan Srebro

arXiv:1902.04217v2cs.LGstat.ML

TL;DR

The paper asks whether finite-VC classes can be learned to produce adversarially robust predictors from non-adversarial i.i.d. data. It develops improper learning rules and proves that every finite-VC class is robustly PAC learnable, while some such classes admit no proper robust learner. The paper also identifies open questions about optimal sample complexity and a complexity measure characterizing robust learnability.

  • Problem

    The paper studies whether finite-VC hypothesis classes are adversarially robustly PAC learnable and whether proper learning rules suffice.

  • Method

    The paper uses sample-compression-based improper learning rules that enforce zero empirical robust loss and leverage dual-space discretization of adversarial examples.

  • Results

    Every finite-VC hypothesis class is robustly PAC learnable with an improper rule, whereas some finite-VC classes cannot be robustly PAC learned by any proper rule.

  • Takeaways & Limitations

    Robust generalization may require departing from robust empirical risk minimization and considering improper methods such as bagging or ensembles.

  • Takeaways & Limitations

    The optimal robust-learning sample complexity remains unresolved, including whether exponential dependence on vc(H) can be improved to linear dependence.

Abstract

from arXiv · show

We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{H}$ with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are not robustly PAC learnable with any proper learning rule.

1. Introduction

The paper studies robust prediction from i.i.d. data and contrasts proper learners restricted to H with improper learners. It shows finite VC dimension guarantees improper robust PAC learnability, while proper learning can fail and prior uniform-convergence approaches may be insufficient.

  • Problem motivation: The target is low population robust risk after i.i.d. training, not robustness of the training process to an adversarial sample.Robust risk evaluates adversarial perturbations at test time, whereas the observed sample remains non-adversarial.
  • Problem setup: The adversary maps each input x to a nonempty set U(x) of test-time perturbations, including metric-bounded perturbations such as ℓ∞ balls.The common computational formulation minimizes empirical robust risk over a hypothesis class, while the true objective is population robust risk.
  • Problem motivation: Uniform-convergence analyses of robust risk justify proper empirical minimization, but robust and empirical robust errors can have a large generalization gap.This motivates studying learning rules beyond proper empirical risk minimization.
  • Main results: Some finite-VC hypothesis classes cannot be robustly PAC learned by any proper rule, including robust empirical risk minimization.The impossibility can occur even when the class has VC dimension one.
  • Main results: Finite VC dimension guarantees robust PAC learnability with an improper learning rule for every adversary, although sample complexity can sometimes be exponential in VC dimension.The result applies to arbitrary adversaries and does not require the output predictor to lie in H.
  • Relation to prior work: The paper contrasts its approach with prior robust-generalization work based on uniform convergence and notes improved dependence on the number of finite perturbations in a related setting.For finite |U(x)|≤k, the stated approach scales roughly logarithmically with k rather than roughly linearly.

2. Problem Setup

Robust PAC learning seeks a distribution-independent rule whose population robust risk competes with the best hypothesis in H, in realizable and agnostic settings. Unlike standard PAC learning, finite VC dimension alone does not ensure proper robust learnability, while improper rules can succeed.

  • Learning objective: Robust PAC learning requires a rule that, from i.i.d. samples, competes with the best h*∈H in population robust risk using distribution-independent sample complexity.The framework includes both realizable and agnostic settings.
  • Learning settings: In the realizable setting, the distribution admits an h*∈H with zero robust risk; in the agnostic setting, the rule competes with the best robust-risk hypothesis in H.The two definitions differ in whether zero robust risk is assumed or approximation to the best class member is required.
  • Learning rules: Proper learning restricts the output to H, whereas improper learning permits any predictor in Y^X.This distinction is central because robust learnability may require leaving the original hypothesis class.
  • Technical assumptions: The formal setup assumes measurability conditions for hypotheses and robust losses so that standard VC-theoretic tools apply.These are stated as implicit technical restrictions rather than the paper’s main learning condition.
  • Robust versus standard learning: When U(x)={x}, robust learnability reduces to standard supervised learning, but stronger adversaries need not correspond to supervised learning over a modified class or loss.Robust learning is framed as a form of general learning rather than ordinary ERM on a transformed hypothesis class.
  • Complexity measures: Finite VC dimension is sufficient for improper robust learning, but the robust loss class can have arbitrarily larger VC dimension than H.Thus, uniform convergence of the robust loss class is not a necessary route to learnability.

3. Sometimes There are no Proper Robust Learners

Finite VC dimension does not guarantee adversarially robust PAC learnability with proper rules, even when the class has VC dimension 1. The construction creates classes with robust loss complexity far larger than ordinary VC complexity, yielding persistent proper-learning failure.

  • 3. Sometimes There are no Proper Robust Learners: Theorem 1 constructs a finite-VC class and adversary for which proper robust PAC learning is impossible in the realizable setting.The resulting class has vc(H) ≤ 1.
  • 3. Sometimes There are no Proper Robust Learners: The construction keeps ordinary VC dimension at most 1 while allowing the robust loss class to shatter arbitrarily many points.Perturbation sets are chosen mutually disjoint, and hypotheses share labels on the original points while encoding distinct signatures inside perturbation sets.
  • 3. Sometimes There are no Proper Robust Learners: The hypotheses cannot shatter two points because their construction permits only restricted labelings across signature sets and perturbation regions.This establishes vc(H) ≤ 1 for the constructed classes.
  • 3. Sometimes There are no Proper Robust Learners: Even with vc(H) = 1, a hypothesis class can contain a zero-robust-risk predictor while every proper learner incurs robust risk greater than 1/8 with probability at least 1/7.This holds for any prescribed sample size m, so proper robust learning can require infinitely many samples.
  • 3. Sometimes There are no Proper Robust Learners: For any sample size m, a proper learner can be forced to select a hypothesis from the wrong class, whose classifiers make mistakes on the target distribution’s points.The construction uses separate classes H_m and adjusts their predictions so hypotheses from H_m′, with m′ ≠ m, are non-robust on X_m.

4. Finite VC Dimension is Sufficient for (Improper) Robust Learnability

Finite VC dimension guarantees adversarially robust PAC learnability through an improper learner, using compression and boosting ideas. The proof obtains bounds involving the primal and dual VC dimensions, while proper learning can require substantially worse dependence on adversary complexity.

  • Main result: Finite VC dimension is sufficient for robust learnability, but the learner may need to leave H and output an improper predictor.The result establishes robust learnability for both realizable and agnostic settings via a reduction from agnostic to realizable learning.
  • Proof strategy: Sample compression, discretization of inflated perturbation data, and boosting construct a majority vote with zero empirical robust error.The construction uses classifiers RERM_H(L) trained on subsets of size n=O(vc(H)), then combines them through boosting and sparsification.
  • Sample complexity: The compression analysis yields a bound based on vc(H) and vc*(H), with vc*(H)<2vc(H)+1.The proof first controls the discretized perturbation set using the dual VC dimension and then applies robust compression generalization guarantees.
  • Adversary dependence: For bounded perturbation sets, the approach reduces dependence on adversary size k from k log(k) to log(k)(log log(k))^3.The improvement relies on improper learning, while the paper leaves open whether proper rules can attain polylogarithmic dependence on k.

5. Necessary and Sufficient conditions for Robust Learnability

The paper separates sufficient and necessary complexity measures for robust learnability. Finite VC dimension is sufficient, while robust shattering dimension is necessary, but a tight characterization remains unknown.

  • Non-necessity of VC dimension: VC dimension is not necessary for robust learnability, since an infinite-VC class under an all-powerful adversary can be learned from one example.In that construction, only the all-positive and all-negative predictors minimize population robust risk.
  • Limits of robust shattering: The standard robust shattering dimension dim_U×(H) is not sufficient: some classes have dim_U×(H)=0 but infinite robust sample complexity.Thus, even the absence of fully shattered perturbation sets does not guarantee robust learnability.
  • Robust shattering dimension: U-robust shattering allows labels to select separate representatives whose perturbation regions must be classified consistently.The robust shattering dimension dim_U(H) is the largest number of points satisfying this condition.
  • Characterization: Finite VC dimension is sufficient, whereas robust shattering dimension provides a lower bound on robust sample complexity.The paper establishes the comparison for arbitrary adversaries and hypothesis classes.
  • Open question: Whether robust shattering dimension is sufficient, and whether the remaining gap can be large, remains an open question.The paper therefore does not provide a necessary-and-sufficient complexity characterization.

6. Discussion and Future Directions

The paper argues that improper learning should be considered for adversarially robust learning, while identifying unresolved questions about sample complexity, computation, and multiclass extensions.

  • Discussion and Future Directions: The results suggest considering improper learning rules, including bagging or other ensembles, instead of relying exclusively on robust ERM and M-estimation.The paper notes that its improper rule may not be practical, but presents this direction as a consequence of the proper-versus-improper gap.
  • Discussion and Future Directions: The optimal sample complexity remains unresolved, including whether the exponential dependence on vc(H) can be reduced to linear dependence.The paper connects this question to possible improvements in the learning rule, its analysis, or VC compression schemes.
  • Discussion and Future Directions: Efficient robust learning remains open because the paper ignores computational considerations and its rule may require many oracle calls and substantial time and space.The paper asks whether efficient PAC learnability implies efficient robust PAC learnability.
  • Discussion and Future Directions: The results extend to multiclass settings by replacing VC dimension with graph dimension in the upper bounds.The lower-bound argument also extends using a multiclass analogue of robust shattering dimension, while a corresponding upper bound remains open.

Appendix A. Auxilliary Proofs Related to Proper Robust Learnability

The appendix proves that proper robust learning can fail for finite-VC classes by constructing distributions that force any proper learner to miss many robustly relevant points.

  • Lower-bound construction: The adversarial distributions are supported on 2m points, while the learner observes only m samples and therefore cannot identify which unseen points belong to the support.For every such distribution, the class contains a classifier with zero robust risk.
  • Lower-bound argument: A probabilistic-method argument averages over a family of distributions and shows that some distribution yields expected robust loss at least 1/4.The proof then converts this expectation into a nontrivial failure probability using a variant of Markov’s inequality.
  • Lower-bound construction: Any proper learner is forced to choose a classifier that is not robustly correct on at least m points of a 3m-point shattered set.The constructed class retains classifiers robustly correct only on subsets of size 2m.

Appendix B. Auxilliary Proofs Related to Realizable Robust Learnability

The appendix extends sample-compression generalization guarantees from ordinary 0-1 loss to robust loss, using a union bound over compressed subsequences.

  • Compression-based guarantee: Robust-loss generalization holds for predictors specified by a fixed function of k sample points when their empirical robust risk is zero.The guarantee applies with high probability over an i.i.d. sample.
  • Proof: The argument is essentially the classical sample-compression proof because the same reasoning remains valid under robust loss.The appendix notes that analogous extensions can apply to other compression-based guarantees.
  • Proof: The proof counts all m^k choices of compression indices and applies a union bound to control the probability of zero empirical but high population robust risk.The resulting bound uses m^k(1 − ε)^(m−k) ≤ m^k e^(−ε(m−k)).

Appendix C. Proof of Agnostic Robust Learnability

The agnostic robust-learning proof constructs a zero-empirical-robust-loss predictor by combining weak robust classifiers through boosting and then applies compression-based uniform convergence.

  • Agnostic robust learning: The proof uses robust ERM to find a maximal subsequence with zero empirical robust loss, then constructs weak robust classifiers from compressed samples.Each weak classifier is obtained from an MRE-sized tuple selected from the subsequence.
  • Boosting construction: Robust α-Boost updates distributions over the subsequence and combines the weak classifiers until the final predictor has zero empirical robust risk.The construction sets α = 1/8 and runs T = 1 + 48 ln(|S′|) rounds.
  • Compression representation: The resulting predictor is specified by an ordered sequence of MRE·T sample points, enabling compression-based generalization analysis.This representation allows the robust-loss analogue of compression guarantees to be applied.
  • Generalization bound: The realizable-case and agnostic-case bounds combine concentration and union bounds to obtain the required robust-risk guarantee for sufficiently large samples.The proof uses Hoeffding’s inequality, a union bound, and T_m = O(log(m)).

Appendix D. Auxilliary Proofs Related to Necessary Conditions for Robust Learnability

The appendix constructs hypothesis classes whose ordinary robust shattering behavior yields necessary conditions for robust learnability. It proves lower bounds for arbitrary learning rules and exhibits finite U×-dimension alongside infinite U-robust shattering dimension.

  • Construction: The construction defines classifiers on disjoint γ-ball pairs so that only same-index intersections can realize differing labels, while all other regions behave identically.For each bit string, the classifier is specified on the γ-balls around paired points and labels the remaining space +1.
  • Necessary condition: The resulting class has dimU×(H) = 0 but dimU(H) = ∞, and therefore MRE(ε, δ; H, U) = ∞.The zero U× dimension follows because no single γ-ball receives both labels, whereas the intersection points u1, u2, ... are shattered.
  • Realizable lower bound: For any learning rule, the realizable construction chooses a distribution concentrated mostly on one index and uses unseen labels on other indices to force robust error.The proof conditions on sample sequences containing few indices from {2, ..., d}, then applies expectation and probability bounds to obtain the lower bound.
  • Realizable lower bound: With m ≤ (1/(2ε)) ln(1/δ), the construction yields robust error at least ε/2 with probability at least 1/2 in the complementary argument.The learner can observe only examples from one label configuration, causing a mistake at an intersection shared by differently labeled perturbation regions.
  • Agnostic extension: The agnostic extension assigns distributions according to bit strings, with probabilities (1−α)/(2d) or (1+α)/(2d) depending on each bit.The parameter α is selected as a function of ε and δ, following a standard agnostic-learning argument.
Loading 1902.04217v2…