Technical Summary: On the Gradient Complexity of Private Optimization with Private Oracles

Problem Statement

This paper investigates the oracle complexity (running time measured in first-order oracle queries) of differentially private (DP) empirical risk minimization (ERM) and stochastic convex optimization (SCO) for Lipschitz convex losses. The authors focus on two distinct settings:

1. Non-smooth losses with Private Oracles: The optimizer interacts with a "proxy oracle" that processes a minibatch of gradients and returns a message satisfying differential privacy (specifically $\rho$-zCDP). This models common practices like DP-SGD where gradients are perturbed before transmission.
2. Smooth losses with Private Optimizers: The assumption is relaxed to require only that the final optimization procedure satisfies $(\epsilon, \delta)$-DP, without restricting the internal oracle mechanism to be private.

The primary goal is to establish lower bounds on the number of gradient queries required to achieve an excess risk of $\alpha$, specifically analyzing how privacy constraints and dimensionality $d$ impact runtime compared to non-private counterparts.

Methodology

The authors employ a hybrid of "vector discovery" and information-theoretic lower bound techniques.

Hard Problem Construction

The core of the lower bound relies on a specific loss function construction inspired by Nemirovski's function but augmented with a regularization term. The loss is defined as:
$$L(w) = \max \left\{ \max_{k \in [K]} \{ |\langle w, X_k \rangle - \alpha| \}, \| \Pi_V w \| \right\}$$
where:

• $X_1, \dots, X_K$ are random orthonormal vectors in $\mathbb{R}^d$.
• $V$ is a random subspace orthogonal to the span of $\{X_k\}$.
• $\Pi_V$ is the orthogonal projection onto $V$.
• The loss is replicated $n$ times for the ERM setting.

Information-Theoretic Analysis

The proof strategy involves showing that to minimize this loss, an optimizer must "discover" each vector $X_k$. However, unlike standard vector discovery where observing a vector is sufficient, here the optimizer must obtain high mutual information about each $X_k$ despite the privacy constraints.

• Mutual Information Tracking: The authors track the sum of conditional mutual informations $\sum I(X_k; W | X_{\neq k}, V)$, where $W$ is the output solution. They argue that estimating $X_k$ remains a high-dimensional problem even when other vectors are known.
• Privacy Constraints: For private oracles, the authors bound the information leaked about $X_k$ using properties of $\rho$-zCDP and group privacy. They demonstrate that unless the optimizer makes $\Omega(d)$ queries to learn the subspace $V$, it cannot effectively utilize the unpenalized subspace to estimate $X_k$.
• Information-Limited Oracles: The technique extends to oracles with bounded information capacity $\Gamma$ (bits), showing that the optimizer must query the oracle enough times to accumulate sufficient information about the gradients.

Key Contributions and Results

1. Non-Smooth Optimization with Private Oracles

The paper establishes that for dimension $d \geq 1/\alpha^2$, any optimizer interacting with a $\rho$-zCDP proxy oracle requires an expected running time of:
$$\Omega\left( \min\left\{ \frac{\sqrt{d}}{\alpha^2 \sqrt{\rho}} + \frac{d}{\bar{m}\rho}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
where $\bar{m}$ is the maximum minibatch size.

• Tightness: This lower bound is shown to be tight (up to logarithmic factors) for the regime $d \geq 1/\alpha^4$ via an analysis of DP-SGD.
• Batch Size Impact: The result explicitly characterizes the negative impact of small batch sizes ($\bar{m}$) on private learning dynamics. If $\bar{m} < \sqrt{d}$, the runtime penalty increases.
• Corollary for DP-SGD: For DP-SGD with batch size $m$, the runtime is $\Omega(\min\{ \frac{\sqrt{d} + d/m}{\alpha^2}, \frac{d}{m \log(1/\alpha)} \})$.

2. Non-Smooth Optimization with Information-Limited Oracles

Extending the proof technique, the authors show that if a proxy oracle transmits at most $\Gamma$ bits of information about the gradients, the required number of oracle calls is:
$$\Omega\left( \min\left\{ \frac{d}{\alpha^2 \Gamma}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
This result highlights fundamental limitations of gradient quantization techniques in private optimization, showing that the optimizer must effectively use "the entirety" of the gradient information to succeed.

3. Smooth Optimization with Private Optimizers

For smooth losses, where only the final optimizer is required to be $(\epsilon, \delta)$-DP (not the oracle), the authors prove a lower bound on the expected number of oracle calls:
$$\tilde{\Omega}\left( \frac{\sqrt{d}}{\alpha} + \min\left\{ \frac{1}{\alpha^2}, n \right\} \right)$$

• Privacy Independence: Notably, this lower bound does not depend on the privacy parameter $\epsilon$ (provided $\alpha$ is fixed). The authors argue that stronger privacy guarantees only impact the minimum achievable accuracy ($\alpha^*_{\epsilon, \delta}$), not the runtime cost once a target accuracy is fixed.
• Tightness: Modifications to existing algorithms (Phased SGD) show this bound is nearly tight.

4. Reductions between ERM and SCO

The paper demonstrates that DP-SCO is no harder than DP-ERM (up to polylogarithmic factors) via a reduction that incurs only polylog(n) overhead in runtime and privacy. This implies that characterizing the complexity of DP-ERM is sufficient for understanding DP-SCO in most regimes.

Significance and Claims

The authors position this work as the first to provide oracle complexity lower bounds that leverage differential privacy beyond the local privacy model.

• Runtime Penalty: The results formally demonstrate that a class of private optimizers (those using private oracles) incur a dimension-dependent runtime penalty compared to non-private optimizers. In the non-private setting, the complexity is $\Theta(1/\alpha^2)$ for non-smooth functions; the private setting introduces a factor of $\sqrt{d}$ or $d$ depending on the regime.
• Practical Relevance: The private oracle model is motivated by practical scenarios such as federated learning and distributed training, where untrusted servers query nodes for gradients. The findings suggest that small batch sizes, often used for privacy amplification, fundamentally degrade runtime performance in high dimensions.
• Limitations of Quantization: The information-limited oracle result provides a theoretical justification for the limits of gradient quantization in private settings, showing that compressing gradients below a certain threshold necessitates a proportional increase in the number of queries.

The paper concludes that while algorithmic advances have improved upper bounds, the fundamental cost of privacy in terms of oracle complexity is now better characterized, revealing a trade-off between dimensionality, batch size, and privacy that was previously not fully understood in the central DP model.