The Reliability of OKRidge Method in Solving Sparse Ridge Regression Problems

Authors: xiyuan  li
youjun  wang
weiwei  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 10:22:45

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.

Main paper: 
 introduction: 
 Sparse Ridge Regression (SRR) has achieved notable success across various machine learning applications, including statistics [2] , signal processing [3] , dynamical systems [4, 5] , and others. In this paper, we are interested in addressing the following k-sparse linear regression problem with additive noise:EQUATIONwhere β β β * ∈ R d represents the "true" weight parameter, X X X = (x x x 1 , x x x 2 , • • • , x x x n ) ⊤ ∈ R n×d is the input measurement matrix, y y y = (y 1 , y 2 ,• • • , y n ) ⊤ ∈ R n is the real output responses, ϵ ϵ ϵ = (ϵ 1 , ϵ 2 , • • • , ϵ n ) ⊤ ∈R n is the noise vector, k ∈ Z + specifies the maximum number of nonzero elements for the model, ∥ • ∥ 0 denotes the number of nonzero elements of the given vector. Moreover, the entries of X X X are drawn i.i.d. from N (0, 1); the entries of ϵ ϵ ϵ are drawn i.i.d. from N (0, σ 2 ); and we assume k d is a constant and lim d→∞ n(d) d = δ ∈ (0, 1). The formulation (1) represents a black box model where β β β * is fixed. Given X X X and y y y, to determine the target vector β β β * , the most basic method is solving the following k-Sparse Ridge Regression Optimization (k-SRO), as outlined by [1, 6, 7] :EQUATIONwhere λ > 0 is a regularizer parameter, and ∥ • ∥ 2 denotes the Euclidean norm. Our paper focuses on the worst-case scenario ∥β β β * ∥ 0 = k. This k-SRO is different from the traditional ridge regression due to the constraint of k-sparse structure for β β β. The k-SRO problem (2) is NP-hard, and is more challenging in the presence of highly correlated features [8] .Two main types of algorithms are commonly employed for solving k-SRO problem (2): heuristic algorithms [9, 10] and optimal algorithms [11] . 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, [1] introduces a highly efficient method called OKRidge. Therefore, a complete algorithm of OKRidge, including how to choose hyper-parameters can be seen in the original paper [1] . OKRidge substitutes k-SRO problem (2) with an unconstrained optimization on a novel tight lower bound. The experiment results in [1] show that OKRidge is superior to heuristic algorithms, optimal algorithms, and existing mixed-integer programming (MIP) formulations solved by the commercial solver Gurobi. Nevertheless, the absence of theoretical error analysis for OKRidge impedes its scalability in practical applications.In this paper, we provide theoretical error analysis for OKRidge utilizing the framework of the CGMT [12] . Specifically, we propose another novel tight lower bound L OKRidge (β β β) to replace k-SRO problem (2):EQUATIONwhere ⊙ denotes Hadamard product, and SumTop k (•) represents the summation of the largest k elements of a given vector. The tight lower bound (3) is equivalent to that proposed by [1] . Thus, L OKRidge (β β β) can replace the objective function of OKRidge. It is noteworthy that our proposed regularizer, defined as γ(β β β) = SumTop k (β β β ⊙ β β β), differs from any previously proposed instances by [12] . Then, the optimal solution obtained by OKRidge isEQUATION[1] utilizes β β β as the estimate of β β β * in problem (1) . By combining formulations (1) and ( 3), the estimation error of OKRidge can be obtained through the following normalized optimization problem:EQUATIONwhere w w w := β β β -β β β * is a random variable with randomness from the random variables X X X and ϵ ϵ ϵ, and the estimation error can be measured by ∥w w w∥ 2 . Subsequently, we transform the optimization (5) into a PO problem about the error of OKRidge, using the Fenchel-Moreau theorem [13] . Then, we employ the CGMT framework to substitute the complex PO problem with a 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:EQUATIONwhere NSE := ∥ β β β -β β β * ∥ 2 2 σ 2 , and ∆( λ) is a function of λ. These theoretical results indicate that if the regularizer parameter λ used in OKRidge is constant, the NSE limit of OKRidge is also fixed. Moreover, β β β learned by OKRidge is reliable to estimate β β β * , due to lim d→∞ lim σ→0 ∥ β β β -β β β * ∥ 2 P -→ 0. The comprehensive experiments of OKRidge on real-world examples were conducted by the NeurIPS 2023 paper [1] (see Figure 3 and Appendix H in [1] ), which demonstrates that the error of OKRidge tends to zero. Our analysis explains the experimental phenomenon observed in [1] , strengthens the theoretical underpinnings of 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 a fixed constant determined by λ, aligning excellently with our theoretical predictions.The structure of the remaining sections in this paper is as follows. Section 2 provides a review of related work. Section 3 offers background information on OKRidge, CGMT, and basic concepts. Section 4 introduces an alternative tight lower bound for the objective function of OKRidge. In Section 5, we convert the estimation error of OKRidge into a PO problem and simplify it into an AO problem using CGMT. Subsequently, an estimation error analysis of OKRidge based on the AO problem is conducted. Section 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 2 Related work 
heuristic and optimal methods: 
 Heuristic methods approximate solutions to optimization problems based on practical experience [14] , including ensemble methods [15] , swapping features [16] , 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 [18] , the conditional-valueat-risk (CVaR) approach [19] , big-M free mixed integer second order conic (MISOC) method [19] , and so on. However, exact optimal methods are slow, particularly for large instances, to achieve near-optimality [20, 21] . To address the limitations of heuristic and optimal methods, [1] proposes an efficient approximation algorithm, OKRidge. Experimental results in [1] demonstrate that OKRidge outperforms heuristic algorithms, optimal algorithms, and existing MIP formulations solved by the commercial solver Gurobi.Lower bound methods are capable of solving the NP-hard k-SRO problems. Several algorithms utilize the lower bound method, such as SOS1 formulation [18] , big-M formulation [18] , Subset Selection CIO method [22] , and others. However, the SOS1 formulation lacks scalability in high dimensions, the big-M formulation is sensitive to hyperparameters, and the Subset Selection CIO method runs slowly. Recently, the perspective formulation [6, 23, 24] has been employed to induce a convex relaxed lower bound that is easier to solve. Building upon the perspective formulation, [1] proposes a novel lower bound used as the objective function for the OKRidge method.NSE, defined as ∥ β β β -β β β * ∥ 2 2 σ 2, serves as a natural measure of the estimation error. NSE is an important indicator in signal-to-noise ratio scenes [25, 26] . 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 X X and utilize the Approximate Message Passing (AMP) framework for analysis [30, 31] . These achievements motivate us to utilize NSE for evaluating the estimation error of the OKRidge method.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Our paper explicitly acknowledges the dependency on Gaussian inputs as a limitation, prompting further investigation into its applicability to non-Gaussian contexts.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
