Unlocking the Theory Behind Scaling 1-Bit Neural Networks

## Abstract

Recently, 1-bit Large Language Models (LLMs) have emerged, showcasing an impressive combination of efficiency and performance that rivals traditional LLMs. Research by WMD + [ 91 ], MWM + [ 70 ] indicates that the performance of these 1-bit LLMs progressively improves as the number of parameters increases, hinting at the potential existence of a Scaling Law for 1-bit Neural Networks . In this paper, we present the first theoretical result that rigorously establishes this scaling law for 1-bit models. We prove that, despite the constraint of weights restricted to { − 1 , + 1 } 1 1 \{-1,+1\} { - 1 , + 1 } , the dynamics of model training inevitably align with kernel behavior as the network width grows. This theoretical breakthrough guarantees convergence of the 1-bit model to an arbitrarily small loss as width increases. Furthermore, we introduce the concept of the generalization difference, defined as the gap between the outputs of 1-bit networks and their full-precision counterparts, and demonstrate that this difference maintains a negligible level as network width scales. Building on the work of KMH + [ 51 ] , we conclude by examining how the training loss scales as a power-law function of the model size, dataset size, and computational resources utilized for training. Our findings underscore the promising potential of scaling 1-bit neural networks, suggesting that int1 could become the standard in future neural network precision.

## 1 Introduction

Large-scale neural networks, particularly Large Language Models (LLMs) [, ] and Large Multimodel Models (LMMs) [, ], are becoming increasingly relevant to our day-to-day lives, finding a huge variety of applications in both the workplace and at home [, ]. However, it is expensive to deploy and run these models due to their substantial computational requirements, large memory footprints, and energy consumption [, , ]. This is especially true for resource-constrained environments, such as mobile devices, edge computing, or companies with limited infrastructure [, , ]. To make these models more efficient and accessible, quantization techniques are used, which reduce the precision of the model’s parameters (such as weights and activations) from floating-point numbers to lower-bit representations (e.g., 8-bit or even lower) [, , , , ]. Quantization reduces the memory and computational costs of inference, enabling faster processing with less energy, while maintaining a comparable level of performance. This optimization allows language models to be more practical, scalable, and sustainable for widespread use across various platforms [, , ].

In particular, quantization techniques could be primarily divided into two methods: Post-Training Quantization (PTQ) [, , ] and Quantization-Aware Training (QAT) [, , ]. PTQ methods, including uniform and non-uniform quantization, conveniently convert pre-trained model weights and activations to lower-bit representations post-training. However, this leads to accuracy loss, especially in lower precision, as the model is not optimized for these quantized representations and significant shifts in weight distribution occur []. The alternative, Quantization-Aware Training (QAT), incorporates quantization during training, allowing the model to fine-tune and adapt its parameters to the quantized representation, compensating for quantization errors. Therefore, compared to PTQ, QAT maintains higher accuracy and robustness even in lower precision.

Recent studies [, , , ] have shown that $1$-bit LLMs, most of which have matrix weights in the range of $\{-1,+1\}$, can be trained from scratch to deliver performance that rivals that of standard LLMs. These models exhibit remarkable efficiency, particularly in terms of scaling laws. Experimental results indicate that the performance of the $1$-bit model improves as the number of parameters increases, a principle that mirrors the training approach utilized in standard LLMs []. Despite the demonstrated efficiency of quantization methods, our understanding of the training mechanism for quantization remains limited. Specifically, it remains unclear how and why the $1$-bit QAT enhances learning capability as the number of neurons in the model is scaled up. In addition, we are also concerned about whether the quantization method damages the generalization ability compared to full precision networks.

In this study, we initially apply the Neural Tangent Kernel (NTK) framework to delve into the optimization and generalization issues associated with a two-layer linear network operating in 1-bit (int1) precision, as detailed in Section 4. We introduce a 1-bit quantization method to the hidden-layer weights $W\in\mathbb{R}^{d\times m}$ of the conventional NTK linear network, where $d$ represents the input dimension and $m$ indicates the model’s width. Our analysis reveals that the training dynamics of the 1-bit model approximate kernel behavior as the model width $m$ expands. This key finding paves the way for an established relationship between the theoretically guaranteed loss and the model width, endowing the model with robust learning capabilities akin to kernel regression. Ultimately, the model achieves an insignificantly small training loss, contingent on setting a sufficiently large model width, selecting an appropriate learning rate, and allowing an adequate training duration.

Moreover, Section 5 provides a theoretical confirmation that, within the scaling trend, the disparities in predictions of the 1-bit model from those of the original linear network on identical inputs maintain a negligible value. We assess the error between our 1-bit linear and standard linear networks on both the training and test datasets. Our theorem demonstrates that for any input from these datasets, the absolute error between the two network predictions can be denoted as $\epsilon_{\rm quant}\leq O(\kappa d\log(md/\delta))$ for scale coefficient $\kappa\leq 1$, model width $m$, dimension $d$ and failure probability $\delta\in(0,0.1)$. This indicates that the output behavior of the 1-bit linear model increasingly aligns with that of the standard linear model. The observed similarity on the test dataset validates the generalization similarity, suggesting the feasibility of approximating training neural networks with int1 precision equivalent to full precision.

Finally, in Section 6, we verify our theoretical results by implementing training models to learn complicated functions to compare the difference between $1$-bit networks and full precision networks. Firstly, we choose a combination of difficult functions across the exponential function, trigonometric function, logarithmic function, the Lambert W function, the Gamma function, and their combination. Therefore, we sample random data points and split train and test datasets. We next compare how the training loss decreases as the model width $m$ scales up. Besides, as shown in Section 6.3, in the trend of a growing number of parameters, the error of predictions both on training and test input likewise converge as the power-law in $1$-bit networks optimization. In particular, we visualize some $1$-dimension function to see how the differences of outputs are. We demonstrate the results complying with our theoretical guarantee with a negligible error.

## 2 Related Work

Efficient Training Methods for Quantized Networks
Training large-scale neural networks with quantization introduces significant computational and memory savings, but it also presents challenges in optimization, particularly when dealing with extremely low precision formats like 1-bit or 8-bit. To address these challenges, several efficient training methods have been developed that aim to maintain accuracy while leveraging the benefits of quantization. One key method is Gradient Quantization, where the gradients during backpropagation are quantized to lower precision to reduce memory overhead and bandwidth during distributed training. Techniques like stochastic rounding are used to mitigate the impact of quantization noise, ensuring the training process remains stable and converges effectively.

Another important approach is Low-Rank Factorization [, ], which decomposes the large weight matrices in neural networks into smaller matrices, reducing the number of parameters that need to be updated during training. When combined with quantization, this method significantly reduces both the memory footprint and computational complexity, allowing for faster training on hardware with limited resources.

Quantization Techniques for Accelerating Language Models
Beyond traditional weight and activation quantization, several advanced methods utilize quantization to enhance the efficiency of large language models (LLMs). One key approach is KV cache quantization [, , , ], which reduces the memory footprint of transformer models during inference by quantizing the stored attention keys and values. This method is particularly beneficial for tasks involving long sequences, significantly speeding up inference and lowering memory consumption without a substantial loss in accuracy.

Another effective technique is mixed-precision quantization [, ], where different parts of the model are quantized at varying precision levels based on their sensitivity. For example, attention layers might use higher precision (e.g., 16-bit), while feedforward layers are quantized to 8-bit or lower. This balances computational efficiency and model performance. These strategies, combined with methods like activation pruning, showcase how targeted quantization can drastically accelerate LLMs while maintaining their effectiveness in real-world applications.

Neural Tangent Kernel. The study of Neural Tangent Kernel (NTK) [] focuses on the gradient flow of neural networks during the training process, revealing that neural networks are equivalent to Gaussian processes at initialization in the infinite-width limit. This equivalence has been explored in numerous studies [, , , , , , , , , , , , , , ] that account for the robust performance and learning capabilities of over-parameterized neural networks. The kernel-based analysis framework provided by NTK is gaining popularity for its utility in elucidating the emerging abilities of large-scale neural networks. In a remarkable stride, ADH^+ [] introduced the first exact algorithm for computing the Convolutional NTK (CNTK). This was followed by AWBB [] who proposed the Recurrent NTK, and HBSDN [] who presented the concept of infinite attention via NNGP and NTK for attention networks. These innovative works have showcased the enhanced performance achievable with the application of NTK to various neural network architectures. In a specific study, MWY^+ [] examined the training dynamics of fine-tuning Large Language Models (LLMs) using NTK, affirming the efficiency of such approaches.

## 3 Preliminary

In this section, we give the basic setups of this paper, which includes the introduction of the quantization method in this paper (Section 3.1), our NTK-style problem setup that we aim to solve in this paper (Section 3.2) and recalling the classical NTK setup for a two-layer linear network with ReLU activation function (Section 3.3).

### 3.1 Quantization

We first show how we reduce the computation of the inner product of two vectors from multiplication and addition operations to addition operations only, which is achieved by binarizing one of the vectors. This method could be extended to matrix multiplication easily since the basic matrix multiplication is to implement the inner product computation of two vectors in parallels. For a vector $w\in\mathbb{R}^{d}$, we define our quantization function as [, ]:

$$ $\displaystyle{\rm Quant}(w):={\sf Sign}\Big{(}{\sf Ln}(w)\Big{)}\in\{-1,+1\}^{ d},$ $$

where ${\sf Ln}(w)$ is the normalization method that is given by:

$$ $\displaystyle{\sf Ln}(w):=\frac{w-E(w)\cdot{\bf 1}_{d}}{\sqrt{V(w)}}\in\mathbb {R}^{d}.$ $$

Specially, we use $E(w):=\frac{1}{d}\sum_{k=1}^{d}w_{k}\in\mathbb{R}$ to denote the computational expectation of vector $w$ and use $V(w):=\|w-E(w)\cdot{\bf 1}_{d}\|_{2}^{2}\in\mathbb{R}$ to denote the corresponding variance.

Besides, the $k^{\text{th}}$ entry of signal function ${\sf Sign}(z)\in\mathbb{R}^{d}$ for $z\in\mathbb{R}^{d}$, $k\in[d]$ is define by:

$$ $\displaystyle{\sf Sign}_{k}(z):=\begin{cases}+1,&z_{k}\geq 0\\ -1,&z_{k}<0\end{cases}$ $$

Hence, we have a binary vector ${\rm Quant}(w)$ where each entry of it is limited in the range $\{-1,+1\}$, and we denote that $\widetilde{w}:={\rm Quant}(w)$ to simplify the notation. For any other vector $x\in\mathbb{R}^{d}$, addition operation $\sum_{k=1}^{d}\pm x_{k}$ is sufficient to compute $\langle\widetilde{w},x\rangle$.
After that, we introduce the dequantization function to recover the original computation result by showing:

$$ $\displaystyle{\rm Dequant}(\langle\widetilde{w},x\rangle):=\sqrt{V(w)}\cdot \langle\widetilde{w},x\rangle+E(w)\cdot\langle{\bf 1},x\rangle$ $$

### 3.2 NTK Problem Setup

Data Points. We consider a supervised learning task with a training dataset ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$, where each data point is under a mild assumption that $\|x_{i}\|_{2}=1$ and $y_{i}\leq 1$, $\forall i\in[n]$ [].
Moreover, we are also concerned about the problem of the generalization of $1$-bit models, we define the test dataset to compare $1$-bit networks with standard networks, that is ${\cal D}_{\rm test}:=\{(x_{{\rm test},i},y_{{\rm test},i})\}_{i=1}^{n}\subset
\mathbb{R}^{d}\times\mathbb{R}$, where $\|x_{{\rm test},i}\|_{2}=1$ and $y_{{\rm test},i}\leq 1$, $\forall i\in[n]$.

Model. Here, we use hidden-layer weights $W=[w_{1},w_{2},\dots,w_{m}]\in\mathbb{R}^{d\times m}$ and output-layer weights $a=[a_{1},a_{2},\dots,a_{m}]^{\top}\in\mathbb{R}^{m}$. We consider a two-layer attention model $f$, which is defined as follows:

$$ $\displaystyle f(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU }\Big{(}\mathsf{dq}(\langle\widetilde{w}_{r},x\rangle)\Big{)},$ $$

where ${\sf ReLU}(z):=\begin{cases}z,&z\geq 0\\
0,&z<0\end{cases}$, for all $z\in\mathbb{R}$, $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ is a omitted version of dequantization function ${\rm Dequant}:\mathbb{R}\rightarrow\mathbb{R}$, and $\widetilde{w}_{r}:={\rm Quant}(w_{r})$ as we denoted in previous section, $\kappa\in(0,1]$ is a scale coefficient. Especially, we initialize each weight vector $w_{r}$, $\forall r\in[m]$ by sampling $w_{r}(0)\sim\mathcal{N}(0,\sigma\cdot I_{d})$ with $\sigma=1$. For output-layer $a$, we randomly sample $a_{r}\sim{\sf Uniform}\{-1,+1\}$ independently for $r\in[m]$. Additionally, output-layer weight $a$ is fixed during the training.

Training and Straight-Through Estimator (STE). The training loss is measured by quadratic $\ell_{2}$ norm of the difference between model prediction $f(x_{i},W,a)$ and ideal output vector $y_{i}$. Formally, we consider to train $W(t)=[w_{1}(t),w_{2}(t),\dots,w_{m}(t)]\in\mathbb{R}^{d\times m}$ for $t\geq 0$ utilizing the following loss:

$$ $\displaystyle{\sf L}(t):=\frac{1}{2}\cdot\sum_{i=1}^{n}\|f(x_{i},W(t),a)-y_{i} \|_{2}^{2}.$ (1) $$

Moreover, since the signal function ${\sf Sign}$ is not differentiable, we use Straight-Through Estimator (STE) to skip the signal function in back-propagation [, , , ], thus updating the trainable weights $W(t)$. For $t\geq 0$ and denote $\eta$ as the learning rate, we omit $f_{i}(t):=f(x_{i},W(t),a)\in\mathbb{R},\forall i\in[n]$, the formulation to update $r^{\text{th}}$ column of $W(t)$ for all $r\in[m]$ is given by:

$$ $\displaystyle w_{r}(t+1):=w_{r}(t)-\eta\sum_{i=1}^{n}(f_{i}(t)-y_{i})\cdot \kappa a_{r}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r},x_{i}\rangle)\geq 0} x_{i}.$ $$

### 3.3 Recalling Classic NTK Setup

We now recall the classic NTK setup for the two-layer ReLU linear regression [, , , ]. The function is given by:

$$ $\displaystyle f^{\prime}(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\sf ReLU}\Big{(}\langle w_{r},x\rangle\Big{)}.$ $$

We define that $W^{\prime}(0):=W(0)\in\mathbb{R}^{d\times m}$ to denote the trainable parameter for classic NTK setup, these two matrices are equal at initialization.
For $t\geq 0$, we define the loss of training $f^{\prime}$ as follows:

$$ $\displaystyle{\sf L}^{\prime}(t):=\frac{1}{2}\cdot\sum_{i=1}^{n}\|f^{\prime}(x _{i},W^{\prime}(t),a)-y_{i}\|_{2}^{2}.$ $$

Then the update of $W^{\prime}(t)$ is:

$$ $\displaystyle W^{\prime}(t+1):=W^{\prime}(t)-\eta\cdot\nabla_{W^{\prime}(t)}{ \sf L}^{\prime}(t).$ $$

## 4 Kernel Behavior and Training Convergence

We give our convergence analysis for training $1$-bit model within the framework of Neural Tangent Kernel (NTK) in this section. First, we state our theoretical results that define the kernel function in training and show how it converges to NTK and maintains the PD (Positive Definite) property in Section 4.1. Then we demonstrate the arbitrary small loss convergence guarantee of training $1$-bit model (Eq. (1)) in Section 4.2.

### 4.1 Neural Tangent Kernel

Here, we utilize the NTK to describe the training dynamic of the $1$-bit model. Following pre-conditions in the previous section, we define a kernel function, that denotes $H(t)\in\mathbb{R}^{n\times n}$ (Gram matrix). Especially, the $(i,j)$-th entry of $H(t)$ is given by:

$$ $\displaystyle H_{i,j}(t):=\kappa^{2}\frac{1}{m}x_{i}^{\top}x_{j}\sum_{r=1}^{m} {\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{j}\rangle)\geq 0}.$ (2) $$

We define the formal NTK as $H^{*}:=H(0)\in\mathbb{R}^{n\times n}$.
Additionally, there’s a commonly introduced assumption in NTK analysis: we denote the minimum value of eigenvalues of $A$ with $\lambda_{\min}(A)$ for any $A\in\mathbb{R}^{n\times n}$. In our work’s context, we presuppose that $H$ is a Positive-definite (PD) matrix, meaning that $\lambda_{\min}(H^{*})>0$ [].

1-Bit ReLU Pattern.
The pattern of the Rectified Linear Unit (ReLU) function is determined by the indicator of function activation. As illustrated by DZPS [], in the settings of Section 3.3, the event ${\bf 1}_{\langle w_{r}(0),x\rangle\geq 0}\neq{\bf 1}_{\langle w,x\rangle\geq 0}$ happens infrequently for any $w,x\in\mathbb{R}^{d}$ that satisfies $\|w-w_{r}(0)\|_{2}\leq R$. Notably, $R:=\max_{r\in[m]}\|w_{r}(t)-w_{r}(0)\|_{2}=\eta\|\sum_{\tau=1}^{t}\Delta w_{r}
(\tau)\|_{2}$. In our analysis, for Eq. (2), the event ${\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x\rangle)\geq 0}\neq{\bf 1}_{
\mathsf{dq}(\langle\widetilde{w}_{r}(t),x\rangle)\geq 0}$ is also unlikely to occur during training.

The convergence of $H(t)$ towards $H^{*}$, as well as the property of $H(t)$ being a PD matrix for any $t\geq 0$, can be validated by the following lemma:

###### Lemma 4.1 (NTK convergence and PD property during the training, informal version of Lemma G.5 ) .

