Research map / Adversarial robustness and security / Certified and empirical robustness

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs

ICML 2025 · Adversarial robustness and security › Certified and empirical robustness · approach: Theory of adversarial risk

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that gradient flow on a two-layer polynomial-ReLU network (p>2), trained on samples from an orthonormal Gaussian mixture without adversarial examples, converges to a nearly optimal ℓ2-robust classifier.

Problem

Whether standard gradient-based training without adversarial examples or defense mechanisms can provably learn a maximally robust classifier for localized, multi-cluster data (orthonormal Gaussian mixture), where ReLU networks are known to fail.

Approach

Characterizes the maximum achievable ℓ2-robustness (√2/2) for orthonormal GMMs, shows the nearest-cluster Bayes classifier attains it, and proves that gradient flow with small balanced initialization on a two-layer pReLU network (p>2) converges to a classifier close to that optimal robust classifier, in contrast to ReLU networks.

Key results

• Proposition 1: no classifier can defend against ℓ2 attacks of radius √2/2 on orthonormal GMMs; the Bayes classifier is nearly optimal, robust up to √2/2 - Θ((α²/D)^{1/4}).
• Theorem 1: for p>2, gradient flow on pReLU with small balanced non-degenerate initialization yields f^(p) within Õ(α0²) of the optimal robust classifier F^(p) over a time window.
• Corollary 1: the learned pReLU network defends against ℓ2 attacks of radius √2/2 − Õ(α0^{2/p}) with high probability; experiments show ReLU/MLP/Tanh/LogReg fail while pReLU (p=3) succeeds (D=2000).

Measured effects reported in the paper

Surprising findings

• Standard ReLU networks trained with GD fail to be robust on orthonormal GMMs even though a robust classifier exists, and switching to a deeper MLP, Tanh, or a linear classifier does not fix it.

Limitations

• Random initialization does not satisfy the non-degenerate initialization assumption (gap is O(1/√D)); convergence is shown only for a non-degenerate initialization with Θ(1) gap, with experiments for random init.
• Analysis assumes a balanced dataset, balanced initialization, ℓ2 loss, and a specific orthonormal Gaussian mixture data model; extension to more realistic data (e.g., unions of subspaces) is left open.
• Requires sufficiently small intra-cluster variance and large dimension and sample size.

Experimental setup

Datasets: synthetic orthonormal Gaussian mixture

Benchmarks: synthetic orthonormal Gaussian mixture (D=2000, 12 positive and 8 negative clusters)

Metrics: adversarial robustness radius clean accuracy closeness of network to pReLU classifier F^(p)

Baselines: two-layer ReLU network trained by GF/GD Bayes optimal classifier (0-1 loss) linear classifier (LogReg) MLP Tanh network

Builds on: Min & Vidal (2024) pReLU network Boursier et al. (2022) gradient flow alignment analysis Frei et al. (2023) ReLU non-robustness Pal et al. (2023) data localization and separation

Closest papers by meaning

• Adversarial examples from computational constraints (ICML 2019 · similarity 0.88)
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (NeurIPS 2019 · similarity 0.88)
• Consistent Non-Parametric Methods for Maximizing Robustness (NeurIPS 2021 · similarity 0.88)
• Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.87)
• Lower Bounds on Adversarial Robustness from Optimal Transport (NeurIPS 2019 · similarity 0.87)
• Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.87)