The Reliability of OKRidge Method in Solving Sparse Ridge Regression Problems
Authors: Xiyuan Li
Youjun Wang
Weiwei Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: regression
Primary area: learning_theory

Abstract: Sparse ridge regression problems play a significant role across various domains. To solve sparse ridge regression, Liu et al. (2023) recently propose an advanced algorithm, Scalable Optimal $K$-Sparse Ridge Regression (OKRidge), which is both faster and more accurate than existing approaches. However, the absence of theoretical analysis on the error of OKRidge impedes its large-scale applications. In this paper, we reframe the estimation error of OKRidge as a Primary Optimization ($\textbf{PO}$) problem and employ the Convex Gaussian min-max theorem (CGMT) to simplify the $\textbf{PO}$ problem into an Auxiliary Optimization ($\textbf{AO}$) problem. Subsequently, we provide a theoretical error analysis for OKRidge based on the $\textbf{AO}$ problem. This error analysis improves the theoretical reliability of OKRidge. We also conduct experiments to verify our theorems and the results are in excellent agreement with our theoretical findings.

The Reliability of OKRidge Method in Solving Sparse Ridge Regression Problems
Xiyuan Li Youjun Wang Weiwei Liu"
School of Computer Science, Wuhan University
National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University
Hubei Key Laboratory Multimedia and Network Communication Engineering. Wuhan University Lee_xiyuan womm com, youjunw 1 1008 @ gmail.com, liuweivei863 @gmiil.comm
Abstract
Sparse ridge regression problems play a significant role across various domains. To solve sparse ridge regression, [ recently proposes advanced algorithm, Scalable Optimal K -Sparse Ridge Regression (OKRidge), which is both faster and more accurate than existing approaches. However, the absence of theoretical analysis on the error of OKRidge impedes its large-scale applications. In this paper, reframe the estimation error of OKRidge as Primary Optimization (PO) problem and employ the Convex Gaussian min-max theorem (CGMT) to simplify the PO problem into an Auxiliary Optimization (AO) problem. Subsequently, we provide theoretical eтror analysis for OKRidge based on the AO problem. This error analysis improves the theoretical reliability of OKRidge. We also conduct experiments to verify our theorems and the results are in excellent agreement with our theoretical findings.
Introduction
Sparse Ridge Regression (SRR) has achieved notable success across various machine learning applications, including statistics (2, signal processing [3], dynamical systems 4 [], and others. In this paper, interested in addressing the following k-sparse linear regression problem with additive noise:
y XB" +e with ||8" llo S k;
(I) gaxd
where 8 Rdd represents the "true" weight parameter, X (2.. the input measurement matrix, y (y1, U2. "Bn) R is the real output responses, R is the noise vector, is E -- specifies the maximum number of nonzero elements for the model, || llo denotes the number of nonzero elements of the given vector. Moreover, the entries of X are drawn i.i.d. from (0, 1): the entries of are drawn i.i.d. from (O, o²); and m(d)
= 62, ..)
we assume is a constant and limg- d = E (0,
The formulation ( represents a black box model where 8 is fixed. Given X and y, to determine the target vector 3 most basic method is solving the following k-Sparse Ridge Regression Optimization (k-SRO), as outlined by 71:
min y B
XB 1
s.t.
|B811 < k.
where À > is regularizer parameter, and ll2 denotes the Fuclidean norm. Our paper focuses on the worst-case scenario 1|8" = k. This SRO is different from the traditional ridge regression
CCoresponding author: Weiwei Liu (liuweiwei8633 @gmail.com)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

due to the constraint of k-sparse structure for B. The k-SRO problem is NP-hard, and is more challenging the presence of highly correlated features
Two main types of algorithms are commonly employed for solving k-SRO problem (2) heuristic algorithms [9] [0] and optimal algorithms [TT]. However, heuristic algorithms lack the ability to
assess the solution quality, while the optimal algorithms are slow. In order to rapidly solve k-SRO problem (2) while ensuring solution optimality,
I introduces highly efficient method called OKRidge. Therefore, complete algorithm of OKRidge, including how to choose hyper-parameters can be seen in the original paper [T. OKRidge substitutes k-SRO problem 2 with an unconstrained optimization on a novel tight lower bound. The experiment results in [I show that OKRidge is superior to heuristic algorithms, optimal algorithms. and existing mixed-ine -iieeer programming (MIP) formulations solved by the commercial solver Gurobi. Nevertheless, the absence of theoretical error analysis for OKRidge impedes scalability in practical applications.
In this paper, we provide theoretical error analysis for OKRidge utilizing the framework of the CGMT [1]. Specifically, we propose another novel tight lower bound COKRidge (B) replace k-SRO problem
CokRidge (B) := lly XB1 + ASumTopp (B @ B),
where @ denotes Hadamard product, and SumTop (.) represents the summation of the largest k elements of given vector. The tight lower bound is equivalent that proposed by M. Thus. LokRidge can replace the objective function of OKRidge. It is noteworthy that our proposed regularizer, defined as (B) = SumTop,, (B @ B), differs from any previously proposed instances by 112. Then, the optimal solution obtained by OKRidge is
B arg min LoKRidge (B)
(4)
B
By combining formulations I and (3. the estimation error of OKRidge can be obtained through the following normalized optimization problem:
utilizes 3 as the estimate of 8 in problem ().
min
X el12 + ASumTop; ((w + 83*) @ (w + ++))
(5)
where w : B 8 is random variable with randomness from the random variables X and e, and the estimation error can be measured by |//||2 Subsequently, we transform the optimization (5) into PO problem about the eгror of OKRidge, using the Fenchel-Moreau theorem [13]. Then, we employ the CGMT framework to substitute the complex PO problem with simplified AO problem. Finally, we present the theoretical error analysis of OKRidge based on the AO problem. Our theoretical results focus on the Normalized Squared Error (NSE) of OKRidge and can be summarized as:
lim lim NSE _ A()),
(6)
where NSE ||B B 12//2, and (A) is a function of A. These theoretical results indicate that if the regularizer parameter À used in OKRidge is constant, the NSE limit of OKRidge also fixed.
Moreover, 3 learned by OKRidge reliable estimate 8*, due to lim lim - _ 0. The comprehensive experiments of OKRidge on real-world examples were conducted by the NeurIPS 2023 paper IT (see Figure 3 and Appendix in M]) which demonstrates that the error of OKRidge tends to zero. Our analysis explains the experimental phenomenon observed in []]. strengthens the theoretical underpinnings OKRidge, and provides theoretical reliability for its broad application.
We also conduct numerical experiments to validate our theorems. The findings demonstrate that the NSE converges to fixed constant determined by X, aligning excellently with our theoretical predictions.
1.1 Outline
The structure of the remaining sections in this paper is as follows. Section 2 provides review of related work. Section[Jooferrs background information on OKRidge, CGMT, and basic concepts. Section 4 introduces an alternative tight lower bound for the objective function of OKRidge. In Section S we convert the estimation error of OKRidge into a PO problem and simplify into an AO problem using CGMT. Subsequently, an estimation error analysis of OKRidge based on the 6 presents the experimental results. Finally, we conclude with a summary in Section 7 Additionally, the limitaion and impact of our work are detailed in Appendix A
AO problem conducted. Section

---

2 Related work
2.1 Heuristic and Optimal Methods
Heuristic methods approximate solutions to optimization problems based practical experience [4]. including ensemble methods [[5), swapping features [[6], greedy methods [17], etc. While heuristic methods are fast, they often become trapped in local minima, and their solution quality cannot be assessed due to the absence of a lower bound on performance. Optimal methods aim to precisely solve sparse regression problems, such as the big-M method [8], the conditional-value- at-risk (CVaR) approach [19], big-M free mixed integer second order conic (MISOC) method [T9], and However, exact optimal methods are slow, particularly for large instances, to achieve near-optimality [20) (1]. To address the limitations of heuristic and optimal methods, [1] proposes an efficient approximation algorithm, OKRidge. Experimental results in [ demonstrate that OKRidge outperforms heuristic algorithms, optimal algorithms, and existing MIP formulations solved by the commercial solver Gurobi.
2.2 Lower Bound Methods
Lower bound methods are capable of solving the NP-hard k-SRO problems. Several algorithms utilize the lower bound method, such as SOS1 formulation [8). big-M formulation [1]] Subset Selection CIO method [22). and others. However, the SOS1 formulation lacks scalability in high dimensions, the big-M formulation sensitive to hyperparameters. and the Subset Selection CIO method runs slowly. Recently, the perspective formulation [6] 23 24 has been employed to induce convex relaxed lower bound that is easier solve. Building upon the perspective formulation, proposes novel lower bound used as the objective function for the OKRidge method.
2.3 Normalized Squared Error
NSE, defined as ||B 8 1/1//02 serves as natural measure of the estimation error. NSE is an important indicator in signal-to-noiss ratio scenes 225] [66]. Bounds on NSE have been derived by 27 (28). Additionally, [29] is the first to precisely formulate the limiting behavior of NSE. These studies primarily consider a Gaussian sensing matrix X and utilize the Approximate Message Passing (AMP) framework for analysis [30 31,. These achievements motivate to utilize NSE for evaluating the estimation error of the OKRidge method.
3 Preliminary
3.1 Relaxed Transformation of k-SRO
According to 11. the k-SRO problem
can be reformulated as the following optimization problem:
1 < k. 23 {0, 1}. min Cridge (B), {
(1- 1)), = 0, j = 1,2.......
B
where z (21, ..,
Rd, and Ladge (B) by X + B4. This problem 7 remains NP-hard under the sparsity constraint 32 Existing methods such SOS1, big-M, the perspective formulation do not leverage the k-sparse structure of the problem. 1 develops a novel method, OKRidge, to preserve the special structure through the following relaxed transformation.
By employing the perspective formulation 33 34 and the Fenchel conjugate [35]. transforms
the problem new perspective optimization problem:
d
min max ridge 8.
Fenchell (,,,c), s.t. 2j S 2j E {0. 1}.
(8)
where c = (c1, C22 ... Cx) E Rd, and Fennhell
(B,z.c) := ly X313
+ x (B,c - 2))
rige
This transformation does not change the optimal solution the problem problem (7) can be replaced by problem (8). To efficiently solve problem 8 further relaxs
3135 indicating that

---

the binary constraint {0, 1} to the interval [0, 1], ultimately yielding the following relaxed convex optimization problem:
min max Fenchel (B,2,c), (B B
2j S s.t. Σ
k, 2j [0, 1].
(9)
ridge
==1
preserve the special sparse structure of B, we always have 3, 0 2, 0. Directly solving the min-max problem (9) is computationally challenging. [ utilizes the relaxed problem (9) obtain tight lower bound for the problem (8), where the lower bound corresponds to the objective function of OKRidge.
According to problem
3.2 The Convex Gaussian Min-max Theorem
The CGMT framework, introduced by 28 has been utilized to analyze the performance of solutions to non-smooth regularized convex optimization problems. has achieved significant success in various practical applications. including regularized logistic regression [36), max-margin classifiers
[37, adversarial training [38] 39] and others. These achievements inspire us to apply the CGMT framework analyze the NSE of the OKRidge method.
CGMT originates from Gordon's Gaussian Min-max Theorem (GMT) [4], which provides prob- abilistic bounds on the optimal cost of PO problem via simpler AO problem. CGMT further tightens the bounds under convexity assumptions. According GMT, 41] introduces the following asymptotic sequence and notation.
Definition 3.1 (GMT admissible sequence). The sequence {G(d) g (d), A,(4), Ste S(i)) 2l(d))
deN
indexed by d, with ()()) E R (())) E RR,, h(d) E &Rd, s(d) C Rdd, S(a) C R", sold) S x s(d) R and n ndd), is said to be admissible if, for each d N,
((d) and (d) are compact sets and wi(d) is continuous on its domain. Onwards, we will drop the superscript (d) from G(d), g g(d), h (d))
sequence (G(d), g(d) h s s(d) ( JaEN defines a sequence min-max problems
(1d) (G) = min max u Gw + 4b(()) (w, u),
(10)
w west wes!
df (ghh) = min
| u |lul|2h w (i (w, u).
(11)
wES
wes(
Importantly, the formulation is called Auxiliary Optimization (AO). Additionally, let w. (G) denote the optimal minimizer
10 is called Primary Optimization (PO) and the formulation
of PO problem (10 and w (g. h) denote the optimal minimizer of AO problem (11) Define
(dd) s(d) + as follows,
(/(0) (w: g) max (()
|w|l2g ||u||2h w + ()(() u).
(12)
Clearly, (())) hg min west
(d) (w: g. h). For sequence of random variables (x) JEN and
constant E R, (d) P. denotes convergence in probability, i.e. Ve 0, lima-ro ((
e) 0. Based the GMT admissible sequence and the notation introduced above, present
the CGMT below.
Theorem 3.2 (CGMT 12
Let (G( (())),(()))))) ( s(())) ( (b)(0) ]aeN be a GMT admissible se- quence as in Definition 3.1 for which additionally the entries GG h are drawn i.i.d. from ( 1).
Let a (G), (( (g.h) h) be the optimal costs, and, w bb (G), w()) (g.h) the corresponding optimal minimizers of the PO and AO problems in (TO) and [T7. The following three statements hold
(i) For any d E N and c E IR,
P( (G) <P (2) hg s)

---

be replaced with (i) For any d N. If SS s(d) are convex, and, (.,)) is conver-concave on Si S. then, for any μ E R and t > 0,
P([ (G) - 14) > 1) (P((((())gg)) - pl) > t).
(iii) Assume the conditions of (i) hold for all E Let [I denote some norm in R and recall [2]. If. there exist constants (independent of d) k", O and O such that
(a) (id)) h)) P K*.
(b) 1w (d) g. h1ll
a², a",
(c) with probability one in the limit d +
{vl (w:g.h) g. h) 2 ol (g,h) + +
ve E s(d) } w (g,h))
then,
P a² (d) (G)ll |/
a"
(13)
indicates that, the optimal cost o(g. h) of I1 concentrates to some value μt, the same holds true for (G)) of (10). Furthermore, under appropriate additional assumptions, the optimal solutions of the AO and PO problems are also closely related by | (G)]] = (g. |l. as n + co. This suggests that, within the CGMT framework, challenging PO problem
Theorem 3.2
a simplified AO problem, from which the optimal solution of the PO problem can be accurately inferred [12]. Subsequently, rewrite the lower bound of problem (9) in the form of PO problem (10) and analyze the minimizer of the simplified AO problem instead.
3.3 Basic Concept
Suppose f: _2 IR and u, Rd, the Fenchel conjugate of f is defined as f*)) sup, u f(v). Additionally, f is always convex and lower semi-continuous. According to the Fenchel- Moreau theorem [13], f convex and continuous, we have f(v) sup, u v fu). In this paper, we utilize the following conjugate pairs
f(v) = |1a|2 + (u)
(14)
4
If 7(-) Rd IR is convex function of B, the subdifferential of x-)) 8 is the set of vectors: 0y(8*) (s Rd (B + +u)= 2 >(8)) + u). According to [13, (x())) is nonempty, convex and compact. Given h E Rd, define dist(h, (B"))) min *B
s||2. Then, the Gaussian
squared distance corresponding to the scaled subdifferential is defined (T)) Da-(B-) (T) Es dist (h, ()] where > O. Suppose C(r) = 2 d+ lim y/2 + E (0,
a)(r)
lim D(7) + D(7) E (0, 1), lim C(r) + C(r). Based on the Gaussian squared distance, we define map function:
1 1 (-(( - -D(T)
map(r) =
V1 - D(T) ,T . O.
(15)
We denote Xmap the solution of map(7) X/2 O. Since map(T) depends on 7(-) and B*, when the form of 7-) and the value of 3 are determined, the Xmap is fixed.
4 Tight Lower Bound in OKRidge
In this section, we utilize problem 9 to derive another novel lower bound for problem R serving as used as the objective function of OKRidge. Our lower bound is equivalent to the tight lower bound provided by [T. Specifically, ( eliminates the parameter e problem (9) by setting the gradient of B to O. while climinate the parameter e by setting the gradient of to 0. These two methods
5

---

are equivalent due to the independence and convexity of c and B. Given any & and the optimality condition for in problem taking Ō ridgo
ridge (B, 2, c),c = 0. Therefore, we have
i DL Fonchel ridge
(8.2.c)
diag(z)c O, 2
=
(16)
de
p IR
if 2j = 0, if 2j # 0,
Cj
28
(17)
where diag(z) a diagonal matrix with z on the diagonal. Inspired by this optimality condition, we present the following theorem.
Theorem 4.1. we define the parameter 16 optimization problem:
the problem
is equivalent to the following
min
Lsaddlle ridge 8,
(B,z), 8.1.
Σ
S k,
E (0,
(18)
j=1
where
B j=1,zyæ00 Zj
Canddle (B,z) := 11
XB +
(19)
The proof of Theoremr 4.1 f. follows Theorem 3.1 of [1] and included in Appendix B for completeness.
Following the approach by M1 we can approximately solve the problem 18 while still obtaining function L(B) as:
feasible lower bound. We define
L(B) min Gaaddle (B,z), s.t.
Σ
23 k3 (0.1].
(20)
For any B. C(B) serves as valid lower bound for problem lower bound LB) is tight.
7
We should choose such that this
Theorem 4.2. The function L(3) defined in Equation 20 is lower bounded by
((B) 2 ll x,812 + XSumTop, B).
(21)
where @ is Hadamard product, and SumTop (-) denotes the summation of the largest l elements of given vector.
The proof of Theorem can be seen in Appendix C Based on 18 and (20), the tight lower
bound (2T) equivalent to the one provided by [1, as both are derived through equivalent processes.
OKRidge solves the original k-sparse problem using this tight lower bound (21) as its objective
function. If we define
CoKRidge (B)
|1
xB11 ASumTop, (B B),
OKRidge solves k-SRO problem 2 with
min LokRidge B
(22)
where we obtain LOKRidge of formulation 3). So far. we transform the constrained k-SRO problem
into the unconstrained optimization problem Let
β argming LokRidgo (B).
OKRidge regards B as the estimation of 8* in problem Next, we apply CGMT to analyze the error | 88 for OKRidge.

---

The Error Analysis for OKRidge
5.1 From PO AO
As discussed in Section 4 the estimation error of OKRidge is characterized by | - Taking
formulation ( into the properly normalized objective (2). OKRidge 22) can be equivalently
transformed to the following optimization:
min B
( 8*) + ASumTop, (B o B)].
(23)
The crucial step is to convert
23 into PO problem within the framework of CGMT. We introduce the new variable w := B B and apply the Fenchel-Moreau theorem (4) to formulation 23)
Xw cl1 ASumTopy ((w + 8*) (w B*))
|ul2 max 1 Xw u
ASumTop, ((w (ww + (w + B*))
(24)
4
the PO problem corresponding to the estimation where Rd RR. Based 10 and 24 error of OKRidge is
PoKRidge (X) min max
(u Xw + vww,u))
(25)
vn
where
(ww u)
ASumTop; ((w B8) ② (w + B*).
(26)
Since the entries of X drawn i.i.d. from (00, 1), replace the challenging PO problem 25 with a simplified AO problem through CGMT, (ww u) should be a convex-concave function. The following Lemma illustrates that the (ww, u) satisfies the conditions of Theorem 3.2
Lemma 5.1. Suppose (ww, u) is defined as in formulation 26 function.
Then, (w u) is convex-concave
The proof of Lemma 5.1 can be seen in Appendix D Define
( = SumTop, (B @ B).
Because the PO problem 225 satisfies the assumptions of CGMT, we transform it to the following AO problem:
|ull + AT + tw)]
ΦOKRitge hg = min max
Vū
||/||| u |2ul22h e
|2111 + Ar + =w)
min max
(1|w||2g e) + ||ul|sh w
(27)
Vn
where the entries g. h are drawn i.i.d. from (o. 1). due to the property of X. Suppose Woomste
the of optimal solutions of the PO problem 25 and w Wooksagee the optimal solutions of the AO
problem (7p. According to Theorem 3.2 if W Corgare ||2 P.
a², we have | ll2 P, a
Thus, can analyze the minimizer of AO problem instead of PO problem (25
5.2 Simplification for AO
In this chapter, we simplify the AO problem (27 into ones involving only scalar quantities. Since 7()) is convex (see Lemma 5.1). (B*)) is nonempty, convex and compact. According to [3 Theorem 23.4], we have 7(B + w) = 7(*)) + max
+ [[] The first-order
approximation of (B) around the vector of interest 8 is
6(8" + w) (B8)) + max 8 W.
(28)
$EOr(

---

where B = B + w. Then, following the approach from [12 the AO problem 27 can be simplified
by the first-order approximation 28
2 2
ØOKRidge g. h) min max
(1lea l2g
E) uu | w + (x)
max 8 w) =EOr(B))
Vn
min
max 10/220 #COT((")
(1w]||g-<d 1 -e)
T u (1+ll/u//2ht
(29)
Vn
Suppose f(B) and f(8) denote the objective functions of the original and the approximated AO
problems 27 and 29 respectively,
2l c) u |uul2h T w ((8)
+ A (r((++w)) +w).
f(8) - [1| T)Tu + |ulllh Tww |u112
*(7(8*)+ + max s'w). *EAy((-)
Then, based on
28 we have
lim
f(B) - f(B).
(30)
Compared with AO problem (27). the approximated AO problem (2) is tight when || - 11 0. and we later demonstrate that this condition is satisfied as の² - 6, independent of the original AO problem (27) This fact allows to translate the analysis the optimal solution coxciig of the
approximated AO problem (29) to the analysis on the optimal solution w Wossiigg of the corresponding original AO problem (27). Because 7(8) is constant, the approximated AO problem 29 is
equivalent to the following optimization problem:
|u/1 4
min W
max Iu 1220 KEPY(R
Vn [1|w]) - -e) - + (1|ua12h + As) w
(31)
where have approximated ry in the first order. Since o( I), the term | statistically identical to random vector with entries drawn i..dd from N(0,, [//l| + o ). where is
above is
the unit matrix. Following the method used by [42], we substitute the first term in the objective (31 with
w
2 + o²g Then, we obtain:
|
min W
max 2lll xE0r(8*)
Vn
w
02
g u + (llullah As) To
(32)
Let 17 |/u||2. Since max/uu expectation, the optimization 32
Tu= 1 //2|122 and h ~ N(O,I), in term of mathematical can be cquivalently expressed as:
min W
max 928
| 1| + o² 02]1g|127 ( 8)
w
(33)
The objective 33 strongly convex in w and (jointly) concave in 7), 8, and the constraint sets are bounded. Therefore, we can reverse the order of min-max in problem (33) based on 13 Corollary
37.3.2]. Let a = |w|]2- Since min [|w]]= (-h + 43) aall s12,, the optimization 33 can be equivalently reformulated as:
max min (Va² + 02. ||l||27 - anli 920 xE
-
s|12
(34)
az0 Vn
Next, we further reverse the order of min-max, as the objective 34 exhibits the desired concave-
convex structure. Then, we proceed maximize over s @B*))) Since min || dist(h, (B*)) the optimization problem (34) can alternatively be formulated as:
A =
1 (Va² + 02. ||gl|21 an dist(h, -3) n1
min max
(35)
a20 720 Vn
71

---

Because both the random components gg and dist(h, () are Lipschitz, lll|2 concentrates around
vn and dist(h, () around D
43 Lemma B.2]. Suppose, as d - oo, D(r)
D(T) E (0, 1),
C(r) C(r), and (1)) := lim 4y"
Then, the optimal minimizer of (35 converges to the
optimal minimizer the following deterministic optimization in probability
max min min a² + 0² V D I(m). 220
(36)
Here, we complete the simplifications by reducing the AO problem (27 to an equivalent optimization (36 that now only involves two scalar variables: and 17.
5.3
Error Analysis
Based on the analysis above, if the optimal solution of optimization (36 is a", we have If ax further tends to 0, according to
|
bonnies 1l2
P a² for approximated AO problem 29 holds for PO problem (55 Then, for the
formulation
30 and CGMT, || | 1/2
estimation error of OKRidge produced by 222.. we have - 1 - a". Therefore, it only
remains obtain the optimal value of a in optimization (36) that plays the role of ||w||2 Following
45]. we conclude the estimation error of OKRidge with Theorem [.22 below.
Theorem 5.2. Suppose B is the true weight parameter of the problem D. B is the optimal solution
to the objective function (22) of OKRidge, D(r) + D(T) E (0,1), aNSE == lim NSE 10 ||3 - 8 12/022 Define Amap the solution of map(r) = 0 for 0, then, the estimation error of OKRidge is given by the following probability limit:
lim aNSE P, A(3), d=0
(37)
((A) where A(Å) = D-D(A)'
and Amap.
The proof of Theorem 5.2 can be seen in Appendix
Remark 5.3. In the objective (2 concerning estimation error of OKRidge, >(8) Sum @ o B) and the value of 3* is assumed to be known. Then, the analysis on map(-) in Section 3.3 reveals that the form of map(-) and the value of Xmap are fixed. Thus, ((Å) is function of X. In other words, if the regularizer parameter À of OKRidge is fixed, the NSE limit of OKRidge A(Å) is also fixed. Additionally, Theorem 5.2 also indicates that limg-+oo lim | 8 _ 0, which guarantees the effectiveness of learned by OKRidge accurately estimating 8 These results substantiate the theoretical reliability of OKRidge and promote its broad application in the real world.
6 Numerical Experiments
In this section, we conduct experiments verify Theorem 5.2 The experiments contain aspects: (i) When À is fixed, NSE tends to a fixed constant as o + O. (ii When o + 0, NSE is determined by the weight À of the regularizer. other words, NSE a function of A.
In our experiments, 8 is randomly generated with || < k. For i E (1.2.....n)) I; is drawn L..dd from (0, I), and is drawn i.i.d. from (0, o ²) According to the k-sparse linear regression 11 y: _ 8 + E;, get dataset (æ;, 3/ with 1, 2, ... ,n. Then, we appy OKRidge to get the estimator 8 and calculate the NSE by || | 02 The NSE averaged over 10 trials to evaluate the effectiveness of the OKRidge algorithm. the main paper, we set à
.n).
" = 0.5, d 0.1, d = 100.
The computer resources are detailed in Appendix F.T More experiments with various settings about and & can be seen in Appendix F22

---

003
25
2.3
NISE
Payr 20
60 200
1/o
Figure 1:
The change of NSE with 1/0 for OKRidge under different A. The red curve at the bottom corresponds to the case X Abest-
Figure 2: The change of NSE with À for OKRidge under different σ. The blue curve corresponds to the real change A(²). Here, Abeat is the optimal weight of the regularizer.
6.1 The Change of NSE with
We investigate the change of NSE with 1/0 under À = 1, 5. 10, Abest, ... The results are illustrated in Figure As depicted in Figure [ when is constant, NSE converges fixed value as -> This observation validates aspect (i) of Theorem 5.2
6.2 The Change of NSE with À
We analyze the change of NSE with under σ² 0.1, 0.01, 0.001. The outcomes depicted in Figure 2
As shown in Figure 2 the curves converge towards the real blue curve as - 0, where the blue curve relies on A. This observation confirms aspect (ii) Theorem 5.2
7 Conclusion
In this paper, we present theoretical high-dimensional error analysis of the OKRidge algorithm in idealized settings using the CGMT framework. Specifically, when OKRidge tackles a k-sparse linear model with æ ~ (O, I), (10, and limo 8 (0, 1), we have
| 8- P A()) and lim lim | B 0.
lim lim
where A(Å) depends A. This indicates that (i) the NSE limit of OKRidge remains constant when is fixed; (ii) B learned by OKRidge effective in estimating 3 Our experimental findings support these theoretical assertions. This theoretical error analysis substantiates the reliability of OKRidge and provides guidelines on the error analysis of other algorithms.
Acknowledgments and Disclosure of Funding
This work is supported by the Key R&D Program of Hubei Province under Grant 2024BAB038, National Key R&D Program of China under Grant 2033YFC36 and the Fundamental Research Fund Program of LIESMARS.
10

---

References
[1] Jiachang Liu, Sam Rosen, Chudi Zhong, and Cynthia Rudin. Okridge: Scalable optimal k-sparse ridge regression for learning dynamical systems. In NeurlPS, 2023.
[2] Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than n. The Annals of Statistics, page 1-13311,1,222 2007.
[3] Alexandre Belloni, Victor Chernozhukov, and Lie Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):991-806 2011.
[4] Xiyuan Li, Xin Zou, and Weiwei Liu. Residual network with self-adaptive time step size. Puttern Recognition, 158: 1008, 2025.
[5] Xiyuan Li, Zou Xin, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[6] Weijun Xie and Xinwei Deng. Scalable algorithms for the sparse ridge regression. SIAM Journal on Optimization, 30(4):3359-3386 2020.
[7] Mert Pilanci, Martin J. Wainwright, and Laurent El Ghaoui. Sparse learning via boolean relaxations. Mathematical Programming, 151(1):63-87, 2015.
[8] B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM Journal on Scientific Computing, 24(2):227-234, 1995.
[9] Kathleen P. Champion, Peng Zheng, Aleksandr Y. Aravkin, Steven L. Brunton, and J. Nathan Kutz. A unified sparse optimization framework to learn parsimonious physics-informed models from data. IEEE Access, 8: 169299-169277,, 2020.
[10] Samuel H Rudy, Steven L Brunton, Joshua L Proctor, and Nathan Kutz. Data-driven discovery of partial differential equations. Science advances, ((4))e1602611) 2017.
[11] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2009.
[12] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-500 56228, 2018.
[13] R. Tyrrell Rockafellar. Convex Analysis, volume 28. Princeton University Press, 1997.
[14] Joel A. Tropp. Greed is good: algorithmic results for sparse approximation. IEFE Transactions on Information Theory, (0(10):2231-2244 2004.
[15) Urban Fasel, J Nathan Kutz, Bingni W Brunton, and Steven L Brunton. Ensemble-sindy: Robust sparse model discovery the low-data, high-noise limit, with active learning and control. Proceedings of the Royal Society A, 478(2260): 2022.
[16] Amir Beck and Yonina C. Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on Optimization, 23(3): 1880-119,, 2013.
[17] T. Tony Cai and Lie Wang. Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Transactions on Information Theory, 57(7):468044688 2011.
[18] Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern optimization lens. The Annals of Statistics, 44(2):813-852, 2016.
[19] Arkadi Nemirovski and Alexander Shapiro. Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17(4):999-996, 2006.
[20] Dimitris Bertsimas and Wes Gurnee. Learning sparse nonlinear dynamics via mixed-integer optimization. Nonlinear Dynamics, 111(7):6585-660) 2023.
[21] Weiwei Liu and Ivor W. Tsang. Making decision trees feasible in ultrahigh feature and label dimensions. Journal Of Machine Learning Research, 18:81:1-81:36 2017.
11

---

[22] Dimitris Bertsimas, Jean Pauphilet, and Bart Van Parys. Sparse regression: Scalable algorithms and empirical performance. Statistical Science, 35(4):555- 5788 2020.
[23] Alper Atamtürk, Andrés Gómez, and Shaoning Han. Sparse and smooth signal estimation: Convexification of 10-formulations. Journal of Machine Learning Research, 22:52:1-52:43
2021.
[24] Oktay Günlük and Jeff Linderoth. Perspective reformulations of mixed integer nonlinear programs with indicator variables. Mathematical programmingg 124(1):183-205, 2010.
[25] Chenglin Yu, Xinsong Ma, and Weiwei Liu. Delving into noisy label detection with clean data. In ICML, volume 202, pages 40290-40305.
[26] Lianghe Shi and Weiwei Liu. Adversarial self-training improves robustness and generalization for gradual domain adaptation. In NeurIPS, 2023.
[27] Peter Bickel, Ya'acov Ritov, and Alexandre Tsybakov. Simultancous analysis of lasso and dantzig selector. The Annals of Statistics, 37(p))pp. 1705-1732, 2009.
[28] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized lincar regression: A precise analysis of the estimation error. In COLT, pages 1683-1709, 2015.
[29] David L. Donoho, Arian Maleki, and Andrea Montanari. The noise-sensitivity phase transition in compressed sensing. IEEE Transactions on Information Theory, 57(10):920-6941 2011.
[30] Arian Maleki, Laura Anitori, Zai Yang, and Richard G. Baraniuk. Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP). IEEE Transactions Information Theory, 59()):4990-3308, 2013.
[31] Christopher A. Metzler, Arian Maleki, and Richard G. Baraniuk. From denoising to compressed sensing. IEEE Transactions on Information Theory, 17-55451 2016.
[32] Ryuhei Miyashiro and Yuichi Takano. Subset selection by mallows' cp: A mixed integer programming approach. Expert Systems with Applications, 42(1):325-331, 2015.
[33] Antonio Frangioni and Claudio Gentile. Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming, 106(2):225-236, 2006.
[34] Patrick L Combettes. Perspective functions: Properties, constructions, and examples. Set-Valued and Variational Analysis, 26(2):247-264, 2018.
[35] Alper Atamturk and Andrés Gómez. Safe screening rules for 10-regression from perspective relaxations. In ICML, pages 421-430, 2020.
[36] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. In NeurIPS, volume 32, 2019.
[37] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers separable data. In ICML, pages 8417-8426, 2020.
[38] Yanbo Chen and Weiwei Liu. A theory of transfer-based black- attacks: Explanation and implications. In NeurlPS, 2023.
[39] Jingyuan Xu and Weiwei Liu. Characterization of overfitting in robust multiclass classification. In NeurlPS, 2023.
[40] Yehoram Gordon. On milman's inequality and random subspaces which escape through mesh in R". In Geometric Aspects of Functional Analysis, 1988.
[41] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The gaussian min-max theorem in the presence of convexity. arXiv preprint arXiv: 440.448778887 2014.
[42] Christos Thrampoulidis, Ashkan Panahi, and Babak Hassibi. Asymptotically exact error analysis for the generalized equation- lasso. In ISIT, pages 2021-2025, 2015.
12

---

[43] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. The squared-error of generalized LASSO: precise analysis. In Allerton, pages 1002-1009, 2013.
[44] Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Handbook of econometrics, 4:21 12211,, 1994.
[45] Christos Thrampoulidis, Ashkan Panahi, Daniel Guo, and Babak Hassibi. Precise error analysis of the LASSO. In ICASSP, pages 3467-3471, 2015.
13

---

The Reliability of OKRidge (Appendix)
A Limitaion and Impact
Our results rely on Gaussian input settings. For non- Gaussian settings, we can utilize Fisher transformation, Box-Cox transformation, or inversion sampling to transform non-Gaussian distribution to Gaussian distribution. In our future work, we will discuss potential extensions of our findings to non-Gaussian input settings, providing insights into the universality of the results.
Limitaion:
Impact: Our work provides theoretical support for the broad application of OKRidge, which does not require proprietary software expensive licenses [T]. unlike its main competitor. This can significantly impact various regression applications.
B Proof of Theorem 4.1
Theorem 4.1
If define the parameter saddle point optimization problem:
16 the problem ( is equivalent the following
min
Asuddle ridge (B.z)
s.t.
2j
S k 2j E
[0,1],
(38)
B.z
j=1
where
Chadelee
ridge
(B,z) = 11
X
+
Σ
(39)
Zj
j
5=1,zy00
Proof. The problem p is
min max ridgo (B,z,c), A,2
s.t.
2j S. k, 2j E [0.1].
j=l
where
-
Fonchel ridee
(B, ;= 11 XB11 + A
(3,c
4
The parameter c in (16)
P R
if
24 =0
Cj
28g
if
2j #
Substitute parameter of 16 into 9
Fenchell
(B,2,c) = 11
XB112 + A
d
(B,c,
222))
2
4 2g)
ridge
233
28
= XB11 A
Σ
[B
/2/4 zj
4-22) 23
1,3y/00
2,83
83
x
2j
1=
d
2
11 - x
Σ
Zj
3=1,2,
14

---

Define
(saddle ridge
(B,z) == y X 2 X
Σ
1=1, Zj
Then, the problem 9 can be equivalently written as
min
ridge
Asuudlle
(B,z)
S.t.
2j S k 2j E 10.
A.2
j=1
which is our saddle point optimization 388.
C Proof of Theorem 4.2
Theorem 4.2
The function (B)) defined in Equation 20 is lower bounded by
L( 2 1 - x + & @ B).
(40)
where @ is Hadamard product, and SumTop, (-) denotes the summation of the largest & elements of given vector.
Proof. The Equation 20
C(B)
min Laaddle (B,z),
d s.t. Σ ==1
2j S k, E 1].
According to (00 and 39
$3
L(B) min ridge (B,z) min y1y X +
Σ
(41)
f=1.2; #00 3j
Following the method of [. we minimize in the optimization (41) under the constraints
D/= 2j S ls and zj E [0, 1] for vjj, have 2j for the top terms of B3 and zj 0 otherwise. Then, we have
83 1
C(B) 2 1
X
X
Σ
ly XB112 ASumTop,, @ B).
1=1,,,
D Proof of Lemma 5.1
Lemma 5.1 Suppose (w, u) defined as formulation (66 Then, (lw u) convex-concave on Rd
R
Proof. Obviously, (ww, u) is concave about u. Next, we indicate that viw u) is convex about w. For any w. w E Rdd and vo E (0, 1), [0m, + (1 - 0) < O0² + (1 - 0))
Then, we have
SumTop (10w (1 0)w] (rw + (1 0yw)
<SumTTop, (Ow + (1 w w
<SmTTop, (hw w + SumTopp ((1 w w
<0SumTop, W + 0 Sum
@ w)
SumTop& is a convex operator. Therefore, 4/(w (w. u) is concave about u and convex about w.
15

---

E Proof of Theorem 5.2
Suppose 3 is the true weight parameter of the problem ( 8 is the optimal solution
Theorem 5.2
to the objective function 22 of OKRidge, D(7) - D(T) E (0, 1),
aNSE lim NSE lim || 8 11/00/2
-
o² o2-0
Define Amap the solution of map(r) for r > 0, then, the estimation error of OKRidge given by the following probability limit:
lim aNSE - A()), d=0
(42)
where A(Å) D(A) DA) and x Amap-
Proof. Starting from the simplified AO problem (36), let's define
x(a,n) = n/2² + o² N
D r(n).
(43)
Given that k(a, 17) is strongly convex in and concave in 77, we denote (a*, n7) as the Nash equilibrium of k(a, 17). Then, a' is unique and we use duality to compute a". For any
@x(a, 11) dc
on
D - 1 0. (1) 0,=
D
01 1 2
(44)
Va² + 0²
which is well-defined, due to 1 - + > 0. Substituting a (17) back into (43) gives:
<(a" = 1/V 1/ 2 + 0² - a'n D(=)
- -((n)
17
2
D
17
0² 1 2
+ on
1- D V D - r(m)
110 )
170
1 v
D - 1'()).
1'(n) no
V 2
2
Differentiating k(a", n)) with respect to 17, we have
On(a", m) On o D(=)) A
C
X
1 1- ( ((
2 110
r'(1)
(')))
V D(2)
2
1/2
V1 1(
= =omap( -
lim n
(45)
00
2/12
Here, map(r) = 0 when T Amap. Hence, 17" Amap
the optimal solution, due to
Ok(aa, .1)
On lypp" emma((Amap)
lim 0-000
O.
2Nmap /n
Because the form of 7-) and the value of 8 are determined, the form of map(-) and the value of Amap fixed. In other words, Amap is function about A. Therefore, we can take 17" Xmap to formulation
(( a²(n') = o. | - (
D(Amap) D(Xmap)
T V
16

---

Moreover o(a",1")) Xmap Amop
A ovo 1-
D D(Amap). Denote
Amap.
(
a² 0 V - D(À)
(46)
Based on the analysis above, if the optimal solution of optimization (36) a = a', we have
||0 Dossitee ||2 _ a for approximated AO problem (29) Furthermore, according to formulation 466
l OF occurs for the approximated AO problem (29) and is independent the original AO
problem Thus, formulation (30) holds:
lim
f(B) = f(3) + lim lim f(B) = f(3).
(47)
B 8-1
d-+000-00
In the case + and 0. formulation 47 allows us translate the optimal error a' of the
approximated AO problem (2 to the optimal error of the original AO problem (27). Combining
formulations (4 (47 and CGMT, |
12 P a holds for PO problem 25) Then, for the
estimation error of OKRidge produced by (22)
we have
|| B - a".
Therefore, combining PO problem (25). AO problem (2 the relation and the formulations
23 and 4 according to CGMT, obtain::
D(1)
P D(Ā) d 0-10
lim lim - ---1/112/0 d000 0-0
P
lim lim ||B 8/1///0
1 D(1)
1 1 D(2)
To sum up,
lim aNSE P, A()), d-0
where A(Å) ((A) I-D(A)*
and Ā Amap-
F
Experiments Appendix
Computing Platform
All experiments were run the 10x TensorEX TS2-673917-DPN Intel Xeon Gold 6226 Processor, 2.7Ghz. We set the memory limit be 100GB.
F.2
More Experiments
Figures
FI
F7 (a) demonstrate that when is fixed, NSE converges to constant as - 0. In
Figures (b), the curves converge towards the real blue curve as a 0, with the real blue
curve representing A (Å). These observation validate Theorem 5.2
17

---

1-30
Pear
(a) The change of NSE with 1/0 under different A.
(b) The change of NSE with À under different
Figure Fl: The change of NSE under = 0.5,, = =0.1, d = 200
225
<- 6.00
2.0
202
375
1
10-
1-30
(a) The change of NSE with 1/0 under different A.
(b) The change of NSE with À under different
Figure F2: The change of NSE under = 0.5, & = 0.1, d = 1000
18

---

115
CT
125
ISE
(a) The change of NSE with 1/a under different
(b) The change of NSE with À under different
Figure F3: The change of NSE under
= 0.4, = 0.1, d = 1000
==10
A-36
=01
=001
d 0.000
372
roa
3-
NSE
2-
103
14
025
Joer
100
(a) The change of NSE with 1/ under different A.
(b) The change of NSE with À under different
Figure F4: The change of NSE under = 0.6, $/4 = 0.1, d = 1000
19

---

23
1-30
NSE
(a) The change of NSE with 1/0 under different
(b) The change of NSE with À under different
Figure F5: The change of NSE under the sparsity = 0.10
175
==10
==1
15.0
=001
d' 0.000
rta
10.0
NSS
5.0
25
100
(a) The change of NSE with 1/0 under different A.
(b) The change of NSE with À under different dr
Figure F6: The change of NSE under the sparsity = 0.15
20

---

=1=10
4.1
0.01
0.001
15-2
50
17.
40
3.2
5.2
Abe
100
(a) The change of NSE with 1/a under different X.
(b) The change of NSE with À under different
Figure F7: The change of NSE under the sparsity = 0.20
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We highly summarize what we do in the abstract. The introduction clearly introduces the concepts and issues that are related to our main results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our paper explicitly acknowledges the dependency on Gaussian inputs limitation, prompting further investigation into applicability to non-Gaussian contexts.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: We provide the assumptions of the theorems and all our theorems are followed by their proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our paper meticulously details all methodologies, parameters, and experimen- tal conditions necessary for replication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
23

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We focus on the OKRidge algorithm in our paper. The codes of the OKRidge algorithm are from [ which is open.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//dddeeebmimiia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our paper comprehensively details all training and testing protocols, including data management, hyperparameter selection, and optimization techniques.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our results based averaging the results from 10 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our paper specifies the computing platform, processor details, and memory constraints, ensuring accurate replication of the experimental setup and results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics hattps://neur/ wttppppss.cppppcccppeeeeeeecseee htt.aa/ieeehhesuueeeelleeeeeeeee
Answer: [Yes]
Justification: Our research strictly adheres to the NeurlPS Code of Ethics, focusing theoretical advancements without ethical concerns in implementation or application.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper assesses the broad accessibility and potential application impacts of OKRidge, highlighting its advantages over costlier alternatives.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper focuses theoretical aspects of the OKRidge algorithm and uses synthetic data, mitigating risks associated with real-world data misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our paper properly credits the original creators of the OKRidge algorithm and adheres to the licensing terms the cited open resources required by NeurIPS paper II.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/dataseta
datasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
We don't introduce new assets in our paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA],
Justification: Our paper is theoretical and includes numerical verification experiments. does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is theoretical and includes numerical verification experiments. It does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "8IsDsLMVbM", "reviewer": "Reviewer_553k", "summary": "This paper improves the theoretical reliability of OKRidge method for the sparse ridge regression by introducing a theoretical error analysis. OKRidge is reframed in this paper as a Primary Optimization problem. Then this paper use the Convex Gaussian Min-max Theorem (CGMT) to simplify it to an Auxiliary Optimization problem. This paper provide a theoretical error analysis for OKRidge based on the  problem.", "questions": "- Can the authors provide more insight into the practical applications where this theoretical error analysis will be most impactful?\n- Are there any specific strategies proposed for extending the theoretical findings to non-Gaussian input settings?\n- How robust are the experimental findings to variations in the underlying assumptions, such as the sparsity level and noise distribution?", "limitations": "The authors have addressed the limitations related to Gaussian input settings and indicated future work on extending the results to non-Gaussian settings.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a novel theoretical error analysis for the OKRidge method, leveraging the CGMT framework, which is a contribution to the field of sparse regression.\n- The paper is well-structured, with a clear outline of the problem, methodology, and results.", "weaknesses": "- While the theoretical contributions are clear, the practical motivation for why this particular error analysis is crucial could be better articulated. More emphasis on how this analysis directly impacts real-world applications would strengthen the paper.\n- The experiments, although validating the theoretical claims, are limited in scope. They primarily focus on synthetic data with Gaussian noise. Including more diverse datasets, especially real-world examples, would enhance the validity of the results.\n- The reliance on Gaussian input settings is a significant limitation. The paper acknowledges this but does not provide a clear path for extending the results to non-Gaussian settings. This could limit the applicability of the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 553k, we truly appreciate the patience and effort you've dedicated to providing valuable feedback. We appreciate the opportunity to address your concerns.\n\n### For Weaknesses:\n\n__W1:__ Error analysis of algorithms is a very crucial and popular topic in the field of machine learning, as evidenced by several papers [A1-A8]. Therefore, it is important to study the theoretical error of this advanced OKRidge algorithm which is both faster and more accurate than existing approaches [1]. In our paper, there have been some contents of practical motivation and impact on real-world applications:\n\n(1). Practical motivation:\n\nSparse Ridge Regression (SRR) has achieved notable success in machine learning applications, including statistics [2], signal processing [3], dynamical systems [4], and others. The OKRidge method is both faster and more accurate than existing approaches in solving SRR. However, the absence of theoretical analysis on the error of OKRidge impedes its large-scale applications. We provide a theoretical perspective on the estimation error of the OKRidge method under Gaussian assumption. (see lines 1-15 and 29-39)\n\n(2). Impact on real-world applications:\n\ni). This theoretical error analysis substantiates the reliability of OKRidge and provides guidelines on the error analysis of other algorithms. (see lines 10-11 and 303-304)\n\nii). Our analysis strengthens the theoretical underpinnings of OKRidge and provides theoretical reliability for its broad application in the real-world. (see lines 59-60)\n\nii). Our work provides theoretical support for the broad application of OKRidge, which does not require proprietary software or expensive licenses, unlike its main competitor [1]. This can significantly impact various regression applications. (see lines 395-397)\n\nFollowing your suggestion, in our revision, we will provide more practical motivation and impacts on real-world applications to strengthen our paper.\n\n[A1] Estimating the Error of Randomized Newton Methods: A Bootstrap Approach. ICML 2020\n\n[A2] $l_{1, p}$-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods. ICML 2015\n\n[A3] Addressing Function Approximation Error in Actor-Critic Methods. ICML 2018\n\n[A4] Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error. NeurIPS 2021\n\n[A5] A Comparison of Hamming Errors of Representative Variable Selection Methods. ICLR 2022\n\n[A6] On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning. ICLR 2020\n\n[A7] Generalization error of spectral algorithms. ICLR 2024\n\n[A8] Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap. ICML 2018\n\n__W2:__ The OKRidge proposed by [1]  is both faster and more accurate than existing approaches in solving SRR problems. But, the paper [1] lacks theoretical analysis on the estimation error of OKRidge. To the best of our knowledge, we are the first to fill this gap. The primary contribution of our paper is to provide a theoretical perspective on the estimation error of the OKRidge method under Gaussian settings, where the Gaussian hypothesis is a commonly used approach in learning theory, as evidenced by papers [B1~B6]. Our paper is purely theoretical and Reviewer uvCX verifies the correctness of our theorems. The numerical experiments in our paper are sufficient to validate our theoretical claims. Moreover, the experiments of OKRidge on real-world examples have been done by [1] (See Figure 3 in [1]), which shows that the error of OKRidge tends to 0. This verifies the validity of our theorems.\n\n[B1] Explicit Regularisation in Gaussian Noise Injections. NeurIPS 2020\t\n\n[B2] Communication-Constrained Bandits under Additive Gaussian Noise. ICML 2023\n\n[B3] Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise. COLT 2024\n\n[B4] Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections. ICML 2021\n\n[B5] Pitfalls of Gaussians as a noise distribution in NCE. ICLR 2023\n\n[B6] Precise Error Analysis of Regularized M-Estimators in High Dimensions. IEEE Trans. Inf. Theory. 2018\n\n[B7] On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions. NeurIPS 2023\n\n[B8] Hyperbolic VAE via Latent Gaussian Distributions. NeurIPS 2023\n\n__W3:__ It is worth emphasizing that the Gaussian setting is a commonly used approach for theoretical analysis of algorithms in machine learning, as evidenced by papers [B1~B8]. Thus, our paper provides a theoretical perspective on the error of the OKRidge method under Gaussian settings. Reviewer 8imU also mentions this limitation but acknowledges our contribution under Gaussian settings. Although extending the results to non-Gaussian distributions is beyond the scope of this paper, we briefly discuss the strategies for non-Gaussian distributions here: We can utilize Fisher transformation, Box-Cox transformation, or inversion sampling to transform non-Gaussian distribution to Gaussian distribution. \n\n### For Questions:\n\n__Q1:__ See Answer to W1.\n\n__Q2:__ See Answer to W3.\n\n__Q3:__ We analyze the error of the OKRidge method under Gaussian assumption, where the Gaussian noise level is $\\sigma$. The experiments on noise level have been shown in Figures 1 and F1~F4 (a) of our paper. \n\nFollowing your advice, we conduct experiments on the variations in the sparsity level and noise distribution. The experimental results are shown in the pdf of Author Rebuttal by Authors. The experimental findings to variations about the sparsity level and noise distribution show that the NSE converges to a constant decided by $\\lambda$, aligning excellently with our theoretical predictions. In other words, these experimental findings are robust to support our theoretical claims. We will add these experimental results in our revision.\n\nWe sincerely thank you once again for your time, effort, and expertise in reviewing our manuscript. We hope our responses have met your expectations and satisfaction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Br8RKSRNzc", "reviewer": "Reviewer_mn2F", "summary": "OKRidge proposed in [1] shows promising results and becomes the SOTA sparse ridge regression solvers. This paper conducts the first error analysis for OKRidge. Convex Gaussian min-max theorem (CGMT) is well introduced in this paper. Based on CGMT, they develop the asymptotic theory for OKRidge. The experiments are also conducted to support the theory. This is a solid and up-to-date work.", "questions": "1, What is the difference between GMT and CGMT and what are the advantages of CGMT over GMT?\n2, Why can we reduce the problem (26) to (35) that only involves two scalar variables?", "limitations": "The author has presented the limitations in the checklist.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper first uses CGMT to conduct the rigorous analysis for OKRidge, which is an up-to-date research. It is novel to reformulate the estimation error of OKRidge as a PO problem and further reduce the PO problem to an AO problem. By analyzing the AO problem, they show that the NSE of OKRidge tends to a constant. Then the estimators of OKRidge is close to the groundtruth. The empirical results also support the theories presented in this paper. The theoretical results in this paper are original which has never been explored before. This paper bridges the gap between theory and practice.", "weaknesses": "The paper presents both GMT and CGMT. But the difference between these two concepts and the advantages of CGMT over GMT are not well clarified. \n\nIn Line 208, the LHS of (23) misses the \\min_{\\beta}.\n\nIt is interesting to reduce the AO problem (26) to an equivalent optimization (35) that only involves two scalar variables. But more descriptions about why can we do this transformation are needed.\n\nIn Line 300, it is improper for the formulation to use “=”, as it should indicate an approximation in probability according to Theorem 5.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer mn2F\n\nDear Reviewer mn2F,\n\nThank you for your job in reviewing our paper. We are very sorry for the inconvenience caused by our presentations. To this end, following your comments, we will correct our work in the revision. \n\n### In regards to your Weaknesses:\n\n__Weakness 1.__ The paper presents both GMT and CGMT. But the difference between these two concepts and the advantages of CGMT over GMT are not well clarified. \n\n__Answer:__ We have introduced the concepts of GMT and CGMT, and clarified the difference between GMT and CGMT in Section 3.2:\n\n``CGMT originates from Gordon’s Gaussian Min-max Theorem (GMT), which provides probabilistic bounds on the optimal cost of $\\textbf{PO}$ problem via a simpler $\\textbf{AO}$ problem. CGMT further applies convexity assumptions to tighten the upper and lower bounds of both the optimal cost and the norm of the optimal solution of the original problem.''\n\nThe CGMT framework has been utilized to analyze the performance of solutions to non-smooth regularized convex optimization problems, which inspires us to apply the CGMT framework to analyze the NSE of the OKRidge method.\n\n(Please refer to Section 3.2 of our main paper.)\n\n__Weakness 2.__ In Line 208, the LHS of (23) misses the $\\min_{\\beta}$.\n\n__Answer:__ Formulation (23) is the intermediate process of deriving from (22) to (24), which is correct and doesn't affect (24). More specifically, \n\n$$\\mathop{\\min}\\limits_ {\\pmb{\\beta}}\\frac{1}{\\sqrt{n}}\\big[\\Vert \\pmb{X} (\\pmb{\\beta}-\\pmb{\\beta}^*) + \\pmb{\\epsilon} \\Vert_ 2^2 + \\lambda\\text{SumTop}_ {k}(\\pmb{\\beta}\\odot\\pmb{\\beta})\\big]\\tag{22}$$\n\nWe introduce the new variable $\\pmb{w}:=\\pmb{\\beta}-\\pmb{\\beta}^*$ and apply the Fenchel-Moreau theorem (14) to formulation (22),\n\n$$\\begin{align*}\n&\\mathop{\\min}\\limits_ {\\pmb{\\beta}}\\frac{1}{\\sqrt{n}}\\big[\\Vert \\pmb{X} (\\pmb{\\beta}-\\pmb{\\beta}^*) + \\pmb{\\epsilon} \\Vert_ 2^2 + \\lambda\\text{SumTop}_ {k}(\\pmb{\\beta}\\odot\\pmb{\\beta})\\big],\\\\\\\\\n=&\\mathop{\\min}\\limits_ {\\pmb{\\beta}}\\frac{1}{\\sqrt{n}}\\big[\\Vert \\pmb{X} \\pmb{w} - \\pmb{\\epsilon} \\Vert_ 2^2 + \\lambda\\text{SumTop}_ {k}\\big((\\pmb{w}+\\pmb{\\beta}^*)\\odot(\\pmb{w}+\\pmb{\\beta}^*)\\big)\\big],\\\\\\\\\n=&\\mathop{\\min}\\limits_ {\\pmb{w}}\\max_ {\\pmb{u}} \\frac{1}{\\sqrt{n}}\\Big[\\pmb{u}^\\top\\pmb{X}\\pmb{w}- \\pmb{u}^\\top \\pmb{\\epsilon}-\\frac{\\Vert\\pmb{u}\\Vert^2_ 2}{4}+ \\lambda\\text{SumTop}_ {k}\\big((\\pmb{w}+\\pmb{\\beta}^*)\\odot(\\pmb{w}+\\pmb{\\beta}^*)\\big)\\Big]=:\\Phi_ {\\text{OKRidge}}(\\pmb{X}),\\tag{24}\n\\end{align*}$$\n\nwhere,\n$$\\begin{align*}\n&\\frac{1}{\\sqrt{n}}\\big[\\Vert \\pmb{X} \\pmb{w} - \\pmb{\\epsilon} \\Vert_ 2^2 + \\lambda\\text{SumTop}_ {k}\\big((\\pmb{w}+\\pmb{\\beta}^*)\\odot(\\pmb{w}+\\pmb{\\beta}^*)\\big)\\big],\\\\\\\\\n=&\\max_ {\\pmb{u}} \\frac{1}{\\sqrt{n}}\\Big[\\pmb{u}^\\top\\pmb{X}\\pmb{w}- \\pmb{u}^\\top \\pmb{\\epsilon}-\\frac{\\Vert\\pmb{u}\\Vert^2_ 2}{4}+ \\lambda\\text{SumTop}_ {k}\\big((\\pmb{w}+\\pmb{\\beta}^*)\\odot(\\pmb{w}+\\pmb{\\beta}^*)\\big)\\Big],\\tag{23}\n\\end{align*}$$\n\nTherefore, the formulation (23) doesn't need ``$\\mathop{\\min}\\limits_ {\\pmb{\\beta}}$''.\n\n(Please refer to lines 206-212 of our main paper.)\n\n\n__Weakness 3.__ It is interesting to reduce the AO problem (26) to an equivalent optimization (35) that only involves two scalar variables. But more descriptions about why can we do this transformation are needed.\n\n__Answer:__ Theorem 3.2 indicates that, if the optimal cost $\\phi(\\pmb{g},\\pmb{h})$ of $\\textbf{AO}$ concentrates to some value $\\mu$, the same holds true for $\\Phi(\\pmb{G})$ of $\\textbf{PO}$. Furthermore, under appropriate additional assumptions, the optimal solutions of the $\\textbf{AO}$ and $\\textbf{PO}$ problems are also closely related by $\\Vert\\pmb{w}_ {\\Phi}(\\pmb{G})\\Vert = \\Vert \\pmb{w}_ {\\phi}(\\pmb{g},\\pmb{h})\\Vert$, as $n\\to \\infty$. This suggests that, within the CGMT framework, a challenging $\\textbf{PO}$ problem can be replaced with a simplified $\\textbf{AO}$ problem, from which the optimal solution of the $\\textbf{PO}$ problem can be accurately inferred. Moreover, we are more concerned about $\\Vert \\pmb{w}_ {\\phi}(\\pmb{g},\\pmb{h})\\Vert$. Therefore, if we reduce the AO problem only involves scalar variable about $\\Vert \\pmb{w}_ {\\phi}(\\pmb{g},\\pmb{h})\\Vert$, we obatain the error of OKRidge method by the relationship $\\Vert\\pmb{w}_ {\\Phi}(\\pmb{G})\\Vert = \\Vert \\pmb{w}_ {\\phi}(\\pmb{g},\\pmb{h})\\Vert$.\n\nIf the optimal solution of optimization (35) is $\\alpha=\\alpha^*$, we have $\\Vert\\pmb{w}_ {\\hat{\\phi}_ {\\text{OKRidge}}}\\Vert_ 2\\stackrel{P}{\\longrightarrow}\\alpha^*$ for approximated $\\textbf{AO}$ problem (28). If $\\alpha^* $ further tends to $0$, according to formulation (29) and CGMT, $\\Vert\\pmb{w}_ {\\Phi_{\\text{OKRidge}}}\\Vert_ 2\\stackrel{P}{\\longrightarrow} \\alpha^*$ holds for $\\textbf{PO}$ problem (24). Then, for the estimation error of OKRidge produced by (21), we have $\\Vert\\hat{\\pmb{\\beta}}-\\pmb{\\beta}^*\\Vert_ 2\\stackrel{P}{\\longrightarrow} \\alpha^* $. Therefore, it only remains to obtain the optimal value of $\\alpha$ in optimization (35) that plays the role of $\\Vert\\pmb{w}\\Vert_ 2$.\n\n(Please refer to lines 152-158 and 259-264 of our main paper.)\n\n\n__Weakness 4.__ In Line 300, it is improper for the formulation to use “=”, as it should indicate an approximation in probability according to Theorem 5.2.\n\n__Answer:__ Thank you for your comments. We will change the “=” to ``$\\stackrel{P}{\\longrightarrow}$'' in our revision.\n\n### In regards to your Questions:\n\n__Question 1.__ What is the difference between GMT and CGMT and what are the advantages of CGMT over GMT? \n\n__Answer:__ Thank you for your comments. Question 1 is similar to Weakness 1 . Please see our Answers to Weakness 1.\n\n__Question 2.__ Why can we reduce the problem (26) to (35) that only involves two scalar variables?\n\n__Answer:__ Thank you for your comments. Question 2 is similar to Weakness 3. Please see our Answers to Weakness 3.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xQuX6doKph", "reviewer": "Reviewer_uvCX", "summary": "The authors provide a theoretical error analysis for the OKRidge method, which is both faster and more accurate than existing approaches for solving sparse ridge regression. The experimental results are in excellent agreement with the theoretical findings.", "questions": "See the weaknesses.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors analyze the estimation error of OKRidge using Convex Gaussian min-max theorem, and the proof appears to be correct.\n\n2. The theoretical and experimental results validate the reliability of the OKRidge method.\n\n3. This theoretical error analysis provides support for the broad application of OKRidge.", "weaknesses": "1. Because the OKRidge method is used to solve a k-sparse linear regression problem and the authors make the Gaussian assumption, the following related literatures are recommended to be cited:\n\n> * 1.1 Mohsen Bayati and Andrea Montanari. The lasso risk for Gaussian matrices. Information Theory, IEEE Transactions on, 58(4):1997–2017, 2012\n\n> * 1.2 D. Bertsimas, J. Pauphilet, and B. Van Parys. Sparse regression: Scalable algorithms and empirical performance. Statistical Science, 35(4):555–578, 2020\n\n> *1.3 Peter J Bickel, Yaacov Ritov, and Alexandre B Tsybakov. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009.\n\n2. The authors provide numerical experiments with $n/d=0.4, 0.5 and 0.6$, but the sparsity is just $k/d=0.1$. I want to see more experiments with various sparsity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer uvCX\n\nDear Reviewer uvCX,\n\nThank you very much for your detailed and thorough review of our paper. We sincerely appreciate the time and effort you have dedicated to providing insightful comments and bringing these issues to our attention. \n\n### In regards to your Weaknesses:\n\n\n__Weakness 1.__  Because the OKRidge method is used to solve a k-sparse linear regression problem and the authors make the Gaussian assumption, the following related literatures are recommended to be cited:\n\n1.1 Mohsen Bayati and Andrea Montanari. The lasso risk for Gaussian matrices. Information Theory, IEEE Transactions on, 58(4):1997–2017, 2012\n\n1.2 D. Bertsimas, J. Pauphilet, and B. Van Parys. Sparse regression: Scalable algorithms and empirical performance. Statistical Science, 35(4):555–578, 2020\n\n1.3 Peter J Bickel, Yaacov Ritov, and Alexandre B Tsybakov. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009.\n\n__Answer:__ Thank you for you suggestions. Following your suggestions, we will cite these related literatures in our revision.\n\n\n__Weakness 2.__  The authors provide numerical experiments with $n/d=0.4, 0.5$ and $0.6$, but the sparsity is just $k/d=0.1$. I want to see more experiments with various sparsity.\n\n__Answer:__ Thank you for your suggestion. Following your suggestion, we conduct experiments with sparsity levels $0.1, 0.15,\\text{and}\\ 0.2$. The experimental results can be seen in the pdf of Author Rebuttal by Authors.\n\nThe experimental findings with various sparsity levels demonstrate that the NSE converges to a fixed constant determined by $\\lambda$, aligning excellently with our theoretical predictions. We will add these experimental results in our revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E0tQ2EBKEW", "reviewer": "Reviewer_mBVh", "summary": "An error analysis of a lower bound technique for solving sparse ridge regression problems is presented. Sparse ridge regression is ridge regression with the constraint that the parameter vector has at most k non-zero entries, where k is a parameter. It has been proposed to solve the sparse ridge regression problem by solving a \"tight lower\" bound problem. The normalized deviation of the solution of the lower bound problem to the \"true\" model parameter vector is analyzed in the high-dimensional setting, that is, the setting where the number of features (and data points) go to infinity.", "questions": "1. When you solve Problem 4 with the objective function from Equation 3, do you set the n-k smallest entries in \\hat\\beta to zero?\n2. In Line 56, why is it \\Delta (\\hat\\lambda) and not \\Delta (\\lambda)?", "limitations": "None. This is a theory paper.", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The problem that is addressed by the paper is interesting (for an expert community) and technically challenging.", "weaknesses": "I am not able to thoroughly review the paper in the time available for a NeurIPS review. However, since the contributions of the paper are mostly theoretical, a careful review by someone closer to the topic would be necessary to make sure that the paper is sound. Probably a journal is a better venue for this type paper.  Nonetheless, I would have tried to check technical details of the paper if it had been more accessible. The presentation is fairly poor, which makes it difficult (and time-consuming) for a non-expert like me to thoroughly review it. \n\nSome areas where the presentation can be improved:\n- Abstracts should not include references.\n- The introduction immediately becomes technical, which makes it difficult to understand that problem that you are addressing. Make clear that you provide a theoretical high-dimensional analysis of an algorithm in an idealized setting. You are analyzing the case, where the entries of data matrix are chosen i.i.d from standard normal distributions. Another assumption is that the number n(d) of data points grows with d such that n(d)/d = \\delta \\in (0,1), where \\delta is a constant. All this information is there in the paper, but it could be put better into perspective if your goals had been clearly stated at this point. \n- Make clear that the estimation error in Equation 5 is a random variable, because X and \\epsilon are random.\n- Equation 5 is missing a \\odot\n- The main paper provides many technical definitions/details but no proofs. The details are relevant when checking the proofs, but do not help with the intuition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer mBVh\n\nDear Reviewer mBVh,\n\nWe truly appreciate the patience and effort you've dedicated to providing valuable feedback. Your meticulous guidance is greatly valuable for us to enhance the overall quality of our research. We appreciate the opportunity to address your questions and concerns.\n\n### In regards to your Weaknesses proposed to improve presentation:\n\n__Weakness 1.__ Abstracts should not include references.\n\n__Answer:__ Thank you for your comments. Following your suggestion, we will delete the references in the abstraction in our revision.\n\n__Weakness 2.__ The introduction immediately becomes technical, which makes it difficult to understand the problem that you are addressing. Make clear that you provide a theoretical high-dimensional analysis of an algorithm in an idealized setting. You are analyzing the case, where the entries of data matrix are chosen i.i.d from standard normal distributions. Another assumption is that the number n(d) of data points grows with d such that $n(d)/d = \\delta \\in (0,1)$, where $\\delta$ is a constant. All this information is there in the paper, but it could be put better into perspective if your goals had been clearly stated at this point.\n\n__Answer:__ Thank you for your comments. We apologize for any inconvenience caused by our presentations. Following your suggestion, we make our goals more clearly stated: We provide a theoretical high-dimensional analysis of the OKRidge algorithm in idealized settings that the entries of the data matrix are chosen i.i.d from standard normal distributions and $\\lim_{d\\to\\infty}n(d)/d = \\delta \\in (0,1)$. We will emphasize this point in our revision.\n\n\n__Weakness 3.__ Make clear that the estimation error in Equation 5 is a random variable, because $X$ and $\\epsilon$ are random.\n\n__Answer:__ Thank you for your suggestion. In our original paper, the estimation error in Equation (5) defaults to a random variable. We are sorry for the inconvenience caused by our presentations. Following your suggestion, in our revised version, we will emphasize that the estimation error $w$ in Equation (5) is a random variable with randomness from the random variables $X$ and $\\epsilon$.\n\n\n__Weakness 4.__ Equation 5 is missing a ``$\\odot$''.\n\n__Answer:__ Thank you for your comments. We will add $\\odot$ to rectify Equation (5) in our revision.\n\n\n__Weakness 5.__ The main paper provides many technical definitions/details but no proofs. The details are relevant when checking the proofs, but do not help with the intuition.\n\n__Answer:__ Thank you for your insightful feedback on our manuscript. Our paper is purely theoretical, with technical details and proofs provided in our Appendix B~E (See lines 398-450). We have also marked the locations of the proofs for the key steps in the original paper. We apologize for any inconvenience caused by our presentations. Following your suggestions, we will provide more intuitions for our technical details in our revision.\n\n### In regards to your Questions:\n\n__Question 1.__ When you solve Problem 4 with the objective function from Equation 3, do you set the $n-k$ smallest entries in $\\hat\\beta$ to zero?\n\n__Answer:__ Thank you for your comments. According to our Theorem 5.2, $\\lim_{d\\to \\infty}\\lim_{\\sigma\\to 0}\\Vert\\hat{\\pmb{\\beta}}-\\pmb{\\beta}^*\\Vert_2\\stackrel{P}{\\longrightarrow} 0$. Therefore, when $n(d)$ is sufficiently large, the $n-k$ smallest entries in $\\hat\\beta$ will become zero. We do not manually set the $n-k$ smallest entries in $\\hat\\beta$ to zero.\n\n__Question 2.__ In Line 56, why is it $\\Delta (\\hat\\lambda)$ and not $\\Delta (\\lambda)$?\n\n__Answer:__  Thank you for your comments. According to our Theorem 5.2, we have $\\hat\\lambda=\\lambda_{map}$. Although $\\lambda_{map}$ is decided by $\\lambda$, they have different meanings. Therefore, it is $\\Delta (\\hat\\lambda)$, not $\\Delta (\\lambda)$. We will emphasize this in our revision.\n\nWe sincerely thank you once again for your time and effort in reviewing our paper. The opportunity to solve your concerns undoubtedly contributes to my personal growth. We hope that our answers have met your expectations and satisfaction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tXIUJJyCFw", "reviewer": "Reviewer_8imU", "summary": "This paper analyzes the estimation error of the Scalable Optimal K-Sparse Ridge Regression (OKRidge) method proposed by [1]. Specifically, they reframe the estimation error of OKRidge as a Primary Optimization (PO) problem and use the Convex Gaussian Min-Max Theorem (CGMT) to simplify the PO problem into an Auxiliary Optimization (AO) problem. Subsequently, this paper provides a theoretical error analysis for OKRidge based on the AO problem.", "questions": "The theoretical results are based on CGMT technology, which requires the input to be Gaussian. Could you generalize the input to non-Gaussian distributions?", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "__Originality:__ The absence of theoretical analysis on the error of OKRidge impedes its large-scale applications. This paper analyzes the estimation error of OKRidge to fill this gap.\n\n__Clarity:__ This paper demonstrates a high level of clarity in its presentation, which significantly enhances its readability. All symbols are clearly defined at the outset and the proofs provided are rigorous and detailed. \n\n__Quality and Significance:__ This paper applies CGMT technology to transform the estimation error of OKRidge into a simplified AO problem and offer a theoretical error analysis for OKRidge. This theoretical error analysis substantiates the reliability of OKRidge and provides guidelines for the error analysis of other algorithms.", "weaknesses": "1. Many formulas lack punctuation marks after them, such as formulations (10), (11), (22), etc. The author should review the entire text and pay attention to these details. \n\n2. Theorem 5.2 demonstrates that $\\hat{\\lambda}=\\lambda_{map}$. It would be more concise to substitute $\\Delta(\\hat{\\lambda})$ with $\\Delta(\\lambda_{map})$.\n\n3. The colors of the curves for $\\lambda=1$ and $\\lambda=50$ in Figure 1 and F1-F4 (a) are the same. This paper should ensure that the curves are distinguishable by using different colors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Answer to Reviewer 8imU\n\nDear Reviewer 8imU,\n\nThank you for your job in reviewing our paper. We are very sorry for the inconvenience caused by our presentations. We extend our heartfelt gratitude for your patience and meticulous guidance. Your insightful comments is valuable for us and we appreciate the opportunity to address your questions and concerns.\n\n### In regards to your Weaknesses:\n\n\n__Weakness 1.__  Many formulas lack punctuation marks after them, such as formulations (10), (11), (22), etc. The author should review the entire text and pay attention to these details. \n\n__Answer:__  Thank you for your comments. We have checked the entire paper and rectified these details in our revision.\n\n__Weakness 2.__ Theorem 5.2 demonstrates that $\\hat{\\lambda}=\\lambda_{map}$. It would be more concise to substitute $\\Delta(\\hat{\\lambda})$ with $\\Delta(\\lambda_{map})$.\n\n__Answer:__ Thank you for your suggestion. Following your suggestion, we will replace $\\Delta (\\lambda)$ with $\\Delta (\\hat\\lambda)$ in our revision to make it more clear.\n\n__Weakness 3.__ The colors of the curves for $\\lambda=1$ and $\\lambda=50$ in Figure 1 and F1-F4 (a) are the same. This paper should ensure that the curves are distinguishable by using different colors.\n\n__Answer:__ Thank you for your suggestion. We will rectify this to ensure that the curves are distinguishable by using different colors in our revision.\n\n\n### In regards to your Questions:\n\n__Question 1.__ The theoretical results are based on CGMT technology, which requires the input to be Gaussian. Could you generalize the input to non-Gaussian distributions?\n\n__Answer:__ Thank you for your comments. The OKRidge proposed by [1] is currently the state-of-the-art algorithm for solving sparse ridge regression problems. However, [1] lacks theoretical analysis on the error of the OKRidge method. To the best of our knowledge, we are the first to investigate the estimation error of the OKRidge method. The primary contribution of our paper is to provide a theoretical perspective on the error of the OKRidge method under Gaussian assumption. Extending to general conditions like non-Gaussian distributions is beyond the scope of this paper.\n\nFor non-Gaussian settings, we can utilize Fisher transformation, Box-Cox transformation, or inversion sampling to transform non-Gaussian distribution to Gaussian distribution. We will generalize the input to non-Gaussian distributions in our future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Additional experiments on the variations about the sparsity level and noise distribution can be seen in following pdf.

Meta-review: This paper considers a $k$-sparse linear regression model where the number of active (non-zero) coefficients is bounded by the constant $k$. The basic solution method is framed as ridge regression with the $\ell_0$ constraint. As it is NP-hard, one approach for scalable estimation is to consider a lower bound to the the objective function, as adopted in the OKRidge paper (Liu et al., NeurIPS). The contributions of this paper are theoretical (i.e., to provide theoretical justifications for OKRidge) and include the following: (i) a proposal of another novel tight lower bound to the NP-hard objective function, using the Convex Gaussian min-max theorem (CCMT);(ii) asymptotic analysis of the estimation error of OKRidge. This paper provides valuable contributions to the literature and potentially helps the practitioners to use OKRidge in large-scale applications. Throughout the author-reviewer discussion period, there were relatively active discussions and it would strengthen the paper substantially if the authors revise the paper accordingly. In addtion, the following aspects might be useful: (i) to make this paper self-contrained, it might be useful to provide a complete algorithm of OKRidge, including how to choose hyper-parameters; (ii) to streamline the exposition in sections 5.1 and 5.2 to help the readers; (iii) to more fully discuss the implications of the theoretical findings.
Decision: Accept (poster)