Provable Privacy Attacks on Trained Shallow Neural Networks

## Abstract

Abstract We study what provable privacy attacks can be shown on trained, 2-layer ReLU neural networks. We explore two types of attacks; data reconstruction attacks, and membership inference attacks. We prove that theoretical results on the implicit bias of 2-layer neural networks can be used to provably reconstruct a set of which at least a constant fraction are training points in a univariate setting, and can also be used to identify with high probability whether a given point was used in the training set in a high dimensional setting. To the best of our knowledge, our work is the first to show provable vulnerabilities in this setting.

## 1 Introduction

Recently, it was shown that theoretical tools used to study neural networks can be leveraged to reconstruct certain portions of the dataset on which the neural network was trained []. The idea behind these attacks is that under some conditions, trained neural networks must satisfy certain properties that are a consequence of the implicit bias of the training algorithm, which can be used to extract information on the training set.
This was followed by many other works that applied the same techniques in a broader setting [, , , , ], raising this vulnerability as a potential practical concern for the widespread use of neural networks. However, despite the fact that these works were motivated by theory, none of them give an explanation for why such a reconstruction is possible, since there can be potentially many different sets that possess these properties, including some that are significantly different than the actual data the neural network was trained on.

In this paper, we take what is to the best of our knowledge the first step in developing a better theoretical understanding of this phenomenon, by showing that such attacks can be provably executed on trained neural networks under various assumptions. This indicates that such attacks are successful since *all* datasets that satisfy these properties must store at least some information on the training data, which can be used by a malicious attacker. More specifically, we use known results on the implicit bias of ReLU neural networks, which establish that such networks tend to converge to a certain margin maximization solution [, ]. This characterization of the implicit bias of neural networks allows us to rigorously analyze certain cases in which the neural network memorizes the training data. In particular, this includes examples where an attacker is capable of reconstructing certain portions of the data in a univariate setting, or perform membership inference attacks with high success rates in a high dimensional setting, effectively distinguishing between instances that are in the training set and fresh instances that were generated by the same distribution that was used to generate the training set.

While our attacks are applicable in certain settings under various assumptions, we also conduct experiments that show that these vulnerabilities can be a concern in more generality, even if some of our assumptions are not met. Nevertheless, it is currently not clear what is the extent of the vulnerabilities that we reveal, and to what extent they can be circumvented. We leave the intriguing question of how to provably defend against such exploits to future work, and we hope that our work will pave the way for and motivate additional rigorous study of privacy attacks and defenses in trained neural networks.

The remainder of the paper is structured as follows: After specifying our contributions in more detail below, we turn to discuss related work. In Section 2 we present our notations, some required background, and the main assumptions we make throughout the paper. In Section 3 we study data reconstruction in the univariate setting, and in Section 4 we study membership inference attacks in high dimensions. Lastly, in Section 5, we conduct experiments to empirically support our findings, even in cases where our assumptions do not necessarily hold.

### Our contributions

Our main contribution is to provide rigorous guarantees in this setting, since to the best of our knowledge, all previous works are empirical. In more detail, our contributions can be summarized as follows:

- •
We prove that in the univariate case, under Assumption 2.1, which states that the weights of a trained neural network reach a stationary point of a maximum-margin problem that can be expressed as a function of the training data, an attacker can reconstruct a portion of the training data with a constant probability, which is independent of the training set and the size of the network.
We show how to extract that portion of the training data in Algorithm 1.
- •
We prove that in the high dimensional case, under Assumption 4.1, i.e. that the vectors in the training data
are nearly orthogonal
w.h.p., an attacker can execute a membership inference attack with high success rates. We show that some commonly used continuous distributions satisfy Assumption 4.1, and we also provide in Subsection 4.1 examples of different attacks that can be performed depending on the information available to the attacker.
- •
We empirically show that the membership inference attack we analyze in Section 4 may still be executed successfully when we slightly relax Assumption 4.1. This suggests that the vulnerabilities we study in this paper are potentially even more widespread than what our theory establishes.

### Related Work

Privacy attacks in neural networks were studied extensively in recent years. Since this paper focuses on two specific types of attacks, we only review here papers that also study these kinds of attacks, or those that closely relate to it.

##### Data reconstruction attacks.

Data reconstruction attacks aim to fully recover the training set or parts of it. These include attacks on generative models such as large language models
[, , ], diffusion models [, ], and in federated learning settings [, , , , , ]. Perhaps the most relevant works that are concerned with reconstruction attacks are Haim et al. [] and Buzaglo et al. []. Using a known result on the implicit bias of trained neural networks, they define and optimize over a loss function, which upon empirical minimization, allows for the recovery of some of the training set. Inspired by these works, we use the same constraints implied by the implicit bias to study this problem, but to rigorously *prove* the existence of privacy vulnerabilities rather than empirically demonstrate them.

##### Membership inference attacks.

The second type of attacks we consider in this paper are membership inference attacks [, , , ], which discern the inclusion or exclusion of a particular data point within the training set. This attack exploits the observation that machine learning models often behave differently on the data that they were trained on versus
fresh test examples.
One such difference is that
trained models tend to output more confident predictions on training examples compared to test examples.
This difference can be used to determine if a certain point was in the training set or not. Olatunji et al. [] used this confidence-based technique on graph neural networks. Jha et al. [], Farokhi and Kaafar [] use tools from information theory to upper bound the probability of success of a membership inference attack on neural networks, which is in contrast to our result which exemplifies settings with provable lower bounds on the success rates. Attias et al. [] also show provable membership inference attacks, but for models whose objective function is a convex function.

##### Differential privacy.

A fundamental theoretical framework in the study of privacy is differential privacy [, , , ], which is intuitively used to guarantee that sharing some information on a given dataset is done without leaking too much information on specific instances. This framework constitutes a rather strong standard for privacy guarantees, whereas we consider a setting where our assumptions on the implicit bias of neural networks are typically not differentially private. Namely, we study a setting where our base assumption is that there is already some data leakage in terms of differential privacy, and our work explores what is the extent of the information that can be extracted. Thus, our results are not directly comparable to those which study differential privacy.

##### Benign overfitting.

Another well-studied phenomenon in the theory of deep learning, which may explain the prevalence of privacy vulnerabilities, is benign overfitting [, , ]. This is when a neural network overfits on the training set, essentially achieving perfect training error, but still enjoys very good generalization on previously unseen instances. This suggests that even well-performing neural networks can memorize their training sets, and therefore become more prone to privacy attacks. While this provides a potential theoretical explanation for this phenomenon, as does our work, it does not immediately imply a method for extracting any information on the training set, nor does it prove the existence of such a method.

## 2 Background, preliminaries and notation

In this section, we introduce the notations and settings used throughout this paper, and
discuss relevant background.

We consider a binary classification setting, where each data instance consists of a pair $(\mathbf{x},y)\in\mathbb{R}^{d}\times\{-1,1\}$, and we define the training set as $\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$
which consists of $n$ data points. We let $\Phi(\boldsymbol{\theta};\cdot):\mathbb{R}^{d}\rightarrow\mathbb{R}$ denote a neural network, where $\boldsymbol{\theta}\in\mathbb{R}^{k}$ are the parameters of the network represented as a vector.
Let $\ell:\mathbb{R}\rightarrow\mathbb{R}$ denote the exponential loss function $z\mapsto e^{-z}$ or the logistic loss function $z\mapsto\log(1+e^{-z})$, and let $L(\boldsymbol{\theta})\coloneqq\frac{1}{n}\sum_{i=1}^{n}\ell(y_{i}\cdot\Phi(
\boldsymbol{\theta};\mathbf{x}_{i}))$ be the empirical (training) loss.
A network $\Phi(\boldsymbol{\theta};\mathbf{x})$ is called *homogeneous* if there exists $c>0$ such that for every $b>0$, $\boldsymbol{\theta}$ and $\mathbf{x}$, it holds that $\Phi(b\cdot\boldsymbol{\theta};\mathbf{x})=b^{c}\Phi(\boldsymbol{\theta};
\mathbf{x})$.
The ReLU activation function is $\left[x\right]_{+}\coloneqq\max(0,x)$, and a homogeneous 2-layer ReLU network has the form
$\Phi(\boldsymbol{\theta},\mathbf{x})=\sum_{j=1}^{k}v_{j}\left[\mathbf{w}_{j}^{
\top}\mathbf{x}+b_{j}\right]_{+}$ where $\boldsymbol{\theta}$ encapsulates the parameters $\{\mathbf{w}_{j},v_{j},b_{j}\}_{j=1}^{k}$. We denote the ($d-1$)-dimensional unit sphere in $\mathbb{R}^{d}$ by $\mathbb{S}^{d-1}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}:\|\mathbf{x}\|_{2}=1\}$ . We use standard asymptotic notation (e.g. $O,o,\Omega$, etc.).

The following theorem is a well-known result in the literature, for which we give a paraphrased version for the sake of completeness.

###### Theorem 2.1 ( Lyu and Li [ 28 ] , Ji and Telgarsky [ 25 ] ) .

Let $\Phi(\boldsymbol{\theta};x)$ be a homogeneous ReLU neural network.
Consider minimizing the logistic ($z\mapsto\log(1+e^{-z})$) or exponential ($z\mapsto e^{-z}$) loss using gradient flow (which is a continuous time analog of gradient descent) over a binary classification set $\{(x_{i},y_{i})\}_{i=1}^{n}\subseteq\mathbb{R}^{d}\times\{-1,1\}$. Assume that there is a time $t_{0}$ where $L(\boldsymbol{\theta}(t_{0}))<\frac{1}{n}$. Then, gradient flow converges in direction(^1^11We say that gradient flow *converges in direction* to $\hat{\boldsymbol{\theta}}$ if $\lim_{t\rightarrow\infty}\frac{\boldsymbol{\theta}(t)}{\|\boldsymbol{\theta}(t )\|}=\frac{\hat{\boldsymbol{\theta}}}{\|\hat{\boldsymbol{\theta}}\|}$.) to a first order stationary point (KKT point) of the following maximum-margin problem:

$$ $\min_{\boldsymbol{\theta}}\frac{1}{2}\|\boldsymbol{\theta}\|^{2}~{}~{}\text{s. t}~{}~{}\forall i\in[n]~{}~{}y_{i}\Phi(\boldsymbol{\theta};x_{i})\geq 1.$ (1) $$

In light of the above result, it is natural to assume that our network has converged to a KKT point of the above maximum-margin problem. This implies a series of constraints on its weights, that are captured in the following assumption we make throughout the paper:

###### Assumption 2.1 .

Let $\Phi(\boldsymbol{\theta};\mathbf{x})$ be a 2-layer neural network, and let $m\coloneqq\min_{i}\left|\Phi(\boldsymbol{\theta};\mathbf{x}_{i})\right|$.
We are given access to $\Phi(\boldsymbol{\theta},\cdot)$, and we have full knowledge of the vector $\boldsymbol{\theta}$.(^2^22Many of our results or similar ones can be proven even with only partial access to the network’s weights, however for the sake of simplicity we assume full knowledge of the weights.) Moreover, we have that $\boldsymbol{\theta}$ satisfies the following KKT conditions of Eq. (1):

$$ $\displaystyle\boldsymbol{\theta}=\sum_{i=1}^{n}\lambda_{i}y_{i}\nabla_{ \boldsymbol{\theta}}\Phi(\boldsymbol{\theta};\mathbf{x}_{i}),$ (2) $\displaystyle\forall i\in[n],~{}~{}~{}y_{i}\Phi(\boldsymbol{\theta};\mathbf{x} _{i})\geq m,$ (3) $\displaystyle\lambda_{1},\dots,\lambda_{n}\geq 0,$ (4) $\displaystyle\forall i\in[n],~{}~{}\text{ if }~{}y_{i}\Phi(\boldsymbol{\theta} ;\mathbf{x}_{i})\neq m~{}\text{ then }\lambda_{i}=0.$ (5) $$

We refer to the parameter $m$ as *the margin’s value*, and we say that a set of points $A\subseteq\mathbb{R}^{d}$ *lies on the margin* if $\Phi(\boldsymbol{\theta};\mathbf{x})$ equals the margin’s value for all $\mathbf{x}\in A$. We stress that in general, the attacker does not have knowledge of the value of $m$. Nevertheless, it is still possible that the attacker might be able to either deduce this value or obtain it in some way, and even if they cannot, this merely results in a single additional hyperparameter that the attacker must accommodate for, which indicates that our proposed attacks can reveal unwanted information. Throughout this paper, we present various results which vary based on the information that we have on $m$.

###### Theorem 2.1 ( Lyu and Li [ 28 ] , Ji and Telgarsky [ 25 ] ) .

###### Assumption 2.1 .

## 3 One dimensional input

In this section, we consider univariate neural networks with ReLU activations. Such a network takes the form

$$ $x\mapsto\sum_{j=1}^{k}v_{j}\left[w_{j}x+b_{j}\right]_{+},$ (6) $$

where $x\in\mathbb{R}$. Note that this computes a piece-wise linear function (in $x$), and its breakpoints (i.e. points where the function changes its linearity) are $\{-\frac{b_{j}}{w_{j}}\}_{j=1}^{k}$. We assume w.l.o.g. $-\frac{b_{1}}{w_{1}}<\ldots<-\frac{b_{k}}{w_{k}}$.

Throughout this section, we assume that the attacker has knowledge of the value of the margin, and that this value is $1$ without loss of generality.

### 3.1 Warming up – the case n = k = 1 𝑛 𝑘 1 n=k=1 italic_n = italic_k = 1

It is easy to show that for the simple case of $n=k=1$ there is a single possible solution, and thus the attacker can always recover the dataset:

###### Theorem 3.1 .

Suppose that $\Phi(\boldsymbol{\theta};\cdot)$ is a univariate neural network as in Eq. (6), and that Assumption 2.1 holds. Moreover, suppose that $n=k=1$. Then, there exists a single solution $x$. Moreover, it can be easily recovered.

###### Proof.

Eq. (3) implies that $\Phi(\boldsymbol{\theta};x_{1})$ cannot be the zero function. By Eq. (5), $y_{1}\Phi(\boldsymbol{\theta};x_{1})\neq 1$ implies that Eq. (2) equals zero which thus leads to a contradiction, and therefore we deduce that $y_{1}\Phi(\boldsymbol{\theta};x_{1})=m=1$ which implies that $\Phi(\boldsymbol{\theta};x_{1})\in\{-1,1\}$. Since $n=k=1$, we have $\Phi(\boldsymbol{\theta};x_{1})=v_{1}\left[w_{1}x_{1}+b_{1}\right]_{+}$. This function equals 0 0 whenever the ReLU neuron is inactive and is necessarily not zero whenever the neuron is active, thus it has a non-zero slope, and it equals either $-1$ or $1$ at a unique point which is necessarily $x_{1}$.
∎

While the above example is highly degenerate, it nevertheless highlights the danger and exemplifies the impact this theoretical tool may have in practice, and further motivates us to explore whether such vulnerabilities exist in more general settings.

###### Theorem 3.1 .

###### Proof.

### 3.2 The general univariate case

As we will see in this subsection, fully recovering the dataset in the more general univariate case as in the previous case is much more complicated – if at all possible. Nevertheless, we will show that under our assumptions, there is still some information on the training set that can be extracted.

Our analysis in the previous simple example relied on the observation that following from the KKT conditions, points whose value lies on the margin are potential candidates for being training points. However, it is unclear whether this holds in general, and what exactly is the portion of the points whose value lies on the margin that are also training points. Moreover, in the univariate case which we consider now, the neural network can either cross the margin with a non-zero slope, or have a zero slope on an interval where it equals the margin. In the former case, we have at most two points per each interval on which the network takes a linear form and crosses the margin, thus at most two points are added to the set of potential candidates; but in the latter case, there is a continuum of potential candidate points. However, a more careful analysis reveals that in both cases, there is a finite set of candidates which must contain a training point.

