Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

Summary

The paper investigates the problem of differentially private stochastic convex optimization (SCO) under the heavy-tailed setting and achieves a nearly optimal rate of $G_2 \cdot \frac{1}{\sqrt{n}}+G_k\left(\frac{\sqrt{d}}{n \varepsilon}\right)^{1-\frac{1}{k}}$. Specifically, it first provides results using Clipped-DP-SGD in the differentially private empirical risk minimization (DP-ERM) framework and then utilizes generalization techniques to offer similar results in the population case. Finally, it explores the heavy-tailed DPSCO.

Strengths

1. The paper provides a nearly optimal bound for DPSCO in the heavy-tailed setting.

Weaknesses

1. Section 3 is not very clear. The connection between Sections 3.1 and 3.2 is not well explained. 2. The presentation needs improvement. One of the most important parts, Population-level Localization, is placed on the last page and is only briefly introduced and discussed. For example, how to choose parameters like $\lambda$ in Algorithm 2 and what $\Delta 4^i$ in Equation 8 represents should be explained.

Questions

NA

Rating

5

Confidence

3

Soundness

3

Presentation

1

Contribution

2

Limitations

NA

Summary

This paper addresses differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where previous assumptions of uniform Lipschitz constants are relaxed to bounded k-th moments. The authors introduce a new reduction-based framework that adapts strategies from the uniform Lipschitz setting, enabling optimal rates up to logarithmic factors under (ε,δ)-approximate differential privacy. They propose several algorithms, including an optimal algorithm for known Lipschitz constants, a near-linear time algorithm for smooth functions, and an optimal linear-time algorithm for smooth generalized linear models. A novel population-level localization framework is also presented, overcoming technical barriers and providing robust bounds on excess population loss without stringent gradient moment assumptions. This work advances the theoretical and practical understanding of DP-SCO with heavy-tailed gradients, outperforming previous approaches in handling real-world data challenges.

Strengths

1. The paper introduces a novel reduction-based framework for handling heavy-tailed gradients in differentially private stochastic convex optimization (DP-SCO). This innovative approach enables the achievement of near-optimal rates and overcomes limitations of previous methods, marking a significant advancement in the field. 2. The proposed method bypasses the need for bounding $\mathbb{E}b_{\mathcal{D}}^2$

Weaknesses

1. Referring to Corollary 2 in Line 4 of Algorithm 3 reduces readability. To enhance clarity, it would be beneficial to specify the algorithm $\mathcal{A}$ (from Corollary 2) clearly, at least within the proof. While leaving the optimization oracle as a black box might help generalize the framework, it makes the algorithm harder to follow if the instantiations are not highlighted. 2. The motivation of the population-level localization could be further clarified.

Questions

1. To solve population-level localization, could one use the same (or slightly adjusted) method for the localization of the empirical minimizer? 2. How does the sample split parameter $J$ affect the utility of Algorithm 3? 3. Should $G_2^2$ and $G_k^k$ on line 7 be $G_2$ and $G_k$?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

.The paper studies DP-SGD under the assumption that the gradients have heavy-tailed phenomenon. This has been recently motivated and studied a lot by recent works. The authors claim to achieve optimal rate for this problem.

Strengths

They obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error that depends on $\frac{G_1}{\sqrt{n}} + G_k(\sqrt{d}/nk)^{1-1/k}$ under approximate-DP guarantee. They additionally study this problem under well-studied assumptions: Lipschitz constant assumption, smooth convex functions, and smooth generalized linear model. I haven't checked the proof, but the paper is definitely an accept considering it solves a problem in this domain.

Weaknesses

N/A

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper gives three main results. The first is a nearly optimal (losing a few logarithmic factors) excess loss rate for differentially private stochastic convex optimization (DP-SCO) when the gradient norms have $k$ bounded moments. In particular, they achieve the optimal excess loss under $\rho$-concentrated differential privacy (CDP) of $\frac{G_2 D}{\sqrt{n}} + G_kD \cdot \left(\frac{\sqrt{d}}{n\sqrt{\rho}} \right)^{1-1/k}$ where $G_i$ denotes the uniform upper bound on the $i$th moment of the gradients and $D$ is the diameter of the domain. This improves over the prior state of the art [LR23] by a factor of $G_kD \cdot \left(\frac{\sqrt{d}}{n\sqrt{\rho}} \right)^{1/k}$. This improvement is increasingly pronounced as we decrease the number of gradient moments that we assume are bounded, which is probably the important regime in this work. As I understand, the main technical innovation is a "population-level localization framework", through which the authors are able to control the population excess risk without having to argue about the variance of the bias term arising from gradient clipping. The second main result is an algorithm that achieves the optimal excess risk when each sample function arrives with a known Lipschitz constant. This yields algorithms for privately learning a generalized linear model with the optimal excess risk. This follows from a clean reduction to the case where we know that our losses are uniformly Lipschitz. The third main result is an improved query complexity for optimizing smooth functions. The algorithm follows from an application of the sparse vector technique.

