PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Methods Provably Converge to Non-Robust Networks

Gal Vardi, Gilad Yehudai, Ohad Shamir

arXiv:2202.04347v2cs.LG

TL;DR

Why gradient methods learn non-robust networks despite the existence of robust classifiers remains unclear. This paper analyzes gradient flow for depth-2 ReLU networks and links its implicit bias to max-margin KKT points. It proves that such trained networks can be non-robust on the training set, even when robust classifiers exist.

  • Problem

    Why gradient methods learn non-robust networks remains unclear, including in cases where robust classifiers exist.

    Source: §1 · p. 1

  • Method

    The paper uses implicit-bias results for gradient flow to show that, under its dataset assumptions, every network satisfying the max-margin problem’s KKT conditions is non-robust.

    Source: §1 · p. 2

  • Results

    Gradient flow with logistic or exponential loss is biased toward non-robust depth-2 ReLU networks even when robust networks correctly classify the training set.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors argue that implicit bias may help explain adversarial examples and that its relationship to robustness merits further study.

    Source: §7 · p. 12

    The result establishes non-robustness on the training dataset, not on test data; extending the approach to test-data robustness is left for future research.

    Source: §7 · pp. 12–13

Abstract

from arXiv · show

Despite a great deal of research, it is still unclear why neural networks are so susceptible to adversarial examples. In this work, we identify natural settings where depth-$2$ ReLU networks trained with gradient flow are provably non-robust (susceptible to small adversarial $\ell_2$-perturbations), even when robust networks that classify the training dataset correctly exist. Perhaps surprisingly, we show that the well-known implicit bias towards margin maximization induces bias towards non-robust networks, by proving that every network which satisfies the KKT conditions of the max-margin problem is non-robust.

1 Introduction

The paper studies why gradient methods produce non-robust trained networks even when robust classifiers exist, and proves this behavior for depth-2 ReLU networks trained with logistic or exponential loss. It connects the result to implicit bias and reports empirical evidence beyond the dataset-size scope of the theory.

1 Introduction

  • Gradient flow with logistic or exponential loss is biased toward non-robust depth-2 ReLU networks even when robust networks correctly classify the training set.The result applies to networks of any width and uses the non-robustness of networks satisfying the max-margin problem's KKT conditions.Source: §1 · p. 2
  • A robust depth-2 ReLU network can classify the same training data, while gradient flow converges to networks that admit smaller label-flipping perturbations.The paper contrasts the perturbation scales for robust and gradient-flow solutions; the supplied passages do not preserve the scale expressions clearly.Source: §1 · p. 2
  • For m = Θ(d) examples whose maximum pairwise absolute inner product is O(1), the trained network has adversarial perturbations of size O(1) for each example in the dataset.Source: §1 · p. 2
  • The initial negative result is limited by an upper bound on dataset size; an extension instead bounds the number of examples attaining the trained network’s exact margin.The extension is intended to cover datasets that may be arbitrarily large.Source: §1 · p. 2
  • Empirically, the paper reports that the theoretical small perturbation flips almost all dataset labels even when the dataset exceeds the input dimension, and that changing network width does not change its size.The empirical study addresses two limits or scope questions raised by the theoretical result.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the depth-2 ReLU setting, robustness, and gradient-flow training, then state the implicit-bias result used in the paper: under specified conditions, gradient flow converges in direction to a KKT point of a parameter-space max-margin problem.

2 Preliminaries

  • The notation defines the Euclidean norm, indicator and sign functions, the index set [d], uniform distributions U(A), and asymptotic bounds O(·) and ˜O(·).The parameter vector is also treated as a concatenation of network parameters with its ℓ2 norm.Source: §2 · p. 3
  • The paper studies depth-2 ReLU networks, which it identifies as homogeneous with degree 2, and uses exponential and logistic losses.The network uses the ReLU activation σ(z) = max{0, z}; gradient flow is presented as the infinitesimal-step-size analogue of gradient descent.Source: §2 · pp. 3–4
  • Robustness here concerns preserving each training input’s predicted sign under sufficiently small ℓ2 perturbations.The definition is stated relative to the training inputs and a robustness scale R(d).Source: §2 · p. 3
  • For homogeneous ReLU networks trained with exponential or logistic loss, gradient flow that reaches a correctly classified dataset converges in direction to a KKT point of a parameter-space max-margin problem.The theorem also states that the loss tends to zero and the parameter norm tends to infinity; a KKT point need not be a global or local optimum.Source: §2 · p. 4

3 Robust networks exist

This section proves that sufficiently low pairwise correlations permit a correctly classifying robust depth-2 ReLU network. Its construction activates a neuron for each example, and the stated correlation condition holds with high probability for certain random sphere datasets.