The following theorems each addresses a different case from the cases described above, and establishes the existence of a discrete set of points that must contain a training point. All proofs can be found in Appendix A.

###### Theorem 3.2 .

Let $\Phi(\boldsymbol{\theta};x)$ be a 2-layer univariate network satisfying Assumption 2.1. Let $[-\frac{b_{i-1}}{w_{i-1}},-\frac{b_{i}}{w_{i}}]$ and $[-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}}]$ be two adjacent intervals which none of them is constant on the margin. Then, there must be a training point in the interval $[-\frac{b_{i-1}}{w_{i-1}},-\frac{b_{i+1}}{w_{i+1}}]$, and that training point must lie on the margin. In addition, the number of points lying on the margin in this interval is at most $4$.

Having presented our theorem for the case where the neural network is not constant on the margin, we now present our theorem for the complementary case where it is constant.

###### Theorem 3.3 .

Let $\Phi(\boldsymbol{\theta};x)$ be a 2-layer univariate network satisfying Assumption 2.1. In addition, assume the following:

- •
There is a neuron $c_{1}$ that is active on all the points in the training set.
- •
$\Phi(\boldsymbol{\theta};x)$ is a local minimum of Eq. (1).
- •
$\Phi(\boldsymbol{\theta};x)$ alternatingly lies on the margin on three adjacent intervals, i.e. it is constant on $[-\frac{b_{i-2}}{w_{i-2}},-\frac{b_{i-1}}{w_{i-1}}]$ and on $[-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}}]$ (but not in between) and lies on the margin, for some $i$.

Then, either $-\frac{b_{i-1}}{w_{i-1}}$ or $-\frac{b_{i}}{w_{i}}$ is a training point.

We note that in terms of the structure of the function $\Phi(\boldsymbol{\theta};\cdot)$, the above case analysis is exhaustive (excluding degenerate cases such as $\Phi(\boldsymbol{\theta};\cdot)$ which consists of at most two different intervals, on which it is linear). This holds true since if the conditions in Thm. 3.3 do not hold, then this implies that $\Phi(\boldsymbol{\theta};\cdot)$ does not lie on the margin in two adjacent intervals, hence the conditions for Thm. 3.2 must hold. We also remark that we have assumed that there is a neuron which is active on all the training data points, which typically makes sense in settings where the network is highly over-parameterized for example, but even if this assumption does not hold, then we can enforce it by modifying our architecture to have a linear neuron with no activation function in the first hidden layer.

The next result demonstrates how our previous two theorems can be leveraged to construct a set of which at least a quarter of the instances are training points.

###### Theorem 3.4 .

Let $\Phi:\mathbb{R}\rightarrow\mathbb{R}$ be a 2-layer homogeneous network satisfying Assumption 2.1. In addition, assume the following:

- •
There is a neuron $c_{1}$ that is active on all the points in the training set.
- •
$\Phi(\boldsymbol{\theta};x)$ is a local minimum of Eq. (1).

Then, the following algorithm builds a finite set of which a constant fraction $p\geq\frac{1}{4}$ of the points are training points.

Figure: Algorithm 1 Build a finite set of candidates

The above algorithm essentially iterates over the linear intervals of the network, and uses either Thm. 3.2 or Thm. 3.3 based on the structure of $\Phi(\boldsymbol{\theta};\cdot)$ to add a constant number of candidate points, until the final set of points is constructed. We point out that we have assumed that $\boldsymbol{\theta}$ is a local minimum of Eq. (1) rather than just a critical point. It is known that in general, not all critical points of Eq. (1) are also local minima, and that gradient flow may converge to a critical point which is not a local minimum (see Safran et al. [, Example 1]), but it is not clear what is the ‘typical’ behavior of gradient flow in this context. We also remark that despite our requirement to have full knowledge of $\boldsymbol{\theta}$, the above results can also be implemented with partial knowledge of $\boldsymbol{\theta}$.(^3^33For example, if we have access to $\Phi(\boldsymbol{\theta};\cdot)$ and only the breakpoints where the network changes its linearity are known, we can still interpolate and compute the points which cross the margin.) In any case, we leave the exploration of other privacy related questions on relaxations of our assumptions for future work.

###### Theorem 3.2 .

###### Theorem 3.3 .

###### Theorem 3.4 .

## 4 High dimensional input

Having discussed the one-dimensional setting, we now investigate the case $\mathbf{x}\in\mathbb{R}^{d}$ where $d$ is large. In this case, it is not obvious how to reconstruct the training data using an approach which is similar to the previous section: even if one can identify a $(d-1)$-dimensional manifold (which corresponds to domain points that lie on the margin) in which the data is contained, there is still a continuum of potential candidates. For this reason, we instead investigate a different variant of privacy vulnerability, called *membership inference* queries: Given a point $\mathbf{x}\in\mathbb{R}^{d}$ which is either a random point from the training set or a freshly sampled test point, sampled from the same distribution used to generate the training set – can the attacker tell how $\mathbf{x}$ was generated with high probability?

In very high dimensional settings, under many commonly used data distributions, we have that the dataset is almost orthogonal with high probability. We exploit this property to show that also with high probability over drawing the training set, all the points in the training set will lie on the margin. On the other hand, if we draw a new data point from the same distribution, the neural network will output a target value which is typically much smaller than the margin. These key observations will allow us to make the distinction between training points and test points, effectively answering membership inference queries.

###### Remark 4.1 (Black box attacks) .

We note that since our results in this section are only based on querying the value of $\Phi(\boldsymbol{\theta};\cdot)$, the attacker need not know $\boldsymbol{\theta}$ to successfully execute the membership inference attack, and therefore the attack can also be applied in the black box model.

We now formally state our assumptions on the underlying distribution $\mathcal{D}$ which generates the dataset:

###### Assumption 4.1 .

The following hold for some $\tau>0$.

- 1.
For $\mathbf{x}_{1},\mathbf{x}_{2}\sim\mathcal{D},~{}~{}\Pr[n\cdot|\mathbf{x}_{1}^{
\top}\mathbf{x}_{2}|\leq o(d)]\geq 1-\frac{\tau}{n^{2}}$.
- 2.
For $\mathbf{x}\sim\mathcal{D},~{}~{}p\left[\|\mathbf{x}\|^{2}\geq\Omega(d)\right]
\geq 1-\frac{\tau}{n}$.

where $n$ is the size of the training set.

Note that we do not make any assumptions on the labels of the data, and therefore our results hold for all possible labellings on the data. We also point out that even though this assumption may seem somewhat restrictive at a first glance, it can be expected to hold for continuous distributions in sufficiently large dimensions, and when the sample size is modest. We also prove that our assumption is satisfied by several rather standard data distributions. This includes (but is not limited to) the following concrete examples:

- 1.
The uniform distribution over the sphere $\sqrt{d}\cdot\mathbb{S}^{d-1}$, where $n=o\left(\frac{\sqrt{d}}{\log{d}}\right)$ and $\tau=o_{d}(1)$.
- 2.
The normal distribution $\mathcal{N}(\boldsymbol{\mu},I)$ with mean $\boldsymbol{\mu}$, where $\|\boldsymbol{\mu}\|^{2}=o(d)$, and where $n=\frac{o(d)}{\|\boldsymbol{\mu}\|^{2}+d^{\epsilon}}$ for some $\frac{1}{2}~{}<~{}\epsilon~{}<~{}1$ and $\tau=o_{d}(1)$.
- 3.
Mixture of $k$ Gaussians with means $\boldsymbol{\mu}^{(1)},\dots,\boldsymbol{\mu}^{(k)}$, where $\|\boldsymbol{\mu}^{(1)}\|^{2},\dots,\|\boldsymbol{\mu}^{(k)}\|^{2}=o(d)$ and identity covariance matrices, and $n=\frac{o(d)}{\max\left\{\|\boldsymbol{\mu}^{(i)}\|^{2}\right\}_{i=1}^{k}+d^{
\epsilon}}$ for some $\frac{1}{2}~{}<~{}\epsilon~{}<~{}1$, and $\tau=o_{d}(1)$.

The first two examples are rather standard in the literature, whereas the last example is somewhat more complex, but is meant to exemplify a setting where our proposed attacks can be executed in the statistically learnable case (see Frei et al. [] for the sample complexity analysis of this example).
For proofs that these distributions satisfy Assumption 4.1, we refer the reader to Appendix C.

Before we continue, we will introduce some further notation to be used throughout this section. Recall that $m>0$ denotes the value of the network’s margin, and define $\delta\coloneqq\max_{i\neq j}\left\{|\mathbf{x}_{i}^{\top}\mathbf{x}_{j}|\right\}$ and $\Delta\coloneqq\min_{i\in[n]}\left\{\|x_{i}\|^{2}\right\}$. Note that by Assumption 4.1 and by the union bound, we have that $n\cdot\delta=o(\Delta)$ with probability at least $1-2\tau$.

Given a point $\mathbf{x}\in\mathbb{R}^{d}$, we would like to know whether $\mathbf{x}$ was in the training set, or if it was generated from the same distribution that generated the training set. As previously discussed, our strategy is to calculate the value of $|\Phi(\boldsymbol{\theta};\mathbf{x})|$. We expect to see larger values that are closer to the margin when $\mathbf{x}$ is in the training set, and smaller values when it is not. Formalizing this idea, the following theorem is used to determine w.h.p. whether a given point $\mathbf{x}\in\mathbb{R}^{d}$ is in fact a training point, or a test point which was freshly sampled from $\mathcal{D}$.

###### Theorem 4.2 .

Let $n\geq 3$. Let $\mathcal{D}$ be a distribution on $\mathbb{R}^{d}$ that satisfies Assumption 4.1. Let $\mathbf{x}\in\mathbb{R}^{d}$ and let $\Phi(\boldsymbol{\theta};\cdot)$ be a 2-layer neural network satisfying Assumption 2.1. Then the following hold:

- •
With probability at least $1-2\tau$ over the choice of the training set, if $\mathbf{x}$ is a training point then $|\Phi(\boldsymbol{\theta};\mathbf{x})|=m$.
- •
If $\mathbf{x}\sim\mathcal{D}$ then with probability $1-2\tau$ over the sampling of $\mathbf{x}$ and the sampling of the training data, $|\Phi(\boldsymbol{\theta};\mathbf{x})|=O(\frac{n\cdot m\cdot\delta}{\Delta})=o
_{d}(m)$.

This theorem gives us a useful tool to perform membership inference attacks. Given a point $\mathbf{x}\in\mathbb{R}^{d}$, run $\mathbf{x}$ through the neural network, and consider the output $\Phi(\boldsymbol{\theta};\mathbf{x})$. If $|\Phi(\boldsymbol{\theta};\mathbf{x})|=m$, then $\mathbf{x}$ is in the training set, and if $|\Phi(\boldsymbol{\theta};\mathbf{x})|=o_{d}(m)$,
then $\mathbf{x}$ is not in the training set
(with high probability).

The intuition behind the proof of the theorem can be explained as follows: Using Assumption 2.1, we show that the value $|\Phi(\boldsymbol{\theta};\mathbf{x})|$ can be expressed as a weighted combination of $\{\mathbf{x}_{i}^{\top}\mathbf{x}\}_{i=1}^{n}$ (where $\{\mathbf{x}_{i}\}_{i=1}^{n}$ are the training points). Using Assumption 4.1, we know that if $\mathbf{x}$ is in the training set, then $\mathbf{x}=\mathbf{x}_{k}$ for some $k\in[n]$ and $\|\mathbf{x}_{k}\|^{2}$ must be large, while $\mathbf{x}_{j}^{\top}\mathbf{x}_{k}$ is small for all $j\neq k$, and therefore the weighted combination is large. On the other hand, when $\mathbf{x}\sim\mathcal{D}$, then with high probability it is “nearly orthogonal” to all training points, meaning that $\mathbf{x}_{j}^{\top}\mathbf{x}$ is small for all $j=1,\dots,n$, and thus the weighted combination is small. For the complete proof of the theorem, we refer the reader to Appendix B.

Having presented our main tool in this section, we now turn to discuss several particular use cases, based on the amount of knowledge known to the attacker. Similarly to the previous section, we first assume that the value of the margin is known to the attacker. However, since an attacker cannot deduce the value of the margin in general, we also provide examples where membership inference questions can be answered without this knowledge.

###### Remark 4.1 (Black box attacks) .

###### Assumption 4.1 .

###### Theorem 4.2 .

### 4.1 Example use cases of Thm. 4.2

In all of the following cases, let $\Phi(\boldsymbol{\theta};\mathbf{x})$ be a 2-layer neural network satisfying Assumption 2.1, and let $\mathcal{D}$ be a distribution that satisfies Assumption 4.1 for some $\tau>0$, so as to satisfy the assumptions in Thm. 4.2.

We begin with the simplest case, where the value of the margin is known to the attacker.

###### Corollary 4.3 (Known margin value) .

Let $\mathbf{x}\in\mathbb{R}^{d}$, assume that $d$ is sufficiently large, and further assume that we know the value of the margin $m$. Then, we have that:

- •
With probability at least $1-2\tau$ over the choice of the training set, if $\mathbf{x}$ is in the training set then $|\Phi(\boldsymbol{\theta};\mathbf{x})|=m$.
- •
If $\mathbf{x}\sim\mathcal{D}$ is a fresh example then, with probability at least $1-2\tau$ over the choice of the training set and over the randomness in sampling $\mathbf{x}$, $|\Phi(\boldsymbol{\theta};\mathbf{x})|<\frac{m}{2}$.

###### Proof.

From Thm. 4.2 we know that with probability at least $1-2\tau$ over the choice of the training set we have that if $\mathbf{x}$ is in the training set then $|\Phi(\boldsymbol{\theta};\mathbf{x})|=m$ and if $\mathbf{x}\sim\mathcal{D}$ then with probability at least $1-2\tau$

$$ $|\Phi(\boldsymbol{\theta};\mathbf{x})|\leq O\left(\frac{n\cdot m\cdot\delta}{ \Delta}\right)=m\cdot O\left(\frac{n\cdot\delta}{\Delta}\right)<\frac{m}{2},$ $$

where in the last inequality we used the fact that $O(\frac{n\cdot\delta}{\Delta})=o_{d}(1)$.
∎

Thus, by the above, if the margin’s value $m$ is known to the attacker, they can simply compute $|\Phi(\boldsymbol{\theta};\mathbf{x})|$ and return that $\mathbf{x}$ is in the training set if and only if $|\Phi(\boldsymbol{\theta};\mathbf{x})|\approx m$.

As previously discussed, in general, the value of the margin is not known to the attacker. Nevertheless, under different assumptions, the attacker can still execute a successful membership inference attack.

###### Corollary 4.4 (Leaked data point) .

Let $k$ be a constant (independent of $d$), let $\mathbf{z}_{1},\ldots,\mathbf{z}_{k}\sim\mathcal{D}$ be $k$ points, and assume we know that at least one point in this set is in the training set. Let $\alpha=\max_{1\leq i\leq k}\left\{|\Phi(\boldsymbol{\theta};\mathbf{z}_{i})|\right\}$, then, we have for all $i\in[k]$:

- •
If $\mathbf{z}_{i}$ is in the training set then with probability at least $1-2k\tau$ over the training set and over $\{\mathbf{z}_{j}\}_{j\neq i}$, $|\Phi(\boldsymbol{\theta};\mathbf{z}_{i})|=\alpha$.
- •
If $\mathbf{z}_{i}\sim\mathcal{D}$ then with probability at least $1-2k\tau$ over the training set and over $\mathbf{z}_{i}$, $|\Phi(\boldsymbol{\theta};\mathbf{z}_{i})|<\frac{\alpha}{2}$.

###### Proof.