relaxed transformation of k-sro: 
 According to [1] , the k-SRO problem (2) can be reformulated as the following optimization problem:EQUATIONwherez z z = (z 1 , z 2 , • • • , z n ) ⊤ ∈ R d , and L ridge (β β β) := ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1 β 2 j .This problem (7) remains NP-hard under the sparsity constraint [32] . Existing methods such as SOS1, big-M, or 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] , [1] transforms the problem (7) to a new perspective optimization problem:EQUATIONwherec c c = (c 1 , c 2 , • • • , c n ) ∈ R d , and L Fenchel ridge (β β β, z z z, c c c) := ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1 (β j c j - c 2 j 4 z j). This transformation does not change the optimal solution of the problem (7) [1, 35] , indicating that problem (7) can be replaced by problem (8) . To efficiently solve problem (8), [1] further relaxs the binary constraint {0, 1} to the interval [0, 1], ultimately yielding the following relaxed convex optimization problem:EQUATIONAccording to problem (7) , to preserve the special sparse structure of β β β, we always have β j = 0 if z j = 0. Directly solving the min-max problem ( 9) is computationally challenging. [1] utilizes the relaxed problem (9) to obtain a tight lower bound for the problem (8) , where the lower bound corresponds to the objective function of OKRidge.The CGMT framework, introduced by [28] , has been utilized to analyze the performance of solutions to non-smooth regularized convex optimization problems. It 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 to analyze the NSE of the OKRidge method.CGMT originates from Gordon's Gaussian Min-max Theorem (GMT) [40] , which provides probabilistic bounds on the optimal cost of PO problem via a simpler AO problem. CGMT further tightens the bounds under convexity assumptions. According to GMT, [41] introduces the following asymptotic sequence and notation.Definition 3.1 (GMT admissible sequence). The sequence G G G (d) , g g g (d) , h h h (d) , Sw w w , SEQUATIONEQUATIONw w w and S (d) u u u are compact sets and ψ (d) is continuous on its domain. Onwards, we will drop the superscript (d) from G G G (d) , g g g (d) , h h h (d) .A sequence G G G (d) , g g g (d) , h h h (d) , S (d) w w w , S (d) u u u , ψ (d) d∈N defines a sequence of min-max problemsEQUATIONEQUATIONImportantly, the formulation (10) is called Primary Optimization (PO) and the formulation (11) is called Auxiliary Optimization (AO). Additionally, let w w wΦ (G G G) denote the optimal minimizer of PO problem (10) , and w w w (d) ϕ (g g g, h h h) denote the optimal minimizer of AO problem (11) . DefineEQUATIONClearly, ϕ (d) (g g g, h h h) := min w w w∈S (d) w w w υ (d) (w w w; g g g, h h h). For a sequence of random variables {X (d) } d∈N and a constant c ∈ R, X (d) P -→ c denotes convergence in probability, i.e. ∀ϵ > 0, lim d→∞ P |X (d) -c| > ϵ = 0. Based on the GMT admissible sequence and the notation introduced above, we present the CGMT below. Theorem 3.2 (CGMT [12] ). Let G G G (d) , g g g (d) , h h h (d) , S (d)w w w , S (d) u u u , ψ (d)d∈N be a GMT admissible sequence as in Definition 3.1, for which additionally the entries of G G G, g g g, h h h are drawn i.i.d. from N (0, 1). Let Φ (d) (G G G), ϕ (d) (g g g, h h h) be the optimal costs, and, w w w ϕ (g g g, h h h) the corresponding optimal minimizers of the PO and AO problems in (10) and (11) . The following three statements hold (i) For any d ∈ N and c ∈ R, u u u , then, for any µ ∈ R and t > 0,P Φ (d) (G G G) < c ≤ 2P ϕ (d) (g g g, h h h) ≤ c .P |Φ (d) (G G G) -µ|) > t ≤ 2P |ϕ (d) (g g g, h h h) -µ|) > t .(iii) Assume the conditions of (ii) hold for all d ∈ N. Let ∥ • ∥ denote some norm in R d and recall (12) . If, there exist constants (independent of d) κ * , α * and τ > 0 such that (a) ϕ (d) (g g g, h h h)EQUATION)Theorem 3.2 indicates that, if the optimal cost ϕ(g g g, h h h) of ( 11) concentrates to some value µ, the same holds true for Φ(G G G) of (10) . Furthermore, under appropriate additional assumptions, the optimal solutions of the AO and PO problems are also closely related by ∥w w w Φ (G G G)∥ = ∥w w w ϕ (g g g, h h h)∥, as n → ∞. This suggests that, within the CGMT framework, a challenging PO problem can be replaced with a simplified AO problem, from which the optimal solution of the PO problem can be accurately inferred [12] . Subsequently, we rewrite the lower bound of problem (9) in the form of PO problem (10) and analyze the minimizer of the simplified AO problem instead.Suppose f :R d → R and u u u, v v v ∈ R d , the Fenchel conjugate of f is defined as f * (u u u) = sup v v v v v v ⊤ u u u - f (v v v).Additionally, f * is always convex and lower semi-continuous. According to the Fenchel-Moreau theorem [13] , if f is convex and continuous, we havef (v v v) = sup u u u u u u ⊤ v v v -f * (u u u).In this paper, we utilize the following conjugate pairsEQUATION) If γ(•) : R d → R is a convex function of β β β, the subdifferential of γ(•) at β β β * is the set of vectors: ∂γ(β β β * ) = {s s s ∈ R d γ(β β β * + u u u) ≥ γ(β β β * ) + s s s ⊤ u u u}. According to [13], ∂γ(β β β * ) is nonempty, convex and compact. Given h h h ∈ R d , we define dist(h h h, ∂γ(β β β * )) = min s s s∈∂γ(β β β * ) ∥h h h -s s s∥ 2 .Then, the Gaussian squared distance corresponding to the scaled subdifferential is defined as D(τ) := D ∂γ(β β β * ) (τ ) := E h h h dist 2 (h h h, τ ∂γ(β β β * )) , where τ > 0. Suppose C(τ ) = -τ 2 ∂D(τ ) ∂τ , lim d→∞ n d → δ ∈ (0, 1), lim d→∞ D(τ ) n → D(τ ) ∈ (0, 1), lim d→∞ C(τ ) n → C(τ ).Based on the Gaussian squared distance, we define a map function:EQUATION)We denote λ map as the solution of map(τ ) -λ/2 = 0. Since map(τ ) depends on γ(•) and β β β * , when the form of γ(•) and the value of β β β * are determined, the λ map is fixed.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to 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 [1] , which is open. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