Assume $\lambda_{\min}(H^{*})>0$. $\delta\in(0,1)$, define $D:=\max\{\sqrt{\log(md/\delta)},1\}$.
Let $R\leq O(\lambda\delta/(\kappa^{2}n^{2}dD))$, then for any $t\geq 0$, with probability at least $1-\delta$, we have:

- •
Part 1. $\|H(t)-H^{*}\|_{F}\leq O(\kappa^{2}n^{2}dRD/\delta)$.
- •
Part 2. $\lambda_{\min}(H(t))\geq\lambda/2$.

###### Proof of Lemma 4.1 .

The proof of Part 1 of this Lemma follows from the pattern ${\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}$ for $i\in[n]$ and $r\in[m]$ is rarely changed during the training, this habit is similar to the regular ReLU pattern ${\bf 1}_{\langle w_{r}(t),x_{i}\rangle\geq 0}$ []. The proof of Part 2 of this Lemma can be obtained by plugging $R\leq O(\lambda\delta/(\kappa^{2}n^{2}dD))$. Please refer to Lemma G.5 for the detailed proof.
∎

###### Lemma 4.1 (NTK convergence and PD property during the training, informal version of Lemma G.5 ) .

###### Proof of Lemma 4.1 .

### 4.2 Training Convergence

Having confirmed the convergence of the kernel function of the $1$-bit linear network during training in Lemma 4.1, we can transform the dynamics of the loss function ${\sf L}(t)$ into the following kernel behavior:

$$ $\displaystyle{\sf L}(t+1)-{\sf L}(t)=$ $\displaystyle~{}-(\mathsf{F}(t)-y)^{\top}H(t)(\mathsf{F}(t)-y)+C_{2}+C_{3}+C_{4}$ $\displaystyle\approx$ $\displaystyle~{}-(\mathsf{F}(t)-y)^{\top}H(t)(\mathsf{F}(t)-y),$ $$

In this equation, $\mathsf{F}(t)=[f(x_{1},W(t),a),\cdots,f(x_{n},W(t),a)]^{\top}\in\mathbb{R}^{n}$ and $y=[y_{1},\cdots,y_{n}]^{\top}\in\mathbb{R}^{n}$, while $C_{2},C_{3},C_{4}$ are negligible terms (please refer to Appendix I for a rigorous proof).

Further, by $\lambda_{\min}(H(t))>0$ (as per Part 2 of Lemma 4.1), for each optimization step $t\geq 0$, we find that ${\sf L}(t+1)\leq(1-\eta\lambda/2){\sf L}(t)$, thus ensuring a non-increase in loss. Given sufficient training iterations and an appropriately chosen learning rate, we can achieve training convergence, the confirmation of which is provided in the following section.

###### Theorem 4.2 (Training convergence guarantee, informal version of Theorem I.1 ) .

Given an expected error $\epsilon>0$. Assume $\lambda_{\min}(H^{*})>0$. $\delta\in(0,0.1)$, define $D:=\sqrt{\log(md/\delta)}$. Choose $m\geq\Omega(\lambda^{-8}n^{12}d^{8}/(\delta\epsilon)^{4})$, $\eta\leq O(\lambda\delta/(\kappa^{2}n^{2}dD))$. Then let $T\geq\Omega((\eta\lambda)^{-1}\log(ndD^{2}/\epsilon))$, with probability at least $1-\delta$, we have: ${\sf L}(T)\leq\epsilon$.

###### Proof sketch of Theorem 4.2 .

We first combine ${\sf L}(0)=O(\sqrt{n}dD^{2})$ (Lemma I.3) and ${\sf L}(t+1)\leq(1-\eta\lambda/2){\sf L}(t)$ (Lemma I.2), then we choose a sufficient large $T\geq\Omega((\eta\lambda)^{-1}\log(ndD^{2}/\epsilon))$ to achieve ${\sf L}(T)\leq\epsilon$. For the complete proof, please see Theorem I.1.
∎

Scaling Law for $1$-Bit Neural Networks. Theorem 4.2 primarily illustrates a fact for any dataset with $n$ data points. After initializing the hidden-layer weights $W\in\mathbb{R}^{d\times m}$ from a normal distribution, and assuming the minimum eigenvalue of NTK $\lambda>0$, we set $m$ to be a large enough value to ensure the network is sufficiently over-parameterized. With an appropriate learning rate, the loss can be minimized in finite training time to an arbitrarily small error $\epsilon$. This offers a crucial insight that confirms the existence of a scaling law for 1-bit neural networks, which is strictly bounded by the model width $m$ and training steps $T$. Consequently, we present the following Proposition that elucidates the principle of training 1-bit linear networks from scratch. This proposition is built upon Theorem 4.2 and the principle of training loss that scales as a power-law with model size, dataset size, and the amount of compute used for training [].

###### Proposition 4.3 (Scaling Law for $1$ -Bit Neural Networks) .

$\delta\in(0,0.1)$. Define $\mathsf{N}:=O(md)$ as the number of parameters, $\mathsf{D}:=O(n)$ as the size of training dataset, ${\sf C}:=O({\sf ND}T)$ as the total compute cost. Especially, we denote the scale coefficients as $\alpha:=\mathsf{D}d\log(md/\delta)$, and we then choose $\eta\leq O(\lambda\delta/(m\kappa^{2}n^{2}dD))$ and $T\geq\Omega((\eta\lambda m)^{-1}\log(nd\log(md/\delta)/\epsilon))$. Thus, the training loss, denoted as ${\sf L}_{\rm scale}$, satisfies:

$$ $\displaystyle{\sf L}_{\rm scale}\approx\max\{\frac{\mathsf{D}^{3}\cdot d^{2.25 }}{\lambda^{2}\mathsf{N}^{0.25}},\frac{\alpha}{\exp(\eta\lambda{\sf C})}\}$ $$

###### Proof of Proposition 4.3 .

This proof follows from the definitions of $\mathsf{N}$, $\mathsf{D}$, ${\sf C}$ and $\alpha$. Then, by choosing $\eta\leq O(\lambda\delta/(mn^{2}dD))$ and $T\geq\Omega((\eta\lambda m)^{-1}\log(nd\log(md/\delta)/\epsilon))$, we utilize Theorem 4.2 to obtain our proposition.
∎

Proposition 4.3 demonstrates that the training loss of the prefix learning converges exponentially as we increase the computational cost $\mathsf{C}$, which primarily depends on the number of parameters and the training time in prefix learning. This further suggests a potential relationship for formulating a scaling law for 1-bit neural networks.

Extensibility. Our analysis is conducted within a two-layer linear network defined in Section 3, which might raise concerns about its effectiveness in real-world multiple-layer 1-bit networks.
However, due to the theory of Hierarchical Learning [, , ], the optimization of a deep neural network is equivalent to training each layer of the network greedily. Therefore, our theoretical conclusion could be easily extended to the situation of training multiple layers 1-bit model.

Figure: Figure 1: Verification experiment for scaling law for $1$-bit neural networks. Minimum training loss of scaling number of parameters for MLP model to learn complicated functions $f_{1},f_{2},f_{3},f_{4},f_{5}$ and $f_{6}$, and these function is defined in Section 6.1.
Refer to caption: x1.png

###### Theorem 4.2 (Training convergence guarantee, informal version of Theorem I.1 ) .

###### Proof sketch of Theorem 4.2 .

###### Proposition 4.3 (Scaling Law for 1 1 1 1 -Bit Neural Networks) .

###### Proof of Proposition 4.3 .

## 5 Generalization Similarity

In this section, we present our theoretical analysis that proves that training large-scale $1$-bit neural networks is equivalent to training standard large-scale neural networks. In Section 5.1, we explain how the difference between the outputs of our $1$-bit model and outputs of the standard NTK-style linear network for the same input at initialization, which is defined as function difference at initialization, will be kept in a small error while the model width (denoted as $m$) increase. Next, in Section 5.2, we confirm that in the trend of scaling up the model width, during the training, the predictions of $1$-bit model and full precision model are also similar to a very slight error on both the training dataset and the test dataset.

### 5.1 Function Difference at Initialization

To begin with, at initialization, the boundary on $|f(x,W(0),a)-f^{\prime}(x,W^{\prime}(0),a)|$ is stated as follows:

###### Lemma 5.1 (Function difference at initialization, informal version of Lemma K.4 ) .

$\delta\in(0,0.1)$. Denote $D:=\sqrt{\log(md/\delta)}$. $\forall x\in\mathbb{R}^{d}$ that satisfies $\|x\|_{2}=1$, for any initial quantization error $\epsilon_{\rm init}>0$, we choose $\kappa\leq O(\epsilon_{\rm init}/(\sqrt{d}D^{2}))$. Then with a probability $1-\delta$, we have:

$$ $\displaystyle|f(x,W(0),a)-f^{\prime}(x,W^{\prime}(0),a)|\leq\epsilon_{\rm init}$ $$

###### Proof sketch of Lemma 5.1 .

Due to the initialization of $W(0)$ and $W^{\prime}(0)$, we then have the tail bound of the Gaussian distribution. Hence, the difference could be bounded by Hoeffding bound, we then get the result. Please refer to Lemma K.4 for the formal proof of this Lemma.
∎

###### Lemma 5.1 (Function difference at initialization, informal version of Lemma K.4 ) .

###### Proof sketch of Lemma 5.1 .

### 5.2 Generalization Similarity

We now address whether using $1$-bit precision compromises the generalization ability of standard neural networks. Specifically, we use the test dataset to evaluate the generalization similarity - a measure of the similarity between two functions on out-of-distribution (OOD) data. This measure is designed to assess the equivalence between two functions. If, during each step of training two networks, these two training processes are deemed equivalent, then we assert that the generalization similarity is valid.

Addressing the above concern, we demonstrate that the predictions of two functions on both training and test datasets can be bounded to an arbitrarily small quantization error, provided that $m$ is sufficiently large. Theoretically, as $m$ scales towards infinity, the quantization error converges to 0 0. This finding confirms the validity of our generalization similarity measure and asserts that 1-bit precision does not compromise the generalization ability of standard neural networks.

###### Theorem 5.2 (Training and generalization similarity, informal version of Theorem K.1 ) .

Let all pre-conditions in Theorem 4.2 satisfy. For any quantization error $\epsilon_{\rm quant}>0$, we choose $\kappa\leq O(\epsilon_{\rm quant}/(dD^{2}))$. Integer $\forall t\geq 0$. For any training input $x_{i}\in\mathbb{R}^{d}$ in $\mathcal{D}$ and any test input $x_{{\rm test},i}\in\mathbb{R}^{d}$ in $\mathcal{D}_{\rm test}$, with a probability at least $1-\delta$, we have:

- •
Part 1. $|f(x_{i},W(t),a)-f(x_{i},W(t),a)|\leq\epsilon_{\rm quant}$.
- •
Part 2. $|f(x_{{\rm test},i},W(t),a)-f(x_{{\rm test},i},W(t),a)|\leq\epsilon_{\rm quant}$.

###### Proof.

Proof sketch of Theorem 5.2
Since we proved $|f(x,W(0),a)-f^{\prime}(x,W^{\prime}(0),a)|\leq\epsilon_{\rm init}$ in Lemma 5.1, then as we choose appropriate $R$ and learning rate $\eta$, the equations in Part 1 and Part 2 of this Theorem would be bounded by scaling $m$ to be sufficiently large. We state the complete proof in Theorem K.1.
∎

Training Equivalence. Here, we say training $f$ and $f^{\prime}$ are equivalent since we achieve the predictions that these two functions are extremely similar by plugging an appropriate value of $\kappa$. Besides, as we proved in Theorem 4.2, this implementation would not harm the optimization of $1$-bit networks. This further explains why $1$-bit precision even processes better when the scales of networks are increasing, instead of turning to a training collapse. Therefore, we believe it is the theory unlocking the potential of $1$-bit neural networks from the perspective of kernel-based analysis.

Figure: Figure 2: This plot shows the difference between the predicted and actual values of the functions on the test dataset. We tested three complex functions, as seen in the images, and the performance of the 1-bit model is nearly identical to that of the standard 32-bit floating-point model.
Refer to caption: x2.png

###### Theorem 5.2 (Training and generalization similarity, informal version of Theorem K.1 ) .

###### Proof.

## 6 Experiments

In this section, we aim to verify our theory by evaluating how well our quantization works for learning rigorous functions and comparing it to the standard model. We designed our experiment to 1) validate the scaling law (Section 6.1), 2) visually demonstrate that the performance difference is minimal compared to the standard model, which uses full-bit precision, through visualizations of single-variable input functions (Section 6.2), and 3) show how the test and train losses decrease as the model’s parameter size increases and as the epochs progress (Section 6.3).

### 6.1 Verification on Scaling Law

Experiment Setup In this experiment, we aimed to learn rigorous functions using a Multi-Layer Perceptron (MLP) with varying depths of 3 and 5 layers. The MLP models had different sizes for the hidden layers, and we measured the minimum loss achieved throughout the training process. Each model was trained for 100,000 steps. We experimented with various parameter sizes and plotted the corresponding loss functions. Additionally, we compared our method with the standard training approach using 32-bit floating-point precision.

We experimented with a variety of target functions, and for each function, the inputs $x_{i}$ were randomly chosen within the range $[-1,1]$. Specifically, each $x_{i}$ was sampled from a uniform distribution over this interval to ensure that the network could handle input values across the entire domain of interest. We sampled 100 data points and trained our model over the this set.

The functions we aimed to learn during the experiment are listed below:

- 1.
$f_{1}(x_{1},x_{2},x_{3},x_{4},x_{5})=\exp\left(\frac{1}{5}\sum_{i=1}^{5}\sin^{
2}\left(\frac{\pi x_{i}}{2}\right)\right)$, This function takes five inputs and applies a sinusoidal transformation followed by an exponential operation.
- 2.
$f_{2}(x_{1},x_{2},x_{3},x_{4})=\ln(1+|x_{1}|)+\left(x_{2}^{2}-x_{2}\right)+
\sin(x_{3})-e^{x_{4}}$, the function combines logarithmic, polynomial, trigonometric, and exponential components over four input variables.
- 3.
$f_{3}(x_{1},x_{2},x_{3})=x_{1}\times x_{2}-x_{3}$,
This is a simple linear function over three inputs, involving multiplication and subtraction.
- 4.
$f_{4}(x_{1},x_{2},x_{3},x_{4})=x_{0}\cdot\sin(x_{1})+\cos(x_{2})-0.5\cdot x_{3}$,
A four-input function mixing trigonometric and linear terms, with coefficients applied to the terms.
- 5.
$f_{5}(x_{1},x_{2},x_{3},x_{4})=\frac{x_{0}^{2}}{1+|x_{1}|}-e^{x_{2}}+\tanh(x_{
3})+\sqrt{|x_{0}\cdot x_{2}|}$,
This function incorporates nonlinear operations like exponentials, hyperbolic tangents, and square roots.
- 6.
$f_{6}(x_{1},x_{2},x_{3},x_{4})=\text{LambertW}(x_{0}\cdot x_{1})+\frac{x_{2}}{
\log(1+e^{x_{3}})}-\frac{\Gamma(x_{1})}{1+|x_{0}|}$,
The most complex function we tested, which includes special functions like the Lambert W function and the Gamma function, alongside logarithmic and exponential components.

We compare our quantized model (using INT1, $32\times$ smaller) to a standard non-quantized model (using 32-bit precision). For all functions ($f_{1}$ to $f_{6}$), we observe (in ) that as the number of parameters increases, the loss decreases, supporting our theoretical claim that larger models lead to convergence.

Although the standard method generally performs better due to its 32-bit precision, the gap decreases as the number of parameters grows. This shows that while our method has a slightly higher loss, it remains competitive, offering significant memory and computational efficiency.

### 6.2 Comparison on 1-D Functions

In this experiment, we aimed to visually demonstrate the performance on highly complex functions with sharp spikes between $[-\pi,\pi]$. We sampled 100 uniformly spaced points and trained a 2-layer MLP with 20M parameters to learn the function. Additionally, we sampled 100 random points uniformly from this interval as the test dataset.

The first observation from the plot is that both the standard and 1-bit methods learn all the functions almost perfectly, with minimal difference between them. Secondly, both methods perform similarly on these functions, which can be easily observed by comparing the scatter plots of the 1-bit and standard models. The 1-bit model requires $32\times$ less energy and computation.

Figure: Figure 3: This plot shows the $\ell_{2}$ difference between both the training and test points and the predicted points throughout the training phase for different model sizes and parameter counts. Each plot demonstrates how the error decreases as training progresses, highlighting the impact of model size on both training and test performance.
Refer to caption: x3.png

### 6.3 Evaluation on Training and Generalization Similarity

For the same set of functions, we show how the loss functions for both the train and test datasets decrease as the number of epochs increases. As the training progresses, the loss converges towards zero for models with a higher number of parameters. We experimented with models containing 2.4k, 204k, and 20M parameters, each consisting of only 2 layers.

Across all three functions, the loss decreases rapidly in the early epochs and stabilizes for both the training and test sets. Larger models with 20M parameters consistently achieve lower final losses compared to smaller models with 2.4k and 204k parameters, demonstrating the benefit of increased model size. The gap between training and test losses remains minimal, indicating strong generalization across different parameter sizes. More importantly, the key observation is that the models predict similarly on both the training and test datasets, a behavior we refer to as *generalization similarity*. This means that the models, regardless of size, behave similarly across both datasets, supporting the scaling law that increasing model size leads to better convergence and generalization, but also highlighting the consistent similarity in performance between training and testing across different functions.

## 7 Conclusion

In conclusion, our theoretical results confirm the scaling law for 1-bit neural networks. We demonstrated that the model achieves a small loss as the number of parameters increases. Despite the constraint of binary weights, 1-bit models show similar behavior to full-precision models as their width grows. Our experiments support this theory, showing that 1-bit networks perform nearly as well as standard models on complex functions. As the number of parameters grows, the performance gap between 1-bit and full-precision models reduces. These findings highlight that 1-bit networks are both efficient and effective, providing a strong alternative to traditional models.

## Acknowledgement

The authors sincerely thank Bo Chen, Xiaoyu Li, Zhizhou Sha, Jing Xiong, Junwei Yu and Yufa Zhou for their helpful suggestions and discussion.

