Public-data Assisted Private Stochastic Optimization: Power and Limitations

• Presentation:

We will add a table to our updated version as you suggest and clarify tightness of the rates. Please see the global response PDF for this table.

• Missing conditions on $n_\text{pub}$ :

Theorems 3, 6, and 7 claim the rate is achievable given access to some number of public samples which is at most $n_\text{pub} = \tilde{O}(n_{\text{priv}}\epsilon)$. We will clarify the phrasing of these theorems to make this more clear.

• The significance of Theorem 3 is unclear. Similar algorithms and similar improvements of dimension dependence were obtained in other works. The authors mention line 245 that their result avoids "many of the strong assumptions seen in previous work" without giving any details. What are these assumptions and how does Theorem 3 compare to existing results?

With regards to the [PHYS24] paper we cite, in addition to the assumptions we make, [PHYS24] additionally requires that the underlying distribution satisfies both a large margin condition and a low rank assumption (see Definition 3 and Theorem 1 of their paper). Further, they also only provide a statement for the privacy regime $\epsilon = o(1)$. We will add these details to the revision.

• Corollaries 2 and 3 are frankly hard to interpret, and their significance is unclear to me. Maybe more effort is needed in this section.

Corollary 2 shows that with enough public data, it is possible to privately learn feed-forward neural networks without paying any explicit penalty for the network width (the rate only scales with the norm of the weights). Corollary 3 shows that (with access to public data) it is possible to obtain dimension-independent rates for constrained non-Euclidean GLMs. In both cases, such a width/dimension independence was previously unknown. We will add such comments to the revision.

• The general message of the paper, that "more sophisticated attempts at leveraging public data will yield no benefit" (in the labeled case), should be toned down a bit. While the new bounds indeed show some fundamental limits, these come under assumptions, and improvements were in fact shown for certain classes of problems like linear regression, as in some of the papers that were cited lines 28-29, (most of these were cited without discussion unfortunately).

As with all theoretical works, our results come with certain assumptions, and our statements are made with respect to those assumptions. The class of problems we study for our lower bounds, Lipschitz losses over compact parameter space, are one of the most commonly studied classes in the DP optimization literature. Further, we do not believe the overall tone of our paper suggests that more sophisticated algorithms are useless in other settings. To the contrary, half our paper is devoted towards showing that in a slightly different setting (unlabeled public data) more sophisticated algorithms are useful.

• What do the authors mean by "the non trivial regime $n_{\text{priv}} = \Theta(n)$ and $n_{\text{pub}} = o(n)$"? Do you mean either of these is true? (if so, it would be clearer to use or, not and).

We mean "and" for this statement. The regime $n_{\text{priv}} = \Theta(n)$ and $n_{\text{pub}} = o(n)$ is the only non-trivial regime, at least if one is interested in asymptotics. This is because if either condition is not true, one can discard the private dataset and still have a dataset of size $\Theta(n)$; i.e., one does not have to worry about privacy. This is obvious if $n_{\text{pub}}=o(n)$ is not true. If $n_{\text{priv}}=\Theta(n)$ is not true, then it must also be the case that $n_{\text{pub}} = \Theta(n)$ since by definition $n = n_{\text{pub}} + n_{\text{priv}}$. We will elaborate in the revision.

• In the discussion following Cor.3, how do the $\log(d)$ terms appear?

The $\log{d}$ term appears from the choice of the function $\Delta(w) = \frac{\log{d}}{2}\Vert w \Vert_{1+1/\log{d}}$ -- see discussion in line 366 in the paper. This choice is standard in the $(\ell_1,\ell_\infty)$-case -- see referenced work [FGV17]. We will revise the Corollary and discussion following it to make it clear.

• Response to Questions:

Differentially private subroutines often incur some penalty proportional to the problem dimension, $d$. Thus, at a high level, the reason for performing the projection before applying the DP subroutine is to ensure that the penalty does not scale with $d$. Indeed, we show that one can reduce the dimension of the problem (using public data) to the extent that, no dependence on $d$ (the original dimension) shows up in the final rate. This is because the effective dimension after projection does not exceed $n_{pub}$.

• Response to Weakness 1:

We completely agree exact constants are important here, and we will make a note to better emphasize this. However, we do not believe this devalues the importance of characterizing the asymptotic rates, as we do in our paper. Most of the existing understanding of (private and non-private) optimization is in terms of asymptotic rates.

• Response to Weakness 2:

Many of the novel ideas in our paper are more technical in nature. For example, in our lower bound proof, while we leverage the pre-existing framework of fingerprinting codes, our proof involves several novel steps to overcome the challenges of applying this framework to PA-DP settings. For example, we observe it is crucial to use fingerprinting distributions with small mean and also rely on a clipping analysis when getting the $\sqrt{\log(1/\delta)}$ improvement in the lower bound. This analysis is different from the way fingerprinting codes have been used previously. We include further discussion of these novelties in Appendix B.2, but did not have space to include this in the main body. We can include this in the final version using the extra space given.

With regards to the proof ideas in the unlabelled public data section, while it indeed bears similarities to existing work of [ABM19], which we have acknowledged in the paper, there are several novel components in the analysis; for instance, the analysis of the size of the cover required. We perform this analysis by posing it as another supervised learning problem in the realizable setting with squared loss. Using optimistic rates for the squared loss [SST08], we achieve fast $1/n$ rate for this intermediate learning problem, which is crucial in achieving optimal rates. This is in contrast to the analysis in [ABM19], which is done via VC-dimension based counting arguments.

• Response to Questions:

This could lead to an improvement over ignoring the public data entirely, but will not lead to an improvement over ignoring the private data entirely. That is, one incurs a $\frac{1}{\sqrt{n_{\text{pub}}}}$ penalty due to the error in the subspace approximation made using $n_{\text{pub}}$ points. Note that this is never better than the $O(\frac{1}{\sqrt{n_{\text{pub}}}})$ rate achieved by ignoring the private dataset and running some optimal non-private optimization algorithm.