W.l.o.g. let $\mathbf{z}_{1}$ be in the training set. Using Thm. 4.2 and the union bound over $\mathbf{z}_{1},\ldots,\mathbf{z}_{k}$, we have $\left|\Phi(\boldsymbol{\theta},\mathbf{z}_{i})\right|\leq m$ for all $i$ with probability at least $1-2k\tau$, so in particular $\alpha\leq m$.
On the other hand, using Thm. 4.2 again, we have that $\left|\Phi(\boldsymbol{\theta},\mathbf{z}_{1})\right|=m$ with probability at least $1-2\tau\geq 1-2k\tau$, so $m\leq\alpha$. So we have that with probability at least $1-2k\tau$, $m=\alpha$.
Now we complete the proof by using Corollary 4.3.
∎

The above corollary implies that even if the attacker has no knowledge of the value of the margin, but has knowledge that at least one element in a set of size $k$ is in the training set, then this value must achieve the maximal prediction value in absolute value among the set. This allows the attacker to deduce the margin value by computing $\max_{i}|\Phi(\boldsymbol{\theta};\mathbf{z}_{i})|$. Thereafter, the attacker can continue in the same manner as in Corollary 4.3.

One might argue that even the previous assumptions are somewhat restrictive, since they require that at least one training point is leaked a priori. The following corollary makes some additional assumptions on the underlying distribution and that the margin value is bounded rather than known, which is much milder than in the previous result.

###### Corollary 4.5 (Bounded margin) .

Let $\mathcal{D}$ be a distribution that satisfies the following slightly stronger version of Assumption 4.1:

Let $\tau>0$.

- •
For $\mathbf{x},~{}\mathbf{y}\sim\mathcal{D},~{}n\cdot|\mathbf{x}^{\top}\mathbf{y}|
=o\left(\frac{d}{t(d)}\right)$ for some function $t(d)$ with probability at least $1-\frac{\tau}{n^{2}}$.
- •
For $\mathbf{x}\sim\mathcal{D},~{}~{}\|\mathbf{x}\|^{2}=\Omega(d)$ with probability at least $1-\frac{\tau}{n}$.

Furthermore, let $\mathbf{x}\sim\mathcal{D}$ and suppose that $C<m<t(d)$ for some constant $C$. Then the following holds:

- •
With probability at least $1-2\tau$ over the training set, if $\mathbf{x}$ is in the training set then $|\Phi(\boldsymbol{\theta};\mathbf{x})|>C$.
- •
If $\mathbf{x}\sim\mathcal{D}$ then with probability at least $1-2\tau$ over the training set and $\mathbf{x},~{}|\Phi(\boldsymbol{\theta};\mathbf{x})|<o_{d}(1)$.

###### Proof.

Assume that $\mathbf{x}$ is in the training set. From Thm. 4.2 we know that $|\Phi(\boldsymbol{\theta};\mathbf{x})|=m>C$ with probability at least $1-\tau$. Assume that $\mathbf{x}$ is not in the training set. From Thm. 4.2 and our stronger assumption on $\mathcal{D}$ we know that

$$ $|\Phi(\boldsymbol{\theta};\mathbf{x})|=O\left(\frac{n\cdot\delta\cdot m}{ \Delta}\right)\leq O\left(o\left(\frac{d}{t(d)}\right)\cdot\frac{m}{\Delta} \right)=O\left(o\left(\frac{d}{t(d)}\right)\cdot\frac{m}{d}\right)=o_{d}(1).$ $$

with probability at least $1-2\tau$.
∎

This corollary implies the following: for $\mathbf{x}\in\mathbb{R}^{d}$, let us compute $|\Phi(\boldsymbol{\theta};\mathbf{x})|$. If $\mathbf{x}$ is not in the training set, then w.h.p. we get a number which is smaller than $C$, and if $\mathbf{x}$ is in the training set, w.h.p we get a number which is larger than $C$.

###### Remark 4.6 (On the lower and upper bounds of the margin) .

We argue that the lower and upper bound assumptions on the margin that we use above are mild. This follows from the fact that if we assume an exponential or logistic loss function (which is a standard assumption in this setting), then the gradient is exponentially small in the margin. Hence, if the margin is even just polylogarithmic in $d$, then making further progress with training is extremely inefficient.
Conversely, if the margin is too small, then this implies that the loss over points that lie on the margin is large,
which indicates that the network had stopped training very early. For more formal arguments justifying this assumption, we refer the reader to Remarks B.5 and B.6.

###### Corollary 4.3 (Known margin value) .

###### Proof.

###### Corollary 4.4 (Leaked data point) .

###### Proof.

###### Corollary 4.5 (Bounded margin) .

###### Proof.

###### Remark 4.6 (On the lower and upper bounds of the margin) .

## 5 An experiment for intermediate values of d 𝑑 d italic_d

Thus far, our theory addressed the one-dimensional case, as well as the high-dimensional case where the input’s dimension is much larger than the training set size. This naturally raises the question of what happens in between these two regimes.

Exploring this question empirically, in this section, we conducted a few experiments focusing on the membership inference problem, and observed that while our theoretical results’ assumptions do not necessarily hold, their implications are nevertheless still valid.
We sampled training and test sets (both i.i.d.) uniformly from the scaled hypersphere, trained a 2-layer neural network until reaching an approximate KKT point, and examined the network’s predictions on both the training and the test sets in comparison to the margin. Our code is available in following link: [https://github.com/guy120494/Provable-Privacy-Attacks-on-Trained-Shallow-Neural-Networks](https://github.com/guy120494/Provable-Privacy-Attacks-on-Trained-Shallow-Neural-Networks).

More specifically, we conducted all our simulations using the following settings:

- •
Architecture: We focused on 2-layer ReLU networks, where the hidden layer has 10,000 neurons. The neurons in the hidden layer each have a bias term while the second layer does not, thus making the network homogeneous.
- •
Range of the input dimension: We tested $d$ for various values in the range between 1 and 1000. This range includes values of $d$ where it is much larger than the training set as in our theoretical results, but also includes more moderate values of $d$ where our assumptions do not necessarily hold.
- •
Data generation: All points were sampled uniformly and i.i.d. from $\sqrt{d}\cdot\mathbb{S}^{d-1}$. The training set contains 20 instances, since this small size ensures that Assumption 4.1 holds for the larger values of $d$ that we tested. The test set contains 5,000 instances.
- •
Training: In order to converge faster to an approximate KKT point, we used a small initialization scheme as was done in Haim et al. [].

Our experiment focused on studying two objectives. The first studies how many training points lie on the margin as a function of the dimension $d$,(^4^44It is noteworthy that a similar experiment was conducted in Vardi et al. [], albeit under a different context where the adversarial robustness of the neural network is studied.) and the second studies how many test points that were sampled from the same distribution as the training set lie on or above the margin.

Our results reveal that the output of the network can be used as an inference tool for privacy attacks for a much wider spectrum of input dimensions, indicating that our theory is likely applicable in broader settings.
More specifically, Fig. 1(a) shows that as the input dimension increases, more training points lie on the margin, which suggests that the probability that a training point lies on the margin is increasing as a function of the input’s dimension.
Fig. 1(b) and Fig. 1(c) show that as the input dimension increases, the number of test points that lie on or above the margin decreases, which suggests that the probability that a point sampled from the same distribution as the training set lies on or above the margin is decreasing as a function of the input dimension. Note that this experiment not only verifies our theoretical findings, it also shows that our claims hold for much smaller values of $d$ than what our theory predicts. For example, with a training set of size $20$, Thm. 4.2 is expected to hold for dimensions of at least $d=n^{2}=20^{2}=400$,(^5^55This is because of the fact that under the assumption $n=\sqrt{d}$, we have w.h.p. that $n\cdot|\mathbf{x}_{1}^{\top}\mathbf{x}_{2}|=\Theta(d)$, so Assumption 4.1 is very unlikely to hold for values of $d$ that are smaller than that.) but our experiment reveals that virtually all test points lie below the margin for $d$ as small as $100$, and that even for $d=n=20$, approximately 80% of the test points lie below the margin, indicating that membership inference attacks already pose a problem for much more modest values of $d$.

Following our empirical findings, we conclude that our theory is expected to hold more generally, and that the magnitude of the output of the neural network on a data instance can provably reveal whether it is a training point or a test point with high success rates. This is in line with many empirical findings (see Hu et al. []), and provides a theoretical explanation for this phenomenon.

Figure: (a) The percentage of training points that lie on the margin (up to a slack of 10%) increases as the dimension increases.
Refer to caption: x1.png

### Acknowledgements

GV is supported by research grants from the Center for New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker – Weizmann Annual Grant.

## Appendix A Proofs from Subsection 3.2

We start by stating a few notations:
Denote by $\sigma^{\prime}_{j}$ the subgradient of $\left[\mathbf{w}_{j}^{\top}\mathbf{x}+b_{j}\right]_{+}$. If $\mathbf{w}_{j}^{\top}\mathbf{x}+b_{j}\neq 0$ then $\sigma^{\prime}_{j}$ is well defined, and if $\mathbf{w}_{j}^{\top}\mathbf{x}+b_{j}=0$ then $\sigma^{\prime}_{j}\in[0,1]$. In any case, $\sigma^{\prime}_{j}\geq 0$.
For a training point $\mathbf{x}_{i}$, denote by $\sigma^{\prime}_{i,j}$ the subgradient of $\left[\mathbf{w}_{j}^{\top}\mathbf{x}_{i}+b_{j}\right]_{+}$.

For all $j\in[k]$ that the partial derivatives of our 2-layer homogeneous neural network are given by

$$ $\displaystyle\frac{\partial}{\partial v_{j}}\Phi(\boldsymbol{\theta};\mathbf{x })=\left[\mathbf{w}_{j}^{\top}\mathbf{x}+b_{j}\right]_{+},$ $\displaystyle\frac{\partial}{\partial\mathbf{w}_{j}}\Phi(\boldsymbol{\theta}; \mathbf{x})=v_{j}x\sigma^{\prime}_{j},$ $\displaystyle\frac{\partial}{\partial b_{j}}\Phi(\boldsymbol{\theta};\mathbf{x })=v_{j}\sigma^{\prime}_{j}.$ $$

Combining the above with the KKT conditions, we arrive at

$$ $\displaystyle v_{j}=\sum_{i=1}^{n}\lambda_{i}y_{i}\left[\mathbf{w}_{j}^{\top} \mathbf{x}_{i}+b_{j}\right]_{+},$ (7) $\displaystyle\mathbf{w}_{j}=v_{j}\sum_{i=1}^{n}\lambda_{i}y_{i}\mathbf{x}_{i} \sigma^{\prime}_{i,j},$ (8) $\displaystyle b_{j}=v_{j}\sum_{i=1}^{n}\lambda_{i}y_{i}\sigma^{\prime}_{i,j},$ (9) $$

for all $j\in[k]$.

###### Lemma A.1 .

Let $\phi$ be a 2-layer homogeneous network that satisfy the KKT conditions. Let $x_{l}<x_{l+1}$ be 2 adjacent marginal training points. The number of breaking points in the interval $[x_{l},x_{l+1}]$ is at most 2, i.e. $|\{-\frac{b_{j}}{w_{j}}:~{}x_{l}\leq-\frac{b_{j}}{w_{j}}\leq x_{l+1}\}|\leq 2$. Moreover, if there are 2 breaking points, the neurons forming the breaking points must have different signs.

###### Proof.

Let $c_{j_{1}}(x)=v_{j_{1}}[w_{j_{1}}x+b_{j_{1}}]_{+}$ and $c_{j_{2}}(x)=v_{j_{2}}[w_{j_{2}}x+b_{j_{2}}]_{+}$ be 2 neurons with $w_{j_{1}}<0$ and $w_{j_{2}}<0$ such that their breaking points are between $x_{l}$ and $x_{l+1}$. Both $c_{j_{1}}$ and $c_{j_{2}}$ are determined by all the training points that are smaller than $x_{l+1}$.
let us look at their breaking point $-\frac{b_{l}}{w_{l}}$ and $-\frac{b_{l+1}}{w_{l+1}}$.
From Eq. (8) and Eq. (9) we get that

$$ $-\frac{b_{j_{1}}}{w_{j_{1}}}=-\frac{v_{j_{1}}\sum_{i=1}^{l}\lambda_{i}y_{i}}{v _{j_{1}}\sum_{i=1}^{l}\lambda_{i}y_{i}x_{i}}=-\frac{\sum_{i=1}^{l}\lambda_{i}y _{i}}{\sum_{i=1}^{l}\lambda_{i}y_{i}x_{i}}=-\frac{v_{j_{2}}\sum_{i=1}^{l} \lambda_{i}y_{i}}{v_{j_{2}}\sum_{i=1}^{l}\lambda_{i}y_{i}x_{i}}=-\frac{b_{j_{2 }}}{w_{j_{2}}}$ $$

This means the neurons have the same breaking point and are active on the same region, which means they are the same neuron.

The same argument can be made to show that if $w_{l}>0$ and $w_{l+1}>0$ the neurons have the same breaking point.
We conclude that in this interval we can have at most one neuron with $w>0$ and at most one neuron with $w<0$ with breaking points in the interval $[x_{l},x_{l+1}]$.
∎

###### Lemma A.2 .

Let $x_{1}<x_{2}<\dots<x_{n}$ be the training points on the margin and $\phi(x;\theta)$ be a 2-layers NN. If The network $\phi(x;\theta)$ satisfies the KKT conditions, and is not constant in any interval, then the number of times it crosses the margin is at most $6n$.

###### Proof.

between each $x_{l},~{}x_{l+1}$ there are at most 2 breaking points, i.e the networks crosses the margin at most 6 times in the interval $[x_{l},~{}x_{l+1}]$ (3 times the the margin $y=1$ and 3 times the margin $y=-1$). Before the point $x_{1}$ and after the point $x_{n}$ the network crosses the line at most 6 times in each interval. So if we sum up all the crosses we get that the network crosses the margin at most $6\cdot(n-2)+12=6n$
∎

Figure: Figure 2: The blue network is a network which the breaking point is not a training point. The dotted-red network has smaller norm.
Refer to caption: x4.png

###### Proof Of Thm. 3.2 .

Assume towards contradiction that there are no training points in the interval $[-\frac{b_{i-1}}{w_{i-1}},-\frac{b_{i+1}}{w_{i+1}}]$. Denote $x_{1}=\max\{x_{i}:~{}x_{i}<-\frac{b_{i-1}}{w_{i-1}}\text{ and }x_{i}\text{ is
a marginal training point}\}$ and $x_{2}=\min\{x_{i}:~{}x_{i}>-\frac{b_{i+1}}{w_{i+1}}\text{ and }x_{i}\text{ is
a marginal training point}\}$
$x_{1}$ must exist, otherwise $-\frac{b_{i-1}}{w_{i-1}}$ and $-\frac{b_{i}}{w_{i}}$ are active on the same set of training points, and by Eq. (8) and Eq. (9), $-\frac{b_{i-1}}{w_{i-1}}=-\frac{b_{i}}{w_{i}}$. Same argument holds for $x_{2}$. Let us look at the interval $[x_{1},x_{2}]$. This interval has three breaking points, $-\frac{b_{i-1}}{w_{i-1}},~{}-\frac{b_{i}}{w_{i}}$ and $-\frac{b_{i+1}}{w_{i+1}}$, contradiction to A.1.
Each interval crosses the margin at most twice, so the number points lying on the margin is at most 4.
∎

###### Proof Of Thm. 3.3 .

This proof follows the same logic as the proof of Lemma A.6 in Kornowski et al. [].

Assume towards contradiction that neither $-\frac{b_{i}}{w_{i}}$ nor $-\frac{b_{i+1}}{w_{i+1}}$ are in the training set, if $x\in[-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}}]$ then $x\in(-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}})$.

Note that $sgn(w_{i-1})=-sgn(w_{i})$ because there is no training point in the interval $(-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}})$ so by A.1 they must have different signs.

Also note that there must be a training point either in $[-\frac{b_{i-2}}{w_{i-2}},-\frac{b_{i-1}}{w_{i-1}}]$ or in $[-\frac{b_{i}}{w_{i}},-\frac{b_{i+1}}{w_{i+1}}]$ (or in both). If it is not the case there are at least 3 breaking points between to training data points, contradiction to A.1.

