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

Thank you for your reviewing efforts and feedback.

Section 3: We apologize for the lack of clarity in Section 3. In Section 3.1, we propose Algorithm 1, which achieves good performance on an empirical loss assuming the dataset satisfies a property (bounded $b_{\mathcal{D}}$, see (6)). In Section 3.2, we show we can use Algorithm 1 to get a solution with respect to the population function if the dataset is drawn from a heavy-tailed distribution. We included a description of this relationship at the start of Section 3 (Lines 226-235), but will include more connective tissue between Sections 3.1 and 3.2.

Presentation: Due to page limitations, we did not add many details about the population-level localization in the main paper (some details were deferred to the appendix). We will revise our final version and add more details and intuitions to clarify it. Currently, a short description is given in Lines 85-92, and full proof of its guarantees is given in Proposition 2 in the main body. We provided additional intuition of why we developed this technical tool and its comparison to prior work in our response to Reviewer KReZ, and will incorporate this response into our revision. For your other questions, $\lambda$ is a hyperparameter that we optimize in Line 295 to minimize the expression on the previous Line 294, and $\Delta$ is a scaling of the objective error defined in Line 301.

We hope this discussion was clarifying, addressed some of your concerns, and elevated the merits of our paper in your view.

Thank you for your reviewing efforts. We appreciate your positive feedback. Please feel free to let us know if you have any questions or suggestions.

Thank you for your careful reading; we address your questions here.

Re: clarity, we agree with your suggestion, and will add a description of the algorithm and the specific guarantees we are using about it to help the reader. Thanks for pointing this out.

Re: population-level localization, we will add an additional description after Line 85. The motivation for population-level localization is that we wish to aggregate empirical solutions to multiple datasets, some of which satisfy assumptions of Corollary 1 (i.e., have small $b_{\mathcal{D}}$), and some of which do not. However, each dataset has a different empirical minimizer, so it is unclear which to argue about convergence to. We instead aggregate solutions close to a population-level minimizer, shared across datasets. Previous localization frameworks could not handle the setting we consider, as described in Section 1.2, prompting our new development. In particular, previous localization frameworks used non-strongly convex losses, which have known difficulties in generalizing to population-level objectives [SSSS09].

Q1: Our population-level localization is inspired by and closely related to frameworks used to minimize an empirical loss. Both rely on stochastic access to the input, but a key difference is that we cannot verify our empirical dataset actually satisfies a key assumption used to get the optimal rate (bounded $b_{\mathcal{D}}$), so the empirical solution could be meaningless. This is why we target population-level objectives, which can aggregate multiple datasets.

Q2: Suppose that we can get $x_{i,j}$ such that $\|x_{i,j}-x_i\|\le R(i,J)||$ with probability at least 0.55. Then $J$ can not be too small, to make use of a Chernoff bound to show at least half of the $x_{i,j},j\in [J]$ are close to $x_i$. On the other hand, the larger $J$ is, the smaller the privacy budget we can use to generate $x_{i,j}$, since we need to compose over $J$ instances, which hurts our final utility bound. Hence $J$ can not be too small, or too large.

Q3: We believe Line 7 is correct as stated. As assumed in Line 67, $G_j^j$ is the $j^{\text{th}}$ moment.

We appreciate you found our approach innovative, and that our result was a significant advancement. We hope our response was clarifying, and that it elevates the merits of our paper in your view.

Thank you to the reviewers for the clarifications. I will stay moderately positive on this paper, and keep my score.

Thank you for your reviewing efforts, and we appreciate your positive feedback. Please feel free to let us know if you have any questions or suggestions.

Thanks for your valuable feedback. We answer your questions below.

Experiments: The focus of our work is theoretical in nature: developing algorithms that address known gaps in the literature on DP-SCO, a problem of interest in both theory and practice. We believe this goal has significant merit in its own right, as it provides insights that lay the groundwork for future research, both theoretical and experimental. We absolutely agree with the reviewer on the complementary importance of experimental evaluation of theoretical derivations. We chose to restrict our focus, but think that transferring our insights to practice is an exciting and promising direction for future research.

Organization: We take the organization of our paper and presentation of our contributions seriously as concerns, and appreciate the feedback. We would like to kindly request that the reviewer provide some more specific feedback on our organization and presentation. Re: our contributions, all of our key results are described in Section 1.1 (with corresponding formal statements as Theorems 1-4), and compared to prior work in Section 1.2.

Q1: Indeed, the k-heavy-tailed assumption applies to more situations than the uniform Lipschitz assumption, as a distribution can be $k$-heavy-tailed but not $\infty$-heavy-tailed. However, there is a tradeoff in the gains achievable for finite $k$. Our work is the first to obtain an algorithm that gives the best possible tradeoff up to logarithmic factors.

In practice, differentially private neural networks are trained with clipped gradients (see [ACG+16]), due to outliers which create undesirable tail behavior. For more problems in practice where the $k$-heavy-tailed assumption is a more appropriate model than the uniform Lipschitz assumption, we refer the reviewer to the reference [WXDX20], which discusses how biomedicinal and financial research often use heavy-tailed modeling. More generally, power laws are heavy-tailed, and used to model many phenomena in the sciences. We will add additional discussion of this motivation; thank you for raising this point.

Regarding the relative strength of these assumptions, for $k’ > k$, the $k’$-heavy-tailed assumption is stronger than the $k$-heavy-tailed assumption (with appropriate parameters), as a variable can have a finite $k$-th moment but not a finite $k'$-th moment. In this sense, as uniform Lipschitzness is an $\infty$-heavy-tailed assumption, it is the strongest.

Q2: We compared our bounds to existing work in Lines 57-61 of the submission, as well as more in depth in Section 1.3. The heavy-tailed DP-SCO problem is relatively new, and few theoretical guarantees are provided by the literature. The two most relevant works are of [KLL22] and [LR23]: the first requires stringent conditions (such as uniformly smooth loss functions) to guarantee optimality, whereas the former obtains sub-optimal rates that can be polynomially worse than ours. We close the gap left by these prior works, achieving the first near-optimal rate, as well as generalizations in many settings (smooth and/or GLM).

We were not sure if the reviewer meant how our Assumption 1 compared to previous definitions of the problem. Our problem statement is the same as in [LR23]. The problem definition is phrased slightly differently in [WXDX20, KLL22], using a (in our opinion, less natural) coordinatewise bound; we chose the definition consistent with more of the literature, e.g. previous works on private mean estimation [BD14], and uniform Lipschitz DP-SCO.

Q3: We believe all of our algorithms have complete analyses and proofs. For example, Theorem 1 is proven in Section 3 and Appendix A, with a fully specified algorithm description. We are happy to address your concerns, but we would like to again kindly request that the reviewer be specific about which missing convergence analyses they refer to.

We appreciate that you found our research solid and our descriptions comprehensive, providing a good foundation for the problem. We hope our response was clarifying, and that it elevates our contributions from your viewpoint. Thank you for your feedback again.