On Traceability in $\ell_p$ Stochastic Convex Optimization

We thank the reviewer for their review. We respond to the main points below.

W1: The exposition is dense and intuition is missing

Thanks for the suggestion. In the final version of the paper, due to the extra space, we will add more intuitions behind trace value by relating it to the idea of hypothesis testing. Also, we add more intuition related to the sparse fingerprinting lemma and why the distribution family in the sparse fingerprinting lemma lets us show that the output of an accurate learning algorithm in the context of $\ell_p$ SCO must correlate with its training set.

Q1 Many constants and logarithmic factors…

In the main results section, where we discuss the results in more detail, we present the results with all logarithmic factors. Regarding constants, it is indeed customary for the sake of clarity of presentation to hide universal constants because we want to mainly focus on the dependence of the results on the key parameters, such as dimension and the number of samples. Also, we used many of the concentration results from [Ver18]. As can be seen, the universal constants are also hidden in [Ver18].

Limitation: Experiments

Even though our paper doesn’t have experiments, empirically evaluating tracing (or membership inference) is an active area of research in the empirical literature. For instance see [SSSS17, Car+22]. In these works, the focus is on devising strategies for the tracer in modern machine learning settings, particularly neural networks. Our work takes a more fundamental perspective, aiming to determine whether tracing (or membership inference) is inherently unavoidable or simply a byproduct of specific training algorithms. We show that in the fundamental setting of SCO, it is indeed unavoidable and, in certain settings, the number of traceable (memorized) examples scales with the sample complexity.

References

[Ver18] Vershynin, R. “High-dimensional probability: An introduction with applications in data science” Cambridge university press.

[SSSS17] Shokri, R., Stronati, M., Song, C., Shmatikov, V. “Membership inference attacks against machine learning models.” 2017 SP.

[Car+22] Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., & Tramer, F . “Membership inference attacks from first principles.” In 2022 SP

We thank the reviewer for their review.

Q1: Significance of our results

Our work has 1) conceptual significance, 2) improved traceability results compared to state-of-the art, and 3) new proof techniques.

Our work establishes a fundamental and universal principle in stochastic convex optimization: any algorithm in the setup of stochastic convex optimization in general $\ell_p$ geometries achieving error better than that of a DP algorithm must be traceable with the number of samples that scales as a constant fraction of sample complexity. This phenomenon, previously known only for $\ell_2$ geometry [ADHLR24], is shown to hold across all $\ell_p$ geometries. The generalization to $\ell_p$ geometries is crucial as different ML applications naturally require different geometries. For instance, sparse data for feature selection requires working in $\ell_1$ geometry. We also show that this phenomenon is unique to SCO: In Section 1.1.1, we show that this fundamental tradeoff does NOT hold for PAC binary classification.

Compared to previous work, the results of [DSSUV15] are similar to a part of our results related to p=1. In particular, [DSSUV15] proved traceability of $\Omega\left(1/\alpha^2\right)$ samples, which constitutes only $1/\log(d)$ fraction of the sample complexity. In contrast, our work improves this by showing that $\Theta\left(\log(d)/\alpha^2\right)$ samples are traceable, and thus, a constant fraction of the samples is traceable. Our results, moreover, improved the state-of-the art DP SCO lower bounds for $\ell_p$ geometry with $p>2$, making progress on the known gap in this setup [BGN21,ABGMU22,GLLST23,LLL24].

Beyond specific improvements, our work introduces powerful new techniques with broader applicability. Our sparse fingerprinting lemma (Lemma 3.8) extends classical fingerprinting to sparse domains with the key property that correlation scales inversely with sparsity. The subgaussian trace value framework provides a unified approach to convert fingerprinting bounds into traceability results, DP lower bounds, and even non-private sample complexity bounds.

W1: The contribution section is missing

Our paper has a contributions section on Page 2.

W2: Notations and Table for Comparison

We thank the reviewer for catching the inconsistency regarding $\mathcal{A}_n$. We will fix this in the updated version of the paper! We will also add a table to the Appendix that presents all the notations in the paper. We will add a column to Table 1 comparing our results with [DSSUV15] for p=1, which is the closest paper to ours (as discussed in the paper, [DSSUV15] doesn’t achieve the optimal traceability).

Limitations

We apologize for this oversight. We incorrectly marked that limitations were discussed when they were removed due to space constraints. In particular, we want to add a list of possible future works and limitations in the next version of the paper, concerning closing the small gap in our results regarding $\ell_1$ geometry, and extending the results for non-convex losses such as the ones that arise in deep neural networks.

References

[DSSUV15] Dwork, C., Smith, A., Steinke, T., Ullman, J., & Vadhan, S. Robust traceability from trace amounts. FOCS 2015.

[ADHLR 24] Attias, I., Dziugaite, G.K., Haghifam, M., Livni, R. and Roy, D.M., Information complexity of stochastic convex optimization: Applications to generalization and memorization. ICML 2024.

[BGN21] Bassily, R., Guzmán, C., Nandi, A. (2021, July). Non-euclidean differentially private stochastic convex optimization. COLT 2021.

[ABGMU22] Arora, R., Bassily, R., Guzmán, C., Menart, M. and Ullah, E. Differentially private generalized linear models revisited. NeurIPS 2022.

[GLLST23] Gopi, S., Lee, Y.T., Liu, D., Shen, R. and Tian, K., Private convex optimization in general norms. SODA 2023