CASE 1: $v_{i}^{2}+\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}+\frac{b_{i}}{1-\delta}(\frac{w_{i}
b_{i-1}}{w_{i-1}}-b_{i})-\frac{w_{1}v_{i}w_{i}}{v_{1}}-\frac{b_{1}b_{i-1}v_{i}
w_{i}}{v_{1}w_{i-1}}>0$
Define the following neural network:

$$ $\displaystyle\phi(\theta_{\delta},x):=$ $\displaystyle\sum_{j\in[n]\setminus\{i-1,i,1\}}v_{j}\left[w_{j}\cdot x+b_{j} \right]_{+}+\left(1-\delta\frac{v_{i}w_{i}}{v_{i-1}w_{i-1}}\right)v_{i-1}\left [w_{i-1}x+b_{i-1}\right]_{+}+$ $\displaystyle(1-\delta)v_{i}\left[w_{i}x+b_{i}-\frac{\delta}{1-\delta}\left( \frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i}\right)\right]_{+}+$ $\displaystyle v_{1}\left[\left(w_{1}+\delta\frac{v_{i}w_{i}}{v_{1}}\right)x+ \left(b_{1}+\delta\frac{v_{i}w_{i}b_{i-1}}{v_{1}w_{i-1}}\right)\right]_{+}$ $$

For small enough $\delta$, the new breaking points do not cross any training point so for any training point $x_{j}$ we have that $\phi(\theta,x_{j})=\phi(\theta_{\delta},x_{j})$ and in particular $\phi(\theta_{\delta},x)$ satisfies the margin condition for each training point $x_{j}$. Also note that $\|\phi(\theta,x)-\phi(\theta_{\delta},x)\|^{2}\rightarrow 0$ as $\delta\rightarrow 0$. Let us compute $\|\phi(\theta_{\delta},x)\|^{2}$:

$$ $\displaystyle\|\phi(\theta_{\delta},x)\|^{2}=$ $\displaystyle\sum_{j\in[n]\setminus\{i-1,i,1\}}(v_{j}^{2}+w_{j}^{2}+b_{j}^{2}) +\left(1-\delta\frac{v_{i}w_{i}}{v_{i-1}w_{i-1}}\right)^{2}v_{i-1}^{2}+w_{i-1} ^{2}+b_{i-1}^{2}+$ $\displaystyle(1-\delta)^{2}v_{i}^{2}+w_{i}^{2}+\left(b_{i}-\frac{\delta}{1- \delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})\right)^{2}+$ $\displaystyle v_{1}^{2}+\left(w_{1}+\delta\frac{v_{i}w_{i}}{v_{1}}\right)^{2}+ \left(b_{1}+\delta\frac{v_{i}w_{i}b_{i-1}}{v_{1}w_{i-1}}\right)^{2}=$ $\displaystyle\|\phi(\theta,x)\|^{2}-2\delta\left(v_{i}^{2}+\frac{v_{i}w_{i}v_{ i-1}}{w_{i-1}}+\frac{b_{i}}{1-\delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})- \frac{w_{1}v_{i}w_{i}}{v_{1}}-\frac{b_{1}b_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}} \right)+O(\delta^{2})$ $\displaystyle<\|\phi(\theta,x)\|^{2}$ $$

CASE 2: $v_{i}^{2}+\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}+\frac{b_{i}}{1-\delta}(\frac{w_{i}
b_{i-1}}{w_{i-1}}-b_{i})-\frac{w_{1}v_{i}w_{i}}{v_{1}}-\frac{b_{1}b_{i-1}v_{i}
w_{i}}{v_{1}w_{i-1}}<0$
Define the following neural network:

$$ $\displaystyle\phi(\theta_{\delta},x):=$ $\displaystyle\sum_{j\in[n]\setminus\{i-1,i,1\}}v_{j}\left[w_{j}\cdot x+b_{j} \right]_{+}+\left(1+\delta\frac{v_{i}w_{i}}{v_{i-1}w_{i-1}}\right)v_{i-1}\left [w_{i-1}x+b_{i-1}\right]_{+}+$ $\displaystyle(1+\delta)v_{i}\left[w_{i}x+b_{i}+\frac{\delta}{1+\delta}\left( \frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i}\right)\right]_{+}+$ $\displaystyle v_{1}\left[\left(w_{1}-\delta\frac{v_{i}w_{i}}{v_{1}}\right)x+ \left(b_{1}-\delta\frac{v_{i}w_{i}b_{i-1}}{v_{1}w_{i-1}}\right)\right]_{+}$ $$

The norm $\|\phi(\theta_{\delta},x)\|^{2}$ is:

$$ $\displaystyle\|\phi(\theta_{\delta},x)\|^{2}=$ $\displaystyle\sum_{j\in[n]\setminus\{i-1,i,1\}}(v_{j}^{2}+w_{j}^{2}+b_{j}^{2}) +\left(1+\delta\frac{v_{i}w_{i}}{v_{i-1}w_{i-1}}\right)^{2}v_{i-1}^{2}+w_{i-1} ^{2}+b_{i-1}^{2}+$ $\displaystyle(1+\delta)^{2}v_{i}^{2}+w_{i}^{2}+\left(b_{i}+\frac{\delta}{1- \delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})\right)^{2}+$ $\displaystyle v_{1}^{2}+\left(w_{1}-\delta\frac{v_{i}w_{i}}{v_{1}}\right)^{2}+ \left(b_{1}-\delta\frac{v_{i}w_{i}b_{i-1}}{v_{1}w_{i-1}}\right)^{2}=$ $\displaystyle\|\phi(\theta,x)\|^{2}-2\delta\left(-v_{i}^{2}-\frac{v_{i}w_{i}v_ {i-1}}{w_{i-1}}-\frac{b_{i}}{1-\delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})+ \frac{w_{1}v_{i}w_{i}}{v_{1}}+\frac{b_{1}b_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}} \right)+O(\delta^{2})$ $\displaystyle<\|\phi(\theta,x)\|^{2}$ $$

CASE 3: $v_{i}^{2}+\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}+\frac{b_{i}}{1-\delta}(\frac{w_{i}
b_{i-1}}{w_{i-1}}-b_{i})-\frac{w_{1}v_{i}w_{i}}{v_{1}}-\frac{b_{1}b_{i-1}v_{i}
w_{i}}{v_{1}w_{i-1}}=0$
In this case, define the following neural network:

$$ $\displaystyle\phi(\theta_{\delta},x):=$ $\displaystyle\sum_{j\in[n]\setminus\{i-1,i,1\}}v_{j}\left[w_{j}\cdot x+b_{j} \right]_{+}+$ $\displaystyle(1-\delta)v_{i-1}\left[w_{i-1}x+b_{i-1}-\frac{\delta}{1-\delta} \left(\frac{w_{i-1}b_{i}}{w_{i}}-b_{i-1}\right)\right]_{+}+$ $\displaystyle\left(1-\delta\frac{v_{i-1}w_{i-1}}{v_{i}w_{i}}\right)v_{i}\left[ w_{i}x+b_{i}\right]_{+}+$ $\displaystyle v_{1}\left[\left(w_{1}+\delta\frac{v_{i-1}w_{i-1}}{v_{1}}\right) x+b_{1}+\delta\frac{v_{i-1}w_{i-1}b_{i}}{v_{1}w_{i}}\right]_{+}$ $$

Before computing the norm, let us note a two observations:

- 1.
By assumption, $v_{i}w_{i}=-v_{i-1}w_{i-1}$ and hence $\frac{v_{i}}{w_{i-1}}=-\frac{v_{i-1}}{w_{i}}$,
- 2.
By definition of case 3, $v_{i}^{2}+\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}+\frac{b_{i}}{1-\delta}\left(\frac{
w_{i}b_{i-1}}{w_{i-1}}-b_{i}\right)-\frac{w_{1}v_{i}w_{i}}{v_{1}}-\frac{b_{1}b
_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}}=0$,

Now let us compute the norm:

$$ $\displaystyle\|\phi(\theta_{\delta},x)\|^{2}=\sum_{j\in[n]\setminus\{i-1,i,1\} }(v_{j}^{2}+w_{j}^{2}+b_{j}^{2})+(1-\delta)^{2}v_{i-1}^{2}+w_{i-1}^{2}+\left(b _{i-1}-\frac{\delta}{1-\delta}(\frac{w_{i-1}b_{i}}{w_{i}}-b_{i-1})\right)^{2}+$ $\displaystyle\left(1-\delta\frac{v_{i-1}w_{i-1}}{v_{i}w_{i}}\right)^{2}v_{i}^{ 2}+w_{i}^{2}+b_{i}^{2}+$ $\displaystyle\left(w_{1}+\delta\frac{v_{i-1}w_{i-1}}{v_{1}}\right)^{2}+\left(b _{1}+\delta\frac{v_{i-1}w_{i-1}b_{i}}{v_{1}w_{i}}\right)^{2}=$ $\displaystyle\|\phi(\theta,x)\|^{2}-2\delta\left(v_{i-1}^{2}+\frac{b_{i-1}}{1- \delta}(\frac{w_{i-1b_{i}}}{w_{i}}-b_{i-1})+\frac{v_{i-1}w_{i-1}v_{i}}{w_{i}}- \frac{w_{1}v_{i-1}w_{i-1}}{v_{1}}-\frac{b_{1}b_{i}v_{i-1}w_{i-1}}{v_{1}w_{i}} \right)+O(\delta^{2})$ $$

We need to show that

$$ $v_{i-1}^{2}+\frac{b_{i-1}}{1-\delta}\left(\frac{w_{i-1b_{i}}}{w_{i}}-b_{i-1} \right)+\frac{v_{i-1}w_{i-1}v_{i}}{w_{i}}-\frac{w_{1}v_{i-1}w_{i-1}}{v_{1}}- \frac{b_{1}b_{i}v_{i-1}w_{i-1}}{v_{1}w_{i}}\neq 0$ $$

(if $v_{i-1}^{2}+\frac{b_{i-1}}{1-\delta}(\frac{w_{i-1b_{i}}}{w_{i}}-b_{i-1})+\frac
{v_{i-1}w_{i-1}v_{i}}{w_{i}}-\frac{w_{1}v_{i-1}w_{i-1}}{v_{1}}-\frac{b_{1}b_{i
}v_{i-1}w_{i-1}}{v_{1}w_{i}}<0$ then, as in the previous cases, we change every $\delta$ to $-\delta$ and every $-\delta$ to $\delta$).
By observation 1 we know that:

$$ $\displaystyle\frac{v_{i-1}w_{i-1}v_{i}}{w_{i}}=-\frac{v_{i}w_{i}v_{i}}{w_{i}}= -v_{i}^{2}$ (10) $\displaystyle\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}=-\frac{v_{i-1}w_{i-1}v_{i}}{w_{ i-1}}=-v_{i-1}^{2}$ (11) $$

Combine this with observation 2 we get:

$$ $\displaystyle v_{i}^{2}+\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}+\frac{b_{i}}{1- \delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})-\frac{w_{1}v_{i}w_{i}}{v_{1}}- \frac{b_{1}b_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}}=0$ $\displaystyle\Rightarrow\frac{b_{i}}{1-\delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_ {i})-\frac{b_{1}b_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}}=\frac{w_{1}v_{i}w_{i}}{v_{1}} -\frac{v_{i}w_{i}v_{i-1}}{w_{i-1}}-v_{i}^{2}$ $\displaystyle\Rightarrow\frac{b_{i}}{1-\delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_ {i})-\frac{b_{1}b_{i-1}v_{i}w_{i}}{v_{1}w_{i-1}}=v_{i-1}^{2}-v_{i}^{2}+\frac{w _{1}v_{i}w_{i}}{v_{1}},$ (12) $$

where Eq. (12) follows by substitution of Eq. (11). Rewriting the equation in case 3 using Eq. (10), we need to show that

$$ $v_{i-1}^{2}-v_{i}^{2}+\frac{w_{1}v_{i}w_{i}}{v_{1}}+\frac{b_{i-1}}{1-\delta}( \frac{w_{i-1}b_{i}}{w_{i}}-b_{i-1})-\frac{b_{1}b_{i}v_{i-1}w_{i-1}}{v_{1}w_{i} }\neq 0$ $$

and using Eq. (12), we can further simplify it to

$$ $\frac{b_{i}}{1-\delta}(\frac{w_{i}b_{i-1}}{w_{i-1}}-b_{i})-\frac{b_{1}b_{i-1}v _{i}w_{i}}{v_{1}w_{i-1}}+\frac{b_{i-1}}{1-\delta}(\frac{w_{i-1}b_{i}}{w_{i}}-b _{i-1})+\frac{b_{1}b_{i}v_{i}w_{i}}{v_{1}w_{i}}\neq 0$ $$

That expression can be rewritten as

$$ $\frac{b_{1}v_{i}(b_{i}w_{i-1}-b_{i-1}w_{i})}{v_{1}w_{i-1}}+\frac{1}{1-\delta}( -b_{i-1}^{2}+\frac{b_{i-1}b_{i}w_{i}}{w_{i-1}}+\frac{b_{i-1}b_{i}w_{i-1}}{w_{i }}-b_{i}^{2})$ $$

The only way this expression is equal to 0 for every sufficiently small $\delta>0$ is when both summands are 0. let us look at the second summand.

$$ $\displaystyle\frac{1}{1-\delta}(-b_{i-1}^{2}+\frac{b_{i-1}b_{i}w_{i}}{w_{i-1}} +\frac{b_{i-1}b_{i}w_{i-1}}{w_{i}}-b_{i}^{2})=\frac{1}{1-\delta}(-b_{i-1}^{2}+ b_{i-1}b_{i}(\frac{w_{i}}{w_{i-1}}+\frac{w_{i-1}}{w_{i}})-b_{i}^{2})\leq$ $\displaystyle\frac{1}{1-\delta}(-b_{i-1}^{2}-2b_{i-1}b_{i}-b_{i}^{2})=-\frac{1 }{1-\delta}(b_{i-1}+b_{i})^{2}$ $$

Where the inequality stems from the inequality $x+\frac{1}{x}\leq-2$ for every $x<0$ (and equality holds when $x=-1$) where in our case $x=\frac{w_{i}}{w_{i-1}}$, and they have different signs so $\frac{w_{i}}{w_{i-1}}<0$. For the summand to be 0 it must holds that $w_{i}=-w_{i-1}$ and $b_{i}=-b_{i-1}$, but that can not happen because if that would have happened then $-\frac{b_{i}}{w_{i}}=-\frac{b_{i-1}}{w_{i-1}}$; i.e., the two neurons have the same breakpoint.

An example of a network with smaller norm can be found in Figure 2.
∎

###### Proof Of Thm. 3.4 .

We prove that for each iteration, we add at least one training point to the set $S$. As the number of iteration is finite, and in each iteration the number of points added to $S$ are finite, $S$ is finite.

If the condition in line 6 in Algorithm 1 is met, by Thm. 3.2 one of the points added to $S$ must be a training point, and the number of such points is at most 4.

If both conditions at lines 9 and 11 are met, by Thm. 3.3 either $y$ or $z$ is a training point.
So the ratio of training points in $S$ is at least $\frac{1}{4}$
∎

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Proof Of Thm. 3.2 .

###### Proof Of Thm. 3.3 .

###### Proof Of Thm. 3.4 .

## Appendix B Proofs of lemmas and theorems in Section 4

We show an upper bound on the value $|\phi(\theta,\mathbf{x})|$ whenever $x$ is sampled according to $\mathcal{D}$ (that holds with high probability w.r.t the initialization and $\mathbf{x}$) and a lower bound whenever $\mathbf{x}$ is in the training set (that holds with high probability w.r.t the initialization). We prove that the lower bound is greater than the upper bound, thus giving us a way to differentiate between training and non training examples.

We use the same notations as the previous section.

#### Notations