Appendix

## Roadmap

We initially introduce the intention of each section in the appendix here. In Appendix A, we review more prior works that relate to our work. In Appendix B, we provide the preliminary for our theoretical analysis. In Appendix C, we give the formal definition of the NTK-style problem setup we aim to solve in this paper. In Appendix D, we strictly define the quantization method we utilize for our approach. We discuss the potential pattern changing of ReLU and signal function in Appendix E. For optimizing $1$-bit neural network, we state the Straight-Through Estimator method (STE) definitions in Appendix F. In Appendix G, we define NTK for our optimization problem and discuss its properties. In Appendix I, we prove the convergence guarantee of training $1$-bit neural networks. In Appendix J, we review the classical setup of solving the NTK-style linear regression. We confirm the generalization similarity in Appendix K.

## Appendix A More Related Work

Theoretical Approach for Understanding Modern Neural Networks.
The intricate architecture of transformer-based models, coupled with the stochastic nature of their optimization processes, presents a formidable challenge in comprehending the behaviors of large language models (LLMs). However, delving into these complexities through a theoretical lens can illuminate pathways for enhancing and innovating future AI systems. This exploration encompasses various facets, including the optimization strategies for LLMs [, , ], the intricacies of white-box transformers [, , , ], and the analysis of emergent capabilities that arise within these models [, , , , , ]. Additionally, the modern Hopfield model [, , , , , , ] offers a rich terrain for investigation, revealing the nuanced dynamics that govern these advanced neural networks.

Efficient Neural Networks.
As the principles of scaling laws come to the forefront, contemporary neural networks are increasingly trained on expansive datasets, necessitating substantial computational resources [, , , , , , , , , , , ]. This demand for efficiency has spurred research into algorithms that optimize computational complexity, minimize memory usage, and enhance alignment with GPU architectures. Such advancements are crucial in navigating the challenges posed by the ever-growing scale of data and the intricate demands of modern AI applications, ensuring that these powerful tools remain accessible and effective in their deployment.

## Appendix B Preliminary

### B.1 Notations

In this paper, we use integer $m>0$ to denote the width of neural networks, in particular, $m$ is sufficiently large. We use integer $d>0$ to denote the dimension of neural networks. We use integer $n>0$ to denote the size of the training dataset.

### B.2 Basic Facts

###### Fact B.1 .

For a variable $x\sim\mathcal{N}(0,\sigma^{2})$, then with probability at least $1-\delta$, we have:

$$ $\displaystyle|x|\leq C\sigma\sqrt{\log(1/\delta)}$ $$

###### Fact B.2 .

For an $1$-Lipschitz function $f(\cdot)$, we have:

$$ $\displaystyle|f(x)-f(y)|\leq|x-y|,\forall x,y\in\mathbb{R}^{d}$ $$

###### Fact B.3 .

For a Gaussian variable $x\sim\mathcal{N}(0,\sigma^{2}\cdot I_{d})$ where $\sigma\in\mathbb{R}$, then for any $t>0$, we have:

$$ $\displaystyle\Pr[x\leq t]\leq\frac{2t}{\sqrt{2\pi}\sigma}$ $$

###### Fact B.4 .

For a Gaussian vector $w\sim\mathcal{N}(0,\sigma^{2}\cdot I_{d})$ where $\sigma\in\mathbb{R}$, and a fixed vector $x\in\mathbb{R}^{d}$, we have:

$$ $\displaystyle w^{\top}x\sim\mathcal{N}(0,\sigma^{2}\|x\|_{2}^{2}\cdot I_{d})$ $$

###### Fact B.5 .

For two matrices $H,\widetilde{H}\in\mathbb{R}^{n\times n}$, we have:

$$ $\displaystyle\lambda_{\min}(\widetilde{H})\geq\lambda_{\min}(H)-\|H-\widetilde {H}\|_{F}$ $$

###### Fact B.6 .

For $x\in(0,1)$, integer $t\geq 0$, we have:

$$ $\displaystyle\sum_{\tau=1}^{t}(1-x)^{\tau}\leq-\frac{1}{\log(1-x)}\leq\frac{2} {x}$ $$

###### Fact B.1 .

###### Fact B.2 .

###### Fact B.3 .

###### Fact B.4 .

###### Fact B.5 .

###### Fact B.6 .

### B.3 Probability Tools

Here, we state a probability toolkit in the following, including several helpful lemmas we’d like to use. Firstly, we provide the lemma about Chernoff bound in [] below.

###### Lemma B.7 (Chernoff bound, [ 23 ] ) .

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and $X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$ are independent. Let $\mu=\operatorname*{{\mathbb{E}}}[X]=\sum_{i=1}^{n}p_{i}$. Then

- •
$\Pr[X\geq(1+\delta)\mu]\leq\exp(-\delta^{2}\mu/3)$, $\forall\delta>0$;
- •
$\Pr[X\leq(1-\delta)\mu]\leq\exp(-\delta^{2}\mu/1)$, $\forall 0<\delta<1$.

Next, we offer the lemma about Hoeffding bound as in [].

###### Lemma B.8 (Hoeffding bound, [ 44 ] ) .

Let $X_{1},\cdots,X_{n}$ denote $n$ independent bounded variables in $[a_{i},b_{i}]$ for $a_{i},b_{i}\in\mathbb{R}$. Let $X:=\sum_{i=1}^{n}X_{i}$, then we have

$$ $\displaystyle\Pr[|X-\operatorname*{{\mathbb{E}}}[X]|\geq t]\leq 2\exp(-\frac{2 t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}})$ $$

We show the lemma of Bernstein inequality as [].

###### Lemma B.9 (Bernstein inequality, [ 16 ] ) .

Let $X_{1},\cdots,X_{n}$ denote $n$ independent zero-mean random variables. Suppose $|X_{i}|\leq M$ almost surely for all $i$. Then, for all positive $t$,

$$ $\displaystyle\Pr[\sum_{i=1}^{n}X_{i}\geq t]\leq\exp(-\frac{t^{2}/2}{\sum_{j=1} ^{n}\operatorname*{{\mathbb{E}}}[X_{j}^{2}]+Mt/3})$ $$

Then, we give the Khintchine’s inequality in [, ] as follows:

###### Lemma B.10 (Khintchine’s inequality, [ 49 , 36 ] ) .

Let $\sigma_{1},\cdots,\sigma_{n}$ be i.i.d sign random variables, and let $z_{1}\cdots,z_{n}$ be real numbers. Then there are constants $C>0$ so that for all $t>0$

$$ $\displaystyle\Pr[|\sum_{i=1}^{n}z_{i}\sigma_{i}|\geq t\|z\|_{2}]\leq\exp(-Ct^{ 2})$ $$

We give Hason-wright inequality from [, ] below.

###### Lemma B.11 (Hason-wright inequality, [ 45 , 76 ] ) .

Let $x\in\mathbb{R}^{n}$ denote a random vector with independent entries $x_{i}$ with $\operatorname*{{\mathbb{E}}}[x_{i}]=0$ and $|x_{i}|\leq K$ Let $A$ be an $n\times n$ matrix. Then, for every $t\geq 0$

$$ $\displaystyle\Pr[|x^{\top}Ax-\operatorname*{{\mathbb{E}}}[x^{\top}Ax]|>t]\leq 2 \exp(-c\min\{t^{2}/(K^{4}\|A\|_{F}^{2}),t/(K^{2}\|A\|)\})$ $$

We state Lemma 1 on page 1325 of Laurent and Massart [].

###### Lemma B.12 (Lemma 1 on page 1325 of Laurent and Massart, [ 59 ] ) .

Let $X\sim\mathcal{X}_{k}^{2}$ be a chi-squared distributed random variable with $k$ degrees of freedom. Each one has zero mean and $\sigma^{2}$ variance. Then

$$ $\displaystyle\Pr[X-k\sigma^{2}\geq(2\sqrt{kt}+2t)\sigma^{2}]\leq\exp(-t)$ $\displaystyle\Pr[X-k\sigma^{2}\geq 2\sqrt{kt}\sigma^{2}]\leq\exp(-t)$ $$

Here, we provide a tail bound for sub-exponential distribution [].

###### Lemma B.13 (Tail bound for sub-exponential distribution, [ 31 ] ) .

We say $X\in\mathrm{SE}(\sigma^{2},\alpha)$ with parameters $\sigma>0$, $\alpha>0$, if

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[e^{\lambda X}]\leq\exp(\lambda^{2} \sigma^{2}/2),\forall|\lambda|<1/\alpha.$ $$

Let $X\in\mathrm{SE}(\sigma^{2},\alpha)$ and $\operatorname*{{\mathbb{E}}}[X]=\mu$, then:

$$ $\displaystyle\Pr[|X-\mu|\geq t]\leq\exp(-0.5\min\{t^{2}/\sigma^{2},t/\alpha\})$ $$

In the following, we show the helpful lemma of matrix Chernoff bound as in [, ].

###### Lemma B.14 (Matrix Chernoff bound, [ 85 , 54 ] ) .

Let $\mathcal{X}$ be a finite set of positive-semidefinite matrices with dimension $d\times d$, and suppose that

$$ $\displaystyle\max_{X\in\mathcal{X}}\lambda_{\rm max}(X)\leq B.$ $$

Sample $\{X_{1},\cdots,X_{n}\}$ uniformly at random from $\mathcal{X}$ without replacement. We define $\mu_{\rm min}$ and $\mu_{\rm max}$ as follows:

$$ $\displaystyle\mu_{\rm min}:=n\cdot\lambda_{\rm min}(\operatorname*{{\mathbb{E} }}_{X\in\mathcal{X}}(X))$ $\displaystyle\mu_{\rm max}:=n\cdot\lambda_{\rm max}(\operatorname*{{\mathbb{E} }}_{X\in\mathcal{X}}(X)).$ $$

Then

$$ $\displaystyle~{}\Pr[\lambda_{\rm min}(\sum_{i=1}^{n}X_{i})\leq(1-\delta)\mu_{ \rm min}]\leq d\cdot\exp(-\delta^{2}\mu_{\rm min}/B)\text{~{}for~{}}\delta\in( 0,1],$ $\displaystyle~{}\Pr[\lambda_{\rm max}(\sum_{i=1}^{n}X_{i})\geq(1+\delta)\mu_{ \rm max}]\leq d\cdot\exp(-\delta^{2}\mu_{\rm max}/(4B))\text{~{}for~{}}\delta \geq 0.$ $$

Finally, we state Markov’s inequality as below.

###### Lemma B.15 (Markov’s inequality) .

If $X$ is a non-negative random variable and $a>0$, then the probability that $X$ is at least $a$ is at most the expectation of $X$ divided by $a$:

$$ $\displaystyle\Pr[X\geq a]\leq\frac{\operatorname*{{\mathbb{E}}}[X]}{a}$ $$

###### Lemma B.7 (Chernoff bound, [ 23 ] ) .

###### Lemma B.8 (Hoeffding bound, [ 44 ] ) .

###### Lemma B.9 (Bernstein inequality, [ 16 ] ) .

###### Lemma B.10 (Khintchine’s inequality, [ 49 , 36 ] ) .

###### Lemma B.11 (Hason-wright inequality, [ 45 , 76 ] ) .

###### Lemma B.12 (Lemma 1 on page 1325 of Laurent and Massart, [ 59 ] ) .

###### Lemma B.13 (Tail bound for sub-exponential distribution, [ 31 ] ) .

###### Lemma B.14 (Matrix Chernoff bound, [ 85 , 54 ] ) .

###### Lemma B.15 (Markov’s inequality) .

### B.4 Basic Bound

###### Definition B.16 .

For $\delta\in(0,0.1)$ and a sufficiently large constant $C>0$, we define:

$$ $\displaystyle D:=\max\{C\sqrt{\log(md/\delta)},1\}$ $$

###### Definition B.16 .

## Appendix C NTK Problem Setup

### C.1 Dataset

We consider a dataset where each data point is a tuple that includes a vector input and a scalar output. In particular, we assume that $\ell_{2}$ norm of each input equals $1$ and the absolute value of each target is not bigger than $1$. We give the formal definition as follows:

###### Definition C.1 (Data Points) .

We define dataset ${\cal D}:=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$, where $\|x_{i}\|_{2}=1$ and $|y_{i}|\leq 1$ for any $i\in[n]$.

###### Definition C.1 (Data Points) .

### C.2 Model

Weights and Initialization.

###### Definition C.2 .

We give the following definitions:

- •
Hidden-layer weights $W\in\mathbb{R}^{d\times m}$. We define the hidden-layer weights $W:=\begin{bmatrix}w_{1},w_{2},\cdots,w_{m}\end{bmatrix}\in\mathbb{R}^{d\times m}$ where $w_{r}\in\mathbb{R}^{d},\forall r\in[m]$.
- •
Output-layer weights $a\in\mathbb{R}^{m}$. We define the output-layer weights $a:=\begin{bmatrix}a_{1},a_{2},\cdots,a_{m}\end{bmatrix}^{\top}\in\mathbb{R}^{m}$, especially, vector $a$ is fixed during the training.

###### Definition C.3 .

We give the following initializations:

- •
Initialization of hidden-layer weights $W\in\mathbb{R}^{d\times m}$. We randomly initialize $W(0):=\begin{bmatrix}w_{1}(0),w_{2}(0),\cdots,w_{m}(0)\end{bmatrix}\in\mathbb{
R}^{d\times m}$, where its $r$-th column for $r\in[m]$ is sampled by $w_{r}(0)\sim\mathcal{N}(0,\sigma^{2}\cdot I_{d})$ with $\sigma^{2}=1$.
- •
Initialization of output-layer weights $a\in\mathbb{R}^{m}$. We randomly initialize $a\in\mathbb{R}^{m}$ where its $r$-th entry for $r\in[m]$ is sampled by $a_{r}\sim{\sf Uniorm}\{-1,+1\}$.

Model.

###### Definition C.4 .

For a scalar $x\in\mathbb{R}$, we define:

$$ $\displaystyle{\sf ReLU}(x)=\max\{0,x\}\in\mathbb{R}$ $$

###### Definition C.5 .

If the following conditions hold:

- •
For a input vector $x\in\mathbb{R}^{d}$.
- •
For a hidden-layer weights $W\in\mathbb{R}^{d\times m}$ as Definition C.2.
- •
For a output-layer weights $a\in\mathbb{R}^{m}$ as Definition C.2.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let ${\sf ReLU}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition C.4.
- •
For $\kappa\in(0,1]$.

We define:

$$ $\displaystyle f(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU }\Big{(}\mathsf{dq}(\langle\widetilde{w}_{r},x\rangle)\Big{)}\in\mathbb{R}$ $$

###### Lemma C.6 .

If the following conditions hold:

- •
For a input vector $x\in\mathbb{R}^{d}$.
- •
For a hidden-layer weights $W\in\mathbb{R}^{d\times m}$ as Definition C.2.
- •
For a output-layer weights $a\in\mathbb{R}^{m}$ as Definition C.2.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let ${\sf ReLU}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition C.4.
- •
Let $u:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ be defined as Definition D.6.
- •
For $\kappa\in(0,1]$.

Then we have:

$$ $\displaystyle f(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU }\Big{(}\langle w_{r},x\rangle+\langle u(w_{r}),x\rangle\Big{)}$ $$

###### Proof.

We have

$$ $\displaystyle f(x,W,a)=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU}\Big {(}\mathsf{dq}(\langle\widetilde{w}_{r},x\rangle)\Big{)}$ $\displaystyle=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU}\Big {(}\sqrt{V(w)}\cdot(\langle\widetilde{w},x\rangle+E(w)\cdot\langle x,{\bf 1}_{ d}\rangle)\Big{)}$ $\displaystyle=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU}\Big {(}\langle w_{r},x\rangle+\langle u(w_{r}),x\rangle\Big{)}$ $$

where the first step follows from Definition C.5, the second step follows from Definition D.5, the last step follows from Definition D.6.
∎

###### Definition C.2 .

###### Definition C.3 .

###### Definition C.4 .

###### Definition C.5 .

###### Lemma C.6 .

###### Proof.

### C.3 Training

Training.

###### Definition C.7 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\rightarrow
\mathbb{R}$ be defined as Definition C.5.
- •
For any $t\geq 0$.

We define:

$$ $\displaystyle L(W(t)):=\frac{1}{2}\cdot\sum_{i=1}^{n}(f(x_{i},W(t),a)-y_{i})^{2}$ $$

###### Definition C.8 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\rightarrow
\mathbb{R}$ be defined as Definition C.5.
- •
For any $t\geq 0$.
- •
Let $L(W(t))$ be defined as Definition C.7.
- •
Denote $\eta>0$ as the learning rate.
- •
Let $\Delta W(t)\in\mathbb{R}^{d\times m}$ be defined as Definition F.2.

We update:

$$ $\displaystyle W(t+1):=W(t)-\eta\cdot\Delta W(t)$ $$

Compact Form.

###### Definition C.9 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\rightarrow
\mathbb{R}$ be defined as Definition C.5.
- •
For any $t\geq 0$.
- •
Let $L(W(t))$ be defined as Definition C.7.
- •
Let $W(t)$ be updated by Definition C.8.

We give the following compact form of defined variables and functions:

- •
Compact form of model function. We define:
$\displaystyle\mathsf{F}(t):=\begin{bmatrix}f(x_{1},W(t),a),f(x_{2},W(t),a),
\cdots,f(x_{n},W(t),a)\end{bmatrix}^{\top}\in\mathbb{R}^{n}$
- •
Compact form of the input vector in the training dataset. We define:
$\displaystyle X:=\begin{bmatrix}x_{1},x_{2},\cdots,x_{n}\end{bmatrix}^{\top}
\in\mathbb{R}^{n\times d}$
- •
Compact form of the targets in the training dataset. We define:
$\displaystyle y:=\begin{bmatrix}y_{1},y_{2},\cdots,y_{n}\end{bmatrix}^{\top}
\in\mathbb{R}^{n}$
- •
Compact form of the training objective. We define:
$\displaystyle{\sf L}(t):=\frac{1}{2}\cdot\|\mathsf{F}(t)-y\|_{2}^{2}$
Especially, we have ${\sf L}(t)=L(W(t))$ by simple algebras.

