Robust Training under Label Noise by Over-parameterization

Sheng Liu; Zhihui Zhu; Qing Qu; Chong You

Source-linked AI summary

Robust Training under Label Noise by Over-parameterization

Sheng Liu, Zhihui Zhu, Qing Qu, Chong You

arXiv:2202.14026v2Feb 28, 2022cs.LGcs.AIcs.CVstat.ML

TL;DR

Over-parameterized networks can overfit corrupted labels, motivating robust training methods that separate sparse noise from the underlying data. The paper introduces SOP, which adds a sparse noise over-parameterization and exploits implicit regularization; experiments and simplified-model theory support improved generalization and exact separation under stated conditions.

Problem
Over-parameterized networks can fit incorrect labels in corrupted training data, leading to poor generalization.
Method
SOP models label noise with an additional sparse over-parameterization and uses gradient-descent implicit regularization to separate it from the data.
Results
The method improves generalization in deep image-classification experiments, while theory shows convergence to the ground truth under rank, incoherence, sparsity, and optimization conditions.
Takeaways & Limitations
Sparse over-parameterization provides a practical approach for preventing overfitting to corrupted labels and a theoretical route to separating sparse corruption from low-rank data.
Takeaways & Limitations
The theoretical analysis assumes a simplified low-rank model, and the extension from vanilla gradient descent to practical stochastic momentum training remains theoretically unjustified.

Abstract

from arXiv · show

Recently, over-parameterized deep networks, with increasingly more network parameters than training samples, have dominated the performances of modern machine learning. However, when the training data is corrupted, it has been well-known that over-parameterized networks tend to overfit and do not generalize. In this work, we propose a principled approach for robust training of over-parameterized deep networks in classification tasks where a proportion of training labels are corrupted. The main idea is yet very simple: label noise is sparse and incoherent with the network learned from clean data, so we model the noise and learn to separate it from the data. Specifically, we model the label noise via another sparse over-parameterization term, and exploit implicit algorithmic regularizations to recover and separate the underlying corruptions. Remarkably, when trained using such a simple method in practice, we demonstrate state-of-the-art test accuracy against label noise on a variety of real datasets. Furthermore, our experimental results are corroborated by theory on simplified linear models, showing that exact separation between sparse noise and low-rank data can be achieved under incoherent conditions. The work opens many interesting directions for improving over-parameterized models by using sparse over-parameterization and implicit regularization.

1 Introduction

Over-parameterized networks perform well with clean data but can fit corrupted labels and generalize poorly. The paper proposes Sparse Over-Parameterization (SOP), which models label noise separately and uses implicit regularization to improve robust training.

Over-parameterized networks can achieve zero training error even on incorrect labels, causing poor generalization.
SOP introduces an extra variable to model unknown label noise and minimizes the discrepancy between network predictions plus noise and observed labels.The noise variable is parameterized as s_i = u_i ⊙ u_i − v_i ⊙ v_i to promote sparsity.
SOP uses implicit algorithmic regularization from gradient descent to avoid the noisy-label solution despite adding learnable parameters.The method starts the additional variables from a small initialization.
SOP trains deep image-classification networks without overfitting to wrong labels and achieves better generalization across experiments on varied datasets.The introduction points to a broader empirical study beyond the motivating CIFAR-10 example.
The paper theoretically justifies SOP by showing exact separation of sparse corruption from data in a simplified over-parameterized linear model.The theory connects the induced regularization on the sparse corruption to classical ℓ1-based robust methods.

2 Robust Classification with Label Noise

The section presents SOP for image classification with noisy labels, combining sparse per-example variables, constrained optimization, and stochastic gradient training. Experiments cover synthetic and realistic noise across several datasets, showing robustness, gains over comparison methods, and fast training.

Method: SOP trains an over-parameterized network alongside per-example variables that model label noise, using stochastic gradient descent.The method uses objective (2), SGD, and variables u_i and v_i initialized near zero.
Method: The noise representation incorporates label structure by constraining s_i to match observed positive and negative label entries and bounding u_i, v_i in [-1, 1].The constraints are enforced through projection after each gradient update.
Method: SOP uses mean squared error for optimizing v_i because cross-entropy cannot optimize those variables, with one-hot projection empirically accelerating convergence.The training procedure is summarized in Algorithm 1.
Experiments: Experiments evaluate SOP and SOP+ on synthetic CIFAR-10/CIFAR-100 noise and realistic CIFAR-N, Clothing-1M, and WebVision noise.SOP+ adds consistency and class-balance regularization; synthetic noise includes symmetric and asymmetric label flips.
Results: SOP is reported as robust to substantial label noise, outperforming comparison methods on realistic datasets and achieving the fastest training speed across baselines.The comparisons include transition-matrix, loss-design, two-network, and label-noise-correction methods.