tight lower bound in okridge: 
 In this section, we utilize problem (9) to derive another novel lower bound for problem (8) , serving as used as the objective function of OKRidge. Our lower bound is equivalent to the tight lower bound provided by [1] . Specifically, [1] eliminates the parameter c c c in problem ( 9) by setting the gradient of β β β to 0, while we eliminate the parameter c c c by setting the gradient of c c c to 0. These two methods are equivalent due to the independence and convexity of c c c and β β β. Given any β β β and z z z, the optimality condition for c c c in problem ( 9) is taking ∂L Fenchel ridge (β β β, z z z, c c c)/∂c c c = 0 0 0. Therefore, we haveEQUATIONEQUATIONwhere diag(z z z) is a diagonal matrix with z z z on the diagonal. Inspired by this optimality condition, we present the following theorem.Theorem 4.1. If we define the parameter c c c as ( 16), the problem ( 9) is equivalent to the following optimization problem:EQUATIONwhereEQUATION)The proof of Theorem 4.1 follows Theorem 3.1 of [1] and is included in Appendix B for completeness. Following the approach by [1] , we can approximately solve the problem (18) while still obtaining a feasible lower bound. We define a new function L(β β β) as:EQUATIONFor any β β β, L(β β β) serves as a valid lower bound for problem (7) . We should choose z z z such that this lower bound L(β β β) is tight.Theorem 4.2. The function L(β β β) defined in Equation ( 20) is lower bounded byEQUATION)where ⊙ is Hadamard product, and SumTop k (•) denotes the summation of the largest k elements of a given vector.The proof of Theorem 4.2 can be seen in Appendix C. Based on ( 9), ( 18) and ( 20), the tight lower bound ( 21) is equivalent to the one provided by [1] , as both are derived through equivalent processes.OKRidge solves the original k-sparse problem (7) using this tight lower bound (21) as its objective function. If we defineEQUATIONwhere we obtain L OKRidge of formulation (3) . So far, we transform the constrained k-SRO problem (2) into the unconstrained optimization problem (22) . Letβ β β = argmin β β β L OKRidge (β β β),OKRidge regards β β β as the estimation of β β β * in problem (1) . Next, we apply CGMT to analyze the error ∥ β β β -β β β * ∥ 2 2 for OKRidge.5 The Error Analysis for OKRidge 