###### Definition C.7 .

###### Definition C.8 .

###### Definition C.9 .

## Appendix D Quantization

### D.1 Quantization Functions

###### Definition D.1 .

For a vector $w\in\mathbb{R}^{d}$, we define ${\sf Sign}(w)\in\{-1,+1\}^{d}$ where its $k$-th entry for $k\in[d]$ is given by:

$$ $\displaystyle{\sf Sign}_{k}(w):=\begin{cases}-1,&\text{\rm if }w_{k}<0\\ +1,&\text{\rm if }w_{k}\geq 0\end{cases}\in\{-1,+1\}$ $$

###### Definition D.2 .

For a vector $w\in\mathbb{R}^{d}$, we define expectation function as follows:

$$ $\displaystyle E(w):=\frac{\langle w,{\bf 1}_{d}\rangle}{d}\in\mathbb{R}$ $$

###### Definition D.3 .

Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2. For a vector $w\in\mathbb{R}^{d}$, we define variance function as follows:

$$ $\displaystyle V(w):=\frac{1}{d}\cdot\|w-E(w)\cdot{\bf 1}_{d}\|_{2}^{2}\in \mathbb{R}$ $$

###### Definition D.4 .

If the following conditions hold:

- •
Let ${\sf Sign}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.1.
- •
Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2.
- •
Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3.
- •
For a weight vector $w\in\mathbb{R}^{d}$.

We define the quantization function as follows:

$$ $\displaystyle\mathsf{q}(w):={\sf Sign}(\frac{w-E(w)\cdot{\bf 1}_{d}}{\sqrt{V(w )}})\in\{-1,+1\}^{d}$ $$

###### Definition D.1 .

###### Definition D.2 .

###### Definition D.3 .

###### Definition D.4 .

### D.2 Dequantization Functions

###### Definition D.5 .

If the following conditions hold:

- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2.
- •
Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3.
- •
For a weight vector $w\in\mathbb{R}^{d}$.
- •
Denote quantized vector $\widetilde{w}:=\mathsf{q}(w)\in\{-1,+1\}^{d}$.
- •
For a vector $x\in\mathbb{R}^{d}$.

We define the dequantization function as follows:

$$ $\displaystyle\mathsf{dq}(\langle\widetilde{w},x\rangle):=\sqrt{V(w)}\cdot \langle\widetilde{w},x\rangle+E(w)\cdot\langle x,{\bf 1}_{d}\rangle\in\mathbb{R}$ $$

###### Definition D.5 .

### D.3 Quantization Error

###### Definition D.6 .

If the following conditions hold:

- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2.
- •
Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3.
- •
For a weight vector $w\in\mathbb{R}^{d}$.
- •
Denote quantized vector $\widetilde{w}:=\mathsf{q}(w)\in\{-1,+1\}^{d}$.
- •
For a vector $x\in\mathbb{R}^{d}$.

We define the quantization difference vector as follows:

$$ $\displaystyle u(w):=\sqrt{V(w)}\widetilde{w}+E(w)\cdot{\bf 1}_{d}-w\in\mathbb{ R}^{d}$ $$

###### Lemma D.7 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2.
- •
Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3.
- •
For a weight vector $w\in\mathbb{R}^{d}$.
- •
Denote quantized vector $\widetilde{w}:=\mathsf{q}(w)\in\{-1,+1\}^{d}$.
- •
For a vector $x\in\mathbb{R}^{d}$ and $\|x\|_{2}=1$.
- •
Let $u:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ be defined as Definition D.6.

Then we have:

$$ $\displaystyle\langle u(w),x\rangle\leq O\Big{(}d(D+R)\Big{)}$ $$

###### Proof.

We define:

$$ $\displaystyle{\sf Ln}(w)=\frac{w-E(w){\bf 1}_{d}}{\sqrt{V(w)}}$ $$

Then by simple algebras, we can show that:

$$ $\displaystyle\frac{1}{d}\|{\sf Ln}(w)\|_{2}^{2}=\frac{1}{d}\left\|\frac{w-E(w) {\bf 1}_{d}}{\sqrt{V(w)}}\right\|_{2}^{2}<\frac{1}{d}\frac{\left\|w-E(w){\bf 1 }_{d}\right\|_{2}^{2}}{V(w)}<1$ (3) $$

Thus, we obtain:

$$ $\displaystyle\|{\sf Ln}(w)\|_{\infty}\leq$ $\displaystyle~{}\|{\sf Ln}(w)\|_{2}$ $\displaystyle=$ $\displaystyle~{}(\|{\sf Ln}(w)\|_{2}^{2})^{\frac{1}{2}}$ $\displaystyle<$ $\displaystyle~{}\sqrt{d}$ $$

where these steps follow from simple algebras and Eq. (3).

Finally, we can get that

$$ $\displaystyle|\langle u(w),x\rangle|=$ $\displaystyle~{}\sqrt{V(w)}\cdot|\langle\widetilde{w}-{\sf Ln}(w),x\rangle|$ $\displaystyle=$ $\displaystyle~{}O(D+R)\cdot|\langle\widetilde{w}-{\sf Ln}(w),x\rangle|$ $\displaystyle\leq$ $\displaystyle~{}O(D+R)\cdot\|\widetilde{w}-{\sf Ln}(w)\|_{2}$ $\displaystyle=$ $\displaystyle~{}O(D+R)\cdot\Big{(}\sum_{k=1}^{d}(\widetilde{w}_{k}-{\sf Ln}_{k }(w))^{2}\Big{)}^{\frac{1}{2}}$ $\displaystyle\leq$ $\displaystyle~{}O(D+R)\cdot\Big{(}\sum_{k=1}^{d}(\max\{\sqrt{d}-1,1\})^{2}\Big {)}^{\frac{1}{2}}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}d(D+R)\Big{)}$ $$

where the first step follows from Definition D.6, the second step follows from Part 7 of Lemma I.6, the third step follows from Cauchy-Schwarz inequality and $\|x\|_{2}=1$, the fourth step follows from the definition of $\ell_{2}$ norm, the fifth step follows from Definition D.1 and simple algebras, the last step follows from simple algebras.
∎

###### Definition D.6 .

###### Lemma D.7 .

###### Proof.

## Appendix E Patterns

### E.1 ReLU Pattern

###### Definition E.1 .

If the following conditions hold:

- •
For any $w\in\mathbb{R}^{d}$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
For $R>0$.
- •
For $i\in[n]$ and $r\in[m]$.

We define:

$$ $\displaystyle\mathsf{A}_{i,r}:=\{\exists w\in\mathbb{R}^{d}:\|w-w_{r}(0)\|_{2} \leq R,{\bf 1}_{\mathsf{dq}(\langle w_{r}(0),x_{i}\rangle)\geq 0}\neq{\bf 1}_{ \mathsf{dq}(\langle w,x_{i}\rangle)\geq 0}\}$ $$

###### Definition E.2 .

Let event $\mathsf{A}_{i,r}$ for $i\in[n]$ and $r\in[m]$ be defined as Definition E.1. We define:

$$ $\displaystyle~{}\mathcal{S}_{i}:=\{r\in[m]:\mathbb{I}\{\mathsf{A}_{i,r}\}=0\}$ $\displaystyle~{}\mathcal{S}_{i}^{\bot}:=[m]/\mathcal{S}_{i}$ $$

###### Definition E.1 .

###### Definition E.2 .

### E.2 Sign Pattern

###### Definition E.3 .

If the following conditions hold:

- •
For any $w\in\mathbb{R}^{d}$.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
For $R>0$.
- •
For $k\in[d]$ and $r\in[m]$.

We define:

$$ $\displaystyle\mathsf{B}_{r,k}:=\{\exists w\in\mathbb{R}^{d}:|w_{k}-w_{r,k}(0)| \leq R,{\bf 1}_{w_{r,k}(0)-E(w_{r}(0))\geq 0}\neq{\bf 1}_{w_{k}-E(w)\geq 0}\}$ $$

###### Definition E.3 .

## Appendix F Straight-Through Estimator (STE)

### F.1 STE Functions

###### Definition F.1 .

If the following conditions hold:

- •
For a input vector $x\in\mathbb{R}^{d}$.
- •
For a hidden-layer weights $W\in\mathbb{R}^{d\times m}$ as Definition C.2.
- •
For a output-layer weights $a\in\mathbb{R}^{m}$ as Definition C.2.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let ${\sf ReLU}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition C.4.

We define:

$$ $\displaystyle f_{\rm ste}(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r},x\rangle)\geq 0}\cdot \langle w_{r},x\rangle\in\mathbb{R}$ $$

Then its compact form is given by

$$ $\displaystyle\mathsf{F}_{\rm ste}(t):=\begin{bmatrix}f_{\rm ste}(x_{1},W(t),a) ,f_{\rm ste}(x_{2},W(t),a),\cdots,f_{\rm ste}(x_{n},W(t),a)\end{bmatrix}^{\top }\in\mathbb{R}^{n}$ $$

###### Definition F.2 .

Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3. For any $t\geq 0$. We define:

$$ $\displaystyle\Delta W(t):=\sum_{i=1}^{n}(\mathsf{F}_{i}(t)-y_{i})\cdot\frac{ \mathrm{d}\mathsf{F}_{{\rm ste},i}(t)}{\mathrm{d}W(t)}$ $$

###### Definition F.1 .

###### Definition F.2 .

### F.2 Gradient Computation

###### Lemma F.3 .

If the following conditions hold:

- •
For $i\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{F}_{\rm ste}(t)$ be defined as Definition F.1.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
For $\kappa\in(0,1]$.

Then we have:

$$ $\displaystyle\frac{\mathrm{d}\mathsf{F}_{{\rm ste},i}(t)}{\mathrm{d}w_{r}(t)}= \kappa\frac{1}{\sqrt{m}}a_{r}\cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r }(t),x_{i}\rangle)\geq 0}\cdot x_{i}$ $$

###### Proof.

This proof follows from simple calculations.
∎

###### Lemma F.3 .

###### Proof.

## Appendix G Neural Tangent Kernel

### G.1 Kernel Function

###### Definition G.1 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
For $\kappa\in(0,1]$.

We define the kernel function as $H(t)\in\mathbb{R}^{n\times n}$, where its $(i,j)$-th entry is given by:

$$ $\displaystyle H_{i,j}(t):=\kappa^{2}\frac{1}{m}x_{i}^{\top}x_{j}\cdot\sum_{r=1 }^{m}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{j}\rangle)\geq 0}\in \mathbb{R}$ $$

###### Claim G.2 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
For $\kappa\in(0,1]$.

We first define the neural tangent network as $H^{*}:=H(0)\in\mathbb{R}^{n\times n}$, where its $(i,j)$-th entry is given by:

$$ $\displaystyle H_{i,j}^{*}:=$ $\displaystyle~{}H_{i,j}(0)$ $\displaystyle=$ $\displaystyle~{}\kappa^{2}\frac{1}{m}x_{i}^{\top}x_{j}\cdot\sum_{r=1}^{m}{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{j}\rangle)\geq 0}$ $\displaystyle\approx$ $\displaystyle~{}\kappa^{2}x_{i}^{\top}x_{j}\cdot\operatorname*{{\mathbb{E}}}_{ w_{r}\sim\mathcal{N}(0,\sigma^{2}\cdot I_{d})}[{\bf 1}_{\mathsf{dq}(\langle \widetilde{w}_{r}(0),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{\mathsf{dq}(\langle \widetilde{w}_{r}(0),x_{j}\rangle)\geq 0}]$ $$

###### Proof.

We have

$$ $\displaystyle H_{i,j}^{*}=$ $\displaystyle~{}H_{i,j}(0)$ $\displaystyle=$ $\displaystyle~{}\kappa^{2}\frac{1}{m}x_{i}^{\top}x_{j}\cdot\sum_{r=1}^{m}{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{j}\rangle)\geq 0}$ $\displaystyle\approx$ $\displaystyle~{}\kappa^{2}x_{i}^{\top}x_{j}\cdot\operatorname*{{\mathbb{E}}}_{ w_{r}\sim\mathcal{N}(0,\sigma^{2}\cdot I_{d})}[{\bf 1}_{\mathsf{dq}(\langle \widetilde{w}_{r}(0),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{\mathsf{dq}(\langle \widetilde{w}_{r}(0),x_{j}\rangle)\geq 0}]$ $$

where the first step follows from the definition of $H^{*}$, the second step follows from Definition G.1, the third step holds since $m\rightarrow+\infty$.
∎

###### Definition G.3 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.

We the pattern-changing kernel function as $H^{\bot}(t)\in\mathbb{R}^{n\times n}$, where its $(i,j)$-th entry is given by:

$$ $\displaystyle H_{i,j}^{\bot}(t):=\kappa^{2}\frac{1}{m}x_{i}^{\top}x_{j}\cdot \sum_{r\in\mathcal{S}_{i}^{\bot}}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r} (t),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t), x_{j}\rangle)\geq 0}\in\mathbb{R}$ $$

###### Definition G.1 .

###### Claim G.2 .

###### Proof.

###### Definition G.3 .

### G.2 Assumption: H ∗ superscript 𝐻 H^{*} italic_H start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is Positive Definite

###### Assumption G.4 .

Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Definition G.1. We assume that $H^{*}$ is positive definite (PD), where its minimum eigenvalue is given by:

$$ $\displaystyle\lambda:=\lambda_{\rm min}(H^{*})>0$ $$

###### Assumption G.4 .

### G.3 Kernel Convergence and PD Property

###### Lemma G.5 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
Denote $\lambda=\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2.
- •
$R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$.
- •
$\delta\in(0,0.1)$.

Then with probability at least $1-\delta$, we have:

- •
Part 1.
$\displaystyle\|H(t)-H^{*}\|_{F}\leq O\Big{(}n^{2}dR\delta^{-1}D\Big{)}$
- •
Part 2.
$\displaystyle\lambda_{\min}(H(t))\geq\lambda/2$

###### Proof.

Proof of Part 1.
Let $\mathsf{A}_{i,r}$ be defined as Definition E.1, we first show that when $\langle w_{r}(0),x\rangle\geq R+O\Big{(}d(D+R)\Big{)}$

$$ $\displaystyle\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)=$ $\displaystyle~{}\sqrt{V(w_{r}(0))}\cdot\langle\widetilde{w}_{r}(0),x_{i} \rangle+\langle E(w_{r}(0))\cdot{\bf 1}_{d},x_{i}\rangle$ $\displaystyle=$ $\displaystyle~{}\langle w_{r}(0),x_{i}\rangle+\langle u(w_{r}(0)),x_{i}\rangle$ $\displaystyle\geq$ $\displaystyle~{}\langle w_{r}(0),x_{i}\rangle-|\langle u(w_{r}(0)),x_{i}\rangle|$ $\displaystyle\geq$ $\displaystyle~{}R$ $$

where the first step follows from Definition D.5, the second step follows from Definition D.6. the third step follows from simple algebras, the last step follows from $\langle w_{r}(0),x\rangle\geq R+O\Big{(}d(D+R)\Big{)}$ and Lemma D.7.

Thus, for any $w\in\mathbb{R}^{d}$ that satisfies $\|w-w_{r}(0)\|_{2}\leq R$, we have:

$$ $\displaystyle\mathsf{dq}(\langle\widetilde{w},x_{i}\rangle)=$ $\displaystyle~{}\sqrt{V(w)}\cdot\langle\widetilde{w},x_{i}\rangle+\langle E(w) \cdot{\bf 1}_{d},x_{i}\rangle$ $\displaystyle=$ $\displaystyle~{}\langle w,x_{i}\rangle+\langle u(w),x_{i}\rangle$ $\displaystyle\geq$ $\displaystyle~{}\langle w,x_{i}\rangle-|\langle u(w),x_{i}\rangle|$ $\displaystyle\geq$ $\displaystyle~{}\langle w_{r}(0),x_{i}\rangle-\|w-w_{r}(0)\|_{2}-|\langle u(w) ,x_{i}\rangle|$ $\displaystyle\geq$ $\displaystyle~{}0$ $$

where the first step follows from Definition D.5, the second step follows from Definition D.6. the third step follows from simple algebras, the fourth step follows from Cauchy-Schwarz inequality and $\|x_{i}\|=1$, the last step follows from $\|w-w_{r}(0)\|_{2}\leq R$, $\langle w_{r}(0),x\rangle\geq R+O\Big{(}d(D+R)\Big{)}$ and Lemma D.7.

The above situation says:

$$ $\displaystyle\Pr\Big{[}\mathbb{I}\{\mathsf{A}_{i,r}\}=1]\leq$ $\displaystyle~{}\Pr[\langle w_{r}(0),x\rangle<R+O\Big{(}d(D+R)\Big{)}\Big{]}$ $\displaystyle\leq$ $\displaystyle~{}\frac{4R+O\Big{(}d(D+R)\Big{)}}{\sqrt{2\pi}}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}dR(D+R)\Big{)}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}dRD\Big{)}$ (4) $$

where the second step follows from anti-concentration of Gaussian (Fact B.3) and Fact B.4, the third step follows from simple algebras and the last step follows from plugging $R\leq D$.

For $i,j\in[n]$, we have

$$ $\displaystyle~{}\operatorname*{{\mathbb{E}}}[|H_{i,j}(t)-H_{i,j}^{*}|]$ $\displaystyle=$ $\displaystyle~{}\operatorname*{{\mathbb{E}}}\Big{[}\Big{|}\kappa^{2}\frac{1}{m }x_{i}^{\top}x_{j}\sum_{r=1}^{m}({\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r} (t),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t), x_{j}\rangle)\geq 0}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i} \rangle)\geq 0}\cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{j} \rangle)\geq 0})\Big{|}\Big{]}$ $\displaystyle=$ $\displaystyle~{}\kappa^{2}\frac{1}{m}\sum_{r=1}^{m}\operatorname*{{\mathbb{E}} }\Big{[}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{j}\rangle)\geq 0}-{ \bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)\geq 0}\cdot{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{j}\rangle)\geq 0}\Big{]}$ $\displaystyle\leq$ $\displaystyle~{}\kappa^{2}\frac{1}{m}\sum_{r=1}^{m}\operatorname*{{\mathbb{E}} }\Big{[}\mathbb{I}\{A_{i,r}\cup A_{j,r}\}\Big{]}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\kappa^{2}dRD\Big{)}$ (5) $$

