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

2026-04-09 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Cybersecurity & Data Privacy · Depth: Expert, long

Summary

A new study characterizes the minimax optimal excess-risk rate for pure ε-differentially private (DP) stochastic convex optimization (SCO) with heavy-tailed gradients, achieving this rate up to logarithmic factors. The research addresses a long-standing open problem in pure ε-DP, where prior work focused on approximate (ε,δ)-DP. The proposed algorithm achieves the optimal rate in polynomial time with high probability, and with probability 1 if the worst-case Lipschitz parameter is polynomially bounded. For specific structured problem classes, including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes, the algorithm guarantees the same excess-risk in deterministic polynomial time, even with infinite worst-case Lipschitz parameters. This approach introduces a novel framework for privately optimizing Lipschitz extensions of the empirical loss and provides a new high-probability lower bound.

Key takeaway

For research scientists developing differentially private machine learning algorithms, this work provides a critical advancement for pure ε-DP SCO with heavy-tailed data. You should consider adopting the Lipschitz extension and double output perturbation framework to achieve minimax optimal excess risk rates, especially when dealing with unbounded gradient distributions where traditional Lipschitz assumptions are too restrictive or vacuous. This approach offers a computationally efficient path to strong privacy guarantees.

Key insights

Optimal pure ε-DP heavy-tailed SCO rates are achieved via Lipschitz extensions and double output perturbation.

Principles

• Bounded k-th moment assumption allows for heavy-tailed gradients.
• Lipschitz extensions reduce heavy-tailed ERM to Lipschitz ERM.
• Double output perturbation ensures privacy and accuracy.

Method

The method involves reducing heavy-tailed SCO to regularized ERM, optimizing Lipschitz extensions via a jointly convex reformulation and adaptive projected subgradient methods, and applying a double output perturbation for privacy.

In practice

• Use Lipschitz extensions for heavy-tailed gradient problems.
• Employ adaptive projected subgradient for unknown Lipschitz constants.
• Apply output perturbation for pure ε-DP guarantees.

Topics

• Pure ε-Differential Privacy
• Stochastic Convex Optimization
• Heavy-tailed Gradients
• Minimax Optimal Rates
• Lipschitz Extension

Best for: Research Scientist, AI Scientist

Related on AIssential

• Minimax Optimal Two-Sample Testing under Local Differential Privacy — Minimax optimal two-sample tests under LDP are developed for multinomial and continuous data.
• Portfolio Optimization Proxies under Label Scarcity and Regime Shifts via Bayesian and Deterministic Students under Semi-Supervised Sandwich Training — Hybrid optimization-learning, particularly Bayesian distillation, enhances portfolio robustness and cost-efficiency in data-scarce, non-stationary markets.
• Faster Rates For Federated Variational Inequalities — Improved algorithms and analysis yield faster convergence rates for federated stochastic variational inequalities.
• Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation — The paper provides information-theoretic lower bounds for bit-constrained stochastic optimization, linking it to compressed Gaussian mean estimation.
• Differentially Private Multivariate Medians — Differentially private multivariate medians offer robust location estimation with strong finite-sample performance guarantees.
• Convex training of Lipschitz-regularized shallow neural networks — A convex restriction efficiently solves non-convex Lipschitz-regularized shallow neural network training, enhancing adversarial robustness.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.