Private Stochastic Convex Optimization with Tysbakov Noise Condition and Large Lipschitz Constant

Q2

Response We have already make clarification in Remark 1 after we give the definition of zCDP. Here we will explain it again. The main reason here is that in the proof, we need a private version of Fano's lemma (Lemma 6 in our paper). Currently, there are two versions of the private Fano's lemma: one is in the zCDP version and the other one is in the $(\epsilon, \delta)$-DP version [2]. However, compared to the zCDP version, the $(\epsilon, \delta)$-DP version is quite loose for our problem. That is the main reason we choose $\rho$-zCDP in the paper. Notably, as we mentioned, our Algorithms 1-5 are based on the stability analysis and Gaussian mechanism, and they are a one-pass algorithm with no privacy amplification. Thus, these algorithms can be converted to the zCDP version directly.

[2] Acharya, Jayadev, Ziteng Sun, and Huanyu Zhang. "Differentially private assouad, fano, and le cam." Algorithmic Learning Theory. PMLR, 2021.

Q3

Response

Note that $p$ is very important in our algorithm and analysis. We cannot arbitrarily set $p$, it should satisfy $L_f\leqslant n^{p/2}\widetilde{R}_{2k,n}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d\log n}}{\epsilon n})^{\frac{k-1}{k}})$. Intuitively, we explore the potential of using terms like $n^p$ to approximate the magnitude of this constant. The exponent p is employed to regulate the Lipschitz constant, allowing us to omit it from the final bound. As shown in line 444 of the proof, there is an occurrence of the term $n^p$ in both the numerator and the denominator. By assuming that $L_f$ is governed by $O(n^{p/2})$ and selecting an appropriate $\eta$, we are able to remove the dependence on p in the final bound.

W3

Response Thanks for the suggestion. In fact, we are motivated by the fact that while most of the current paper focuses on the loss as either convex or strongly convex, many losses lie between these two categories, i.e., they are not strongly convex but their statistical rate is better than convex ones. So, we want to study the theoretical behaviors of these loss functions.

It has been shown that many machine learning problems beyond the example we provided are not strongly convex but satisfying TNC, which also motivates this work [1,33]. For example:

(1) Piecewise Linear Problems (PLP): $\min_{W}\mathbb{E} [f(w,x)]$. When the objective function is piecewise linear (such as hinge loss) and W is a bounded polyhedron. Then it satisfies $(2, O(1))$-TNC.

(2) Risk Minimization Problems over an $\ell_2$ ball. $\min_{W}\mathbb{E} [f(w,x)]$. When the W is an $\ell_2$-norm ball and $\min_{W}\mathbb{E} [f(w,x)]< \min_{\mathbb{R}^d}\mathbb{E} [f(w,x)]$. Then it satisfies $(2, O(1))$-TNC.

(3) $\ell_1$ Regularized Risk Minimization Problems. For $\ell_1$ regularized problem $\min_{\|w\|_1\leq B}\mathbb{E} [f(w,x)]+\lambda \|w\|_1$, it satisfies $(2, O(1))$-TNC.

Thus, designing appropriate algorithms will give these problems better generalization ability.

Moreover previous studies on TNC always need to assume the data are regular, such as normalized, and they cannot handle cases where these data are heavy-tailed. Thus, it is essential to design algorithms to handle this heavy-tailed and sensitive data.

[1] Liu, Mingrui, et al. "Fast rates of erm and stochastic approximation: Adaptive to error bound conditions." Advances in Neural Information Processing Systems 31 (2018).

In the final version, we will add the above motivations to the introduction section.

W4

Response We disagree with the comment. First, to the best of our knowledge, we still do not know the excess population risk given by clipped SGD with general clipping threshold if the convex loss function is not Lipschitz. We would appreciate it if the reviewer could provide some references, and we would be happy to compare them. Most existing work on the excess population risk of clipped SGD needs to assume the loss function is Lipschitz, and they assume the clipping threshold is the Lipschizt constant, indicating the utility will depend on the Lipschitz constant. From this perspective, our parameter could be much smaller than the Lipschitz constant, and thus, our results are better.

Here we provide an example to show that the moment bound could be far less than the Lipschitz constant: For linear regression on a unit ball W with 1-dimensional data $x_1,x_2\in[-10^{10},10^{10}]$ having Truncated Normal distributions and $Var(x_1)=Var(x_2)\leq 1$, we have $L_f\geq 10^{20}$ while for $k<\infty$, $\tilde{r}_k$ is much smaller than $L_f$, such as $\tilde{r}_2\leq 5,\tilde{r}_4\leq 8,\tilde{r}_8\leq 14$.