where the first step follows from Definition G.1 and Claim G.2, the second and third step follows from simple algebras, the last step follows from Eq. (G.3).

Then we have:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{i=1}^{n}\sum_{j=1}^{n}|H_{i,j} (t)-H_{i,j}^{*}|]=$ $\displaystyle~{}\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname*{{\mathbb{E}}}[|H_{i ,j}(t)-H_{i,j}^{*}|]$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\kappa^{2}n^{2}dRD\Big{)}$ $$

where the first step follows from simple algebras, the second step follows from Eq. (G.3).

Hence, by Markov’s inequality (Lemma B.15), with probability at least $1-\delta$, we have:

$$ $\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}|H_{i,j}(t)-H_{i,j}^{*}|\leq$ $\displaystyle~{}\frac{\operatorname*{{\mathbb{E}}}[\sum_{i=1}^{n}\sum_{j=1}^{n }|H_{i,j}(t)-H_{i,j}^{*}|]}{\delta}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\kappa^{2}n^{2}dR\delta^{-1}(D+R)\Big{)}$ $$

We obtain:

$$ $\displaystyle\|H(t)-H^{*}\|_{F}\leq$ $\displaystyle~{}\|H(t)-H^{*}\|_{1}$ $\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{n}\sum_{j=1}^{n}|H_{i,j}(t)-H_{i,j}^{*}|$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\kappa^{2}n^{2}dR\delta^{-1}D\Big{)}$ $$

Now following Fact B.5, we have:

$$ $\displaystyle\lambda_{\min}(H(t))\geq$ $\displaystyle~{}\lambda_{\min}(H^{*})-\|H(t)-H^{*}\|_{F}$ $\displaystyle\geq$ $\displaystyle~{}\lambda-O\Big{(}\kappa^{2}n^{2}dR\delta^{-1}D\Big{)}$ $\displaystyle\geq$ $\displaystyle~{}\lambda/2$ $$

where the last step follows from choosing $R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$.
∎

###### Lemma G.5 .

###### Proof.

## Appendix H Training Dynamic

### H.1 Decompose Loss

###### Definition H.1 .

Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3. For any $t\geq 0$. Let $u:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ be defined as Definition D.6. For $r\in[m]$.
We define:

$$ $\displaystyle\mathsf{u}_{r}(t):=u(w_{r}(t))$ $$

Then the $\mathsf{F}_{i}(t),\forall i\in[n]$ can be given by:

$$ $\displaystyle\mathsf{F}_{i}(t)=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \cdot\Big{(}\langle w_{r}(t),x_{i}\rangle+\langle\mathsf{u}_{r}(t),x_{i} \rangle\Big{)}$ $$

###### Claim H.2 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
Define
$\displaystyle C_{1}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}}a_{r}({\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle)\cdot(\mathsf{F}_{i}(t)-y_{i})$
- •
Define
$\displaystyle C_{2}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}^{\bot}}a_{r}\Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}
\rangle)\geq 0}\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_{i}(t)-y
_{i})$
- •
Define
$\displaystyle C_{3}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r=1}^{m}a_{r}\Big
{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle\mathsf{u}_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle\mathsf{u}_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_
{i}(t)-y_{i})$
- •
Define
$\displaystyle C_{4}:=\frac{1}{2}\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_{2}^{2}$
- •
For $\kappa\in(0,1]$.

Then we have:

$$ $\displaystyle{\sf L}(t+1)=L(t)+C_{1}+C_{2}+C_{3}+C_{4}$ $$

###### Proof.

We have

$$ $\displaystyle{\sf L}(t+1)=$ $\displaystyle~{}\frac{1}{2}\cdot\|\mathsf{F}(t+1)-y\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{1}{2}\cdot\|(\mathsf{F}(t)-y)-(\mathsf{F}(t)-\mathsf{F}( t+1))\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{1}{2}\cdot(\|\mathsf{F}(t)-y\|_{2}^{2}-2\langle\mathsf{F }(t)-y,\mathsf{F}(t)-\mathsf{F}(t+1)\rangle+\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_ {2}^{2})$ $\displaystyle=$ $\displaystyle~{}{\sf L}(t)-\langle\mathsf{F}(t)-y,\mathsf{F}(t)-\mathsf{F}(t+1 )\rangle+\frac{1}{2}\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_{2}^{2}$ $$

these steps follow from simple algebras and Definition C.9.

Then for $i\in[n]$

$$ $\displaystyle~{}\mathsf{F}_{i}(t)-\mathsf{F}_{i}(t+1)$ $\displaystyle=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot\Big{(} \langle w_{r}(t),x_{i}\rangle+\langle\mathsf{u}_{r}(t),x_{i}\rangle\Big{)}$ $\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}\rangle)\geq 0}\cdot\Big{(} \langle w_{r}(t+1),x_{i}\rangle+\langle\mathsf{u}_{r}(t+1),x_{i}\rangle\Big{)}$ $\displaystyle=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\cdot\Bigg{(}{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot\Big{(} \langle w_{r}(t),x_{i}\rangle+\langle\mathsf{u}_{r}(t),x_{i}\rangle\Big{)}$ $\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i} \rangle)\geq 0}\cdot\Big{(}\langle w_{r}(t+1),x_{i}\rangle+\langle\mathsf{u}_{ r}(t+1),x_{i}\rangle\Big{)}\Bigg{)}$ $\displaystyle=$ $\displaystyle~{}M_{1,i}+M_{2,i}+M_{3,i}$ $$

where these steps follows from simple algebras and defining:

$$ $\displaystyle M_{1,i}:=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r\in\mathcal{S}_{i}}a_{r}\Big{(} {\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot \langle w_{r}(t),x_{i}\rangle-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+ 1),x_{i}\rangle)\geq 0}\cdot\langle w_{r}(t+1),x_{i}\rangle\Big{)}$ $\displaystyle M_{2,i}:=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r\in\mathcal{S}_{i}^{\bot}}a_{r} \Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \cdot\langle w_{r}(t),x_{i}\rangle-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{ r}(t+1),x_{i}\rangle)\geq 0}\cdot\langle w_{r}(t+1),x_{i}\rangle\Big{)}$ $\displaystyle M_{3,i}:=$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\Big{(}{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot\langle \mathsf{u}_{r}(t),x_{i}\rangle-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t +1),x_{i}\rangle)\geq 0}\cdot\langle\mathsf{u}_{r}(t+1),x_{i}\rangle\Big{)}$ $$

Thus, by the definitions in Lemma conditions, we can show that

$$ $\displaystyle{\sf L}(t+1)=$ $\displaystyle~{}{\sf L}(t)+C_{1}+C_{2}+C_{3}+C_{4}$ $$

∎

###### Definition H.1 .

###### Claim H.2 .

###### Proof.

### H.2 Bounding C 1 subscript 𝐶 1 C_{1} italic_C start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT

###### Lemma H.3 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{\bot}(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.3.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
$\delta\in(0,0.1)$.
- •
Define
$\displaystyle C_{1}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}}a_{r}({\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle)\cdot(\mathsf{F}_{i}(t)-y_{i})$
- •
For $\kappa\in(0,1]$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle C_{1}\leq\Big{(}-\eta\kappa\lambda+O(\eta\kappa\frac{n^{2}dRD}{ \delta})\Big{)}\cdot{\sf L}(t)$ $$

###### Proof.

We have:

$$ $\displaystyle C_{1}=$ $\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{ i}}a_{r}({\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \langle w_{r}(t),x_{i}\rangle$ $\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i} \rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle)\cdot(\mathsf{F}_{i}(t)-y_{i})$ $\displaystyle=$ $\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{ i}}a_{r}(\langle w_{r}(t),x_{i}\rangle-\langle w_{r}(t+1),x_{i}\rangle)\cdot( \mathsf{F}_{i}(t)-y_{i})$ $\displaystyle=$ $\displaystyle~{}-\kappa^{2}\eta\frac{1}{m}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_ {i}}(\mathsf{F}_{i}(t)-y_{i})\cdot(\sum_{j=1}^{n}x_{i}^{\top}x_{j}\cdot{\bf 1} _{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{j}\rangle)\geq 0}\cdot(\mathsf{F}_{ j}(t)-y_{j}))$ $\displaystyle=$ $\displaystyle~{}-\eta(\mathsf{F}(t)-y)^{\top}\cdot(H(t)-H^{\bot}(t))\cdot( \mathsf{F}(t)-y)$ $\displaystyle=$ $\displaystyle~{}-\eta(\mathsf{F}(t)-y)^{\top}\cdot H(t)\cdot(\mathsf{F}(t)-y)+ \eta(\mathsf{F}(t)-y)^{\top}\cdot H^{\bot}(t)\cdot(\mathsf{F}(t)-y)$ $\displaystyle\leq$ $\displaystyle~{}-\eta\lambda/2\cdot\|\mathsf{F}(t)-y\|_{2}^{2}+\eta\|H^{\bot}( t)\|_{F}\cdot\|\mathsf{F}(t)-y\|_{2}$ $\displaystyle=$ $\displaystyle~{}(-\eta\lambda+\|H^{\bot}(t)\|_{F})\cdot{\sf L}(t)$ $$

where the first step follows from definition of $C_{1}$, the second step follows from the definition of $\mathcal{S}_{i}$ (Definition E.2), the third step follows from Definition C.8 and Definition F.2, the fourth step follows from Definition G.1, Definition G.3 and simple algebras, the fifth step follows from simple algebras, the sixth step follows from Lemma G.5 and simple algebras, the last step follows from Definition C.9.

Besides, we have

$$ $\displaystyle|H_{i,j}^{\bot}|=$ $\displaystyle~{}|\frac{1}{m}x_{i}^{\top}x_{j}\cdot\sum_{r\in\mathcal{S}_{i}^{ \bot}}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0} \cdot{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{j}\rangle)\geq 0}|$ $\displaystyle\leq$ $\displaystyle~{}|\frac{1}{m}x_{i}^{\top}x_{j}\cdot|\mathcal{S}_{i}^{\bot}||$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{m}|\mathcal{S}_{i}^{\bot}|$ (6) $$

where the first step follows from Definition G.3, the second step follows from simple algebras, the third step follows from $\|x\|_{i}=1$.

We give that

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{i=1}^{n}|\mathcal{S}_{i}^{\bot }|]=$ $\displaystyle~{}\sum_{i=1}^{n}\sum_{r=1}^{m}\Pr[\mathbb{I}\{\mathsf{A}_{i,r}\} =1]$ $\displaystyle\leq$ $\displaystyle~{}O(mndRD)$ $$

where the first step follows from simple algebras, the second step follows from Eq. (G.3).

Hence, by Markov’s inequality (Lemma B.15), we have

$$ $\displaystyle\sum_{i=1}^{n}|\mathcal{S}_{i}^{\bot}|\leq O(\frac{mndRD}{\delta})$ (7) $$

Thus,

$$ $\displaystyle\|H^{\bot}\|_{F}\leq$ $\displaystyle~{}\sum_{i=1}^{n}\sum_{j=1}^{n}|H_{i,j}^{\bot}|$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{m}\sum_{i=1}^{n}\sum_{j=1}^{n}|\mathcal{S}_{i}^{\bot}|$ $\displaystyle\leq$ $\displaystyle~{}O(\frac{n^{2}dRD}{\delta})$ $$

where the first step follows from simple algebras, the second step follows from Eq. (H.2), the last step follows from simple algebras and Eq. (7).

Finally, we conclude all the results, we have:

$$ $\displaystyle C_{1}\leq\Big{(}-\eta\lambda+O(\eta\frac{n^{2}dRD}{\delta})\Big{ )}\cdot{\sf L}(t)$ $$

∎

###### Lemma H.3 .

###### Proof.

### H.3 Bounding C 2 subscript 𝐶 2 C_{2} italic_C start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT

###### Lemma H.4 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{\bot}(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.3.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
$\delta\in(0,0.1)$.
- •
Define
$\displaystyle C_{2}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}^{\bot}}a_{r}\Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}
\rangle)\geq 0}\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_{i}(t)-y
_{i})$
- •
$\kappa\in(0,1]$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle|C_{2}|\leq O(\eta\kappa\frac{n^{1.5}dRD}{\delta})\cdot{\sf L}(t)$ $$

###### Proof.

We have:

$$ $\displaystyle|C_{2}|=$ $\displaystyle~{}|\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{ i}^{\bot}}a_{r}\Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i} \rangle)\geq 0}\langle w_{r}(t),x_{i}\rangle$ $\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i} \rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_{i}(t)-y _{i})|$ $\displaystyle\leq$ $\displaystyle~{}|\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}|\mathcal{S}_{i^{\bot}} |\cdot|\langle w_{r}(t),x_{i}\rangle-\langle w_{r}(t+1),x_{i}\rangle|\cdot( \mathsf{F}_{i}(t)-y_{i})|$ $\displaystyle\leq$ $\displaystyle~{}|\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}|\mathcal{S}_{i^{\bot}} |\cdot\|\eta\Delta w_{r}(t)\|_{2}\cdot(\mathsf{F}_{i}(t)-y_{i})|$ $\displaystyle\leq$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}|\mathcal{S}_{i^{\bot}}| \cdot\|\eta\Delta w_{r}(t)\|_{2}\|\mathsf{F}(t)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\eta\kappa\frac{\sqrt{n}}{m}\sum_{i=1}^{n}|\mathcal{S}_{i^{ \bot}}|\cdot\|\mathsf{F}(t)-y\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}O(\eta\kappa\frac{n^{1.5}dRD}{\delta})\cdot{\sf L}(t)$ $$

where the first step follows from the definition of $C_{2}$, the second step follows from Fact B.2 and Definition E.2 ($S_{i}^{\bot}$), the third step follows from simple algebras and Definition C.8, the fourth step follows from simple algebras, the fifth step follows from Lemma I.4, last step follows from Eq. (7) and Definition C.9.
∎

###### Lemma H.4 .

###### Proof.

### H.4 Bounding C 3 subscript 𝐶 3 C_{3} italic_C start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT

###### Lemma H.5 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{\bot}(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.3.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
$\delta\in(0,0.1)$.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.
- •
Define
$\displaystyle C_{3}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r=1}^{m}a_{r}\Big
{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle\mathsf{u}_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle\mathsf{u}_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_
{i}(t)-y_{i})$
- •
$\kappa\in(0,1]$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle C_{3}\leq$ $\displaystyle~{}O\Big{(}\eta\kappa\frac{R^{2}n^{1.5}\sqrt{d}}{\delta\epsilon \sqrt{m}}D\Big{)}\cdot{\sf L}(t)$ $$

###### Proof.

We have:

$$ $\displaystyle~{}|\mathsf{u}_{r,k}(t)-\mathsf{u}_{r,k}(t+1)|$ $\displaystyle=$ $\displaystyle~{}|\sqrt{V(w_{r}(t))}\cdot\widetilde{w}_{r,k}(t)+E(w_{r}(t))-w_{ r,k}(t)$ $\displaystyle~{}-\sqrt{V(w_{r}(t+1))}\cdot\widetilde{w}_{r,k}(t+1)-E(w_{r}(t+1 ))+w_{r,k}(t+1)|$ $\displaystyle\leq$ $\displaystyle~{}|\widetilde{w}_{r,k}(t)\sqrt{V(w_{r}(t))}-\widetilde{w}_{r,k}( t+1)\sqrt{V(w_{r}(t+1))}|$ $\displaystyle~{}+|\eta E(\Delta w_{r}(t))|+|\eta\Delta w_{r,k}(t)|$ $\displaystyle\leq$ $\displaystyle~{}\Big{|}\widetilde{w}_{r,k}(t+1)(\sqrt{V(w_{r}(t))}-\sqrt{V(w_{ r}(t+1))})\Big{|}$ $\displaystyle~{}+\Big{|}\sqrt{V(w_{r}(t))}(\widetilde{w}_{r,k}(t)-\widetilde{w }_{r,k}(t+1))\Big{|}+|\eta E(\Delta w_{r}(t))|+|\eta\Delta w_{r,k}(t)|$ $\displaystyle=$ $\displaystyle~{}Q_{1,r,k}+Q_{2,r,k}+Q_{3,r,k}+Q_{4,r,k}$ (8) $$

where the first step follows from Definition H.1, the second step follows from triangle inequality and Definition C.8, the third step follows from simple algebras, the last step follows from defining:

$$ $\displaystyle Q_{1,r,k}:=$ $\displaystyle~{}\Big{|}\widetilde{w}_{r,k}(t+1)(\sqrt{V(w_{r}(t))}-\sqrt{V(w_{ r}(t+1))})\Big{|}$ $\displaystyle Q_{2,r,k}:=$ $\displaystyle~{}\Big{|}\sqrt{V(w_{r}(t))}(\widetilde{w}_{r,k}(t)-\widetilde{w} _{r,k}(t+1))\Big{|}$ $\displaystyle Q_{3,r,k}:=$ $\displaystyle~{}|\eta E(\Delta w_{r}(t))|$ $\displaystyle Q_{4,r,k}:=$ $\displaystyle~{}|\eta\Delta w_{r,k}(t)|$ $$

Bounding $Q_{1,r,k}$.

We have:

$$ $\displaystyle Q_{1,r,k}=$ $\displaystyle~{}\Big{|}\widetilde{w}_{r,k}(t+1)(\sqrt{V(w_{r}(t))}-\sqrt{V(w_{ r}(t+1))})\Big{|}$ $\displaystyle=$ $\displaystyle~{}\Big{|}(\sqrt{V(w_{r}(t))}-\sqrt{V(w_{r}(t+1))})\Big{|}$ $\displaystyle\leq$ $\displaystyle~{}\|w_{r}(t)-E(w_{r}(t)){\bf 1}_{d}-w_{r}(t+1)+E(w_{r}(t+1)){\bf 1 }_{d}\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\|\eta\Delta w_{r}(t)\|_{2}+\sqrt{d}\cdot|\eta E(\Delta w_{r}( t))|$ $\displaystyle\leq$ $\displaystyle~{}\eta\frac{(1+\sqrt{d})\sqrt{n}}{\sqrt{m}}\|\mathsf{F}(t)-y\|_{2}$ $$

