Towards Understanding GD with Hard and Conjugate Pseudo-labels for Test-Time Adaptation

Jun-Kun Wang, Andre Wibisono

Abstract

We consider a setting where a model needs to adapt to a new domain under distribution shifts, given that only unlabeled test samples from the new domain are accessible at test time. A common idea in most related works is constructing pseudo-labels for the unlabeled test samples and applying gradient descent (GD) to a loss function with these pseudo-labels. Recently, Goyal et al. (2022) proposed conjugate labels, a new kind of pseudo-label for self-training at test time, and empirically showed that they outperform other pseudo-labeling methods. However, provably showing that GD with conjugate labels learns a good classifier for test-time adaptation remains open. In this work, we aim at theoretically understanding GD with hard and conjugate labels for a binary classification problem. We show that for square loss, GD with conjugate labels converges to an $\epsilon$-optimal predictor under a Gaussian model for any arbitrarily small $\epsilon$, while GD with hard pseudo-labels fails. We also analyze them under different loss functions. Our results shed light on understanding when and why GD with hard or conjugate labels works in test-time adaptation.

Introduction

Machine learning models often encounter "distribution shift," where deployment data differs significantly from training data. Fully Test-Time Adaptation (TTA) addresses this by updating the model using only the unlabeled samples encountered during deployment. A popular TTA strategy is self-training, where the model generates "pseudo-labels" for unlabeled data and uses them as ground truth for gradient descent updates.

While traditional "hard" pseudo-labels (taking the most confident prediction) are common, recent empirical work has highlighted the superiority of conjugate pseudo-labels. This paper provides the first rigorous theoretical foundation explaining this performance gap.

Theoretical Framework: The Gaussian Model

The authors analyze TTA using a binary classification task under a Gaussian Model. Data points $(x, y)$ are generated such that $x \sim N(y\mu, \sigma^2 I)$, where $y \in \{+1, -1\}$. An optimal classifier is defined by a weight vector $w$ that aligns with the mean vector $\mu$.

The study focuses on the Population Dynamics of Gradient Descent, analyzing how the model's weights evolve on average when exposed to an infinite stream of unlabeled test data. This allows for a clean mathematical comparison of different pseudo-labeling strategies across various loss functions, including square, logistic, and exponential losses.

Hard vs. Conjugate Pseudo-labels

The core of the analysis lies in how pseudo-labels are constructed:

  • Hard Labels: The model assigns a discrete label (e.g., +1 or -1) based on its current prediction.
  • Conjugate Labels: These are derived from the mathematical properties of conjugate functions, providing a "softer" and more theoretically grounded target for adaptation.

A key theoretical contribution is the definition of Property $\clubsuit$. This set of mathematical conditions regarding symmetry and the tail behavior of the loss derivative allows the authors to unify the analysis of different loss functions.

The shape of the conjugate logistic loss function, illustrating the mathematical properties analyzed under Property $\clubsuit$.

Key Results and Convergence Properties

The paper establishes several critical propositions regarding the convergence of these methods:

  1. The Failure of Hard Labels: Under square loss, GD with hard labels is proven to fail. It can get "stuck" at a sub-optimal solution or oscillate indefinitely, never reaching an $\epsilon$-optimal predictor even in noiseless environments.
  2. The Success of Conjugate Labels: Conversely, GD with conjugate labels under square loss achieves exponentially fast convergence to the optimal predictor.
  3. Loss Function Sensitivity: For losses satisfying Property $\clubsuit$ (like logistic and exponential), both hard and conjugate labels achieve a convergence rate of $\Omega(\log(t))$. However, conjugate labels typically maintain better constant factors, leading to faster progress in practical scenarios.
Simulation results comparing hard and conjugate labels. (a) With a small step size, hard labels plateau while conjugate labels reach the theoretical minimum error. (b) With a large step size, hard labels oscillate wildly, whereas conjugate labels remain stable and effective.

Discussion and Limitations

This work provides a rare example of proving that GD can reach a global optimum in a non-convex setting relevant to real-world adaptation. However, several avenues for future work remain:

  • Multi-class Extension: The current theory is limited to binary classification.
  • Finite-Sample Analysis: Moving beyond "population dynamics" to account for the noise inherent in finite mini-batches is necessary.
  • Deep Architectures: While linear models provide a strong theoretical starting point, extending these proofs to deep neural networks is a significant challenge.

By formalizing the advantages of conjugate labels, this research offers a roadmap for developing more robust and efficient test-time adaptation algorithms.

Summary updated

Abstract

We consider a setting that a model needs to adapt to a new domain under distribution shifts, given that only unlabeled test samples from the new domain are accessible at test time. A common idea in most of the related works is constructing pseudo-labels for the unlabeled test samples and applying gradient descent (GD) to a loss function with the pseudo-labels. Recently, \cite{GSRK22} propose conjugate labels, which is a new kind of pseudo-labels for self-training at test time. They empirically show that the conjugate label outperforms other ways of pseudo-labeling on many domain adaptation benchmarks. However, provably showing that GD with conjugate labels learns a good classifier for test-time adaptation remains open. In this work, we aim at theoretically understanding GD with hard and conjugate labels for a binary classification problem. We show that for square loss, GD with conjugate labels converges to an $\epsilon$-optimal predictor under a Gaussian model for any arbitrarily small $\epsilon$, while GD with hard pseudo-labels fails in this task. We also analyze them under different loss functions for the update. Our results shed lights on understanding when and why GD with hard labels or conjugate labels works in test-time adaptation.
BibTeX
@inproceedings{wang2023towards,
  author = {Jun-Kun Wang and Andre Wibisono},
  title = {{Towards Understanding GD with Hard and Conjugate Pseudo-labels for Test-Time Adaptation}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=FJXf1FXN8C},
}
Figure