from po to ao: 
 As discussed in Section 4, the estimation error of OKRidge is characterized by∥ β β β -β β β * ∥ 2 2 .Taking formulation (1) into the properly normalized objective (22) , OKRidge (22) can be equivalently transformed to the following optimization:EQUATIONThe crucial step is to convert (23) into a PO problem within the framework of CGMT. We introduce the new variable w w w := β β β -β β β * and apply the Fenchel-Moreau theorem (14) to formulation (23) ,EQUATIONwhere w w w ∈ R d , u u u ∈ R n . Based on ( 10) and ( 24), the PO problem corresponding to the estimation error of OKRidge isEQUATIONwhereEQUATIONSince the entries of X X X are drawn i.i.d. from N (0, 1), to replace the challenging PO problem (25) with a simplified AO problem through CGMT, ψ(w w w, u u u) should be a convex-concave function. The following Lemma illustrates that the ψ(w w w, u u u) satisfies the conditions of Theorem 3.2. Lemma 5.1. Suppose ψ(w w w, u u u) is defined as in formulation (26) . Then, ψ(w w w, u u u) is convex-concave function.The proof of Lemma 5.1 can be seen in Appendix D. Defineγ(β β β) := SumTop k (β β β ⊙ β β β).Because the PO problem (25) satisfies the assumptions of CGMT, we transform it to the following AO problem:EQUATIONwhere the entries g g g, h h h are drawn i.i.d. from N (0, 1), due to the property of X X X. Suppose w w w ΦOKRidge is the of optimal solutions of the PO problem (25) , and w w w ϕOKRidge is the optimal solutions of the AO In this chapter, we simplify the AO problem (27) into ones involving only scalar quantities. Since γ(β β β) is a convex (see Lemma 5.1), ∂γ(β β β * ) is nonempty, convex and compact. According to [13, Theorem 23 .4], we have γ(β β β * + w w w) = γ(β β β * ) + max s s s∈∂γ(β β β * ) s s s ⊤ w w w + O(∥w w w∥ 2 2 ). The first-order approximation of γ(β β β) around the vector of interestEQUATION)where β β β = β β β * + w w w. Then, following the approach from [12] , the AO problem ( 27) can be simplified by the first-order approximation (28) :EQUATIONSuppose f (β β β) and f (β β β) denote the objective functions of the original and the approximated AO problems ( 27) and ( 29), respectively,f (β β β) =(∥w w w∥ 2 g g g -ϵ ϵ ϵ) ⊤ u u u + ∥u u u∥ 2 h h h ⊤ w w w - ∥u u u∥ 2 2 4 + λγ(β β β * + w w w), f (β β β) =(∥w w w∥ 2 g g g -ϵ ϵ ϵ) ⊤ u u u + ∥u u u∥ 2 h h h ⊤ w w w - ∥u u u∥ 2 2 4 + λ γ(β β β * ) + max s s s∈∂γ(β β β * )s s s ⊤ w w w .Then, based on (28), we haveEQUATIONCompared with AO problem ( 27), the approximated AO problem ( 29) is tight when ∥β β β -β β β * ∥ 2 → 0, and we later demonstrate that this condition is satisfied as σ 2 → 0, independent of the original AO problem (27) . This fact allows us to translate the analysis on the optimal solution w w w φOKRidge of the approximated AO problem (29) to the analysis on the optimal solution w w w ϕOKRidge of the corresponding original AO problem (27) . Because γ(β β β * ) is a constant, the approximated AO problem ( 29) is equivalent to the following optimization problem:EQUATIONwhere we have approximated γ in the first order. Since ϵ ϵ ϵ ∼ N (0, σ 2 I I I), the term ∥w w w∥ 2 g g g -ϵ ϵ ϵ above is statistically identical to a random vector with entries drawn i.i.d. from N (0, ∥w w w∥ 2 2 + σ 2 ), where I I I is the unit matrix. Following the method used by [42] , we substitute the first term in the objective (31) with ∥w w w∥ 2 2 + σ 2 g g g ⊤ u u u. Then, we obtain:EQUATIONLet η = ∥u u u∥ 2 . Since max ∥u u u∥2=η g g g ⊤ u u u = ∥g g g∥ 2 • ∥u u u∥ 2 and h h h ∼ N (0, I I I), in term of mathematical expectation, the optimization (32) can be equivalently expressed as:EQUATIONThe objective (33) is strongly convex in w w w and (jointly) concave in η, s s s, 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 α = ∥w w w∥ 2 . Since min ∥w w w∥2=α (-h h h + λ η s s s) ⊤ w w w = -α∥h h h -λ η s s s∥ 2 , the optimization (33) can be equivalently reformulated as:EQUATIONNext, we further reverse the order of min-max, as the objective (34) exhibits the desired concaveconvex structure. Then, we proceed to maximize over s s s ∈ ∂γ(β β β * ). Since min s s s∈∂γ(β β β * ) ∥h h h -λ η s s s∥ 2 = dist h h h, λ η ∂γ(β β β * ) , the optimization problem (34) can alternatively be formulated as:EQUATIONBecause both the random components ∥g g g∥ n . Then, the optimal minimizer of (35) converges to the optimal minimizer of the following deterministic optimization in probability [44] :EQUATIONHere, we complete the simplifications by reducing the AO problem (27) to an equivalent optimization (36) that now only involves two scalar variables: α and η.Based on the analysis above, if the optimal solution of optimization ( 36) is α = α * , we have ∥w w w φOKRidge ∥ 2 P -→ α * for approximated AO problem (29) . If α * further tends to 0, according to formulation (30) and CGMT, ∥w w w ΦOKRidge ∥ 2 P -→ α * holds for PO problem (25) . Then, for the estimation error of OKRidge produced by (22) , we have∥ β β β -β β β * ∥ 2 P -→ α * .Therefore, it only remains to obtain the optimal value of α in optimization (36) that plays the role of ∥w w w∥ 2 . Following [45] , we conclude the estimation error of OKRidge with Theorem 5.2 below. Theorem 5.2. Suppose β β β * is the true weight parameter of the problem (1), β β β is the optimal solution to the objective function (22) of OKRidge, D(τ) n → D(τ ) ∈ (0, 1), aNSE := lim σ 2 →0 NSE = lim σ 2 →0 ∥ β β β -β β β * ∥ 2 2 σ 2 .Define λ map is the solution of map(τ ) = 0 for τ > 0, then, the estimation error of OKRidge is given by the following probability limit:EQUATIONwhere ∆( λ) = D( λ) 1-D( λ) , and λ = λ map .The proof of Theorem 5.2 can be seen in Appendix E. Remark 5.3. In the objective (24) concerning estimation error of OKRidge, γ(β β β) = SumTop k (β β β ⊙ β β β)and the value of β β β * is assumed to be known. Then, the analysis on map(•) in Section 3.3 reveals that the form of map(•) and the value of λ map are fixed. Thus, ∆( λ) is a function of λ. In other words, if the regularizer parameter λ of OKRidge is fixed, the NSE limit of OKRidge ∆( λ) is also fixed. Additionally, Theorem 5.2 also indicates that lim d→∞ lim σ→0 ∥ β β β -β β β * ∥ 2 P -→ 0, which guarantees the effectiveness of β β β learned by OKRidge in accurately estimating β β β * . These results substantiate the theoretical reliability of OKRidge and promote its broad application in the real world. 
numerical experiments: 
 In this section, we conduct experiments to verify Theorem 5.2. The experiments contain two aspects: (i) When λ is fixed, NSE tends to a fixed constant as σ → 0. (ii) When σ → 0, NSE is determined by the weight λ of the regularizer. In other words, NSE is a function of λ.In our experiments, β β β * is randomly generated with ∥β β β * ∥ 0 ≤ k. For i ∈ {1, 2, • • • , n}, x x x i is drawn i.i.d. from N (0, I I I), and ϵ i is drawn i.i.d. from N (0, σ 2 ). According to the k-sparse linear regression (1) , Here, λ best is the optimal weight of the regularizer.y i = x x x ⊤ i β β β * + ϵ i , we get dataset (x x x i , y i ) with i = 1, 2, • • • , n.We investigate the change of NSE with 1/σ under λ = 1, 5, 10, λ best , • • • . The results are illustrated in Figure 1 . As depicted in Figure 1 , when λ is constant, NSE converges to a fixed value as σ → 0. This observation validates aspect (i) of Theorem 5.2.We analyze the change of NSE with λ under σ 2 = 1, 0.1, 0.01, 0.001. The outcomes are 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 λ. This observation confirms aspect (ii) of Theorem 5.2. 