3 Robust networks exist

  • The construction uses neurons arranged so each is active for exactly one training example, limiting the gradient contribution at that example.The passage attributes the sufficiently small gradient to weight vectors that are not too large.Source: §3 · p. 4
  • For |⟨xi,xj⟩| ≤ c·d, with constant 0 < c < 1 independent of d and width k ≥ m, a depth-2 ReLU network achieves yiN(xi) ≥ 1 on every example; flipping any output requires perturbation larger than 1−c.Source: §3 · p. 4
  • For i.i.d. inputs sampled uniformly from the sphere with m ≤ d^k, the cited lemma gives high-probability bounds on all pairwise inner products, including a bound proportional to log(d)√d.The theorem’s correlation condition therefore holds with high probability in the stated random-data setting.Source: §3 · p. 5

4 Gradient flow converges to non-robust networks

Under the theorem’s stated conditions, every KKT depth-2 ReLU network admits a perturbation that flips margin examples; consequently, gradient flow reaching zero loss converges to non-robust networks even when robust classifiers exist.

4 Gradient flow converges to non-robust networks

  • Theorem 4.1 gives a shared vector z that flips the outputs of all margin examples in a KKT network: positive examples at xi − z and negative examples at xi + z.The theorem’s conditions include a bound on dataset size relative to pairwise inner products; the perturbation size is bounded in terms of the theorem’s parameters.Source: §4 · pp. 5, 7
  • When m = Θ(d) and pairwise inner products are O(1), the perturbation has size O(1), making the trained solutions highly non-robust.The example describes the data points as almost orthogonal and says the perturbation can flip outputs for all examples.Source: §4 · p. 5
  • If gradient flow reaches zero loss, it converges in direction to a KKT point regardless of initialization, so Theorem 4.1 implies non-robustness.The result is stated to require neither a width assumption nor a particular initialization.Source: §4 · p. 6
  • The perturbation depends only on the dataset, applying across depth-2 networks reached by gradient flow and corresponding to universal, transferable adversarial perturbations.The paper relates the shared perturbation to universal perturbations [Moosavi-Dezfooli et al. 2017, Zhang et al. 2021] and transferability [Liu et al. 2016, Akhtar and Mian 2018].Source: §4 · p. 6
  • The corollary permits arbitrarily large datasets when the subset attaining exactly the margin is bounded and satisfies the technical assumptions.For the original theorem, the assumptions constrain dataset size and exclude clusters or points with norms different from the specified scale; the spherical-input assumption is described as mostly technical.Source: §4 · p. 6

5 Proof sketch of Theorem 4.1

The proof sketch illustrates how margin maximization can yield less robust networks, then constructs a perturbation using KKT conditions: examples attain margin 1, positive-neuron contributions do not increase, and negative-neuron contributions decrease.

5 Proof sketch of Theorem 4.1

  • The proof sketch presents these component arguments as the route to establishing Theorem 4.1.The formal proof is in Appendix C.Source: §5 · p. 7

5.1 A simple example

  • A margin-maximizing network in the example is less robust than a correctly classifying network, because a perturbation can affect multiple neurons’ contributions.The example contrasts the margin-maximizing network’s robustness with a network requiring perturbations of size d/2.Source: §5.1 · p. 7

5.2 Proof overview

  • The proof overview chooses z along a signed sum of training inputs and shows that moving each margin example by the appropriate sign makes the network output cross the classification threshold.For positive examples the movement is xi − z; the negative-example case is described as analogous.Source: §5.2 · p. 8

5.4 The contribution of the neurons J+ to the output does not increase

  • For positive examples, moving by −z ensures that the nonnegative contribution from neurons in J+ does not increase.The proof combines this bound with the decrease in the contribution from J−.Source: §5.2 · p. 8, §5.4 · p. 9

5.3 The examples in the dataset attain margin 1

  • All training examples must attain margin 1: assuming one exceeds it leads, through the KKT relations, to a contradiction.The argument uses a lower bound on a coefficient sum to infer that another example has margin strictly above 1, contradicting the bound.Source: §5.3 · pp. 8–9

5.5 The contribution of the neurons J−to the output decreases

  • For J−, the perturbation is split into two stages: first raise neuron inputs to at least zero, then increase their outputs enough to lower the network output.A lower bound on the relevant coefficient sum allows the second-stage choice to produce a decrease of at least 2.Source: §5.5 · pp. 9–10

6 Experiments

The experiments test whether the theoretical non-robustness result extends to larger datasets and different network widths. On synthetic uniform-sphere data, a shared perturbation flips almost all margin samples, and changing network width has little effect on the minimum perturbation size.

6 Experiments

  • Experiments train depth-2 fully connected ReLU networks on synthetic data with exponential loss, using SGD with batch size 5,000 and five random seeds.Inputs are sampled uniformly from a sphere, and the reported results average across seeds.Source: §6 · p. 10

6.1 Results

  • At least 92% of samples lie on the margin for m = d^α with α = 0.8, 1, 1.2, or 1.5, and a single small perturbation flips almost all samples.The experiments use uniformly distributed inputs; the perturbation is tested on the margin samples.Source: §6.1 · pp. 11–12, Figure 1 · p. 11
  • The minimal perturbation size is almost unchanged across network widths from 100 to 8000 when m = d.This empirical result matches the width-independent prediction of Theorem 4.1 for datasets larger than the theory’s bound.Source: Figure 1 · p. 11, §6.1 · p. 12

