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

• URL: http://arxiv.org/abs/2604.06492v1
• Date: Tue, 07 Apr 2026 21:54:29 GMT
• Title: Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails
• Abstract summary: We study convex optimization with heavy-tailed gradients under pure epsilon-differential privacy (DP)<n>Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded k-th moment.<n>Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss.
• Score: 10.43808453274953
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure epsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded k-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. The minimax optimal rate for approximate (epsilon, delta)-DP SCO is known in this setting, but the pure epsilon-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure epsilon-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in polynomial time with probability 1 when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes - including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes - we achieve the same excess-risk guarantee in polynomial time with probability 1 even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our excess risk upper bound with a novel high probability lower bound.

Related papers

• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  We study the problem of differentially private convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a $ktextth$-moment bound on the Lipschitz constants of sample functions rather than a uniform bound. We propose a new reduction-based approach that enables us to obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error $Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon)1
  arXiv  Detail & Related papers  (2024-06-04T21:26:29Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations [52.031701581294804]
  Lipschitz bounds for neural networks can be computed with upper time preservation guarantees. Our paper bridges the gap and extends Lipschitz beyond slope-restricted activation functions. Our proposed analysis is general and provides a unified approach for estimating $ell$ and $ell_infty$ Lipschitz bounds.
  arXiv  Detail & Related papers  (2024-01-25T09:23:31Z)
• Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity [5.866816093792934]
  We show that a wide class of continuity algorithms, including the subgradient method, preserve the $mathO convergence rate with constant failure rate. Our analyses rest on rather weak assumptions: the Lipschitz parameter can be either bounded by a general growth function of $|x|$ or locally estimated through independent random samples.
  arXiv  Detail & Related papers  (2024-01-25T06:06:31Z)
• Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter [14.040676498310198]
  We study differentially private (DP) inequality optimization (SO) with loss functions whose worst-case Lipschitz parameter over all data may be infinite. For smooth loss functions, we provide linear-time algorithms with state-of-the-art excess risk. We also provide the first algorithm to handle non-optimal convex loss functions.
  arXiv  Detail & Related papers  (2022-09-15T16:03:23Z)
• Beyond Uniform Lipschitz Condition in Differentially Private Optimization [28.04430869054056]
  Most prior results on differentially private gradient descent (DP-SGD) are derived under the simplistic assumption of uniform Lipschitzness, i.e., the per-sample gradient is uniformly uniform. We provide principled guidance choosing the norm over-dependent in our general version of Lipschitzness when the per-sample Lipschitz constants are bounded.
  arXiv  Detail & Related papers  (2022-06-21T20:11:30Z)
• Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks [77.82638674792292]
  Lipschitz constants of neural networks allow for guarantees of robustness in image classification, safety in controller design, and generalizability beyond the training data. As calculating Lipschitz constants is NP-hard, techniques for estimating Lipschitz constants must navigate the trade-off between scalability and accuracy. In this work, we significantly push the scalability frontier of a semidefinite programming technique known as LipSDP while achieving zero accuracy loss.
  arXiv  Detail & Related papers  (2022-04-02T11:57:52Z)
• Private Non-Convex Federated Learning Without a Trusted Server [7.971065005161566]
  We propose novel algorithms for cross-silo learning (FL) with non-trusted loss functions and data from people who do not trust other silos. Our algorithms attain the optimal strongly convex, homogeneous (i.i.d.) for ISRL-DP FL without assuming convexity or i.i.d. data. Numerical experiments show that our algorithm has better accuracy than baselines for most privacy levels.
  arXiv  Detail & Related papers  (2022-03-13T19:17:15Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data [13.465471169118974]
  We study convex optimization with heavy-tailed data under the constraint of differential privacy. We prove nearly-matching lower bounds under the constraint of pure differential privacy, giving strong evidence that our bounds are tight.
  arXiv  Detail & Related papers  (2021-06-02T17:45:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.