PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Stochastic Convex Optimization with Optimal Rates

Raef Bassily, Vitaly Feldman, Kunal Talwar, Abhradeep Thakurta

arXiv:1908.09970v1cs.LGcs.CRcs.DSstat.ML

TL;DR

The paper addresses a gap in population-loss guarantees for differentially private stochastic convex optimization. It combines existing private algorithms with uniform-stability analyses, showing optimal population-loss rates up to logarithmic factors and extending the approach to non-smooth losses and objective perturbation.

  • Problem

    Known private convex-optimization results focused on empirical loss, leaving a significant gap in bounds for population loss.

  • Method

    The paper analyzes private noisy SGD, Moreau-Yosida smoothing, and objective perturbation using algorithmic stability to control generalization.

  • Results

    O(1/√n) is achievable for DP-SCO whenever d = O(n), matching known lower bounds up to logarithmic factors.

  • Takeaways & Limitations

    Private SCO can attain the statistically optimal non-private rate in the parameter regime d = O(n), unlike DP-ERM’s dimension-dependent privacy cost.

  • Takeaways & Limitations

    Objective perturbation’s privacy guarantee requires additional assumptions, notably that each loss Hessian has rank at most one.

Abstract

from arXiv · show

We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d. samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of $1/\sqrt{n}$ as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of $1/n^{1/4}$. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.

1 Introduction

The paper studies the gap between private stochastic convex optimization’s population-loss bounds and shows that optimal rates are achievable using stability-based analyses and existing private algorithms.

  • DP-SCO seeks to minimize population loss from i.i.d. samples while satisfying differential privacy.The problem covers settings including mean estimation, least-squares regression, and convex surrogate classification losses.
  • Uniform-convergence bounds can be suboptimal, becoming Ω(1) when n = Θ(d), despite non-private excess population loss of O(1/n).This limits the usefulness of empirical-to-population-loss arguments in high-dimensional settings.
  • Existing DP-SCO approaches derived population-loss guarantees from privacy generalization or stability, but the resulting bounds were suboptimal.The stability approach used strongly convex regularization to control generalization.
  • 1.1 Our contribution: O(1/√n) is achievable when d = O(n), matching known lower bounds and contrasting with dimension-dependent privacy costs for DP-ERM.The result gives private SCO the statistically optimal rate in this regime.
  • 1.1 Our contribution: Noisy mini-batch SGD, Moreau-Yosida smoothing, and objective perturbation provide approaches for smooth and non-smooth losses.Objective perturbation achieves optimal DP-SCO bounds under additional assumptions and can use O(n log n) gradient evaluations.
  • 1.1 Our contribution: The analysis emphasizes uniform stability as a tool for studying differentially private statistical analyses.The authors suggest applications beyond this problem class.

2 Preliminaries

The preliminaries define SCO, empirical and population losses, differential privacy, DP-SCO, and uniform stability over a convex parameter domain.

  • The parameter space W is a convex, compact subset of R^d, and the loss maps parameters and data points to real values.The notation also introduces an arbitrary data domain Z and distribution D.
  • Empirical loss averages losses over the sample, while population loss takes expectation over the data distribution.Excess losses compare these quantities with their respective minima.
  • Uniform stability bounds how much an algorithm’s loss behavior changes when one sample is replaced.The paper uses stability to upper-bound expected population loss by stability plus expected empirical loss.
  • SCO uses i.i.d. samples to generate an approximate minimizer of the population loss for a convex loss function.Accuracy is measured by expected excess population loss.
  • Differential privacy requires neighboring datasets to induce similar output-event probabilities, with typical meaningful parameters ε < 1 and δ ≪ 1/n.DP-SCO is an SCO algorithm satisfying this privacy condition.

3 Private SCO via Mini-batch Noisy SGD