- •
Let $J_{+}=\{j:v_{j}>0\}$ and $J_{-}=\{j:v_{j}<0\}$.
- •
Let $m$ be the value of the network’s margin.
- •
Let $\delta=\max_{i\neq j}\left\{|\mathbf{x}_{i}^{\top}\mathbf{x}_{j}|\right\}$ and $\Delta=\min_{i\in[n]}\left\{\|x_{i}\|^{2}\right\}$.
- •
For $\mathbf{x}\sim\mathcal{D}$ let $\delta_{x}=\max\{\delta,\max_{i}\in[n]\{|\mathbf{x}_{i}^{\top}\mathbf{x}|\}\}$.

The following 2 lemmas are taken from []. In their paper, they proved a similar variant of the lemmas, and for the completeness of our proof, we give the proof of our variant.

###### Lemma B.1 .

For all $l\in[n]$ we have

$$ $max\left\{\sum_{j\in J_{+}}v_{j}^{2}\lambda_{l}\sigma^{\prime}_{l,j},\sum_{j \in J_{-}}v_{j}^{2}\lambda_{l}\sigma^{\prime}_{l,j}\right\}\leq\frac{m}{\Delta +1-2\delta(n-1)}$ $$

###### Proof.

Denote $\alpha_{+}=\max_{i\in[n]}\left(\sum_{j\in J_{+}}v_{j}^{2}\lambda_{i}\sigma^{
\prime}_{i,j}\right)$ and $\alpha_{-}=\max_{i\in[n]}\left(\sum_{j\in J_{-}}v_{j}^{2}\lambda_{i}\sigma^{
\prime}_{i,j}\right)$. w.l.o.g $\alpha_{+}\geq\alpha_{-}$ (other direction is similar). Denote $\alpha=\alpha_{+}$ and $k\in\text{argmax}_{i\in[n]}\left(\sum_{j\in J_{+}}v_{j}^{2}\lambda_{i}\sigma^{
\prime}_{i,j}\right)$.
If $\lambda_{k}=0$ we are done. Otherwise, by KKT we know that $y_{k}\phi(\theta,x_{k})=m$.
By Eq. (8) and Eq. (9) we have for all $j$

$$ $\displaystyle\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j}=\sum_{i=1}^{n}\lambda_{ i}y_{i}\sigma^{\prime}_{i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)= \lambda_{k}y_{k}\sigma^{\prime}_{k,j}v_{j}(\|\mathbf{x}_{k}\|^{2}+1)+\sum_{i \neq k}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf {x}_{k}+1)$ (13) $$

Consider 2 cases:
CASE 1: assume $y_{k}=1$.

$$ $\displaystyle m=y_{k}\phi(\theta,\mathbf{x}_{k})$ $\displaystyle=\sum_{i=1}^{n}v_{i}\left[\mathbf{w}_{i}^{\top}\mathbf{x}_{k}+b_{ i}\right]_{+}$ $\displaystyle\geq\sum_{j\in J_{+}}v_{j}(\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_ {j})+\sum_{j\in J_{-}}v_{j}\left[\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j} \right]_{+}$ (14) $$

Using the fact that $y_{k}=1$ and Eq. (13) we get

$$ $\displaystyle\sum_{j\in J_{+}}v_{j}(\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j}) =\sum_{j\in J_{+}}\left(\lambda_{k}\sigma^{\prime}_{k,j}v_{j}^{2}(\|\mathbf{x} _{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}v_{j}^{2}( \mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right)$ $\displaystyle\geq\sum_{j\in J_{+}}\lambda_{k}v_{j}^{2}\sigma^{\prime}_{k,j}( \Delta+1)-\delta\sum_{j\in J_{+}}\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j }v_{j}^{2}$ $\displaystyle\geq(\Delta+1)\alpha-\delta(n-1)\alpha$ (15) $$

Using $y_{k}=1$ and Eq. (13) again we get

$$ $\displaystyle\sum_{j\in J_{-}}v_{j}\left[\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b _{j}\right]_{+}=\sum_{j\in J_{-}}v_{j}\left[\lambda_{k}y_{k}\sigma^{\prime}_{k ,j}v_{j}(\|x_{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}v _{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}$ $\displaystyle\geq\sum_{j\in J_{-}}v_{j}\left[\sum_{i\neq k}\lambda_{i}y_{i} \sigma^{\prime}_{i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}= \sum_{j\in J_{-}}v_{j}\left[\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}|v_{ j}|(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}$ $\displaystyle\geq\sum_{j\in j_{-}}v_{j}\left[\sum_{i\neq k}\lambda_{i}\sigma^{ \prime}_{i,j}|v_{j}|(\delta+1)\right]_{+}$ $\displaystyle\geq-(\delta+1)\sum_{j\in j_{-}}\sum_{i\neq k}\lambda_{i}\sigma^{ \prime}_{i,j}v_{j}^{2}\geq-(\delta+1)(n-1)\alpha$ (16) $$

Combining Eq. (14), Eq. (15) and Eq. (16) we get

$$ $\displaystyle m\geq(\Delta+1)\alpha-\delta(n-1)\alpha-\delta(n-1)\alpha$ $\displaystyle=(\Delta+1)\alpha-2\delta(n-1)\alpha=\alpha(\Delta+1-2\delta(n-1))$ $\displaystyle\Rightarrow\alpha\leq\frac{m}{\Delta+1-2\delta(n-1)}$ $$

CASE 2: Assume $y_{k}=-1$.
Fix some $j\in J_{+}$. If $\sigma^{\prime}_{j,k}=0$ then

$$ $\lambda_{k}\sigma^{\prime}_{k,j}v_{j}=0\leq\frac{\delta+1}{\Delta+1}\sum_{i \neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2}$ $$

Otherwise, by the definition of $\sigma^{\prime}_{k,j}$ we have $\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j}\geq 0$.

$$ $\displaystyle 0\leq\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j}=\sum_{i\neq k} \lambda_{i}y_{i}\sigma^{\prime}_{i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k} +1)+\lambda_{k}y_{k}\sigma^{\prime}_{k,j}v_{j}(\|\mathbf{x}_{k}\|^{2}+1)$ $\displaystyle\leq\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}(\delta+1) -\lambda_{k}\sigma^{\prime}_{k,j}v_{j}(\Delta+1)$ $\displaystyle\Rightarrow\lambda_{k}\sigma^{\prime}_{k,j}v_{j}\leq\frac{\delta+ 1}{\Delta+1}\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}$ $\displaystyle\Rightarrow\lambda_{k}\sigma^{\prime}_{k,j}v_{j}^{2}\leq\frac{ \delta+1}{\Delta+1}\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2}$ $$

This is true for every $j\in J_{+}$, so by summing over all $j\in J_{+}$ we get

$$ $\displaystyle\sum_{j\in J_{+}}\lambda_{k}\sigma^{\prime}_{k,j}v_{j}^{2}$ $\displaystyle\leq\frac{\delta+1}{\Delta+1}\sum_{j\in J_{+}}\sum_{i\neq k} \lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2}$ $\displaystyle\leq\frac{\delta+1}{\Delta+1}(n-1)\cdot\max_{i\in[n]}\left(\sum_{ j\in J_{+}}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2}\right)$ $\displaystyle<\max_{i\in[n]}\left(\sum_{j\in J_{+}}\lambda_{i}\sigma^{\prime}_ {i,j}v_{j}^{2}\right)=\sum_{j\in J_{+}}\lambda_{k}\sigma^{\prime}_{k,j}v_{j}^{2}$ $$

Where the last equality is the definition of $k$. This case can not happen, so $y_{k}=1$ and we have already proved that case.
∎

###### Lemma B.2 .

For all $l\in[n]$ such that $y_{l}=1$ we have

$$ $\sum_{j\in J_{+}}v_{j}^{2}\lambda_{l}\sigma^{\prime}_{l,j}\geq\left(m-(\delta+ 1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}\right)\cdot\frac{1}{\Delta+1}$ $$

and for all $l\in[n]$ such that $y_{l}=-1$ we have

$$ $\sum_{j\in J_{-}}v_{j}^{2}\lambda_{l}\sigma^{\prime}_{l,j}\geq\left(m-(\delta+ 1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}\right)\cdot\frac{1}{\Delta+1}$ $$

###### Proof.

Let $k\in[n]$ such that $y_{k}=1$. We have

$$ $m\leq\phi(\theta,x_{k})=\sum_{j\in J}v_{j}\left[\mathbf{w}_{j}^{\top}\mathbf{x }_{k}+b_{j}\right]_{+}\leq\sum_{j\in J+}v_{j}\left[\mathbf{w}_{j}^{\top} \mathbf{x}_{k}+b_{j}\right]_{+}\leq\sum_{j\in J_{+}}v_{j}|\mathbf{w}_{j}^{\top }\mathbf{x}_{k}+b_{j}|$ $$

Let us upper bound it

