Implicit Regularization in Over-Parameterized Support Vector Machine
Authors: Yang Sui
Xin HE
Yang Bai
Venue: NeurIPS 2023 poster (2023)
Keywords: Over-parameterization
SVM
Sparsity
Lasso

Abstract: In this paper, we design a regularization-free algorithm for high-dimensional support vector machines (SVMs) by integrating over-parameterization with Nesterov's smoothing method, and provide theoretical guarantees for the induced implicit regularization phenomenon. In particular, we construct an over-parameterized hinge loss function and estimate the true parameters by leveraging regularization-free gradient descent on this loss function. The utilization of Nesterov's method enhances the computational efficiency of our algorithm, especially in terms of determining the stopping criterion and reducing computational complexity. With appropriate choices of initialization, step size, and smoothness parameter, we demonstrate that unregularized gradient descent achieves a near-oracle statistical convergence rate. Additionally, we verify our theoretical findings through a variety of numerical experiments and compare the proposed method with explicit regularization. Our results illustrate the advantages of employing implicit regularization via gradient descent in conjunction with over-parameterization in sparse SVMs.

Implicit Regularization in Over-Parameterized Support Vector Machine
Yang Sui' Xin He Yang Bait
School of Statistics and Management Shanghai University of Finance and Economics
suiyang1027@stu sufe. edu. en ,he. kin17@maail shufe edu. en; statbyang@mail. shufe edu. cn
Abstract
In this paper, we design a regularization-fre algorithm for high-dimensional sup- vector machines (SVMs) by integrating wver-parameterization with Nesterov's smoothing method, and provide theoretical guarantees the induced implicit reg- ularization phenomenon. In particular, we construct
parameterizze hinge loss function and estimate the true parameters by leveraging regularization frre gra- dient descent this loss function. The utilization of Nesterov's method enhances the computational efficiency of our algorithm, especially terms of determining the stopping criterion and reducing computational complexity. With appropriate choices of initialization, step size, and smoothness parameter, we demonstrate that unregularized gradient descent achieves a near-oracle statistical convergence rate. Additionally, we verify our theoretical findings through a variety of numerical experiments and compare the proposed method with explicit regularization. Our results illustrate the advantages of employing implicit regularization via gradient descent in conjunction with over-paramettrizzaion in sparse SVMs.
Introduction
In machine learning, over-parameterized models, such as deep learning models, are commonly used for regression and classification [22, 36, 31, 10]. The corresponding optimization tasks are primarily tackled using gradient-based methods. Despite challenges posed by the nonconvexity of the objective function and wver-parameterization [40], empirical observations show that simple algorithms, such as gradient descent, tend to converge to global minimum. This phenomenon is known as the implicit regularization of variants of gradient descent, which acts form of regularization without an explicit regularization term [30, 29].
Implicit regularization has been extensively studied in many classical statistical problems, such as linear regression [35, 23, 44] and matrix factorization [14, 24, 3]. These studies have shown that unregularized gradient descent can yield optimal estimators under certain conditions. However, deeper understanding of implicit regularization in classification problems, particularly in support vector machines (SVMs), remains limited. Existing studies have focused specific cases and alternative regularization approaches [33, 27, 2). A comprehensive analysis of implicit regularization via direct gradient descent SVMs is still lacking. We need further investigation explore the implications and performance of implicit regularization in SVMs.
The practical significance of such exploration becomes evident when considering today's complex data landscapes and the challenges they present. In modern applications, we often face classification
Equual contributions. Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

