2024/03/05 by T. González, González, Tomás, Cristóbal Guzmán +3 · 2 citations
Business, Management and Accounting · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #Advanced Queuing Theory Analysis #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2403.02912
openalex publication_date 2024/03/05 · openalex created_date 2024/03/07 · openalex updated_date 2026/07/28
We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the ℓ1 setting. We propose (ε, δ)-DP algorithms based on stochastic mirror descent that attain nearly dimension-independent convergence rates for the expected duality gap, a type of guarantee that was known before only for bilinear objectives. For convex-concave and first-order-smooth stochastic objectives, our algorithms attain a rate of √(log(d)/n) + (log(d)3/2/[nε])1/3, where d is the dimension of the problem and n the dataset size. Under an additional second-order-smoothness assumption, we show that the duality gap is bounded by √(log(d)/n) + log(d)/√(nε) with high probability, by using bias-reduced gradient estimators. This rate provides evidence of the near-optimality of our approach, since a lower bound of √(log(d)/n) + log(d)3/4/√(nε) exists. Finally, we show that combining our methods with acceleration techniques from online learning leads to the first algorithm for DP Stochastic Convex Optimization in the ℓ1 setting that is not based on Frank-Wolfe methods. For convex and first-order-smooth stochastic objectives, our algorithms attain an excess risk of √(log(d)/n) + log(d)7/10/[nε]2/5, and when additionally assuming second-order-smoothness, we improve the rate to √(log(d)/n) + log(d)/√(nε). Instrumental to all of these results are various extensions of the classical Maurey Sparsification Lemma \citePisier:1980, which may be of independent interest.