Search papers, labs, and topics across Lattice.
This paper characterizes the minimax optimal excess-risk rate for pure epsilon-DP stochastic convex optimization (SCO) with heavy-tailed gradients, closing a gap in the literature. They achieve this rate with a polynomial-time algorithm, even when the Lipschitz parameter is unbounded for structured problem classes like hinge/ReLU-type losses. The approach uses a novel framework for privately optimizing Lipschitz extensions of the empirical loss, and the upper bound is complemented with a high probability lower bound.
Pure differential privacy no longer lags behind approximate DP in heavy-tailed stochastic convex optimization: this work establishes matching minimax optimal rates.
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.