conclusion: 
 In this paper, we present a 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 x x x ∼ N (0, I I I), ϵ ∼ N (0, σ 2 ), and lim d→∞ n d = δ ∈ (0, 1), we havelim d→∞ lim σ 2 →0 ∥ β β β -β β β * ∥ 2 2 σ 2 P -→ ∆( λ), and lim d→∞ lim σ→0 ∥ β β β -β β β * ∥ 2 P -→ 0.where ∆( λ) depends on λ. This indicates that (i) the NSE limit of OKRidge remains constant when λ is fixed; (ii) β β β learned by OKRidge is effective in estimating β β β * . 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. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: Our paper focuses on 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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Our paper properly credits the original creators of the OKRidge algorithm and adheres to the licensing terms of the cited open resources required by NeurIPS paper [1] .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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?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/code/model as part of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)?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 crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 an equivalent approval/review based on 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 crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between 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. 
 
 Appendix: Limitaion: 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 the potential extensions of our findings to non-Gaussian input settings, providing insights into the universality of the results.Impact: Our work provides theoretical support for the broad application of OKRidge, which does not require proprietary software or expensive licenses [1] , unlike its main competitor. This can significantly impact various regression applications.Theorem 4.1. If we define the parameter c c c as ( 16), the problem ( 9) is equivalent to the following saddle point optimization problem:EQUATIONwhereEQUATIONProof. The problem ( 9) is The parameter c c c in ( 16) isc j = ρ ∈ R , if z j = 0, 2βj zj , if z j ̸ = 0.Substitute parameter c c c of ( 16) into (9),L Fenchel ridge (β β β, z z z, c c c) = ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1 (β j c j - c 2 j 4 z j ) = ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1,zj ̸ =0 β j • 2β j z j -( 2β j z j ) 2 4 • z j = ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1,zj ̸ =0 2β 2 j z j - β 2 j z j = ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1,zj ̸ =0 2β 2 j z j Define L saddle ridge (β β β, z z z) := ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1,zj ̸ =0 β 2 j z j .Then, the problem ( 9) can be equivalently written asmin β β β,z z z L saddle ridge (β β β, z z z) s.t. d j=1 z j ≤ k, z j ∈ [0, 1],which is our saddle point optimization (38) .C Proof of Theorem 4.2Theorem 4.2. The function L(β β β) defined in Equation ( 20) is lower bounded byEQUATION)where ⊙ is Hadamard product, and SumTop k (•) denotes the summation of the largest k elements of a given vector.Proof. The Equation ( 20) isL(β β β) = min z z z L saddle ridge (β β β, z z z), s.t. d j=1 z j ≤ k, z j ∈ [0, 1].According to (20) and (39) ,EQUATIONFollowing the method of [1] , if we minimize z in the optimization (41) under the constraints p j=1 z j ≤ k and z j ∈ [0, 1] for ∀j, we have z j = 1 for the top k terms of β 2 j and z j = 0 otherwise. Then, we haveL(β β β) ≥ ∥y y y -X X Xβ β β∥ 2 2 + λ d j=1,zj ̸ =0 β 2 j 1 = ∥y y y -X X Xβ β β∥ 2 2 + λSumTop k (β β β ⊙ β β β).D Proof of Lemma 5.1Lemma 5.1. Suppose ψ(w w w, u u u) is defined as formulation (26) . Then, ψ(w w w, u u u) is convex-concave onR d × R n .Proof. Obviously, ψ(w w w, u u u) is concave about u u u. Next, we indicate that ψ(w w w, u u u) is convex about w w w.For any w w w, w w w ∈ R d and ∀θ ∈ (0, 1),[θ wj + (1 -θ) w j ] 2 ≤ θ w2 j + (1 -θ) w 2 j . Then, we have SumTop k [θ w w w + (1 -θ) w w w] ⊙ [θ w w w + (1 -θ) w w w] ≤SumTop k θ w w w ⊙ w w w + (1 -θ) w w w ⊙ w w w ≤SumTop k θ w w w ⊙ w w w + SumTop k (1 -θ) w w w ⊙ w w w ≤θSumTop k w w w ⊙ w w w + (1 -θ)SumTop k w w w ⊙ w w w .SumTop k (•) is a convex operator. Therefore, ψ(w w w, u u u) is concave about u u u and convex about w w w.Theorem 5.2. Suppose β β β * is the true weight parameter of the problem (1), β β β is the optimal solution to the objective function (22) of OKRidge, D(τ ) n → D(τ ) ∈ (0, 1),aNSE := lim σ 2 →0 NSE = lim σ 2 →0 ∥ β β β -β β β * ∥ 2 2 σ 2 .Define λ map is the solution of map(τ ) = 0 for τ > 0, then, the estimation error of OKRidge is given by the following probability limit:EQUATIONwhere ∆( λ) = D( λ) 1-D( λ) , and λ = λ map .Proof. Starting from the simplified AO problem (36), let's defineEQUATION)Given that κ(α, η) is strongly convex in α and concave in η, we denote (α * , η * ) as the Nash equilibrium of κ(α, η). Then, α * is unique and we use duality to compute α * . For any η,EQUATIONwhich is well-defined, due to 1 -D( λ η ) > 0. Substituting α * (η) back into (43) gives:κ(α * , η) = η α * 2 + σ 2 -α * η D( λ η ) -Γ(η) = η σ 2 D( λ η ) 1 -D( λ η ) + σ 2 -ση D( λ η ) 1 -D( λ η ) • D( λ η ) -Γ(η) = ησ 1 -D( λ η ) - ησ D( λ η ) 1 -D( λ η ) -Γ(η) = ησ 1 -D( λ η ) -Γ(η).Differentiating κ(α * , η) with respect to η, we haveEQUATION)Here, map(τ ) = 0 when τ = λ map . Hence, η * = λ λmap is the optimal solution, due to ∂κ(α * , η)∂η η=η * = σmap(λ map ) -lim n→∞ λ 2λ map √ n = 0.Because the form of γ(•) and the value of β β β * are determined, the form of map(•) and the value of λ map are fixed. In other words, λ map is a function about λ. Therefore, we can take η * = λ λmap to formulation (44) ,EQUATION)Based on the analysis above, if the optimal solution of optimization ( 36) is α = α * , we have ∥w w w φOKRidge ∥ 2 P -→ α * for approximated AO problem (29) . Furthermore, according to formulation (46), lim σ→0 α * = 0 occurs for the approximated AO problem (29) and is independent of the original AO problem (27) . Thus, formulation (30) holds:lim ∥β β β-β β β * ∥2→0 f (β β β) = f (β β β) ⇔ lim d→∞ lim σ→0 f (β β β) = f (β β β).(47)In the case n → ∞ and σ → 0, formulation (47) allows us to translate the optimal error α * of the approximated AO problem (29) to the optimal error of the original AO problem (27) . Combining formulations ( 46), (47), and CGMT, ∥w w w ΦOKRidge ∥ 2 P -→ α * holds for PO problem (25) . Then, for the estimation error of OKRidge produced by ( 22), we have∥ β β β -β β β * ∥ 2 P -→ α * .Therefore, combining PO problem (25) , AO problem ( 27), the relation (47), and the formulations ( 23) and ( 46), according to CGMT, we obtain::lim d→∞ lim σ→0 ∥ β β β -β β β * ∥ 2 /σ P -→ D( λ) 1 -D( λ) ⇒ lim d→∞ lim σ→0 ∥ β β β -β β β * ∥ 2 2 σ 2 P -→ D( λ) 1 -D( λ) .To sum up,lim d→0 aNSE P -→ ∆( λ),where ∆( λ) = D( λ) 1-D( λ) , and λ = λ map .All experiments were run on the 10x TensorEX TS2-673917-DPN Intel Xeon Gold 6226 Processor, 2.7Ghz. We set the memory limit to be 100GB.Figures F1 ∼ F7 (a) demonstrate that when λ is fixed, NSE converges to a constant as σ → 0. In Figures F1 ∼ F7 (b), the curves converge towards the real blue curve as σ → 0, with the real blue curve representing ∆( λ). These observation validate Theorem 5.2. 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 in 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 as long as it is clear that these goals are not attained by the paper. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