where the first step follows from the definition of $Q_{1,r,k}$, the second step follows from $\widetilde{w}_{r,k}(t+1)\in\{-1,+1\}$, the third step follows from Definition D.3 and reverse triangle inequality, the fourth step follows from $\|{\bf 1}_{d}\|_{2}=\sqrt{d}$ and Definition C.8, the last step follows from Lemma I.4.

Bounding $Q_{2,r,k}$.

We have:

$$ $\displaystyle Q_{2,r,k}=$ $\displaystyle~{}\Big{|}\sqrt{V(w_{r}(t))}(\widetilde{w}_{r,k}(t)-\widetilde{w} _{r,k}(t+1))\Big{|}$ $\displaystyle=$ $\displaystyle~{}|\sqrt{V(w_{r}(t))}|\cdot|\widetilde{w}_{r,k}(t)-\widetilde{w} _{r,k}(t+1)|$ $\displaystyle\leq$ $\displaystyle~{}\|w_{r}(t)-E(w_{r}(t)){\bf 1}_{d}\|\cdot|\widetilde{w}_{r,k}(t )-\widetilde{w}_{r,k}(t+1)|$ $\displaystyle\leq$ $\displaystyle~{}O(\sqrt{d}D+R)\cdot|\widetilde{w}_{r,k}(t)-\widetilde{w}_{r,k} (t+1)|$ (9) $$

where the first step follows from the definition of $Q_{2,r,k}$, the second step follows from simple algebras, the third step follows from Definition D.3, the last step follows from Part 2 of Lemma I.6.

At the same time, we can show that

$$ $\displaystyle~{}\operatorname*{{\mathbb{E}}}[|\widetilde{w}_{r,k}(t)- \widetilde{w}_{r,k}(t+1)|]$ $\displaystyle\leq$ $\displaystyle~{}2(1-\Pr[\mathbb{I}\{\mathsf{B}_{r,k}\}=0\cap\mathbb{I}\{|w_{r, k}(t)-E(w_{r}(t))|\geq|\eta\Delta w_{r,k}(t)-\eta E(\Delta w_{r}(t))|\}])$ $\displaystyle\leq$ $\displaystyle~{}2(1-\Pr[z\geq 2R+2\eta\frac{\sqrt{n}}{\sqrt{m}}\|\mathsf{F}(t) -y\|_{2}])$ $\displaystyle=$ $\displaystyle~{}2\Pr[z\leq 2R+2\eta\frac{\sqrt{n}}{\sqrt{m}}\|\mathsf{F}(t)-y \|_{2}]$ $\displaystyle\leq$ $\displaystyle~{}O(\eta\frac{\sqrt{n}}{\sqrt{m}})\|\mathsf{F}(t)-y\|_{2}+O(1)R$ $\displaystyle\leq$ $\displaystyle~{}O(\eta\frac{R\sqrt{n}}{\epsilon\sqrt{m}})\|\mathsf{F}(t)-y\|_{2}$ $$

where the first step follows from Definition E.3 and simple algebras, the second step follows from defining:

$$ $\displaystyle z:=$ $\displaystyle~{}w_{r,k}(0)-E(w_{r}(0))$ $\displaystyle=$ $\displaystyle~{}\frac{d-1}{d}w_{r,k}-\frac{1}{d}\sum_{k^{\prime}\in[d]/\{k\}}w _{r,k^{\prime}}(0)$ $\displaystyle\sim$ $\displaystyle~{}\mathcal{N}\Big{(}0,\sigma^{2}\sqrt{\frac{d-1}{d}}\cdot I_{d} \Big{)}$ $$

and the last steps follow from the anti-concentration of the Gaussian variable (Fact B.3) and $\|\mathsf{F}(t)-y\|_{2}\geq\epsilon$ by Lemma condition.

Following Markov’s inequality, we get:

$$ $\displaystyle|\widetilde{w}_{r,k}(t)-\widetilde{w}_{r,k}(t+1)|\leq O(\eta\frac {R\sqrt{n}}{\delta\epsilon\sqrt{m}})\|\mathsf{F}(t)-y\|_{2}$ (10) $$

Hence,

$$ $\displaystyle Q_{2,r,k}\leq O\Big{(}\eta\frac{R^{2}\sqrt{nd}}{\delta\epsilon \sqrt{m}}D\Big{)}\|\mathsf{F}(t)-y\|_{2}$ $$

where this step follows from Eq. (10) and Eq. (H.4).

Bounding $Q_{3,r,k}$ and $Q_{4,r,k}$.

We can show that $Q_{3,r,k}\leq\eta\frac{\sqrt{n}}{\sqrt{m}}\cdot\|\mathsf{F}(t)-y\|_{2}$ and $Q_{4,r,k}\leq\eta\frac{\sqrt{n}}{\sqrt{m}}\cdot\|\mathsf{F}(t)-y\|_{2}$ by following Lemma I.4.

Combination.
We have:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[C_{3}]=0$ $$

where this step follows from the symmetry of $a$.

Also

$$ $\displaystyle~{}\Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i} \rangle)\geq 0}\langle\mathsf{u}_{r}(t),x_{i}\rangle-{\bf 1}_{\mathsf{dq}( \langle\widetilde{w}_{r}(t+1),x_{i}\rangle)\geq 0}\langle\mathsf{u}_{r}(t+1),x _{i}\rangle\Big{)}$ $\displaystyle\leq$ $\displaystyle~{}|\langle\mathsf{u}_{r}(t),x_{i}\rangle-\langle\mathsf{u}_{r}(t +1),x_{i}\rangle|$ $\displaystyle=$ $\displaystyle~{}Q_{1,r,k}+Q_{2,r,k}+Q_{3,r,k}+Q_{4,r,k}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\eta\frac{R^{2}\sqrt{nd}}{\delta\epsilon\sqrt{m}}D\Big {)}\|\mathsf{F}(t)-y\|_{2}$ (11) $$

where the first step follows from ${\sf ReLU}$ is a $1$-Lipschitz function (Fact B.2), the last step follows from simple algebras and the combination of these terms.

By Hoeffding’s inequality (Lemma B.8), with a probability at least $1-\delta$, we have:

$$ $\displaystyle|C_{3}|\leq$ $\displaystyle~{}O\Big{(}\eta\kappa\frac{R^{2}n^{1.5}\sqrt{d}}{\delta\epsilon \cdot m}\sqrt{m}D\Big{)}\|\mathsf{F}(t)-y\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\eta\kappa\frac{R^{2}n^{1.5}\sqrt{d}}{\delta\epsilon \sqrt{m}}D\Big{)}\cdot{\sf L}(t)$ $$

∎

###### Lemma H.5 .

###### Proof.

### H.5 Bounding C 4 subscript 𝐶 4 C_{4} italic_C start_POSTSUBSCRIPT 4 end_POSTSUBSCRIPT

###### Lemma H.6 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{\bot}(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.3.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
$\delta\in(0,0.1)$.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.
- •
Define
$\displaystyle C_{4}:=\frac{1}{2}\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_{2}^{2}$

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle|C_{4}|\leq$ $\displaystyle~{}O\Big{(}\eta^{2}\kappa^{2}\frac{R^{4}n^{2}d}{\delta^{2} \epsilon^{2}m}D^{2}\Big{)}{\sf L}(t)$ $$

###### Proof.

We have:

$$ $\displaystyle~{}|{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle )\geq 0}(\langle w_{r}(t),x_{i}\rangle+\langle\mathsf{u}_{r}(t),x_{i}\rangle)$ $\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i} \rangle)\geq 0}(\langle w_{r}(t+1),x_{i}\rangle+\langle\mathsf{u}_{r}(t+1),x_{ i}\rangle)|$ $\displaystyle\leq$ $\displaystyle~{}|\langle\eta\Delta w_{r}(t),x_{i}\rangle+\langle\mathsf{u}_{r} (t),x_{i}\rangle-\langle\mathsf{u}_{r}(t+1),x_{i}\rangle|$ $\displaystyle\leq$ $\displaystyle~{}U_{1,i,r}+U_{2,i,r}$ $$

where the first step follows from Fact B.2, the fifth step follows from Definition C.8, and the last step follows from defining:

$$ $\displaystyle U_{1,i,r}:=$ $\displaystyle~{}\langle\eta\Delta w_{r}(t),x_{i}\rangle$ $\displaystyle U_{2,i,r}:=$ $\displaystyle~{}\langle\mathsf{u}_{r}(t),x_{i}\rangle-\langle\mathsf{u}_{r}(t+ 1),x_{i}\rangle$ $$

For the first term $U_{1,i,r}$, we have:

$$ $\displaystyle|U_{1,i,r}|\leq\eta\frac{\sqrt{n}}{\sqrt{m}}\|\mathsf{F}(t)-y\|_{2}$ $$

this step holds since Part 2 of Lemma I.4.

For the second term $U_{2,i,r}$, we have:

$$ $\displaystyle|U_{2,i,r}|\leq O\Big{(}\eta\frac{R^{2}\sqrt{nd}}{\delta\epsilon \sqrt{m}}D\Big{)}\|\mathsf{F}(t)-y\|_{2}$ $$

this step follows from Eq. (H.4) and Eq. (H.4).

Thus, we have:

$$ $\displaystyle C_{4}=$ $\displaystyle~{}\frac{1}{2}\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{1}{2}\sum_{i=1}^{n}(\mathsf{F}_{i}(t)-\mathsf{F}_{i}(t+1 ))^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{1}{2}\sum_{i=1}^{n}\Big{(}\kappa\frac{1}{\sqrt{m}}\sum_{ r=1}^{m}a_{r}(U_{1,i,r}+U_{2,i,r})\Big{)}^{2}$ $$

Combining two terms, then by Hoeffing inequality (Lemma B.8), with a probability at least $1-\delta$, $\operatorname*{{\mathbb{E}}}[\sum_{r=1}^{m}a_{r}(U_{1,i,r}+U_{2,i,r})]=1$, we have:

$$ $\displaystyle|C_{4}|\leq O\Big{(}\eta^{2}\kappa^{2}\frac{R^{4}n^{2}d}{\delta^{ 2}\epsilon^{2}m}D^{2}\Big{)}\|\mathsf{F}(t)-y\|_{2}^{2}\leq$ $\displaystyle~{}O\Big{(}\eta^{2}\kappa^{2}\frac{R^{4}n^{2}d}{\delta^{2} \epsilon^{2}m}D^{2}\Big{)}{\sf L}(t)$ $$

∎

###### Lemma H.6 .

###### Proof.

## Appendix I Inductions

### I.1 Main Result 1: Training Convergence Guarantee

###### Theorem I.1 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
Given a expected error $\epsilon>0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
$\delta\in(0,0.1)$, $\kappa\in(0,1]$.
- •
Choose $m\geq\Omega\Big{(}\lambda^{-8}\frac{n^{12}d^{8}}{\delta^{4}\epsilon^{4}}\Big{)}$.
- •
Choose $\eta\leq O\Big{(}\lambda\frac{\delta}{\kappa^{2}n^{2}dD}\Big{)}$.
- •
Choose $T\geq\Omega\Big{(}\frac{1}{\eta\lambda}\log(\epsilon^{-1}ndD^{2})\Big{)}$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle{\sf L}(T)\leq\epsilon$ $$

###### Proof.

Choice of $m$.

Following Lemma I.2, we have

$$ $\displaystyle m\geq\Omega\Big{(}\lambda^{-4}\kappa^{4}\frac{R^{8}n^{6}d^{2}}{ \delta^{4}\epsilon^{4}}\Big{)}$ $$

Particularly, following Claim I.5, we have:

$$ $\displaystyle R\leq$ $\displaystyle~{}\frac{4\sqrt{n}}{\lambda\sqrt{m}}\|\mathsf{F}(0)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{4\sqrt{n}}{\lambda\sqrt{m}}\cdot O\Big{(}\sqrt{n}dD^{2} \Big{)}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\frac{nd}{\lambda\sqrt{m}}D^{2}\Big{)}$ $$

where the first step follows from Claim I.5, the second step follows from Lemma I.3, the third step follows from simple algebras.

Besides, by Lemma I.2, we need that

$$ $\displaystyle R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$ $$

where the second step follows from Definition B.16.

Thus, showing that $D^{3}\leq O(m^{\frac{1}{4}})$ and $\kappa\leq 1$, we plug $m$ as follows:

$$ $\displaystyle m\geq\Omega\Big{(}\lambda^{-8}\frac{n^{12}d^{8}}{\delta^{4} \epsilon^{4}}\Big{)}$ $$

Choice of $\eta$.
We have

$$ $\displaystyle\|\eta\Delta w_{r}(0)\|_{2}\leq$ $\displaystyle~{}\eta\frac{\sqrt{n}}{\sqrt{m}}\|\mathsf{F}(0)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\eta\frac{\sqrt{n}}{\sqrt{m}}O\Big{(}\sqrt{n}dD^{2}\Big{)}$ $\displaystyle\leq$ $\displaystyle~{}R$ $$

where the first step follows from Part 2 of Lemma I.4, the second step follows from Lemma I.3, the third step follows from plugging $\eta\leq O\Big{(}\lambda\frac{\delta}{\kappa n^{2}dD}\Big{)}$ and $m\geq\Omega\Big{(}\lambda^{-8}\frac{n^{12}d^{8}}{\delta^{4}\epsilon^{4}}\Big{)}$.

Choice of $T$.
We have:

$$ $\displaystyle{\sf L}(T)\leq\epsilon\iff$ $\displaystyle~{}(1-\eta\lambda/2)^{T}{\sf L}(0)\leq\epsilon$ $\displaystyle\iff$ $\displaystyle~{}(1-\eta\lambda/2)^{T}O\Big{(}\sqrt{n}dD^{2}\Big{)}\leq\epsilon$ $\displaystyle\iff$ $\displaystyle~{}(1-\eta\lambda/2)^{T}\leq O\Big{(}\frac{\epsilon}{\sqrt{n}dD^{ 2}}\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}T\geq\Omega\Big{(}\log(\frac{\epsilon}{\sqrt{n}dD^{2}})/\log(1 -\eta\lambda/2)\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}T\geq\Omega\Big{(}-\frac{1}{\eta\lambda}\log(\frac{\epsilon}{ \sqrt{n}dD^{2}})\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}T\geq\Omega\Big{(}\frac{1}{\eta\lambda}\log(\epsilon^{-1}ndD^{ 2})\Big{)}$ $$

where the first step follows from Lemma I.2, the second step follows from Lemma I.3, the third and fourth steps follow from simple algebras, the fifth step follows from Fact B.6, the sixth step follows from simple algebras.
∎

###### Theorem I.1 .

###### Proof.

### I.2 Induction for Loss

###### Lemma I.2 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let $H(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.1.
- •
Let $H^{\bot}(t)\in\mathbb{R}^{n\times n}$ be defined as Definition G.3.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
$\delta\in(0,0.1)$.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.
- •
$m\geq\Omega\Big{(}\lambda^{-4}\kappa^{4}\frac{R^{8}n^{6}d^{2}}{\delta^{4}
\epsilon^{4}}\Big{)}$.
- •
$R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$.
- •
Define
$\displaystyle C_{1}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}}a_{r}({\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle)\cdot(\mathsf{F}_{i}(t)-y_{i})$
- •
Define
$\displaystyle C_{2}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r\in\mathcal{S}_{
i}^{\bot}}a_{r}\Big{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}
\rangle)\geq 0}\langle w_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle w_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_{i}(t)-y
_{i})$
- •
Define
$\displaystyle C_{3}:=$
$\displaystyle~{}-\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\sum_{r=1}^{m}a_{r}\Big
{(}{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}
\langle\mathsf{u}_{r}(t),x_{i}\rangle$
$\displaystyle~{}-{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t+1),x_{i}
\rangle)\geq 0}\langle\mathsf{u}_{r}(t+1),x_{i}\rangle\Big{)}\cdot(\mathsf{F}_
{i}(t)-y_{i})$
- •
Define
$\displaystyle C_{4}:=\frac{1}{2}\|\mathsf{F}(t)-\mathsf{F}(t+1)\|_{2}^{2}$
- •
$\delta\in(0,1]$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle{\sf L}(t+1)\leq(1-\lambda/2\eta)\cdot{\sf L}(t)$ $$

Moreover, we can show that:

$$ $\displaystyle{\sf L}(t)\leq(1-\lambda/2\eta)^{t}\cdot{\sf L}(0)$ $$

###### Proof.

We have:

