Abstract
Interval Bound Propagation (IBP) is a cornerstone of state-of-the-art methods for training neural networks with certifiable robustness guarantees. Despite its practical success, the theoretical convergence of IBP training has remained largely unexplored. In this paper, we provide a rigorous analysis of IBP convergence within the regime of overparameterized two-layer ReLU networks. We demonstrate that when using a logistic loss, gradient descent converges linearly to zero robust training error, provided the network is sufficiently wide and the adversarial perturbation radius remains below a specific threshold.
Introduction
Deep neural networks are notoriously fragile; small, often imperceptible perturbations to an input can drastically alter model predictions. Certified robust training aims to mitigate this by optimizing models to remain correct for all points within a defined region (typically an $\ell_\infty$ ball) around an input. Among various techniques, Interval Bound Propagation (IBP) has emerged as a preferred method due to its computational efficiency. By propagating interval bounds through the network layers, IBP provides a tractable "worst-case" output for optimization.
While standard training theory suggests that sufficiently wide networks can always reach a global minimum, it was previously unknown if this "overparameterization magic" extended to the more complex landscape of robust training. This work addresses this gap by providing the first theoretical convergence guarantees for IBP-based robust training.
Methodology and Theoretical Framework
The analysis focuses on a two-layer ReLU neural network trained for binary classification using a logistic loss. The authors employ a Gradient Flow framework—essentially gradient descent with an infinitesimally small step size—to track the evolution of network weights over time.
The core of the proof involves analyzing the stability of the Gram Matrix, which serves as the robust counterpart to the Neural Tangent Kernel (NTK). In standard training, the Gram matrix remains relatively constant in the overparameterized regime. However, in IBP training, the activation state of a neuron is not a simple binary function of a single input; instead, it depends on the interval bounds of that neuron. The authors prove that if the perturbation radius $\epsilon$ is sufficiently small, the robust Gram matrix remains positive definite throughout the training process, ensuring that the loss decreases at a linear rate.
Key Insights
1. Linear Convergence to Zero Error
The primary contribution is the mathematical proof that robust training error vanishes at a linear rate: $$L(t) \leq \exp(-\lambda_0 t / 2) L(0)$$ where $\lambda_0$ represents the minimum eigenvalue of the initial robust Gram matrix. This confirms that IBP is not merely a heuristic but has a solid theoretical foundation in the overparameterized regime.
2. The Critical Perturbation Threshold
A significant finding is that convergence is not guaranteed for arbitrary perturbation radii. There exists a specific upper bound on $\epsilon$. If the perturbation exceeds this threshold, the optimization landscape may prevent the model from reaching zero robust error, regardless of the network width. This provides a theoretical explanation for why training with large $\epsilon$ is notoriously difficult in practice.
3. Width-Perturbation Trade-off
The theory establishes a relationship between the required network width $m$ and the perturbation radius $\epsilon$. As $\epsilon$ increases, the width required to guarantee convergence grows significantly. This highlights the increased complexity of the robust optimization landscape compared to standard training and provides theoretical support for "epsilon scheduling," where $\epsilon$ is gradually increased during training.
Experimental Validation
To validate the theoretical findings, experiments were conducted on a binary classification task using the MNIST dataset (specifically distinguishing between the digits 2 and 5). The results confirmed the "hard limit" predicted by the theory:
- Standard vs. Robust Training: While standard training reached zero error easily, IBP training error remained higher for equivalent widths.
- Convergence Limits: When $\epsilon$ was set to 0.04, even a network with 80,000 hidden neurons failed to reach zero error, supporting the existence of the theoretical $\epsilon$ threshold.
Conclusion and Limitations
This work provides a crucial first step in understanding the optimization dynamics of certified robust training. By proving linear convergence for overparameterized shallow networks, it validates the use of IBP in robust machine learning.
However, several challenges remain. The current analysis is limited to two-layer networks and binary classification. Future research is needed to extend these guarantees to deep architectures and multi-class settings. Additionally, while this paper analyzes fixed $\epsilon$, investigating the convergence of dynamic $\epsilon$-scheduling remains an important open theoretical challenge.
Summary updated