Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails

1. Problem Statement

The paper addresses Stochastic Convex Optimization (SCO) under Pure $\epsilon$-Differential Privacy (DP).

• Goal: Minimize the population risk $F(w) = \mathbb{E}_{z \sim P}[f(w, z)]$ over a convex compact domain $W \subset \mathbb{R}^d$.
• Challenge 1: Heavy-Tailed Gradients. Traditional DP-SCO literature assumes the loss function is uniformly Lipschitz continuous with a bounded gradient norm $L$ (i.e., $\sup \|\nabla f\| \le L$). However, in many real-world scenarios (e.g., linear regression with unbounded features), $L$ can be infinite or extremely large. The paper relaxes this to a bounded $k$-th moment assumption:
  $$\mathbb{E}\left[\sup_{w \in W} \|\nabla f(w, z)\|^k\right] \le G_k^k$$
  for some $k \ge 2$. This allows for heavy-tailed gradient distributions while controlling average behavior.
• Challenge 2: Pure DP vs. Approximate DP. While optimal rates for approximate $(\epsilon, \delta)$-DP heavy-tailed SCO are known (using noisy clipped gradients), the pure $\epsilon$-DP case ($\delta=0$) remained an open problem. Existing heavy-tailed algorithms rely on clipping, which is suboptimal or computationally inefficient under pure DP due to the lack of advanced composition theorems.

2. Methodology

The authors propose a novel framework that moves away from standard noisy clipped gradient methods and instead utilizes Lipschitz extensions of the empirical loss.

A. Core Framework: Lipschitz Extension

Instead of optimizing the original heavy-tailed loss $f$, the algorithm optimizes its Lipschitz extension $f_C$:
$$f_C(w, z) := \inf_{y \in W} \left[ f(y, z) + C\|w - y\| \right]$$

• Properties: $f_C$ is convex and $C$-Lipschitz, even if $f$ has unbounded gradients.
• Bias Control: The extension introduces a bias ($f - f_C$). To control this, the authors use a localization strategy. They first shrink the optimization domain $W$ to a smaller set $W_0$ where the minimizer is likely to reside. Since the bias scales with the diameter of the domain, optimizing over $W_0$ (where $\text{diam}(W_0) \ll \text{diam}(W)$) significantly reduces the bias.

B. Algorithmic Pipeline: Localized Double Output Perturbation

The main algorithm, Localized Double Output Perturbation, operates in phases (following a population-localization framework) and consists of three key steps for each phase:

1. Private Localization (First Output Perturbation):
   • Compute an approximate minimizer of the regularized Lipschitz extension.
   • Add Laplace noise to this solution and project it back to $W$.
   • Define a small ball $W_0$ around this noisy point. This step ensures the true minimizer lies in $W_0$ with high probability while satisfying $\epsilon/2$-DP.
2. Efficient Optimization over $W_0$:
   • Joint Convex Reformulation: The minimization of the Lipschitz extension involves an inner infimum. The authors reformulate the problem into a jointly convex objective over variables $(w, y_1, \dots, y_n)$:
     $$\Phi(w, y) = \frac{1}{n}\sum (f(y_i, z_i) + C\|w - y_i\|) + \frac{\lambda}{2}\|w - w_0\|^2$$
   • Adaptive Inexact Projected Subgradient: Since the Lipschitz constant of $\Phi$ is unknown (due to heavy tails), they employ an adaptive projected subgradient method. This method adjusts step sizes based on observed gradient norms and uses an inexact projection oracle for $W_0$ (constructed via bisection on the Lagrange multiplier). This guarantees a certified approximate minimizer in polynomial time with high probability.
3. Private Output (Second Output Perturbation):
   • Add Laplace noise to the approximate minimizer found in $W_0$ and project it back to $W_0$. This final step ensures the output is $\epsilon/2$-DP.

C. Handling Infinite Lipschitz Parameters

For specific structured problem classes (e.g., hinge/ReLU losses on polytopes), the authors show that if one can efficiently compute approximate subgradients of the Lipschitz extension $f_C$, the algorithm runs in polynomial time with probability 1, even if the worst-case Lipschitz parameter is infinite.

3. Key Contributions

1. Optimal Minimax Rates for Pure DP:
   The paper establishes the minimax optimal excess risk rate for pure $\epsilon$-DP heavy-tailed SCO (up to logarithmic factors):
   $$\tilde{O}\left( G_k D \left(\frac{d}{n\epsilon}\right)^{1 - 1/k} + \frac{G_2 D}{\sqrt{n}} \right)$$
   This matches the known rates for approximate DP, closing the gap for pure DP.

2. First Polynomial-Time Pure DP Algorithm:
   They provide the first computationally efficient algorithm achieving this rate.

   • High Probability: Runs in polynomial time with high probability.
   • Probability 1: Runs in polynomial time with probability 1 if the worst-case Lipschitz parameter is polynomially bounded.
   • Structured Classes: For specific losses (hinge, ReLU, absolute value) on Euclidean balls/polytopes, it runs in polynomial time with probability 1 even with infinite worst-case Lipschitz parameters.

3. Novel Lower Bound:
   The authors prove a high-probability lower bound that is sharper (by logarithmic factors) than previous in-expectation bounds. They combine packing techniques with a reduction from quantile estimation to decoding.

4. Impossibility Result:
   They prove that exact computation of the Lipschitz extension is impossible in finite time from local oracle information in general, justifying the need for their approximate optimization framework.

4. Key Results

• Theorem 3.1 (Main Result): The Localized Double Output Perturbation algorithm achieves the optimal excess risk bound with high probability in polynomial time.
• Runtime Guarantees:
  • General case: Polynomial time with high probability.
  • Bounded Lipschitz case: Polynomial time with probability 1.
  • Structured losses (e.g., Hinge/ReLU): Polynomial time with probability 1 even with unbounded gradients.
• Lower Bound (Theorem 4.1): Any $\epsilon$-DP algorithm must incur an excess risk of at least:
  $$\Omega\left( G_k D \left(\frac{d + \log(1/\delta)}{n\epsilon}\right)^{1 - 1/k} + G_2 D \sqrt{\frac{\log(1/\delta)}{n}} \right)$$
  This confirms the optimality of the upper bound up to logarithmic factors.

5. Significance

• Bridging the Pure DP Gap: This work resolves a major open problem in differential privacy by showing that pure DP does not require a statistical penalty (in terms of convergence rates) compared to approximate DP, even in the challenging heavy-tailed regime.
• Algorithmic Innovation: The shift from "clipped gradients" to "optimizing Lipschitz extensions" via joint convex reformulation and adaptive subgradient methods provides a new toolkit for private optimization under weak regularity assumptions.
• Practical Applicability: By identifying structured subclasses (common in ML like SVMs and ReLU networks) where the algorithm runs in polynomial time with probability 1, the results are not just theoretical but potentially applicable to real-world heavy-tailed data scenarios where privacy is critical.
• Tightness: The matching lower bound confirms that the derived rates are fundamental limits, not just artifacts of the specific algorithm.

In summary, this paper provides a complete characterization of the statistical and computational complexity of pure differentially private stochastic convex optimization under heavy-tailed assumptions, offering optimal rates and efficient algorithms where none previously existed.