The smooth-loss result analyzes mini-batch noisy SGD as a private SCO method, combining privacy, empirical-loss, and stability guarantees to obtain population-loss bounds.

  • Mini-batch noisy SGD is designed for convex, Lipschitz, smooth losses over a convex parameter set.The algorithm samples mini-batches with replacement and adds Gaussian noise during gradient updates.
  • Algorithm 1 is (ε, δ)-differentially private.Its privacy analysis uses moments accounting and privacy amplification through sampling.
  • Optimizing the step size and iteration count yields the theorem’s stated excess population-loss bound.The final population guarantee combines empirical-loss and stability bounds.
  • The algorithm’s empirical-loss analysis separates the optimization error from the additional empirical error caused by privacy.The bound is obtained using the stochastic-oracle analysis and the chosen Gaussian-noise variance.
  • Uniform stability of noisy SGD extends stability analyses for gradient methods and requires η ≤ 2/β.This stability result controls the population-versus-empirical loss gap.

4 Private SCO for Non-smooth Losses

For non-smooth convex losses, the paper smooths each loss with the Moreau-Yosida envelope and applies ANSGD, obtaining optimal population loss for the original loss while enabling an efficient proximal implementation.

  • Reduction via smoothing: Moreau-Yosida smoothing reduces non-smooth private SCO to a smooth-loss problem while preserving an optimal population-loss guarantee for the original loss.The smoothed losses are analyzed through their convexity, smoothness, and Lipschitz properties.
  • Proximal implementation: The Moreau envelope connects gradient evaluation to proximal minimization, allowing approximate proximal operations to replace generally inefficient exact smoothing.Evaluating the smoothed gradient can be reduced to approximately minimizing a strongly convex function.
  • Smoothed objectives: The smoothed empirical and population losses are defined by averaging or taking expectations of the individual Moreau envelopes.For each data point z, ℓβ(·, z) denotes the smoothed loss; these induce bLβ(·; S) and Lβ(·; D).
  • Population-loss guarantee: ANSGD run on appropriately β-smoothed losses achieves the stated excess population-loss bound with respect to the original non-smooth loss.The parameter β is set according to the Lipschitz constant and domain bound, with η and T chosen as in the smooth-loss theorem.

Computationally efficient algorithm AProxGD (NSGD + Prox)

AProxGD implements the non-smooth reduction using approximate proximal operators, preserving privacy, accuracy, and stability while achieving the optimal population-loss bound with polynomial-time gradient-based computation.

  • Algorithm: AProxGD replaces each gradient of the non-smooth loss with an approximate gradient of its Moreau-smoothed loss computed by an approximate proximal operator.The approximation uses a computationally efficient proximal routine for a strongly convex subproblem.
  • Privacy: The approximate proximal operator preserves the ANSGD privacy guarantee because its gradient norm, and therefore mini-batch sensitivity, remains essentially unchanged.The approximate gradient norm is bounded by L(1 + 1/n), so the same privacy analysis applies.
  • Accuracy: The approximation adds at most 2LM/n to the empirical-loss bound, and this term is dominated by the other error terms.Thus the approximation has no significant impact on the final empirical-loss rate.
  • Stability: Non-expansive gradient updates prevent approximation errors from being amplified, so stability changes by only an additive term and remains essentially the same.Across T updates, the accumulated output error is bounded by TηL/n, with the stability contribution bounded by an additive TηL^2/n term.
  • Overall guarantee: AProxGD is computationally efficient and achieves the optimal population-loss bound.The paper establishes this after combining the privacy, empirical-error, and stability analyses.

5 Private SCO via Objective Perturbation