$$ $\displaystyle\sum_{j\in J_{+}}v_{j}\left|\lambda_{k}y_{k}\sigma^{\prime}_{k,j} v_{j}(\|\mathbf{x}_{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}y_{i}\sigma^{\prime}_ {i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right|$ $\displaystyle\leq\sum_{j\in J_{+}}v_{j}\left(\lambda_{k}\sigma^{\prime}_{k,j}v _{j}(\|\mathbf{x}_{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v _{j}|\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1|\right)$ $\displaystyle=\sum_{j\in J_{+}}\left(\lambda_{k}\sigma^{\prime}_{k,j}v_{j}^{2} (\|\mathbf{x}_{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j} ^{2}|\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1|\right)$ $\displaystyle\leq\sum_{j\in J_{+}}\left((\Delta+1)\lambda_{k}\sigma^{\prime}_{ k,j}v_{j}^{2}+(\delta+1)\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2 }\right)$ $\displaystyle=(\Delta+1)\sum_{j\in J_{+}}\lambda_{k}\sigma^{\prime}_{k,j}v_{j} ^{2}+(\delta+1)\sum_{j\in J_{+}}\sum_{i\neq k}\lambda_{i}\sigma^{\prime}_{i,j} v_{j}^{2}$ $$

Using B.1 we get

$$ $\displaystyle m\leq(\Delta+1)\sum_{j\in J_{+}}\lambda_{k}\sigma^{\prime}_{k,j} v_{j}^{2}+(\delta+1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}$ $\displaystyle\Rightarrow\sum_{j\in J_{+}}\lambda_{k}\sigma^{\prime}_{k,j}v_{j} ^{2}\geq\left(m-(\delta+1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}\right)\cdot \frac{1}{\Delta+1}$ $$

Similar arguments yield the other inequality
∎

###### Lemma B.3 .

Under Assumption 4.1, with probability at least $1-2\tau$

$$ $O(\frac{n\cdot\delta}{\Delta})=o_{d}(1)$ $$

###### Proof.

First, we prove using the union bound that $\Pr[n\cdot\delta\geq\Omega(d)]<\tau$.

$$ $\displaystyle\Pr[n\cdot\delta\geq\Omega(d)]\leq\sum_{\begin{subarray}{c}i,j=1 \\ i\neq j\end{subarray}}^{n}\Pr[n\cdot|\mathbf{x}_{i}^{\top}\mathbf{x}_{j}|\geq \Omega(d)]\leq\binom{n}{2}\cdot\frac{\tau}{n^{2}}<\tau$ $$

Secondly, we prove using the union bound that $\Pr[\Delta<o(d)]<\tau$

$$ $\displaystyle\Pr[\Delta<o(d)]\leq\sum_{i=1}^{n}\Pr[\|\mathbf{x}_{i}\|^{2}<o(d) ]\leq n\cdot\frac{\tau}{n}=\tau$ $$

Now, using the union bound again, we get

$$ $\displaystyle\Pr[\frac{n\cdot\delta}{\Delta}>\Omega_{d}(1)]\leq\Pr[\Delta<o(d) ]+\Pr[n\cdot\delta\geq\Omega(d)]\leq 2\tau$ $$

And hence with probability at least $1-2\tau$ we have that

$$ $O(\frac{n\cdot\delta}{\Delta})=o_{d}(1)$ $$

∎

###### Lemma B.4 .

Let $x\sim\mathcal{D}$. Under Assumption 4.1, with probability at least $1-2\tau$

$$ $O(\frac{n\cdot\delta_{x}}{\Delta})=o_{d}(1)$ $$

###### Proof.

First, we prove using the union bound that $\Pr[\Delta<o(d)]<\tau$

$$ $\displaystyle\Pr[\Delta<o(d)]\leq\sum_{i=1}^{n}\Pr[\|\mathbf{x}_{i}\|^{2}<o(d) ]\leq n\cdot\frac{\tau}{n}=\tau$ $$

Second, we prove using the union bound that $\Pr[n\cdot\delta_{x}\geq\Omega(d)]<\tau$.

$$ $\displaystyle\Pr[n\cdot\delta_{x}\geq\Omega(d)]\leq\sum_{\begin{subarray}{c}i, j=1\\ i\neq j\end{subarray}}^{n}\Pr[n\cdot|\mathbf{x}_{i}^{\top}\mathbf{x}_{j}|\geq \Omega(d)]+\sum_{i=1}^{n}\Pr[n|\mathbf{x}_{i}^{\top}\mathbf{x}|\geq\Omega(d)]$ $\displaystyle\leq\binom{n+1}{2}\cdot\frac{\tau}{n^{2}}<\tau$ $$

Where in last inequality we used the fact that $n\geq 3$.
Now, using the union bound again, we get

$$ $\displaystyle\Pr[\frac{n\cdot\delta_{x}}{\Delta}>\Omega_{d}(1)]\leq\Pr[\Delta< o(d)]+\Pr[n\cdot\delta_{x}\geq\Omega(d)]\leq 2\tau$ $$

And hence with probability at least $1-2\tau$ we have that

$$ $O(\frac{n\cdot\delta_{x}}{\Delta})=o_{d}(1)$ $$

∎

###### Proof Of Thm. 4.2 .

Assume $\mathbf{x}$ is in the training data, i.e there is $k\in[n]$ such that $\mathbf{x}=\mathbf{x}_{k}$. Assume w.l.o.g that $\phi(\theta,\mathbf{x}_{k})>0$, i.e $y_{k}=1$ (the case $y_{k}=-1$ is similar).
We can decompose the network into 2 components, as follow:

$$ $\displaystyle\phi(\theta,\mathbf{x}_{k})=\sum_{i=1}^{n}v_{i}\left[\mathbf{w}_{ i}^{\top}\mathbf{x}_{k}+b_{i}\right]_{+}=\sum_{j\in J_{+}}v_{j}\left[\mathbf{w }_{j}^{\top}\mathbf{x}_{k}+b_{j}\right]_{+}+\sum_{j\in J_{-}}v_{j}\left[ \mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b_{j}\right]_{+}$ (17) $$

Let us bound every sum from below. Using Eq. (8), Eq. (9) and the fact that $\left[x\right]_{+}\geq x$ we get

$$ $\displaystyle\sum_{j\in J_{+}}v_{j}\left[\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b _{j}\right]_{+}\geq\sum_{j\in J_{+}}v_{j}(\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+ b_{j})=\sum_{j\in J_{+}}v_{j}\left[\sum_{i=1}^{n}\lambda_{i}y_{i}v_{j}\sigma^{ \prime}_{i,j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]$ $\displaystyle=\sum_{j\in J_{+}}v_{j}^{2}\lambda_{k}y_{k}\sigma^{\prime}_{k,j}( \|\mathbf{x}_{k}\|^{2}+1)+\sum_{j\in J_{+}}\sum_{i\neq k}v_{j}^{2}\lambda_{i}y _{i}\sigma^{\prime}_{i,j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)$ $\displaystyle\geq\sum_{j\in J_{+}}v_{j}^{2}\lambda_{k}\sigma^{\prime}_{k,j}(\| \mathbf{x}_{k}\|^{2}+1)-\sum_{j\in J_{+}}\sum_{i\neq k}v_{j}^{2}\lambda_{i} \sigma^{\prime}_{i,j}|\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1|$ (18) $$

And for the second sum

$$ $\displaystyle\sum_{j\in J_{-}}v_{j}\left[\mathbf{w}_{j}^{\top}\mathbf{x}_{k}+b _{j}\right]_{+}=\sum_{j\in J_{-}}v_{j}\left[\sum_{i=1}^{n}\lambda_{i}y_{i}v_{j }\sigma^{\prime}_{i,j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}$ $\displaystyle=\sum_{j\in J_{-}}v_{j}\left[\lambda_{k}y_{k}v_{j}\sigma^{\prime} _{k,j}(\|\mathbf{x}_{k}\|^{2}+1)+\sum_{i\neq k}\lambda_{i}y_{i}v_{j}\sigma^{ \prime}_{i,j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}$ $\displaystyle\geq\sum_{j\in J_{-}}v_{j}\left[\sum_{i\neq k}\lambda_{i}y_{i}v_{ j}\sigma^{\prime}_{i,j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{k}+1)\right]_{+}$ (19) $$

We need to show that $\sum_{j\in J_{+}}v_{j}^{2}\lambda_{k}\sigma^{\prime}_{k,j}$, $\sum_{j\in J_{+}}\sum_{i\neq k}v_{j}^{2}\lambda_{i}\sigma^{\prime}_{i,j}$, $\sum_{j\in J_{-}}\sum_{i\neq k}\lambda_{i}y_{i}v_{j}^{2}\sigma^{\prime}_{i,j}$ and $\sum_{j\in J_{-}}v_{j}^{2}\lambda_{k}\sigma^{\prime}_{k,j}$ are not too small and not too large.

From Lemma B.2 we have that

$$ $\sum_{j\in J_{+}}v_{j}^{2}\lambda_{k}\sigma^{\prime}_{k,j}\geq\left(m-(\delta+ 1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}\right)\cdot\frac{1}{\Delta+1}$ $$

By Lemma B.3 we have that with probability at least $1-2\tau$

$$ $O(\frac{n\cdot\delta}{\Delta})=O(\frac{n\cdot\delta}{\Delta})=o_{d}(1)$ $$

which means that

$$ $\left(m-(\delta+1)(n-1)\frac{m}{\Delta+1-2\delta(n-1)}\right)\cdot\frac{1}{ \Delta+1}>0$ $$

which means that $\lambda_{k}>0$, which means that $x_{k}$ is on the margin and hence $\phi(\theta,x_{k})=m$.
If $\mathbf{x}$ is not a training point, then

$$ $\displaystyle|\phi(\theta,x)|=\left|\sum_{j\in J_{+}}v_{j}\sum_{i\in[n]} \lambda_{i}y_{i}\sigma^{\prime}_{i,j}v_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}+1)+ \sum_{j\in J_{-}}v_{j}\sum_{i\in[n]}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}v_{j} (\mathbf{x}_{i}^{\top}\mathbf{x}+1)\right|$ $\displaystyle\leq\sum_{j\in J_{+}}\sum_{i\in[n]}\lambda_{i}\sigma^{\prime}_{i, j}v_{j}^{2}|\mathbf{x}_{i}^{\top}\mathbf{x}+1|+\sum_{j\in J_{-}}\sum_{i\in[n]} \lambda_{i}\sigma^{\prime}_{i,j}v_{j}^{2}|\mathbf{x}_{i}^{\top}\mathbf{x}+1|$ $\displaystyle\leq 2\cdot n\cdot(\delta_{x}+1)\cdot\frac{m}{\Delta+1-2\delta \cdot(n-1)}\leq 2\cdot n\cdot(\delta_{x}+1)\cdot\frac{m}{\Delta+1-2\delta_{x} \cdot(n-1)}=O(\frac{n\cdot m\cdot\delta_{x}}{\Delta})$ $$

Where in the second inequality we used Lemma B.1. By Lemma B.4 we have that with probability at least $1-2\tau$

$$ $\displaystyle 2\cdot n\cdot(\delta_{x}+1)\cdot\frac{m}{\Delta+1-2\delta_{x} \cdot(n-1)}=O(\frac{n\cdot m\cdot\delta_{x}}{\Delta})=m\cdot O(\frac{n\cdot \delta_{x}}{\Delta})=o_{d}(m)$ $$

∎

###### Remark B.5 (On the lower bound of the margin) .

From Thm. 4.2 we know that w.h.p. at least $\frac{n}{2}$ training points lie on the margin. Our loss function is

$$ $\ell(\Phi(\theta;\mathbf{x})\cdot y)=\log(1+e^{-y\cdot\Phi(\theta;\mathbf{x})})$ $$

so we have that

$$ $\displaystyle\frac{1}{2e}>L(\boldsymbol{\theta})=\frac{1}{n}\sum_{i=1}^{n}\ell (\Phi(\mathbf{x}_{i}),y_{i})\geq\frac{1}{n}\cdot\frac{n}{2}\cdot\log(1+e^{-m})$ $\displaystyle\Rightarrow\frac{1}{e}>\log(1+e^{-m})$ $$

Now we can extract a lower bound on $m$:

$$ $\displaystyle\log(1+e^{-m})<\frac{1}{e}\Rightarrow 1+e^{-m}<e^{e^{-1}} \Rightarrow e^{-m}<e^{e^{-1}}\Rightarrow m>\frac{1}{e}.$ $$

Same argument shows a similar bound for the exponential loss $\ell(x)=e^{-x}$.

###### Remark B.6 (On the upper bound of the margin) .

When training a neural network using gradient-based methods, the training process usually halts once the gradient is sufficiently small. When considering the exponential or logistic losses as in our case, a large margin implies small loss which in turn implies that the gradient is small. This suggests that making further progress when the margin is large becomes very difficult, and the training process is expected to halt. More formally, recall the logistic loss function (a similar argument implies the same result for the exponential loss):

$$ $\ell(\Phi(\boldsymbol{\theta};\mathbf{x})\cdot y)=\log(1+e^{-y\cdot\Phi( \boldsymbol{\theta};\mathbf{x})}).$ $$

This function is monotonically decreasing in the expression $y\Phi(\theta;\mathbf{x})$, so the loss is maximized for points that are on the margin, and we can upper bound

$$ $\left|\frac{\partial\ell(\Phi(\boldsymbol{\theta};\mathbf{x})\cdot y)}{ \partial\Phi(\boldsymbol{\theta};\mathbf{x})}\right|=\left|\frac{-y\cdot\Phi( \boldsymbol{\theta};\mathbf{x})\cdot e^{-y\cdot\Phi(\boldsymbol{\theta}; \mathbf{x})}}{1+e^{-y\cdot\Phi(\boldsymbol{\theta};\mathbf{x})}}\right|\leq \left|\frac{me^{-m}}{1+e^{-m}}\right|.$ $$

The above yields

$$ $\displaystyle\left|\frac{\partial L(\boldsymbol{\theta})}{\partial\boldsymbol{ \theta}_{j}}\right|\leq\frac{1}{n}\sum_{i=1}^{n}\left|\frac{\partial\ell(\Phi( \boldsymbol{\theta};\mathbf{x}_{i})\cdot y_{i})}{\partial\Phi(\boldsymbol{ \theta};\mathbf{x}_{i})}\right|\cdot\left|\frac{\partial\Phi(\boldsymbol{ \theta};\mathbf{x}_{i})}{\partial\boldsymbol{\theta}_{j}}\right|\leq \operatorname{poly}(d)\cdot\left|\frac{me^{-m}}{1+e^{-m}}\right|,$ $$

which allows us to bound the norm of the gradient by:

$$ $\|\nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta})\|\leq w\cdot\operatorname {poly}(d)\cdot\left|\frac{me^{-m}}{1+e^{-m}}\right|=\operatorname{poly}(d) \cdot\left|\frac{me^{-m}}{1+e^{-m}}\right|,$ $$

where $w$ denotes the width of the network which we assume to be polynomial in $d$ (since otherwise even making a prediction is computationally inefficient).

If, for example, the margin is $m=\log^{2}{d}=o(\sqrt{d})$, we get that

$$ $\|\nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta})\|\leq\operatorname{poly}( d)\left|\frac{\log^{2}{d}e^{-\log^{2}{d}}}{{1+e^{-\log^{2}{d}}}}\right|\leq \operatorname{poly}(d)\log^{2}{d}\cdot e^{-\log^{2}{d}}=\operatorname{poly}(d) \log^{2}{d}\cdot d^{-\log{d}},$ $$

which is smaller than any inverse polynomial in $d$. Hence, if we train for at most polynomially many iterations and label
all the data points correctly (i.e. the margin is strictly positive), then training effectively stops when the margin
reaches $O(\log^{2}{d})=o(\sqrt{d})$, and all the data points on the margin (which consist
of at least one point) will have an output of magnitude $O(\text{polylog}(d))$.

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Lemma B.4 .

###### Proof.

###### Proof Of Thm. 4.2 .

###### Remark B.5 (On the lower bound of the margin) .

###### Remark B.6 (On the upper bound of the margin) .

## Appendix C Proofs of distributions

In this section we prove the examples in section 4.

##### Uniform Distribution

For the uniform distribution on $\sqrt{d}\cdot\mathbb{S}^{d-1}$,the next lemma shows why is satisfies our assumptions.
The lemma is from Vardi et al. [], and we give a paraphrased version of it for the sake of the reader.

###### Lemma C.1 .

Let $\mathbf{x},\mathbf{y}\sim U(\sqrt{d}\cdot\mathbb{S}^{d-1})$. Then, with probability at least $1-d^{1-\ln(d)/4}=1-o_{d}(1)$ we have $|\langle\mathbf{x},\mathbf{y}\rangle|\leq\sqrt{d}\cdot\log{d}=o(d)$.

###### Remark C.2 .

For the uniform distribution, the training set size can be $n=o\left(\frac{\sqrt{d}}{\log{d}}\right)$ and $\tau~{}=~{}n^{2}~{}\cdot~{}d^{1-\ln(d)/4}=o_{d}(1)$

###### Lemma C.1 .

###### Remark C.2 .

##### Normal Distribution

As for the normal distribution, the following two lemmas prove its correctness

###### Lemma C.3 .

Let $\mathcal{N}=\mathcal{N}(\boldsymbol{\mu},I)$ be a normal distribution on $\mathbb{R}^{d}$. Let $\mathbf{x},~{}\mathbf{y}\sim\mathcal{N}(\mu,I)$. Assume that $\|\boldsymbol{\mu}\|^{2}=o(d)$.
then with probability at least

$$ $\displaystyle 1-2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\cdot\frac{d^{2\epsilon}} {\|\mu\|^{2}}\right)-\max\left(2\exp\left(-\frac{c_{1}}{2c_{2}^{2}}d^{\epsilon }\right),2\exp\left(-\frac{c_{1}}{4c_{2}^{4}}\cdot d^{2\epsilon-1}\right)\right)$ $\displaystyle-\max\left(2\exp\left(-\frac{c_{1}}{c_{2}^{4}}d^{2\epsilon-1} \right),2\exp\left(-\frac{c_{1}}{c_{2}^{2}}d^{\epsilon}\right)\right)$ $\displaystyle=1-o_{d}(1)$ $$

we have $|\langle\mathbf{x},\mathbf{y}\rangle|=o(d)$ and $\|\mathbf{x}\|^{2}=O(d)$, where $c_{1},~{}c_{2}$ are constants independent of $d$, and $\frac{1}{2}<\epsilon<1$.

###### Proof.

Let $\mathbf{x},\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma)$ independently.
W.l.o.g $\Sigma$ is diagonal, otherwise there is a unitary matrix $U$ such that $U\mathbf{x},U\mathbf{y}\sim\mathcal{N}(U\boldsymbol{\mu},U\Sigma U^{\top})$ where $U\Sigma U^{\top}$ is diagonal. Since $U$ is unitary we have that

$$ $\displaystyle\langle U\mathbf{x},U\mathbf{y}\rangle=\langle\mathbf{x},\mathbf{ y}\rangle$ $\displaystyle\|U\mathbf{x}\|=\|\mathbf{x}\|$ $$

So we can assume that $\Sigma$ is diagonal.
For comfort, we define some notations:

- •
The sub-Gaussian norm $\|\cdot\|_{\psi_{2}}$ for a sub-Gaussian random variable $\mathbf{x}$ is defined by
$\|\mathbf{x}\|_{\psi_{2}}=\inf\left\{t>0:E\left[\text{exp}\left(\frac{\mathbf{
x}^{2}}{t}\right)\right]\leq 2\right\}$
- •
The sub-exponential norm $\|\cdot\|_{\psi_{1}}$ for a sub-exponential random variable $\mathbf{x}$ is defined by
$\|\mathbf{x}\|_{\psi_{1}}=\inf\left\{t>0:E\left[\text{exp}\left(\frac{|\mathbf
{x}|}{t}\right)\right]\leq 2\right\}$

First, let us compute $E\left[\|\mathbf{x}\|^{2}\right]$. Note that

$$ $\|\mathbf{x}\|^{2}=\sum_{i=1}^{d}\mathbf{x}_{i}^{2}$ $$

, then $E[\mathbf{x}_{i}^{2}]=E[\mathbf{x}_{i}]^{2}+\text{Var}(\mathbf{x}_{i})=
\boldsymbol{\mu}_{i}^{2}+1$

$$ $E\left[\|\mathbf{x}\|^{2}\right]=E\left[\sum_{i=1}^{d}\mathbf{x}_{i}^{2}\right ]=\sum_{i=1}^{d}E[\mathbf{x}_{i}^{2}]=\sum_{i=1}^{d}\text{Var}(\mathbf{x}_{i}) +\boldsymbol{\mu}_{i}^{2}=\text{tr}(I)+\|\boldsymbol{\mu}\|^{2}=O(d)$ $$

Note that we can write $\mathbf{x}$ as $\mathbf{x}=\boldsymbol{\mu}+\mathbf{z}$ where $\mathbf{z}\sim\mathcal{N}(0,I)$.
We can write $\|\mathbf{x}\|^{2}=\|\boldsymbol{\mu}+\mathbf{z}\|^{2}=\|\boldsymbol{\mu}\|^{2
}+2|\boldsymbol{\mu}^{\top}\mathbf{z}|+\|\mathbf{z}\|^{2}$.
So we need to upper bound

$$ $\|\mathbf{x}\|^{2}-E\left[\|\mathbf{x}\|^{2}\right]=\|\boldsymbol{\mu}\|^{2}+2 \boldsymbol{\mu}^{\top}\mathbf{z}+\|\mathbf{z}\|^{2}-\|\boldsymbol{\mu}\|^{2}- 2\boldsymbol{\mu}^{\top}E[\mathbf{z}]-E\left[\|\mathbf{z}\|^{2}\right]=\| \mathbf{z}\|^{2}-E\left[\|z\|^{2}\right]+2\boldsymbol{\mu}^{\top}\mathbf{z}$ $$

Where in the last equality we used the fact that $E[\mathbf{z}]=0$

From the union bound we get that for every $t>0$

$$ $\displaystyle\Pr\left[\left|\mathbf{x}^{2}-E[\|\mathbf{x}\|^{2}]\right|>t \right]=\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]+2\boldsymbol{ \mu}^{\top}\mathbf{z}\right|>t\right]$ $\displaystyle\leq\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]\right |+2\left|\boldsymbol{\mu}^{\top}\mathbf{z}\right|>t\right]$ $\displaystyle\leq\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]\right |>\frac{t}{2}\right]+\Pr\left[2\left|\boldsymbol{\mu}^{\top}\mathbf{z}\right|> \frac{t}{2}\right]$ $$

Let us bound the first term. To do so, we use Hanson-Wright Inequality ([] Theorem 6.2.1).

$$ $\displaystyle\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]\right|> \frac{t}{2}\right]\leq 2\text{exp}\left[-c_{1}\min\left(\frac{t^{2}}{4\cdot K^ {4}\cdot d},\frac{t}{2\cdot K^{2}}\right)\right]$ $$