7 Discussion

The discussion presents implicit bias as a useful tool for studying robustness and argues that depth-2 ReLU gradient flow favors non-robust solutions even when robust solutions exist. The theoretical results are limited to training-data robustness and rely on a dataset-size or margin-attainer bound; extending them to test data and other settings remains open.

7 Discussion

  • Gradient flow in depth-2 ReLU networks is biased toward non-robust solutions even when robust solutions exist.The authors use prior implicit-bias results for homogeneous models with exponentially tailed losses and suggest studying its implications for robustness.Source: §7 · p. 12
  • The results establish non-robustness on the training dataset, not on test data.The authors note that training-set robustness should be easier to achieve than test-data robustness and identify the latter as future work.Source: §7 · pp. 12–13
  • The negative results assume an upper bound on dataset size or on the subset of examples attaining the margin, an assumption required by the proof for technical reasons.The authors conjecture that this assumption can be relaxed and say their experiments support that conjecture.Source: §7 · p. 13
  • The authors identify deeper ReLU architectures and optimization methods with different implicit biases as open directions.They ask whether other methods might direct training toward robust networks.Source: §7 · p. 13

A Preliminaries on the KKT conditions

The preliminaries introduce KKT conditions for locally Lipschitz constrained optimization using the Clarke subdifferential. They define feasibility and characterize a KKT point through nonnegative multipliers.

A Preliminaries on the KKT conditions

  • For continuously differentiable functions, the Clarke subdifferential reduces to the gradient, while the chain rule holds as an inclusion.The section cites Clarke et al. [2008] for the subdifferential and Lyu and Li [2019] and Dutta et al. [2013] for the KKT review.Source: A Preliminaries on the KKT conditions · p. 15
  • The section introduces KKT conditions for a constrained optimization problem with locally Lipschitz objective and constraint functions.It defines a feasible point as one satisfying all constraints.Source: A Preliminaries on the KKT conditions · pp. 15–16
  • A feasible point is a KKT point when there exist nonnegative multipliers satisfying the stated KKT condition.The displayed condition itself is not included in the supplied passage.Source: A Preliminaries on the KKT conditions · p. 16

B Proof of Lemma 3.1

The proof uses the distribution of inner products between independent uniform points on the sphere to bound large pairwise correlations. A union-bound argument yields a probability that tends to zero with dimension.

B Proof of Lemma 3.1

  • The inner product of two independent uniform sphere points has the same distribution as the first coordinate of one such point.The squared first coordinate is identified with a Beta distribution, and a change of variables gives the density of the absolute inner product.Source: B Proof of Lemma 3.1 · p. 16
  • The proof combines the density calculation with Eq. (8) to bound the probability of large pairwise inner products.It then applies a union bound over pairs; the resulting probability is stated to be o_d(1).Source: B Proof of Lemma 3.1 · pp. 16–17

C Proof of Theorem 4.1

The proof of Theorem 4.1 uses the KKT conditions and margin equalities to construct perturbations of training examples. Its lemmas show that the constructed perturbation reverses the output sign while controlling its norm.

C Proof of Theorem 4.1

  • The proof sets up a depth-2 network with positive- and negative-output-weight groups and bounds pairwise dataset correlations by p.It assumes a dataset-size condition involving m, d, and p.Source: C Proof of Theorem 4.1 · p. 17
  • Lemma C.1 establishes that every example in the relevant index set has signed network output equal to 1.The proof proceeds under KKT conditions with nonnegative multipliers, which vanish for examples not attaining the margin.Source: C Proof of Theorem 4.1 · p. 17
  • Lemma C.9 bounds the norm of the constructed perturbation, and the theorem follows from Lemmas C.7, C.8, and C.9.The displayed norm bound depends on the dimension, dataset size, correlation bound, and other parameters.Source: C Proof of Theorem 4.1 · pp. 25–26

D Proof of Corollary 4.1

The proof of Corollary 4.1 carries over to the set I because the network expressions and proof arguments depend only on examples that attain margin 1. Additional dataset points outside those expressions do not affect the proof.

D Proof of Corollary 4.1

  • The expressions for w_j and b_j depend only on examples that attain margin 1 in N_θ.Examples with y_iN_θ(x_i) ≠ 1 have λ_i = 0.Source: D Proof of Corollary 4.1 · p. 26
  • Examples outside the expressions in Eqs. (9) and (10) do not affect the proof of Theorem 4.1.All arguments in that proof require only the examples appearing in those expressions.Source: D Proof of Corollary 4.1 · p. 26
  • The proof of Theorem 4.1 applies with respect to I, with Lemma C.1 omitted because every point in I attains margin 1.Source: D Proof of Corollary 4.1 · p. 26
Loading 2202.04347v2…