W5

Response The review misunderstood our algorithm, note that here we use privacy amplification by shuffling rather than subsampling. Privacy amplification by sampling cannot achieve our results. Moreover, the comment "which results in $\epsilon$ being tiny just for this algorithm to work" is not correct. The requirement of $\epsilon$ comes from the current theorem of privacy amplification by shuffling. As we mentioned in the paper, we showed that using shuffling can significantly improve the previous results. Our algorithm can also remove the Lipschitz assumption.

Q1

Response Our results are totally different from Chen et al [1]:

(1) The problem studied is different. In our paper we focus on DP-SCO for TNC loss and aim to develop the optimal rates of excess population risk. [1] aims to understand clipped DP-SGD for general (non)-convex loss. It is unknown whether clipped DP-SGD can achieve the optimal rate for our problem. In our paper, we develop several new algorithms for optimality.

(2) The utility form is also different. We mainly use excess population risk for the utility, which is the standard utility in the existing literature on DP-SCO or DP-ERM with convex loss. [1] aims to provide a convergence rate for clipped DP-SGD. However, their utility is based on the gradient norm or the inner product with the gradient, and their upper bounds (their Theorem 1 and 5) are incomparable with our results. Actually, [1] mainly focuses on providing some theoretical understanding rather than the excess population risk for the DP-SCO problem. Obviously, their analysis is also totally different from ours.

We believe that the reviewer misunderstood some of our contributions. And we have already make thorough explanation in our paper. Below we will address your concerns.

W1

Response Localization involves iteratively "zooming in" on a solution. In the early phases, when we are far from the optimum $w^*$, we use more samples (larger $n_i$) and a larger learning rate $\eta_i$ to make quick progress. As $i$ increases and $w_i$ gets closer to $w^*$, fewer samples and a slower learning rate suffice. Since the step size $\eta_i$ shrinks geometrically faster than $n_i$, the effective variance of the privacy noise ($\eta_i^2\sigma_i^2$) decreases with $i$. This prevents $w_{i+1}$ from deviating too far from $w_i$ and hence from $w^*$. We further enforce this localization behavior by increasing the regularization parameter $\lambda_i$ and shrinking $D_i$ over time. Additionally, we used the minimizer from the previous phase as the initialization for the subsequent phase. We choose $D_i$ to be as small as possible while ensuring that $argmin_{w\in\mathcal{W}} \widehat{F}_i(w)\in\mathcal{W}_i$. This constraint ensures that Algorithm 2 can find $w_i$ with minimal excess risk and also leads to the final estimation for $w_l$. Details in Line 740, Theorem 8 show how the tiny diameters and stepsizes contribute to the estimation. Especially, Line 794 shows how iteration helps.

In Algorithm 4, the updates are divided into m stages, and we perform LNC-GM at each stage. Each use of Alg3 is initialized from the endpoint obtained from the previous stage， inheriting some property from last stage. Line 950, Lemma 5 shows what we do exactly in each step.

In Algorithm 6, we randomly permute each batch before executing the main algorithm, which helps reduce variance. This technique, combined with the methods mentioned above, allows us to improve the upper bound in Theorem 6. In line 6, our clipping method eliminates the need for the Lipschitz property of loss functions.

Similar iterated idea is introduced into Algorithm 5 and 7. For Algorithm 5, we partition the dataset aggressively while keeping the convex set to be projected invariant, which is necessary, for instance, in Line 1079 and from Line 1088 to 1108, proof of theorem 3.

W2

Response We cannot agree with the comment; our algorithm is totally different from the localization algorithm (Algorithm 2) of [1]:

(1) The locality algorithm in [1] is based on the stability of projected SGD, meaning that it depends on the Lipschitz condition, and thus, all of their results depend on the Lipschitz constant. However, as we mentioned, our paper aims to eliminate this constant and we aim to use the moment instead. Thus, our algorithm (Algorithm 3) is more complicated.

(2) The locality algorithm in [1] is for general convex loss while we consider the TNC loss. However, directly using the stability of SGD cannot leverage such property. Thus, we need to design a new locality algorithm (our Algorithm 3).

(3) The details and the main idea of our Algorithm 3 are also different from the locality algorithm in [1]. Specifically, for each phase, we need to consider a regularized function (step 5) and perform a clipped version (the clipping threshold is also important) of the gradient descent method over a shrunk domain set $\mathcal{W}_i$. These are crucial for our analysis. However, in the locality algorithm of [1], during each phase, it just simply performs the projected gradient descent over the original domain set.

Thus, these two algorithms are incomparable.