The Reliability of OKRidge Method in Solving Sparse Ridge Regression Problems

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.