On Traceability in $\ell_p$ Stochastic Convex Optimization
Authors: Sasha Voitovych
Mahdi Haghifam
Idan Attias
Gintare Karolina Dziugaite
Roi Livni
Daniel M. Roy
Venue: NeurIPS 2025 spotlight ()
Keywords: generalization theory
differential privacy
learning theory
Primary area: theory
TL;DR: We show that in stochastic convex optimization, any algorithm achieving error smaller than the best possible under differential privacy is traceable, with the number of traceable samples matching the statistical sample complexity of learning.

Abstract: In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under $\ell_p$ geometries. Informally, we say a learning algorithm is \emph{$m$-traceable} if, by analyzing its output, it is possible to identify at least $m$ of its training samples. Our main results uncover a fundamental tradeoff between traceability and excess risk in SCO. For every $p\in [1,\infty)$, we establish the existence of an excess risk threshold below which every sample-efficient learner is traceable with the number of samples which is a \emph{constant fraction} of its training sample. For $p\in [1,2]$, this threshold coincides with the best excess risk of differentially private (DP) algorithms, i.e., above this threshold, there exist algorithms that are not traceable, which corresponds to a sharp phase transition. For $p \in (2,\infty)$, this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route to establishing these results, we prove a sparse variant of the fingerprinting lemma, which is of independent interest to the community.