3 Theoretical Insights with Simplified Models

The theory studies recovery of a low-dimensional model and sparse corruptions in an over-parameterized linear setting. It shows that implicit regularization makes gradient descent equivalent to a convex formulation and enables exact recovery under incoherence and sparsity conditions.

Problem setup: The linearized model represents corrupted observations as y = Jθ⋆ + s⋆, where s⋆ is sparse, and seeks to recover both θ⋆ and s⋆.Because p > N, the system is underdetermined; minimum ℓ2-norm selection is used to make recovery well-posed.
Exact Recovery under Incoherence Conditions: Under rank-r, µ-incoherence, and sparsity assumptions, gradient dynamics converges to (θ⋆, s⋆) when k2r < N/(4µ) and α is below a suitable threshold.The same guarantee follows by combining exact recovery of the convex problem with the gradient-flow equivalence.
Landscapes & implicit sparse regularization: Gradient descent on the nonconvex formulation has a benign landscape: every critical point is either globally minimizing or a strict saddle, so random initialization almost surely reaches a global solution.Global convergence alone is insufficient because multiple global solutions may exist.
Landscapes & implicit sparse regularization: The algorithm’s implicit regularization corresponds to the convex program 1/2 ∥θ∥2^2 + λ∥s∥1 subject to y = Jθ + s.The ℓ2 penalty selects a minimum-norm θ, while the ℓ1 penalty promotes sparse s.
Problem setup: Over-parameterization alone leaves infinitely many decompositions, so sparse corruption and incoherence conditions are needed to identify the ground truth.Without additional structure, any observation can be decomposed into a sparse vector and a vector from the column space of J.
Exact Recovery under Incoherence Conditions: Numerical simulations show phase transitions: recovery occurs only above a λ threshold and when both rank r and sparsity k are small.The λ threshold varies with r and k, consistent with the theoretical recovery condition.

4 Related Work and Discussion

The discussion situates SOP within implicit regularization, robust learning, label-noise methods, sparsity, optimization, and modeling assumptions. It also identifies theoretical and practical boundaries, including low-rank idealization, optimizer dependence, sparse-noise assumptions, and representation robustness.

Implicit regularization: Implicit regularization motivates SOP by adding sparse regularization to an already implicitly regularized over-parameterized model for sparse corruptions.The resulting design involves two forms of implicit regularization and introduces new optimization and analysis questions.
Robust learning: SOP extends implicit sparse regularization from robust recovery of low-rank matrices and images to image classification with label noise.The paper states that SOP demonstrates effectiveness in this setting and provides dedicated theoretical analyses.
Label-noise methods: Existing label-noise approaches include robust losses, transition-probability modeling, and label correction, but SOP explicitly models sparse corruptions through over-parameterization.The cited discussion contrasts SOP's explicit noise modeling with approaches that reduce outlier effects, estimate transitions, or use heuristic sample behaviors.
Sparsity in deep learning: Sparsity in SOP represents a small percentage of corrupted labels and is enforced through gradient-descent implicit bias rather than primarily for computational efficiency or pruning.This distinguishes the method's objective, source of sparsity, and enforcement mechanism from prior sparsity work.
Optimization algorithms: SOP depends critically on the optimization algorithm: vanilla gradient descent is theoretically justified, whereas stochastic gradient descent with momentum is supported empirically but not theoretically.The discussion links the desired implicit regularization to algorithm choice and reports experiments with practical variants.
Limitations and future directions: The theory assumes a sparse label-noise matrix and an idealized low-rank structure, while future work is needed for approximate low-rank assumptions and robustness of learned representations.The paper also notes that no additional sparsity-pattern assumption is imposed beyond stated sign constraints and highlights representation robustness as an open direction.

Appendices

The appendices provide reproducibility details for the experiments and proofs for the theoretical results.

Appendix organization: Appendix Section A gives additional details for reproducing the experiments, while Section B provides proofs for the theoretical results.The appendix is organized around experimental reproducibility and theoretical verification.

A Training Details for Robust Classification with Label Noise

The training-details section explains why MSE, rather than cross-entropy, enables the sparse variable to learn label corruption, and specifies the synthetic noise settings used in evaluation.

