Corruption-Tolerant Algorithms for Generalized Linear Models

Bhaskar Mukhoty, Debojyoti Dey, Purushottam Kar

Abstract

Generalized Linear Models (GLMs) are foundational in machine learning but highly susceptible to adversarial label corruption. We introduce SVAM (Sequential Variance-Altered MLE), a unified framework that achieves robustness by iteratively adjusting the variance of the likelihood function. Starting with a "blurry" likelihood to mitigate outlier influence and gradually "sharpening" focus, SVAM provides strong theoretical guarantees and superior empirical performance. Our results demonstrate that SVAM handles significant corruption fractions and converges reliably regardless of initialization.

Problem Statement: The Vulnerability of GLMs

Generalized Linear Models (GLMs), including logistic and gamma regression, are workhorses of statistical modeling. However, they are notoriously sensitive to adversarial label corruption. Even a small fraction of maliciously modified training labels—such as flipped binary labels or extreme outliers in regression—can cause standard Maximum Likelihood Estimation (MLE) to fail completely.

Existing robust methods often suffer from three main drawbacks:

  1. Lack of Generality: Many are tailored to specific loss functions (e.g., squared error) and do not generalize across the exponential family.
  2. Susceptibility to Adaptive Adversaries: They may fail when an attacker strategically chooses corruptions based on the dataset or model.
  3. Weak Theoretical Guarantees: Many algorithms lack a proven "breakdown point"—the maximum fraction of corruption an algorithm can tolerate before its error becomes unbounded.

The SVAM Framework: Likelihood Annealing

The core innovation of this work is SVAM (Sequential Variance-Altered MLE). Unlike traditional weighted MLE approaches, SVAM employs a novel variance-reduction technique that functions similarly to simulated annealing.

1. Variance Altering

The framework utilizes a transformation that scales the variance of an exponential family distribution while preserving its mode and the relative ordering of likelihoods.

2. The "Blurry" Start and Sequential Sharpening

The algorithm begins with a very high variance (low $\beta$). In this initial "blurry" state, the likelihood function is relatively flat, ensuring that all data points—clean or corrupted—receive comparable weights. This prevents the model from being immediately derailed by adversarial outliers. As iterations proceed, the algorithm gradually increases $\beta$ (decreases variance). As the model estimate improves, the likelihood of uncorrupted points naturally dominates, allowing the algorithm to "home in" on the clean data.

3. Universal Applicability

Because SVAM operates on the underlying distribution's variance, it can be applied to any GLM by simply swapping the distribution (e.g., Gaussian for least squares, Gamma for positive-valued regression).

Key Results and Discussion

The authors evaluated SVAM against several state-of-the-art robust methods (e.g., TORRENT, SEVER, STIR) using synthetic benchmarks designed to test the limits of adversarial robustness.

Robustness to Corruption Levels

A critical metric for robust algorithms is the breakdown point. As shown in the following analysis, SVAM-RR maintains a near-zero error even as the corruption fraction $\alpha$ increases towards 0.4, significantly outperforming methods like SEVER and STIR which break down much earlier.

Sensitivity of various robust algorithms to the corruption fraction $\alpha$. SVAM-RR demonstrates a significantly higher breakdown point compared to competitors.

Global Convergence and Initialization

Many robust algorithms require a "warm start" or a good initial guess to avoid local minima created by outliers. SVAM, however, exhibits remarkable robustness to initialization. Whether initialized at the origin or with adversarially corrupted data, the algorithm consistently converges to the true model parameters.

Convergence of the model error $\|w - w^*\|_2$ over iterations for different initialization strategies. SVAM-RR converges to the true parameters even under adversarial initialization.

Performance Highlights

  • Speed: In least-squares tasks, SVAM-RR is often twice as fast as specialized competitors like TORRENT.
  • Exact Recovery: In the absence of random noise, SVAM can recover exact true parameters even against a fully adaptive adversary.
  • Gamma Regression: SVAM provides the first provable guarantees for robust Gamma regression, a task previously lacking a known breakdown point.

Limitations and Future Work

While SVAM represents a significant step forward, some challenges remain. The algorithm's performance is somewhat sensitive to hyperparameters like the initial scale ($\beta_1$) and the increment factor ($\xi$). Furthermore, while SVAM provides a breakdown point for Gamma regression, it currently scales with $1/\sqrt{d}$ (where $d$ is dimensionality), suggesting potential fundamental limits compared to the constant breakdown point achieved in least-squares. Future research will explore how these methods perform under "dirty" feature distributions in real-world datasets, moving beyond label-only corruption.

Summary updated

Abstract

This paper presents SVAM (Sequential Variance-Altered MLE), a unified framework for learning generalized linear models under adversarial label corruption in training data. SVAM extends to tasks such as least squares regression, logistic regression, and gamma regression, whereas many existing works on learning with label corruptions focus only on least squares regression. SVAM is based on a novel variance reduction technique that may be of independent interest and works by iteratively solving weighted MLEs over variance-altered versions of the GLM objective. SVAM offers provable model recovery guarantees superior to the state-of-the-art for robust regression even when a constant fraction of training labels are adversarially corrupted. SVAM also empirically outperforms several existing problem-specific techniques for robust regression and classification. Code for SVAM is available at https://github.com/purushottamkar/svam/
BibTeX
@inproceedings{mukhoty2023corruption,
  author = {Bhaskar Mukhoty and Debojyoti Dey and Purushottam Kar},
  title = {{Corruption-Tolerant Algorithms for Generalized Linear Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26108},
}
Figure