Objective perturbation attains optimal population loss for a broad subclass of smooth convex losses by combining noisy linear perturbation with regularization-induced stability; an approximate version also offers near-linear oracle complexity.

  • Objective perturbation: Objective perturbation adds a noisy linear term and regularization to the empirical loss, using regularization to improve generalization through stability.Privacy requires additional Hessian-related assumptions on the loss.
  • Privacy guarantee: Under the rank-one Hessian assumption and β ≤ ϵnλ, AObjP is (ϵ, δ)-differentially private.The theorem assumes twice differentiability and Hessian rank at most one for every loss and domain point.
  • Population-loss guarantee: With an appropriate λ, AObjP achieves asymptotically optimal excess population loss.The proof combines the optimal empirical-loss bound with the stability of regularized ERM and optimizes λ.
  • Scope: The objective-perturbation analysis is scoped to additional Hessian assumptions, although the rank condition can be extended to higher rank without changing asymptotic population-loss guarantees.The paper notes that a more general Hessian condition can suffice for privacy.
  • Approximate objective perturbation: AObjP−App replaces exact optimization with approximate optimization and Gaussian perturbation while retaining (ϵ, δ)-differential privacy and nearly the same population loss.Its privacy guarantee is established under the same β ≤ ϵnλ condition.
  • Oracle efficiency: AObjP−App achieves O(n log n) gradient evaluations and asymptotically optimal excess population loss when SVRG is used as the optimizer.The oracle-complexity conclusion treats ϵ, M, and L as constants.

A Proof of Lemma 3.4

The proof bounds ANSGD’s stability by comparing trajectories on neighboring datasets and tracking how often the differing sample enters each mini-batch.

  • Neighboring datasets: The proof compares ANSGD trajectories on datasets differing in one sample and defines their iterate difference ξt.The comparison includes the algorithm’s mini-batch indices and noise vectors.
  • Inductive argument: An induction on t establishes the trajectory-distance claim, beginning with the identical initialization at t = 0.The argument follows a stability proof technique for stochastic gradient methods.
  • Update control: If the differing index appears r times in a mini-batch, non-expansiveness of the gradient update controls the next trajectory distance.The proof fixes the current randomness before accounting for the differing sample’s occurrences.
  • Averaging and completion: The occurrence count r is Binomial with mean m/n, so averaging over mini-batch sampling and noise completes the recursive bound.The final Lipschitz-loss step converts trajectory distance into a loss-stability bound.

B Proof of Lipschitz property of Moreau envelope (Lemma 4.3)

The Moreau envelope has gradient norm at most 2L, established by bounding the distance to its minimizer using Lipschitzness and then applying the gradient identity.

  • ||∇fβ(w)|| ≤ 2L follows by combining ||w − v*|| ≤ 2L/β with ||∇fβ(w)|| = β||w − v*||.The distance bound uses that f is L-Lipschitz.

C Optimality of Our Bounds

The paper establishes tightness of its upper bounds through a lower-bound argument and a reduction from private SCO to private ERM. The reduction samples from the empirical distribution, transfers population-loss guarantees to empirical loss, and proves privacy via sampling stability and group differential privacy.

  • The upper bounds in Sections 3 and 4 are tight up to logarithmic factors in 1/δ.They match a lower bound stated in the paper.
  • The population-loss lower bound is the larger of the non-private population-loss lower bound and the private empirical-loss lower bound.The latter transfers because a lower bound on excess empirical loss implies nearly the same population-loss lower bound.
  • A private SCO algorithm with expected excess population loss at most γ yields a private algorithm with expected excess empirical loss at most γ.The reduction applies to any distribution on the domain and any γ > 0.
  • The reduction constructs the empirical distribution from S and samples T from that distribution before applying the private SCO algorithm.The sampled dataset T is then used as the input to algorithm A.
  • The constructed algorithm satisfies Δ̂L(B; S) ≤ γ because population loss under the empirical distribution equals empirical loss on S.Privacy is analyzed by comparing samples generated from neighboring datasets.
  • With high probability, the neighboring sampled datasets differ in at most 4 log(2/δ) points, enabling a group-privacy argument for B.The probability bound uses Chernoff’s inequality, while the privacy conclusion uses that A is differentially private.
Loading 1908.09970v1…