Loss choice: Cross-entropy cannot correctly train the sparse variable because its gradient across entries does not depend on the model output beyond a shared divider.This prevents the variable from learning the label noise.
Loss choice: Under MSE, entrywise gradients vary with how well f(x, θ) + s matches y, allowing the sparse variable to learn corruption when predictions deviate from labels.The deviation can occur when a label is corrupted, providing a signal for recovering the underlying corruption.
Noise settings: Experiments cover symmetric noise levels α ∈ {0.2, 0.4, 0.5, 0.6, 0.8} and asymmetric flips between specified CIFAR class pairs, while Clothing1M and WebVision have estimated noise levels of 38.5% and 20%.For asymmetric noise, 40% of training labels are randomly selected for rule-based flipping.

A.3 Implementation Details of SOP+

SOP+ adds consistency and class-balance regularizers to stabilize training and encourage sensible predictions, producing a three-term final loss with tunable weights.

Regularizers: The consistency regularizer encourages matching network predictions on an original image and its augmented counterpart.It uses images generated with Unsupervised Data Augmentation.
Implementation reference: The appendix identifies a hyper-parameter table for SOP on CIFAR-10/100, Clothing-1M, and WebVision.The table is presented as a reference for these datasets.
Regularizers: The class-balance regularizer prevents assigning all data points to one class by matching batch mean predictions to class-prior probabilities using KL divergence.The batch mean prediction is compared with the prior probability p of each class.
Final objective: SOP+ combines the base objective with consistency and class-balance terms, weighted by hyper-parameters λc and λB.The final loss is constructed from three terms.

A.4 Experimental Settings

Experiments use standard image preprocessing and augmentation tailored to each dataset. CIFAR uses random crops and flips, SOP+ adds consistency views, and Clothing-1M uses resizing, cropping, and flipping.

Data augmentation: CIFAR10/100 experiments use random crops and horizontal flips without extra techniques.SOP+ additionally follows unsupervised data augmentation to create another view for consistency training.
Data preprocessing: Clothing-1M images are resized to 256 × 256, randomly cropped to 224 × 224, and horizontally flipped.

B.1 Proof of Proposition 3.2

The proof shows that every non-global critical point has a direction of negative curvature. Therefore, such points are strict saddles rather than local minima.

Critical-point structure: At a non-global critical point, some coordinate has ri ≠ 0 while ui = vi = 0.This follows from the gradient conditions and the fact that r ≠ 0.
Negative-curvature directions: For ri > 0, the proof perturbs the corresponding v coordinate while keeping dθ and du zero.
Negative-curvature directions: For ri < 0, the proof perturbs the corresponding u coordinate while keeping dθ and dv zero.
Negative-curvature directions: Both case-specific perturbations construct a direction of negative curvature, proving that the critical point is a strict saddle.

B.2 Proof of Proposition 3.3

The proof establishes global convergence and connects the limiting gradient-descent solution to an optimal solution of a regularized convex problem. The argument uses global optimality, limiting relations, and KKT conditions.

Global convergence: The global-convergence argument begins from the strict-saddle result and uses gradient descent’s almost-sure escape from saddle points.
Global convergence: For any fixed (γ, α), the limit r∞(γ, α) exists and is expressed through the limiting variables θ∞, u∞, and v∞.The expression is r∞(γ, α) = Jθ∞(γ, α) + u∞(γ, α) ⊙u∞(γ, α) −v∞(γ, α) ⊙v∞(γ, α).
Global convergence: The proof shows that the limiting point is a global solution to (14).
Implicit regularization: The implicit-regularization argument verifies that the limiting triplet satisfies the KKT conditions of the convex optimization problem in (25).
Implicit regularization: The limiting residual relation is Jθ∞(γ, α) + u∞(γ, α) ⊙u∞(γ, α) −v∞(γ, α) ⊙v∞(γ, α) = y.
Implicit regularization: After considering the possible signs of each component of bs, the proof concludes that (bθ, bs) is optimal for (25).

B.3 Proof of Proposition 3.5

The proof establishes exact recovery of the clean parameter and sparse corruption under a stable null space property. It then shows that an incoherence condition guarantees this property for sparse supports.

Recovery under the null space property: If A annihilates J on the left and satisfies the stable null space property, solving (25) recovers (θ⋆, s⋆) for λ > λ0.The threshold λ0 depends only on (J, θ⋆, ρ).
Incoherence and recovery: An incoherence condition implies that A satisfies the null space property for every support of size k.
Incoherence and recovery: Because s⋆ is k-sparse, the null space property applies to its support and yields the recovery conclusion of Proposition 3.5.
Proof strategy: The proof uses the compact SVD of J to rewrite the constraint in (25) before applying null-space arguments.
Recovery under the null space property: The null space property ensures that s⋆ is the unique minimizer when the sparse term is recovered by minimizing its ℓ1 norm.