Strengths

The algorithms seem very natural, the analysis looks clean, and the results yield quantitative improvements over prior work. Therefore, I think this work is an important contribution to private convex optimization. The ideas are cleanly explained and at least on a surface level make sense to a complete outsider to the field (such as myself).

Weaknesses

Can't really think of anything significant. A natural criticism I anticipate is that the improvement over [LR23] is pretty minor when $k$ is large, but given that the authors get the optimal result and [LR23] doesn't, this doesn't seem like a real issue.

Questions

N/A

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes

Summary

This paper studies the problem of differentially private stochastic convex optimization with heavy-tailed gradients. This paper points out that in typical optimization research, the assumption of uniformly G-Lipschitz, while convenient for bounding sensitivity, does not always hold. Based on this weakness, the authors studied k-heavy-tailed DP-SCO. The author obtains near-optimal algorithms that lie in the clipped DP-SGD subroutine and ensure the private minimization of a regularized ERM problem under k-heavy-tailed DP-SCO conditions. This method yields points that closely approximate the minimizer of population loss, verified through Markov’s inequality. Updates post response: - I find the lack of experiments a bit underwhelming, and the authors' response didn't really convince me why this should not be part of this paper. Data privacy is a highly practical question that should be of strong interest to practitioners. The lack of practical implications is thus concerning. - The paper does not have a conclusion section, which is very strange for a NeurIPS paper. I have been reviewing NeurIPS submissions for many years; It is really awkward for a paper to not have a conclusions section. Not having a conclusions section also means that the authors did not carefully think about the "Limitations" of their work, which is a requirement as per NeurIPS submission guidelines. - Lastly, I wonder what are some of the broader impacts/implications of this work. It would be helpful if the authors could add some discussions about this. Again, I feel like this would require a proper "conclusions" section added to the paper. - While reading through the paper I noticed many notational inconsistencies and concepts that have not been clearly explained (please see concrete examples under the list of questions below), I suggest the authors to carefully proof read their paper and making improvements on explaining their work. This will help broaden the impact of this research. Disclaimer: Please be aware that due to the rather short reviewing time, I have not been able to check all the proof details in the appendix.

Strengths

- This paper provides a comprehensive analysis of prior work, enabling readers to quickly understand the limitations of previous research on DP-SCO and why the authors believe this work is necessary. - This paper conducts solid theoretical research and has a profound understanding of the k-heavy-tailed DP-SCO problem. The entire paper is filled with rigorous derivations, providing a theoretical foundation for future research.

Weaknesses

- Experiments could be added to validate the proposed algorithm for readers to better understand the key takeaways. - The paper's organization could be improved, and the contribution can be better highlighted.

Questions

- Why is the k-heavy-tailed assumption more common than the uniformly G-Lipschitz assumption? Intuitively, the uniform is indeed a weaker assumption, but I would like more direct evidence to prove the necessity of using the k-heavy-tailed assumption. - What are the comparisons between the bounds under the k-heavy-tailed assumption with those of prior work? Please comment on this - Is it possible to provide the convergence analysis of the proposed algorithm? - From equation (1) to equation (2), what's the difference between $G$ and $G_2$? - In line 45, can you give a specific example of what you mean by "heavy-tailed gradients"? When might readers expect this condition to hold in practice (e.g., in the training of a neural network)? - While citing a paper, can you please properly cite the author's name(s) using \cite{}, as opposed to things like [LR23]? - In the introduction, can you please clarify exactly under what notion of DP your results will hold? Note: I'm seeing multiple versions of DP definitions in section 2, page 5, thus prompting this question. - Is Theorem 1 (at the bottom of page 9) supposed the main result in your paper? - What are some of the broader impacts/implications of your work? Please comment on this.

Rating

3

Confidence

4

Soundness

2

Presentation

1

Contribution

2

Limitations

Limitations are discussed on page 32.

Response to authors

Thanks for the clarification. I look forward to seeing more discussion in the revised paper. I've increased my score.