Where $K=\max_{i}\|\mathbf{x}_{i}\|_{\psi_{2}}=c_{2}$ and $c_{1},~{}c_{2}$ are constant independent of $d$.
We set $t=d^{\epsilon}$ for $\frac{1}{2}<\epsilon<1$.

###### Lemma C.3 .

###### Proof.

##### Case 1 - t 2 4 ⋅ K 4 ⋅ d superscript 𝑡 2 ⋅ 4 superscript 𝐾 4 𝑑 \frac{t^{2}}{4\cdot K^{4}\cdot d} divide start_ARG italic_t start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG 4 ⋅ italic_K start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT ⋅ italic_d end_ARG is the minimum

$$ $\displaystyle\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]\right|> \frac{t}{2}\right]\leq 2\exp\left(-c_{1}\frac{d^{2\epsilon}}{c_{2}^{4}\cdot 4 \cdot d}\right)=2\exp\left(-\frac{c_{1}}{4\cdot c_{2}^{4}}\cdot d^{2\epsilon-1 }\right)=o_{d}(1)$ $$

##### Case 2 - t 2 ⋅ K 2 𝑡 ⋅ 2 superscript 𝐾 2 \frac{t}{2\cdot K^{2}} divide start_ARG italic_t end_ARG start_ARG 2 ⋅ italic_K start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG is the minimum

$$ $\Pr\left[\left|\|\mathbf{z}\|^{2}-E[\|\mathbf{z}\|^{2}]\right|>\frac{t}{2} \right]\leq 2\exp\left(-c_{1}\frac{d^{\epsilon}}{2\cdot c_{2}^{2}}\right)=o_{d }(1)$ $$

Now we upper bound the term $\Pr\left[2|\boldsymbol{\mu}^{\top}\mathbf{z}|>\frac{t}{2}\right]=\Pr\left[|
\boldsymbol{\mu}^{\top}\mathbf{z}|>\frac{t}{4}\right]$.
From General Hoeffding’s inequality ([] Theorem 2.6.3) we get that

$$ $\displaystyle\Pr\left[|\boldsymbol{\mu}^{\top}\mathbf{z}|>\frac{t}{4}\right] \leq 2\exp\left(-\frac{c_{1}t^{2}}{16\cdot K^{2}\cdot\|\boldsymbol{\mu}\|^{2}}\right)$ $$

Where $K=\max_{i}\|\mathbf{x}_{i}\|_{\psi_{2}}=c_{2}$ and $c_{1},~{}c_{2}$ are constant independent of $d$.
Putting it all together we get

$$ $\displaystyle\Pr\left[|\boldsymbol{\mu}^{\top}\mathbf{z}|>\frac{t}{4}\right] \leq 2\exp\left(-\frac{c_{1}t^{2}}{16\cdot K^{2}\cdot\|\boldsymbol{\mu}\|^{2}}\right)$ $\displaystyle=2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\frac{d^{2\epsilon}}{\| \boldsymbol{\mu}\|^{2}}\right)=2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\frac{d^{2 \epsilon}}{\|\boldsymbol{\mu}\|^{2}}\right)=o_{d}(1)$ $$

Where in last inequality we used the fact that $2\epsilon>1$.

All in all, we showed that $E[\|\mathbf{x}\|^{2}]=O(d)$ and that with probability

$$ $1-\max\left(2\exp\left(-\frac{c_{1}}{4c_{2}^{2}}\cdot d^{2\epsilon-1}\right),2 \exp\left(-\frac{c_{1}}{2c_{2}^{2}}\cdot d^{\epsilon}\right)\right)-2\exp\left (-\frac{c_{1}}{16c_{2}^{2}}\frac{d^{2\epsilon}}{\|\mu\|^{2}}\right)=1-o_{d}(1)$ $$

we have that

$$ $\left|\|\mathbf{x}\|^{2}-E[\|\mathbf{x}\|^{2}]\right|<d^{\epsilon}=o(d)$ $$

and specifically $\|\mathbf{x}\|^{2}=O(d)$

Since $\mathbf{x}$ is normal, each $\mathbf{x}_{i}$ is sub-Gaussian (and the same for $\mathbf{y}$).
Let us have a look at $\mathbf{x}^{\top}\mathbf{y}$: Since $\mathbf{x}_{i},\mathbf{y}_{i}$ are sub-Gaussians, $\mathbf{x}_{i}\cdot\mathbf{y}_{i}$ is sub-exponential ([], Lemma 2.7.7). It is also known that a sum of sub-exponential random variables is in itself sub-exponential, so we get that

$$ $\mathbf{x}^{\top}\mathbf{y}=\sum_{i=1}^{d}x_{i}y_{i}$ $$

is sub-exponential. By the centering lemma ([] Exercise 2.7.10), $x_{i}y_{i}-E[x_{i}y_{i}]=x_{i}y_{i}-\mu_{i}^{2}$ is also sub-exponential, with mean zero. We can use Bernstein’s inequality ([], Theorem 2.8.1) to get:

$$ $\displaystyle\Pr\left[\left|\mathbf{x}^{\top}\mathbf{y}-\|\boldsymbol{\mu}\|^{ 2}\right|>t\right]=\Pr\left[\left|\sum_{i=1}^{d}x_{i}y_{i}-\mu_{i}^{2}\right|> t\right]$ $\displaystyle\leq 2\text{exp}\left[-c_{1}\cdot\min\left(\frac{t}{\max_{i}{\|x_ {i}y_{i}-\mu_{i}\|_{\psi_{1}}}},\frac{t^{2}}{\sum_{i=1}^{d}\|x_{i}y_{i}-\mu_{i }\|_{\psi_{1}}^{2}}\right)\right]$ $\displaystyle\leq 2\text{exp}\left[-c_{1}\cdot\min\left(\frac{t}{\max_{i}{\|x_ {i}y_{i}\|_{\psi_{1}}}},\frac{t^{2}}{\sum_{i=1}^{d}\|x_{i}y_{i}\|_{\psi_{1}}^{ 2}}\right)\right]$ $\displaystyle\leq 2\text{exp}\left[-c_{1}\cdot\min\left(\frac{t}{\max_{i}{\|x_ {i}\|_{\psi_{2}}\|y_{i}\|_{\psi_{2}}}},\frac{t^{2}}{\sum_{i=1}^{d}\|x_{i}\|_{ \psi_{2}}^{2}\|y_{i}\|_{\psi_{2}}^{2}}\right)\right]$ $\displaystyle=2\text{exp}\left[-c_{1}\cdot\min\left(\frac{t}{c_{2}^{2}},\frac{ t^{2}}{\sum_{i=1}^{d}c_{2}^{4}}\right)\right]$ $$

Where $c_{1},~{}c_{2}$ are constants that do not depend on the dimension $d$. In the second inequality we used the fact that $\|\mathbf{x}-E[\mathbf{x}]\|_{\psi_{1}}\leq\|\mathbf{x}\|_{\psi_{1}}$ ([] Exercise 2.7.10) and in the third inequality we used the fact that $\|x_{i}y_{i}\|_{\psi_{1}}\leq\|x_{i}\|_{\psi_{2}}\|y_{i}\|_{\psi_{2}}$ ([] Lemma 2.7.7).
Setting $t=d^{\epsilon}$ for some $\frac{1}{2}<\epsilon<1$ we get:

##### Case 1 - t c 2 2 𝑡 superscript subscript 𝑐 2 2 \frac{t}{c_{2}^{2}} divide start_ARG italic_t end_ARG start_ARG italic_c start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG is the minimum

$$ $\Pr[\left|\mathbf{x}^{\top}\mathbf{y}-\|\boldsymbol{\mu}\|^{2}\right|>d^{ \epsilon}]\leq 2\text{exp}\left[-c_{1}\cdot\frac{d^{\epsilon}}{c_{2}^{2}} \right]=o_{d}(1)$ $$

And since both $\|\boldsymbol{\mu}\|^{2}=o(d)$ and $d^{\epsilon}=o(d)$ we get that w.h.p $\mathbf{x}^{\top}\mathbf{y}=o(d)$

##### Case 2 - t 2 ∑ i = 1 d c 2 4 superscript 𝑡 2 superscript subscript 𝑖 1 𝑑 superscript subscript 𝑐 2 4 \frac{t^{2}}{\sum_{i=1}^{d}c_{2}^{4}} divide start_ARG italic_t start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT italic_c start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT end_ARG is the minimum

$$ $\displaystyle\Pr[\left|\mathbf{x}^{\top}\mathbf{y}-\|\boldsymbol{\mu}\|^{2} \right|>d^{\epsilon}]\leq 2\text{exp}\left[-c_{1}\cdot\frac{d^{2\epsilon}}{c_{ 2}^{4}\cdot d}\right]$ $\displaystyle=2\text{exp}\left[-\frac{c_{1}}{c_{2}^{4}}\cdot d^{2\epsilon-1} \right]=o_{d}(1)$ $$

Using the union bound, with probability at least

$$ $\displaystyle 1-2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\cdot\frac{d^{2\epsilon}} {\|\mu\|^{2}}\right)-\max\left(2\exp\left(-\frac{c_{1}}{2c_{2}^{2}}d^{\epsilon }\right),2\exp\left(-\frac{c_{1}}{4c_{2}^{4}}\cdot d^{2\epsilon-1}\right)\right)$ $\displaystyle-\max\left(2\exp\left(-\frac{c_{1}}{c_{2}^{4}}d^{2\epsilon-1} \right),2\exp\left(-\frac{c_{1}}{c_{2}^{2}}d^{\epsilon}\right)\right)$ $\displaystyle=1-o_{d}(1)$ $$

we have $|\langle\mathbf{x},\mathbf{y}\rangle|=o(d)$ and $\|\mathbf{x}\|^{2}=O(d)$.
∎

###### Remark C.4 .

we want $n\cdot|\mathbf{x}^{\top}\mathbf{y}|=o(d)$ to hold, so

$$ $n\cdot|\mathbf{x}^{\top}\mathbf{y}|\leq n\cdot(\|\mu\|^{2}+d^{\epsilon})=o(d) \Rightarrow n=\frac{o(d)}{\|\mu\|^{2}+d^{\epsilon}}$ $$

###### Lemma C.5 .

Let $\mathcal{N}=\mathcal{N}(\boldsymbol{\mu},I)$ be a normal distribution on $\mathbb{R}^{d}$. Let $\mathbf{x},~{}\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu},I)$. Assume that $\|\boldsymbol{\mu}\|^{2}=o(d)$, and $n=\frac{o(d)}{\|\boldsymbol{\mu}\|^{2}+d^{\epsilon}}$ for $\frac{1}{2}<\epsilon<1$.
Denote

$$ $\displaystyle k=2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\cdot\frac{d^{2\epsilon}} {\|\mu\|^{2}}\right)+\max\left(2\exp\left(-\frac{c_{1}}{2c_{2}^{2}}d^{\epsilon }\right),2\exp\left(-\frac{c_{1}}{4c_{2}^{4}}\cdot d^{2\epsilon-1}\right)\right)$ $\displaystyle+\max\left(2\exp\left(-\frac{c_{1}}{c_{2}^{4}}d^{2\epsilon-1} \right),2\exp\left(-\frac{c_{1}}{c_{2}^{2}}d^{\epsilon}\right)\right)$ $$

where $c_{1},~{}c_{2}$ are the constants from Lemma C.3.
Let $\tau=k\cdot n$.
Then with probability at least $1-\frac{\tau}{n^{2}}$ have $|n\cdot\langle\mathbf{x},\mathbf{y}\rangle|=o(d)$ and $\|\mathbf{x}\|^{2}=O(d)$. In particular, those $n$ and $\tau$ satisfy Assumption 4.1.

###### Proof.

From Lemma C.3 we know that with probability at least $1-k$ we have that $|\langle\mathbf{x},\mathbf{y}\rangle|\leq\|\mu\|^{2}+d^{\epsilon}$, so with probability at least $1-k$ we have that $n\cdot|\langle\mathbf{x},\mathbf{y}\rangle|=\frac{o(d)}{\|\mu\|^{2}+d^{
\epsilon}}\cdot|\langle\mathbf{x},\mathbf{y}\rangle|\leq o(d)$. We also know from Lemma C.3 that with probability at least $1-k$ we have that $\|\mathbf{x}\|^{2}=\Omega(d)$. Setting $\tau=k\cdot n^{2}=o_{d}(1)$ completes the proof.
∎

###### Remark C.4 .

###### Lemma C.5 .

###### Proof.

##### Mixture of k 𝑘 k italic_k Gaussians

We prove the case where we have 2 Gaussians, but the proof is similar for any number of Gaussians.

###### Lemma C.6 .

Let $\mathcal{N}=\pi\mathcal{N}(\boldsymbol{\mu}^{(1)},I)+(1-\pi)\mathcal{N}(
\boldsymbol{\mu}^{(2)},I)$ where $0\leq\pi\leq 1$ be a mixture of normal distributions on $\mathbb{R}^{d}$. Assume the following:

- •
$\|\boldsymbol{\mu}^{(1)}\|^{2}=o(d)$, $\|\boldsymbol{\mu}^{(2)}\|^{2}=o(d)$
- •
$n=\frac{o(d)}{\max(\|\mu^{(1)}\|^{2},\|\mu^{(2)}\|^{2})+d^{\epsilon}}$ for $\frac{1}{2}<\epsilon<1$.
- •
$k$ defined as in Lemma C.5
- •
$\tau=k\cdot n^{2}$

then with probability at least $1-\frac{\tau}{n^{2}}$ we have $n\cdot|\langle\mathbf{x},\mathbf{y}\rangle|=o(d)$ and $\|\mathbf{x}\|^{2}=O(d)$

###### Proof.

Let $\mathbf{x},\mathbf{y}\sim\pi\mathcal{N}(\boldsymbol{\mu}^{(1)},I)+(1-\pi)
\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$ where $0\leq\pi\leq 1$. Let us compute $E\left[\|\mathbf{x}\|^{2}\right]$.
We can think of $\mathbf{x}$ as

$$ $\mathbf{x}=\begin{cases}\mathbf{x}_{1},&\text{with probability }\pi\\ \mathbf{x}_{2},&\text{with probability }1-\pi\end{cases}$ $$

where $\mathbf{x}_{1}\sim\mathcal{N}(\boldsymbol{\mu}^{(1)},I)$ and $\mathbf{x}_{2}\sim\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$. From the law of total expectation we get

$$ $E[\|\mathbf{x}\|^{2}]=\pi E[\|\mathbf{x}_{1}\|^{2}]+(1-\pi)E[\|\mathbf{x}_{2} \|^{2}]$ $$

and from C.5 we get

$$ $E[\|\mathbf{x}\|^{2}]=\pi\cdot\left(\|\boldsymbol{\mu}^{(1)}\|^{2}+\text{tr}(I )\right)+(1-\pi)\cdot\left(\|\boldsymbol{\mu}^{(2)}\|^{2}+\text{tr}(I)\right)= O(d)$ $$

Denote $A=\{\mathbf{x}:\left|\|\mathbf{x}\|^{2}-E[\|\mathbf{x}\|]^{2}\right|>d^{
\epsilon}\}$ where $\frac{1}{2}<\epsilon<1$.
From the law of total probability we get:

$$ $\displaystyle p(A)=p(A|\mathbf{x}=\mathbf{x}_{1})\cdot\pi+p(A|\mathbf{x}= \mathbf{x}_{2})\cdot(1-\pi)$ $\displaystyle=1-\max\left(2\exp\left(-\frac{c_{1}}{4c_{2}^{2}}\cdot d^{2 \epsilon-1}\right),2\exp\left(-\frac{c_{1}}{2c_{2}^{2}}\cdot d^{\epsilon} \right)\right)-2\exp\left(-\frac{c_{1}}{16c_{2}^{2}}\frac{d^{2\epsilon}}{\|\mu \|^{2}}\right)=1-o_{d}(1)$ $$

and specifically, $\|\mathbf{x}\|^{2}=O(d)$.