$$ $\displaystyle{\sf L}(t+1)\leq$ $\displaystyle~{}{\sf L}(t)+\Big{(}-\eta\lambda+O(\eta\frac{n^{2}dRD}{\delta})+ O(\eta\kappa\frac{n^{1.5}dRD}{\delta})$ $\displaystyle~{}+O(\eta\kappa\frac{R^{2}n^{1.5}\sqrt{d}}{\delta\epsilon\sqrt{m }}D)+O(\eta^{2}\kappa^{2}\frac{R^{4}n^{2}d}{\delta^{2}\epsilon^{2}m}D^{2}\Big{ )}\cdot{\sf L}(t)$ $\displaystyle\leq$ $\displaystyle~{}{\sf L}(t)+\Big{(}-\eta\lambda+\frac{1}{8}\eta\lambda+\frac{1} {8}\eta\lambda+\frac{1}{8}\eta\lambda+\frac{1}{8}\eta\lambda\Big{)}\cdot{\sf L }(t)$ $\displaystyle\leq$ $\displaystyle~{}(1-\eta\lambda/2){\sf L}(t)$ $$

where the first step follows from Claim H.2, Lemma H.3, Lemma H.4, Lemma H.5, Lemma H.6 and $\eta\lambda\leq 1$, the second step follows from the choice of $R$ and $m$, the last step follows from simple algebras.

Choice of $R$.
We have:

$$ $\displaystyle R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$ (12) $$

where this step is following the combination of Lemma G.5 and $O(\eta\frac{\kappa^{2}n^{2}dRD}{\delta}\leq\frac{1}{8}\eta\lambda)$.

Choice of $m$.
We have:

$$ $\displaystyle~{}\sqrt{m}\geq\Omega\Big{(}\lambda^{-1}\kappa\frac{R^{2}n^{1.5}d ^{0.5}}{\delta\epsilon}D\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}\sqrt{m}\geq\Omega\Big{(}\lambda^{-1}\kappa\frac{R^{2}n^{1.5}d ^{0.5}}{\delta\epsilon}m^{\frac{1}{4}}\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}m^{\frac{1}{4}}\geq\Omega\Big{(}\lambda^{-1}\kappa\frac{R^{2}n ^{1.5}d^{0.5}}{\delta\epsilon}\Big{)}$ $\displaystyle\iff$ $\displaystyle~{}m\geq\Omega\Big{(}\lambda^{-4}\kappa^{4}\frac{R^{8}n^{6}d^{2}} {\delta^{4}\epsilon^{4}}\Big{)}$ $$

where the first step follows from plugging $O(\eta\kappa\frac{R^{2}n^{1.5}\sqrt{d}}{\delta\epsilon\sqrt{m}}D)\leq\frac{1}{
8}\eta\lambda$, the last three steps follow from simple algebras.
∎

###### Lemma I.3 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle\|\mathsf{F}(0)-y\|_{2}\leq O\Big{(}\sqrt{n}dD^{2}\Big{)}$ $$

###### Proof.

We have:

$$ $\displaystyle\|\mathsf{F}(0)-y\|_{2}\leq$ $\displaystyle~{}\|\mathsf{F}(0)\|_{2}+\|y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\|\mathsf{F}(0)\|_{2}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}(\sum_{i=1}^{n}|\mathsf{F}_{i}(0)|^{2})^{\frac{1}{2}}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}(\sum_{i=1}^{n}|\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\sf ReLU}\Big{(}\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle) \Big{)}|^{2})^{\frac{1}{2}}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\sqrt{n\log(m/\delta)}dD\Big{)}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\sqrt{n}dD^{2}\Big{)}$ $$

where the first step follows from triangle inequality, the second step follows from $y_{i}\leq 1,\forall i\in[n]$ and simple algebras, the third step follows from the definition of $\ell_{2}$ norm, the fourth step follows from Definition C.9 and Definition C.5, the last two steps follow by Hoeffding’s inequality (Lemma B.8), Definition C.1 and simple algebras, and we can show that:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU} \Big{(}\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)\Big{)}]=0$ $$

also,

$$ $\displaystyle\mathsf{dq}(\langle\widetilde{w}_{r}(0),x_{i}\rangle)=$ $\displaystyle~{}\sqrt{V(w_{r}(0)}\cdot\langle\widetilde{w}_{r}(0),x_{i}\rangle +E(w_{r}(0))\langle{\bf 1}_{d},x_{i}\rangle$ $\displaystyle\leq$ $\displaystyle~{}O(\sqrt{d}D)\cdot\sqrt{d}+O(D)\cdot\sqrt{d}$ $\displaystyle\leq$ $\displaystyle~{}O(dD)$ $$

where these steps follow from Definition D.5, Lemma I.6 and simple algebras.
∎

###### Lemma I.2 .

###### Proof.

###### Lemma I.3 .

###### Proof.

### I.3 Induction for STE Gradient

###### Lemma I.4 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.

Then with probability at least $1-\delta$, we have:

- •
Part 1. $\forall k\in[d]$
$\displaystyle|\Delta w_{r,k}(t)|\leq\sqrt{\frac{n}{m}}\cdot\|\mathsf{F}(t)-y\|
_{2}$
- •
Part 2.
$\displaystyle\|\Delta w_{r}(t)\|_{2}\leq\sqrt{\frac{n}{m}}\cdot\|\mathsf{F}(t)
-y\|_{2}$

###### Proof.

Proof of Part 1. We have:

$$ $\displaystyle|\Delta w_{r,k}(t)|=$ $\displaystyle~{}|\kappa\frac{1}{\sqrt{m}}\sum_{i=1}^{n}a_{r}\cdot{\bf 1}_{ \mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot x_{i,k}\cdot (\mathsf{F}_{i}(t)-y_{i})|$ $\displaystyle\leq$ $\displaystyle~{}\kappa\frac{1}{\sqrt{m}}\Big{(}\sum_{i=1}^{n}(a_{r}\cdot{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot x_{i,k})^ {2}\Big{)}^{\frac{1}{2}}\cdot\|\mathsf{F}(t)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\sqrt{\frac{n}{m}}\cdot\|\mathsf{F}(t)-y\|_{2}$ $$

where the first step follows from Definition F.2, the second step follows from Cauchy-Schwarz inequality, the third step follows from

$$ $\displaystyle\max_{r\in[m],i\in[n],k\in[d]}|{\bf 1}_{\mathsf{dq}(\langle \widetilde{w}_{r}(t),x_{i}\rangle)\geq 0}\cdot x_{i,k}|\leq 1$ $$

the above equation follows from simple algebras and $\|x_{i}\|_{i}=1$.

Proof of Part 2.

By $\|x\|_{i}=1,\forall i\in[n]$, this proof is trivially the same as Proof of Part 1.
∎

###### Lemma I.4 .

###### Proof.

### I.4 Induction for Weights

###### Claim I.5 .

If the following conditions hold:

- •
For $i,j\in[n]$, $r\in[m]$ and integer $t\geq 0$.
- •
Let ${\sf L}(t)$ be defined as Definition C.9.
- •
Let ${\sf F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $\mathsf{dq}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition D.5.
- •
Denote $\widetilde{w}_{r}=\mathsf{q}(w_{r})\in\{-1,+1\}^{d}$.
- •
Let $\mathcal{S}_{i},\mathcal{S}_{i}^{\bot}$ be defined as Definition E.2.
- •
Let $\mathsf{u}_{r}(t)$ be defined as Definition H.1.
- •
For an error $\epsilon>0$ and $\|\mathsf{F}(t)-y\|_{2}\geq c\cdot\epsilon$ for a sufficient small constant $c>0$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle R:=\max_{t\geq 0}\max_{r\in[m]}\|w_{r}(0)-w_{r}(t)\|_{2}\leq \frac{4\sqrt{n}}{\lambda\sqrt{m}}\|\mathsf{F}(0)-y\|_{2}$ $$

###### Proof.

We have

$$ $\displaystyle R=$ $\displaystyle~{}\max_{t\geq 0}\max_{r\in[m]}\|w_{r}(0)-w_{r}(t)\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\max_{t\geq 0}\max_{r\in[m]}\|\sum_{\tau=1}^{t}\eta\Delta w_{r }(\tau)\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\eta\max_{t\geq 0}\max_{r\in[m]}\sum_{\tau=1}^{t}\|\Delta w_{r }(\tau)\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\eta\frac{\sqrt{n}}{\sqrt{m}}\max_{t\geq 0}\sum_{\tau=1}^{t}\| \mathsf{F}(\tau)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\eta\frac{\sqrt{n}}{\sqrt{m}}\max_{t\geq 0}\sum_{\tau=1}^{t}(1 -\eta\lambda/2)^{\tau}\|\mathsf{F}(0)-y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{4\sqrt{n}}{\lambda\sqrt{m}}\|\mathsf{F}(0)-y\|_{2}$ $$

where the first step follows from the definition of $R$, the second step follows from Definition C.8, the third step follows from triangle inequality, the fourth step follows from Part 2 of Lemma I.4, the fifth step follows from Lemma I.2, the last step follows from Fact B.6.
∎

###### Lemma I.6 .

Let $\delta\in(0,0.1)$. Let $D>0$ be defined as Definition B.16. Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2. Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3. Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3, denote $W:=\begin{bmatrix}w_{1},w_{2},\cdots,w_{m}\end{bmatrix}\in\mathbb{R}^{d\times m}$ satisfying $\|w_{r}-w_{r}(0)\|_{2}\leq R$ where $R\geq 0$, then with a probability at least $1-\delta$, we have

- •
Part 1. $|w_{r,k}(0)|\leq O(D)$, $\forall r\in[m],k\in[d]$.
- •
Part 2. $\|w_{r}(0)\|_{2}\leq O(\sqrt{d}D)$, $\forall r\in[m]$.
- •
Part 3. $\|w_{r}\|_{2}\leq O(\sqrt{d}D+R)$, $\forall r\in[m]$.
- •
Part 4. $E(w_{r}(0))\leq O(D)$, $\forall r\in[m]$.
- •
Part 5. $\sqrt{V(w_{r}(0))}\leq O(D)$, $\forall r\in[m]$.
- •
Part 6. $E(w_{r})\leq O(D+R)$, $\forall r\in[m]$.
- •
Part 7. $\sqrt{V(w_{r})}\leq O(D+R)$, $\forall r\in[m]$.

###### Proof.

This proof follows from the union bound of the Gaussian tail bound (Fact B.1) and some simple algebras.
∎

###### Claim I.5 .

###### Proof.

###### Lemma I.6 .

###### Proof.

## Appendix J Supplementary Setup for Classical Linear Regression

### J.1 Model Function

###### Definition J.1 .

If the following conditions hold:

- •
For a input vector $x\in\mathbb{R}^{d}$.
- •
For a hidden-layer weights $W\in\mathbb{R}^{d\times m}$ as Definition C.2.
- •
For a output-layer weights $a\in\mathbb{R}^{m}$ as Definition C.2.
- •
Let ${\sf ReLU}:\mathbb{R}\rightarrow\mathbb{R}$ be defined as Definition C.4.
- •
Let $D=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
$t\geq 0$, let $W(0)\in\mathbb{R}^{d\times m}$ and $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
$W^{\prime}(0):=W(0)$.
- •
Let $W^{\prime}(t)\in\mathbb{R}^{d\times m}$ be updated as Claim J.3.
- •
$\kappa\in(0,1]$.

We define:

$$ $\displaystyle f^{\prime}(x,W,a):=\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\sf ReLU}(\langle w_{r},x\rangle)\in\mathbb{R}$ $$

Then we define the compact form of $f(x,W^{\prime}t),a)$, we define:

$$ $\displaystyle\mathsf{F}^{\prime}(t)=\begin{bmatrix}f(x_{1},W^{\prime}(t),a),f( x_{2},W^{\prime}(t),a),\cdots,f(x_{n},W^{\prime}t),a)\end{bmatrix}^{\top}\in \mathbb{R}^{n}$ $$

###### Definition J.1 .

### J.2 Loss and Training

###### Definition J.2 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $f^{\prime}:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}
\rightarrow\mathbb{R}$ be defined as Definition J.1.
- •
For any $t\geq 0$.

We define:

$$ $\displaystyle{\sf L}^{\prime}(t):=\frac{1}{2}\|\mathsf{F}^{\prime}(t)-y\|_{2}^ {2}$ $$

###### Claim J.3 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $f^{\prime}:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}
\rightarrow\mathbb{R}$ be defined as Definition J.1.
- •
Let ${\sf L}^{\prime}(t)$ be defined as Definition J.2.
- •
For any $t\geq 0$.
- •
Denote $\eta>0$ aa the learning rate.

We define:

$$ $\displaystyle W^{\prime}(t+1):=W^{\prime}(t)-\eta\cdot\Delta W^{\prime}(t)$ $$

Here, we also define that:

$$ $\displaystyle W^{\prime}(t):=$ $\displaystyle~{}\frac{\mathrm{d}}{\mathrm{d}W^{\prime}(t)}{\sf L}^{\prime}(t)$ $\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{n}(\mathsf{F}_{i}^{\prime}(t)-y_{i})\cdot\kappa \begin{bmatrix}a_{1}\cdot{\bf 1}_{\langle w_{1}^{\prime}(t),x_{i}\rangle\geq 0 }x_{i}&\cdots&a_{m}\cdot{\bf 1}_{\langle w_{m}^{\prime}(t),x_{i}\rangle\geq 0} x_{i}\end{bmatrix}\in\mathbb{R}^{d\times m}$ $$

###### Proof.

This proof follows from simple algebras.
∎

###### Definition J.2 .

###### Claim J.3 .

###### Proof.

### J.3 Induction for Weights

###### Lemma J.4 (See Corollary 4.1 and the fifth equation of page 6 in DZPS [ 29 ] ) .

If the following conditions hold:

- •
$t\geq 0$, let $W(0)\in\mathbb{R}^{d\times m}$ and $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
$W^{\prime}(0):=W(0)$.
- •
Let $W^{\prime}(t)\in\mathbb{R}^{d\times m}$ be updated as Claim J.3.
- •
$R\leq O(\frac{\lambda\delta}{\kappa^{2}n^{2}dD})$.

Then we have

$$ $\displaystyle\|w_{r}^{\prime}(t)-w_{r}^{\prime}(0)\|\leq R$ $$

###### Proof.

Following Corollary 4.1 in DZPS [], we can show that:

$$ $\displaystyle\|w_{r}^{\prime}(t)-w_{r}^{\prime}(0)\|\leq\frac{4\sqrt{n}}{\sqrt {m}\lambda}\|\mathsf{F}^{\prime}(0)-y\|_{2}$ $$

Then we can complete this proof by combining the equation above with Lemma J.5 and $R\leq O(\frac{\lambda\delta}{n^{2}dD})$ in Lemma conditions.
∎

###### Lemma J.4 (See Corollary 4.1 and the fifth equation of page 6 in DZPS [ 29 ] ) .

###### Proof.

### J.4 Induction for Loss

###### Lemma J.5 .

If the following conditions hold:

- •
Let ${\cal D}=\{(x_{i},y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition C.1.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
Let $a\in\mathbb{R}^{m}$ be initialized as Definition C.3.
- •
Let $f^{\prime}:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}
\rightarrow\mathbb{R}$ be defined as Definition J.1.
- •
For any $t\geq 0$.
- •
$W^{\prime}(0):=W(0)$.
- •
Let $W^{\prime}(t)\in\mathbb{R}^{d\times m}$ be updated as Claim J.3.
- •
$\delta\in(0,0.1)$.

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle\|\mathsf{F}^{\prime}(0)-y\|_{2}\leq O\Big{(}\sqrt{n}dD^{2}\Big{)}$ $$

###### Proof.

We have:

$$ $\displaystyle\|\mathsf{F}^{\prime}(0)-y\|_{2}\leq$ $\displaystyle~{}\|\mathsf{F}^{\prime}(0)\|_{2}+\|y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\|\mathsf{F}^{\prime}(0)\|_{2}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}(\sum_{i=1}^{n}|\mathsf{F}_{i}^{\prime}(0)|^{2})^{\frac{1}{2}} +\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}(\sum_{i=1}^{n}|\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\sf ReLU}\Big{(}\langle w_{r}^{\prime}(0),x_{i}\rangle\Big{)}|^{2})^{ \frac{1}{2}}+\sqrt{n}$ $\displaystyle=$ $\displaystyle~{}(\sum_{i=1}^{n}|\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r} \cdot{\sf ReLU}\Big{(}\langle w_{r}(0),x_{i}\rangle\Big{)}|^{2})^{\frac{1}{2}} +\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\sqrt{n\log(m/\delta)}dD\Big{)}+\sqrt{n}$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}\sqrt{n}dD^{2}\Big{)}$ $$

where the first step follows from triangle inequality, the second step follows from $y_{i}\leq 1,\forall i\in[n]$ and simple algebras, the third step follows from the definition of $\ell_{2}$ norm, the fourth step follows from Definition C.9 and Definition C.5, the fifth step follows from $W^{\prime}(0)=W(0)$, the last two steps follow by Hoeffding’s inequality (Lemma B.8), Definition C.1, $\kappa\leq 1$ and simple algebras, and we can show that:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{r=1}^{m}a_{r}\cdot{\sf ReLU} \Big{(}\langle w_{r}(0),x_{i}\rangle\Big{)}]=0$ $$

also,

$$ $\displaystyle\langle w_{r}(0),x_{i}\rangle=$ $\displaystyle~{}\langle w_{r}(0),x_{i}\rangle$ $\displaystyle\leq$ $\displaystyle~{}O(\sqrt{d}D)\leq O(dD)$ $$

where this step follows from Lemma I.6 and simple algebras.
∎

###### Lemma J.5 .

###### Proof.

## Appendix K Similarities

### K.1 Main Result 2: Training Similarity

###### Theorem K.1 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
Given a expected error $\epsilon>0$.
- •
Let $H^{*}\in\mathbb{R}^{n\times n}$ be defined as Claim G.2. Assume $\lambda_{\min}(H^{*})>0$ as Assumption G.4.
- •
Let $\mathcal{D}_{\rm test}:=\{(x_{{\rm test},i},y_{{\rm test},i})\}_{i=1}^{n}
\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition K.2.
- •
Let $\mathsf{F}^{\prime}(t)\in\mathbb{R}^{n}$ be defined as Definition J.1.
- •
Let $\mathsf{F}(t)\in\mathbb{R}^{n}$ be defined as Definition C.9.
- •
Let $\mathsf{F}^{\prime}_{\rm test}(t)\in\mathbb{R}^{n}$ be defined as Definition K.3.
- •
Let $\mathsf{F}_{\rm test}(t)\in\mathbb{R}^{n}$ be defined as Definition K.3.
- •
For any $t\geq 0$.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
$W^{\prime}(0):=W(0)$.
- •
Let $W^{\prime}(t)\in\mathbb{R}^{d\times m}$ be updated as Claim J.3.
- •
For any error $\epsilon_{\rm quant}>0$.
- •
$\delta\in(0,0.1)$.
- •
Choose $\kappa\leq O(\frac{\epsilon_{\rm quant}}{dD^{2}})$.

Then with probability at least $1-\delta$, we have:

- •
Part 1. $|\mathsf{F}_{{\rm test},i}(t)-\mathsf{F}_{{\rm test},i}^{\prime}(t)|\leq
\epsilon_{\rm quant}$.
- •
Part 2. $|\mathsf{F}_{i}(t)-\mathsf{F}_{i}^{\prime}(t)|\leq\epsilon_{\rm quant}$.

