Technical Summary: Modulated Learning for Private and Distributed Regression with One Sample per Client

Problem Statement

This work addresses a critical limitation in standard Federated Learning (FL) and Differentially Private (DP) learning paradigms: the assumption that client devices possess local datasets large enough to compute meaningful gradient updates. In many real-world scenarios—such as fitness trackers, body-worn sensors, and daily event monitors—clients may hold only a single data sample (or very few).

In this "one-sample-per-client" regime, standard DP-SGD based FL fails because:

1. Unreliable Local Updates: A local gradient computed on a single point is highly noisy and unreliable for estimating model coefficients, particularly in early training rounds.
2. Privacy Noise Amplification: The noise injected to satisfy differential privacy further degrades the utility of these already weak local updates, rendering the global model convergence ineffective.

The paper asks: Can we enable useful, differentially private distributed learning when each client contributes only one example data point?

Methodology

The authors propose a Modulated Learning framework. Instead of clients sending model coefficients (as in standard FL) or raw gradients, clients transmit a privately transformed representation of their single data sample. The server then aggregates these representations to recover an unbiased estimate of the centralized gradient.

Core Mechanism: Cosine-Modulated Transformation

The protocol operates in rounds. In each round $t$, the server maintains a global model $\beta_t$ and selects a modulation direction $v_t$ (orthogonal to $\beta_t$).

1. Client-Side Processing:
Given a private sample $(x_i, y_i)$, the client performs the following steps:

• Modulation: The client samples a random phase $\phi_i \sim \text{Unif}[0, 2\pi]$ and computes a modulated feature vector:
  $$g_i = (1 - \alpha)x_i + \lambda \cos(\omega \langle x_i, v_t \rangle + \phi_i) v_t$$
  Here, $\alpha, \lambda, \omega$ are hyperparameters. The term $(1-\alpha)x_i$ preserves the signal, while the cosine term introduces a contractive, privacy-preserving perturbation.
• Noise Injection: To ensure $(\epsilon, \delta)$-local differential privacy (LDP), the client adds Gaussian noise $\xi_i \sim \mathcal{N}(0, \sigma_{DP}^2 I)$:
  $$\tilde{g}_i = g_i + \xi_i$$
• Transmission: The client sends the pair $(\tilde{g}_i, y_i)$ to the server. Note that $y_i$ is treated as public/non-sensitive in this specific setup, while $x_i$ is the private input.

2. Server-Side Aggregation and De-biasing:
The server receives $\{(\tilde{g}_i, y_i)\}_{i=1}^K$ and performs algebraic corrections to remove the bias introduced by modulation and noise:

• Covariance Estimation: The server computes the empirical covariance of the received features and subtracts the known bias terms (the modulation variance and noise variance):
  $$\hat{\Sigma}_x = \frac{1}{(1-\alpha)^2} \left( \frac{1}{K}\sum \tilde{g}_i \tilde{g}_i^\top - \frac{\lambda^2}{2} v_t v_t^\top - \sigma_{DP}^2 I \right)$$
  Theorem 3.1 and Corollary 3.2 prove that $\hat{\Sigma}_x$ is an unbiased estimator of the true data covariance $\Sigma_x = \frac{1}{K}\sum x_i x_i^\top$.
• Gradient Recovery: The server constructs an unbiased gradient estimator $G$:
  $$G = \hat{\Sigma}_x \beta_t - \frac{1}{1-\alpha} \frac{1}{K} \sum y_i \tilde{g}_i$$
  This $G$ satisfies $\mathbb{E}[G] = \nabla L(\beta_t)$, matching the non-private centralized gradient in expectation.

Variants

• Multi-Vector Modulation: To reduce the Lipschitz constant (and thus the required noise $\sigma_{DP}$), the authors generalize the method to use $m$ orthonormal vectors. This reduces the sensitivity bound from $|1-\alpha| + \lambda\omega$ to $|1-\alpha| + \frac{\lambda\omega}{\sqrt{m}}$.
• Non-Iterative (One-Shot) Estimator: The paper also derives a closed-form moment estimator that solves for $\beta$ in a single step, avoiding the privacy composition costs of iterative methods.

Key Contributions

1. Unbiased Gradient Estimation from Single Samples: The paper demonstrates that by transforming data via a specific cosine-modulated map and applying post-processing debiasing, a server can recover an unbiased gradient estimate even when clients hold only one sample each.
2. Privacy-Utility Trade-off Optimization:
   • The method establishes a Cramér-Rao lower bound on the reconstruction error, proving that the modulation parameters ($\lambda, \omega$) actively increase the difficulty of reconstructing the private input $x_i$ beyond the protection offered by Gaussian noise alone.
   • The multi-vector variant is shown to reduce the required noise variance by a factor related to $\sqrt{m}$, improving utility for a fixed privacy budget.
3. Theoretical Guarantees:
   • Unbiasedness: Rigorous proof that the server's estimator is unbiased.
   • Convergence: The paper establishes the asymptotic normality of the estimator and derives variance bounds, showing convergence rates for projected stochastic gradient descent.
   • Privacy Accounting: The method uses zero-concentrated differential privacy (zCDP) accounting, which offers tighter composition bounds than standard $(\epsilon, \delta)$-DP for sequential rounds.
4. Reconstruction Lower Bounds: The authors derive a theoretical lower bound on the mean squared error of any unbiased attacker attempting to reconstruct $x_i$ from the transmitted message, quantifying the privacy protection directly in terms of protocol parameters.

Experimental Results

The authors evaluated the approach on five real-world regression datasets (e.g., CO2 emissions, Fairness in marriage duration, Mode Choice) where each training example was treated as a separate client.

• Comparison: The proposed Modulated Iterative and Modulated One-Shot estimators were compared against a tuned DP-SGD FedAvg baseline.
• Findings:
  • High Privacy (Low $\epsilon$): The Modulated One-Shot estimator outperformed iterative methods. Because it relies on a single private release, it avoids the cumulative privacy loss (composition) inherent in iterative DP-SGD, making it more robust when the privacy budget is extremely tight.
  • Moderate/Low Privacy (High $\epsilon$): The Modulated Iterative estimator improved steadily with more rounds and eventually outperformed the one-shot method and the DP-SGD baseline on most tasks.
  • Baseline Performance: DP-SGD struggled significantly in this regime because the noise required to protect a single sample per round, compounded over multiple rounds, overwhelmed the signal.

Significance and Claims

The paper claims to solve a specific regime where standard federated learning is inapplicable: learning from devices with extremely limited data (one sample) under strict privacy constraints.

• Paradigm Shift: Unlike traditional private FL which shares model updates (gradients/weights), this approach shares privatized data representations. This shift allows the server to perform global statistical corrections that are impossible when clients only send noisy local gradients.
• Practicality: The method enables devices with minimal data to collaboratively learn accurate regression models without sacrificing individual privacy or requiring large local datasets.
• Theoretical Rigor: The work provides a complete theoretical framework, including unbiasedness proofs, variance analysis, convergence guarantees, and reconstruction lower bounds, establishing that the method is not just heuristic but statistically sound.

The authors conclude that this approach makes it feasible to deploy privacy-preserving machine learning in scenarios previously considered impossible due to data scarcity and privacy requirements.