questions: questions: - Can the authors provide more insight into the practical applications where this theoretical error analysis will be most impactful?
- Are there any specific strategies proposed for extending the theoretical findings to non-Gaussian input settings?
- How robust are the experimental findings to variations in the underlying assumptions, such as the sparsity level and noise distribution?
limitations: limitations: The authors have addressed the limitations related to Gaussian input settings and indicated future work on extending the results to non-Gaussian settings.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

In Line 208, the LHS of (23) misses the \min_{\beta}.

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.

In Line 300, it is improper for the formulation to use “=”, as it should indicate an approximation in probability according to Theorem 5.2.
questions: questions: 1, What is the difference between GMT and CGMT and what are the advantages of CGMT over GMT?
2, Why can we reduce the problem (26) to (35) that only involves two scalar variables?
limitations: limitations: The author has presented the limitations in the checklist.
paper_summary: paper_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.
strength_weakness: strength_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:

> * 1.1 Mohsen Bayati and Andrea Montanari. The lasso risk for Gaussian matrices. Information Theory, IEEE Transactions on, 58(4):1997–2017, 2012

> * 1.2 D. Bertsimas, J. Pauphilet, and B. Van Parys. Sparse regression: Scalable algorithms and empirical performance. Statistical Science, 35(4):555–578, 2020

> *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.

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.
questions: questions: See the weaknesses.
limitations: limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Some areas where the presentation can be improved:
- Abstracts should not include references.
- 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. 
- Make clear that the estimation error in Equation 5 is a random variable, because X and \epsilon are random.
- Equation 5 is missing a \odot
- 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.
questions: 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?
2. In Line 56, why is it \Delta (\hat\lambda) and not \Delta (\lambda)?
limitations: limitations: None. This is a theory paper.
paper_summary: paper_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.
strength_weakness: strength_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. 

2. Theorem 5.2 demonstrates that $\hat{\lambda}=\lambda_{map}$. It would be more concise to substitute $\Delta(\hat{\lambda})$ with $\Delta(\lambda_{map})$.

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.
questions: 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: limitations: Yes, the authors have adequately addressed the limitations.

Comments: title: k is a function of d
k as a function of d?
Clarification once again
Appreciation for Raising Score
Kindly Requesting Confirmation on Responses
Appreciation for Your Continued Review and Feedback
Appreciation to Reviewer mn2F
Prompt response
comment: Thank you for your acknowledgment and effort.
Dear Reviewer mBVh:

We sincerely appreciate the time and effort you have invested in the discussion period. We sincerely apologize for our misunderstanding of the concepts of sparsity and $k$ in your Question 1. Your detailed explanation of Question 1 is valuable for us in addressing your concerns.

The linear model of our paper is
$$ \pmb{y}=\pmb{X} \pmb{\beta}^* + \pmb{\epsilon} \;\text{ with }\; \Vert\pmb{\beta}^* \Vert_0 \leq k, \tag{1}$$

where $\pmb{\beta}^*\in\mathbb{R}^d$ represents the ``true" weight parameter. We provide an upper $k$ to maintain consistency with the forms of the k-Sparse Ridge Regression Optimization (k-SRO): 
$$\mathop{\min}\limits_ {\pmb{\beta}}\Vert \pmb{y} - \pmb{X} \pmb{\beta}\Vert_ 2^2 + \lambda \Vert\pmb{\beta}\Vert_ 2^2,   \text{s.t.} \Vert\pmb{\beta} \Vert_ 0 \leq k. \tag{2}$$

Our paper addresses the worst-case scenario $\Vert\pmb{\beta}^* \Vert_0 = k$ for the linear model (1), we apologize for any inconvenience caused by our presentations and we will further clarify this in our revision.  