[LLL24] Lee YT, Liu D, Lu Z. The power of sampling: Dimension-free risk bounds in private ERM. arXiv preprint 2024.

Thank you for your review.

W1 & Q1: Validity of Our Results, Sample Complexity for $p=1$, and the Reviewer's Example.

We believe that the concerns raised are due to misunderstandings. We want to emphasize that there is no mistake in our reported sample complexity: the sample complexity of $\ell_1$ SCO is $O\left(\log(d)/\alpha^2\right)$. These results are well established in the literature and are correct. For instance see textbook [SS12, cor 2.14] or research papers [BGN21, Table 1(first row)], [AFKT21, second paragraph in the introduction], [GLLST23, Table 1(second column)]). We can provide further references or more details on the proof if needed.

The example provided is not a counter-example: Consider the definition of $\ell_p$ SCO in Definition 2.2, which follows the standard definition in the literature. Notice that Definition 2.2 requires a valid cost function and a constraint on $\Theta$ (which the example doesn't specify). In case $\Theta$ is assumed to be in the $\ell_1$ ball, then the sample complexity of the problem is indeed $O(\log(d)/\alpha^2)$ as we report. The reason is that this problem follows Definition 2.2 with $p = 1$, and thus, as discussed above, [SS12, cor 2.14] guarantees the existence of an algorithm that achieves $\log(d)/\alpha^2$ sample complexity. Otherwise, if $\Theta$ is assumed to be in the $\ell_\infty$ ball, then the problem does not fall within Definition 2.2 for $p=1$.

It might be that the reason behind this misunderstanding is related to the interpretation of $\ell_p$ SCO when $p=1$. We use the convention where $p$ corresponds to the geometry of the primal space, while, maybe, you are referring to $p$ as the geometry of the dual space. While both conventions have been used in the literature, we stick to one that is prevalent in the DP literature (see [BGN21, Table 1(first row)], [AFKT21, second paragraph in the introduction], [GLLST23, Table 1(second column)]). Once one accounts for this misunderstanding, the sample complexity of learning with $p = 1$ is $\log(d)/\alpha^2$, and the complexity of learning with $p = \infty$ is $d/\alpha^2$, as stated in the paper.

As you state in your review, "The problem considered in this work is well-motivated,...,If the proposed results are valid, they would address timely and relevant challenges on how to maintain data security guarantees…" We hope this resolves the central concern and kindly ask that you reconsider your evaluation in light of this clarification.

The main theoretical guarantee in Theorem 1 is only applicable when the learning error achieved by the algorithm falls into a regime of $n=O(d)$, which is already quite restricted.

We think this comment stems from the confusion around the sample complexity for different $p$. While the $n = O(d)$ regime might seem quite restrictive at first glance, we, in fact, argue that this is the only regime where the question of traceability is non-vacuous. Indeed, take, for instance, the case $p = 2$ from Theorem 2.5 and the middle row of Table 1. As we point out in the introduction, the problem of traceability is only non-vacuous when the optimal DP error (with $\varepsilon = \Theta(1)$) is more than a constant away from the optimal statistical rate. These rates, for $p = 2$, scale as $\sqrt{d}/n$ and $1/\sqrt{n}$ respectively, which means the question is only non-vacuous when $\sqrt{d}/n \ge C/\sqrt{n}$, i.e., $d \ge C^2 n$, for some constant $C > 0$. The same reasoning can be applied to all other geometries as well, and this basic requirement $n = O(d)$ can be derived from the rates we present in Table 1 of the paper.

Q2 Terminology for SCO.

We believe our terminology is correct and follows a long line of work on stochastic convex optimization initiated by [SSSS09, Eq.1]. In particular, the learning problem of interest in our paper is: Given samples from an unknown distribution $\mathcal{D}$ over the data space $\mathcal{Z}$, the goal is to identify a $\hat{\theta}$ that approximately minimizes $F_\mathcal{D}(\theta)=E_{Z\sim \mathcal{D}}[f(\theta,Z)]$, where $f$ is a function such that $f(\cdot,z)$ is convex and $\ell_p$-Lipschitz for all $z$ in $\mathcal{Z}$.

References

[SS’12] Shai Shalev Shwartz, Online Learning and Online Convex Optimization

[AFKT21] Asi, H., Feldman, V., Koren, T., Talwar, K. Private stochastic convex optimization: Optimal rates in l1 geometry. ICML 2021.

[BGN21] Bassily, R., Guzmán, C., Nandi, A. (2021, July). Non-euclidean differentially private stochastic convex optimization. COLT 2021.

[GLLST23] Gopi, S., Lee, Y.T., Liu, D., Shen, R. and Tian, K., Private convex optimization in general norms. SODA 2023

[SSSS09] Shalev-Shwartz, S., Shamir, O., Srebro, N., Sridharan, K. Stochastic Convex Optimization, COLT 2009

We thank the reviewer for their thoughtful and constructive review. Also, thank you for providing your intuition behind our result on how the trace value can recover the non-private sample complexity. We will add this intuition in the final version of the paper.

The surprising aspect to us was that a single conceptual tool—the subgaussian trace value—could so cleanly unify lower bounds for traceability, private learning, and non-private learning. We also note that if the score function is not linear, then, we believe the idea based on Cauchy-Schwarz inequality (or Holder's inequality) may not work. Our proof in Appendix G doesn’t require that the score function to be linear, therefore, it is more general.