###### Proof.

Proof of Part 1.
We have:

$$ $\displaystyle~{}|{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{{\rm test },i}\rangle)\geq 0}(\langle w_{r}(t),x_{{\rm test},i}\rangle+\langle\mathsf{u} _{r}(t),x_{{\rm test},i}\rangle)$ $\displaystyle~{}-{\bf 1}_{\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle \geq 0}\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle|$ $\displaystyle\leq$ $\displaystyle~{}|\langle w_{r}(t),x_{{\rm test},i}\rangle+\langle\mathsf{u}_{r }(t),x_{{\rm test},i}\rangle-\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle|$ $\displaystyle=$ $\displaystyle~{}|\langle w_{r}(0)-\eta\sum_{\tau=0}^{t-1}\Delta w_{r}(\tau),x_ {{\rm test},i}\rangle+\langle\mathsf{u}_{r}(t),x_{{\rm test},i}\rangle-\langle w _{r}^{\prime}(0)-\eta\sum_{\tau=0}^{t-1}\Delta w_{r}^{\prime}(\tau),x_{{\rm test },i}\rangle|$ $\displaystyle=$ $\displaystyle~{}|-\langle\eta\sum_{\tau=0}^{t-1}\Delta w_{r}(\tau),x_{{\rm test },i}\rangle+\langle\mathsf{u}_{r}(t),x_{{\rm test},i}\rangle+\langle\eta\sum_{ \tau=0}^{t-1}\Delta w_{r}^{\prime}(\tau),x_{{\rm test},i}\rangle|$ $\displaystyle\leq$ $\displaystyle~{}|\langle\eta\sum_{\tau=0}^{t-1}\Delta w_{r}(\tau),x_{{\rm test },i}\rangle|+|\langle\eta\sum_{\tau=0}^{t-1}\Delta w_{r}^{\prime}(\tau),x_{{ \rm test},i}\rangle|+|\langle\mathsf{u}_{r}(t),x_{{\rm test},i}\rangle|$ $\displaystyle\leq$ $\displaystyle~{}R+R+|\langle\mathsf{u}_{r}(t),x_{{\rm test},i}\rangle|$ $\displaystyle\leq$ $\displaystyle~{}O\Big{(}d(D+R)\Big{)}$ $$

where the first step follows from Fact B.2, the second step follows from Definition C.8 and Claim J.3, the third step follows from $w_{r}^{\prime}(0)=w_{r}(0)$, the fourth step follows from triangle inequality, the fifth step follows from Claim I.5 and Lemma J.4, the last step follows from Lemma D.7 and $\delta\in(0,0.1)$.

Then we have:

$$ $\displaystyle|\mathsf{F}_{{\rm test},i}(t)-\mathsf{F}_{{\rm test},i}^{\prime}( t)|\leq$ $\displaystyle~{}\Big{|}\kappa\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\Big{(}{\bf 1 }_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{{\rm test},i}\rangle)\geq 0}( \langle w_{r}(t),x_{{\rm test},i}\rangle+\langle\mathsf{u}_{r}(t),x_{{\rm test },i}\rangle)$ $\displaystyle~{}-{\bf 1}_{\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle \geq 0}\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle\Big{)}\Big{|}$ $\displaystyle\leq$ $\displaystyle~{}\kappa\sqrt{\log(m/\delta)}\cdot O\Big{(}d(D+R)\Big{)}$ $\displaystyle\leq$ $\displaystyle~{}\epsilon_{\rm quant}$ $$

where the first step follows from Definition K.3, the second step follows from Hoeffding’s inequality (Lemma B.8), $\operatorname*{{\mathbb{E}}}[\sum_{r=1}^{m}a_{r}\sigma_{i,r}]=0$, $\sigma_{i,r}\leq O\Big{(}\frac{\sqrt{n}}{m}(D+R)+R/\delta\Big{)}$ and defining:

$$ $\displaystyle\sigma_{i,r}:=$ $\displaystyle~{}|{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(t),x_{{\rm test },i}\rangle)\geq 0}(\langle w_{r}(t),x_{{\rm test},i}\rangle+\langle\mathsf{u} _{r}(t),x_{{\rm test},i}\rangle)$ $\displaystyle~{}-{\bf 1}_{\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle \geq 0}\langle w_{r}^{\prime}(t),x_{{\rm test},i}\rangle|$ $$

and the last step follows from choosing

$$ $\displaystyle\kappa\leq O(\frac{\epsilon_{\rm quant}}{dD^{2}+dDR})\leq O(\frac {\epsilon_{\rm quant}}{dD^{2}})$ $$

Proof of Part 2.
This part can be proved in the same way as Proof of Part 1.
∎

###### Theorem K.1 .

###### Proof.

### K.2 Test Dataset for Generalization Evaluation

###### Definition K.2 .

We define test dataset $\mathcal{D}_{\rm test}:=\{(x_{{\rm test},i},y_{{\rm test},i})\}_{i=1}^{n}
\subset\mathbb{R}^{d}\times\mathbb{R}$, where $\|x_{{\rm test},i}\|_{2}=1$ and $y_{{\rm test},i}\leq 1$ for any $i\in[n]$.

###### Definition K.3 .

If the following conditions hold:

- •
Let $\mathcal{D}_{\rm test}:=\{(x_{{\rm test},i},y_{{\rm test},i})\}_{i=1}^{n}
\subset\mathbb{R}^{d}\times\mathbb{R}$ be defined as Definition K.2.
- •
Let $f^{\prime}:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}
\rightarrow\mathbb{R}$ be defined as Definition J.1.
- •
Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\rightarrow
\mathbb{R}$ be defined as Definition C.5.
- •
For any $t\geq 0$.
- •
Let $W(t)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3 and be updated by Definition C.8.
- •
$W^{\prime}(0):=W(0)$.
- •
Let $W^{\prime}(t)\in\mathbb{R}^{d\times m}$ be updated as Claim J.3.

We define:

$$ $\displaystyle~{}\mathsf{F}_{\rm test}^{\prime}(t):=\begin{bmatrix}f^{\prime}(x _{{\rm test},1},W^{\prime}(t),a),f^{\prime}(x_{{\rm test},2},W^{\prime}(t),a), \cdots,f^{\prime}(x_{{\rm test},n},W^{\prime}(t),a)\end{bmatrix}^{\top}$ $\displaystyle~{}\mathsf{F}_{\rm test}(t):=\begin{bmatrix}f(x_{{\rm test},1},W( t),a),f(x_{{\rm test},2},W(t),a),\cdots,f(x_{{\rm test},n},W(t),a)\end{bmatrix }^{\top}$ $$

###### Definition K.2 .

###### Definition K.3 .

### K.3 Function Similarity at Initialization

###### Lemma K.4 .

If the following conditions hold:

- •
Let $D>0$ be defined as Definition B.16.
- •
Let $\mathsf{q}:\mathbb{R}^{d}\rightarrow\{-1,+1\}^{d}$ be defined as Definition D.4.
- •
Let $E:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.2.
- •
Let $V:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as Definition D.3.
- •
For a weight vector $w\in\mathbb{R}^{d}$.
- •
Denote quantized vector $\widetilde{w}:=\mathsf{q}(w)\in\{-1,+1\}^{d}$.
- •
For a vector $x\in\mathbb{R}^{d}$ and $\|x\|_{2}=1$.
- •
Let $f^{\prime}:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}
\rightarrow\mathbb{R}$ be defined as Definition J.1.
- •
Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\rightarrow
\mathbb{R}$ be defined as Definition C.5.
- •
Let $W(0)\in\mathbb{R}^{d\times m}$ be initialized as Definition C.3.
- •
$W^{\prime}(0):=W(0)$.
- •
$\delta\in(0,0.1)$.
- •
For any error $\epsilon_{\rm init}>0$.
- •
We choose $\kappa\leq O(\epsilon_{\rm init}/(\sqrt{d}D^{2}))$

Then with probability at least $1-\delta$, we have:

$$ $\displaystyle|f(x,W(0),a)-f^{\prime}(x,W^{\prime}(0),a)|\leq\epsilon_{\rm init}$ $$

###### Proof.

We have:

$$ $\displaystyle~{}|{\bf 1}_{\mathsf{dq}(\langle\widetilde{w}_{r}(0),x\rangle) \geq 0}\mathsf{dq}(\langle\widetilde{w}_{r}(0),x\rangle)$ $\displaystyle~{}-{\bf 1}_{\langle w_{r}(0),x\rangle\geq 0}\langle w_{r}(0),x\rangle|$ $\displaystyle\leq$ $\displaystyle~{}|\mathsf{dq}(\langle\widetilde{w}_{r}(0),x\rangle)-\langle w_{ r}(0),x\rangle|$ $\displaystyle\leq$ $\displaystyle~{}|\sqrt{V(w_{r}(0))}\langle\widetilde{w}_{r}(0),x\rangle+E(w_{r }(0))\cdot\langle{\bf 1}_{d},x\rangle-\langle w_{r}(0),x\rangle|$ $\displaystyle\leq$ $\displaystyle~{}O(\sqrt{d}D)$ $$

where the first step follows from Fact B.2, the second step follows from Definition D.5, the last step follows from Lemma I.6.

Then by Hoeffding inequality (Lemma B.8), with a probability at least $1-\delta$, we have:

$$ $\displaystyle|f(x,W(0),a)-f^{\prime}(x,W^{\prime}(0),a)|\leq$ $\displaystyle~{}\kappa|\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\widehat{\sigma}_{ r}|$ $\displaystyle\leq$ $\displaystyle~{}\kappa O(\sqrt{d}D)\cdot\sqrt{\log(m/\delta)}$ $\displaystyle\leq$ $\displaystyle~{}O(\kappa\sqrt{d}D^{2})$ $$

where we have:

$$ $\displaystyle~{}\widehat{\sigma}_{r}:={\bf 1}_{\mathsf{dq}(\langle\widetilde{w }_{r}(0),x\rangle)\geq 0}\mathsf{dq}(\langle\widetilde{w}_{r}(0),x\rangle)-{ \bf 1}_{\langle w_{r}(0),x\rangle\geq 0}\langle w_{r}(0),x\rangle$ $\displaystyle~{}\operatorname*{{\mathbb{E}}}[\sum_{r=1}^{m}a_{r}\widehat{ \sigma}_{r}]=1$ $\displaystyle~{}|\widehat{\sigma}_{r}|\leq O(\sqrt{d}D)$ $$

∎

###### Lemma K.4 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: Please see the weaknesses. I'll ask more questions after looking at the author's rebuttal.
soundness: 3
strengths: 1. The topic this paper tries to push is timely, as there have been several works in Quantization Aware Training of low-bitwidth models recently, which show how these models start working better at scale.

2. This paper takes an interesting NTK perspective to justify training dynamics and generalization of binary neural networks. They also derive a scaling law of 1-bit neural networks under certain assumptions.
summary: This paper provides theoretical justification for scaling 1-bit neural networks, showing that their training dynamics converge to kernel-like behavior as model width increases. The authors demonstrate that the training loss can become arbitrarily small with sufficient network width and that the generalization difference between 1-bit and full-precision networks shrinks with scale. Using the Neural Tangent Kernel (NTK) framework, the authors guarantee training convergence to minimal loss. Preliminary empirical results confirm that 1-bit models perform comparably to full-precision networks on complex tasks, with significant efficiency gains. This work suggests that scaling quantization aware training of 1-bit neural networks are a promising direction for efficient deep learning.
weaknesses: 1. The main weakness of the paper is the lack of realistic experiments and the positioning of the paper. The authors use 1-bit LLMs to motivate the paper in the abstract and introduction, but their theory and experiments are for quantized MLPs at a very small scale. The authors should rewrite the abstract and introduction to clarify what their focus is on rather than overemphasizing low-bitwidth LLMs. For example, authors should explicitly state their focus is on quantized MLPs for learning functions, and clarify how their results may or may not extend to large-scale LLMs.

2. In section 3.2, the authors mention $f$ is a two layer attention model; however, the equations suggest it’s a two-layer MLP. Symbols like $m$ are not defined clearly. This section needs better clarity.

3. The choice of experiments (learning rigorous functions) seems arbitrary to me, given that the motivation of the paper is 1-bit LLMs. Can the authors explain this disparity?

4. Authors should look at related papers that try to empirically derive the scaling law of low-bit (binary and ternary) quantization-aware training of LLMs like [1], which might make the arguments in their paper stronger. They also provide the model checkpoints and losses at various scales for 1-bit and 1.58-bit LLMs. I think if the authors want to position their paper as validating the scaling of low-bit LLMs using their theory, they can use the existing checkpoints from this work.

[1] A Kausal et al. Spectra: Surprising Effectiveness of Pretraining Ternary Language Models at Scale

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 2
questions: See above.
soundness: 2
strengths: - The paper studies an important topic of training quantized networks, from a theoretical point of view.
- Showing convergence of 1-bit network with quantization aware training is, to my knowledge, novel.
- Studying the relation between 1-bit network and full-precision networks is interesting and important.
summary: The work studies theoretically the power of 1-bit networks, using NTK theory. Specifically, the authors bound the convergence time for training 1-bit quantized network using Quantization Aware Training, where the network is quantized in the forward pass, and computes the gradient with a straight-through estimator in the backward pass. They also relate the convergence guarantees to scaling laws for 1-bit networks, and complement these scaling laws with experiments. Additionally, the authors bound the difference between the quantized and non-quantized network at initialization and during training.
weaknesses: - Lemma 4.1: the results in the lemma depend on $\lambda$, which I assume is $\lambda_{\min}(H^*)$ (this should be properly stated). However, if this is the case $\lambda$ should depend explicitly on $\kappa^2$, and the dependence on $\kappa^2$ should be tracked throughout the results. It is better to define $\lambda$ as the minimal eigenvalue of the non-scaled Gram matrix, and have the explicit dependence on $\kappa^2$ in the results.
- It is worth noting that the scaling laws derived in proposition 4.3 are very different form than the Kaplan scaling laws (e.g., $N$ and $D$ in the Kaplan scaling laws are in the denominator with fractional power, and are not exponentiated).
- The authors claim that the function implemented by the quantized network approaches the function computed by the full-precision network as the network size grows, but I do not see how this is reflected in the results. Specifically, it is worthwhile to write down an explicit bound on the difference between the two networks that goes to zero with $m$, when keeping other parameters (e.g. dataset size and network scale) constant. I currently did not see such a bound, but maybe I am missing something.
- Related to the above, the main results that relate the quantized and non-quantized networks (Theorems 5.1 and 5.2) rely on the scaling parameter $\kappa$ being very small. However, clearly taking $\kappa$ to zero makes both functions go to zero, and thus trivially the difference between the two functions becomes small. But this is also true for any (bounded) function multiplied by $\kappa$, so it seems that these results trivially hold. Do the results simply imply that all functions go to zero with $\kappa$ and thus become close, or can these result hold when both functions are bounded away from zero (e.g. by a constant)?
- The functions studied in 6.1 are relatively low-dimensional, which may mean that they can be approximated easily in the kernel regime by any kernel. Did you try experimenting with functions of higher dimensions?

Additionally, there are some unclear sentences/phrases in the paper, e.g.:
- Lines 392-395, these two sentences are not clear.
- Line 347
- Line 260-261
- Line 422: "we aimed to learn rigorous functions" - what does "rigorous function" mean here?

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: Could the authors provide evaluation on practical models, e.g., GPT-2 and validate the proposed scaling law?
soundness: 2
strengths: - This paper studies an important problem as to scaling 1-bit neural networks. Given the increasing deployment of large foundation models, how to reduce their energy consumptions become an increasingly important problem. 1-bit quantization is a promising approach to study.
- The authors conduct thorough experiments to validate the theoretical analysis.
summary: This paper conducts a theoretical analysis on scaling 1-bit neural networks. The authors use the NTK framework to derive a scaling law formula for 1-bit quantized networks. Experiments on simulating target functions demonstrate the effectiveness of the proposed scaling law.
weaknesses: - This paper studies the scaling law of 1-bit neural networks. However, the analysis is performed on simple toy models. The original scaling law as proposed by Kaplan [1] is conducted on  Transformers with millions/billions of parameters with huge amounts of pretraining compute. The goal of scaling law should be to study how to reliably predict the performance of pretraining with larger compute. However, the setting of this paper does not fit in the category of “scaling law”, given the small scale experiments conducted on toy models.  
- The experiments do not support the claim that there is a scaling law for 1-bit quantized neural networks. The authors do not demonstrate the exact scaling law formula, e.g. what are the values of hyperparameters in proposition 4.3 when fitting this curve to the experiments in Figure 1.  Obtaining the coefficient in the scaling law is of practical importance, which can be used to predict performance of training larger 1-bit quantized models.  
- What is the justification for using NTK for studying this problem? The introduction of section 3.3 seems rather abrupt, which lacks the discussion for motivation.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: See Weaknesses
soundness: 2
strengths: 1) The paper introduces a variation of the soft-commite machine that can be analytically traced to show the convergence of 1-bit models.

2) The convergence is analysed for the number of model parameters and the size of the training data set.
summary: The paper shows that a modified 1-bit soft-commite machine converges to an arbitrarily small loss as the width of the hidden layer goes to infinity. It also gives a theoretical upper bound on the rate of convergence.
They also show that a 1-bit model can be trained to estimate complex functions with high accuracy.
weaknesses: 1) Given that the paper provides numerical results, I found it problematic that the main result of the paper (the functional form of the convergence of the training loss of 1-bit models) is not verified with numerical results.  

2) The finding of a "scaling law" in Fig.1 with four data points, no comparison with a theory curve, and significant fluctuations is, in my opinion, not a valid verification of Proposition 4.3 at all.

3) The figures are not properly described/referenced in the text. 

4) The introduction of $\kappa$ in the model seems a bit arbitrary, especially considering that it is necessary to "plug an appropriate value of $\kappa$" (Line 391) into the model to ensure learning.

5) The abstract does not adequately explain what is being done in the paper. Instead of citing previous results in the abstract, I would like to see the model and a more precise definition of the results there.