In our paper, $k$ is indeed a function of $d$, as we assume $\frac{D(\tau)}{n}\to \bar{D}(\tau)\in (0,1)$ as $d\to \infty$, where $D(\tau)$ is related to $k$ (see lines 253 and 266). Following your suggestion, we will further emphasize this in our revision. Under this assumption, $k(d)/d$ can be a constant. 

To illustrate the impact of sparsity value on our theoretical results, the sparsity value $k/d$ should be a constant once model (1) is selected, which means that $k$ changes proportionally with $d$. For ease of understanding, $k/d$ and $n/d$ can be regarded as the inherent attributes of model (1); they become known once model (1) is selected. For any given model (1), when we apply the OKRidge method to estimate $\pmb{\beta}^*$, under the assumption  $\frac{D(\tau)}{n}\to \bar{D}(\tau)\in (0,1)$, we arrive at the theoretical result
$$\lim_ {d\to \infty}\lim_ {\sigma\to 0}\text{NSE}\stackrel{P}{\longrightarrow}\Delta(\hat{\lambda}).\tag{6}$$  

In other words, our theoretical result (6) holds for any selected sparsity value $k/d$. This is why I assert that the sparsity value (i.e., the choice of model (1)) does not impact our theoretical results. This assertion does not imply that " When the sparsity is $k(d)=d$, the ridge regression problem can be solved exactly and there is no error for any value of $\lambda$", because our theoretical results only hold in probability for the linear model (1) under the conditions $\sigma\to 0$ and $d\to \infty$.


Based on the analysis above, once model (1) is selected, $\Delta(\hat{\lambda})$ depends on $\lambda$. This is not contradictory to the notion that $\Delta(\hat{\lambda})$ should depend on sparsity $k/d$, because $\Delta(\hat{\lambda})$ is also influenced by the selection of a model (1) which is determined by $k(d)$ and $n(d)$. However, since our paper assumes that model (1) has already been selected, the sparsity $k/d$ is a known constant, and therefore $\Delta(\hat{\lambda})$ depends on $\lambda$.


We would like to once again express our sincere gratitude for the time, effort, and careful consideration you have dedicated to our discussions.  Engaging with you has been invaluable for our growth. We hope our responses have met your expectations and satisfaction. We kindly request the opportunity to address any additional concerns you may have. Thank you for your time and attention to our work.  We are looking forward to your response soon.
Thanks for the author's reply, my concerns have been well answered. Thanks.
I do not understand your answer to Question 1.

Note that in reference [1] the optimization problem is given, but not the model. Of course, when you solve a concrete sparse ridge regression problem, then k should be fixed and, in the optimization problem, it is enough to use k as an upper bound on the sparsity, zero-norm of $\beta*$. But you specify a model that you are analyzing in a high-dimensional setting, where $\lim_{d\rightarrow \infty} \frac{n(d)}{d}$ converges to a constant. So, in any fixed dimension $d$, the true parameter vector should have a definite sparsity value $k(d)$. Therefore, in the specification of the model, the sparsity should be given by an equality, and not by an inequality. Moreover, such as $n$, the number of data points, the sparsity should be a function of $d$. Otherwise, $k$ would be a dimension-independent constant, which makes no sense to me.  What could make sense is that $\frac{k(d)}{d}$ is constant, and maybe that is your assumption. Actually, I would be very surprised if the sparsity value does not impact your theoretical analysis. When the sparsity is $k(d)=d$, then the ridge regression problem can be solved exactly and there is no error for any value of $\lambda$. So the function $\Delta (\lambda)$ should depend on $k(d)$.
Reviewer 8imU:

Can you please respond to the rebuttal as soon as possible? Your comments will be greatly appreciated. Many thanks,

AC
Dear Reviewer 553k:

Can you please respond to the rebuttal as soon as possible? Your comments will be greatly appreciated. Many thanks,

AC
Dear Reviewer 553k,

 We sincerely appreciate the time and effort you have invested in reviewing our paper. Your concerns center around the experimental results on real-world examples and the limitation of Gaussian settings.

(1). The comprehensive experiments of OKRidge on real-world examples were conducted by the NeurIPS 2023 paper [1] (see Figure 3 and Appendix H in [1]), which demonstrates that the error of OKRidge tends to zero. Our paper aims to offer a theoretical guarantee for this experimental phenomenon observed in [1]. Therefore, the experiments in [1] on real-world examples are adequate in validating the validity of our theorems, making it redundant to repeat these experiments to observe the same phenomenon again. 


(2). The Gaussian setting is a widely adopted framework for theoretical analysis of algorithms in machine learning, as evidenced by papers [B1~B8]. Consequently, our work offers a theoretical perspective on the error of the OKRidge method under Gaussian settings. We also acknowledge this Gaussian setting in our Limitations Section (see lines 391-397). According to NeurIPS official principles and NeurIPS Reviewer principles, our limitation should not be punished, where these principles are presented by following:

NeurIPS official principles emphsize: "The authors are encouraged to create a separate Limitations section in their paper. We understand that authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection. Reviewers will be specifically instructed to not penalize honesty concerning limitations." (see NeurIPS official website)

NeurIPS Reviewer principles emphsize:" Authors should be rewarded rather than punished for being upfront about the limitations of their work and any potential negative societal impact." (see the Limitations part of NeurIPS Reviewer operation panel)

Thank you once again for your consideration and assistance. We understand that you have other commitments, and we apologize for any disruption this follow-up may cause. Since there are only a few days left in the discussion period, your timely feedback would be greatly valued and essential to our process. We look forward to hearing from you soon.


[1] Okridge: Scalable optimal k-sparse ridge regression for learning dynamical systems. In NeurIPS, 2023.
We sincerely thank you for recognizing our work and raising our score.
Dear Reviewer mBVh,

Thank you for rechecking our paper and your prompt response. We apologize for any inconvenience caused by our initial presentation. To this end, following your comments, we will correct our work in the revision.

In regards to your Questions

