Principled Approaches for Private Adaptation from a Public Source

Raef Bassily, Mehryar Mohri, Ananda Theertha SureshAISTATS 2023

Introduction

Domain adaptation is a cornerstone of modern machine learning, addressing the challenge of training a model on a labeled "source" domain to perform effectively on a different "target" domain. However, a significant hurdle arises when the target domain contains sensitive, unlabeled data—such as private user information on personal devices—while the source data is public. Standard domain adaptation algorithms often ignore privacy, potentially leaking sensitive target information. Conversely, traditional Differential Privacy (DP) methods typically assume that training and testing data share the same distribution. This paper bridges this gap by introducing principled algorithms for private domain adaptation, ensuring the target domain's privacy is preserved during the adaptation process.

The Problem: Privacy and Discrepancy

The authors focus on a scenario where a learner has access to public labeled source data and private unlabeled target data. The goal is to minimize the target error by reweighting the source samples. A common approach is discrepancy minimization, which seeks to reduce the statistical difference between the reweighted source distribution and the target distribution.

Mathematically, the discrepancy metric often involves calculating the maximum eigenvalue of a matrix, which is a non-differentiable operation. This lack of smoothness is a major obstacle for Differential Privacy; DP optimization typically requires smooth gradients to calibrate the noise added to protect individual data points. Without bounded sensitivity, the amount of noise required would overwhelm the signal, rendering the model useless.

Proposed Methodology

To overcome these challenges, the researchers developed several innovative techniques:

1. Smooth Approximation of Discrepancy

The authors introduce a softmax-based smooth approximation of the discrepancy metric. They prove that this approximation has bounded gradient sensitivity, which allows for the application of DP mechanisms. This smoothing "unlocks" the ability to use gradient-based optimization while maintaining rigorous privacy guarantees.

2. Single-Stage Private Frank-Wolfe

The paper proposes a novel, non-convex optimization algorithm that jointly optimizes the source data weights and the model parameters in a single stage. This is technically challenging because the data weights exist in a probability simplex ($\ell_1$ geometry), while the model parameters reside in a Euclidean ball ($\ell_2$ geometry). The algorithm employs a hybrid approach, applying Laplace noise for the $\ell_1$ components and Gaussian noise for the $\ell_2$ components, ensuring convergence to a stationary point while maintaining $(\epsilon, \delta)$-differential privacy.

3. Two-Stage Algorithms

As an alternative, the authors present two-stage algorithms. In the first stage, the optimal weights for the source data are found privately using either Private Frank-Wolfe or Noisy Mirror Descent. In the second stage, the model is trained non-privately on the public source data using these fixed weights.

Key Insights and Theoretical Results

  • Geometry Matters: A key theoretical finding is that the Private Frank-Wolfe algorithm is significantly more efficient than Noisy Mirror Descent for this task. The noise in Frank-Wolfe scales logarithmically with the number of source samples, whereas it scales polynomially in Mirror Descent. This makes Frank-Wolfe much more stable for standard dataset sizes.
  • Theoretical Guarantees: The authors provide rigorous $(\epsilon, \delta)$-differential privacy guarantees and generalization bounds for all proposed algorithms, establishing a solid mathematical foundation for private adaptation.

Empirical Evaluation

The algorithms were evaluated using a 10-dimensional synthetic Gaussian dataset. The target distribution was a spherical Gaussian, while the source was a mixture of the target (25%) and a distractor Gaussian (75%).

Results include: * Superiority of Single-Stage PFW: The single-stage Private Frank-Wolfe algorithm consistently outperformed the two-stage approaches and performed nearly as well as non-private baselines. * Graceful Degradation: As the privacy budget $\epsilon$ was tightened (increasing privacy), the model's test error increased predictably and smoothly, rather than failing abruptly. * Validation of Theory: Experiments confirmed that Noisy Mirror Descent suffered from high variance and poor performance compared to Frank-Wolfe, validating the authors' mathematical scaling analysis.

Limitations and Future Work

While this work provides a principled framework for private adaptation, it is currently limited to regression tasks using squared loss and linear predictors. Furthermore, the evaluation was restricted to synthetic data. Future research directions include extending these methods to classification problems, exploring multi-source domain adaptation, and testing the framework on complex, real-world private datasets.

Summary updated

BibTeX
@inproceedings{bassily2023principled,
  author = {Raef Bassily and Mehryar Mohri and Ananda Theertha Suresh},
  title = {{Principled Approaches for Private Adaptation from a Public Source}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
}
Figure