challenges due to redundant features. Data sparsity is notably evident in classification fields like finance, document classification, and gene expression analysis. For instance, in genomics, only a few genes out of thousands are used for disease diagnosis and drug discovery [17]. Similarly, spam classifiers rely on small selection of words from extensive dictionaries [1]. These scenarios highlight limitations in standard SVMs and those with explicit regularization, like the lz norm, From an applied perspective, incorporating sparsity into SVMs is an intriguing research direction. While sparsity in regression has been deeply explored recently, sparse SVMs have received less attention. Discussions typically focus on generalization error and risk analysis, with limited mention of variable selection and error bounds [32]. Our study delves into the implicit regularization in classification, complementing the ongoing research in sparse SVMs.
In this paper, we focus on the implicit regularization of gradient descent applied to high- digeeniienii sparse SVMs. Contrary to existing studies on implicit regularization in first-order iterative methods for nonconvex optimization that primarily address regression, we investigate this intriguing phenomenon of gradient descent applied to SVMs with hinge loss. By re-parameterizing the parameters using the Hadamard product, we introduce novel approach to nonconvex optimization problems. With proper initialization and parameter tuning, our proposed method achieves the desired statistical convergence rate. Extensive simulation results reveal that our method outperforms the estimator under explicit regularization in terms of estimation error, prediction accuracy, and variable selection. Moreover, rivals the performance of the gold standard oracle solution, assuming the knowledge of true support.
1.1 Our Contributions
First, we reformulate the parameter 3 as W ④ W - V v. where @ denotes the Hadamard product operator, resulting in non-convex optimization problem. This ce-parameterizatioon technique has not been previously employed for classification problems. Although it introduces some theoretical complexities, it is not computationally demanding. Importantly, allows for a detailed theoretical analysis of how signals change throughout iterations, offering a novel perspective on the dynamics of gradient descent not covered in prior works [13, 33]. With the help of re- re-parameterization, we provide theoretical analysis showing that with appropriate choices of initialization size a, step size n. and smoothness parameter y, our method achieves a near-oracle rate of /s ssogp/n, where s is the number of the signals, p the dimension of (3, and n is the sample size. Notice that the near-oracle rate is achievable via explicit regularization [32, 46, 20]. To the best of our knowledge, this is the first study that investigates implicit regularization via gradient descent and establishes the near-oracle rate specifically in classification.
Second, we employ a simple yet effective smoothing technique [28, 45] for the re- ce-parameterized hinge loss, addressing the non-differentiabiiiyy of the hinge loss. Additionally, our method introduces a convenient stopping criterion post- mootthoo.,,ing. which we discuss in detail in Section 2.2. Notably, the smoothed gradient descent algorithm is not computationally demanding, primarily involving vector multiplication. The variables introduced by the smoothing technique mostly take values of 0 or 1 as smoothness parameter " decreases, further streamlining the computation. Incorporating Nesterov's smoothing instrumental in our theoretical derivations. Directly analyzing the gradient algorithm with re- parameterization for the non-smooth hinge loss, while computationally feasible, introduces complexities theoretical deductions. essence, Nesterov's smoothing proves vital both computationally and theoretically.
Third, to support our theoretical results, we present finite sample performances of method through extensive simulations, comparing it with both the fj-regularized estimator and the gold standard oracle solution. We demonstrate that the number of iterations t in gradient descent parallels the role of the & regularization parameter A. When chosen appropriately, both can achieve the near-oracle statistical convergence rate. Further insights from our simulations illustrate that, firstly, in terms of estimation error, our method generalizes better than the E Ey-regular estimator. Secondly, for variable selection, our method significantly reduces false positive rates. Lastly, due to the efficient transferability of gradient information among machines, our method is easier to be paralleled and generalized to large- scale applications. Notably, while our theory is primarily based on the Sub-Gaussian distribution assumption, our method is actually applicable to much wider range. Additional simulations under heavy-tailed distributions still yield remarkably desired results. Extensive experimental results indicate that our method's performance, employing implicitly regularized gradient descent in SVMs,
2

---

rivals that of algorithms using explicit regularization. In certain simple scenarios, it even matches the performance of the oracle solution.
1.2 Related Work
Frequent empirical evidence shows that simple algorithms such as (stochastic) gradient descent tend find the global minimum of the loss function despite nonconvexity. To understand this phenomenon, studies by [30, 29, 19, 38, 43] proposed that generalization arises from the implicit regularization of the optimization algorithm. Specifically, these studies observe that in over-parameterized statistical models, although optimization problems may contain bad local errors, optimization algorithms, typically variants of gradient descent, exhibit a tendency to avoid these bad local minima and converge towards better solutions. Without adding any regularization term in the optimization objective, the implicit preference of the optimization algorithm itself plays the role of regularization.
Implicit regularization has attracted significant attention in well-established statistical problems, including linear regression [13, 35, 39, 23, 44] and matrix factorization [14, 24, 3, 25, 26]. In high- dimensional sparse linear regression problems, [35, 44] introduced a re-parameterization technique and demonstrated that unregularized gradient descent yields estimator with optimal statistical accuracy under the Restricted Isometric Property (RIP) assumption [6]. [11] obtained similar results for the single index model without the RIP assumption. low-rank matrix sensing, [14, 24] revealed that gradient descent biases towards the minimum nuclear norm solution when initiated close to the origin. Additionally, [3] demonstrated the same implicit bias towards the nuclear norm using a depth-NV linear network. Nevertheless, research on the implicit regularization of gradient descent in classification problems remains limited. [33] found that the gradient descent estimator converges to the direction of the max-margin solution on unregularized logistic regression problems. In terms of the hinge loss in SVMs, [2] provided a diagonal descent approach and established its regularization properties. However, these investigations rely the diagonal regularization process [4], and their algorithms' convergence rates depend on the number of iterations, and are not directly compared with those of explicitly regularized algorithms. Besides, Frank- method and its variants have been used for classification [21, 34]. However, sub-linear convergence to the optimum requires the strict assumption that both the direction-findee finding step and line search step performed exactly [18].
2
Model and Algorithms
2.1 Notations
Throughout this work. denote vectors with boldface letters and real numbers with normal font. Thus, w denotes a vector and wi denotes the i-th coordinate of w. We use [n]] to denote the set {1,2.... n). For any subset S in [ni] and vector w, use ws to denote the vector whose i-th entry is w; if i E and 0 otherwise. For any given vector w. let || its l, f2 and foe norms. Moreover, for any two vectors w, E RP Hadamard product of vectors w and v, whose components are W;U; for i E [p]. For any given matrix represent the Frobenius norm and spectral norm of matrix
| [w]l.. ||w]] and || denote
define @ v E Rp as the
X E IR XP2, we use |X||| F and |X||s X, respectively. In addition, we let {an. bn Jn21 be any two positive sequences. We write an S bn if there exists universal constant C' such that a, C bn and we write an bn if we have an & bn and bn S On Moreover, On = (bb,.) shares the same meaning with an S bn-
2.2 Over-parameterization for & reggullard SVM
Given a random sample z" (xx, y))l with x; E Rp denoting the covariates and y {0, 1} denoting the corresponding label, we consider the following & l-rregularized SVM:
-1 + *113311,
min BERP 1=1
where (.)4 = max(-;0) 0} denotes the hinge loss and À denotes the E, regularization parameter. Let Lzn ((3 denote the first term of the right-hand side of (1). Previous works have shown that the E fi-regularized estimator of the optimization problem (1) and its extensions achieve a near-oracle rate of convergence to the true parameter 3 [32, 37, 43]. In contrast, rather than imposing the L
3

---

regularization term in (I), we minimize the hinge loss function Lz- (3) directly to obtain sparse estimator. Specifically, we re-parameterize 3 3 = & w O v, using two vectors and v in IRP. Consequently, T.z" (3) can be reformulated as Ezn (w, v):
Ew,(ww v) = 1 n T1 _ WW--A/(ow--
Note that the dimensionality of [3 in (L) p. but 2p-dimensional parameter is involved in (2). This nrow-vr in (2). We briefly describe our motivation + ( ||c]]2//. Thus,
indicates that we over-vovaniee weerpparamtterize 3 via on ever-paramettriiing B3 this way. Following [16]. || argmingaape
the optimization problem (1) translates mina,e &2n (a, c) >(||a]² ||c]|2//2 For a better a+c and
understanding of implicit regularization by wwer-parameterization we
-2_
leading to 3 w @ w v O V. This incorporation of new parameters w and v effectively over- parameterizes the problem. Finally, drop the explicit &g regularization term X(|||]| + ||cl and perform gradient descent to minimize the empirical loss Ez-(w, (w, v) in (2), in line with techniques seen neural network training, high-dimensional regression [35, 23, 44], and high-dimensional single index models [11].
2.3 Nesterov's smoothing
It is well-known that the hinge loss function is not differentiable. As result, traditional first-order optimization methods, such as the sub-gra gradient and stochastic gradient methods, converge slowly and are not suitable for large-scale problems [45]. Second-order methods, like the Newton and Quasi- Newton methods, can address this by replacing the hinge loss with a differentiable approximation [8]. Although these second-order methods might achieve better convergence rates, the computational cost associated with computing the Hessian matrix in each iteration is prohibitively high. Clearly, optimizing (2) using gradient-bused methods may not be the best choice.
To address the trade-off between convergence rate and computational cost, we incorporate Nesterov's method [28] to smooth the hinge loss and then update the parameters via gradient descent. By employing Nesterov's 's method, (2) can be reformulated as the following saddle point function:
Egnn (w, v) max PEP: 1=1
1
Σ (1 yxx (WOW Sww---- -oo--vvvll v
where Pi- {m E R" 0 S S 1}. According to [28], the above saddle point function can be smoothed by subtracting prox-function (H), where (H) is strongly convex function of with smoothness parameter y > 0. Throughout this paper, we select the prox-function as (H) 3 11l Consequently, &2n (w.v) can be approximated by
( n n1
E (w, v)
max μEP:
dd,())
(3)
i=1
Since diy (H) is strongly convex, μ4g can be obtained by setting the gradient of the objective function in (3) to zero and has the explicit form:
#r median (0. 1 181--aa y.x; "( O wwov
(4)
yn
For each sample point Z [xx, v:)). i [n], we use Ez, v) and E (w,v) v) to denote its hinge loss and the corresponding smoothed approximation, respectively. With different choices of μ4; for any i E [m] in (4), the explicit form of EZ,,, (w, v) can be written as
0, 8 E (w, = (1 (1-
if yAX (w O w - - > 1, w V 7/22, if yxx (w W / otherwise.
VOV) < yn
- (1-
(5) Note that the explicit solution (5) indicates that a larger yields smoother Ez (w, v) with larger approximation error, and can be considered parameter that controls the trade-off between smoothness and approximation accuracy. The following theorem provides the theoretical guarantee of the approximation error. The proof can be directly derived from (5), and thus is omitted here.

---

Theorem 1.
For any random sample Z' = {(x,, v:) E [n], the corresponding hinge loss (w, is bounded by its smooth approximation Egg,, (w, v), and the approximation ervor is completely controlled by the smooth parameter 7,. For any (w, v), we have
(w, S Ez. &2: 2 (w. 2
2.4 Implicit regularization via gradient descent
In this section, we apply gradient descent algorithm to Egn,, (w, v) in (3) by updating w and v to obtain the estimator of 3 Specifically, the gradients of (3) with respect to w and can be directly obtained, with the form of -2/n >i Vi/4,, @ w and 2/n > Bi @ v, respectively. Thus, the updates for w and v are given as
1 Wi+1 W. 2T T1
Σ
1 UX We and Ve41 Vi 2n n
Σ 1 Ve.
(6)
where 77 denotes the step size. Once (Wr+1. Ve+1) is obtained, we can update 3 as 3 = W O Wr+-1 V Vr+1 via the over-parameterization of B. Note that we cannot initialize the values of Wo and Vo as zero vectors because these vectors are stationary points of the algorithm. Given the and should be initialized with the same sparsity pattern as 3*. with w and Vs being non-zero and the values outside the support S being zero. However, such initialization infeasible as S is unknown. As an alternative, we initialize Wo and Vo as Wo = Vo = alpxi where a > O is a small constant. This initialization approach strikes balance: it aligns with the sparsity assumption by keeping the zero component close zero, while ensuring that the non-zero component begins with non-zero value [11].
sparsity of the true parameter 33' with the support S, ideally,
We summarize the details of the proposed gradient descent method for high-dimensional sparse SVM in the following Algorithm 1.
Algorithm I: Gradient Descent Algorithm for High- ligh-Dimensional Sparse SVM.
Given: Training set 2", initial value step size 7), smoothness parameter y, maximum iteration number Ti, validation set 2".
Initialize: Wo = alpx1, Vo = a1p x 1, and set iteration index t = 0.
While t < Ti, do
W++1
= W. + 21
Vill,,;;; ④ We:
t=1
1
Vi+1
= Vi 21
Σ
yi/4, ① V2
n
i=1
B++1
W141 O Wx+1
Vi+1 Vi+1i
0, 1
y124 Bit1 .1
Pet1
median
my
t
=t +t+1.
End if > T3 or br O. Return Set B3 as B..
We highlight three key advantages of Algorithm First, the stopping condition for Algorithm I can be determined based on the value of in addition to the preset maximum iteration number Ti- Specifically, when the values of μ4 are 0 across all samples, the algorithm naturally stops as further updates are made. Thus, f serves as an intrinsic indicator for convergence, providing more efficient stopping condition. Second, Algorithm avoids heavy computational cost like the computation of the Hessian matrix. The main computational load comes from the vector multiplication in (6). Since a considerable portion of the elements in μ are either 0 or 1, and the proportion of these elements increases substantially as 7 decreases, the computation in (6) can be further simplified. Lastly, the utilization of Nesterov's ' smoothing not only optimizes our approach but also aids our theoretical derivations, detailed in Appendix E.
5

---

3 Theoretical Analysis
In this section, we analyze the theoretical properties of Algorithm 1. The main result is the error bound [|B, 18 where 3" is the minimizer of the population hinge loss function for 3 without the & norm: 9 = arg mingeR B(1 - yx 3)+. We start by defining the 6-incoherence, a key assumption for our analysis.
Definition 1. Ler X RExP be matrix with eg-normalized columns X1, Xp. i.e, ||x||| = 1 for all i E [n.] The coherence 6(X) of the matrix X is defined as
max
(xx 2 1x,,1K ① 1k),
K K
where 1K denotes the n-dimensional vector whose i-th entry is 1 if E and 0 otherwise. Then, the matrix X is said to be satisfying 5-incoherence.
Coherence measures the suitability of measurement matrices in compressed sensing [12]. Several techniques exist for constructing matrices with low coherence. One such approach involves utilizing sub-Gaussian matrices that satisfy the low-incoherence property with high probability [9. 7J. The Restricted Isometry Property (RIP) is another key measure for ensuring reliable sparse recovery in various applications [35, 44], but verifying RIP for a designed matrix is NP-hard, making computationally challenging [5]. In contrast, coherence offers computationally feasible metric for sparse regression [9, 23]. Hence, the assumptions required in our main theorems can be verified within polynomial time, distinguishing them from the RIP assumption.
Recall that 3 E TRP the s-sparse signal to be recovered. Let S C fl.....p) ,P) denote the index set that corresponds to the nonzero components of (*, and the size |S] of S is given by Among the nonzero signal components of 3", we define the index set strong signals as S = {i E S ( 2
C, Pv PV /lg and of weak signals as S₂ = {i E S: |3 S C. Vlogp/n for some constants C, Cw > We denote 81 and 82 as the cardinalities of S₁ and S2, respectively. Furthermore, use m = minjes, |,8²| to represent the minimal strength for strong signals and к to represent the condition number-the ratio of the largest absolute value of strong signals the smallest. In this paper, we focus on the case that each nonzero signal in 3 is either strong or weak, which means that 51 + $2. Regarding the input data and parameters in Algorithm I, we introduce the following two structural assumptions.
Assumption 1. The design matrix X/ /n satisfies ô-incoherence with 0 < 8 S 1/(Ks p). In addition, every entry of X is i.i.d. zero-mean sub-Gaussian random variable with bounded sub- Gaussian norm a.
Assumption 2. The initialization for gradient descent are wo = alpx1, Vo = =alpx1 where the initialization size satisfies 0 < a & 1/p, the parameter of prox-function Y satisfies 0 < S 1/n, and the step size satisfies 0 < S (o).)...
Assumption 1 characterizes the distribution of the input data, which can be easily satisfied across a wide range of distributions. Interestingly, although our proof relies on Assumption 1, numerical results provide compelling evidence that it isn't essential for the success of our method. This indicates that the constraints set by Assumption 1 can be relaxed in practical applications, as discussed in Section 4. The assumptions about the initialization size a, the smoothness parameter 7, and the step size 7 primarily stem from the theoretical induction of Algorithm 1. For instance, controls the strength of the estimated weak signals and error components, 7 manages the approximation error in smoothing, and y affects the accuracy of the estimation of strong signals. Our numerical simulations indicate that extremely small initialization size a, step size 7), and smoothness parameter yy are not required achieve the desired convergence results, highlighting the low computational burden of our method, with details found Section 4. The primary theoretical result is summarized in the subsequent theorem.
Theorem 2. Suppose that Assumptions 1 and hold, then there exist positive constants C1 C2 C3 and es such that there holds with probability at least 1 Cin c2p that, for every time with Cg log (m////// /a²) ((mm)) < t eı log(1/a)/
log(m///
///a//////// (n log n), the solution of the t-th iteration in Algorithm 1,
B, = w, ① W. V, 2 Vo, satisfies
slogp
||B. 11 <
n

---

Theorem 2 demonstrates that if 3 contains nonzero signals, then with high probability. for any t E [ca log(m/ /a/)/ (/mm), ca log(1/a)/ nog the convergence rate of (Vvs s p/n) in terms of the &g norm can be achieved. Such a convergence rate matches the near-oracle rate of sparse SVMs and can be attained through explicit regularization using the L norm penalty [32, 46], as well as through concave penalties [20]. Therefore, Theorem 2 indicates that with over-parameterization. the implicit regularization of gradient descent achieves the same effect imposing an explicit regularization into the objective function in (1).
Proof Sketch. The ideas behind the proof of Theorem 2 are as follows. First, we can control the estimated strengths associated with the non-signal and weak signal components, denoted as l[w, @ 1s; oo and l|v, @ 1s; lo to the order of the square root of the initialization size for up to (log (l/og((/)))) //a//a()n/ n)) steps. This provides an upper boundary on the stopping time. Also, the magnitude of a determines the size of coordinates outside the signal support S] at the stopping time, The importance of choosing small initialization sizes and their role in achieving the desired statistical performance are further discussed in Section On the other hand, each entry of the strong signal part, denoted as Br @ 1s, increases exponentially with an accuracy of around O (log p/n near the true parameter 3 ( 1s, within roughly O (log(m/a²) (1ym) steps. This establishes the left boundary of the stopping time. The following two Propositions summarize these results.
Proposition 1. (Analyzing Weak Signals and Errors) Under Assumptions 1-2, with probability at least 1 - en-1, we have
1 1 and O S Vas vp" Vp
1
1w, o 1s S v
for all t S T = (llog(1/a)// (n n)), where c is some positive constant.
Proposition 2. (Analyzing Strong Signals) Under Assumptions 1-2, with probability at least ein C2p we have
logp
11, о 1s: - -3"
O 1s 100 S
n
holds for all O(log(m/a²)/(mm) <t ((log((/a)///)))o log where C12 C2 two constants.
Consequently, by appropriately selecting the stopping time t within the interval specified in Theorem 2, can ensure convergence of the signal components and effectively control the error components. The final convergence rate can be obtained by combining the results from Proposition and Proposition 2.
4 Numerical Study
In our simulations, unless otherwise specified, we follow a default setup. We generate independent observations. divided equally for training, validation, and testing. The true parameters 3 is set to mls with a constant m. Each entry of is sampled as i.i.d. zero-mean Gaussian random variable, and the labels are determined by a binomial distribution with probability = 1/(1 (1 + exp(x" 3²))))), Default parameters are: true signal strength m = 10, number of signals s = 4, sample size n = 200, dimension 400, step size y 0.3. smoothness parameter 7 = 10-4 and initialization size a 10-$, For evaluation, we measure the estimation error using ||3/1|8 - 3 |I (for comparison with oracle estimator) and the prediction accuracy on the testing set with P ()test). Additionally, "False positive" and "True negative" metries represent variable selection errors. Specifically, "False positive" means the true value is zero but detected as signal, while "True negative" signifies non-zero true value that isn' It detected. Results are primarily visualized employing shaded plots and boxplots, where the solid line depicts the median of 30 runs and the shaded area marks the 25-th and 75-th percentiles over these runs.
Effects of Small Initialization Size. We investigate the power of small initialization size on the performance of our algorithm. We set the initialization size a = {10-4, 10-6, 10008 10100-10 other parameters are set by default. Figure 1 shows the importance of small initialization size in inducing exponential paths for the coordinates. Our simulations reveal that small initialization size leads to lower estimation errors and more precise signal recovery, while effectively constraining the error term a negligible magnitude. Remarkably, although small initialization size might slow the convergence rate slightly, this trade-off is acceptable given the enhanced estimation accuracy.
10-101 J,, and
7

---

Intolestor 1e-22
Intoliztton Le-d
Infoleston
26.07
0.5
Ente Componerts
26-45
680
140
250
180
623
Effects of Initialization
(b) Paths Signals
(c) Paths of Errors
Figure 1: Effects of small initialization size a. In Figure (a)), the estimation error is calculated by
B. |/
Effects Signal Strength and Sample Size. We examine the influence of signal strength on the estimation accuracy of our algorithm. We set the true signal strength m 0.5 k k = ......27 20 and keep other parameters their default values. As depicted Figure 2, we compare our method (denoted by GD) with & -regularizedd SVM (denoted by Lasso method), and obtain the oracle solution (denoted by Oracle) using the true support information. We assess the advantages of our algorithm from three aspects. Firstly, in terms of estimation error, our method consistently outperforms the Lasso method across different signal strengths, approaching near-oracle performance. Secondly, all three methods achieve high prediction accuracy on the testing set. Lastly, when comparing variable selection performance, our method significantly surpasses the Lasso method terms of false positive error. Since the true negative error of both methods is basically 0, we only present results for false positive error in Figure 2.
Mathed
Lanz
Crucc
Methed
Nethod
1.75
1.00
180-
2.1
Daee
0.75
Prodeco
0:30
8.5
11x
0.0
20
ide
15-
15
ido
1/
150
Strorgh Sigral
Steegh of Sigral
Stergth Sigral
(a) Estimation Result
(b) Prediction Result
(c) Variable Selection Result
Figure 2: Effects of signal strength m. The orange vertical line Figure 2(a) show the threshold of strong signal log Togp/logp/ lon.//.
We further analyze the impact of sample size strength fixed at m = 5, we vary the sample size as n = 50 * k for 1...., Other parameters remain at their default values. Consistently, prediction, and variable selection, see Figure for summary of the results.
proposed algorithm. Keeping the true signal
method outperforms the Lasso method in estimation,
Performance on Complex Signal Structure. To examine the performance of our method under
more complex signal structures, we select five signal structures: (5, 6, 7, 8), B (4, 6, 8, 9), C - (3, 6, 9, 10), D (2, 6, 10, 11), and E (1, 11, 12). Other parameters are set by default. The

---

Method
Lasta
Method
Metrod L2000
21+
0.00
30
200
350
403
180
203
(a) Estimation Result
(b) Prediction Result
(c) Variable Selection Result
Figure Effects of sample size n.
results, summarized in Figure 4, highlight the consistent superiority of our method over the Lasso method in terms of prediction and variable selection performance, even approaching oracle-like performance for complex signal structures. High prediction accuracy is achieved by the both methods.
Nabe Postoe
0.2
23-
Digrennsigral
Birert
Sigrak
Estimation Result
(b) Prediction Result
Variable Selection Result
Figure 4: Performance complex signal structure. The boxplots are depicted based on 30 runs.
Performance on Heavy-tailed Distribution. Although the sub-Gaussian distribution of input data is assumed in Assumption 1, we demonstrate that our method can be extended to a wider range of distributions. We conduct simulations under both uniform and heavy-tailed distributions. The simulation setup mirrors that of Figure 4, with the exception that sample from a [-1, 1] uniform distribution and (() distribution, respectively. Results corresponding the /(3) distribution are presented in Figure 5, and we can see that our method maintains strong performance, suggesting that the constraints of Assumption can be substantially relaxed. Additional simulation results can be found in the Appendix A.
with respect smoothness parameter 7.. We analyze the impact of smoothness parameter on our proposed algorithm. Specifically, the detailed experimental setup follows the default configuration, and y replicated 30 times, and the numerical results of estimation error and four estimated signal strengths are presented Figure 6. From Figure 6, it's evident that the choice of > relatively insensitive in the sense that the estimation errors and the estimated strengths of the signals under different ys are very close. Furthermore, as y increases, the estimation accuracy experiences minor decline, but remains within an acceptable range. See Appendix A for simulation results of Signal and Signal 4.
Sensitivity Analysis
within the range [2.5 10-b 55 1 x 10-37. The simulations are

---

Method
Michod
Latte
Nothod
Pase Porkee
Estimation Result
(b) Prediction Result
(c) Variable Selection Result
Figure 5: Performance on complex signal structure under 1(3) distribution. The boxplots are depicted based on 30 runs.
45.
236-00
226-03
Cenma Values
Estimation Result
(b) Signal
(c) Signal
Figure 6: Sensitivity analysis of smoothness parameter y. The boxplots depicted based 30
runs. The estimation error is calculated by ||B |*
5 Conclusion
In this paper, we leverage paramtterizationn to design an unregularized gradient- algorithm for SVM and provide theoretical guarantees for implicit regularization. We employ Nesterov's method to smooth the re- re-parameterized hinge loss function, which solves the difficulty of con-differentiability and improves computational efficiency. Note that theory relies the incoherence of the design matrix. It would interesting to explore to what extent these assumptions can be relaxed, which topic of future work mentioned in other studies implicit regularization. It is also promising to consider extending the current study to nonlinear SVMs, potentially incorporating the kernel technique delve into the realm of implicit regularization in nonlinear classification. In summary, this paper not only provides novel theoretical results for rreetparaettrrized SVMs but also enriches the literature on high high-dimensional classification with implicit regularization.
Acknowledgements
The authors sincerely thank the anonymous reviewers, AC, and PCs for their valuable suggestions that have greatly improved the quality our work. The authors also thank Professor Shaogao Lv for the fruitful and valuable discussions at the very beginning of this work. Dr. Xin He's and Dr. Yang Bai's work is supported by the Program for Innovative Research Team of Shanghai University of Finance and Economics and the Shanghai Research Center for Data Science and Decision Technology.
10

---

References
[1] Tiago A Almeida, José María G Hidalgo, and Akeho Yamakami. Contributions to the study of sms spam filtering: new collection and results. In Proceedings of the 11th ACM symposium Document engineering, pages 259-262, 2011.
[2] Vassilis Apidopoulos, Tomaso Poggio, Lorenzo Rosasco, and Silvia Villa. Iterative regular- ization in classification via hinge loss diagonal descent. arXiv preprint arXiv:2212.12675, 2022.
[3] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[4] MA Bahraoui and B Lemaire. Convergence of diagonally stationary sequences in convex optimization. Ser- Valued Analysis, 2:49-61, 1994.
[5] Afonso S Bandeira, Edgar Dobriban, Dustin G Mixon, and William F Sawin. Certifying the restricted isometry property is hard. IEEE transactions on information theory, 59(6))3448-344 2013.
[6] Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, (1(12)4403--2255 2005.
[7] Lawrence Carin, Dehong Liu, and Bin Guo. Coherence, compressive sensing, and random sensor arrays. IEEE Antennas and Propagation Magazine, 53(():28-39, 2011.
[8] Olivier Chapelle. Training a support vector machine in the primal. Neural computation, 155-111555) 2007.
[9] David L Donoho, Michael Elad, and Vladimir N Temlyakov. Stable recovery of sparse over- complete representations in the presence of noise. IEEE Transactions on information theory, 52(1):6-18, 2005.
[10] Jianqing Fan, Cong Ma, and Yiqiao Zhong. A selective overview of deep learning. Statistical science: a review journal of the Institute of Mathematical Statistics, 36(2):264, 2021.
[11] Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in over- parameterized single index model. Journal of the American Statistical Association, pages 1-14, 2022.
[12] Simon Foucart, Holger Rauhut, Simon Foucart, and Holger Rauhut, An invitation to compressive sensing. Springer, 2013.
[13] Suriya Gunasckar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. Advances in neural information processing systems, 31, 2018.
[14] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
[15] Xin He, Shaogao Lv, and Junhui Wang. Variable selection for classification with derivative- induced regularization. Statistica Sinica, 30(4):2075-2103, 2020.
[16] P. Hoff. Lasso. fractional norm and structured sparse estimation using a hadamard product parametrization. Computational Statistics & Data Analysis, 115: 185-188999. 2017.
[17] Yuan Huang, Jian Huang, Ben-Chang Shia, and Shuangge Ma. Identification of cancer genomic markers via integrative sparse boosting. Biostatistics, 13(3):509-522, 2012.
[18] Martin Jaggi. Revisiting frank-wolfe: Projection-free free sparse convex optimization. In Interna- tional conference on machine learning, pages 427 PMLR, 2013.
[19] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On largh-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations.
11

---

[20] Rachid Kharoubi, Abdallah Mkhadri, and Karim Oualkacha. High- sigh-dimensional penalized bernstein support vector machines. arXiv preprint WrXiv:2303.09066 2023.
[21] Simon Lacoste-Julies Martin Jaggi, Mark Schmidt, and Patrick Pletscher. cookdcoor frank-wolfe optimization for structural syms. In International Conference on Machine Leurning, pages 53-61. PMLR, 2013.
[22] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521((553):436 2015.
[23] Jiangyuan Li, Thanh Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse regularization: The impact of depth and early stopping. Advances in Neural Information Processing Systems, 01222298-28309 2021.
[24] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMLR, 2018.
reguliiiatinnn in over-parameterized
[25] Jianhao Ma and Salar Fattahi. Sign-rip: A robust restricted isometry property for low-rank matrix recovery. arXiv preprint
102.02999 2021.
[26] Jianhao Ma and Salar Fattahi. Global convergence of sub-gradin rebb-raddent method for robust matrix recovery: Small initialization, noisy measurements, and parameterization. arXiv preprint vrXiv:2202.08788 2022.
[27] Cesare Molinari, Mathurin Massias, Lorenzo Rosasco, and Silvia Villa. Iterative regularization for convex regularizers. In International conference on artificial intelligence and statisties, pages 1684-1692, PMLR, 2021.
[28] Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103:127-152, 2005.
[29] Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint 175 2017.
[30] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. International Conference on Learning Representations, 2015.
[31] Daniel W Otter, Julian R Medina, and Jugal K Kalita. A survey of the usages of deep learning for natural language processing. IEEE transactions on neural networks and learning systems, 32(2):604 624, 2020.
[32] Bo Peng, Lan Wang, and Yichao Wu. An error bound for 11-norm support vector machine coefficients in ultra-high dimension. The Journal of Machine Learning Research, 17(1):8279- 8304, 2016
[33] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-288 2878, 2018
[34] Kenya Tajima, Yoshihiro Hirohashi, Esmeraldo Ronnie Rey Zara, and Tsuyoshi Kato. Frank- wolfe algorithm for learning svm-type multi-category classifiers. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 432-440. SIAM, 2021.
[35] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances Neural Information Processing Systems, 32, 2019.
[36] Athanasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, Eftychios Protopapadakis, al. Deep learning for computer vision: brief review. Computational intelligence and neuroscience, 2018, 2018
12

---

[37] Junhui Wang, Jiankun Liu, Yong Liu, et al. Improved learning rates of a functional lasso-ty type svm with sparse kernel representation. Advances in Neural Information Processing Systems, 34:21467-21179, 2021.
[38] Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value adaptive gradient methods in machine learning. Advances neural informa- fion processing systems, 30, 2017.
[39] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673, PMLR, 2020.
[40] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference on Learning Representations.
[41] Hao Helen Zhang. Variable selection for support vector machines via smoothing spline anova. Statistica Sinica, pages 659-674, 2006.
[42] Xiang Zhang, Yichao Wu, Lan Wang. and Runze Li. Variable selection for support vector machines in moderately high dimensions. Journal of the Royal Statistical Society Series B: Statistical Methodology, 78(1):53-76, 2016.
[43] Yingying Zhang, Yan-Yong Zhao, and Heng Lian. Statistical rates of convergence for functional partially linear support vector machines for classification. Journal of Machine Learning Research, 23(15)):1 2022.
[44] Peng Zhao, Yun Yang, and Qiao-Chu He. High-dimensional linear regression via implicit regularization. Biometrika, 103(4) 1046, 2022.
[45] Tianyi Zhou, Dacheng Tao, and Xindong Wu. Nesvm: A fast gradient method for support vector machines. In 2010 IEEE International Conference Data Mining, pages 679-688. IEEE, 2010.
[46] Xingcai Zhou and Hao Shen. Communicationn-effcieent distributed learning for high-dimensional support vector machines. Mathematics, 10(7):1029, 2022.
13

---

Appendix
The appendix is organized follows.
In Appendix A, we provide supplementary explanations and additional experimental results for the numerical study.
In Appendix B, we discuss the performance of our method using other data generating schemes.
In Appendix C, we characterize the dynamics of the gradient descent algorithm for minimizing the Hadamard product re-parametrized smoothed hinge loss Eg
In Appendix D, we prove the main results stated in the paper.
In Appendix E, we provide the proof of propositions and technical lemmas in Section 3.
A
Additional Experimental Results
A.1
Effeets of Small Initialization on Error Components
We present comprehensive analysis of the impact of initialization the enror components, as depicted in Figure 7. Our results demonstrate that, while the initialization size a does not alter the error trajectory, it significantly affects the error bounds. Numerically, when the initialization is 10-A the maximum absolute value of the error components around x 10-6, which is bounded by the initialization size 10 Similarly, when the initialization is 10 10 the maximum absolute value of the error components is around 7.5 x 10-14 14, which is bounded by the initialization size 10 10, The same result is obtained for the other two initialization sizes. The specific numerical results obtained validate the conclusions drawn in Proposition 1, as the error term satisfies
|| o ls = |[ C W. Ol - v. O 19 1oo $ (Va)² = a.
A.2 True Negative Results
In the main text, we could not include the True Negative error figures in 2, 3, 4, and 5 due to space constraints. However, these figures are provided in Figure 8. We observe that both the gradient descent estimator and the Lasso estimator effectively detect the true signals across different settings.
A.3 Additional Results under Uniform Distribution
As previously described, we sample X from [-1, 1] uniform distribution and other parameters
as follows: true signal structures are A = (5, 6, 7,8, B = (4, 6, 8, 9). C = (3, 6, 9, 10), D (2, 6, 10, 11), and E- (1, 6, 11, 12). The number of signals is 4, the sample size
200, dimension is p = 400, step size is 7 = 0.5, smoothness parameter is 7 10-4 and the initialization size is a 10-8 The experimental results are summarized in Figure 9. As depicted in Figure the gradient descent (GD) estimator consistently outperforms the Lasso estimator in terms of estimation accuracy and variable selection error. Both methods slightly surpass the oracle estimator in terms of prediction. However, this advantage mainly stems from the inevitable overestimation of the number of signals in the estimates by both the GD and Lasso methods.
A.4 Additional Results of Sensitivity Analysis
Within our sensitivity analysis, the simulation results for Signal 3 and Signal 4 are presented in Figure 10. We observe that the estimated strengths of the signals exhibit similar distributions across different values of the smoothness parameter y..
B Other Data Generating Schemes
In section 4, the scheme for generating y in our original submission based on a treatment similar to those in [41, 42], where the task of variable selection for the support vector machine is considered.
14

---

Infolleston
Intoltzsdoo
70-02
Enn Comporents
26-2
Ente Componerts
24-38
Jed0
140
380
Ietebbation
14-0
Intebattnn
7.54-4
Ent Compononett
Eno Compunests
180
2/
4/
Figure 7: Effects of small initialization a on error components.
In this section, we also introduce other generating schemes as adopted in [32, 15]. Specifically, we generate random data based on the following two models.
Model 1: x (O, E). E = (axy) with nonzero elements σy 0.41i-ji for 1 < i,j S p. Ply = 1|x) (xx )*) where ((-) is the cumulative density function of the standard normal distribution, 8 (1.1, 1.1, 1.1, .,.....). 0)7 and 4.
Model 2: P(y = = Ply -1) -1) 0.5, x (v
=) ~ MN u. E), x((y x1y= -1) ~ MN(-H, E), = 5, f (0.1, 0.11,..2,033044,4 0.5, 0.........00
Σ (aty) with diagonal entries equal to 1, nonzero entries dij 0.2 for Sitj S and other entries equal to The bayes rule is sign(1.39x, 1.47x2 + 1.56x; + 1.65x4 1.74xs) with bayes error 6.3%.
We follow the default parameter setup from Section 4, and the experiments are repeated times. The averaged estimation and prediction results are presented in Figure 11. From Figure 11, it's evident that the GD estimator closely approximates the oracle estimator terms estimation error and prediction accuracy.
C Gradient Descent Dynamics
First, let's recall the gradient descent updates. We over-parameterrize ,3 by writing it as where w and v are X vectors. We then apply gradient descent to the following optimization problem:
n 11 www -d, d.(w)).
min max W.V PEP,
15

---

Netiod
Mettod
23-
2.5
L5
15-
The Regatve
Thee
10.0
180
200
(a) Results in Figure
(b) Results in Figure
Method
Method
1.00
1.23
Siynals
D.Perer Signsh
(c) Results in Figure 4
(d) Results in Figure 5
Figure 8: The True Negative results correspond to the settings illustrated in Figures 2, 3, 4 and 5, respectively.
where (H)) = 21110ll? The gradient descent updates with respect to w and v are given by
W++1 = w, + 27 yi ④ Wt and Ve+1 Vt 2n Σ Mill,i Vt-
For the sake of convenience, let Gr E R represent the gradients in the form of G. 1 pa where is diagonal matrix composed of the elements of y. Consequently, the i-th element of G. be expressed as G.,; Subsequently, the updating rule can be rephrased as follows:
Σ (e, where jr, median(O, (1 yux! 3/m/mmmmmmmmmmmmmmm 1).
W = We + 21/w, ④ G. and Vi+1= = 2n/, @ 9..
Furthermore, the error parts of and v, are denoted by wt O 1gy and O 1sç. which include both weak signal parts and pure error parts. addition, strong signal parts of w, and va are denoted by Wt ② 1s, and Va O 1s, respectively.
We examine the dynamic changes of error components and strong signal components two stages. Without loss of generality, we focus on analyzing entries E Si where 3r > 0. The analysis for the case where 37 < 0 and E S similar and therefore not presented here. Specifically, within Stage One, can ensure that with high probability, for > To 2 log(m/o² (m/aa))((m)) the following
16

---

Nethod
Michod
32-
Estimation Result
(b) Prediction Result
Vellod
Last
Midied
LIISE
3.50
Tou Moydhe
(c) False Positive Result
(d) True Negative Result
Figure 9: Performance on complex signal structure under [-1, 1] uniform distribution. The boxplots depicted based on 30 runs.
results hold under Assumptions and 2:
3r
nš
a² -0² for S1, > 0,
strong signal dynamics:
Br, 2 min
1 +
2
max [||w, O 1s
los v 3 1s, bloo S a² for Sn,
error component dynamics:
max (llw, c ls ||v,
o 1s S vo for E St.
(8)
From (8), observe that for t Tu, the iterate (wa, vz) reaches the desired performance level. Specifically, each component 3r,; of the positive strong signal part Br @ 1s, increases exponentially in until it reaches 3 /2. Meanwhile, the weak signal and error part Gr @ s remains bounded by O(a). This observation highlights the significance of small initialization size for the gradient descent algorithm, as it restricts the error term. A smaller initialization leads to better estimation but with the trade-off of slower convergence rate.
After each component Br,; the strong signal reaches 3 /2. Stage Two starts. In this stage, 3r,; continues to grow at slower rate and converges to the true parameter 3 After this time, after 3 log(m/ca /a2) (rym)) iterations, Be, the strong signal enters a desired interval, which within distance of C. /oo p/n from the true parameter 83 Simultancously, the error term B O 1s; remains bounded by (aa) until (llog(1/a)/ logn)) n)) iterations.
We summarize the dynamic analysis results described above in Proposition and Proposition 2. By combining the results from these two propositions, we can obtain the proof of Theorem 2 in the subsequent subsection.
17

---

Simm
156-43 136-3 163-44 Gamma Vakkes
2s6-os 166-45 35--05 256-44 5.6--
Gammaa Vakkes
(a) Signal
(b) Signal
Figure 10: Sensitivity analysis of smoothness parameter 7. The boxplots are depicted based on 30 runs.
D Proof of Theorem 2
Proof. We first utilize Proposition to upper bound the eπror components Br 3 1s. By Proposition we are able to control the error parts of the same order as the initialization size a within the time interval 0 < & S T =log(1 /o) (44n log.). Thus, by direct computation, we have
|| C 1s;
3 2 1s 2 = |8 @
1s; + (Be 0 1s, - 3 @ 1s.)ll
(8)
3
1s 2 pl wr w. 1s; 0l (9)
C $2 logg
P 2C
where (i) is based the relationship between & norm and fox norm and (ii) follows form the results in Proposition 1. As for the strong signal parts, by Proposition 2, that with probability at least
1 oin cap obtain
81 logg
B o 1s, - -3- 330 1sssl
C s 1s, - -30 11, C?
(10)
Finally, combining (9) and (10), with probability at least - ein c2p for any that belongs the interval
it holds that
118 - 3- ||B @ 1s; -B" ④ 1195
13 O
1s; 3
1s
< <. 51 log
+ C2 logp +0
n
Since is much larger than n, the last term, 2C p. is negligible. Considering the constants Cu.. C. and Cc, we finally obtain the error bound gradient descent estimator in terms of & norm. Therefore, conclude the proof of Theorem 2.
E Proof of Propositions and 2
In this section, we provide the proof for the two propositions mentioned in Section 3. First, we introduce some useful lemmas, which are about the coherence design matrix X and the upper bound of sub-Gaussiae random variables.
18

---

metthe
Okckk
iichod
Onsee
netood
Okckk
0.4
Phodktan Aconndy
8.2
mehiod
methed
methed
(a) Model Estimation Error
(b) Model Non-normalized Error
(c) Model 1: Prediction Result
0.54
3.6-
0.99
02
melted
(d) Model 2: Estimation Error
(c) Model 2: Non-normalized Error
(f) Model 2: Prediction Result
Figure 11: Estimation error and prediction performance on Model 1 and Model 2. The boxplots are
depicted based on 30 runs. The non-normalized error is calculated by || 3 |/
E.1 Technical Lemmas
Lemma 1. (General Hoeffding's 's inequality) Suppose that 01,
... 0m are independent mean- zero sub- Gaussian random variables and (J11, Mmm) E R Then, for every t >> O, we have
ct²
P
Σ
2
<
exxp
d2 (2|
where d max; [[0:1y and is an absolute constant.
Proof. General Hoeffding's inequality can be proofed directly by the independence of ' 6m and the aab-Gaussian property. The detailed proof is omitted here.
Lemma 2. Suppose that X/ //VT is a n x p l2 lo-romaalzzed matrix satisfying ô-incoherence; that is 1/nl(x, 1x + 1x) < b, 4 j for any K S [n]. Then, for s-sparse vector E RP, we have
( ("xxxx 1)
S ds ds||z||o01
where Xx denotes the n X p matrix whose i-th column is x; if E and 0px1 otherwise.
Proof. The proof of Lemma is similar to Lemma [23]. According to the condition
x ② 1x.x X, @ 1x) 8, 8 j. CCKK [n],
n
19

---

we can verify that for any i E [p].
x X xxxxx
8s 12
24
Therefore,
xxxxxxx - -1) S <0s||z|lo0
E.2 Proof of Proposition
Proof. Here we prove Proposition by induction hypothesis. It holds that our initializations Wo = alpx1 and Vo = alpx1 satisfy our conclusion given in Proposition 1. As initialize wo, and Vo for any fixed E Sí with
|ooil = a Va and | a vā,
Proposition holds when t O. In the following, we show that for any t with 0 S t* < 7 (o/((//)/(/oo))) log the conclusion of Proposition stands for all with 0 < < E", then also stands at the (1" + 1)-th step. From the gradient descent updating rule given in (7), the updates of the weak signals and errors We,s Ut for any fixed i E Si are obtained as follows,
1,+1,1 = (1,a(1 + 2n)Ge,a) and 11+1,1 = vt,i - 2r)))
Recall that |,,,o| S 1 for 1,...,, n, for any fixed E Si, then we have
1
|Gr,al =
PLAUEIAA
km
For ease of notation, we denote M2 nn Eh ooka and M maxiesy M, Then we can easily bound the weak signals and errors as follows,
[We+1 @ ss 1l.0 (1 + Mlw,,, @ 1sylls and || @ lsy S (1 + Mn) @ 1 lla
(11)
By General Hoeffding's inequality of sub-Gaussian random variables, with probability at least 1- on - we obtain M, I a ao/log n E Si, where c is a constant. Since p is much larger than n, the inequality (1 en ")" > 1 en- holds. Then, with probability at least - cn where c is constant, we have M < a /lgn.
Combined (11) and the bound of M, we then have
||wr--1 @ 19; loc s (1 22 1s
exp((1' 1) log(1 + Mn)
S exp(TT log(1 + M1
(8)
2 exp(T" 2n
(H8)
Vo, where (i) and (ii) follow from 1" +1 < T and log(1 +x) when 0, respectively. Moreover, (iii) is based on the definition T** Similarly, we can prove that ||er- @ 1s; bloo & Va. Thus, the induction hypothesis also holds for t* 1. Since ts T is arbitrarily chosen, we complete the proof of Proposition 1.
cxp((1/2)oo((//))))
E.3 Proof of Proposition
Proof. In order to analyze strong signals: Br,, wf, vZ, for any fixed i e St, focus on the dynamics w and v² Following the updating rule (7), we have
wf+1, =m + 4mwu,, Gr, + 4n uf, 2 e 02. -4no,, 2 0 G?
(12)
20

---

Without loss of generality, here we just analyze entries i E S1 with 5 > 0. Analysis for the negative case with 3 0, E S₁ almost the same and is thus omitted. We divide our analysis into two stages, as discussed in Appendix C.
Specifically, in Stage One, since we choose the initialization Wo Vo px1x obtain Bo. for any fixed i E S1, show after 2 log( /n²)/ iterations, the gradient descent coordinate Si, will exceed /2 Therefore, all components of strong signal part will exceed half of the true parameters after 2 log(m/ (aarn/a)/,, //mm)(mm))))))) iterations. Furthermore, we calculate the number of iterations required to achieve f1,; 2 P e, where c = C.v C.ylog p/n, in Stage Two. Thus, we conclude the proof of Proposition 2.
Stage One. First, we introduce some new notations. In t-th iteration, according to the values of jr,ss we divide the set [n] into three parts, Ke, {i E [n]] Me.i }}. Kr, {i E [n] : 0 < Mt. < 1] and K,, = {i E [m] Pt. = 0}. with cardinalities of kr,1, kt.2 and kr,,, respectively. From [28, 45], most elements of f4, are 0 or and the proportion of these elements will rapidly increase with the decreasing of y, which means that k < (ke,, + ks,3) controlling 7 in a small level.
According to the updating formula of 1 in (12), we define the following form of element-wiss bound Et, for any fixed i E S as
W
(1.
1 11 (Brr 81) -8()
4n
1
w ++1,i
mm
417 (3, 13:)
wi+1i
w¹, + 7m
(13)
Wi+1,
wh,
1
(Be, (Be.- - 1B3) + 4n7(
4n
Gis
+ ym
wi+1,
Rewriting (13), we can easily get that
w = = (1
4n (Be, - + Er,
(14)
From (14), it is obvious that if the magnitude of Et, is sufficiently small, we can easily conclude that w2+ 2 w Therefore, our goal to evaluate the magnitude of &,,, in (13) for any fixed S1. First, we focus on the term Gt, + (3r, - 8 ((y) in (13). In particular, recall the definition of Gt,²a and we expand Gt. + (Be,3 - / (ym) in the following form
G yn
1
(Be, - (7) =
Σ
yk +
Σ
UkTAi
x1x7 3r ney
+ ym
(Be, 18))
KEK11
kEK22
Σ
BLuKi +
Σ
yk.IKs
1
Σ
In.i Br m(Br, - Bi)
TOY
7n2
K
kE K
keKia
(yk
X )orks
Tki +
npy
KEKLi
kEKia
Σ 71
x (B. - 1²) -Br,a -
7/0
KEKs
((1) (I2).
For the term (Ti), by the condition ke, & 1 and General Hoeffding's inequality, we have
1
Σ
(yk - xf 3
logp ov
logg
(15)
ny
KE
K..
k
holds with probability at least - -1 where c constant.
21

---

For the term (12), let X1,2 E Rx*p denote the matrix whose k-th column is X₁. if E Ke.2. Then, we approximate (I2) based on the assumption on the design matrix X via Lemma
- X B*) (B, о 1s 3 e ls)) n
- ŌsKm.
(16)
By (15), (16), condition of the minimal strength 1/ (1s p), we have
logpy /ogp/n and condition å x
G - 7m
97) (Br.5 -37)
S
m
(17)
yn log
Then, we can bound G through
GG,, $ |Gt, + (11/(mm) 32) (1/ 1921
1
(18)
+ km
ym
log p
Note that for any fixed E S1, Gt S <n Ex= [ By General Hoeffding's 's inequality, we have with probability at least 0 Gr,il S log n and then |nGr,sl < based on the assumption of 7). Therefore, w2,//=/1,, always bounded by some constant greater than 1.
Recalling the definition of element-wise bound Er,s. and combining (17) and (18), we have that
(6) S
Ke,al
logp + 1/² x² x2mm²
mm
mm
(19)
yn
ynn
log
where we use the bound of w,,,/u/" /u/+1, for any fixed E S₁ in step(i) and step (ii) is based on
mpmm S m/ logp and km S 1. Thus, we conclude that E,, is sufficiently small for any fixed E S₁.
Now, for any fixed E S1, when 0 S 3r. S /8 /2, we can get the increment wf,, for any fixed i Si according to (19),
2 w1+
2
4n
(Be,5 - B7) -
/ 1
17m log
1,
Wi
m
Im
20184
/ (1
7pm yn p/
w
1
y
(18) 2 W
n
+
ym
where (i) follows from 0 < 31, < 81/2 and (ii) holds since m/ log p S B7 Similarly, we can analyze v2, to get that when < 3r, S B /2,
i1, - o, (1 101--1////1 7/8//mm) /mm)
Therefore, w²,, increases at an exponential rate while u², decreases an exponential rate. Stage One ends when R1, exceeds /3, /2, and our goal to estimate fço that satisfies
6,0
1:00
(1-
Be,
a²
a²
/
n
Note that 1e20 forms decreasing sequence and thus is bounded by a² Hence, it suffices to solve the following inequality for ts,0-
(I+
1
2,0
a²
2 1
which is equivalent to obtain 4, satisfying
8+ 20
n7.
4,o 2 Tí,0 = log
+
log
[+ mm
22

---

For Tio, by direct calculation, we have
(X)
8a
/
T,,0 S log
+
1
+
2a
y
7m
(0)
2 log
where (i) follows from z log. x + 2 when x 2 and (ti) holds due log(x/2 1) < log
when x 2 2 as well as the assumption on y and n5; S 1. Thus, we set t,,0 = 2 2oog (m)33) such that for all t 2 t4,0, Br, /2/2 for all E S1.
Stage Two. Define c C.vlogg log p/n and 011 bound i according to (13). For any fixed E S,, if there exists some such that 1 S a S 0;,1 and
(37 Next, we refine the element-wiss
(1 (1-1/ 1/2 < 3t, s (1 1/2n+1 then, based on the analytical thinking in Stage One, we can easily deduce that
17m
Ltal
S
(20)
2 logp
Using this element-wee -wiee bound (20), we get the increment of wi+1, and decrement of u2+1,
2 2 w², (1 n
n/3r
and 22+1,1 S u2.,5
2anm
2
We define ti the smallest t such that Be4 2 (1 - n/ 1,8"" Intuitively, suppose that the current estimate Be, is between (1 ) and 1/20-1) 118%, aim to find the number of iterations required for the sequence (. exceed (1 1/20+ 1) To obtain sufficient
condition for ti we construct the following inequality,
vG,6 (1- 20mm
1133
Betti 2 wł.s
I+
2 (1 - (1-112242)
20mmm
Similar with Stage One, the sequence following inequality for ti,a.
(12,)120 is bounded by a² Then, is sufficient to solve the
(1 (1-1/20+1)08 a²
nB 20mm
li,a : Ti,a log
log 1
w
To obtain a more precise upper bound of Ti we have
- 11-1122+1)83 + a²
n13
Tia = log
log
1
w
2aym
(1 - 1 + +
log
log
1
(1 - 1/24),8
20mm
(2) log
1/20+1
2
(
not
1+ 1/2a
+
(1 - 1/22),3
2anm
2amm
where (i) is based on the condition w x 2 0. By direct calculation, we obtain
> (1 1 1/29) (ii) stands since x log r + 1 > 0 when
(zi1)
1/20+1
a²
n
Tia
1
1/2a
(1
1/20)
2a+lon
(21)
(iv)
2
2a-2
11
where we use log(z + 1) < r when x 2 0 in step (iid) and 1 - 1/22 2 1/2 in step (iv), respectively.
Recall the assumption < 0 [10 /e)] with Covlog p/n, then get 2a+2 <
23

---

43% c I 4 Ayn/ log p5; /C.. Moreover, by the assumption on the initialization size a, we have a² S Ca/p². Thus, we can bound a=+222/n3² in (21) as
20
4C. logp Cep2ns
(
(22)
n V
7/1
where (i) holds when p² logp 2 40 VCovi/CC. Combined (21) and (22), we calculate the final bound of T i,a
T3 S n1,
for any S. 01,1. If there exists an 1 S a S 41, such that Be, (11-1/29)) ( (1-1/2a+ after t,a 2 3/m3f iterations, we can guarantee that 3 2 (1 - 1/2 Now recalling the definition of 01,1. have 8 /2 I Cevlogp/r Therefore, with at most Ea=d Tia iterations, have Br, 2 8 e. By the assumption of a. we obtain
a1.
-
1/ (n13)
Σ Ti I 2 2llog(B) 200g((3//a2/(m8) + 3 log2
a=0
< 5 log
(m
Since the function log(x/a²)/ (1zz) is decreasing with respect we have after 5 llgg(m/a))//// (1mm) iterations that |3r,a 871 S Vlogp/ p/n for any fixed St. Thus, we complete the proof of Proposition 2.
24


Reviews:
[{"review_id": "VUUYmjOaf8", "reviewer": "Reviewer_i2nR", "summary": "This paper studies the implicit regularization in over-parameterized (sparse) support vector machine. The paper by nature is an extension of Vaskevicius et al [28], applying the quadratic reparametrization on SVM (hinge loss). Due to the non-differentiability of hinge loss, Nesterov’s smoothing is applied to enhance the computational efficiency. The authors then propose a regularization free gradient descent algorithm and show that the sparse solution is obtained with early stopping. The convergence result is demonstrated via numerical simulations. This is an active area of research, and the contribution is relevant. My concern is more about the setting/significance of this work. The authors claim that “this is the first study that investigates implicit regularization via gradient descent and establishes the near-oracle rate specifically in classification” (line 49). First of all, the implicit regularization via gradient descent in classification has been studied in [12, 27] for logistic/exponential losses. Therefore, the contribution to hinge-loss is appreciated (with the remedy of Nesterov's smoothing). Secondly, when it comes to classification problems, sparsity is relatively minor and the implicit regularization effect is shown via max-margin/separability. More discussion would be helpful about the sparse SVM. \n\nThese two papers [W]&[Z] below may be closely related to the implicit regularization effect studied in this paper but missed in the related works.\n\n[W] B. Woodworth et al, Kernel and Rich Regimes in Overparameterized Models, COLT, 2020. \n\n[Z] P. Zhao et al, High-Dimensional Linear Regression via Implicit Regularization, Biometrika, 2022.\n", "questions": "1. I didn’t find the definition of either $\\beta^\\star$ or the data generating mechanism. This may cause a big concern if the authors implicitly assume $y=X\\beta^\\star$ somewhere, which would be very restrictive. In line 258, the simulation follows a logistic model. Is that also the case for theorem 2? If $\\beta^\\star$ is a minimizer of the population version of the hinge loss, is that for Eq. (1) or Eq. (3)?\n2. Formatting issue in [11]\n3. Is there a reason that the oracle method performs the worst in Figure 2 (b)?\n4. Is Nesterov’s smoothing necessary here? How about plain sub-gradient descent with quadratic parameterization?\n5. For Proposition 2, isn’t the upper bound of t in Proposition 1 still needed? I didn’t check the proof details, but intuitively the convergence on the support is only guaranteed while the error accumulation outside the support remains small. Correct me if I’m wrong. ", "limitations": "The significance/importance/potential application of this work is not well discussed. \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The implicit regularization under hinge-loss is novel.\n2. Some theoretical results in this paper are interesting.\n", "weaknesses": "1. The importance of sparsity in SVM and how that affects the classification performance is not discussed.\n2. Some metrics used in simulations are not defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback on our paper. We'll carefully review each point and provide explanations. If you have any new questions or ideas, please don't hesitate to share them with us. \n\n1. More discussion of the sparse SVM. \n\nIn modern applications, we frequently encounter classification challenges amidst an abundance of redundant features. The prevalence of sparse-scale data is particularly pronounced in fields like finance, document classification, image analysis, and gene expression analysis. To illustrate, in genomics, only a handful of genes from thousands of candidates are utilized to construct a classifier for disease diagnosis and drug discovery. Similarly, in spam classification, an accurate classifier is sought using a relatively small selection of words from a dictionary containing numerous different terms. In such scenarios, there are potential limitations associated with standard SVMs or SVMs augmented with explicit regularization (such as L2 norm). From an applied perspective, incorporating sparsity into SVMs presents an intriguing avenue for exploration. \n\nConversely, it's well-established that sparsity considerations have undergone extensive and in-depth exploration in regression in recent years. However, the exploration of theoretical assurances for sparse SVMs is comparably less extensive. Typically, the focus revolves around generalization error and empirical risk analysis, with even fewer discussions on variable selection and error bound. Our study of implicit regularization in classification problems, as presented in this paper, stands as a complementary endeavor to the theoretical pursuits within the realm of sparse SVMs.\n\n2. Differences with existing studies of implicit regularization in classification.\n\nCompared to these existing work [12,27], our approach adds a crucial extra step – quadratic parameterization. This step involves using two vectors, w and v, and combining them in a special way: $\\beta=w\\odot w-v\\odot v$. Although this unique step makes our theory more intricate, it lets us precisely understand how gradient descent changes over time, which is explained more in Appendix B. we can theoretically determine How the real signal changes at certain stages and how the error is controlled, which helps us to understand more clearly how the parameters change in gradient descent, which is difficult to see in previous classification work. \n\nAdditionally, while previous work often relates the speed of convergence to the number of steps taken, like ${\\cal O}(1/\\log t)$, our paper's theory showcases that the gradient descent method can achieve a rate of convergence that doesn't depend on the step count $t$, within a certain range. This is a theoretical improvement in how we understand the process.\n\n3. Supplement to the real coefficients $\\beta^*$.\n\nThank you very much for pointing this out for us, we omitted the definition of  the true parameter $\\beta^*$ in the main text.The key result of the paper is an error bound $||\\beta_t-\\beta^*||^2$, where $\\beta^*$ is the minimizer of the population version of the hinge loss function (with respect to $\\beta$, without $\\ell_1$ norm), that is, $\\beta^*=\\arg\\min_{\\beta}{\\mathbb E}(1-yx^T\\beta)_+$. We will certainly make the necessary revisions in the updated version. Moreover, our data generating mechanism in the simulation is within the domain of Theorem 2.\n\n4. Reason why the oracle method performs the worst in Figure 2(b)\n\nIn high-dimensional settings, both the GD estimator and the lasso estimator tend to overestimate the number of signals, which is more than the true number of signals. Consequently, both estimators incorporate a larger number of features, potentially resulting in an improved but ultimately misleading predictive performance.\n\n5. Necessity of Nesterov’s smoothing\n\nIn over-parameterized applications, like the case of gene data classification, the non-smooth nature of the hinge loss poses significant computational and accuracy challenges. Standard first-order methods like the subgradient and stochastic gradient techniques don't achieve rapid convergence for large-scale problems. Second-order methods like Newton's approach and simulated Newton's method can be used, but they're computationally demanding due to the need for the Hessian matrix in each iteration. As a result, a common approach to tackle these complexities in large-scale problems is to 'smooth' the hinge loss. Numerous smoothing methods have been proposed and proven effective in real-world data applications. Given this landscape, using Nesterov's smoothing makes sense in over-parameterized scenarios. It's practically essential. \n\nAdditionally, incorporating Nesterov's smoothing aids in our theoretical deductions. If we were to directly analyze the gradient algorithm with quadratic parameterization for the non-smooth hinge loss (which is computationally possible), its non-differentiability would complicate the theoretical deductions. In essence, Nesterov's smoothing plays a significant role both computationally and theoretically.\n\n6. Explanation of Proposition 2\n\nYour observation is spot-on, and we appreciate you bringing it up. There is indeed an upper limit on the number of iterations to manage the size of the error term outside the support set. The confusion might arise because we presented the error term and strong signal term in two separate propositions. This layout could give the impression that Proposition 2 lacks an upper bound on the number of iterations. We will address this issue and rectify both propositions in the revised version. Thank you for highlighting this, as it helps us enhance the clarity of our work.\n\n7. References and Formatting issue\n\nWe take note that you have provided us with new literature [W], related to implicit regularization, which we will cite in the revised version. Meanwhile, we will revise the formatting issue you mentioned, thanks for pointing it out!"}, {"review_id": "IM2JHCXTid", "reviewer": "Reviewer_Z81p", "summary": "The paper tackles the problem of implicit regularization for classification in the context of over-parameterization. Starting from a $L^1$ regularized SVM, they voluntarily over-parameterize the feature vector $\\beta = w \\odot w - v \\odot v $ using two vectors $w, v \\in \\mathbb{R}^p$.\n\nThe optimization process then consists in (i) dropping the explicit regularization, (ii) smoothing the hinge loss function, (iii) applying gradient descent with early stopping to get the solution.\n\nA theoretical analysis of the estimated parameter is provided, showing under mild conditions that the proposed scheme behaves as well as the explicit regularization scheme if the algorithm is stopped at a certain time.\n\nNumerical experiments highlight the benefits of the approach on synthetic data.", "questions": "- The problem considered here is a linear SVM with $L^1$ penalization. Would the results presented here still hold for a non-linear SVM based on a finite-dimensional feature map ?\n\n- At one point, you drop the explicit regularization to only minimize an empirical risk. What is the ingredient in the algorithm that allows to recover properties similar to the explicit regularization ? Once the regularization is dropped, we could say that the original problem considered another one - e.g. Tychonov regularization - but no the solution presented here retains specific properties usually associated with the $L^1$ penalty. Could you comment on that ?\n\nTypos/remarks:\n\n- Line 18: on gradient based methods\n- I believe it would be of interest to cite [A] alongside [1] and [27] in the introduction, given the link they explore with the Lasso problem.\n- Line 44: Why $u_0$ and not $w_0$ ? Please be consistent with the notation from line 42\n- Line 47: \"near-oracle rate is achievable via explicit regularization using explicit regularization\"\n- Line 145: \"and has an explicit form that\" writes ?\n- Line 146: given that you already use a superscript in equation (4) for $\\mathcal{Z}^n$, you should use a subscript here to avoid overcharge.\n- Line 229: \"that scales as $\\mathcal{O}$\"\n- Line 236: the subscripts are not correct (two times the complement)\n\n[A]: Iterative regularization for convex regularizers; Molinari, Cesare and Massias, Mathurin and Rosasco, Lorenzo and Villa, Silvia; AISTATS 2021", "limitations": "Limitations have overall been addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The topic is of interest for the machine learning community.\n- The paper is well written and mathematically sound.\n- The developed method is novel.\n- The experimental study is convincing.", "weaknesses": "- No real weakness", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable feedback you've provided on our paper. We will go through each point and provide explanations. If you have any new questions or ideas, please feel free to share them with us.\n\n1. Future work about implicit regularization in Non-linear SVM.\n\nExploring implicit regularization in nonlinear SVM is a direction we're considering for future work.\nNote that the proposed method can be extended to the non-linear SVM with a finite-dimensional feature map, which includes the polynomial kernel. Specifically, it is clear that the kernel SVM with linear kernel is exactly the same as our proposed method. Once the polynomical kernel is used, we may reparameterized the corresponding coefficent with some high order vectors, and the theoretical results may be established with some modificatiokns. In the revised version, we have added some detailed discussions on the potential route of extending the proposed method to the nonlinear SVM with finite-dimensional feature map.\n\n2.  What allows our algorithm to recover properties similar to the explicit regularization？ \n\nImplicit regularization is the focus of our paper, and we provide a comprehensive explanation here. Many optimization challenges in networks involve aspects like nonconvexity [C1], nonlinearity, and over-parameterization. These problems potentially lead to subpar performance in regression or classification tasks from a statistical standpoint. \n\nHowever, what's interesting is that practical observations show that simple algorithms like (stochastic) gradient descent often manage to find the global minimum of the loss function, even when faced with nonconvexity. This happens without the need for explicit regularization [B, C2]. In other words,  in over-parametrized statistical models (like our experimental setup), although the optimization problems consist of bad local minima with large generalization error, the choice of optimization algorithm, usually a variant of gradient descent algorithm, usually guard the iterates from bad local minima and prefers the solution that generalizes well. As a result, we don't introduce an extra regularization term to the optimization goal. Instead, the optimization algorithm itself showcases implicit preferences that effectively play the role of regularization. \n\nWe can interpret the iteration count $t$ as a kind of regularization parameter, similar to $\\lambda$ in the lasso penalization algorithm. Our approach attains the desired performance when the number of iterations falls within the appropriate range.\n\n[C1]Yun, C., Sra, S. and Jadbabaie, A. (2019). Small nonlinearities in activation functions create bad local minima in neural networks. In *International Conference on Learning Representations*.\n\n[B] Neyshabur, B., Tomioka, R. and Srebro, N. (2015). In search of the real inductive bias: On the role of implicit regularization in deep learning. In *International Conference on Learning Representations*.\n\n[C2] Zhang, C., Bengio, S., Hardt, M., Recht, B. and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. *International Conference on Learning Representations*.\n\n3. Typos and Remarks.\n\nThank you for your thorough feedback. We will diligently address each of the typos you've highlighted. Furthermore, [A] extensively covered implicit regularization within linear models and delved into L1 penalty and early stopping. This reference is incredibly valuable to us, and we will certainly include it in the revised version. We appreciate your keen observation and for bringing this to our attention."}, {"review_id": "TWuQANBfsM", "reviewer": "Reviewer_S4hZ", "summary": "This paper design a regularization-free algorithm for high-dimensional support vector machines (SVMs) by integrating over-parameterization with Nesterov's smoothing method, and provide theoretical guarantees for the induced implicit regularization phenomenon.", "questions": "Please refer to the Weakness.", "limitations": "No", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides a regularization-free gradient method that has proven to be effective in practice and is supported by some theoretical guarantees. The theoretical results are novel, and the experiments are comprehensive.", "weaknesses": "The theoretical results are relatively weak.\n\n1. The constants $c1\\sim c{4}$ in Theorem 2 are not clearly specified, so we cannot see the trend of these constants changing with the problem size (are they independent of $p$?), which weakens the results. \n\n2. The author did not compare the strength of the $\\delta$-incoherence assumption and the RIP (Restricted Isometry Property) assumption (only a comparison for verifying difficulty was made). This comparison should be included.\n\n3.The restrictions on the initial values in Assumption 2 may seem somewhat stringent. The author may provide an explanation for why they are designed this way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you put into reviewing our work. We've reviewed your comments and summarized our responses below. Please let us know if you have any additional comments or concerns.\n\n1. Clear specifications about the constants $c_1\\sim c_4$ in Theorem 2.\n\nThank you for highlighting this for us. We prepare a more detailed explanation of the constants. In Theorem 1, the constants $c_1$ and $c_2$ arise from inequalities related to sub-gaussian random variables, these constants remain unrelated to $n$ or $p$. Likewise, the constants $c_3$ and $c_4$ are associated with the interval of iterations, and we can give the specific form of this interval, $[5\\log(m/\\alpha^2)/\\eta m,\\log(1/\\alpha)/(4\\sigma\\eta\\log n)]$, thereby setting $c_3=5$ and $c_4=1/(4\\sigma)$. Notably, our assumptions do not involve $\\sigma$, so $c_3$ and $c_4$ remain independent of $n$ or $p$. In conclusion, these constants do not undermine the theoretical results.\n\n2. Comparison of the $\\delta$-incoherence assumption and the RIP assumption.\n\nThis is a pertinent question, and we appreciate the chance to provide a clearer explanation of these two assumptions. The incoherence and RIP are powerful performance measures for guaranteeing sparse recovery and have been widely used in many contexts. Sub-Gaussian matrices satisfy low-incoherence and RIP property with high probability. In fact, incoherence and RIP imply each other[E], showing their close connection. \n\nHowever, compared to the incoherence assumption, the RIP poses a couple of challenges. Firstly, RIP verification becomes NP-hard when dealing with pre-constructed design matrices. Secondly, the RIP's formal complexity renders it challenging to compute. In prior explorations of implicit regularization in matrix factorization and linear regression, some scholars have flagged issues with RIP assumptions. For instance, RIP cannot capture the behaviour of $\\ell_2$-loss in the high noise regime [M], and RIP condition could potentially be replaced [28, 34]. Consequently, we opt for the more flexible incoherence assumption in this paper, a choice supported by recent work [18].\n\n[E] Candes, E.J., 2008. The restricted isometry property and its implications for compressed sensing. *Comptes rendus. Mathematique*, *346*(9-10), pp.589-592.\n\n[M] Jianhao M and Fattahi S. Global convergence of sub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization. *Journal of Machine Learning Research* 24.96 (2023): 1-84.\n\n3. Detailed explanations about Assumption 2.\n\nThe details in Assumption 2 are also worth looking into. In addition to explanations in the paper, we're providing more insights here based on both theory and experiments. Firstly, the assumptions about the starting value $\\alpha$, parameter $\\gamma$, and step size $\\eta$ mainly stem from the theoretical side of the algorithm. For instance, $\\alpha$ controls the strength of the estimated weak signals and error components, $\\gamma$ manages the approximation error in smoothing, and $\\eta$ affects how accurately we estimate strong signals. So, assumptions about these are necessary. Now, for the assumptions about $\\alpha$ and $\\eta$—where we say $\\alpha \\lesssim 1/p$ and $\\eta \\lesssim 1/(\\kappa \\log p)$—we're not sticking strictly to the $\\le$ sign, but $\\lesssim$. These assumptions aren't too strict, and in our tests, making them really small isn't necessary for good results. For example, we tried $\\eta = 0.5$ (much larger than $1/(\\kappa \\log p)$), and even with a larger $\\alpha$ like $10^{-4}$, we still got good estimates. \n\nSpeaking about $\\gamma$, we're strict in the assumption, but in our experiments, we can be a bit flexible. We tested different $\\gamma$ values, like $10^{-4}$, $10^{-3}$, and $5 \\times 10^{-3}$, for estimation and finally we got the estimation errors of $0.383$, $0.404$ and $0.519$, and the four strong signals are estimated as $[5.8,5.8,6.6,6.6]$, $[5.6,5.6,6.4,6.4]$ and $[4.4,4.5,5.2,5.2]$, respectively. Even with larger $\\gamma$ values—like scaling it up a lot—we still got good results in estimating errors and strong signals. To sum it up, the setting of parameters is very common. In related studies like [10,18, 28, 34], they make certain assumptions about initial values and step sizes. In experiments, we can relax the rules a bit. There's no need to make the parameters super small to get the results we want.\n"}, {"review_id": "b2OBOFhaEv", "reviewer": "Reviewer_6PiA", "summary": "The paper proposes an iterative/implicit regularization algorithm for sparse SVM, using an Hadamard product overparametrization of the iterate $\\beta = u \\odot u - v \\odot v$. In addition, a Nesterov smoothing of the Hinge loss (replaced by its Moreau envelope, a term that is lacking in the paper) is performed.\n\nThe main result is Theorem 2, stating that results equivalent to that of explicit penalization approach can be obtained, under similar assumptions (subgaussianity of the samples, low incoherence of the design matrix), in terms of oracle error with high probability.", "questions": "see weaknesses above", "limitations": "no societal impact", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Implicit regularization is a very active area of research; implicitly regularized algorithms usually require a lower computational budget. Extending known results from regression and sparse matrix factorization to classification is interesting.", "weaknesses": "- no code is included in the supplementary material, and no code release is mentioned in the paper.\n- the writing of the paper can be strongly improved; it would benefit from being proofread by a proficient English reader.\n    - E.g. in the first two lines, do not use \"the\" in \"based on the gradient-based methods\", and use plural in \"models, such as the deep learning model\" (there are more than one DL model...)\n    - L20, \"tend to converge to the global minimum.\" : a global minimum\n    - \"$s$ is number of signals\"\n    -  near-oracle rate is achievable via explicit regularization using explicit regularization\n    -  show that gradient descent estimator: missing \"the\"\n    - L110 why \"that\"?\n    - L120 repeats the same idea twice\n    - proxy parameter instead of prox parameter, and it would be clearer to call it \"smoothing paramter\" or Moreau envelope paramter.\n    - etc etc.\n- the paper also lacks rigor and clarity in its writing in many places, e.g. \"the zero component is initialized close to zero\". What the authors mean is that the coordinates which are zero **in $\\beta^*$** are initialized closed to 0 **in the optimization variable**. $\\beta^*$ is not even defined.\n- the algorithm's stopping criterion is based on $\\mu_i$, and the algorithm stops\nwhen all $\\mu_i$'s are negative. This means that all training points are classified in their observed classes. In the case of label noise, doesn't this lead to overfitting? How is this stopping criterion related to the bound on number of iterations $t$ in Theorem 1 and Proposition 2?\n- why is the performance measure not $\\Vert \\beta - \\beta^* \\Vert$ in the experiments? Why are the vectors normalized? This does not match the metric used in the theoretical results.\n- the approach simply drops the two L2 regularization terms, $\\Vert w \\Vert^2 + \\Vert v \\Vert^2$, that come from the original L1 regularization term $\\Vert \\beta \\Vert_1$. Why?\n- the authors claim that there is no parameter in their approach, but the smoothing of the hinge loss does require one.\n- why is $d_\\gamma$ called a prox-function, when it's just a strongly convex function? why introducing a general notation when only the squared L2 norm is used (l142)\n- why are there 3 orange curves in Fig 1c? shouldn't those be shaded plots? Where is the rud curve? can you sort the legend by increasing value instead of having 1e-10, 1e-4, 1e-6 in that order?\n- How is Lasso's (L1 regularized SVM) regularization parameter tuned?\n- Unless I'm mistaken, thee iterates of the proposed method are never exactly zero. Some thresholding needs to be performed in order to avoid dense vectors and many false positive (Fig 2c for example). How is this done?\n\n\n- \"we present finite sample performances of our method in comparisons with the Lasso estimator\": SVM is for classification, Lasso is for regression. How can you compare them? Do you mean L1 regularized SVM?\n- under the assumption of Sub-Gaussian distribution: mention that this is about the noise\n- L114 the fact that there is a generative model with \"true parameters\" is completely missing\n- L139 it's a saddle point problem not a saddle point function\n- In Thm 1 there is no need to mention randomness, as the generative model does not come into play. Making this a theorem is a bold move.\n- the legends in the plots are too small to be read.\n\n### References\n- The proposed Hadamard parametrization is, up to my knowledge, proposed by Vaskevicius. This could be explicitely stated L43 (though it is currently mentioned, it comes later in the paper)\n- A generic algorithm for any type of sparse regularization is proposed in \"Iterative regularization for low complexity regularizers\" (Molinari et al, 2022). In particular, handling of sparse classification is proposed in example 1. How does the proposed approach compare?\n- the authors should cite \"Smoothing and first order methods: a unified framework\" by Beck and Teboulle (2012). Their thm 1 is a known result of this paper, which holds for \"inf-convolution\"/Nesterov smoothing regardless of the function being smoothed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reading our paper and sharing valuable feedback. Due to character limits, we can't address every question separately. We will fix all writing mistakes and unclear parts you've pointed out in the revised version. For other questions, we address them here. If you have more questions, please let us know without hesitation.\n\n- Code.\n\nIn our revised version, we will add a GitHub link. Notably, our algorithm is straightforward. We obtain the lasso estimator through R packages 'sparseSVM' or 'penalizedSVM.' The oracle estimator can be derived from standard SVM.\n\n- Supplement to the setting of initialization and true parameters $\\beta^*$.\n\nWe explain more about initial setting. Ideally, we'd initialize $w$ and $v$ to mirror the sparsity pattern of $\\beta^*$—meaning $w_S$ and $v_S$ would be non-zero, while the values outside the support would be set to 0. Unfortunately, this isn't feasible due to the unknown support of $\\beta^*$. Instead, we initialize as $w_0=v_0=\\alpha1_{p\\times 1}$. This approach strikes a balance: zero components receive almost-zero initial values ($\\alpha$ being very small), and nonzero components receive non-zero initializations. Regarding the definition of real $s$-sparse parameter $\\beta^*$, which we forgot to declare in the main text, $\\beta^*=\\arg\\min_{\\beta}{\\mathbb E}(1-yx^T\\beta)_+$, we will also add it in the revised version.\n\n- Discussion of the stopping criterion.\n\nIn an ideal setup, we can rely on $\\mu_i=0$ to stop iterations, such as in the simulations. In general, we still keep the maximum number of iterations $T_1$ as a stopping condition, (see Algorithm 1), and this stopping condition can be applied to all cases. If we know all parameters, we can estimate the ideal iteration range and subsequently set $T_1$.\n\n- why is the measure normalized? \n\nWe used normalized metrics to compare with the oracle estimator. In simulations, the oracle estimator exhibits a large error before normalization, and a smaller error after normalization. For instance, when dealing with signals like (5,6,7,8) (normalized to (0.38,0.45,0.53,0.61)), the oracle estimator produces values of (1.27,1.57,1.88,2.11) (normalized to (0.37,0.45,0.54,0.61)). The GD estimator yields (3.3,3.97,5.01,5.74) (normalized to (0.36,0.43,0.54,0.62)). \n\nWhile we used the normalized metric for comparison, note that the GD estimator performs well under the $||\\beta_t-\\beta^*||$ metric.\n\n- Reason why we drop the two L2 regularization terms.\n\nWe explain more here. First, the motivation of  implicit regularization comes from some interesting phenomena in deep learning. Applying deep learning to regression and classification, the regression function or classifier is represented by a deep neural network. But the loss function is nonconvex. In addition, neural networks are over-parameterized, which makes the regression or classification ill-posed statistically. However, people found that simple algorithms such as gradient descent tend to find the global minimum of the loss function. \n\nTo understand why, [B,C] suggest that generalization stems from implicit regularization of optimization algorithms. They observed that in over-parameterized models , the algorithm, usually a variant of the gradient descent, prefers solutions that generalize well. Without adding any regularization term, it is the implicit preference of the algorithm that acts as a regularizer. For this reason, in recent work on implicit regularization in statistical models (e.g., regression), scholars follow this line by not adding any regularization terms and focus on the implicit regularization of the algorithm.\n\nTo be specific, in line 122, the new optimization is $\\min{\\cal E}_{{\\cal Z}^n}(a,c)+\\lambda(||a||^2+||c||^2)$. Following neural network training, we remove $\\ell_2$ norm, a practice that is common in implicit regularization work[10, 28, 34].\n\n[B] Neyshabur, B., Tomioka, R. and Srebro, N. (2015). In search of the real inductive bias: On the role of implicit regularization in deep learning.\n\n[C] Zhang, C., Bengio, S., Hardt, M., Recht, B. and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. \n\n- The smoothing requires one parameter.\n\nThe smoothing does require a parameter $\\gamma$, but the constraint on $\\gamma$ is quite relaxed, requiring no complex tuning.\n\n- why is $d(\\gamma)$ called a prox-function?\n\nOur smoothing follows [22], hence certain terms are adopted from the original paper. We'll modify the expressions in the revised version.\n\n- Explanation of Fig 1b and Fig 1c.\n\nFig 1b shows strong signal magnitudes over iterations, while Fig 1c shows error term magnitudes over iterations. Mean values are presented in both figures, omitting quartile-shaded areas for clarity.\n\nOnly 3 orange curves in Fig 1c results from larger estimation error magnitude for 1e-4 compared to the other initial values. For enhanced clarity, an \"Error Components\" Fig is added in \"General.pdf\". This figure aligns with Proposition 1: $\\Arrowvert\\beta_{t}\\odot1_{S_1^c}\\Arrowvert_{\\infty}=\\Arrowvert w_{t}\\odot w_t\\odot1_{S_1^c}-v_{t}\\odot v_t\\odot 1_{S_1^c}\\Arrowvert_{\\infty}\\lesssim (\\sqrt{\\alpha})^2=\\alpha$.\n\nWe'll reorganize the legend in ascending order based on values, as you suggested.\n\n- Tuning in Lasso\n\nThe tuning methods in ‘sparseSVM’ and ‘penalizedSVM’  are cross-validation by default.\n\n- Thresholding procedure. \n\nAfter getting GD estimator and lasso estimator, we choose a threshold (like 1e-5), coordinates less than the threshold are counted as 0.\n\n- Discussion of References.\n\nComparing with (Molinari et al., 2022), we have these distinctions:\n\n1. Our focus is on gradient descent without explicit regularization, while Molinari works on primal-dual algorithm with regularization.\n2. We analyse error bound of iterates, while Molinari analyse stability bound.\n3. We introduce reparametrization to classification, studying gradient descent dynamics. This novel aspect is unexplored in classification."}, {"review_id": "2N0XpQ4ERA", "reviewer": "Reviewer_4Xb3", "summary": "A regularization-free algorithm for high-dimensional support vector machines (SVMs) is designed by integrating over-parameterization with Nesterov's smoothing method, which induces implicit regularization. An over-parameterized hinge loss function is constructed and true parameters are estimated by leveraging regularization-free gradient descent on it. Nesterov's method enhances the computational efficiency of the algorithm, particularly in terms of determining the stopping criterion and reducing computational complexity. With appropriate choices of initialization, stepsize, and prox-parameter, unregularized gradient descent achieves a near-oracle statistical convergence rate. The theoretical findings are verified through a variety of numerical experiments and the proposed method is compared with explicit  $ l\\_1 $ regularization. The advantages of employing implicit regularization via gradient descent subsequent to over-parameterization in sparse SVM are illustrated by the results.", "questions": "Question 1: Since the update of $\\mu$ in Algorithm 1 is due to Eq. (4) which introduces an extra smoothing term $d\\_\\gamma(\\mu)=\\gamma/2\\|\\mu\\|_2^2$ and this $\\mu$-update surely affects $w$ and $v$.  Is it possible that this additional smoothing term intruduces some explicit regularization effects?\n\nQuestion/Suggestion 2: As  Assumption 1 requires the design matrix to satisfy the $\\delta$-incoherence and the sub-Gaussianality, it is suggested to discuss whether this assumption holds on real data. \n\nQuestion 3: Is it possible to discuss the empirical effectiveness of the proposed algorithm?", "limitations": "It seems the authors did not sufficiently address the limitation due to the lack of explicit discussion in the main text.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strenth 1: This manuscript presents an interesting finding about the over-parameterized SVM by showing that if we re-parameterize the sparse unknown parameter $\\beta$ by $w\\odot w-v\\odot v$, then Nesterov's smoothing based alternative update of variables leads to the effect of implicit regularization. That is to say, even we did not explicitly impose $l\\_1$-norm onto the underlying parameter, the algorithm behaves as if the $l\\_1$-norm is implicitly added.\n\nStrength 2: The theoretical analysis is interesting and easy to follow. \n\nStrength 3: The theoretical findings are validated with numerical simulations.", "weaknesses": "Weakness 1: Although it is an interesting result for over-parameterized SVM, the proposed algorithm is not directly designed for the original model (2), but its modifed version in Sec. 2.3. It seems that the proposed Algorithm 1 might have some explicit regulrization term in its single iteration. Specifically, the update of $\\mu$ is due to Eq. (4) which introduces an extra smoothing term $d\\_\\gamma(\\mu)=\\gamma/2\\|\\mu\\|_2^2$ and this $\\mu$-update surely affects $w$ and $v$, which may result an regulurization effect like $l\\_1$.  \n\nWeakness 2: The Assumption 1 requires the design matrix to satisfy the $\\delta$-incoherence and the sub-Gaussianality. It seems this assumption is relatively strict for real datasets. \n\nWeakness 3: The empirical effectiveness of the proposed algorithm is insufficiently discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for providing valuable feedback on our paper. We will explain each point one by one. If you have new questions or ideas, please don't hesitate to let us know.\n\n1. Statement for the smoothing term $d(\\mu)=\\lambda/2||\\mu||^2$\n\nWe appreciate your inquiry regarding the smoothing term, as it's an excellent question that we'll delve into here in detail. Firstly, to address the computational challenges stemming from the non-differentiability of the hinge loss, we employ a smoothing approach by subtracting a prox function $d(\\mu)$. This smoothing technique not only simplifies computations but also introduces more convenient stopping criteria. From the viewpoint of the purpose, the incorporation of the smoothing term $d(\\mu) = \\lambda/2|||\\mu||^2$ is primarily for computational ease. \n\nSecondly, the prox parameter $\\gamma$ we've chosen for specific computations is extremely small ($\\gamma\\le1/n$), and the vast majority of $\\mu_i, i\\in[n]$, remain at $0$ during iterations. As a result, the smoothing term has minimal impact. \n\nLastly, even if we were to optimize the original hinge loss directly, the gradient descent algorithm would still instigate implicit regularization. This is because implicit regularization fundamentally arises from the algorithm itself, rather than from the process of smoothing. However, direct optimization of the original hinge loss poses considerable theoretical challenges (owing to non-differentiability). Therefore, the introduction of smoothness is a clever approach, significantly benefiting both computational and theoretical aspects.\n\n2. Assumption 1 holds on real data？\n\nAssumption 1, in reality, doesn't overly constrict the analysis of real-world data. As we stress in the paper, while our proof relies on Assumption 1, the experimental outcomes present compelling evidence that its strict adherence isn't crucial for the success of our approach. To exemplify, we generate data from the $t$-distribution, which clearly doesn't meet Assumption 1, yet the experimental results remain surprisingly strong. This showcases the potential for relaxing the constraints of Assumption 1 in practical scenarios. \n\nTo provide a more tangible illustration, we've incorporated a practical example. In this case, we applied our algorithm to the colon-cancer dataset sourced from the LIBSVM website (https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/). This dataset comprises 62 samples with 2000 features—a quintessential high-dimensional sparse classification challenge. With 42 samples as the training set, 10 as the testing set, and 10 for validation, our approach achieves impressive results. Specifically, the final prediction accuracy on the training set is 0.8, sensitivity reaches 0.75, and specificity stands at 0.833—an exceptional performance. Looking ahead, our plans encompass introducing new real data analysis results in the revised version.\n\n3. Discussion of the empirical effectiveness of the proposed algorithm\n\nSVM finds extensive use in classification tasks such as face detection, text categorization, image classification, bioinformatics, handwriting recognition, and medical data analysis. Yet, when confronted with high-dimensional data, SVM can encounter challenges, especially when the sample count is significantly smaller than the feature count. Take, for instance, the colon-cancer dataset we previously examined, where features reach 2000, while samples total only 62. Similar situations arise in text and image categorization, where image dimensions can be notably high. However, it's essential to acknowledge that high dimensionality often accompanies sparsity. Consider the news20 dataset from the libsvm website—featuring 19,996 samples and a staggering 1,355,191 features, yet maintaining a sparse 0.034% density. In such scenarios, conventional SVM algorithms can struggle to yield precise classifications. This is where our proposed algorithm, facilitated by implicit regularization, steps in.\n\n As demonstrated in our earlier analysis of the colon-cancer data, our algorithm thrives in the realm of high-dimensional and sparse data. It accomplishes effective classification outcomes while ensuring computational simplicity. In essence, our proposed algorithm holds immense promise in addressing classification challenges within today's high-dimensional, sparse data landscapes. Its potential impact spans across practical applications like face detection, text and image categorization, and medical data analysis. This algorithm has the potential to tackle intricate classification tasks encountered in real-world settings, providing viable solutions. \n\nFurthermore, our algorithm excels in terms of algorithmic effectiveness. In the default experimental setup ($m=10$), the average runtime for executing the gradient descent algorithm is 2.75 seconds. This represents an 18% improvement in speed compared to the Lasso algorithm."}]

Author rebuttal:
We highly appreciate the invaluable feedback we received from reviewers for our work. Your comments aid us in identifying areas where we can enhance our research and make our findings clearer and more accessible to our readers. We have considered all the comments and summarized the responses below. We have selected five key issues to provide a global explanation here.

1. **Discussion of Sparse SVM.**

Several reviewers have highlighted the significance of investigating sparse SVM, prompting us to delve deeper into this topic. In modern applications, the challenge of classification arises when dealing with an abundance of redundant features. such as in the fields of face detection, text classification, image classification, bioinformatics, handwriting recognition, and medical data analysis. To illustrate, in medical imaging, our aim is to construct a classifier using specific pixels from high-dimensional data, while in text analytics, we seek to develop an accurate classifier using a modest subset of words from a vast dictionary (for instance, the libsvm website's news20 dataset comprises 19,996 samples and a feature count as high as 1,355,191, with a sparsity of just 0.034%). Acknowledging sparsity within SVMs adds an intriguing dimension to the study of practical applications.

Conversely, although sparsity in regression has garnered extensive attention in recent years, the corresponding theoretical exploration in classification problems remains relatively limited. The focus generally gravitates towards analyzing aspects like generalization error rate and empirical risk, with less emphasis on error bound. Thus, there exists substantial room for theoretical advancement in the realm of sparse SVM.

In summary, our study of implicit regularization in classification problems in this paper is a very meaningful topic, both as a complement to the theoretical work on sparse SVM and as a new algorithm for the real-world problem of large-scale data classification.

2. **Novelty of our work.**

Our work is the first to design unregularized gradient-based algorithm for SVM by leveraging over-parameterization and provides relevant theoretical guarantees for implicit regularization.

The reparameterization technique has not been applied to classification problems, although it has been widely used in the study of regression. Reparametrization is not computationally burdensome, and although it creates a snag in the theoretical derivation, with reparametrization, we can theoretically analyse how strong signals, weak signals, and error terms change during the iteration process, and we can clearly study the dynamics of gradient descent to get a clearer picture of the algorithmic iteration process, which has never been done in previous papers. With the help of reparameterization, we introduce an error bound for the iterative solution that is independent of the number of iterations $t$.

In addition, we add Nesterov's smoothing, which is a very clever step that computationally overcomes the non-differentiability of the hinge loss and facilitates our theoretical proofs.

3. **Further discussion of assumptions**.

Several reviewers have asked about assumptions, and it is a good opportunity for us to make more explanations of assumptions. Firstly, the assumptions we made in the theory section were mainly motivated by theoretical proofs, such as that the initial size $\alpha$ controls the size of the error term, and that we need to make assumptions about it. However, our assumptions are not strict, for example, ours for $\alpha$ is $\alpha\lesssim 1/p$.

In our experiments, we have found that the theoretical constraints can be relaxed, for example, we can still get good estimation results with heavy-tailed distributions, which means that our method will not be constrained by the assumptions in practical applications.

4. **Addressing unclear and inappropriate expressions in the text.**

We acknowledge the presence of unclear and inappropriate expressions, as well as writing errors in the text. We are committed to rectifying each of these issues in the revised version to enhance the overall quality of the article. We extend our gratitude to the reviewers for their diligent review, as their feedback will undoubtedly contribute to the article's improvement.

5. **Future directions.**

Firstly, as we mentioned above, the assumptions are mainly derived for theoretical considerations and can be relaxed in practical applications, and we would like to explore to what extent these assumptions can be relaxed, which is one of the future work mentioned in other studies on implicit regularization;

Secondly, as suggested by the reviewers, we can consider extending the current study to nonlinear SVM. This could involve incorporating kernel technique to delve into the realm of implicit regularization in nonlinear classification.

(A response to Reviewer 6PiA is included in the pdf file we have provided.)

Meta-review: The proposal is a novel regularization-free algorithm for sparse SVM. Although there were concerns about the explicit regularization and applications of sparse SVM,  the rebuttal has convinced reviewers that contributions are sufficient in the line of implicit regularized learning. The paper may benefit from (i) more motivation on regularization free algorithm design (ii) discussions on the Frank-Wolfe method which also has a bias to sparse solutions.
Decision: Accept (poster)