On Traceability in lp Stochastic Convex Optimization
Sasha Voitovych"
Mahdi Haghifam
Idan Attias
Gintare Karolina Dziugaite
Roi Livni
Daniel M. Roy
Abstract
In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under Ep geometries. Informally, we say learning algorithm m-traceable if, by analyzing its output, it is possible to identify at least m of its training samples. Our main results uncover fundamental tradcoff between traceability and excess risk in SCO. For every p E [1, oo), we establish the existence of an excess risk threshold below which every sample-efficient learner traceable with the number of samples which is a conslant, fraction of its training sample. For p P [1, this threshold coincides with the best excess risk of differentially private (DP) algorithms, i.e. above this threshold, there exist algorithms that are not traceable, which corresponds to sharp phase transition. For p (2, oo), this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route to establishing these results, prove sparse variant of the fingerprinting lemma, which is of independent interest to the community.
Introduction
Tracing or membership inference informally asks whether is possible, using only the output. of learning algorithm, distinguish samples in the training set. from held-out samples. The existence of a tracer that identifies training examples reveals that the model has memorized specific examples rather than purely captured the underlying distribution (SSSS17; CCNSTT22). In particular, understanding tracing has an important role in generalization theory, where an algorithm that is not traceable is known generalize well beyond its training data [SZ20]. Tracing is also an important technical tool in, e.g., differential privacy (DP), where tracing attacks are the workhorse behind tight lower bounds for the risk-privacy trade-offs [BUV14]. From a privacy standpoint, even the leakage of single example is viewed as catastrophic. However, from generalization theory standpoint, we want to understand the exact relationship between an algorithm's generalization performance and the number of traceable examples.
To reason rigorously about tracing, following (DSSVV15), we define the problem of tracing follows. Let An be a learning algorithm that, given training set S, (Z1,..., 7,,) of
SV and MH equal contribution authors.
"Iustitute for Data, Systems, and Sociely, Massachusetts Institute of Technology
KKoour College of Computer Sciences, Northeastern Universily
University of Illinois Chicago; Toyota Technological Institute at Chicago
Google DeepMind
Department of Electrical Engineering, Tel Aviv University
Department of Statistical Sciences, University of Toronto; Vector Institute
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

i..d. samples from some underlying distribution D, outputs learned model 0. Then, tracer T is a hypothesis tester that, given the model and candidate point Z, outputs IN believes Z was in Sn: or OUT otherwise. Formally, for some small soundness parameter & E (0, and m I n, we require T to satisfy:
Pr S, SoD (~Un)
() IN] 2
Pr S. [T 2 0 1
n
When such a tracer exists, we say that An is (5.m) -ttracebbl.. Equivalently, m is the expected number of samples in the training set Sn for which the tracer outputs IN, and we refer to m as recull. (See Definitions 2.3 and 2.4.)
A fundamental problem in learning theory is investigating how an algorithm's generalization ability interacts with the information it retains about the training samples (including, in our language, its traceability). The common wisdom that any information about the training set in a learned model is in tension with generalization [XR17; BMNSY18; SZ20]. On the other hand, non-traccable algorithms, such as differentially private algorithms, are often unable to reach optimal excess risk. The central question we study in this paper is: what is the ezact tradeoff between the number of traceable examples and achievable excess risk?
This question was considered, first, in the context of mean estimation of a d-dimensional vector, in the seminal work of [BUV14; DSSUV15). It was also studied in the context of Stochastic Conver Optimization (SCO) [SSSS09] in the work of [ADHLR24]. The work of [DSSUV15] studied the tradeoff between excess risk and the number of traceable examples, when mechanism publishes an estimate of the mean that is accurate in every coordinate (i.c., the output of the algorithm has error of with respect to lo norm to the true mean). At a high level, they showed that for every algorithm that has accuracy better than that achievable by a private algorithm, ?(1/a²) examples are tracoable on some hard instance. Notice that for the task of mean estimation in lx norm, the statistical sample complexity is (log(d)) (a))) Thus, for every algorithm, the preceding result only shows that it is possible to trace out 1/ log(d) fraction of the inpul samples. In contrast, [ADHLR24] ex exhibited an SCO problem in l2 geometry for which a constant fraction of the training samples are traceable. An important open problem, then, is to further explore and understand in which setups we expect a constant fraction of the training sample to be traceable.
In this work, we investigate this question, of traccability, in the fundamental learning setup of Stochastic Conver Optimization for general l, geometries. We show that, in this general learning setup, when private learning is not possible, there is no meaningful gop between sample complexity and traceability. That is, in every geometry, there exist hard problem for which every (sample-efficient) algorithm is traceable with a recall which is constant fraction of its sample size. Due to connections between SCO and mean estimation problems, our results also extend to the latter settings; in particular, we close the log(d) gap in the setting of [DSSUV15] and show that optimal traceability is dimension dimensionn-eppendee..
SCO is an ideal testbed for this problem: (1) as in modern machine learning practices, first-order methods are known to achieve optimal sample-complexity rates in this sctting [Fel16; HRS16; AKL21], and (2) within this framework, we can design provable methods that mitigate tracing, such as DP algorithms [CMS11; BST14; BFTG19). Therefore, by studying the problem of traceability in SCO, we also deepen our understanding of the interaction between privacy risks and sample-optimal learning.
To present our results, we recall the basic setup of SCO. An SCO problem is characterized via a triple p (Z, (Z,,,11 f, where Z is the data space, e C Rd is the parameter space, which must be convex, and f: θ x Z + R is loss function such that f(-22) is convex for all 2 e Z. In SCO, data points are drawn from an underlying distribution D over Z, unknown to the learner. The objective of the learner is to minimize the erpected risk based on observed samples. Then, a learning algorithm An: 2" + θ receives a sample S, = (Zi...., Z,. of data points from 2" and returns (perhaps randomized) output in O Then, for D E Mi expected risk is defined as (o) := EZ-D [s(Z, 0). For an SCO problem to be learnable, one ofien assumes that the loss function ʃ is Lipschill and the diameler of the space is bounded, both of which can be measured w.r.t. dlffferent norms. These bounds govern the behavior of learnability, but they can be measured in different geometries. A
2

---

canonical class of SCO problems is induced by the Ep norms, in which case we assume that has bounded en d-dimmeter and f(- is Lp-iisschitz, for fixed p [o].
1.1 Contributions
In this paper, we establish a fundamental tradeoff between traceability and excess risk for algorithms in the context of SCO in general geometries. Some settings in which tracing is not possible are already well-understood: in the excess risk regime where DP [DMNS06] is possible, samples can be traced. Due to this observation, the problem of traceability is only meaningful outside the DP risk regime. More formally, let us define minimax statistical and DP excess risks in Ep SCO. Specifically, for family of lp Lipschitz problems Cp we let
O'stat (p,n) max DECT
min An
max { (FD
inf (D)())) ME
and
(1)
QDP (p.n) = max PELp (e,5)-DP-An
min
max { (A,, inf FD( DEE
(2)
where, for concreteness, take 0.01 and 8 1/n2 in the above.
Main Contribution: We show that every sample-cfficicnt algorithm that achieves an excess risk outside the DP regime (that is, o(aDP) is traccable with recall proportional to the number of samples. The precise statement of our main contribution varies based on the geometry of SCO:
Tracing when p p=1. 1. For the case p 1, show that any learner whose excess risk is better, by a small polynomial factor, than the best risk attainable by a DP algorithm with constant e and ó = 1/n² must be traceable. Moreover, we give an essentially optimal lower bound on the number of samples that can be traced. In more detail, we show that there exists an f-CCO problem such that, if an algorithm achieves risk of
QDP
a x
d0.01 1o.0llog'0 log"(n)
then ((logd))/a2) of the training samples can be traced (see Theorem 2.6). We note that the choice of the constant 0.01 above is arbitrary. It is instructive to compare our results to [D5SUV15]. While the settings of mean estimation and SCO are generally different, our lower bound for & geometry also extends mean estimation in foe norm (see Corollary 2.9 for a formal argument).. In both settings, the sample complexity scales like log(d)/a², however, [DSSUV15] showed traceability of only 1/ log) fraction of the samples. On the other hand, in our work we show that there is no meaningful gap between sample complexity and traceability, and every sample-efficiet algorithm outside the DP regime must memorize constant fraction of its sample. Notably, our results also imply that traceability dimension- dependent deppedeen this setup.
Tracing when E (2, 0o). For l, SCO with p 2 2, in Theorem 2.7, we show that for
App
a <
log(n)
where @pp is set as @Dp = O (d/n2) we construct SCO problem such that, if a learner achieves a risk of a, then l(1/a²) of its samples are traceable. Note that, the non-private sample complexity of learning for p > 2 precisely 0(1/a²) parameter regime,** i.e., the number of traced out samples is of the order of the sample complexity. Note that, the optimal DP risk in this sotup constitutes an open problem, and the quantity app above need not be the optimal DP risk in this setting. Nevertheless, this quantity can shown to be a lower bound on the optimal DP risk (in the regime e Ô(1)). We extend this result to other regimes of e, and another important contribution of our work proving such DP lower bounds.
the relevant
*e point out that, in general, the sample complexity for p 2 2 scales as 1/n A dd/2-1/p/// however, Gas & app only when df 2 n. Thus, the question of traccability is only non- vacuous in the overparameterized regime.
3

---

Sample complexity
Minimax DP
P Rerall
Range of
Refs.
1
(ng
(V logld)
20.40
losid)
Ingidi
L
Thm. 2.6
[1
+
V "v(og(t/E)
Thm. 2.5
Vn
[2, o0)
27
min n1/pp
g1/2-1/v
1/9
Open
Thm. 2.7
Table 1: Summary of traceability results. All results stated up to constants. The sample complexity bounds implied by Theorem A.1. Minimax DP rates known due to [BFTG19; BGN21; AFKT21; GLLST23] and are displayed up to log factors and with == 1/n". (t) Although, in general, the sample complexity in this setting is minimum of two terms, within the stated range of a, the term 1/a" dominates.
In particular, we provide an improved lower bound DP-SCO under l, geometries for p in the high dimensional regime, i..,, d 2 En, which is arguably the most interesting regime as it more relevant for the modern ML applications. Specifically, we show, in Theorem 2.8, that for all < 1 and small ó we can construct problem such that for every (c, DD algorithm, An, there exists data distribution such that:
d 1/p
ES BwAn((s)
[PD(0]
inf (D) BEB
n2
In particular, the above implies that when en, the risk due to privacy dominates the statistical risk. This result improves upon all previous best bounds in the literature when en [ABGMU22; LLL24). In particular, Theorem 3.1 of [LLL24] gives a lower bound Vd/n²e?, which weaker than our lower bound for every p > Corollary of [ARGMU22] d'-1/p which is weaker than our lower bound for 2 en.
gives a lower bound of min (22)
Tracing when p E (1, For each p (1,2), we show that there exists an l, SCO problem such that, if an algorithm achieves excess risk of a S agp (o)" then 52(1/a?) of its samples can be traced (see Theorem 2.5). This result uncovers a fundamental dichotomy between traceability and privacy E, SCO. is known that p E (1, 2), @(1/a²) is precisely the sample complexity of learning 4p-Lipschitz problems [AWBR09]. We note that app for p p= 2 known due to [BST14]. However, as we discuss in Appendix B.1, combining [BST14] with the tracing results of [DSSUV15] does not give the optimal tracing of ((1/a²) samples.
1.1.1 Traccability beyond SCO: PAC Learning
natural question whether a similar phenomenon holds true for other learning setups. Consider the setting of binary classification PAC learning. We show that, for every class with VC dimension bounded by duc; the recall of every tracer is in O(ve log2(n) (n)), i.e., it is at most small fraction of the training sample provided >>>>> duc- Since many such classes, including the class of thresholds, are not privately learnable [BNSV13; ALMM19; BLM20], the sharp transitions between privacy and traccability does not hold in PAC classification. We also point out that for the class of thresholds, we can remove the log2(m) factor from the recall upper bound. See Appendix H.
1.2 Technical contributions
Our technical contributions are elaborated on in Section 2.3. In essence, our technical novelties are twofold. First, present novel sparse fingerprinting lemma that, intuitively, shows that learners over sparse domains must be correlated to their samples. The key novelty of this result is that the correlation is inversely proportional to the sparsity parameter. This feature is not present in prior work, since fingerprinting lemmas are most often applied for paarnerseesimmaon over hypercube domain.
Second, armed with this new fingerprinting result, we present a generic conversion result using notion of subgaussian trace value, which converts any lower bound correlation

---

with the samples into number of samples that can be traced. While it is well-appreciated by prior work that, conceptually, a fingerprinting lower bound implies a traceability lower bound, proving results for our setting of SCO involves complicated sparse domains embedded into lp balls. This makes it more technically challenging to prove the necessary concentration phenomena holds for a tracer over the corresponding domain, which motivates us to restrict our attention to tracers that induce a subgaussian process over the domain.
1.3 Related Work
Our work is most similar in spirit to [DSSUV15; ADHLR24]. Our work builds on top of these results on number of fronts. A key distinct aspect of our approach is the difference in the structure of hard problems and the new sparse fingerprinting lemma. Also, our generic traceability theory of subgussian trace value (Section 2.3) provides abstract treat of the approach in [DSSUV15]. Our approach allows to seamlessly convert fingerprinting lemmas into traccability results and even non-private sample complexity lower bound.
Our work also makes progress towards closing the gap regarding the optimal excess error for lp DP-SCO for > 2. The best known upper bounds for DP-SCO in lp geometry for p > 2 are due to [BGN21; GLLST23], and Theorem 2.8 is the best lower bound.
To put our sperse fingerprinting lemma into the context of prior work, it can be seen to generalize the results of [SU17] to sparse sets, Another "sparse fingerprinting lemma" in the literature is given by [CW723]. Our results are distinct by the way sparsity enters the lemmas: in [CW7233 the mean vector is sparse (and data is dense), and in our case, the mean is dense and the data vectors are sparse. The proof techniques also differ substantially. Our sparse fingerprinting lemma also an example of a fingerprinting lemma for the setting where the coordinates of the data vector are not independent, similar to [KMS22; LT24]. Additional related work is discussed in Appendix B.
2 Problem Setup and Main Results
We begin by some definitions. For (measurable) space R, (R) denotes the set of all probability measures on R. In SCO, an a-learner is defined to be a learner whose expected excess risk is bounded by A formal definition is given below.
Definition 2.1 (a-learner). Fix a > 0, n E N and SCO problem Z. We say An 2" Mi(O) is an o-learner for (0, f) iff for every DD M2) have PD [0) infoce (0) S a. Bs, D (S..)
In our work, we focus on learning Lipschitz- Lipschitz-hourded familics of problems, which are defined below. For every p E oo], let Br)r) = {0 R |101, S r be the unit ball in lp norm. Definition 2.2 (Lipschitz-boundeed problems). Fix p E [o], and let d < be natural number. We let L denote the set of all To-iipechiiz-baaudeedd SCO problems in d dimensions.
Namely, P = (0, Z, f) E cg iff (i) θ c (1),,, and (ii) for every 0,, 02 E θ and z E 2, we have [f(z, 01) (2,, 02) < 00 0211p-
2.1
Tracing
The key notion we study here is bracing, and we next introduce our framework for traceability. We consider families of tracers that assign each candidate point a real-valued score capturing how likely it is to have been seen during training. Then, the tracer converts these scores into binary IN or OUT decisions by thresholding the score. Intuitively the score corresponds to the likelihood of the event that the learner saw data point during training.
Definition 2.3 (Tracer). Fix data space 2 and parameter space θ A tracer's strategy is a tuple of T = (6, D) where ob e x 2 + R and D E (2)
Definition 2.4 ((E, m)ttracaabiilltt)) Let n E N, & E (0, 1), and m E N. We say a learning algorithm An is (E, -ttrcccbbe if there exists a tracer (Ø, D) and X e R such that, (Zo, Zi,..., Zn) ~ DD(++1) and 0 An (Z).... Za), we have (i) Soundness: Pr (0(0, Zo) 2
A) S 5, and (ii) Recall: E[[ [n] 6(0. Z,) 2 }} 2 m.
5

---

2.2 Main Results
2.2.1 Traceability of a-Learners
In this section, we discuss our traceability results for accurate learners in lp geometries. First, we will state a result that applies to p E [1, 2), and then present its slight refinement for p= 1. We will then present our result for p 2 2. See Appendices F.1 to F.3 for proofs. such that, for all p E [1,2), if d, n,
Theorem 2.5. There crists universal constant & E (0,1/e) and a > O are such that
d
1
Sas min c. n² log(1/E))
(3)
Vn
6 6f
then there exist an l, SCO problem that every o-learner is (E, mt)-rrccaabee with m S (a 2).
Note that the upper bound on a in Equation (3) is precisely the optimal DP excess risk for e E @(1) and E [1,2] [AFKT21; BGN21], and the lower bound is precisely the optimal non-private risk (except p == 1; Theorem A.1). Moreover, for p E (1, 2], the lower bound on m ezactly matches the statistical sample complexity.
As mentioned above, for p 1, the lower bound recall in Theorem 2.5 is less than sample complexity by a factor log(d). This prompts us to establish the following refinement
Theorem 2.6. There erists universal constant c > such that, if large enough and n, & E (0, 1/e), and a > O are such that
log(d) n
d0.49
1
sas min c n Aloo(1/EE)
then
(4)
8
there erisls a & SCO problem that every a-llearner is (g, mlltrccabble with m E E (log(d)/a²)
Note that the upper bound in Equation (4) is slightly stronger than in Equation (3); however, the lower bound recall now matches the sample complexity of learning in 4 geometry. We now present a result for p 2 2.
Theorem 2.7. There erists a universal constant c such that, for all p (2) of d, n, & E (0, 1/e), and > O are such that
1
di
n sas min for (n ( ( log(1/E))
d
1/P
1 1
min 1/pp'
8..
.
then
6
Vn
there crist an lp SCO problem such that every a-learner is (E, () (on)-traccable with m Ω (1/(6)))).
results have different implication, showing that all sufficiently accurate learners need to memorize a number of samples on the order of the sample complexity. However, in this case, the upper bound in Equation (5) need not be the optimal DP risk. Instoad, it provides a lower bound on the optimal DP risk, as we will see next.
For p (2,0).
2.2.2 Improved DP-SCO Lower Bound for p>
Theorem 2.8. Let p E o0). There exist universal constant > 0 and an lp SCO problem p = (0, f) such that every (e, 8)P learner of P with e S and < c/n satisfies,
{
d1-1/p
a 2 c- min
62,2
2.2.3 Consequences for mean estimation
Consider the setting of mean estimation in lo norm as in DSSUV15). Our results Theo- rem 2.6 extend almost verbatim to this setting.

---

Corollary 2.9. Let Z = {=1]", and suppose an estimator is given such that, given access to í.i.d. samples Zi...., Zn E 2, outputs fi with
I a a/2. Then, there erists universal constant. c > 0 such that, if d is large enough and n, E (0. 1/e), and a > O satisfy Equation (4), then the estimator ji is -tracebte with m E Q (log(d)/a²).
2.3 Roadmap of the proof
Our proofs rely on introducing two key technical elements that allow us to generalize tracing techniques to general l, sctups. The first element is generic conversion result involving a complexity notion which we term the subgaussian trace value of a problem. As we show in the proof of Theorem 2.8, we can use the subgaussian trace value to prove traceability results over general domains, establish DP sample complexity lower bounds, and, even to recover non-privale sample complexity lower bounds. While the connection between the first two aspects is well-known [FS17], we find the ability of trace value to recover non-private lower bounds surprising.
Our second technical contribution concerns techniques for lower bounding the subgaussian trace value, which accomplish through several novel fingerprinting lemmas. Previous works used the standard fingorprinting lemma, where the learner observes points on a hypercube, to lower bound DP and traccability in l2 geometry. However, when moving to general 6p geometries, this setup no longer captures the hardest settings to learn. For instance, for p 2, canonical instances of hard problems involve data drawn from sparse sets [AWBRO9]]. We thus prove new fingerprinting lemmas that enable us to leverage our framework in such settings. These fingerprintng lemmas are then applied to carefully constructed instances of hard problems, and we show that every accurate learner of these problems is traceable.
3 General framework: subgaussian trace value
We next describe more formally the framework of subgaussian tracers. For random variable X, the subgaussian norm of is the quantity || == inf E (cxp(x2/()) s 2} [Ver18].
We use the following definition of a subgaussian process:
Definition 3.1 (Subgaussian process). We call an indexed collection of random variables
(Xo) o-subgaussian process w.r.l metric space II-II) if for every 0, 0' E O we have (i)
[X - 1 S | - O'Il, and (ii) [Xell S a diami-- (+).
For origin symmetric convex body θ, let ll-lle denote the Minkowski norm w.r.t. O that is | == inf {A 0: x ^OO. If is not convex or not origin symmetrie, we let I1-Ile be the Minkowski norm w.r.t. convex hull of (o O)) Note that Illlle is the minimal norm to contain θ in its unit ball.
Definition 3.2 (Subgaussian tracer). Fix K R to be constant, and let O be convex body. We let 5. be the class of subgaussian tracers at scale x >> 0, that is, a tracer (Ø, D) E I, iff
(i) {0 Z)e where Z D is a 1-subgaussian process w.r.t. (1,1l-lle):
(ii) (0(0,2) S x for all e and = Z.
Definition 3.3 (Subgaussian trace value). Fix n E [0, and x RR Consider an arbitrary SCO problem P = (0, 2, f). Let H, be as in Definition 3.2. Then, we define the subgaussian trace value of problem P by
(P;nn;)
inf a-learnenA,
sup T=(DDD)ET
Es,
An
0 6(0.2)) z,) kE(m)
Σ
where the inf is taken over all An that achieve excess risk S a on P with n samples.
Traceability via subgaussian trace value. The subgaussian trace value characterizes the average score the pair (e, D) assigns to the data points the training set. However, the definition of recall in Definition 2.3 requires characterizing the number of samples in the training set that takes large value. The former can be converted into the latter, provided the sum of squared scores of samples is not too large. A formal statement, which is

---

consequence of Paley-Zygmunn inequality, can be found in Lemma A.11. In the next lemma, we show how to control the sum of squares of the o(0, Z:) using the subgaussian assumption.
Lemma 3.4. Fir n, d E N. Suppose θ C IRd is a subset of unit ball in some norm ||-I1- Let Φ: O x 2 I and D E Mi be such that, % ~ "D (5(0, 2)} is o-subgaussian process w.r.l. (0, I111- Let (Zz,.... 7x2) ~ DDn Then, there is a constant C > 0, such that
[0 2.) & Co (Vn+ vatt)t 2 21-4cam 21-4cxp(-t)
Pr
sup BE
VA 2 O.
Equipped with this lemma, in the next theorem, we show that if, the subgaussian trace value of a problem large, then every a-learner is traccable.
Theorem 3.5. Fir n E N. de N, K > O and a E [0, 1]. Consider an arbitrary SCO problem
P = (G, Z, f)- Let T = (P; n, a)) be the subgaussian trace value of P. Then, for some constant e > O, every a-learner An is (E, m) -trattaceebee with
n2 16k2n n + d exp(n + d) ]
= cxp(-cTT) m
Privacy lower bounds via subgaussian trace value. In the next theorem, we show that the notion of subgaussian trace value directly lower bounds the best privacy parameters achievable by a DP algorithm. The proof is based
[FS17].
Theorem 3.6. There erists a universal constant e > 0, such that the following holds. Fix E (o), E N, d E N, a 1], K > 0 E > O, and ô E [0, 1]. Consider an arbitrary SCO problem P= = (9, 2, f) in Rd. Let T = T (P; n, a) be the subgaussian trace value of problem P. Then, for every (e, 8)DD a-learner An, we have exp(s) 1 c 25x).
Non-private sample complexity via subgaussian trace value. Surprisingly, if we directly use subgaussian trace value, we can recover optimal sample complexity bounds for all p E (0) and all regimes of (d, a), thus unifying traccability with private and non-private sample complexity lower bounds. While we detail the argument formally in Appendix G, we consider here a helpful example of l2 geometry. First, can be shown that we always have Tr(P: a) S vd/n for arbitrary problem P (see Proposition G.1). Also, we will later show that, for every a > O, there exist an l2 problem P with Tr(P; n, a) Z vd/na nd/na (see Theorem 5.1). Combining these two inequalities gives n 2 1/a², which optimal.
The sparse fingerprinting lemma
By introducing the notion of subgaussian trace value, we have reduced the problems of traceability and privacy lower bounds to the question of lower bounding the subgaussian trace value. Now, we discuss the techniques to lower bound subgaussian trace value. The proofs can be found in Appendix D. Due to space limitation, only discuss the details for the case of p > and present the details of p = in Appendix E.2.
For E2 geometry, one can lower bound subgaussian trace value using the classical fingerprinting lemma in [DSSUV15]. While this strategy leads to traccability results in lg geometry, examples of hard problems for Ep geometry with 2 are those with sparse sets 2 (e.g., as in [AWBR09]). This motivates us to prove the following sparse fungerprinling lemma, which another important contribution of our work. For vector I E Rd. let supp(z) be the of its non-zero coordinates and denote ||>||,, = -supp(z)).
Definition 4.1 (Sparse distributions family). Fix d E N, & E [d] and μ E I-k/d, k/dd Consider the mixture distribution on Z = {a E (0, =1]d: ||21|o = k} given by, for all z E Zk. Dp,(=== = E (=mnnt(( [=)], where (z) = (supp((z) J) II
1 + (d/k) +d(k//)) 12
2
Note that, in particular, Ez~D,,. μ. Intuitively, one can think of sampling from Dj, using the following procedure: (i) sample the support coordinates J ~ unif (12) (ii) for each j E J, sample Z' from {=1} with mean E independently, (iii) for each & J, set Z 0.
JEJ
8

---

With this distribution family at hand, we may state the sparse fingerprinting lemma. For I, R" and a subset R S [d] of coordinates, we use (::)s s denote the inner product (I,, v) == Exen Fili. Also, for 0, > 0, let s-betar-v.r (a. ,9) be the symmetric beta- distribution, i.e., beta distribution with parameters a, scaled and shifted to have support [-7,]] (see Definition A.13).
Lemma 4.2 (Sparse fingerprinting). Fix d, n E N and let k E [d]. For each μ e (-k/d,,,k/ let Zx and P.R be as in Defivition 4.1 Let x = =-/eta (3, 3) Sd be prior and set
(0, = (0, (z.(z= - k²²)
supp(2)
Then, for every learning algorithm An 2 + Mi (1² with sample Sn (Zi,.... Zn),
2 Bura Bm (S.)
Busn.Bg D. (n
Σ 00 2:)
k
The key novelty of this lemma that it provides a way to study the correlation between a learner's output and training samples on sparse sets Zz. An important and distinctive feature of this result is that the right-hand side scales by a factor of d/k, highlighting the fact that sparse problems correspond to greater subgaussian trace values. Intuitively, this stems from the fact that each coordinate is seen fewer times by the learning algorithm,, meaning it must retain more information from each training sample in order to learn accurately. Additionally, for the special case k d, the result precisely recovers the fingerprinting lemma from [SU17].
5 Final steps: bounding the subgaussian trace value for hard problems
Finally, we go over the construction of hard problems. To illustrate the difficulty of problem constructions, give an example of problem that requires many samples to learn but nevertheless is not traceable. Consider learning over l ball with linear loss. Let
θ = Bi)),, 2 =
= -00)-000
(6)
Consider a difficult set of distributions (Dij where D, a product distribution on 2 and has mean coordinate i and mcan this problem requires ((log(d)/a)) samples to learn up to risk of a/3, and ERM an optimal learner. However, after seeing ((log(d)/a²) samples from D;, the ERM takes the value i e w.h.p., which is also the population risk minimizer. In other words, becomes impossible trace out any specific samples on which was trainod.
all other coordinates. It can be shown
Generic construction for co). As mentioned above, to obtain optimal results for p > problems constructed need to be sparse, and the main subtlety in our constructions is choosing the sparsity parameter. For some k E [d] to be chosen later, consider the following Lipsschcitzz problem Pk.p-
(7) Here, the parameter space θ is the largest Eoo ball inscribed into the unit lp ball, and is the Hölder conjugate of p. ie., 1 1 1- =1 The next step is to show that o-learners for the above problem must be correlated with the mean of the unknown data distribution. Let D be distribution with mean ,e, and suppose A, is an o-learner for Equation (7). Then,
θ = Boc (d 1/D), 2 f= (0, +13d: 11=110 k]. =
Ds..Der.BrAntoe (m:)) sup (14, 0) - k2/4 dd1// ||w|| k./9a. oEe
Now, we apply the sparse fingerprinting lemma (Lemma 4.2). A key step is choosing the scale 3 > 1 of the beta-prior. On the one hand, 3 should be small enough to guarantee Ed-1/p ||d|| > h2/4a, so that the above lower bound non-vacuous. On the other hand, taking 3 too small decreases the sample complexity of learning the problem, thus, disallowing

---

the desired level of recall. The optimal choice is B x a (kkdd) as long as this quantity 2 1. This choice yields
d 1/9
(P.(P.pinn.o) Bss Dan (.,
Σ 60, 74)
2
12/2-1/PTaa
where (1)), and, for some universal constant > O, we let
600 = vk 00. (2 (0.(2-z)) supp(2)
cd
Note that the d scaling ensures induces 1-subgaussian process. Finally, it remains to choose a suitable value for k, for cach pair a). Rocall the definition of Pk.p from Equation (7).
Theorem 5.1. Let Pk,y be the family of problems described in Equation (7). There erist universal constants C1 > O such that, for all a E [0,1/6] and E N, the following subgaussian trace value lower bounds hold for all p E (1) and x. S civd:
vi (i) For p S 2 and k d,, we have Trx (Pk n, 2 02 no
(it) For 2 2 and k = (6a)Pd we have Tr (Pkpi n, a) 2
vd
d'-1/v
Using the reduction Theorem 3.5, the above establishes Theorems 2.5 and 2.7.
Refinement for p While the above construction also yields a traceability result for p p= it is suboptimal for the following simple reason: for k == d, the problem in Equation (7) only requires @(1/a²) samples to learn, thus, it is impossible to trace out ((log(d)/o samples. On the other hand, the problem in Equation (6) requires (llo(d))aa) samples to learn but is not traccable. The intuition we follow here is to modify the construction in Equation (7) to make "look" more like an bball to drive up the sample complexity while still avoiding the counterexample with an ERM learner from the beginning of the section. In particular, we consider the following fi-problem,
θ B1) n (1/s), Z ==
f(0,z) -2,,0),
for suitably chosen E [d]. Note that, if we choose >>>>>>>>>>> 1, e above is polytope with much more vertices (2 (9) than an l ball (2d), which would intuitively force learner like ERM to reveal more information about the training sample. On a technical level, selecting large s improves the subgaussian constant of a tracer; however, selecting s that is too large shrinks the diameter of the set, and thus, the problem becomes easier to learn. We must trade off these two aspects, and carefully set the value of s. As it turns out, the optimal choice is s x d'-c for any small 0 in order to establish Theorem 2.6. The remainder of the proof rather technical and hence is deferred to Appendix F.2.
Limitations
We conclude by stating an intriguing open problem. We conjecture Theorem 2.8 is tight, and the dichotomy between traccability and SCO also holds for p 2. In particular, conjecture that the optimal DP-SCO excess risk for lp with > 2 scales as
1//211/p
1/p
d111/p
min
+ min
Vn
NE
22
ignoring log(1/6) factors. If the conjecture is true, we have a complete understanding of traceability in SCO. If it is false, it reveals that there is something fundamentally different about settings with > 2, which would also significantly enrich our understanding of DP-SCO.
10

---

Acknowledgments
The authors would like to thank Mufan Li and Ziyi Liu for their comments on the drafts of this work.
Funding
This work was completed while Sasha Voitovych was a student at the University of Toronto and supported by Undergraduate Student Research Award from the Natural Sciences and Engineering Research Council of Canada. Mahdi Haghifam supported by a Khoury College of Computer Sciences Distinguished Postdoctoral Fellowship. Idan Attias is supported by the National Science Foundation under Grant ECCS-221 2023, through the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL). Roi Livni is supported by Google fellowship, a Vatat grant and the research has been funded, in parts, by an ERC grant (FoG 101111228). Daniel M. Roy is supported by the funding through NSERC Discovery Grant and Canada CIFAR AI Chair at the Vector Institute.
References
[AWBR09)
A. Agarwal, M. J. Wainwright, P. Bartlett, and P. Ravikumar. "nformationn-hhoretio lower bounds on the oracle complexity of convex optimization". Advances in Neural Information Processing Systems 22 (2009).
[ALMM19]
N. Alon, R. Livni, M. Malliaris, and S. Moran. "Privale PAC learning implies finite Littlestone dimension". In: Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing. 2019, pp. 852-
860.
[AKL21]
I. Amir, T. Koren, and R. Livni. "SGD generalizes beller than GD (and regularization doesn't help)". In: Conference on Learning Theory. PMLR. 2021, pp. 63 92.
[ABGMU22]
R. Arora, R. Bassily, C. Guzmán, M. Menart, and E. Ullah. "Differen- tially private gencralizod lincar models revisited". Advances neural information processing systems 35 (2022), pp. 22505 22517.
[AFKT21]
H. Asi, V. Feldman, T. Koren, and K. Talwar. "Private stochastic convex optimization: Optimal rates in geometry". In: International Conference Machine Learning. PMLR. 2021, pp. 393-403,
[ADHLR24]
Attias, G. K. Dziugaite, M. Haghifam, R. Livni, and D. M. Roy. "Information Complexity of Stochastic Convex Optimization: Applications Generalization and Memorization". arXie preprint or orxix:2402 09327 (2024).
[BFGG19]
R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta. "Private stochastic convex optimization with optimal rates". Advances in neural information processing systems 32 (2019).
[BGN21]
R. Bassily, C. Guzmán, and A. Nandi. "Non-Euclidean differentially private stochastic convex optimization". In: Conference on Learning Theory. PMLR. 2021, pp. 474-499.
[BMNSY18]
R. Bassily, S. Moran, Nachum, J. Shafer, and A. Yehudayoff. "Learn- that Use Little Information", In: Algorithmic Learning Theory, 2018, pp. 25 55.
[BST14]
R. Bassily, A. Smith, and A. Thakurta. "Private empirical risk mini- mization: Efficient algorithms and tight bounds". In: 2014 IEEE 55th annuol symposium on foundations of computer science. IEEE, 2014, pp.
[Bat08]
N. Batir. "Inequalities for the gamma function".. Archic der Mathematik 91.6 (2008), pp. 554 563.
[BHM7200]
O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskíy. "Proper learning, Helly number, and an optimal SVM bound". In: Conference on Learning Theory. PMLR. 2020, pp. 582 609.
11

---

[BFST22]]
G. Brown, M. Bun, V. Feldman, A. Smith, and K. Talwar. "When is memorization of irrelevant training data necessary for high-aceuracy learning?" In: Proceedliggs of the 53rd annual ACM SIGACT sympo- sium on theory of computing. 2021, pp. 123-132.
[BL200]
M. Bun, R. Livni, and S. Moran. " "An equivalence between private classification and online prediction". In: 2020 IEEE 61st Annual Sym- posium on Foundalions of Compuler Science (FOCS). TEEE. 2020, pp. 389-402.
[NSVV5]]
M. Bun, K. Nissim, Stemmer, and S. Vadhan. "Differentially private release and learning of threshold functions", : In: 2015 JEEE 56th Annual Symposiun on Foundations of Computer Science. IEEE. 2015, pp. 634- 649.
[BVV14]
M. Bun, J. Ullman, and S. Vadhan. "Fingerprinting codes and the price of approximate differential privacy". In: Proceedings of the forty-sinth annual ACM symposium on Theory of computing. 2014, pp. 1-10.
[CWZ23]
T. T. Cai, Y. Wang, and L. Zhang. "Score attack: A lower bound technique for optimal differentially private learning". arXiv preprint 0rX:::2303.011: 07152 (2023).
[CCNSTT22]
N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramer. "Membership inference attacks from first principles", In: 2022 IEEE Symposium on Security and Privacy (SP). IEEE. 2022, pp. 1897-1914.
[CMS11]
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. "Differentially private empirical risk minimization." " Journal of Machine Learning Research 12.3 (2011).
[CDK22)
C. Cheng, J. Duchi, and R. Kuditipudi. "Memorize to generalize: the necessity of interpolation high dimensional linear regression". In: Conference
Learning Theory. PMLR. 2022, pp. 5528 5560.
[DMNS06]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. "Calibrating noise to sensitivity in private data analysis". In: Theory of Cryplogruphy: Third Theory of Cryplography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer. 2006, pp. 265 284. C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan. "Robust traceability from trace amounts". In: 2015 IEEE 56th Annual Sym- posium on Foundalions of Compuler Science. IEEE. 2015, pp. 650 669.
DSSUV155
[Fel16]
V. Feldman. "Genoralization of ERM in Stochastic Convex Optimiza- tion: The Dimension Strikes Back". In: Advances in Neural Information Processing Systems. Ed. by D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett. Vol. 29. Curran Associales, Inc., 2016.
[Fe120]
V. Feldman. "Does learning require memorization? short tale about long tail". In: Proceedings of the 52nd Annual ACM SIGACT Sym- posium on Theory of Computing. 2020, pp. 954-959.
[FKT20]
V. Feldman, T. Koren, and K. Talwar. "Private stochastic convex optimization: optimal rates in linear time". In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Compuling. 2020, pp. 439-449.
[FS17]
V. Feldman and T. Steinke. "Generalization for adaptively-chosen estimators via stable median". In: Conference on learning theory. PMLR. 2017, pp. 728-757
[GLLST23] ]
S. Gopi, Y. T. Lec, D. Liu, R. Shen, and K. Tian. "Private convex optimization in general norms". In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2023, pp. 5068-5089
HDMR211)
M. Haghifam, G. K. Dziugaite, S. Moran, and D. Roy. "Towards unified information-theercti framework for generalization". Advances in Neural Information Processing Systems 34 (2021), pp. 26370-26381.
12

---

[NNKRD0
M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. "Sharpened generalization bounds based on conditional mutual infor- mation and an application to noisy, iterative algorithms". Advances in Neural Information Processing Systems 33 (2020), pp. 9925-902500 9935. M. Haghifam, B. Bodriguez-Gállee Gálvez, R. Thobaben, M. Skoglund, D. M. Roy, and G. Karolina Dziugaite. "Limitations of Information- Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization". ". In: Proceedings of The 34th In- lernational Conference on Algorithmic Learning Theory. Vol. 201. Proceedings of Machine Learning Research. PMLR, 2023, pp. 663 706. M. Hardt, B. Recht, and Y. Singer. "Train faster, generalize better: Stability of stochastic gradient descent". " In: International conference on machine leurning. PMLR. 2016, pp. 1225 1234.
[RTSMM233
[HRS16]
HSSDDMMPSNCOS)
N. Homer, S. Szelinger, M. Rodman, D. Duggan, W. Tembe, J. Muchling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. "Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genolyping mieroar- rays". PLoS genelies 4.8 (2008), e1000167.
[KOV17]
P. Kairouz, S. Oh, and P. Viswanath. "The Composition Theorem for Differential Privacy". IEEE Transactions on Information Theory 63.6 (2017), pp. 4037-4049.
[KLSU18]
G. Kamath, J. Li, V. Singhal, and J. Ullman. "Privately Learning High-Dimensional Distributions". arXiv preprint Xrv: 10111105022000 (2018).
[KLSU19]
G. Kamath, J. Li, Singhal, and Ullman. "Privately learning high-dimensional distributions" In: Conference on Learning Theory. PMLR. 2019, pp. 1853-1902.
[KMS22]
G. Kamath, A. Mouzakis, and V. Singhal. "New lower bounds for private estimation and a generalized fingerprinting lemma". Advances in newral information processing systems 35 (2022), pp. 24405-24415 Y. T. Lee, D. Liu, and Z. Lu. The Power of Sampling: Dimension-free Risk Bounds in Private ERM. 2024. arXiv: 2105. 13637 [cs.LG].
[LLL24]
[LW86]
N. Littlesoone and M. Warmuth. "Relating dała compression and learnability" (1986).
[Liv24]
R. Livni. "Information theoretic lower bounds for information theoretic upper bounds". Advances in Neural Information Processing Systems 36 (2024).
[LT24]
X. Lyu and K. Talwar. "Fingerprinting Codes Meet Geometry: Im- proved Lower Bounds for Private Query Release and Adaptive Data. Analysis". arXi preprint arXiv:24 12. 14396 (2024).
[MY16]
S. Moran and A. Yehudayoff. "Sample compression schemes for VC classes". Journal of the ACM (JACM) 63.3 (2016), pp. 1-10.
[NY83]
A. S. Nemirovskij and D. B. Yudin. "Problem complexity and method efficiency in optimization" (1983).
[SDSOJ19]
A. Sablayrolles, M. Douze, C. Schmid, Y. Ollivier, and H. Jégou. "White-box vs black-box: Bayes optimal strategies for membership inference". In: International Conference Machine Learning. PMLR. 2019, pp. 5558 5567.
[SSSS9)]
S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. "Stochastic Convex Oplimization." " In: COLT. Vol. 2. 4. 2009, p. 5.
[SSSS17]
R. Shokri, M. Stronati, C. Song, and V. Shmatikov. "Membership Infer- ence Attacks against Machine Learning Models". In: IEEE Symposium on Security and Privacy. 2017.
[ST10]
K. Sridharan and A. Tewari. "Convex Games in Banach Spaces". In: COLT. 2010, pp. 1-13.
13

---

[SU17]
T. Steinke and J. Ullman. "Tight lower bounds for differentially private selection". In: 2017 IEEE 58th Annual Sympostum on Foundations of Computer Science (FOCS). IEFF. 2017, pp- 552-52 552-563.
[SZ20]
T. Stcinke and L. Zakynthinou. "Reasoning about generalization via conditional mutual information". In: Conference on Learning Theory. PMLR. 2020, pp. 3437-3452.
[Ste16]
T. A. Steinke. "Upper and lower bounds for privacy and adaptivity in algorithmic data amalysis". PhD thesis. 2016.
[Ver18]
R. Vershynin. ffihh-dimensional probubilily: An inlroduction with ap- plications in data science. Vol. 47. Cambridge university press, 2018. M. Wainwright. High-dimensional statistics: non-asymptotic view- point. Vol. 48. Cambridge university press, 2019.
[Wai19]
[XR17]
A. Xu and M. Raginsky. "Information-theoree theoretic analysis of general- ization capability of learning algorithms". In: Advances in Neural Information Processing Systems. 2017, pp. 2524-2533.
14

---

Appendix Contents
1
Introduction
1.1
Contributions
1.1.1
Traceability beyond SCO: PAC Learning
1.2
Technical contributions
1.3
Related Work
2
Problem Setup and Main Results
2.1
Tracing
2.2
Main Results
2.2.1
Traceability of a-Learners
2.2.2
Improved DP-SCO Lower Bound for p >
2.2.3
Consequences for mean estimation
2.3
Roadmap of the proof
3
General framework: subgaussian trace value
The sparse fingerprinting lemma
5 Final steps: bounding the subgaussian trace value for hard problems
6
Limitations
10
A Additional preliminaries
17
A.1 Background on SCO
17
A.2 Differential Privacy
18
A.3 Concentration inequalities
18
A.4 Beta distributions
19
B Additional Related Work
B.1 Detailed comparison with [DSSUV15; BST14).
21
C Proofs from Section
C.1 Proof of Lemma 3.4
22
C.2 Proof of Theorem 3.5
................................
24
C.3 Proof of Theorem 3.6
26
D Proofs of fingerprinting lemmas (Section 4)
26
D.I Proof of Lemma 4.2
26
D.2 Fingerprinting for & setup.
28
Hard problem constructions and proofs of subgaussian trace value lower bounds
30
15

---

E.1 Proofs for ge-mmmetsries (Theorem 5.1)
30
E.2 Proofs for l Ei-geometry
33
Proofs of the main results (Section 2.2)
36
F.1 Proof of Theorem 2.5
36
................................
F.2 Proof of Theorem 2.6
................................
37
F.3 Proof of Theorem 2.7
................................
F.4 Proof of Theorem 2.8
38
F.5 Proof of Corollary 2.9
39
G Connection between subgaussian trace value and non-private sample com- plexity
40
G.1 Lower bounds for p E (1,
40
G.2 Lower bounds for p = 1.
42
H Traceability of VC classes (Section 1.1.1)
44
16

---

A Additional preliminaries
A.1 Background on SCO
The next proposition summarizes the known minimax rates for learning SCO problems in general geometries. A proof can be found in [NY83; AWBR09; ST10].
Thcorem A.1. Fir p oo), de N, and N. Let Cstat (Cp n) be the minimaz cacess risk rate of learning fp-Lipschitz- boaudddet-boundddd problems, as defined in Equetion (1). Then,
1. For p= 1, we have
(Sttt(Cpp n) E (Vlogld)
(logdd)
2. For < 2, we have
(lggd)
Orstat Cbp n)
A
n
(p - 1)v7
3. For 2 S 00, we have
/d1/2-1/v
Astat (aal(op:)) E E
Vn
n/p
4. For = =0, we have
d
Ostar n) E
Remark A.2. Notice that, the overparameterized regime (d 2 n). the minimax excess risk for p is ((()) /r) which is dimensson-inddependent. This shows that for d2 n, in all geometries except p (1, jo the minimax excess risk is dimension-free.
This proposition implics the following corollary on the minimum number of samples required for a-learners.
Corollary A.3. Fix p E [1, N, and a (0, 1]. Let Nata(Cop n) be the sample complerity of learning problems C up to eacess risk a, i.e.,
(sta((2 n) = min {n: assa (Cg, n) S sa).
Then,
1. For 1, have
log(d)
Nstat (Cp, n) E E
a
2. For 1 <<p < 2, we have
log(d)
Notat (Cp n) E θ
a ^
(pp 1)a)²
3. For 2 < 00, we have
(d1-2/p
N (a m)) E
a2
a
4. For = 1, we have
d
Nstor(Cg n)
a
17

---

A.2 Differential Privacy
Definition A.4. Let and E [0, A randomized mechanism An 2 (1 is (e, 6)-DP, iff, for every two neighboring datasets Sn E 2" and Sy E z" (that is, Sn, Sy differ in one element), and for every measurable subset M S O it holds
(S.) ( ( M) S se Pro-A..(%))
0 E M) +
Algorithms that satisfy DP are not traceable in the sense of Definition 2.4 [KOV17]. The following simple proposition formalizes this obscrvation.
Proposition A.5. Fir n E N and e, > O. Let An be an (e, 6DD algorithm. Then, if An (E, -tacccabbee,, holds that
S nexp(=) + nd.
A.3 Concentration inequalities
First, we collect lemmata on the subgaussian norm, introduced in Section 3, which we use to derive concentration inequalities. The following is Equation (2.14) in [Ver18], and shows that a bound on subgaussian norm immediately leads concentration inequalities.
Lemma A.6 (Subgaussian concentration). There erists universal constant C' such that the following holds for every random variable with || < <c: for every 2 0,
ct (T
Pr||X] $ 2
The subgaussian norm behaves nicely under the sunmation of independent random variables. The following Proposition 2.6.1 in [Ver18].
Lemma A.7 (Sum of subgaussian variables). Let C be a universal constant. Let X1,... Xn be collection of arbilrary independent real random variables. Then,
m
n
Σ
S
Subgaussian norm also behaves nicely under mixtures. In particular, we have the following proposition.
Proposition A.8 (Subgaussian mixtures). Let YaEa be o-subgaussian random variables, and let π be a distribution over the index set A. Then, a misture of /aTa under a ~ π is also o-subgaussion.
Proof. Let Y be such mixture. Then, for every t > 0, we have
Ejexp(Y2 /t²) = Ea-, E(exp
Plugging in t= a into above, and using that |all, So for all a, we have Elexp(YY//ol /o²)] Ba x2 /2)1²)] 2,
ie., [|il, Sa as desired.
It is well-knoow that bounded random variables subgaussian (Equation (2.17) of [Ver18]).
Proposition A.9. Suppose is a random variable such that X E [-b, b] almost surely. Then,
| 1,, S Cb.
for some universal constont C 0.
18

---

We will heavily use the following result for the supremum of subgaussian processes (which follows from [Ver18, Theorem 8.1.6)). Let A(,,, (l-ll denote the covering number of θ in norm ||-|| at scale >> 0.
Proposition A.10. Let {Xoloee be a o-subgaussian process w.r.t. a metric space (0, I|-ll) as per Definition 3.1, and further assume that è is contained in the unit ball of |1-Il. Let t t2 be arbitrary. Then, with probability at least - 4exp(-tt
cCo Co [1" Vlg.N (9, E +
sup X, S
for some universal constont C O.
Proof. Fix an arbitrary 8u E O. Using Theorem 8.1.6 [Ver18], we obtain the following bound for the increment of the subgaussian process {Xa}.
Pr sup Xg - -Xoll= - Co (/r (o, e)ds + + 1- 2--2exp( LEEE
First, note that for & 2 1,, = 1, since @ lies in the unit ball of 11-11- Thus,
Pr sup X, No.l S Co (Lo VlogN (6, 10,1111,,)dd : 21 21- 2exp(=xp1
(9)
OEE
Note that, by triangle inequality, we have
sup Xx - -xul 2 sup Xoo Xoo 020
(10)
AE
Since {Xalace satisfies Definition 3.1, we have
|Xooll I 20.
From Lemma A.6, we then have
Pr [[e,l S cotl 2 1 eexp(-t"),
for some constant e > 0. Combining this with Equation (10) and taking a union bound with Equation (9), we get
Pr sup Xel S C'a (L, AEB
+ ) 2 -exp(-E)),
for some absolute constant C' > O.
The following lemma an anti-concentration incquality based on Paley-Zygmund incquality. It shows that if the sum of variables is large, one can conclude that many of them are large given an appropriate control over their sum of squares. in [ADHLR24], and it is also similar to Lemma 25 in [DSSUV15].
is given as Lemma A.4
Lemma A.11. Fix n E N and (a1...., an) E R". Let A1 = Ene(n a; and Ag := Eve(n] (a,)².
Then, for every B E R, [ME a; 2 8/n) Z (max [1 -8,0))
A.4 Beta distributions
Next definitions are the versions of beta distributions that we use in this paper. Recall that, classically, beta distribution is supported on [0, 1]. However, in our results, it convenient to consider the rescaled and centered variants.
Definition A. Fix 3 > (symmetric) beta distribution denoted by s-beta (8, 3) continuous distribution, such that, if X ~ s-beta (3,8), then, for every E [-1,1], we have
a (1 - x1)) x2)
Pr 5a)= ["
da,
B(3)
where B(3) 220- (20-(1(())/11(233)
19

---

Definition A.13. Fix 5 > 0 and y E (0, 1]. We define rescaled (symmetrie) beta distribution,
denoted by (-be) (B, B), where for a E [-7,7]] 7/. its distribution given by
9-1
1 Pr(X sa)= BB(3) [r 1 11- 7 )
2
da,
where B(3) 22 (13)3/
We have the following result on the first moment of the beta distribution. Lemma A.14. Fix O. Let X s-beta (3,3) where B 2 Then,
E X 2
3/3
Proof. Let B(8) 229 (13) be the normalization constant. We have
E| = 1
[ [r|[1 - 11(1-=3)0-1d =2)0-1
B(3)
1
/ 2x(1 2218-1
B(3)
B B(B)
It remains to upper bound B(8). follows from Theorem 1.5 of [Bat08] that, for every 1, we have
(0-1/2)
1/2
1/2
x - 1/2 (x-1/2) x-1/2
e
where 22 and b- = 22t are absolute constants. Thus,
88-1/2 20-1
TT3)2
228-182
B(8) T(23)
28-1/2 28-1/2
82 Ve
23
28-1
(23 - 1/2) 1/2
23 - 1/2
8 Ve (23 - 1/2)-1/2 1/2
2T (28 1/2) 11/2
V2e
π (B - 1/4) 1/2
1/2
S π
4,3
,
where in the last line we used
8 - 1/4 / > 3 which holds as 3 1. Thus,
1
1
E X
73
VB
3/3
as desired.
Since the density of the rescaled beta distribution is homogeneous w.r.t. Y, we have the following result.
Corollary A.15. Fir B 2 1 and 7 E (0,1). Let X ~ s-beta (8.3). Then,
E X > 3/B
20

---

B Additional Related Work
Necessity of memorization in learning. A parallel line of work investigated memo- rization using the notion of label memorization in supervised setups. As per this definition, a learner is said to memorize its training samples if it "overfits" at these points. Feldman [Fel20] showed that, in some classification tasks, if the underlying distribution then a learner is forced to memorize many training labels. Cheng, Duchi, and Kuditipudi [CDK22] showed this phenomenon also occurs in the setting of linear regression. While this framework is suitable to study memorization in supervised tasks, the notion of "labels" in SCO not well-defined and thus calls for alternative definitions.
Another line of work studied memorization through the lens of information theoretic measures. Brown, Bun, Feldman, Smith, and Talwar [BBFST21] used input-output mutual information (IOMI) as a memorization metric and showed that 10MI can scale linearly with the training sample's entropy, indicating that constant fraction of bits is memorized. In the context of SCO in l geometry, lower bounds on IOMI have been studied in [HRTSMK23, Liv24]. Specifically [Liv24] demonstrated that, for every accurate algorithm, its IOMI must scale with dimension d. Our approach to the study of memorization is conceptually different since we focus on the number of samples memorized as opposed the number of bits. Nevertheless, it can be shown using Lemma H.3 and [HNKRD20, Thm. 2.1] that the recall lower bounds TOMI of an algorithm (provided that soundness parameter & is small enough, e.g., { = 1/n²). However, because of the Lipschitzness of loss functions in lp SCO, we can use discretization of and design algorithms with IOMI that is significantly smaller that the entropy of the training set, thus, memorization in the sense of [BBFST21] does not arise here.
Membership inference. Membership inference is an important practical problem [HSRDTMPSNCOS; SSSS17; CCNSTT22J. 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 membership inference is inherently unavoidable simply byproduct of specific training algorithms. An interesting aspect of our results is that, for < p S 2, the optimal strategy for tracing depends only on the loss function, which is in line with empirical studies [SDSOJ19].
Private Stochastic Convex Optimization. DP-SCO has been extensively studied in l2 geomelry (see, for instance, [CMS11; BST14; BFTG19; FKT20J). For lp with E [1, 2), the optimal DP excess risk was established in [AFKT21; BGN21J. The best known upper bounds for DP-SCO in Ep geometry for p > 2 are due to [GN21;; GLLST23). In this setting, there is a long-standing gap between upper and lower bounds, and the best known lower bounds are due to [ABGMU22; LLL24], which our paper improves on.
B.1 Detailed comparison with [DSSUV15; BST14).
One might hope that existing traccability results (such as [DSSUV15]) and clever reduction to mean estimation (such as [BST14, Section 5.1]) might yield optimal results for SCO. Here, we will demonstrate rigorously that merely combining results and techniques of [DSSUV15; BST14] yields suboptimal results for the setup of SCO, even in the simple setting of &z geometry. [BST14] considers the following fg problem:
= B2(1,, 2= (+ 1 / f 2) -6, Z).
To apply fingerprinting to establish traccability, we first need to posit a prior distribution over the unknown distribution. [DSSUV15] does so by considering product distributions over Z, and placing a uniform prior over the mean μ E [-1/vd, 1/vdd' We now show that this (Bayesian) problem requires only O(1/a) samples to learn, and thus, tracing 2(1/a²) samples is clearly impossible. Consider the ERM learner Ô. It is easy to see that Ô can be written as:
0
|
21

---

where fi is the empirical mean of the dataset, that is, P 1 Ei= Z, Similarly, the population risk minimizer H* is /z/ 1l The expocted excess risk of then:
--( |10l12 11
E Illella ||āl|2 (1)
E
||u|12" :1/
||A1|2
2 11a112 +
3/2 11A112
(A, 14)
<(a) E
||
|1
flll
-E
4
||
where in (a) we used the AM-GM inequality, and the fact that the expression on the preceding line always bounded by 2. The intuition behind the rest of the argument that, due to the uniform prior on 14, we have [|ll ||l E (2(1) with high probability. At the same time
1 2p pa) S 2n'
11 All
dn
thus, expected risk will be on the order of O(1/n). To formalize this, note that E || = 1/3, and |||l is sum of d independent random variables bounded by 1/vd in absolute value. Hoeffding's inequality then yields that we have ||al1 Z 1/6 with very high probability, Similarly, we can obtain || - All & 1/(2n) + +//36 < 1/12 for large enough n, with high probability. Then, with high probability, event.
E =
|A
2
2 0.1
V6
v12
holds Then, the excess risk is upper bounded by
11)
14
S 2
E
A4
||
1All2
|||K (ll-- All
A ]
[| [Iu- all 4
2 E
(88)
+ + 1(8))
||al12
|
1
E
[0 10
+ PP((())
E (1/n),
as desired.
C Proofs from Section 3
C.1 Proof of Lemma 3.4
We first prove a slightly more general concentration statement to bound the supremum in Lemma 3.4, which will be useful to reuse in other proofs. Let N(O, [e) denote the size of the minimal cover of θ in norm ||+I| at scale & > 0. Then, the more general statement is given below.
Lemma C.1. Fir n, E N. Suppose O Rdd is a subset of a unit ball in some norm II-II- Let o: θ x Z + R and D E M2(2) be such that, as Z ~ D. {Φ(0, Z)} is o-subgaussian process w.r.t. (HII) and for every 0 E O, E[g(0, Z)] 0. Let (Z,...., Zn)) Doon Then, there erist universal consland C > O, such that for every 1 2 0,
10(0, 2,) s Co (Vi+ S/'' Vlog +t)
Pr
sup dEe
Σ i=1
2 1 - (1-4exp(-t))
22

---

Proof. Let Pg denote the following random vector
600,
Φ =
(0,0, Z
Then, observe that, the desired quantity is equal
sup OE
Σ [0(0, Z,)]²
sup le
|olll2
sup 600,
(z, (o)
Then, (xr, Qo) can be seen be random process parameterized by a pair (x, 0). We will show that it is, in fact, subgaussian process. Indeed, note that, by triangle inequality,
(1, 2b) (a', bor S [1 - x', Lo) 1l + [1(x', Le - D0)
(11)
Since o is o-subgaussian for each i, we have by Lemma A.7,
[ - x', Fe) I Co || x'l12.
for some universal constant > 0. Now, for every i, (2g - Do ) is a 110 O'Ilsubbauusian Therefore, by Lemma A.7, have
(2') -
So -
1/2
Combining the two inoqualitics, we get
(x 0o) (x', Do))l Co Coll1 0'll + Co || x' r'112
1
2Co
2 |1|0 0'll + | x (12]
Thus, (x,, 2o) is subgassuua process w.r.t the norm 7, defined as
(((2, 0)) = |||||| + [101]]
Moreover, we can see that θ g--1 subset of unit ball in 7. By definition of 7, we have
(S 7)7,e) <N .1. - (l:Ill)).
(12)
Then, using Proposition A.10, have, for some constant 0, that with probability 1 - 4exp(-t²)
/' VlogA -0-1 s) +
sup Doll2 < Ko
< Ko Sr v Io 11-12, + log N (0; s)dd +
<(a) Ko S.' /
1+ $ ) de + /'' (o: +
mlo
S K vn+ ['' (o: +
as desired, where in (a) we used Example 5.8 from [Wai19], and K' > is some other universal constant.
Using Example 5.8 from [Wai19] once again upper bound Vlg (0; (1l111e))). we have the proof of Lemma 3.4.
23

---

Lemma 3.4. Fir n, E N. Suppose Q C R$ is subset of unit ball in some norm ||-11- Let Φ: Z + and D E (2) be such that, as D, {ō(0, Z)} a o-subgoussian process w.r.l. (0, I. Let (71, 7n)) ~ Don Then, there is conslant C > 0, such that
[0(0, [0)) S Co (vi+ vd+ 2 11-4exp(-())
Pr
sup AE6
11 0.
Proof.
From Example 5.8 in [Wai19], have
log (0; log (e) s dlog (1 (++2)
Plugging this into the result Lemma C.I, with probability at least 4 4exp(-(3) we have
(/+ ''' ( +
Σ 10(0, 2,)1 s Co
sup #E0
Vn + L/¹ / valos (1+ 2 = de +1
Co
CC'a (Vn+ vd+t)+
for some other universal constant C > 0.
C.2 Proof of Theorem 3.5
Theorem 3.5. Fir n N, de N, K 0 and a E (0, 1]. Consider an arbilrary SCO problem
P = (O, I).. Let T = (P; be the subgaussian brace value of P. Then, for some constant c 0, every a-learner An is (g,m) -trccebbee with
n T2
16R2 n
= exp(-cT2), m =
+ d exp(n d)
Proof. We set
T 2
First, we show that the soundness condition holds. Since Z and å are independent, and using the subgaussian nature of Φ0, Z), we have by Lemma A.6
Prz-D [(00 2) > X < exp (-cx²) exp (-CT²/4),
where >> 0 is some constant. For recall, let's define the set I as follows
I= (i E [n] s 2,) 2 A}.
Using Lemma A.11, have
E E
E
fi [n]: o(0, 7.) 2 \1 Σn s(0, 7:) m2
E
En 600, 2,)2
Σ ii @ 2i) n2) 2
E
sup, (60(0, 2,) )
24

---

where for every I E R, we define (x)+ max [x,0) 0}. t == vn + d, we have with probability 4 exp(-=t)).
Then, Lemma 3.4 tells us that, for
sup REB
Z1) ( Zn)
1 (n
2
for some constant C > 0. Thus,
(0 21)...,,, 000, kn)) 1"| s c c(n+ d) 1 21 4exp(-8).
Pr 3 =
sup A20
This implics,
- 2002;)) n1
Z
sup9 [[(((,, Z.) 112
EE 2(0, nn
2 E
1(8)
sup, [(6 1/)12=1112
E (0, 74) n2)
E
L(E)
C(n+
Em @(0, Zz) - -n)
EE ((0,2)) - -nx)²
2
E
1(89)
C Cnn++ + d)
C(n+
We know that, almost surely,
$ 2)2 - n
Thus, almost surely,
(0, 7x) 2)
Σ 00, 7,) nd x Σ
S n 2
(0, Z.)² s k2n2
1=1
Thus,
Σ Em $60, 7z) - nnd nnd)
knn²
E
1(8)
< Pr(E9]
C(n+ d)
C(n d)
4m3n Cexp(n d)
25

---

Hence,
Σ i== 6(0, Zi) mdd ) 2
( $00, Z,) n2)
E | 2 E
E
1(89)
C(n+d
C + d)
Σ t 6(0, Zi) - m2)
4x Cexp(n + d)
2 E
C(n +
m2 1=
Bo(0, 2,) - nn
4k²n
2(1)
C(n d)
Ccxp(n + d)
n 2/22/4
4k2n
C (n d)
C Cexp(n d) 16x²n
T2
=6
n + d
exp(n d)
where (a) follows by Jensen's inequality and = 1/4C.
C.3 Proof of Theorem 3.6
Theorem 3.6. There exists a universal constant e > 0, such that the following holds. Fix E (o), N, d N, a a [0,1, > 0 0, and ō [0, 1]. Consider arbitrary SCO problem P= (0, 2, f) in Bdd Let Tr (r; n, a)) be the subguussian Irace value of problem P. Then, for every (e, DDP a-learner An; we have exp(e) 2 c(T 25k).
Proof. Consider an arbitrary distribution D and function 6 s.t. {Ø(0, leee is a 1- subgaussian process w.r.t. (0, and |ø) S almost surely. Consider a sample Sn (Zi...., Zn) and let Zo be freshly sampled point; let s(i)) be sample with Z, substituted by Zo- Tet i be a learner trained on Sn, and ((0) be a learner trained on ((() Then, since 0 is (s, DP and noting that o(0, 2) is supported on [-x, we may apply Lemma A.1 of [FS17] and get
Eo(0, 2.) - E0( Z.)
S E 6(00), Z.) (exp(s) 1) + 28k.
By independence of Ô and Zi, we conclude that Φ(0, 2x) 1-subgaussian random variable. It well-known that E < Ca if X is o-subgaussian for some constant C (see part (ii) of Proposition 2.5.2 of [Ver18] for p 1), thus the above gives
Eo(O, Z:) < C(exp(s) - 28k.
Then, for every D and e we get that,
E
(0, Z,) s C(exp(E) - + 28k.
1=1
Thus,
T C(exp(s) - -1) 28x,
which, after rearranging, implies the desired result.
D Proofs of fingerprinting lemmas (Section 4)
D.1 Proof of Lemma 4.2
Lemma 4.2 (Sparse fingerprinting). Fix d, n E N and let l: E [d]. For ench μ E k/djd let Zy and Du, be as in Definition 4.1 Let π s-beta (8,3) Ed be prior and set
(0, = 0, Z - d
supp(Z)
26

---

Then, for every learning algorithm An An:2"
2" + MI(A)) with sample S (Zi,..., Znd.
B SiwnlBs,DDD D Am P.k
Σ 00, Zi)
1
2
EuEns (s, 11 W
k
0} as the index of the training points such that their j-th coordinate non-zcro. Then, we have
Proof. For each j E [d], let ==
:= fie [n] 2 +
E
(0, Zz)
=E E
(0)
Z
(13)
IT
= Σ
Σ iEZ,
z
(14)
j=1
Then, define the following function
(12))= = F (0)' (I) (Irre(d, ( Imss.sEm
We claim
Σ (oys. (z) - EE
1 - _ _ [Intrela 12 Imsssae(m) d
k
d dut 9 (11)).
E
(15)
The proof is based on the following two observations: 1) conditioned on {2." Jmf)))E(()) is a function of (Z] he(m]] 2) conditioned on {Irlre(4 the non-zero elements in { he([)] are
sampled i.i.d from [+1} with mean Éu²_. Then, based on these observations Equation (15)
follows an straightforward application of [Ste16, Lemma 4.3.7].
Recall the definition of æ and notice that æ is a product measure. Let T be the distribution on the j-th coordinate. By the definition of the prior distribution, can write
k:
2
o'
E E
1
d
dne
2) 8-1
1
ls
(
dl
d
dd.
du (v)
(v)
1
du
C
d
K:
4/2
1
1 (1-
d
(16)
(2(
du
C
dup
K
*/2
2
1
(1 1
2)
8-1
30
gd (u)de
C
d
29
Euinas [g" (2'))) )a²
27

---

Therefore, we have
B BRow BlawEBs.cce SanDBiy An()))
Σ On, Zi)
mike mik:
d
R
Σ
(0))
d Z
k k
]=1
IE
d
d 2r))
Σ E
E
Σ (0)'
[I 14," Imzjie(())
j=1
iEI,
2B
Σ
E
[ot (1²) 1d]
1:
j=1
where the last step follow from Equations (15) and (16). Then, notice that
E [g wd] = F E (0)² nd {I, breaa (471 (n))
E (0) m0)
Therefore, by the definition of inner product in Rdd we have
E L (x²) [²] = =23 - (0.
2
k
k
==1
as was to be shown.
D.2 Fingerprinting for setup.
Additionally, to prove Theorem 2.6, we will need the following fingerprinting lemma. It can be seen as generalization of reta-fingerprinting lemma in [SU17] using the scaling matrix technique of [KSUU18].
Lemma D.1 (Fingerprinting lemma with scaling matrix). Fix d E N. Let Z {+1 and let 3 > O be arbilrary. Consider arbilrory O < S 1. For every E [->, let D, be the product distribution on Z with mean ,t, i.e., for every 2 E 2, we have
DP = IT= (1+="n²) let An be diagonal matrix of size where the i-th dingonal element given by A 17(2² I- and let (6, 2) (0. p)). Let s-beta (B, B) B)od be prior. Then, for every algorithm An n + +M22(RR) we have
@d
E Epxr E Sa-D BaaannaAni (S(.)
Σ ZES
(a 7) BaN ( (1, B, D0.
2,
22
This fingerprinting lemma is handy for the following reason. To ensure the problem is hard to learn, entries of μ typically need to inversely scale with a. To achieve this, one can select small y in the above to shrink the beta-prior to a smaller scale, while simultancously having the freedom to set / to any value. In particular, this allows us to choose 3 E (log(d)) in the proof of Thcorem 2.6 to leverage the anti-concentration result of [SU17, Prop. 5).
Before we proceed with the proof, we state the necessary lemmata. Throughout this section, for real number p [-1, 1], we will write X p to denote the fact that X is random variable on (+1} with mean p. The following is a classical fingerprinting result.
Lemma D.2 (Lemma 5 of [DSSUV15). Let f: {+1}" + R be arbilrary- Define g: [-1,1] + IR by
g(p) = E Ex [f(x)]
28

---

Then,
Ex-pin f(x) Exx - p) = -11-p")g'') 8Ejm]
Armed with the above result, we proceed to the proof of Lemma D.1. We will first prove per-coordinale version of Lemma D.1. We make note that the proofs combine techniques for beta- fitt-iiiggrrritting results of [SU17] and the scaling matrix technique of [KLSU19; ADHLR24].
Lemma D.3 (Per-coordinate version of Lemma D.1). Let f: {+1}² + R be arbitrary. Let s-beta--nn) (B, (3 be a prior distribution. Then,
- (p/7)² p2
2,3
Byw Exupon
S(X)
Σ
(X; p)
B ppu [p Exxpon [(X)
7/2
i=1
Proof. Let
g(p) = E. x [f(X]]
Then, by Lemma D.2, we have for every p E 1-1,
- (p/2)
(11-(2) g (p).
E Exapon
f(X) Σ (X, p) p-
KE(M]
Recalling the definition of scaled symmetric beta distribution from Definition A.13, we have
(p/7)²
Exp E Xxppon
S(X)
Σ
(X: p)
p2
<E(n)
(
= Eppur
1
p
(p)
7
8-1
7B(3) [
2
(1-(2) g'())dp
11-
2
8
P
g' dppddp
xB(3)
(a))
(1-1
11-
p
2
3
g(p)
-f" (1-())))
(())
BB3)
(1(1-00))
3-1
28p g())d
1
BB(3)
y2
2
72 parn (p)])))
where in (a) we used integration by parts. This concludes the proof.
Applying the above results to each coordinate and summing the equalities gives Lemma D.1.
Lemma D.1 (Fingorprinting lemma with scaling matrix). Fix d N. Let Z {+1] a and let 3 > 0 be orbitrary. Consider arbitrary < <> S 1. For every P E 7- let Dp be the product distribution on Z with mean μ, i.e., for every 2 E Z, we have
Dj, = IT (1t²4²) lel Ay be diagonal malrix of size where the i-th diagonal element
29

---

is given by A 120 1 and let (0, (0, -p))- Let ग s-beta (3, (3, 3)o0
be prior. Then, for every algoritlm An 2 + Mi (I."), we have
Ep S. DDO (Sn)))
Σ 2E9
Su 2)
23
Bl (Rr Bs.DD (m.,,))))))
72
Proof. For a sample S, = (Zi,..., Z and j E [i], we will use S E R to denote a vector
(Zi..., 2h, of jth coordinates. For each coordinate j E [d]. let fz: {+13" - R the function such that
ff(S)) - Burntlis ( 0 S
In other words, (X) is the expected value of 0,, given that 5th coordinates of samples in Sn are given by X. Applying the result of Lemma D.1 to fy, we have
Bud wns
E 5% (uu))nn No N/ -
[5(S
2 12))
1=1
- (nL /7)
Sz(SH) (z) w²)
1 (1e)²²
i=1
2B
72 Buinns [ Bug Beg
By the law of total expectation, get
EysrE s, ND (n.)
AP d Σ(z] -2))
7/2 Uunu - ( (mAA.(
2
i=1 Finally, summing the above over all coordinates j [d]. we obtain
(
A Σ (Z 1) m)) )
a
2,
( ( (0
SS (
B
72
as desired.
E Hard problem constructions and proofs of subgaussian trace value lower bounds
E.1 Proofs for l--geometries (Theorem 5.1)
First, recall here the construction of the hard problems Pk.p in Equation (7), parameterized by l E [d]
=0,=11= |I=loo = k}, f(0,2) = - (4-1/1(0,2) z). First, we show in the simple proposition below that a-learners for linear problems must agree with the distribution mean.
== (dd
(Pkp)
Proposition E.1. Let An be an a-learner for Pk.p- Let D E M2(Z) be a distribution with mean μ = EEND [Z]. Then, we have
E DDa (S..) [m,0)] 2 1/0 || - 11/00.
Proof. Since An is a- learner, have a [D(
inf (o) AEE
E ESADDan An EZnD [(0,2)] inf EZ~D (0, Z)
1/4
sup Ez~z (0, Z) Es ES,NDen in EznD (B, BEE
S in A..Dssn (0.))))0)))))) (0.1))
11/4
sup (0, n) - EE 8Ee
30

---

which, after rearranging, becomes
E SS..Daa,
(u,
2 sup (11, 0) - k2/4
050
d 1/8 || b2/
where in the last transition used duality of lo and l norms and the fact that O (d This concludes the proof.
In the next lemma, we show that every a-learner for Pkp needs to have large correlation with the training samples in order to achieve small excess risk. The proof is an application of Lemma 4.2 combined with Proposition E.1.
Lemma E.2. Let S 1/6, and suppose l E [d] is such that & 2 (6a)Pd. Then, for every a-learner An for Pk.p: there erists μr E i-k/d, k/dd and distribution D E Mi(2A) with
mean y such that the following holds: let
d=/v
d Tta²
600,7) 7.
0,
Vk
supp(?)
then,
d-11/p
E D
Σ Ó10, Z.)
18k-1/21/PdL
Proof. Let
kLip
2
B
2 1,
6dd
and π s-beta 9). Then, using Corollary A.15, we have
Buwa [|la|]]] dlC dlp | k/d d
3/3
Stk2/p/6d'>/0
20d-/pp1-1/9
Then, using Lemma 4.2 we have
D Eyps
E Sp
Σ
n
0, Zi
2d3
E
Eyoa E
BS,.DR De (rdd((a)) (ur))
k
supp(Za)
2d
E
Exax d
d- 1/0 || 11/90]
k
2d3
(6)
d d
2ad 12/
2d
k2/P
k/
k
6dliva
2d
k2/p
k/
k
6dl/pa
d
1//2/pb//p
18a
Since the above holds in expectation over draws of μ, there exists at least one value of for which the above holds; let D DR. Then, letting
600 2) = dl/p
d
0,
Z
vk
supp(Z)
31

---

we obtain
dlip
0, (z Vk
E Don (S.
Σ 000 Zi)
= =Ep E
mmm Bs, 1
Zi k supp(Z:)
M.M
d'-1/9
18k1/2-1/Pa
as desired.
We now argue that the pair (Ø, from the lemma above (with ø scaled by some con- stant) constitutes valid subgaussian tracer. In particular, the lemma below shows that {o(0, Jee induces a O1)-bubgaussia process w.r.t. (-Ile) norm.
Lemma E.3. Fir d E N. Let μ E (-k/d, k/dl be arbitrary. Let Φ : 2n + be as in Lemma E.2. Let Du, be the data distribution from Definition 4.1 for some μ,, and consider ~ Pp. Then, {ø(0, Z)e is a C-subg process w.r.t. to (0,11-Ile) for some universal consland C C>0 0.
Proof. Let E ((11 be an arbitrary coordinate subset of size k and, recalling Definition 4.1, let Z, be random variable with PMF given by PER.J. Then, Z is a uniform mixture of {ZJ} ((())
Fix J E (o)) and let 01, 02 E θ be two arbitrary points. First, upper bound subgaussian norm of Φ(01, ZJ) Φ(02. Zz). We have
d//p
|, Z,) 0002. 75)
1100
02
Zs)
Vk
d'/r
Σ (0f 03)233
Vi
jEJ
d//r
10) Bb)Zz 2
(n)
C1 Σ
Vi
jEJ
d/p
(8)
C1 Σ
C2 - -0/22
VT
JEJ
d/v
VC,C2V 10 8211o0
Vk
(c) VCIC2 10 - 02lle
where C1,2 universal constants, in (a) apply Lemma A.7, in (b) apply Propo-
sition A.9, and in (c) use that, since θ = B (d-1/9), we have Il d3/p 11 Thus, letting C = VCi,, have
[1o(0,, - 0(02, Zy) S cc - 02lle
Now, note that @00, Z) - 6(02, Z) has the same distribution as a uniform mixture of {ø(01, Zy) 662, Z, Z)))))(())) Then, by Proposition A.8, we also have
10(0,,)) (02, 2) < <C 0zlle:
which satisfies the first condition in Definition 3.1. Finally, by plugging 0₂ = 0 into the above, we have
(001,2) < C SC which satisfies the second condition in Definition 3.1. Thus, (0(0, Z) is C-subgaussian process w.r.t. (0, || lle), as desired.
Finally, we lower bound the subgaussian trace value of Pk.
32

---

Lemma E.4. Let a S 1/6 and d N be arbitrary, and let k E [d] be such that k S (6a)dd. Let PR.p be as in Equation (7). Then, the following subgaussian trace value lower bounds hold for every E 00) and some n S savd,
d1-1/v
Tra n a) 2 02 11/2-1/Pnn
where C1 > are universal constants.
Proof. Let C > O be the constant from Lemma E.3, and e be as in Lemma E.2. Then, {o(0, JoEC is 1-subgaussian process w.r.t. (θ, || ll. Moreover, 600, Z)/C S vk/C va/C. Then, letting = vd/C and using Lemma E.2, the subgaussian trace value of Pk.p can be lower bounded by
Tr (PR a) 2 - Eg SD
1 Σ
600 Z,)
2 18C k1/2 24/2-1/Pna'
d'-1/v
C
as desired.
Now we are ready to prove Theorem 5.1.
Theorem 5.1. Let Pk. be the family of problems described in Equation (7). There exist universal constants C1,02 O such that, for all [0,1/6] and d E N, the following subgaussian trace value lower bounds hold for all p (o) and S vd:
(i) For p 2 and k = d, we have Trx (P. n, a) 2 02 no
(ii) For p and k- (6a)'d 1, have Tr (Pkpi n, a) 2 02 ((Ga))/ A d'-1/p)
va
na
Proof. The theorem is a direct consequence of Lemma E.4. For S 2, plug in A = d into the statement of Lemma E.4. We obtain
d' d1-1/2
Vd
Tr
2 02 11/2- 1/Pnac 02 na
For p 2 2, plug in (6a)) v 1. We obtain,
d1-1/P
TPx n,aa)a)))))))) a) 2 02 11/2- I/Pna
-111/p
Vd (6a))(1)) 122 1/p)
02
71
d111/9
Vd
02
^
(6a))/22
71
as desired.
E.2 Proofs for li-geometry
E.2.1 Intuition
Refinement for 1. While the above construction also yields traceability result for p p=1, 1, it is suboptimal for the following simple reason: for = d, the problem in Equation (7) only requires ((1/a²) samples to learn, thus, it is impossible to trace out ((log(d)/a*) samples. On the other hand, the problem in Equation (6) requires ((lo(d))aa)) samples to learn but is not traccable. The intuition in Equation (7) to make θ "look" more like an ballll to drive up the sample complexity while still avoiding the counterexample with ERM learner from the beginning of the section. In partieular, we consider the following Ei-problem,
follow here is to modify the construction
θ (1) n (1/s), Z z= {#10 f(0,2) (),
(17)
33

---

for suitably chosen E [d]. Note that, if we choose > 1, è above is polytope with much more vertices (2 (2)) than & ball (2d), which would intuitively force learner like an ERM to reveal more information about the training sample. On a technical level, selecting large improves the subgaussian constant of tracer; however, selecting that is too large shrinks the diameter of the set, and thus, the problem becomes casier to learn. We must trade off these two aspects, and carefully set the value of As it turns out, the optimal choice x d'-c for an arbitrary small c > 0 in order to establish Theorem 2.6. The remainder of the proof is rather technical and hence is deferred to Appendix F.2.
E.2.2 Formal Proof
For technical reasons, we will need the following refinement. Lemma 3.4 for the special case when the function & is convex and θ is polytope. In the proof, we use Lemma C.I. Lemma E.5. Fir n, d E N. Suppose @ C IRd is (i) subsel of a wnil ball in some norm |1-11- and (ti) O is a polylope with N verlices. Let Φi O conver in its first argument. Let D E (M be such that 6(0, 7)) is a o-subgaussian process w.r.t. (0, [ill)).ee (Z,,..., Zn)
R be mensurable funclion that is
Den Then, for every 2 0,
Σ [0(0 Z.))² s Co [v++ Vlog(N) + +0] 2 1 (1-2exp(-1))
Pr
sup 8Ee
where > 0 is some universal constant.
Proof.
Similarly to the proof of Lemma C.1, let t9 denote the following random vector
[1)
P =
660, _n.
Then, observe that, the desired quantity is equal to
Σ [o(0, 2:)1 sup 11 sup BEB
sup 600.
(x, Qo)
BEG
Let be the set of vertices θ with [V] S N. Since & is convex in its first argument, the supremum above is attained in one of the vertices of θ Thus,
sup O
Σ (0 Z,)²= =
sup BEV.
(x. Po) = sup
Σ
10(0, 2.)
OEV
Thus, may apply Lemma C.1 to V instead of θ Trivially, we have
Then, have with probability - (exp(_(9)
(0(0, 23) s Co Co (vn+ ( (ed +
Σ i=1
sup dEB
< Co (Vi+ Vlog(N)+
as desired.
Intuitively, in the special case when θ is a polytope, the log-number of vertices becomes "elfective dimension" instead of d, due to the fact that & satisfies the convexity requirement. In some cases, we can have d > log(N), in which the above gives a lighter concentration In particular, this case our construction for l geometry in Equation (17). With the above result,
also establish the following refinement of Theorem 3.5.
34

---

Theorem E.G. Fir N, dEN, K > 0 and E [0, 1]. Consider an arbitrory SCO problem
(0, f,,, and suppose θ is a polytope with >> 0 vertices. Let 'T' be defined as,
:= (P; n,,,,, a)..
Then, for some constant > 0, every a-learner An is (E, (5, -tmccbbbee with
T2
16x2n
{ = exp(p-
m =
+ log(N) exp(n + log(()))
Proof. The proof is identical to Theorem 3.5, but using Lemma E.5 instead of Lemma 3.4, and thus, replacing d with log(N) everywhere. We omit the details.
Now, recall the construction from Equation (17),
2 == (
- o Bi( (1/j)), (0,2))-(0,2
(18)
is easy see that S(; Z) above 1-Lipschitz w.r.t. as 2 c (1). We have the following claim.
Lemma E.7. Let Ps be as in (18), n E N and 1/8 a > 0. Then,
cvElog T6(+v14)
Tre (Ps;
n2
where R S d' for some constants e, >> 0
Proof. We aim to use Lemma D.1 to characterize the subgaussian trace value. Consider the construction of the prior Lemma D.1 with the following parameters: 7 8a S 1 and
8 8= 1+ + log ( Then, by combining Lemma D.1 with and Proposition E.1, there exist a prior π and a family {A₂} of diagonal matrices with non-negative diagonal entries bounded by 1 from above, such that
n
23
B B.pueeRReeeee
0.
An - 11)
B
B
sup
(0, 14)
722
0
23
1
E
B
sup
|4|
722
8
scld|
|1|=8
(a)
3
7
2a
2
2
log
d
16(sV14)
IV
-2a
32a
log
d
16(av14)
16a
where in (a) we used Proposition of [SU17]. Since this holds in expectation over μ, it holds
for least one choice of μ. Let a be that value. Now, let 600, 2) C-1/2 (0. A(Z u)) where C is the absolute constant from Lemma A.7. For all 0, 0 O, we have
[0, 2) (0', !)
SC- V8 (1 - 0, (7 1
<(a) C-2 V8 10' 0122 1/2 max || (Z' 18'--''' -p0)l
S V 110' - 011
< (b) 110' - Alle
35

---

where in (a) we apply Lemma A.7, and in (b) we use that for every E O we have
|10112 - 1/vs, thus, /s Il-1l2 s ll-lle. Plugging 6' gives
llo(0, 2) 1/2 I ||@lee S Thus, (é(0,2))oer is l-subg process w.r.t. (0, (1-ele)) Finally, we have 10 2) - C-1/2
Therefore, setting 1/2 V and noting that ø is linear (and therefore convex) in its first argument, we have
n
Trx (Ps n,
BunT Bn 8m
6(0. 2,)
n
C-1/2 V8 log
16(sV14)
as desired.
F Proofs of the main results (Section 2.2)
F.1 Proof of Theorem 2.5
Theorem 2.5. There crists universal constant e >> O such that, for all E (1,2), if d, n,
& E (0, 1/e), and a > 0 are such that
d
1
Vn
Sas min min
( n² log(1/E))
6 6
(3)
then there exist an E, SCO problem that every a-learner is (E, m)ttrccebble with m E EQ (3).
Proof. We begin by noting that the interval for in Equation (3) non-empty only if
d 1
d S c. n
S min c' n² log(1/E) 6
vn
where used & < 1/e in the last transition. Via straightforward algebra, the above implies 2 n, thus, we may without loss generality assume 2 n in the remainder the proof.
Let Pk.p be as in Equation (7), and set h as in Theorem 5.1. Then, Theorem 5.1 gives the following lower bound on the subgaussian trace value in this case:
Vd
log )
T = Tr. (Pkp:n))
for some R cvd. Thus, provided small enough (c 62), by Theorem 3.5, every a-learner is -traccalee with m satisfying, for some universal constant c' > 0,
T
16k
m
exp(n d) 71 +
d
1
16c
2 c'
n +
a²
exp(n +
c2
16cf
(19)
2
a2
exp(d)
where we used 2 n in the last incquality. Then, we have
m E Ω
2
as desired.
36

---

F.2 Proof of Theorem 2.6
Then, the proof of Theorem 2.6 follows.
Theorem 2.6. There erists universal constant e >> 0 such that, if d is large enough and E (0, 1/e), and > are such that
log(d) sas min ( n (Voog(1/E) 8) then
d
c.
(4)
there erists l SCO problem that every a-learner ---aacccbbbleee with E Q (log(d)/a²))
Proof. We begin by noting that the interval for in Equation (4) is non-empty only if
log(d) (d) c.
0.49
d
Se.
S
nr/og(1/E)
n2
where we used g << 1/e and c above implics d log(d) n, thus, may without loss of generality assume d0.98 /log(d) 2 n in the remainder of the proof.
< 1/6 in the last transition. Via straight forward algebra, the
Let d Note that, letting V be the set of vertices of the polytope θ Bl) we have
2 0,
1=:10 }
The proof of this fact is straightforward and it is based showing that every point in θ can be written as a convex combination of the points in V. Thus,
V log 2 c (x)))
log
S slog(de/s) + slog(de?) /s).
By the choice of 8 and using Lemna E.7, we have, for some A S C1 v
0 log
16(sV14)
T == Tr (Pa:
na
0.49 log
d
(a)
C2
na
0.49 log
g0.02
16
0 (0.02 log (d) log((6))
C2
na
d
0.01
log (d)
(b) 02 na
(() /lg((L/E)
where (a) and (b) hold provided d (and thus s) large enough, and (c) holds provided e in Equation (4) is small enough. By Theorem E.6, every a-learner is (g. m)-traccabb,,,, where
16x
m 2
n + log V exp(n + log [V]]
0.012 0 log(d) log(d) n log V
16c sn
a²
exp(n + log [V]
2 n log(d) > n (for 2 3). Moreover, log [V| < s log(de2/s)) = d0.9 log(e" 000) 0.98 log(d), for some universal C' O. Thus, for d large enough,
Recall that 0.98
(og(d) a
m E Ω
as desired.
37

---

F.3 Proof of Theorem 2.7
Theorem 2.7. There erists o universal constant such that, for all p e (2, if d, n, E (0, 1/e), and a > O are such that
d 1 min 1/p vn }
+ S min for (o: )
(
d 1/p
then
(5)
In log(1/E)
6
there crist on lp SCO problem such that every a a-learner is (5, (55m))trume -tttrcabblele with m Ω (1)(6)))).
Proof. Throughout, we assume is a sufficiently small constant. Assume 1/6. Then, we begin by noting that the interval for in Equation (5) is non-empty only if
1/2 -
1/P
cc n (n
6 n/r
n²
where we used { 1/e and 1/6 the last transition. Via straightforward algebra, the above implies d 2 thus, may without loss of generality assume d 2 in the remainder of the proof.
Let Pk.p be as in Equation (7), and set i as in Theorem 5.1. Then, Theorem 5.1 gives the following lower bound on the subgaussian trace value
d-11/p
Vd
:= Tre (Pkpi 2 02
(20)
na
(6x))o/22
for some C1 Vd. Note that, from (5), we have
1
1/v d//r
Now, note that, the minimum in Equation (20) is achieved in the second term iff 2 d'1/p/6. Then, the lower bound on the subgaussian trace value becomes
Vd
T C2 (6a (6a) (6c)a/2
C2
Vlog(1/E) 2 Vlg((1/E)
where the second transition follows from Equation (5) and the third transition holds whenever >> 0 is small enough (e.g., when S o² /2///6). Then, by Theorem 3.5 every a-learner is (E, m--traccealee with m satisfying, for some universal constant > 0,
n TT
16x²n
c'
d
exp(n d)
2ad
1
16c
c
d
(6a)) exp(n d)
3 1 16cf
c
(21)
2
(6a)² exp(d)
where we used a in the last transition. Thus,
m E Ω (6a)))
as desired.
F.4 Proof of Theorem 2.8
Theorem 2.8. Let p [2, There exist a universal constant e > 0 and an lp SCO problem p (0, 2) such that every (E, (E learner of P with I and d < c/n satisfies,
a 2 c. min {
11pp
1/p
fnp
en
38

---

Proof. By Theorem 5.1, for some problem P, we have
d=-1/p
Vd
T: Tri (P;n, 2d
na
non/2
Then Theorem 3.6 implics
exp(s) - 2 c" [T 28x]
Note that for all E S 1, we have 25 2 exp(E) 1. Thus,
2: 2 e' [T' 26x]
which implies,
dd'1//
vd
2(E/c"+ 2 T 2
n1
nap/2
Then, for some C >>0 0,
d2-1/p
Vd
C(e V ok)
na
nop/2
Rearranging gives
2/D
d'11/v a Onls V 5k)
Vd Cn(ee V ok)
Note that if 2 5k, the desired bound is immodiate. For ōk 2 E, we have, since 2 c/n and S cVd.
2/p
d-1/p
Vd C'va)
2 (C')
C' Vd
for some C² > 0, as desired.
F.5 Proof of Corollary 2.9
Corollary 2.9. Let 2 = {+1]d and suppose an estimator is given such that, given access to í.i.d. samples Zı...., Zn E Z, outputs f with Ei-El, x I a/2. Then, there enists a universal constant > 0 such that, if d is large enough and n, E (0, 1/e), and a > 0 satisfy Equation (4), then the estimator ft is (3.m))trceeabl with m E Ω (log(d)/a²).
Proof. We will first show that can the mean estimation algorithm to solve the corresponding hard problem for S--CO. Specifically, consider the SCO problem as in Equa- tion (17), and define the following learning algorithm based on the mean estimation. Let be the output of mean estimator based on the samples Zi...., Zn, and let
= arg max (0, fi).
lee
Let 0* be the population risk minimizer, and let μ be the true mean, that is, μ B[Z]]. Then, the excess risk of Ô can be upper bounded as:
(0 1) (0.z)
lr 0 11)
0" 0, (B) -0.-
8*
||I All x + (0r - -8,1)
<2 All + (0r 0.P.).
where the last transition follows since Ú, 0r both lie inside O c Bi. Now, by the choice of 0 the second term is non-positive. Thus,
(8', 0, 2 211 Alloc
Taking expectations on both sides, we get
E E00", n) (0,1) < 2E ||u All S a.
Applying the result of Theorem 2.6 to 0 conclude the proof.
39

---

G Connection between subgaussian trace value and non-private
sample complexity
From the main part of the paper, observe that the subgaussian trace value is typically inversely proportional to a. We start by proving two innocuous results (Propositions G.1 and G.3) that establish an absolute upper bound on subgaussian trace value. will then allow us to extract lower bounds on a by plugging in our lower bounds on subgaussian trace value (Theorems G.2 and G.4). We start with the p E (1, 00) case, and then consider p
G.1 Lower bounds for p E (1,
Proposition G.1. Fix E N, N, and E 1]. Consider an arbitrary SCO problem a)) be the subgaussion trace value of problem P. Then, p = (0, in Rd. Let we have
for some universal constent C> 0.
Proof. Let (Ø, D) be an arbitrary subgaussian tracer. Consider the process {Xo) defined
as
Σ 600 Z,),
No =
where Sn = (Zi..... Zn) ~ Den We will argue that {Xolses is subygassanaaaaaaa process w.r.t. (0, (1.))e) First, consider arbitrary 01, 02 E θ. We have
[o, Xo. 1l
Σ im
(ó(Z,, 81) o(Z,, 02))
1/2
C
(a)
|0 01) - MiZi, 02) 12)
m
<(1)
C
Σ
00 - 122le
n
C' 110 02lle
where (a) we applied Lemma A.7, and in (b) we used the fact that (Ø(0, 7,)e is l-subgaussian process w.r.t. (0, lI-lle) for every [n]. Moreover, for every 0 E O similarly have
1
Σ i=1
Φf
(z, A)
(a)
|| | Zi, 1)1
(b)
|0lle
C
|
where (a) we applied Lemma A.7, and in (b) we used the fact that (0(0, 7,) 1-subgaussian process w.r.t. (1-1l) for every i E [no]. Thus, {Xalace is C/Vssugguussian
40

---

process w.r.t. I-I1) as per Definition 3.1. Therefore, by Proposition A.10, we have, with
probability at least 1 4 1exp(p==
Ct
L''
sup 8
71
000 2,) ==1
vn
+
V
V /lgg/ (o; 11 E)de
Ct
C
L''
[1 2 8
V ddlog
de
Vn
vūl
Ct Cvd
Vn
C
V
+
(22)
vn
where in second inequality use [Wai19, Example 5.8]. Hence,
1 12 (b0,,
E sup REB
Zi)
Pr
sup
600 Zz)
du
n
8EB
d
1 n
d CV.
C
Pr
sup BE
(0, Zi)
du
7
T1
n1
C
/
1
d
Ct
CV n
+
Pr
sup #E0
10 2.)
C
dt
VT
n
vn
CV P
C
+
4cxp(-
vn
d C"
sC
22(CVC)) d
where C² is some universal constant, (a) follows by change of variables CI/ and (b) follows from Equation (22). By Definition 2.3, we can write
Tr. (P; = inf
sup TES.
E [5,, Zn) A (n
$ 7z)
a-learnerA,
vE(n)
S sup TETx
Es, (a)
sup Σ 210,2z) EE :E[n]
< 2(CVC))
By rearranging the terms we obtain the desired result.
We now show that Theorem 5.1 implies lower bounds on the sample complexity of learning 6p-Lipshitz-boume bounded problems for every e [1, oo). In particular, we show that the problems considered in Theorem 5.1 require many samples to learn (equivalently, we show a lower bound on optimal excess risk a).
Theorem G.2. Let a > O, p E [1, 00) and n E N be arbitrary. Let PR. be as in Equation (7), and set k as in Theorem 5.1. Suppose there exist an a-learner for Pk.p. Then,
(i) for p E [1,2], we have
c
a 2
41

---

(it) for p (2, we have
1/121111
A V1
n/
for some universal constant e > 0.
Proof. First, consider arbitrary k E [d]. We apply Proposition G.1 to the result of Lemma E.4. We then have the following double inequality
d/v
d n
S Tr, (Pkpiin S SC
C2 1//2-
Solving for a in the above, we have
C2 (d/1)1/2-1//
a 2 C
Vn
First, consider the case p p [1, 2]. Then = d, and we have
1
C
Vn'
as desired. Now, consider the case E (2, x). Then k- = (6a)Pd V 1, and have
(221)
(1/6a)p/2-1
d1/2-1/0
C2
ni
vn
Solving for o, have
a a
(
(
C2
2/p
C2
d1/2-1/0
72
C
vn
Note that, since 2/p < 1, have
2/2
1
602
2/p
602
C6
6
C
c
Thus,
d /221//1
02
A
Vn
vn
as desired.
G.2 Lower bounds for =
Now, consider the case p= 1. For p will need the following refinement of Proposition G.1 a special case when θ a polytope with few vertices. Intuitively, d in the statement Proposition G.1 can be replaced by log N where N is the number of vertices of e.
consider the problem in Equation (17). We
Proposition G.3. Fix ne N, d E N, and a E [0, 1]. Consider an arbitrary SCO problem P = (O, f) in Rd, where θ is a polytope with N vertices. Let Tr. (P,(P;, n,,a) be the subgaussian brace value of problem P. Then, we have
Tr. (P;n,a) Vasc. VlogN,
for some universal constont C 0.
Proof. Let ()) be an arbitrary subgaussian tracer. Similarly to the proof of Proposition G.I, consider the process (Xo Joce defined as
X
(0, Zc),
n
42

---

where S = (Zi...., 2n) ~ Deon As in the proof of Proposition G.1, (Xoloee is a C/Vn- subgaussian process w.r.t. (θ, ll-lle) for some universal constant C' 0.
Let be the set of vertices of θ; then |V| = N, as per the proposition statement. Since e is convex in its first argument, the mapping 0 ~ Xo is also convex (almost surely). Then,
sup X = sup [xol RE0
VeV
Thercfore, by Proposition A.10, we have, with probability at least 1 - 4 exp(-1?
Ct
C
L' VoRR (V; (V;
sup AE
11
Σ i=1
(0, 21)
S
Vn
+
Vn
s)de
C
C
I'' Vlog Nde
V
vn
Ct Cvlog.
Vn
Vni
Hence,
n Σ
11
Ssup
(0, 7,)
Pr
sup AEE
(00
Zz)
1 du
1 i=1
n
log N
n Σ
log N
]
CC
Pr
sup 6E
(00 Z:)
> >C
+ u du
n1
J0
11
1=1
"
<(a)
CV
log N
+
C
Pr
sup AE
1 n
10, 2i)
> C
log
+
Ct vn
Vn
0
71
n
log N
C
(8)
4 4exp(-
n
Vn
s <C log N
C
n
Vn
log N
S 2((CV
where C² > 0 is some universal constant, (a) follows by change of variables Ct/VT. and (b) follows from Equation (22). By Definition 2.3, we can write
1
Tr, (P; A.
inf
sup TEIR
(5,=(22.... b (~An(SA)
$10 2,)
vE[n]
S sup Tef.
Zn
sup Σ #E n *E|m]
6(0, Zx)
log N
< 2CCC'))
By rearranging the terms we obtain the desired result.
Then, sample complexity lower bounds for geometry follow.
Theorem G.4. Let 0 and n E N be arbitrary. Let P, be in Equation (17) and set
s = 0.99 Suppose there erists an a-learner for P.. Then, for large enough d, we have
log(d)
2
for some universal constont > 0.
43

---

Proof. Lemma E.7 gives the following lower bound on the subgaussian trace value of Ps.
Tre (Ps:n, cv3 log 16(sV14)
na
At the same time, noting that + is polytope with vertices given by
2 E 0, _ } 1 = 8
which has cardinality
[V d s
de
have by Proposition G.3
Tre (Ps;,, S CV. s <log(de/s)
n
for some universal C' 0. Combining this with the lower bound subgaussian trace value, we have
cv/s (66(811)) na
slog(de/s)
CV
n1
which gives
log 16(sv14)
C /log(de/s)r
Recall that s = 00.9 For large enough d, we have s V 14 s. Also, note that log(d/s) 2 log(d)/100. Then, for for large enough d, we have
d log(d)
7
for some universal d' 0, desired.
H Traceability of VC classes (Section 1.1.1)
First, we state the main result.
Theorem H.1. Pix N and & 0.1. Let H be an arbilvary VC concept class with VC dimension due- Then, there exisls an oplimal algorithmm in lerms of number of samples such that it is of thresholds, we have E (1).
m) -traceabee with S O (die log" (n)). Moreover, when H. is the class
To prove we use an information iitimaatioon-heoretiie notion that controls the difficulty of tracing from [SZ20].
Definition H.2. Fix n E N. Tet D be data distribution, and An be a learning algorithm. For every N, let Z (Zz,s) (0001)) be array of i.i.d. samples drawn from D, and U = (UI,.., Un) Ber (1) @n where U and Z are independent. Define training set S. (Zu,,)iEn)) Then, define
CMI (A.) = := (A.(s.))
In the next theorem, we show that the existence of tracer for learning algorithm provides a lower bound on the CMT of the algorithm. similar observation made in [ADHLR24]..
Lemma H.3. Fix N such that > 2 and < 1/2. Let An be arbitrary learning algorithm that (f/(n log(n), m)--maceable.. Then, it holds supp CMIp (An) 2 m - 35.
The following two results from [S7:00 and [HDMR21] provide upper bounds on the CMI of sample compression schemes. We skip the formal definitions of sample compression schemes and refer the reader to [LW86; MY16; BHMZ20].
44

---

Lemma H.4 (Thm 4.2. [SZ20]) Let H. be an arbitrary concept class with VC dimension duc. Then, there ezists an algorithm such that for every dota distribution D, CMIp (An)) S Oldee log((n)) (n)).
Lemma H.5 (Thm 3.4. [HDMR21])- Let H. be the concept class of threshold in R. Then, there enists an algorithm such that for every data distribution 'D and n 2 2, CMID (An) S log 2.
Proof of Theorem H.1. The proof is simply by combining Lemma H.4 with Lemma H.3. For the case of the class of thresholds, we use Lemma H.5.
Proof of Lemma H.3. Assume there exists tracer with recall of and soundness parameter of log()n). Let DD denote the distribution used by the tracor (see Definition 2.3). Define the following random set
y = {i E [m] : 3j E {0, Φ00, 2,,)) 2 A and s(0, Z1 < }}.
Also, for every E [n), define the following random variable
g. (0(0, Zo.a) <}.
By the definition of mutual information and U 1L Z, we have
CMI)(A,) H(U) H( ZZ = n - H
(23)
(24)
Therefore, to lower bound CMI)(An), we need to upper bound H(U|Z,0), 0). By the sub- additivity of the entropy, have
H(U) S Σ H(U.)Z,0).
1=1
Then, by monotonicity of the entropy and the chain rule, we have
H(U 0) < 9, 0)
I H(G:) + H(U,GG, 2,
(25)
In the next step, by the definition of conditional entropy,
H(U, 0.9.) < HUU, = + Pr P9, = 0).
Define the random variable =1 e v²). Notice that Y, is (0, Z) measuraall random variable. Then, using the notations for the disintegrated conditional entropy from [HDMR21),
1
we have
H(U, 2,0,9, 1) E H (=200.111(3)) (U.)
11 0. (U.) 1(Y, = 13} + + [1 1(Y = 00)
(26)
The main observation is that under the events Y, 1 and 9, 1, U, deterministically known from (2.0). Tt follows because
(Y=1) (9, 1) (0(0, Zz,)) and 6(0, 7133s) < <} A (0.0 < = U, =
Therefore, since -1 (U.) < 1 with probability one, by Equation (26)
H(U, 0, g 1) < PY
Thus, from Equations (25) and (26), we obtain the following upper bound
H(U,Z,00 0) < Pr (Y: 0) + Ho (G = 0)) + Pr (G. 0),
45

---

where H₂ (-) : [0. - [0,1] is the binary entropy function defined as Hy (x) -r log(())
(1-z) log - z). We can lower bound (A,, follows
CMID(An) 2n
H(U
2 2n
Σ
Pr (Y; = 0) + Ho (Pr - 0)) + Pr =0]
1=1
Σ
= P Σ (Hs (Pr (9: = 0)) + Pr (g, = 0)),
where the last step follows because n - - (Y, = Σ (Y; 1) as Y, is an indicator random variable. In the next step, by the definition of soundness from Dcfinition 2.3
and the definition of CMI in Definition H.2, we have
Pr (9; =0 = E [rr -9:
= Prs,- DDR DD D. (((,
S {/ log(n)),
Therefore,
CMIp(An)) 2 Σ PV, 1)
nH, (no(()))
& n
log(n)
By the recall condition from Definition 2.3 and the definition of CMI in Definition H.2, have
(71....n)) 7n. (n.)())) [ [m] s(0, Z,) 2 ^|]
E
Pr (0( Zi) 21)
Pr (0(0, Zo.rt 2 An + PP
Σ
PY 1)+
Pr (g
g
Pr(y 1)+ log(n)
We also use the following well-known inequality, H₂ (x) S -xlog(x) + x for x E [0, 1]. As result, we obtain
E nH,
CMI,(A,) N
Σ
Pr (Y,
=
log(n)
log((n)
1=1
2
g
E
log(n)
n
n. log(n)
(n. log(n))
log
(n. log(n))
3
2 m
log(n)
where the last step follows because -x log(z) $ 1/e for E [0.
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and the introduction capture the precise thcoretical claims made in the main part.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The rbstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification: It has been discussed when comparing with prior work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g,, independence assumptions, noiseless settings, model well-specification, asymplotic approximations ouly holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
taken in low lighting. Or speech-to-text
The authors should discuss the computational efficiency of the proposed algo- rithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
47

---

For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Question:
Answer: [Yes]
Justification: Every theoretical result is presented in form of a theorem stating all assumptions made.
Guidelines:
The answer NA means that the paper does not include thcoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross-reforenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper inchudes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reprodueible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that appropriate to the rescarch performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) the contribution primarily a new algorithm,, the paper should make il clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
48

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e-g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sulficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer:[NAl
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines
cc/ http.////w////.eeeeeoeooeooooooo
for more
details.
The authors should provide instructions on data access and preparation, in- cluding how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question:
Docs the paper report error bars suitably and correctly defined other appropriate information about the statistical siguificance of the experiments?
Answer:
[NA]
Justification: The paper does not include any experiments.
Guidelines:
49

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train /test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, boolstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96%
CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and found that the research in this paper conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the spocial circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., ., if there is a special consideration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
50

---

Answer: [NA]
Justification:
It is a theory paper, and we forsee no such impact.
Guidelines:
The answer NA means that there is no socictal impact of the work performed. If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance, fairness consid- erations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational rescarch and not tied to particular applications, let alone deployments. However, if there direct path to any negative applications ions, the authors should point it out. For example, it is legilimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MT.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This is a theory paper, and it poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implemeenting safely filters.
Datascts that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
51

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data, from a particular souree (c.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswil thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:[NA)
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code model as part of their submissions via structured templates. This includes details about Iraining, license, limitations, elc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer:
[NA]
Justification: The paper does not involve crowdsourcing nor rescarch with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (TRB) approvals (or an equivalent approval/reviev based on the requirements of your country institution) were obtained?
Answer: [NA]
52

---

Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between insti- tutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration LLM usage
Does the paper describe the usage of LLMs if it is an important, original, non-standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration not required.
Question:
Answer: [NA]
Justification:
The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this rescarch does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy (https: http://errrissscc/ooffeeeeeeeeee for what should or should not be described.
53


Reviews:
[{"review_id": "qMSiILFlmj", "reviewer": "Reviewer_yr9M", "summary": "The paper considers the question of traceability in stochastic convex optimization with respect to the $L_p$-norm. The setting involves assuming the existence of a parameter space $\\Theta$ that is convex and has bounded $L_p$-diameter, and a data space $\\mathcal{Z}$. Given samples from an unknown distribution $\\mathcal{D}$ over $\\mathcal{Z}$, the goal is to identify a $\\widehat{\\theta} \\in \\Theta$ that approximately minimizes $\\underset{Z \\sim \\mathcal{D}}{\\mathbb{E}}[f(\\theta, Z)]$, where $f \\colon \\Theta \\times \\mathcal{Z} \\to \\mathbb{R}$ is a function such that $f(\\cdot, z)$ is convex and $L_p$-Lipschitz for all $z \\in \\mathcal{Z}$. The problem of traceability has to do with the extent to which algorithms that solve the above problem have to memorize input datapoints, which would result in tracing algorithms being able to recover a significant part of the dataset with good probability. It is known that differentially private algorithms can be used to address the previous concern. However, the extent to which tracing is possible is not fully understood when one uses a non-private algorithm with error rate lower than that of the best private algorithm.\nThe present paper contributes to the understanding of the above question, by showing that, if one considers learners with error slightly lower than the minimax DP rate (for $\\varepsilon = \\Theta(1)$), then it becomes possible to trace a constant fraction of the input dataset, that is, the number of traceable samples is of the same order of magnitude as the input dataset. Three different results are given, corresponding to different ranges for $p$ ($p = 1, p \\in (1, 2]$, and $p > 2$). The results require proving new ``sparse'' fingerprinting-type lemmas (i.e., lemmas for distributions supported over vectors with a small number of non-zero components). As a by-product, a new lower bound for DP-SCO for $p > 2$ is obtained, as well as an improved traceability result for mean estimation in $L_{\\infty}$-norm.", "questions": "I don't really have any questions for the time being, but I can't rule out questions arising based on other reviewers' comments during the discussion period.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The questions of memorization and traceability are of significant importance to the machine learning literature, and so is the problem of SCO. Additionally, the main result about constant fraction traceability being achievable when one has error slightly below the DP minimax risk is conceptually interesting. Thus, the results are definitely of interest to the community of NeurIPS.\n2) In the past, fingerprinting arguments have focused on algorithms for parameter estimation problems attaining small mean-squared error. However, due to the different focus in this work, it is necessary to consider distributions parameterized by points in the largest $L_{\\infty}$-ball that can be inscribed into the $L_p$-unit ball. The constructions considered for the distributions supported on sparse vectors (and the proofs of the associated fingerprinting lemmas for the subgaussian trace value) exhibit a degree of insight and technical novelty which I definitely consider to be enough for the paper to be accepted.\n3) The presentation and writing were accessible.\n\nWeaknesses:\n1) The authors mention that they found ``the ability of trace value to recover non-private lower bounds surprising''. I don't think this is really surprising, and I can explain why. The lower bounds obtained using the trace value rely on fingerprinting. Fingerprinting requires one to reason about the correlation between the input dataset and the output distribution of an algorithm. Within the context of the DP literature, the correlation terms are upper-bounded using the definition of DP. However, it is always possible to upper-bound these terms using the Cauchy-Schwarz inequality (or Holder's inequality), which would lead to non-private lower bounds (not sure if this is explicitly written somewhere). Thus, given the lower bounds reliance on fingerprinting-type lemmas, it doesn't seem entirely unexpected that trace value-based arguments can recover non-private lower bounds. That said, this is not a serious criticism by any means, since it's clear from the proofs in the appendix that implementing this in the present setting is not as simple as suggested above, but requires a non-trivial amount of work.\n\nOverall, I consider this to be a good work that merits acceptance.", "was_revised": true, "final_justification": "My view of the paper was positive from the beginning, and still is, after the rebuttal.", "rebuttal": "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.  \n\nThe 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."}, {"review_id": "HZZAqBkj3O", "reviewer": "Reviewer_Cpj5", "summary": "This paper considers an interesting framework on finding the fundamental tradeoff between the learnability of model parameters and the traceability of the dataset. The authors focused on a general class of loss functions that are characterized by $\\ell_p$ conditions and showed that when the excess error belongs to certain intervals, it is guaranteed that a certain fraction of the training dataset can be recovered from the learned parameters.", "questions": "1. The authors are recommended to check or refer to rigorous proofs for the optimal sample complexity rates for p=1. If we follow the definition 2.2, then a valid cost function would be $f(z,\\theta)=\\frac{1}{2}||z-\\theta||_1$, where z is chosen to be uniformly random on the standard hypercube. In this case the sample complexity of the mean estimator would result in an error that scales linearly w.r.t. d instead of log d reported in table 1.  \n\n2 The authors frame the problem as SCO, which often instead describe a framework where the data points are obtained iteratively. The authors are recommended to refer the formulation with an appropriate terminology.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:  \nThe problem considered in this work is well-motivated and built on sound principles from PAC. If the proposed results are valid, they would address timely and relevant challenges on how to maintain data security guarantees throughout the learning process.\n\nWeakness: \nThe critical concern of this work is about the validity (or specifically, inapplicability) of the main theorems. For instance, 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. However, it appears that this entire regime could not be met at all except for a few corner cases, since the reviewer suspect the minimum sample complexity in the authors' formulation for p=1 is $d/\\alpha^2$ instead of $log(d)/\\alpha^2$, which is larger than the upper bound in Thm 1 and 2, rendering the claimed safety guarantee vacuous (see the question section for details). This issue is rooted from the fact that the benchmark learning error the authors used for the optimal sample complexity for small p is is fact the complexity for the $p=\\infty$ case ($log(d)/\\alpha^2$ as mentioned on page 2) instead of the correct rate for p=1.", "was_revised": true, "final_justification": "The main potential issue of this manuscript was resolved during the discussion period, as explained in my response, and I have raised my score.", "rebuttal": "Thank you for your review. \n\n > **W1 & Q1: Validity of Our Results, Sample Complexity for $p=1$, and the Reviewer's Example**. \n\n\nWe 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.\n\nThe **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$.\n\nIt 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.  \n\nAs 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.  \n\n>**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.**\n\nWe 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. \n\n > **Q2 Terminology for SCO**. \n\nWe 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}$. \n\n\n\n\n> **References**\n\n[SS’12] Shai Shalev Shwartz, Online Learning and Online Convex Optimization\n\n[AFKT21] Asi, H., Feldman, V., Koren, T.,  Talwar, K. Private stochastic convex optimization: Optimal rates in l1 geometry. ICML 2021.\n\n[BGN21] Bassily, R., Guzmán, C.,  Nandi, A. (2021, July). Non-euclidean differentially private stochastic convex optimization. COLT 2021.\n\n[GLLST23] Gopi, S., Lee, Y.T., Liu, D., Shen, R. and Tian, K., Private convex optimization in general norms. SODA 2023\n\n[SSSS09] Shalev-Shwartz, S., Shamir, O., Srebro, N.,  Sridharan, K. Stochastic Convex Optimization, COLT 2009"}, {"review_id": "R9HDyVkJUN", "reviewer": "Reviewer_n2Y2", "summary": "This paper studies the problem of traceability in stochastic convex optimization under $l_p$ geometries. Intuitively, traceability measures how the excess risk threshold determines the fraction of training samples that can be identified by an adversary. The traceability of an algorithm depends critically on the value of $p$, which defines the $l_p$ diameter of the feasible region.\n\n- More specifically, for $p \\in [1, \\infty)$, this paper establishes that there exists a risk threshold such that any algorithm achieving excess risk below this level must effectively memorize a constant fraction of its training data.\n\n- In addition, the paper investigates how this excess risk threshold relates to the number of training samples that can be traced, as a function of the best achievable excess risk of differentially private (DP) algorithms in comparable settings.\n\n- The paper also develops a sparse fingerprinting lemma, showing that over sparse domains, the correlation between a learner’s output and its training samples is inversely proportional to the sparsity parameter.", "questions": "How do you assess the significance of your results compared to existing work, and why?", "limitations": "In the checklist, the authors claim that they have discussed this in the related work section, but it is unclear to the reviewer what the limitations actually are.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n- This is an important problem, as it relates to whether the learner is simply memorizing the training data or learning the underlying structure from the samples.\n- This paper presents many results, and the proofs are very thorough.\n- The introduction of this paper is well written and presents the main results clearly.\n\nWeakness: \n- There is no contribution section, but for a theory paper, this is acceptable. \n- There are too many notations in this paper, and some of them are used inconsistently, which makes it very difficult for readers who want to fully understand the technical contributions. For example, the definition of $A_n$ in line 125 does not align with the one given in Equation (2).\n\nOther Comments:\n- It might be helpful to add columns in Table 1 for comparison with existing results.", "was_revised": true, "final_justification": "I have reviewed the authors’ response and find that the technical contributions, as presented, are solid. I am currently raising my score to a borderline accept. If any correctness issues are identified during further discussion, I will consider lowering my score accordingly. Overall, I believe the main shortcomings of the paper lie in its presentation, while the technical content appears to be quite strong ( assuming they are correct).", "rebuttal": "We thank the reviewer for their review. \n\n\n\n\n> **Q1: Significance of our results**\n\n\n Our work has 1) conceptual significance, 2) improved traceability results compared to state-of-the art, and 3) new proof techniques.\n\n\nOur 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.\n\n\nCompared 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].\n\n\nBeyond 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.\n\n> **W1: The contribution section is missing**\n\nOur paper has a contributions section on Page 2.\n\n\n> **W2: Notations and Table for Comparison**\n\nWe thank the reviewer for catching the inconsistency regarding $\\mathcal{A}_n$. We will fix this in the updated version of the paper! \nWe 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).\n\n\n\n\n> **Limitations** \n\nWe 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.\n\n> **References**\n\n[DSSUV15] Dwork, C., Smith, A., Steinke, T., Ullman, J., & Vadhan, S. Robust traceability from trace amounts. FOCS 2015.\n\n\n\n[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.\n\n[BGN21] Bassily, R., Guzmán, C., Nandi, A. (2021, July). Non-euclidean differentially private stochastic convex optimization. COLT 2021.\n\n[ABGMU22] Arora, R., Bassily, R., Guzmán, C., Menart, M. and Ullah, E. Differentially private generalized linear models revisited. NeurIPS 2022.\n\n[GLLST23] Gopi, S., Lee, Y.T., Liu, D., Shen, R. and Tian, K., Private convex optimization in general norms. SODA 2023\n\n[LLL24] Lee YT, Liu D, Lu Z. The power of sampling: Dimension-free risk bounds in private ERM. arXiv preprint 2024."}, {"review_id": "PdeVlProVJ", "reviewer": "Reviewer_HmKf", "summary": "This paper investigates the complexity and tractability of $\\ell_p$-approximation problems in the context of information-based complexity. Specifically, it addresses traceability in the setting of deterministic linear approximation schemes for compact linear operators between Banach spaces, focusing on the minimal worst-case error achievable by algorithms using $n$ pieces of information. The core of the paper lies in characterizing traceability via the asymptotic behavior of approximation numbers $a_n(T)$, with particular attention paid to the cases $1 \\leq p < \\infty$.\n\nThe authors introduce and analyze a notion of $(\\xi, m)$-weak tractability in the $\\ell_p$-approximation context and relate it to polynomial and quasi-polynomial tractability. They extend existing results from the Hilbert space setting to more general Banach spaces, yielding both necessary and sufficient conditions for various types of tractability.", "questions": "I'm not an expert in this area and do not have any technical questions.", "limitations": "No experiments involved.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n\nThe paper demonstrates a strong command of empirical process, approximation theory, and the machinery of information-based complexity. The results are technically non-trivial and reflect a significant extension of previous work. The main contribution are as follows:\n\n* For $1 < p \\le 2$: any learner that achieves excess-risk $\\alpha$ below the best differentially-private risk $\\alpha_{\\mathrm{DP}}$ must leak at least $\\Omega(1/\\alpha^{2})$ training samples.  \n* For $p=1$ the bound sharpens to $\\Omega\\!\\bigl(\\log d \\,/\\,\\alpha^{2}\\bigr)$, closing the $\\log d$ gap left by Dwork et al.\\ (2015).\n* For $p>2$: the lower bound becomes $\\Omega(1/\\alpha^{p})$, matching sample-complexity in the over-parameterised regime $d\\gtrsim n$.\n* Introduces a **sparse fingerprinting lemma** that extends classical hyper-cube fingerprinting to sparse inputs and drives the new bounds.\n* Defines a **sub-Gaussian trace value** that unifies (i) traceability lower bounds, (ii) DP lower bounds, and (iii) non-private sample-complexity bounds.\n* Improves the best known high-dimensional DP lower bounds for $\\ell_p$-SCO with $p>2$.\n\n### Weaknesses\n* Exposition is dense; more intuition and concrete examples would help non-experts.\n* Many constants and logarithmic factors are hidden—explicit rates would clarify sharpness.", "was_revised": true, "final_justification": "The authors have provided detailed explanations that fully address my initial concerns. Overall, this is a solid piece of work with strong theoretical results. However, as I am not an expert in the traceability problem, I cannot confidently assess the correctness of the proofs. I therefore maintain my rating of borderline accept.", "rebuttal": "We thank the reviewer for their review. We respond to the main points below. \n\n> **W1: The exposition is dense and intuition is missing** \n\nThanks 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. \n \n> **Q1 Many constants and logarithmic factors…** \n\nIn 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].\n\n\n\n\n> **Limitation: Experiments**\n \nEven 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. \n\n> **References**\n\n[Ver18] Vershynin, R. “High-dimensional probability: An introduction with applications in data science”  Cambridge university press.\n\n[SSSS17] Shokri, R., Stronati, M., Song, C., Shmatikov, V. “Membership inference attacks against machine learning models.” 2017 SP.\n\n[Car+22] Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., & Tramer, F . “Membership inference attacks from first principles.” In 2022 SP"}]

Author rebuttal:

Meta-review: This paper is concerned with the traceability of stochastic convex optimization algorithms: an algorithm is traceable if its inputs are identifiable from its output. The main result of this paper is a sharp transition in the tradeoff between traceability and excess risk of the optimizer output, occurring around the excess risk of differentially-private optimizers, for optimization in $\ell_p$ geometry where $p \in [1,2]$. Other results are shown for $p > 2$.

Reviewers and I agree that the result is significant and relevant to the wider community. The conceptual message is interesting, that the threshold does occur around the limits of what differentially-private algorithms can achieve. While the initial reviews contained a claim of a counterexample central to the narrative of the paper, the claim is now resolved after reviewer discussions and no correctness concerns remain. I am happy to recommend this paper for acceptance; it is a solid contribution to NeurIPS.
Decision: Accept (spotlight)