Public-data Assisted Private Stochastic Optimization: Power and Limitations

Summary

The paper presents some new lower bounds for public-data assisted private SCO, when some public examples are available, either with or without labels. In the unlabeled case, a simple algorithm for GLM assisted with unlabeled public examples is presented and analyzed (and it is shown that this removes a dimension dependent term, similar to previous results).

Strengths

- The problem is important. - The new results shed additional light on the limits of public-data assisted private SCO. - In particular, they partially closes the gap between lower and upper bounds, in certain regimes of $d$ and $n_{pub}$. - There is good commentary following most of the results.

Weaknesses

- The presentation is poor. Little effort was made to summarize the main results (and how they improve on previous bounds) in an easily accessible form. This could be remedied with a table summarizing assumptions, new and existing results, conditions on $n_{priv}, n_{pub}, \epsilon, d$, ranges in which the bounds are tight, etc. - For example, it was unclear from the abstract and introduction in which regimes the new bounds are tight. This is only discussed later in the text. Similarly, there are boundedness assumption that should have been clarified early on. - In Theorems 3, 6, 7, it seems there are missing conditions on $n_{pub}$. For example, according to the theorem statement, nothing prevents one from taking $n_{pub} = 1$, or even 0, and it seems one would still get the improved bound. This should not be the case. Please clarify in the rebuttal. - 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? - Corollaries 2 and 3 are frankly hard to interpret, and their significance is unclear to me. Maybe more effort is needed in this section. - 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). Minor: - What do the authors mean by "the non trivial regime $n_{pub} = \Theta(n)$ and $n_{pub} = o(n)$"? Do you mean either of these is true? (if so, it would be clearer to use or, not and). - There are minor formatting issues like a broken reference line 359 and some typos. - In the discussion following Cor.3, how do the $log d$ terms appear?

Questions

Please see questions in the weaknesses.

Rating

5

Confidence

3

Soundness

3

Presentation

1

Contribution

2

Limitations

As mentioned above, the paper should be clearer about its assumptions, regimes in which its bounds are tight, etc.

Summary

The paper investigates a public-data-assisted differential privacy problem. Firstly, for labeled public data, the author introduces a novel mean estimation lower bound of $\tilde{\Omega}\left(\min \left{\frac{1}{\sqrt{n_{\mathrm{pub}}}}, \frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n \epsilon}\right}\right)$. Secondly, when considering unlabeled public data with $n_{\text {pub }} \geq n_{\text {priv }}$, the paper presents a dimension-independent rate of $\tilde{O}\left(\frac{1}{\sqrt{n_{\text {priv }}}}+\frac{1}{\sqrt{n_{\text {priv }} \epsilon}}\right)$ given $\tilde{O}\left(n_{\text {priv }} \epsilon\right)$ unlabeled public data. Additionally, the results for unlabeled public data are extended to general hypothesis classes with bounded fat-shattering dimensions.

Strengths

1. The paper provides a technically solid and well-structured analysis of the public-data-assisted differential privacy problem. The most intriguing part is the Private Supervised Learning with Unlabeled Public Data. In this setting, the paper leverages $n_{\text {pub }} \geq n_{\text {priv }}$, showing a dimension-independent rate and demonstrating that an increasing number of unlabeled public data cannot improve the results because unlabeled public data can only reveal information about the marginal distribution. 2. The emergence of the dimension-independent rate from "public data can be used to identify a low-dimensional subspace, which under the appropriate metric acts as a cover for the higher-dimensional space," is particularly interesting. Could the author provide more explanations and insights on this? 3. Algorithm 1 projects the private data to an orthogonal space, derives the solution, and then projects back to the original space to obtain the result. This approach is novel to me, but I have some questions below.

Weaknesses

N/A

Questions

For Algorithm 1, why does the author perform the projection before applying the differential privacy subroutine? What is the function of the projection here, or how does it help the result? I am not sure if it is because the author uses the unlabeled dataset to construct a data space.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Refers to the weakness and questions.

Summary

This paper studies the effectiveness of using public data to assist private convex optimization. Private convex optimization gives the solver query access to a convex function $f:W\times X \to \mathbb{R}$ and samples $S$ drawn i.i.d. from some unknown distribution $D$. The solver is asked to find some point $w\in W$ that minimizes the population risk $\mathbb{E}_{x\sim D}[f(w,x)]$, but to do so in a manner that is private with respect to the sample $S$. This is an important problem that has received much interest in the community. The notion of using public data that one expects has been drawn from the same distribution has been explored earlier, and the authors continue this line of work. The main contributions of this work are: 1. Stronger lower bounds than prior work showing that in the general setting even for approximate DP there is a dependence on the dimension $d$ of the sample space $X = \mathbb{R}^d$ (typically one assumes data is drawn from some bounded $d$-dimensional ball in the DP setting). They also complement prior work and extent a lower bound for the pure DP setting that held previously only for a limited range of values. These lower bounds show that the naive approach of either treating all data (public and private) as private or ignoring the private data and using SCO on public data is asymptotically optimal. 2. A new algorithm for the unlabelled setting showing that one can gainfully use unlabelled public data to perform dimension reduction for labelled private data and achieve a risk bound that has no dependence on the ambient dimension. This is in contrast to the labelled setting where their lower bounds showed a dependence on the ambient dimension $d$.

Strengths

1. I think this problem is well-motivated and of interest to the DP community. 2. The asymptotic separation between the labelled and unlabelled settings is interesting, and the improvement of lower bounds compared to prior work is also good to see. 3. The paper is in general well-written and easy to follow.

Weaknesses

1. I think that in this case it becomes important to understand the exact constants that occur in the upper bound in the labelled case - even if asymptotically one does not hope to see any improvement over the naive strategies, I would imagine that in practice one still does gain some improvement in the public case. Maybe this point could be better made. 2. Although the analyses seem to be formal and strong (and relatively assumption free), there are not necessarily any new high-level ideas in this work (if you would like to emphasize any new highlights or unexpected outcomes that would be great to see though). The technical work is still interesting however.

Questions

There is one point that I don't understand, I think I might be confused about the nature of the results. In principle, if one treats public labelled data as unlabelled and attempts to follow a similar approach of using them to learn a good lower dimensional representation of the labelled private data, is it easy to see why this does not lead to an asymptotic improvement over ignoring the public data entirely, or treating it as private?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

No additional limitations need to be discussed.