__Question 1.__ The problem addressed in the paper should be well explained and in your case, the model (Equation 1) should be justified and limitations of the model should be discussed. For instance, for fixed dimension d, the sparsity should also be a fixed value if \beta^* is the true weight parameter. Why do you only provide an upper k? When specifying the model, you do not say how k changes with d?

__Answer:__ 
We appreciate your comment. As you referenced [1], "OKRidge: Scalable Optimal k-Sparse Ridge Regression," [1] focuses on solving the following k-Sparse Ridge Regression Optimization (k-SRO):

$$\mathop{\min}\limits_ {\pmb{\beta}}\Vert \pmb{y} - \pmb{X} \pmb{\beta}\Vert_ 2^2 + \lambda \Vert\pmb{\beta}\Vert_ 2^2,   \text{s.t.} \Vert\pmb{\beta} \Vert_ 0 \leq k,$$

where [1] only provides an upper bound k for sparsity. To maintain consistency with [1], we also provide an upper bound k for sparsity of the model (Equation 1).

Furthermore, our paper also argues that sparsity is inherently a fixed value when $\beta^*$ is the true weight parameter. It is worth emphasizing that, regardless of the value of sparsity, it does not impact our theoretical results. Therefore, it is unnecessary to discuss how k changes.

__Question 2.__ I also checked reference [1] "OKRidge: Scalable Optimal k-Sparse Ridge Regression", which is, in my opinion, much more accessible. In reference [1] the matrix X is not restricted to a matrix with random entries. Such matrices are only used in the experimental section of reference [1]. So I am not sure how general your error analysis is.

__Answer:__ 
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 estimation error of the OKRidge method under Gaussian settings.

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, the matrix X in our paper is restricted to Gaussian assumption. Reviewer 8imU also mentions this limitation but acknowledges our contribution under Gaussian settings. Extending our analysis to general conditions is beyond the scope of this paper and we will investigate the error of OKRidge under general conditions in our future work.

__Question 3.__ The nine-page version of your paper does not contain proofs of your results, but the whole Page 4 is spent on the formal definition of GMT admissible sequences and a restatement of a theorem from reference [11]. However, the formal results are not needed to gain an informal understanding of your results.

__Answer:__ 
Our proofs are detailed in Appendix B~E (see lines 398-450). We have also indicated where the proofs for the key steps are located in the original paper. Additionally, the formal definition of GMT admissible sequences and the CGMT theorem from reference [11] are crucial for the derivations that follow in our manuscript. Therefore, it is important to introduce these definitions. In response to your advice, we will simplify these contents of Page 4 in our revision.

Given the need for formality, rigor, and accuracy in theoretical work, it is necessary for our purely theoretical paper to provide the formal results. The informal understanding of our results is discussed in our remark 5.3 and conclusion (see lines 270-277 and 297-304).

Most of your concerns pertain to our presentation, which do not impact the validity of our theoretical results. We hope our responses address your concerns and positively influence your evaluation. We are looking forward to hearing from you soon.


[B1] Explicit Regularisation in Gaussian Noise Injections. NeurIPS 2020

[B2] Communication-Constrained Bandits under Additive Gaussian Noise. ICML 2023

[B3] Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise. COLT 2024

[B4] Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections. ICML 2021

[B5] Pitfalls of Gaussians as a noise distribution in NCE. ICLR 2023

[B6] Precise Error Analysis of Regularized M-Estimators in High Dimensions. IEEE Trans. Inf. Theory. 2018

[B7] On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions. NeurIPS 2023

[B8] Hyperbolic VAE via Latent Gaussian Distributions. NeurIPS 2023
I read your paper again and still cannot recommend its acceptance. 

I still find your paper inaccessible. In my opinion, for a premier conference such as NeuRIPS, it is your responsibility to make your results accessible. Since NeuRIPS does not include a revision cycle, the submitted version of the paper must already be of high quality.

* The problem addressed in the paper should be well explained and in your case, the model (Equation 1) should be justified and limitations of the model should be discussed. For instance, for fixed dimension d, the sparsity should also be a fixed value if \beta^* is the true weight parameter. Why do you only provide an upper k? When specifying the model, you do not say how k changes with d?  

* I also checked reference [1] "OKRidge: Scalable Optimal k-Sparse Ridge Regression", which is, in my opinion, much more accessible. In reference [1] the matrix X is not restricted to a matrix with random entries.  Such matrices are only used in the experimental section of reference [1]. So I am not sure how general your error analysis is.  

* The nine-page version of your paper does not contain proofs of your results, but the whole Page 4 is spent on the formal definition of GMT admissible sequences and a restatement of a theorem from reference [11]. However, the formal results are not needed to gain an informal understanding of your results.   


I am not going to change my score, but I am happy to defer the decision to an area chair.
Dear Reviewer 553k,

We hope this message finds you well. I am writing to kindly follow up on our previous correspondence and to request your feedback regarding whether our responses have adequately addressed your concerns. We sincerely appreciate the time and effort you have invested in reviewing our paper.

We understand that you have other commitments, and we apologize for any inconvenience this follow-up may cause. Your timely feedback would be greatly valued and is essential for us to move forward.

Thank you once again for your consideration and assistance. We look forward to hearing from you soon.

Best regards!
Dear Reviewer mBVh,

Thank you very much for taking the time to review my paper and for your thoughtful consideration. I understand that it may require additional effort on your part, and I truly appreciate your dedication to providing feedback. We hope that our responses have met your expectations and addressed your concerns. Please do not hesitate to reach out if you have any further questions or need any additional information from me. I am looking forward to discussing with you.

I apologize for any inconvenience caused by rechecking our paper, and I sincerely thank you once again for your time and effort.

Best regards!
It has been a while since I read your paper. I will check it again and come back to you tomorrow.
Thank you very much for your acknowledgment and efforts.
Thanks for the clarification, I'll update my score.
Thanks to the authors for the detailed responses. You have solved most of my problems, thanks.
Dear Reviewer mBVh,

We hope this message finds you well. I am reaching out to kindly request your prompt response to confirm whether our responses adequately address your queries. We sincerely thank you for your time and effort during this discussion period. Your timely feedback is greatly appreciated.