Now, let us show that $E[\mathbf{x}^{\top}\mathbf{y}]=o(d)$:

$$ $\displaystyle E[\mathbf{x}^{\top}\mathbf{y}]=E[\mathbf{x}^{\top}]E[\mathbf{y}] =\left(\pi\boldsymbol{\mu}^{(1)}+(1-\pi)\boldsymbol{\mu}^{(2)}\right)^{\top} \left(\pi\boldsymbol{\mu}^{(1)}+(1-\pi)\boldsymbol{\mu}^{(2)}\right)$ $\displaystyle=\pi^{2}\|\boldsymbol{\mu}^{(1)}\|^{2}+2\pi(1-\pi){\boldsymbol{ \mu}^{(1)}}^{\top}\boldsymbol{\mu}^{(2)}+(1-\pi)^{2}\|\boldsymbol{\mu}^{(2)}\| ^{2}$ $\displaystyle=\pi^{2}o(d)+2\pi(1-\pi)o(d)+(1-\pi)^{2}o(d)=o(d)$ $$

We divide the proof into 4 cases.

Case 1: $\mathbf{x},~{}\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu}^{(1)},I)$

In this case, both points came from the same normal distribution, which we have already proven.

Case 2: $\mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu}^{(1)},I)$ and $\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$

For every $i$ we have that $x_{i}$ and $y_{i}$ are sub-Gaussians and $\|x_{i}\|_{\psi_{2}}\leq c,~{}~{}\|y_{i}\|_{\psi_{2}}\leq c$, so we can use the same logic as in Lemma C.3 do prove that $\mathbf{x}^{\top}\mathbf{y}=o(d)$ with the same probability.

Case 3: $\mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$ and $\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu}^{(1)},I)$

Same as case 2.

Case 4: $\mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$ and $\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu}^{(2)},I)$

Same as case 1

Similar to C.4, with probability at least $1-k$ we have that

$$ $n\cdot\langle\mathbf{x},\mathbf{y}\rangle\leq n\cdot\max(\|\mu^{(1)}\|^{2},\| \mu^{(2)}\|^{2})+d^{\epsilon}=o(d)\Rightarrow n=\frac{o(d)}{\max\left\{\| \boldsymbol{\mu}^{(1)}\|^{2},\|\boldsymbol{\mu}^{(2)}\|^{2}\right\}+d^{ \epsilon}}$ $$

and also that $\|\mathbf{x}\|^{2}=\Omega(d)$. Setting $\tau=k\cdot n^{2}=o_{d}(1)$ completes the proof.
∎

###### Lemma C.6 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 1
questions: 1. Theorem 2.1 specifically mentions that the gradient flow in a homogenous ReLU NN _eventually converges_  (i.e., at $t\to\infty$) to a stationary point. 
  - Line 146: What does gradient flow over a binary classification set formally mean?
  - Line 154: I invite the authors to explain why it is natural to assume that the existence of a point of convergence automatically implies that the function has converged. It might be a fine assumption for experimentally focused papers, but assuming convergence in a theoretical setting needs to be well motivated.
  - Does the above issue not mean that Assumption 2.1 is an extremely strong condition for a 2-layer NN? 

2. I think that the proof of Theorem 3.1 is incorrect (or at the very least missing certain assertions).
  - it is stated that the real-valued function $\phi(\theta; x_1)$ cannot be the zero function because for all $i\in[n]$, $y_i\phi(\theta;x_i)\geq m$, where $m:=\min_i|{\phi(\theta;x_i)}|$, and therefore can well be $0$. The authors are therefore assuming another implicit condition, i.e., the margin should always be positive. This makes Assumption 2.1 even more untenable for 2-layer NNs in the context of Theorem 2.1.
  - Suppose $\phi(\theta; x_1)>0$. Since $\phi$ is a real-valued function, I am not understanding why $y_1\Phi(\theta;x_1)$ cannot lie in between 0 and 1. Hence the rest of the implications in the proof do not follow.
   - The crux of Assumption 2.1 should be clearly stated in the abstract of the paper and the introduction of the paper in some form.
As it stands, I am not convinced that even in the univariate case, the data can be recovered.

3. In Line 309, the authors state: "In very high dimensional settings, under many commonly used data distributions, we have that the dataset is almost orthogonal with high probability." This forms the basis for Assumption 4.1, which is critical to the rest of the proofs. This is the first time the authors have mentioned the ability to perform membership inference or data reconstruction w.r.t. well-behaved distributions. This is highly unusual and subtracts from the blackbox nature of membership inference or data reconstruction attacks. 
   - For Assumption 4.1 to be considered _valid_, I would prefer if the authors included a discussion addressing the above concern.
   - The crux of Assumption 4.1 should be clearly stated in the abstract of the paper and the introduction of the paper in some form.

4. Most of the main theorems are missing a high level overview from the main paper. The authors should include a proof sketch of Theorems 3.2 and 3.3.

5. Line 474: I invite the authors to clarify the following statement - "in this section, we conducted a few experiments focusing on the membership inference problem, and observed that while our theoretical results’ assumptions do not necessarily hold, their implications are nevertheless still valid." Does this not mean that weaker assumptions would have sufficed? 


## Typos and Grammatical mistakes
Line 231: "be two adjacent intervals which none of them is constant on the margin" - the authors should rewrite this sentence.
soundness: 2
strengths: The overall question is interesting and would certainly be of interest to the community at large. The main contribution of this paper is to show there is _some_ theoretical basis for the literature on data reconstruction and membership inference attacks. However, the results in this paper are somewhat lacklustre for reasons outlined in the next two sections.
summary: The paper tries to show provable guarantees for data reconstruction and membership inference for nonconvex activation functions in shallow Neural networks.
weaknesses: The paper is lacking in the areas of exposition and technical details. Concepts which are central to the paper such as Gradient flow, Data Reconstruction, and Membership Inference are never formally defined, which makes the paper inaccessible to all but a very niche audience.

I have listed a set of points in the next section for the authors to clarify. In the interest of transparency, I am clearly stating my position here:
  - The paper needs more work especially in exposition (see above). At this time it reads like a first draft. For example, the assumptions and the proofs are tightly coupled with each other, without a clear basis for either. Simply based on this issue, I am recommending rejection for the paper.
  - I am open to changing my score in case I have misunderstood something regarding the assumptions. However, I again stress that such clarifications should have been in the paper to begin with, and it will probably not improve my score by a lot.

*Remark*: Judging by the previous works of Haim et al. (2023) etc. it seems to be that it is indeed possible to reconstruct data or perform MI in the settings considered. I believe that the paper stands to benefit a lot if the focus of the theoretical setting would have been to investigate the precise nature of the assumptions that allowed these attacks to take place.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 2
questions: 1) In the proof of Theorem 4.2, in lines 117-118 it is not clear to me how this follows without a high probability statement. The theorem states that with probability $1- \tau$ you have the training points are on the margin, and I believe some high probability argument like Lemma B.3 is implicit in the statement (and would be great to state more explicitly in the proof for completeness).


2) Similarly, at the end of the proof of Theorem 4.2, I believe you mean the final equality occurs with probability $1- 2\tau$ not $1 - \tau$.


3) In the proof of Theorem 3.2 and the existence of $x_1$, it is not clear to me how it not existing would imply the break points were the same with the stated logic. Could we not have $w_{i-1}$ be positive and hence it is determined by the margin points after the breakpoint, but $w_{i}$ can be negative and hence determined by the margin point below its breakpoint (which by assumption would be $0$). In this way they are still different given that $x_2$ exists, which is necessary as there is at least one margin point? What seems to me to be the correct proof is now noting that the breakpoint for $i+1$ would be the same as either $i$ or $i-1$, leading to a contradiction and hence needing $x_1$ to exist.


4) In Line 143 I believe you mean to say “for the sake succinctness” not “completeness” as you are summarizing the statement?
soundness: 3
strengths: 1) As far as I am aware, the first general results of effective privacy attacks on neural networks, as opposed to empirical results known for specific datasets and models.
2) Surfacing assumptions required, which future work can weaken; the paper already discusses how the dimensionality assumptions may be weakened (given empirical evidence).
3) I believe the techniques in the proofs for the attacks to be novel to the private ML community
summary: This paper describes how 2-layer neural networks have provably effective privacy attacks. The reconstruction attack they instantiate assumes complete optimization to the implicit bias solution and then analyzes the implication of the KKT conditions in cases to deduce high probability sets of training datapoints. Notably this algorithm does not require any further assumptions on the dataset, and hence presents a strong attack. The membership inference attacks impose certain restrictions on the data generating distribution, which I will summarize as “being sufficiently spread out in direction and magnitude” (i.e., orthogonal with high probability, and high magnitude relative to dimension), and is the case for common distributions. All together, these are (to the best of my knowledge) the first results on general privacy attacks against deep neural networks, and I believe also presents questions for future empirical and theoretical study.
weaknesses: 1) I think the presentation could make it more explicit what the contributions of the theory is to the broader privacy community. I attribute this mainly to the use of vague language regarding the assumptions in the main text, such as in line 45 which states “certain settings with varying assumptions”. One could instead highlight specific assumptions (e.g., dimensionality for membership inference or the data-independence of the reconstruction attacks) and contrast them with what is already known empirically.

2) On presentation, I had some questions for the proofs as presented, which I believe are resolvable but I list them below in the Questions section.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: - The curve in Figure 1 (a) is not very smooth. If you run multiple experiments and report the average, will it be better?
- Loss is a popular metric for membership inference attack. In general trained samples shall have smaller losses than test samples. Can you explain a bit more on the relationship between loss and margin?
soundness: 2
strengths: This paper studies an important problem of privacy in neural networks. Theoretical analysis are provided. Experiments are conducted to support the theoretical claims. Source codes are provided.
summary: This paper studies the privacy attack on 2-layer Relu activated neural network. Under the assumption that the model converges to a point that satisfies the KKT condition, this paper shows 2 attacks: 1) for the univariate case, this paper is able to recover a part of the training samples from the weights; 2) when the number of training samples $n$ is much smaller than the dimension $d$ of the training data, the output of the neural network can serve as membership inference attack. Experiments show that even n is as large as d, the membership inference attack can still work empirically.
weaknesses: My biggest concern is that the novelty seems to be limited. 
- It is well known [1] that overparameterized neural networks can memorize training input, and it is not surprising that the training input is encoded in the model weights in some way. Actually, empirical study has shown that it is possible to reconstruct training data from model weights [2] and even model updates [3]. From this perspective, the contribution of this work seems to be limited at providing a theoretical proof. However, the proposed attack only work for the univariate case, which means the neural network is essentially a piece-wise linear function. It is not clear how this work can inspire training data reconstruction for general functions.
- For the membership inference attack, in the setting where $n \ll d$, we can think that the model is able to memorize the label ($\pm 1
$) for all the $n$ samples that are seen during training, but the model does not have any idea for the remaining input , which is at least a $d-n$-dimensional subspace. So it is expected that the model output can serve as an indicator for membership. The condition on $n,d$ and the assumption of almost orthogonal training data seem to be quite limited. It is not clear if the proposed theory can help understand the membership inference attack in general case, e.g. [4].

[1] Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-parameterization." International conference on machine learning. PMLR, 2019.

[2] Haim, Niv, et al. "Reconstructing training data from trained neural networks." Advances in Neural Information Processing Systems 35 (2022): 22911-22924.

[3] Wang, Zihan, Jason Lee, and Qi Lei. "Reconstructing training data from model gradient, provably." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[4] Sablayrolles, Alexandre, et al. "White-box vs black-box: Bayes optimal strategies for membership inference." International Conference on Machine Learning. PMLR, 2019.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: I asked multiple questions in the weaknesses section. I am happy to reconsider my score during the discussion time.
soundness: 2
strengths: The topic of data reconstruction gained reasonable popularity recently, and it is true that its theoretical understanding is lacking behind its practice. A better theoretical control of the current recovery schemes can be beneficial for the fields of privacy and security and beyond. Thus, in my opinion, the research question addressed by this paper is well motivated.

The paper implicitely tackles deep questions on the implicit bias of gradient descent algorithms on classification tasks, as the ratio of training points lying on the margin as a function of the data dimensionality (see Fig. 1a), or the output of the model at test time (see Fig. 1bc), which can be associated to the generalization error of the model itself.
summary: This paper looks at the problem of data reconstruction, and especially at the setting empirically discussed in [1]. The goal of the paper is to theoretically prove that reconstruction attacks are provably possible in some settings. The paper looks at data reconstruction in the univariate case (samples are one-dimensional), and also discusses membership inference attacks in the multivariate setting. The paper concludes with some experimental evidence beyond the setting covered by the technical assumptions used in the section on the membership inference attacks.

[1] https://arxiv.org/abs/2206.07758
weaknesses: First, the paper remarks multiple times that this is the first step towards understanding theoretically reconstruction attacks. This is false [2, 3]. Notice that these works (and probably other works I am not aware of) consider a different setting than the one presented in this paper, but (at least) equally interesting. I invite the authors to rephrase their narrative (see, e.g., "first step" in line 32 and "all previous works are empirical" in line 61) and to tune down this side of the contribution. On a minor level, I would invite the authors to remark in introduction that the idea of using the implicit bias of gradient descent on ReLU networks to understand data recovery is not new (see second paragraph of the introduction), as it is the core motivating idea behind the main paper the authors refer to [1].

Another weakness, in my opinion, is the high number of strong and implicit assumptions. The paper implicitely uses Theorem 2.1 from previous work to define its Assumption 2.1. This theorem assumes the loss to be small at some time, which I believe is not necessarily true (maybe the data / number of parameters have to respect some other explicit assumption), and therefore hides in which exact settings Assumption 2.1 is reasonable to be made. Can the authors elaborate, maybe in light of the results obtained in previous work on Theorem 2.1?

Another quite strong assumption made in this work is the implicit upper-bound on the number of training samples deriving from Assumption 4.1 (which translates to $n \ll \sqrt d$ in the case of the sphere). I wonder if with this number of data, it might be impossible for the model to successfully learn the task, as the output of the model at test time will approach 0, justifying why the results in Section 4 work (see for example Corollary 4.3, where at test time the outputs are small with high probability). To verify this, it would be helpful if the authors could also plot the test accuracy of the trained model in Figure 1, which will most likely decrease with $d$ as well. If it turns out that the attack success is strongly related with the test error of the model, it would be an important point to raise during the discussion.

Regarding the univariate case, I would also say it is hard to tell the effective predictive power of the results for more realistic scenarios. This setting might be qualitatively very different from the high dimensional case, and it is also difficult to evaluate how strong is the assumption that the attacker has knowledge of the margin (see line 190). Besides, I found section 3.2 a bit hard to parse at first, and I see the same problem I raised above on the implicit assumptions: what does it mean that $\Phi(\theta, x)$ is a local minimum of Eq. (1)? In which space? Is this stronger than Assumption 2.1? As the authors do not seem to be lacking in space, I would recommend adding an additional Figure in this section, where the intuition behind their results is depicted as a plot (for example, a uniivariate plot of  $\Phi(\theta, x)$ and the corresponding intersections with the margin). On top of this, it would be very helpful a brief discussion on why the results are intuitively true (see, for example, Theorem 3.2, where the reasons behind thesis seem a bit obscure).


[2] https://arxiv.org/abs/2201.04845

[3] https://arxiv.org/abs/2212.03714

Meta-review: This paper studies the privacy attack on 2-layer Relu activated neural network. Under the assumption that the model converges to a point that satisfies the KKT condition, this paper shows 2 attacks: 1) for the univariate case, this paper is able to recover a part of the training samples from the weights; 2) when the number of training samples is much smaller than the dimension of the training data, the output of the neural network can serve as membership inference attack. Experiments show that even n is as large as d, the membership inference attack can still work empirically.

This paper is on the borderline. I agree with the two of the reviewers regarding abstaining from full acceptance, due to the difficulty in the generalization capabilities of the models and their relevance for broader settings.

Decision: Reject