Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees
Authors: Yingzhen Yang
Ping Li
Venue: ICLR 2025 Poster (2025)
Keywords: Sketching
Random Projection
Minimax Rates
Primary area: learning theory
TL;DR: We present novel theoretical results for the approximation error between the optimization results of the original problem and the sketched problem for regularized least square problems with sharp guarantees.

Abstract: Randomized algorithms play a crucial role in efficiently solving large-scale optimization problems. In this paper, we introduce Sketching for Regularized Optimization (SRO), a fast sketching algorithm designed for least squares problems with convex or nonconvex regularization. SRO operates by first creating a sketch of the original data matrix and then solving the sketched problem. We establish minimax optimal rates for sparse signal estimation by addressing the sketched sparse convex and nonconvex learning problems. Furthermore, we propose a novel Iterative SRO algorithm, which reduces the approximation error geometrically for sketched convex regularized problems. To the best of our knowledge, this work is among the first to provide a unified theoretical framework demonstrating minimax rates for convex and nonconvex sparse learning problems via sketching. Experimental results validate the efficiency and effectiveness of both the SRO and Iterative SRO algorithms.

Published as a conference paper at ICLR 2025
SKETCHING FOR CONVEX AND NONCONVEX REGU- LARIZED LEAST SQUARES WITH SHARP GUARANTEES
Yingzhen Yang
Ping Li
School of Computing and Augmented Intelligence Arizona State University, Tempe, AZ 85281, USA yi yingzhen. wargghhen.yanggasus... yang@asu.edu
VecML Inc., Bellevue, WA 98004, USA pingli www.lmmmmmm..oooommm..m......o
ABSTRACT
Randomized algorithms play a crucial role in efficiently solving large-scale opti- mization problems. In this paper, we introduce Sketching for Regularized Opti- mization (SRO), fast sketching algorithm designed for least squares problems with convex or nonconvex regularization. SRO operates by first creating a sketch of the original data matrix and then solving the sketched problem. We establish minimax optimal rates for sparse signal estimation by addressing the sketched propose
sparse convex and nonconvex learning problems. Furthermore, novel Iterative SRO algorithm, which reduces the approximation error geomet- rically for sketched convex regularized problems. To the best of our knowledge, this work is among the first to provide a unified theoretical framework demon- strating minimax rates for convex and nonconvex sparse learning problems via sketching. Experimental results validate the efficiency and effectiveness of both the SRO and Iterative SRO algorithms.
INTRODUCTION
Randomized algorithms for efficient optimization are critical area of research in machine learning and optimization, with wide-ranging applications in numerical linear algebra, data analysis, and sci- entific computing. Among these, matrix sketching and random projection techniques have gained significant attention for solving sketched problems at a much smaller scale (Vempala, 2004; Bout- sidis Drineas, 2009; Drineas et al., 2011; Mahoney, 2011; Kane & Nelson, 2014). These methods have been successfully applied to large-scale scale problems such as least squares regression, robust re- gression, low-rank approximation, singular value decomposition, and matrix factorization (Halko et al.. 2011; Lu et al., 2013; Alaoui & Mahoney, 2015; Raskutti & Mahoney, 2016; Yang et al., 2015; Drineas & Mahoney, 2016; Oymak et al., 2018; Oymak Tropp, 2017; Tropp et al., 2017). Regularized optimization problems with convex nonconvex regularization, such as the widely used in regularized least squares such as Lasso and ridge regression, play a fundamental role in ma- chine learning and statistics. While prior research has extensively explored random projection and sketching methods for problems with standard convex regularization (Zhang et al., 2016b) or con- vex constraints (Pilanci & Wainwright, 2016), there has been limited focus on analyzing regularized problems with general convex or nonconvex regularization frameworks.
We would like to emphasize that while (Yang Li, 2021) also studies sketching for regularized optimization problem, the focus and results of this work are completely different from that in (Yang & Li. 2021), with a detailed discussion deferred to Section 5. In particular, due to our novel result in the approximation eтror bound (Theorem D.2-Theorem D.3), the proposed iterative sketching al- gorithm, Iterative SRO, does not need to sample a new projection matrix and compute the sketched matrix at every iteration, in strong contrast to (Yang & Li, 2021). Moreover, the focus of this work to establish minimax optimal rates for sparse convex and nonconvex learning problems by sketch- ing, which has not been addressed by existing works in the literature including (Yang & Li, 2021). While (Yang & Li, 2021) only focuses on the optimization perspective, that is, approximating the solution to the original optimization problem by the solution to the sketched problem, the focus of this work needs much more efforts beyond the efforts made in (Yang & Li, 2021) for optimization only: we need to show that the solution to the sketched problem can still enjoy the minimax optimal

---

Published as a conference paper at ICLR 2025
rates for estimation of the sparse parameter vector for both sparse convex and nonconvex learning problems. Such efforts and results in minimax optimal rates for sparse convex and nonconvex learn- ing problems by sketching have not been offered by previous works including (Yang & Li, 2021), which are provided in Section 4 of this paper. Such minimax optimal results are established in a highly non-trivial manner. For example, the best of our knowledge, Theorem 4.1 is among the first in the literature which uses an iteratively sketching algorithm to achieve the minimax optimal rate for sparse convex learning. Furthermore, Theorem 4.5 shows that sketching can also lead the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems still considered difficult and open in the literature.
In this paper, we study efficient sketching algorithm for the optimization problem of regularized least squares with convex or nonconvex regularization, which is presented as follows:
f(3) = 2 ly x,312 (x3). BER
min
(1)
Here X E igudd is the data matrix or design matrix for regression problems, hx R + R is reg-
ularizer function and À is positive regularization weight. When hxx+)) XII112 hx(+) = 1|1111 (I) is the optimization problem for ridge regression el regularized least square estimation (Lasso). Section 4.2 provides more examples for nonconvex hx, We focus on paarstt--inducing regularizers, and the solution to the sketched problem (1) can provably approximate the true parameter vector for sparse signal estimation to be detailed in Section 4.
We study the regime that paper, and it is a popular setting for large-scale problems such as fast least square estimation by sketching (Drineas et al., 2011). 1). For example, matrix X in sparse linear regression is usually low- rank or approximately low-rank in practice. However, our results for sparse nonconvex learning in Subsection 4.2 hold for X not necessarily low-rank.
rank(X) where is the rank of X in most results of this
Optimization for (1) is time consuming when n is large, and such large-scale regularized optimiza- tion problems are important due to the increasing interest in massive data. To this end, we propose Sketching for Regularized Optimization (SRO) in this paper as an efficient randomized algorithm the target row number of a sketch of the data matrix X which is also termed the sketch size, SRO first generates a sketched version of X by X PX, then solves the following sketched problem.
for problem (1). With < where
min f(() = 3 X X + (B) BERd
One hopes that the optimization result of the sketched problem (2), denoted by 3", is a good ap- proximation that of the original problem (1), denoted by , The optimization and theoretical computer science literature are particulary interested in the solution approximation measure defind
where ||u||x == [Xully for any vector u. Existing research, such as Iterative Hessian Sketch (IHS) (Pilanci & Wainwright, 2016), prefers relative-error approximation the solution of the original problem in the following form:
as the semi-norm induced by the data matrix X, that is, 3 - 3r = x(
X -3>
| S 1|ll8
(3)
where 0 < < < 1 is a positive constant. With the relative-error approximation (3), IHS proposes an interesting iterative sketching method reduce the approximation error 0 3 geometrically
in the iteration number. Sketching the matrix X only in the quadratic term ||,3]] 2 is proposed in
(Pilanci & Wainwright, 2016) for constrained least square problems with convex constraints. SRO adopts this idea for regularized least square problems admitting broad range of regularizers.
1.1 CONTRIBUTIONS AND MAIN RESULTS
We study the sparse signal estimation problem by sketching in Section 4. For sparse convex or nonconvex learning problems where hy is convex nonconvex, we obtain the minimax optimal
2

---

Published as a conference paper at ICLR 2025
rate of the order (v log d/r²) for the parameter estimation error in sparse signal estimation by solving the sketched problem (2) where is the support size of the unknown sparse parameter vector to be estimated. To the best of our knowledge, our analysis provides the first unified theoretical result for the minimax optimal error rate for sparse signal estimation using sketching based optimization method.
In order to obtain such minimax optimal rate for sparse signal estimation by solving the sketched sparse convex learning problems, we propose an iterative sketching algorithm termed Iterative SRO
in Section 3, which provably reduces the approximation error 3 - 3 x geometrically in an iterative manner. Albeit being bounded, the approximation error of one-time SRO is still small enough for various applications. To this end, Iterative SRO iteratively applies SRO to approximate the residual of the last iteration so as to further reduce the approximation error, given the relative- error approximation (3). More details are introduced in Section 3 and Section 7.
There are two key differences between Iterative SRO and IHS (Pilanci Wainwright, 2016). First, using the subspace embedding as the projection matrix P. Iterative SRO does not need to sample P and compute the sketched matrix X PX at each iteration, in contrast with IHS where separate P is sampled and X is computed at each iteration. This advantage saves considerable computation and storage for large-scale problems. Second, while IHS is restricted to constrained least-square problems with convex constraints, SRO and Iterative SRO are capable of handling all convex regularization and certain nonconvex regularization in unified framework. For example, we show that Generalized Lasso (Tibshirani & Taylor, 2011) can be efficiently and effectively solved by Iterative SRO in Scction 7.
1.2 NOTATIONS
Throughout this paper, use bold letters for matrices and vectors, regular lower letters for scalars. The bold letter with subscript indicates the corresponding element of a matrix or vector, and the bold letter with superscript indicates the corresponding column of matrix, i.e. X' indicates the i-th column of matrix X. I|-II, denotes the fo-morm a vector, or the p-norm of a matrix. ox(.) is the t-th largest singular value of a matrix, and Jmin (-) and maax(-) singular value of matrix respectively. tr(-) is the trace of a matrix. (i) = ((2(()) if there exist constants ki, 1i > 0 and no such that ka (n)) S (n) & f2)2(n). We use X > Y to indicate that X - Y is positive semi-definite matrix, and L4 indicates the d x d identity matrix. rank(X) means the rank of matrix X. N denotes the set of all the natural numbers, and we use [m... to indicate numbers between m and inclusively, and [n] denotes the natural numbers between and n inclusively. nnz(X) indicates the number of nonzero elements of a matrix X. |.| denotes the cardinality of set, and supp (-) denotes the set of indices of nonzero elements for vector.
(-) indicate the smallest and largest
2 THE SRO ALGORITHM
In order to improve the efficiency of optimization for (1), we propose Regularized Optimization by Sketching (SRO) in this section. The key idea is to sketch matrix X in the quadratic term of (1) by random projection. It consisits of two steps:
Step 1. Project the matrix X onto lower dimensional space by linear transformation P E R with á < i.e. X = PX. ñ is named the sketch size.
Step 2. Solve the sketched problem (2).
The linear transformation P is required to be a subspace embedding (Woodruff, 2014) defined in Definition 2.1. The literature (Frankl & Machara, 1987; Indyk & Motwani. 1998: Zhang et al., 2016a) extensively studies such random transformation which is also closely related to the proof of the Johnson-L Lindensrauusss lemma (Dasgupta Gupta, 2003).
Definition 2.1. Suppose P is distribution over ñ X n matrices, where ñ is a function of n, d, s, for any fixed
and 8. Suppose that with probability at least from distribution P has the property that P is (1 + e) eL-subspace embedding for X, that is,
matrix X. matrix P drawn
(1 +) x < |PX 3 < (1 + + +
3

---

Published as a conference paper at ICLR 2025
holds for all 3 E R.. Then we call P an (e, oblivious -ubsspcce embedding.
Definition 2.2 (Gaussian Subspace Embedding, (Woodruff, 2014, Theorem 2.3)), Let 0 < e, 8 < 1,
P P where P' E Rax= is a matrix whose elements are i.i.d samples from the standard
vn
Gaussian distribution (00,,) 1). Then if ñ = O((r + log })=== for any matrix X E Raxd with rank(X), with probability 6, P P' is (1 =) e subspacce embedding for X. P is Vū
named a Gaussian subspace embedding.
Definition 2.3 (Sparse Subspace Embedding). Let P E R For each E [n]. h(i) E [i]] is uniformly chosen from [ū], and o(1) is uniformly random element of {1, -1). We then set Pk(0) = (i) and set , = 0 for all j * i. As a result, P has only a single nonzero element per column, and it is called a sparse subspace embedding.
Lemma 2.1 below, also presented in (Clarkson & Woodruff, 2013), shows that the sparse subspace embedding defined above indeed subspace embedding with high probability.
Lemma 2.1. (Clarkson & Woodruff, 2013, Theorem 2.1). Let P Rax* be sparse embedding matrix with = O 0(x2/(6E")
()E=)) rows. Then for any fixed n x matrix X with r = rank(X), with probability 1 - 8, P is (1 + s) -usubppcce embedding for X. Furthermore, PX can be computed in O(nnz X)) time, where nnz X) is the number of nonzero elements of X.
2.1
ERROR BOUNDS
The solutions to the original problem (1) and the sketched problem (2) by typical iterative optimiza- tion algorithms, such gradient descent for smooth / proximal gradient method for non-smooth h, are always critical points of the corresponding objective functions under mild conditions (Bolte et al., 2014). Therefore, the analysis in the gap between 3 and 3 amounts to the analysis in the distance between critical points of the objective functions of (2) and that of (1), which is presented in Section 5. In the sequel, 3 is critical point of the objective function (2) and 3 is critical point of the objective function (1), if no confusion arises. More details about optimization algorithms are deferred to appendix.
ITERATIVE SRO
Algorithm Iterative SRO
Input: Initialize ((0) 0, iteration number N > 0, 0.
for t- 1 to N Set
3 arg min BERd
x -0--)
12 1 - x,( -xx
(5)
end for Return (NN)
Inspired by Iterative Hessian Sketch (Pilanci & Wainwright, 2016), we introduce an iterative sketch- ing method for SRO, termed Iterative SRO, that the gap between solutions the original problem and the sketched problem can be geometrically reduced compared to the one-time SRO. Iterative SRO will be used solve the sketched Lasso problem with (B) >|||8||, in the sketched prob- lem (2), and obtain the minimax rate of the order O (V 8 log d/n) for the parameter estimation eтror in sparse signal estimation to be detailed in Section 4.
The key idea is to iteratively apply SRO to generate a sequence [ such that ( a more accurate approximation to 3", the solution to the original problem (1), than (((-1), Consider the optimization problem
min X(3 1/ -y -xxx++++++ x (B+ BER 2
(6)
4

---

Published as a conference paper at ICLR 2025
then 3 - (((t1) is an optimal solution to (6). We apply SRO to problem (6) and suppose B is an solution to the sketched problem. i.e.
β arg min BER
X3
xX-(t)--) x6) hB + (((-1)).
is noted that ( 1) is moved from the quadratic term in (6) to the linear term in (7). 3 supposed to be an approximation to 3 - -3(t-1). If ] admits the relative-error approximation bound (3), then (a = 3 + ((-11) becomes a more accurate approximation to 3 than ((t-1) by factor of p. S s - 3((-1)||
This can be verified by noting that ||300 B X - - (3- - 1) x
By mathematical induction, we have Theorem 3.1 below showing that the approximation error of Iterative SRO, which is formally described by Algorithm 1, drops geometrically in the iteration number. It should be emphasized that Theorem 3.1 also handles certain nonconvex regularization.
Theorem 3.1. Suppose 3 is any critical point of the objective function in (2), and 3 is any critical point of the objective function in (1), Suppose 0 < < En < where Eo is a small positive constant, 0 5 P is drawn from (e, 6) oblivious --subspace embedding over ñ n matrices. Then with probability at least - 5 with E (0, the output of Iterative SRO described by Algorithm satisfies
| -3 S <1
(8) for a constant 0 < p < if is convex, or the Frechet subdifferential of is Ln-smooth and X has full column rank with Ln
m (Xj < =1. Frechet subdifferential of h is La-smooth if sup suPpuch(x) ||u - vl12 S La||x- - y for positive number Lμ- In particular, if is a If P sparse subspace
Gaussian subspace embedding, then ñ O ((r + log ) (p embedding, then = O (12/5 (p + /)). Here r = rank(X).
Section 5 presents necessary theoretical results for the proof of Theorem 3.1.
4 SKETCHING FOR SPARSE SIGNAL ESTIMATION
We study sparse signal estimation by sketching in this section. We consider the linear model widely used in the sparse signal estimation literature, y = X,3 + & where is noise vector of i.i.d. sub-gaussian elements with variance proxy o², and ,3 is the sparse parameter vector of interest. Following the standard analysis for parameter estimation in the literature such as (Yang et al., 2016; Zhang, 2010b), we assume max || S vn, and follows that max,e[4] [d]] || [| S 1. The statistical learning literature has extensively studied the approximation to B by the M-estimator obtained as a globally or locally optimal solution problem (1) with X X/v k/Vn.y = v/v That is. one hopes to approximate / by the globally or locally optimal solution to problem (1) with a suitable sparsity-inducing regularizer h1x, In Subsection 4.1, we show that the Iterative SRO described in Algorithm 1 achieves the minimax parameter estimation error of the order v log d/n where s = || In Subsection 4.2, we prove that SRO achieves the minimax parameter estimation error of the order /slog d/n for sparse nonconvex learning, where the nonconvex regularizer h2 is the sum of a concave penalty function ęA and A/I-I11- Section 4.1, 3 obtained by Algorithm through 3 = _(x)), In Section 4.2, 3 is the optimization result of the sketched problem (2).
4.1 SKETCHING FOR SPARSE CONVEX LEARNING
We define L(B) == 1/2 B x x3- T X,3 and Z(3)= = 1/2 the following definition of sparse eigenvalues widely used in sparse signal estimation literature. Definition 4.1. (Sparse Eigenvalues) Let be a positive integer. The largest and smallest s-sparse eigenvalues of the Hessian matrix V² X X is
x We introduce
PC. (s) sup (v T Xv: l S s. |lvl2 1, Rd).
(9)
Pc.-(s) = inf (v x Xv: ||vl, S s, 1 1, Rd)
(10)
(-)+() and P2,-() are defined in similar manner with X replaced by X
5

---

Published as a conference paper at ICLR 2025
The following assumption is frequently used in the sparse signal estimation literature with the convex pparsity-inducing penalty, X/1-I11- Assumption 1. (Assumption in (Yang et al., 2016; Zhang, 2010b) for sparse signal estimation) (b) < 00, Pc.-(s) are positive constants. Moreover, for 8 = || ol there exists a ks E N
such that k* 2 23 and
+3 < 1 + 0.5
(11)
We study the sparse signal estimation problem by solving the sketched Lasso problem with (Q) X||/8||, in the original problem (1) and the sketched problem (2) using our Iterative SRO algorithm. We have the following sharp bound for the parameter estimation error.
Theorem 4.1. Suppose Assumption holds. Let À co /log d/n where c is positive constant.
Suppose Al Algorithm returns 3 = ((N) with E (0. 1) in Theorem 3.1, and the iteration number N is chosen as N = log (|) X 2 ( /xx (Ap))) (lgg)))//oo/////// (1)) Then with probability at least 1 1 - 2/d
with 5 (0,
(1 (1+7) (c uc 2)
s slog d
-
(12)
PL. (*) (1- vv.5)
n
where j is a positive constant, = (1+ μ + 2/c)/(1 - μ 2/c). and μ and e are chosen such that vv0 < 1. In particular, if P is a Gaussian subspace embedding, then ñ O ((r + log }) 1)3/') If P is sparse subspace embedding, then ñ O (12/8- (p + /2)) Here (X).
Theorem 4.1 shows that our Iterative ROS described in Algorithm applied on the sketched problem
(2) achieves the parameter estimation error, which is 3 3 of the order / /olog d/n. n. Such estimation error rate is not improvable and it is the minimax error rate for standard Lasso. With the rank < n, Iterative ROS obtains the solution 3 3((V) efficiently with small sketch size ñ and the iteration number N is only of a logarithmic order.
4.2 SKETCHING FOR SPARSE NONCONVEX LEARNING
We now study sparse signal estimation by sparse nonconvex learning where the regularizer h2 is nonconvex in the original problem (1) and the sketched problem (2), that is, (3) = \|1,3|| +
(x(3) where Qx = Σ ax (B3), Qx is a concave function and 33 is the j-th element of B. We
d
have (B) = Σ (A (A + (3,)). Following the analysis of sparse parameter vector recovery j=1
in (Wang al., 2014), x1 + (x) is nonconvex function which be either smoothly clipped absolute deviation (SCAD) (Fan & Li, 2001) or minimax concave penalty (MCP) (Zhang, 20)0a). More details about the nonconvex regularizer h, are deferred to Section A of the appendix. The following regularity conditions on the concave function Q사 are used in (Wang et al., 2014).
Assumption 2. (Regularity Conditions on Nonconvex Penalty in (Wang et al., 2014) for sparse signal recovery)
(a) 4, ($,) is monotone and Lipschitz continuous. For B3 > 3y. there exist two constants <- 2
0, C+ 2 0 such that -C- S -(,0))))1)))))
- < SSt..
(b) 4x (-),) = (3,) for all B, E R. Also, ax (0) = (0) = 0.
(c) of (8,) E A for all 8y E R. and 144, (8,) 4h (8,) S |Λ1 - Au for all Y1 > 0, > 0.
The following assumption is the standard assumption in (Wang et al., 2014) for sparse signal esti- mation with the minimax error rate, that is. || - B112 0 /Vllog
Assumption 3. (Assumption in (Wang et al., 2014) for sparse signal estimation) Let 5 = | |ll
There exist an integer 8 such that ă > C's such that Pc.+ (3 + 23) < co, PC,- (3 + 28) > 0 are two absolute constants. The concavity parameter (- in Assumption 2 satisfies Ç- S C' (S+22)))223) with constant C' (0, 1). Here C 144x² + 250k with (pc,+ (8 + 23) (4)/ (8 (S+25) 25) (-)-

---

Published as a conference paper at ICLR 2025
The following corollary shows that when the support size of 3 3 is bounded by su. then the
nonconvex sparse learning problem (1) with hy being the nonconvex regularizer specified in this subsection still enjoys relative-error approximation. Corollary 4.2 is employed to prove our main result of minimax estimation error rate by sketching in Theorem 4.5.
Corollary 4.2. Suppose Assumption holds, and let P E RRax" be a Gaussian subspace embedding
and suppose that supp (3- - U Suupp (3*) supp (3))
I So for some integer Su E [d]. Let
n 2 cos-2 (20g(2/8) + so log d + so log 5) for ò E (0, 1) and E E (0, 10 C") where co is a positive constant. Then with probability at least - 6.
EV PCPC
| 3
(1 c)p - 11
(13)
The following assumption, Assumption 4, is necessary to achieve the minimax parameter estimation error by sketching, and the subsequent Remark 4.3 explains that Assumption mild. That is, Assumption 3 holds, then Assumption 4 also holds under mild conditions.
Assumption 4. (Assumption in (Wang et al., 2014) for sparse signal estimation) Let 8, be the parameters specified in Assumption 3 such that Assumption 3 holds. Then it is assumed that (5 (5 + 25) < 00, - (5 + 25) > 0 are two absolute constants. In addition, Ç- satisfies
S- S C' Pc. (5 + 28), and $ > Čs where Č 144R² + 250 with ñ = (P2,+ + 28)
S4)/(p2, + 25) C-))
Remark 4.3 (Assumption 4 is mild). We provide theoretical justification that Assumption 4 is mild. The following theorem, Theorem 4.4, shows that if the standard Assumption 3 holds, then As- sumption 4 also holds with high probability under very mild conditions: either E is set the order of /log d/n with sufficiently large n. or the Restricted Isometry Property (RIP) (Candes & Tao, 2005b) holds. It is well known that RIP holds for various choices of the design matrix X, and (Wang et al., 2014) also uses RIP to justify that the standard Assumption 3 is weaker than RIP.
Theorem 4.4. Suppose Assumption 3 holds with ş and C" specified in Assumption 3, and let 80 $ + 28. Let < e, < 1, P E Râxa be a Gaussian subspace embedding defined in Definition 2.2, and ñ 2 coe-2 (log(2/0) + 80 log d + so log + 1/d"o-1) where co is positive constant. If (c.-(so) (8o) ev Ç- S C" (pc.- - /80) and (144x²2 250k') 8 8 with n' (pc, + - (p)/(pc.-(ss) sumption 4 holds. In particular, Assumption 4 holds with probability at least - ô if any one of the following two conditions holds:
/ (-), then with probability at least 1 ô, As-
(a) log d/n "= 0, Ci Vlog d/n with C1 being a positive constant and sufficiently large; (b) There exists s' 2 so such that ()) holds for ō E (0, S+ = 0.
(so), / < Capc.-(so) 3 > (144x) + 250xo) 3 with Ko = (1+ +)) ((1 ( C. - -Ca)(1 5)). Here the positive constants C2. Cg satisfy C2 + C3 < 1 and C2 < C²(1 Cz). (IP(5, 8) for d E 10 and E is the Restricted Isometry Property (RIP) (Candes & Tao, 2005b) under which 1 - 5 < (s) S PC.+ (8) S 1 1+ holds. It is shown in Section A that 4+ = O and Ç- C2pc. (su) can be easily achieved by setting the hyperparameter of MCP when MCP used as the nonconvex regularizer h2. We have the following sharp bound for the parameter estimation eтror with sparse nonconvex learning by sketching in Theorem 4.5. We note that the approximate path following method described in (Wang et al., 2014, Algorithm 1) is used to solve the original problem (1) and the sketched problem (2) to obtain 3 and 3 such that 3 an critical point of problem (1) and 3 is an critical point of (2). We use = θ ( (55log d/n) for both (1) and (2) at the final stage of the path following method (Wang et al., 2014, Algorithm 1).
<-
Theorem 4.5. Let 8 E (0,1) and P E pax= be a Gaussian subspace embedding defined in min (i//og//n..o) with C1, being positive constants and (0, (1- - (2) Suppose 3 is the optimization result of the sketched problem (2) with sketch size ñ 2 n/Cg for n @(1), Assumption 3 and Assumption 4 hold, d > 5, and let so 3 + 25.
Definition 2.2, and
Then with probability 1 - 8., with probability at least 1 4/d,
| -
5
| 2/ + 8 8/3) p3, (su)
8log d
22 (CIV5 3 2 + 20)
8 log d
(14)
2
(1 C2) PC. PC.- (8o) 5-
n
Pc.- (sp) - -C-
7

---

Published as a conference paper at ICLR 2025
where C1 cc37922o/789CC with C3s
being positive constant.
It is noted that we can choose & = (s). When ||||| is constant, have the parameter estimation
error - - O $ $log d/n which the minimax estimation error according to (Wang
can enjoy small sketch size á n/C3 with a potentially large C3 > 1. and this is at the expense of having a large constant factor C₁ in the
al., 2014). Moreover, with C1 4v 20//9922s/77//
parameter estimation error o ( (Vilogd/n)
5 APPROXIMATION ERROR BOUNDS FOR THE PROOF OF THEOREM 3.1
In this section, we present an introduction to the theoretical results, Theorem D.2 and Theorem D.3 deferred Section D.2 of the appendix, which are necessary for the proof of Theorem 3.1. First, novel universal approximation error bound for SRO on the general problem (1) is given by Theo- rem D.2. Based on such universal approximation error bound, relative-error approximation bounds for regularized least squares with convex regularization and nonconvex regularization under certain conditions are derived in Theorem D.2. Before introducing these results, we present the definitions of Frechet subdifferential and critical point below, which are crucial for our analysis.
Definition 5.1. (Subdifferential and critical points) Given a nonconvex function f: R - RU {+oo} which is proper and lower semi-continuous function,
for a given x E doms. its Frechet subdifferential of f at x, denoted by 0f(x), is the set of all vectors E Id which satisfy lim (xy))f(x)((xx)) (u.y-x. 0. yxx.y-x
ly 1y-xll2
of f at x E Rd, denoted by 0f(x). is defined by 0f(x) {u E Rd: Fx* - xxxxx + f(x), at E 0f(x²) + u). The point x is critical point of f 0 E ax()..
The limiting-subdiiffreenn
It is noted that the Frechet subdifferential generalizes the notions of Frechet derivative and subdiffer- ential of convex functions. When f is convex, then fx(x) is the subdifferential of f at x. Moreover, ff(x) (V fxx} when f is differentiable. In order to derive the relative-error approximation bounds in this section, we need the following definition of the degree of nonconvexity
function. The univariate degree of nonconvexity is first introduced in (Zhang & Zhang, 2012) for the analysis of the consistency of nonconvex sparse estimation models with concave regularization, and Defini- tion 5.2 is extension of such univariate degree of nonconvexity, which is also employed in the analysis of sketching for regularized optimization in (Yang & Li, 2021).
Definition 5.2. The degree of nonconvexity of a function Rd + at a point t E Rd is defined as
-(s - T)T (u v) - <k|s - t|
(t, K) ==
sup SERd,ayt.uEdn (SE
(15)
||s - t||
where K. E R. We abbreviate (15) as (,, x)) SUPEER axt || (s t) (8T(()))-8h(())) ōh((t)
k||s tll2} in the following text.
Remark 5.1. If h is convex, then ((s t) (u v) < 0, so that the degree of nonconvexity of any convex function h is (t, x) I O for any with x 2 0. Moreover, the degree of nonconvexity of a second-order differentiable function h satisfies 0g (t, x) < 0 if h is "more PSD" than -x|1-112- that is, the smallest eigenvalue of its Hessian is not less than K.
Let 3 any critical point of the objective function in (2), 3 any critical point of the objective function in (1), and 0 < Eo < 1 where Eo is small positive constant, 0 < 8 < 1. Suppose P drawn from an (e, 8) oblivious 8 subspace embedding over ñ x n matrices. Then Theorem D.2 asserts that with probability 1 5,
(1 --=)]|3- -B-1 1=1 - -elβ² 3r
11 s Onn (B" m0] (Br,)) -3-1. + k =0|0
3 1- (16)
8

---

Published as a conference paper at ICLR 2025
In partieular, if P is Gaussian subspace embedding, then ñ ((( + -og subspace embedding, then ñ O(r²) (6==))
If P is sparse
Furthermore, Theorem D.3 states that if h1 is convex, then with probability 1 8, then
g 3r S T-E 1x If the Frechet subdifferential of Lm-smooth (h can be noncon- vex), then
3 3r x (1-2)- xLy |x
min (X)
Novelty and Our Results and Their Significant Difference from (Yang & Li, 2021) and (Pi- lanci Wainwright, 2016). is remarked that our results, including the Iterative SRO algorithm in Algorithm 1 and its theoretical guarantee in Theorem 3.1, Theorem D.2-Theorem D.3, and the minimax optimal rates by sketching for sparse convex learning in Theorem 4.1 and sparse noncon- vex learning in Theorem 4.5, are all novel and significantly different from (Yang & Li, 2021) in the following two aspects, although ( (Yang& & Li, 2021) also presents an iterative sketching algorithm for regularized optimization problems. First, Iterative SRO does not need to sample projection matrix P E Rix0 and compute the sketched matrix X PX at every iteration, while the iterative sketching algorithm in (Yang& & Li, 2021) samples a different projection matrix and computes the sketched matrix every iteration which incurs considerable computational cost for large-scale prob- lem with large data size n. Such advantage of Iterative SRO over (Yang & Li, 2021) is attributed to the novel theoretical results in Theorem D.2 and Theorem D.3. In contrast with (Yang & Li, 2021, Theorem 1), the approximation error bound Theorem D.2 is derived for sketching low-rank data matrix by oblivious -uususpacce embedding with the sketched size clearly specified. As a result, Theorem D.3 presents the approximation error bounds for convex and certain nonconvex regular- ization by sketching with oblivious -u-subspace embedding. Based on such results, Theorem 3.1 shows that single projection matrix suffices for the iterative sketching process. Second, minimax optimal rates for convex and nonconvex sparse learning problems by sketching are established by our results, while there are such minimax optimal rates by sketching algorithm in (Yang & Li, 2021). Theorem 4, to the best of our knowledge, is among the first in the literature which uses an iteratively sketching algorithm Furthermore, Theorem 4.5 shows that sketching can also lead to the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems is still considered difficult and open in the literature.
achieve the minimax optimal rate for sparse convex learning.
Our results are also significantly different from those in (Pilanci Wainwright, 2016). It re- marked that (Pilanci & Wainwright, 2016) only handles convex constrained least square problems of the form mingee ||x3 - v112 where the constraint set C is convex set, while our results cover regularized convex and nonconvex problems with minimax optimal rates. It is emphasized that the techniques in (Pilanci & Wainwright, 2016) can never be applied to the regularized problems con- sidered in this paper. (Pilanci & Wainwright, 2016) heavily relies on certain complexity measure of the constraint set C, such the Gaussian width. It shows that the complexity of such constraint set C is bounded, so that sketching with such constraint set C of limited complexity only incurs relatively small approximation error. However, there is never such constraint set in the original problem (1) or the sketched problem (2), so that such complexity based analysis for sketching can not be applied to this work. Furthermore, as mentioned in Section 1.1, Iterative SRO does need to sample the projection matrix and compute the sketched matrix at each iteration, in contrast with IHS (Pilanci & Wainwright, 2016) where separate projection matrix is sampled and the sketched matrix is computed at each iteration. As evidenced by Table in Section 7.1, Iterative SRO is more efficient than its "IHS" counterpart where sketching is performed every iteration while enjoying comparable approximation error.
6
TIME COMPLEXITY
We compare the time complexity of solving the original problem (1) to that of solving the sketched problem (2) with Iterative SRO, which is deferred to Section B of the appendix.
7 EXPERIMENTAL RESULTS
We provide empirical results in this section to justify the effectiveness of the proposed SRO and Iterative SRO.

---

Published as a conference paper at ICLR 2025
7.1 GENERALIZED LASSO
We study the performance of Iterative SRO for Generalized Lasso (GLasso) (Tibshirani & Tay- lor, 2011) in this subsection. The optimization problem of an instance of GLasso studied here is d-1
3 = arg 3 21lyy x311 + + G. - Bit1l. which is solved by Fast Iterative Shrinkage-
Thresholding Algorithm (FISTA) (Beck & Teboulle, 2009), an accelerated version of PGD. X = vnX E Raxd has i..d. standard Gaussian entries with n 80000 and 600, and all the ele- ments of = vny are also i.i.d. Gaussian samples. Figure 4 in Section C.2 of the appendix illus- ||800)-011 and ||stM)
trates the approximation error of SRO and Iterative SRO, which are respectively, for different choices of sketch size ñ with ñ = -d. either sparse subspace embedding or Gaussian subspace embedding. The average approximation errors are reported over 100 trials of data sampling for each 7. It be observed that Iterative SRO significantly reduces the approximation error and its approximation error is roughly 1/ of that of SRO, demonstrating the effectiveness of Iterative SRO. In our experiment, due to the signifi- cant reduction the sample size, for example, 5d 0.0225 when & 3, the running time of Iterative SRO is always less than half of that required to solve the original problem with small 5. We also report the running time of GLasso with sparse subspace embedding in Table 1. Let M be the maximum number of iterations for FISTA, and set M 10000 for SRO and set M 2000 for Iterative SRO, and the running time is reported for 3 3 on CPU of Intel i5- 1300H. Iterative SRO-IHS is the "IHS" version of Iterative SRO where a new sketch matrix P is sampled and the sketched data X PX computed at each it- eration. We observed that both Iterative SRO-IHS and Iterative SRO achieve the same approximation error, while Iterative SRO faster than Itera- tive SRO-IHS because the former only samples the linear transformation P once and computes the sketched matrix X once. We also note that the maximum iteration number of FISTA for Iterative SRO much smaller than that for SRO. This is because Iterative SRO uses an iterative sketching process where the approximation error is geometrically reduced with respect to the iteration number t in Algorithm 1, so that each iteration of Iterative SRO is only required to have moderate ap- proximation error which can be larger than the approximation error of SRO thus a smaller iteration number FISTA suffices for Iterative SRO. Such analysis also explains the fact that Iterative SRO much faster than SRO, and in our experiment the maximum iteration number N for Iterative SRO in Algorithm always not greater than 5.
We set N 10 and employ
x
Table 1: Rumning time (in seconds) of SRO, Iterative SRO with 7 3 and Iterative SRO- IHS for GLasso. The number in the bracket is the approximation error.
SRO 11.04s
Iterative SRO
Iterative SRO-IHS
4.71s(0.036)
5.11s(0.036)
7.2 ADDITIONAL EXPERIMENTS
We defer more experimental results to the Section C of the appendix. In particular, experimental results for ridge regression and sparse signal estimation by Lasso are in Section C.1 and Section C.3 respectively, and more details about GLasso are in Section C.2. We further apply SRO to subspace clustering using Lasso in Section C.4, and presents performance of SRO for sparse nonconvex learn- ing with capped- regularization in Section C.5.
CONCLUSION
We present Sketching for Regularized Optimization (SRO) which efficiently solves general reg- ularized optimization problems with convex or nonconvex regularization by sketching. We further propose Iterative SRO to reduce the approximation error of SRO geometrically, and provide a unified theoretical framework under which the minimax rates for sparse signal estimation both convex and nonconvex sparse learning problems. Experimental results evidence that Iterative SRO effectively and efficiently approximate the optimization result of the original problem.
obtained for
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This material is based upon work supported by the U.S. Department of Homeland Security under Grant Award Number I7STQACC0001-00-000, The views and conclusions contained in this docu- ment are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security. This work is also partially supported by the 2023 Mayo Clinic and Arizona State University Alliance for Health Care Collaborative Research Seed Grant Program under Grant Award Number AWD00038846.
REFERENCES
Ahmed Alaoui and Michael W Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 775-783. Curran Associates, Inc., 2015.
G. Aubrun and S.J. Szarek. Alice and Bob Meet Banach. Mathematical Surveys and Monographs. American Mathematical Society, 2017. ISBN 9781470434687.
Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28(3):253-263, Dec 2008.
Amir Beck and Mare Teboulle. A fast iterative Sninkagg-threshooling algorithm for linear inverse problems. SIAM Img. Sci., 2(1)::83-200) March 2009.
Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program., 146(1-2):459 2):459-4944 August 2014.
Christos Boutsidis and Petros Drineas. Random projections for the nonnegative least-squares prob- lem. Linear Algebra and its Applications, 431(5):760-
E.J. Candes and T. Tao. Decoding by linear programming. Information Theory, IEEE Transactions on, 51(1))144003-4222 4215, Dec 2005a.
E.J. Candes and T. Tao. Decoding by linear programming, IEEE Transactions on Information Theory, 5 (112):4203-42215, 2005b. doi: 00.1009/TT.2005888897799
Kenneth L. Clarkson and David Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings the Forty-Fifth Annual ACM Symposium Theory of Computing, STOC '13, pp. 81-90, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and linden- strauss. Random Struct. Algorithms, 22(():60063 65, January 2003.
Petros Drineas and Michael W. Mahoney. Randnla: Randomized numerical linear algebra. Commun. ACM, 59(6))80-90, 90, May 2016.
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische Mathematik 117())219-249, 2011.
Eva L. Dyer, Aswin C. Sankaranarayanan, and Richard G. Baraniuk. Greedy feature selection for subspace clustering, Journal of Machine Learning Research, 14:2487-2517, 2013.
Ehsan Elhamifar and René Vidal. Sparse manifold clustering and embedding. In NIPS, pp. 55-63, 2011.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, (6(455):1348-11 2001.
Frankl and H. Machara. The johnson- lindenstrausss lemma and the sphericity of some graphs J. Comb. Theory Ser. A, 4453),355-362, June 1987.

---

Published as a conference paper at ICLR 2025
N. Halko, P. G. Martinsson, and J. Tropp. Finding structure with randomness: probabilistic algo- rithms for constructing approximate matrix decompositions. SIAM REV, 53(2):217-288, 2011.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality.. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, pp. 604-613, New York, NY, USA, 1998. ACM.
Daniel M. Kane and Jelani Nelson. Sparser johnson-lindenstraus transforms. J. ACM, 61(1):4:1- 4:23, January 2014.
Yichao Lu, Paramveer S. Dhillon, Dean P. Foster, and Lyle H. Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013, pp. 369- 377. 2013.
Michael W. Mahoney. Randomized algorithms for matrices and data. Foundations and Trends@ in Machine Learning, 3(2):123-222) 2011.
Samet Oymak and Joel A Tropp- Universality laws for randomized dimension reduction, with ap- plications. Information and Inference: A Journal of the IMA, 7(3):337-446, 2017.
Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi. Isometric sketching of any set via the restricted isometry property. Information and Inference: A Journal of the IMA, 7(4):707-726, 03 2018.
Mert Pilanci and Martin J. Wainwright. Iterative hessian sketch: Fast and accurate solution approx- imation for constrained least-squares. J. Mach. Learn. Res., 17(1):1842-1899 January 2016.
Garvesh Raskutti and Michael W. Mahoney. statistical perspective on randomized sketching for ordinary least-squares. J. Mach. Learn. Res., 17:214:1-214:31, 2016.
Mahdi Soltanolkotabi and Emmanuel J. Candés. A geometric analysis of subspace clustering with outliers. Ann. Statist., 40(4):2195-22)) 2238, 08 2012.
Ryan J. Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. Ann. Statist, 39 (3):1335-1371, 1371, 06 2011. doi: 10. 10.11/111--AS875
Joel A. Tropp. Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketching algorithms for low-rank matrix approximation. SIAM Journal on Matrix Analysis and Applications, 38(4): 1454-1485, 2017.
Santosh Srinivas Vempala. The Random Projection Method, volume 65 of DIMACS Series in Dis- crete Mathematics and Theoretical Computer Science. DIMACS/AMS, 2004.
Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. In Yonina C. Eldar and GittaEditors Kutyniok (eds.), Compressed Sensing: Theory and Practice, pp. 210-268. Cambridge University Press, 2012.
Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. In Proceedings of the 30th Inter- national Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pp- 89-97, 2013.
Zhaoran Wang, Han Liu, and Tong Zhang. Optimal computational and statistical rates conver- gence for sparse nonconvex learning problems. The Annals of Statistics, 42(6):2164-2201 2014.
David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-155 2014.
Tianbao Yang. Lijun Zhang, Rong Jin, and Shenghuo Zhu. Theory of dual-sparse regularized ran- domized reduction. In Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 JMLR Workshop and Conference Pro- ceedings, pp. 305-314. org.. 2015.
12

---

Published as a conference paper at ICLR 2025
Yingzhen Yang and Ping Li. FROS: fast regularized optimization by sketching. In IEEE Interna- tional Synposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021, pp. 2780-2785. IEEE, 2021.
Zhuoran Yang, Zhaoran Wang, Han Liu, Yonina C. Eldar, and Tong Zhang. Sparse nonlinear regres- sion: Parameter estimation under nonconvexity. In Maria-Florina Balcan and Kilian Q. Wein- berger (eds.), Proceedingss of the 33nd International Conference Machine Leurning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2472-2481. org. 2016.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Stativlics, 38(2):894-942, 2010a.
Cun-Hui Zhang and Tong Zhang. A general theory of concave regularization for high-dimensional sparse estimation problems. Statist. Sci., 2764):576-593, 11 2012.
Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Sparse learning for large-scale and high-dimennional data: randomized convex-concave optimization approach. In Algorithmic Learning Theory- 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings, pp. 83-97, 2016a.
Tong Zhang. Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res., 11:1081-1107, 2010b.
Tong Zhang. Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res., 11:1081-1000 107, March 2010c.
Weizhong Zhang, Lijun Zhang, Rong Jin, Deng Cai, and Xiaofei He. Accelerated sparse linear regression via random projection. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI). pp. 2337-2343, 2016b.
Xin Zheng. Deng Cai, Xiaofei He, Wei- Ying Ma, and Xueyin Lin. Locality preserving clustering for image database. In Proceedings of the 12th Annual ACM International Conference Multimedia, MULTIMEDIA '04, pp. 885-891, New York, NY, USA, 2004. ACM.
A NONCONVEX PENALTY
We introduce more details about the nonconvex regularizer hy for sparse nonconvex learning in E PA()), and px can be either smoothly clipped absolute deviation (SCAD) (Fan & Li, 2001) or minimax concave penalty (MCP) (Zhang, 2010a). When px is SCAD, we have
Subsection 4.2. h2 Eÿ=
(A = => 18:1
(MESA + (a) -2--2)+ 1|12111 dz, a >> 2. (a- 1)1
When PA is SCAD, we have
PA(3,) = => p13)
-2/11))
(1- (1- 2) dz, b> 0.
Ab
B TIME COMPLEXITY
We compare the time complexity of solving the original problem (1) to that of solving the sketched problem (2) with Iterative SRO. We employ Proximal Gradient Descent (PGD) Gradient De- scent (GD) in our analysis, which are widely used in the machine learning and optimization lit- erature. If is a Gaussian subspace embedding Definition 2.2, it takes ((id)) operations to compute the sketched matrix x = PX and then form the sketched problem (2). Let C(ñ, d) be the time complexity of solving the sketched problem (2), and suppose iterative sketching is performed for N iterations, then the overall time complexity of Iterative SRO in Algorithm is O (ānd NC(,,d)). If P is sparse subspace embedding in Definition 2.3, then it only takes
13

---

Published as a conference paper at ICLR 2025
O (Xnz(X)) operations to compute the sketched matrix X. In this case, the overall time complexity of Iterative SRO is O (xnz(X) + NC d)). Suppose PGD, such as that analyzed in (Bolte et al., 2014), or GD, is used to solve problem (1) and (2) with maximum number of iterations being M. Then C(ñ, d) = O (Mnd). If a sparse subspace emhedding is used for sketching, then the overall time complexity of Iterative SRO is O (nnz(X) Mfdd). In contrast, because IHS (Pilanci & Wainwright, 2016) needs to sample an independent sketch matrix at each iteration, the time com- plexity of IHS using the fast Johnson-Lindenstraun is O (Nnd log ñ + N Mfdd) which is higher than that of Iterative SRO with sparse subspace em- bedding. Noting that N S log n (Pilanci & Wainwright, 2016) and in many practical cases N is bounded by constant, and ńi < the complexity of Iterative SRO, O (nnz(X) + MMdd), is much lower than that of solving the original problem (1) with the complexity of (MMd)..
sketches (that is, the fast Hadamard transform)
C COMPLETE EXPERIMENTAL RESULTS
We demonstrate complete experimental results of SRO and Iterative SRO in this section for three instances of the general optimization problem (1), which include ridge regression where h(3)
d-1 Σ 3r Bitl), and Lasso where h(3) || We
||
Generalized Lasso where h(33)
further show the application of SRO in subspace clustering.
-33
Oppe emooa 400 Appooeattrrrte
1.5
12
12
Reraton Nambe"
turdoo Number
t2r3don Number
121022 Rumber
Rara8in Namber
1.5
Mggattena www.RITTTOOo....oo Cow.AITuuooooo
Igaatennl www.emmruiioooo Sosteootan C011
Agaltennl wOw.RITTI
13
Roraton Numbe
tarooon Number
taroion Number
Rarolo Rumbor
Raralon Number
Figure 1: Approximation Error of Iterative SRO with respect to different sketch size ñ for ridge regression. The first row corresponds to sparse subspace embedding defined in Definition 2.3 and the second row is produced by Gaussian subspace embedding defined in Definition 2.2.
C.1 RIDGE REGRESSION OF LARGER SCALE
We employ Iterative SRO to approximate solution to Ridge Regression in this subsection, whose optimization problem is B arg minnseed. 1 lly x,31 + >|| We assume a linear model = X,3 + where X X X/vn, y = =//Vn, w ~ (o, I.) is the Gaussian noise with unit variance. The unknown regression vector 3 is sampled according to ( L2). We randomly sample Ioo with n 5000 and d 10000. Let X UEV be the Singular Value Decomposition of X where Σ E Rexr is diagonal matrix whose diagonal elements are the singular values of X. U e R"xr is sampled from the uniform distribution over the Stiefel manifold W, (R"), V E dxr is sampled from the uniform distribution over the Stiefel manifold W, (RR), the diagonal elements of Σ are i.i.d. standard Gaussian samples. We set Vlog d/n. Figure 3 Ilx
X E IRaidd of rank
|0
illustrates the logarithm of approximation enror
with respect to the iteration number of
14

---

Published as a conference paper at ICLR 2025
110.00
130880 RO
12086C FLYOM
Logarithm of approximation error of Iterative SRO with respect to different sketch size for ridge regression. The first corresponds sparse subspace embedding and the second row is produced by Gaussian subspace embedding.
Figure 2:
.38>
.3p>
210
=32"
Number
Sumber
12nmxi())
228 Mamicc))
.28 8- Hamtic))
21.7 Hiraid
222
RESHOORIO WWW.ROAAAAROOM CAMP
12
12
10
Vinter
Figure 3: Approximation enror of Iterative SRO with respect to different sketch size ñ for ridge regression. The first row corresponds to sparse subspace embedding and the second row is produced by Gaussian subspace embedding.
Iterative SRO for different choices of sketch size n, and the maximum iteration number of Iterative SRO is set to N 10. We let 5rank(X) where ranges over {12, 14, 16, 18, 20), and sample X, and w 100 times for each 7. The average approximation errors are illustrated in Figure 1. can drops geometrically, or its logarithm drops linearly, evidencing our Theorem 3.1 for Iterative SRO. Moreover, as suggested by Theorem D.2, larger leads to smaller approximation error.
be observed from Figure/ 1 that the convergence rate of approximation
We present more experimental results for ridge regression with larger-scale data where n = 10000 and d = 100000, and other settings remain the same. We let yrank(X) where ranges
15

---

Published as a conference paper at ICLR 2025
{12, 14, 16, 18, 20). and sample X, G and w 100 times for each y. Figure illustrates the logarithm
of approximation error, which is log || llx with respect to the iteration number i of Iterative SRO for different choices of sketch size ni, and the maximum iteration number of Iterative SRO is set to N 10. It can be observed that the logarithm of approximation error drops linearly with respect to the iteration number in most cases, evidencing our theory that the approximation error of Iterative SRO drops geometrically in the iteration number.
Figure illustrates the approximation error of Iterative SRO in red curve for ridge regression, which |30)331 1Ix
The blue bar represents standard deviation caused by the random data sampling and the random sketching. A single projection matrix P is sampled for each sampled data, and this projection matrix is used throughout all the iterations of Iterative SRO, in contrast with Iterative Hessian Sketch (IHS) (Pilanci & Wainwright, 2016) which samples a projection matrix matrix for each iteration of the iterative sketch procedure.
C.2 GENERALIZED LASSO
Spurse Subspace Dmsbeoding
Grussian Subgace Embroling
0.3
0:11
3.058
0.102
3103
0
y=3
y=
y-9
y=
y=10
Figure 4: Approximation error of Iterative SRO vs. SRO for GLasso with respect to different sketch size n. Iterative SRO and SRO are equipped with either sparse subspace embedding (left) or Gaus- sian Subspace Embedding (right).
In this subsection, add more details to Section 7.1 of the paper for Generalized Lasso (GLasso) (Tibshirani & Taylor, 2011). The optimization problem of GLasso studied here is d-1
3 = mingin f - xx312 + Σ 1 Bi+1l. which is solved by Fast Iterative Shrinkage-
==1
Thresholding Algorithm (FISTA) (Beck & Teboulle, 2009). We construct D E (d-11) by
setting Da, = 11, D = 1 for all E [d - 1], then Σ B. Bital || Let
D Dext 0,...,1 with D = 1. Denote
Dext B, then B
(Dext) -1 / be-
cause Dext is nonsingular. The instance of GLasso considered above is then rewritten as B
arg gin
1 2m
Iy - X (D ext
nud which can be solved by FISTA.
C.3 SIGNAL RECOVERY BY LASSO
We present experimental results for signal recovery/approximation by Lasso in this subsection. In this experiment assume linear model y X + where X = X/vnn, y 8/vn, w ( I.) is the Gaussian noise with unit variance. The optimization problem of Lasso considered here is 3 arg minger 1 Ily X312 + Al|/311- We set À = 0.1 / Vllo d/n, sparsity ø |3 log d], and choose the unknown regression vector 3 with its support uniformly sampled with entries + + with equal probability. We randomly sample X E Rnxd of rank not greater than n r 100 with n = 5000 and d 100000 using (48) so that X a low-rank matrix satisfying RIP. That is, X = UUT 52 with E grxr and Ω e gnxd, U is sampled from the uniform distribution over the Stiefel manifold Wr"R"), the elements of Z are i.id. Gaussian random variables with Di ~ (O, 1/r) for E [n].] E [d]. We let ń = Frank(X) where 7 ranges over (12, 14, 16, 18), and sample X, 9 and w 100 times for each y. Figure 5 illustrates the approximation error of SRO
|| and ||a\~_ respectively, for different choices of sketch
and Iterative SRO, i.e.
16

---

Published as a conference paper at ICLR 2025
size á with different 7. It can be observed that Iterative SRO significantly and constantly reduces approximation error of SRO.
Table 2 shows the enror of approximation to the true unknown regression vector / by SRO, Itera- tive SRO and the solution 3 to the original problem (1). The error of approximation to / is the fe-distance to B3, for example, the error of approximation to /3 for f is 3 - - Standard de- viation is caused by random data sampling and random sketching. It can be seen that Iterative SRO approximates the true regression vector much better than SRO with the sketch size ń being frac- tion of n, especially with Gaussian subspace embedding. More importantly, Iterative SRO and 3 have very close error of approximation G. justifying our theoretical analysis. This is because that our theoretical prediction in Theorem 4.1 for the error of approximation to / by Iterative SRO is V &log d/n).
which is the same order as the error by 3r.
Sparse Subspace Embedding
Gaussian Subspace Embedding
0.15
0.08
0005
0,06
0.1
5043
0.04
0.05
0:51
0.02
0012
0
12 12
7= 14 7=16 7=
7= 12
7= 14
7= 16 y= 18
Figure 5: Approximation error of Iterative SRO and SRO for Lasso with respect to different sketch
size ñ = -X)nnk()). Iterative SRO and SRO are equipped with either sparse subspace embedding (left) or Gaussian Subspace Embedding (right).
Table 2: Approximation error to the true unknown regression vector 3 by SRO, Iterative SRO and the solution 33 to the original problem (1) for Lasso.
7
12
14
16
18
Eiror
SRO
0.115
0.149
0.063 + 0.023
0.059 + 0.010
0.025
0.054
Sparse Subspace Embedding
Iteratic SRO
0.010
0.017
0.009
1 0.009
0.004
0.002
0,008
0.005
(
0,008 1 0.002
0.007 1 0.006
0.003 1 0,001
0,006
0.004
SRO
0.067 + 0.092
0.043 4 0.066
0.044 1 0.038
0.046
0.030
Gaussian Subspace Embedding
Iteratie SRO
0.008 + 0.003
0.008
+ 0.007
0.004
+ 0.002
0.003
0.004
13b
0.007 1 0.001
0.006
1 0.003
0.003 1 0.001
0.002
0.002
C.4 APPLICATION IN LASSO SUBSPACE CLUSTERING
We demonstrate application of SRO in subspace clustering in this subsection. Given a data matrix X E Rxd comprised of d data points in Rn which lie a union of subspaces in R". classical subspace clustering methods using sparse codes, such as Noisy Sparse Subspace Clustering (Noisy SSC) (Wang& & Xu, 2013), recovers the subspace structure by solving the Lasso problem
3 arg min BER
1 2n
X
x,31 + A|1B11, B,=0,
(17)
for each i [d]. X' is the i-th column of X. which is also the i-th data point, À > 0 is the weight for the el regularization. Under certain conditions on and the underlying subspaces, is proved by (Soltanolkotabi & Candés, 2012; Wang & Xu, 2013) that nonzero elements of ( cor- respond to data points lying in the same subspace as X and in this case 3 is said to satisfy the Subspace Detection Property (SDP). It has been proved that SDP is crucial for subspace recovery in the subspace clustering literature. By solving (17) for all i E [d], we have sparse code matrix 3= , ........,.. 3d E Rdxdd and a sparse similarity matrix W is constructed by W | Spectral clustering is performed W to produce the final clustering result of Noisy SSC. Two mea- sures are used to evaluate the performance of different clustering methods, ie. the Accuracy (AC) and the Normalized Mutual Information (NMI) (Zheng al., 2004). In this experiment, we employ
17

---

Published as a conference paper at ICLR 2025
SRO to solve the sketched version of problem (17) with ñ 15. Note that SRO is equivalent to It- erative SRO with N = 1, and we do not incur more iterations by Iterative SRO since SRO produces satisfactory results. Figure 6 and Figure 7 illustrate the accuracy (left) and NMI (right) of sketched Noisy SSC by SRO with respect to various choices of the regularization weight on the Extended Yale-B Dataset. The Extended Yale-B Dataset contains face images for 38 subjects with about 64 frontal face images of size 32 x 32 taken under different illuminations for each subject, and X is of size 1024 x 2414. SRO-GSE stands for SRO with Gaussian subspace embedding, and SRO-SSE stands for SRO with sparse subspace embedding. We compare SRO-GSE and SRO-SSE to K-means (KM),, Spectral Clustering (SC), Sparse Manifold Clustering and Embedding (SMCE) (Elhamifar & Vidal, 201 I) and SSC by Orthogonal Matching Pursuit (SSC-OMP) (Dyer et al., 2013). It can be observed that SRO-GSE and SRO-SSE outperform other competing clustering methods by notable margin, and they perform even better than the original Noisy SSC for most values of X, due to the fact that sketching potentially reduces the adverse effect of noise in the original data.
the Yales
0.3
62
32
83
03
0.6
0.7
39
03
03
0.4
35
3.5
37
0.
63
Figure 6: Accuracy with respect to different Figure 7: NMI with respect to different val- values of À on the Extended Yale-B Dataset ues of À on the Extended Yale-B Dataset
C.5 SKETCHING FOR SPARSE NONCONVEX LEARNING WITH CAPPED-E REGULARIZATION
3.5
Capped (Origina))
3.0
Capped-Li (SRO)
Parameter Estimation Ermr
2.5
2.0
1.5
1.0
0.5
0.005
0.020
0.050
0.200
0.500
Figure 8: Illustration the parameter estimation errors of SRO for sparse nonconvex learning with capped-E! regularization.
We study the performance of SRO for sparse nonconvex learning with capped-E" regularization in this subsection. The optimization problem considered here is 3 arg min llly X,3 +
d-1
min (1B1,,a), which is solved by the proximal gradient descent. X - VnX E nod has
i..d. standard Gaussian entries with n = 10000 and = 40000. Following the setup in (Zhang, 2010b), the true parameter vector is generated with nonzero elements uniformly distributed
18

---

Published as a conference paper at ICLR 2025
from [10, 10). The response vector is generated by y X,3 + where is a noise vector of L..d. Gaussian elements with variance o² = 1, and y = vny. We set a = 10A, the sketch size n/55, and repeat the experiment for 100 times. The ee-norm parameter estimation enrors for different values of are illustrated in Figure
D PROOFS
We present proofs of theoretical results of the original paper in this section.
D.1 PROOFS FOR SECTION 5 AND SECTION
Before presenting the proof of Theorem D.2, the following lemma is introduced which shows that subspace embedding approximately preserves inner product with high probability.
Lemma D.I. Suppose P is a (1 + -ssubspace embedding for X, and let C(X) denote the column space of X. Then with probability 8, for any two vectors u E C(X), C(X),
u P u |v| I I |vll2e.
(18)
Proof. If u = or v = 0, then (18) holds trivially. Otherwise, let = ||u u v
[|vl,_
and u', v' E C(X).
According to the definition of (1 E) e -ubsspace embedding for X, with
probability 1 5,
(1 e)]lu' + v' "12 $ [P(u' + + (1 e) + v
(19)
(1 e)]lu' - v' v12 < PP(n' -3'vll < + +)]l v112
(20)
Subtracting (20) from (19), we have
- p'
(21)
and (18) holds by scaling (21) by ||
D.2 GENERAL BOUND
Theorem D.2. Suppose 3 is any critical point of the objective function in (2), 8 is any critical point of the objective function in (1), and < 6n where eo is small positive constant, 0 < 5 < 1, P is drawn from an (e, oblivious (e-subspace embedding over ñ x n matrices. Then with probability 1-
(1 (1-=) / B- 2
- 0
-
-
Br
110 s On, (3" .)|la= (0',
8 + ki 1
3- g01 (22)
In particular, P is Gaussian subspace embedding, then ñ O(rr log ) 2). If a sparse subspace embedding, then ñ = O()2 (()=)))
It can be verified that the degree of nonconvexity vanishes with 0 when h is convex. As a result, we have relative-crror approximation bound for 3 - 3 x
shown in Theorem D.3 below.
Theorem D.3. If hy is convex, then under the conditions of Theorem D.2, with probability 1-8. 8,
3
3-
|8
(23)
X
Moreover, the Frechet subdifferential of is Lp, Sa.sSmooh (h can be nonconvex), then
|| - -301lx (1-
| lxx
(24)
Al.
can be observed from (23) that one-time SRO renders a (3) relative-crror approximation (3). The Iterative SRO algorithm takes advantage of such relative-error approximation, and it applies SRO once at each iteration so as to approximate the residual of the last iteration with relative-error ap- proximation
approximate the solution to the original problem geometrically. Detailed proof of the theoretical guarantee of Iterative SRO, Theorem 3.1, along with the proofs of Theorem D.2 and Theorem D.3, presented in the next parts of this appendix.
19

---

Published as a conference paper at ICLR 2025
Proof of Theorem D.2. By the optimality of B*, we have
X X3 y x + v =1
(25)
for some (3)) In the sequel, we will also use ah(-) indicate element belonging to x (.) if special note is made.
By the optimality of 3", we have
X3 y X u/12 =0 0,
(26)
where E (3x)
Define A 3 - B = (8t) (1x(33)) By (25) and (26), we have
x X +v x X3 - u = x - x x,3 + +11
=0.
(27)
It follows from (27) that
A T x X
x T X33 + A) S |اl|ا
X X x X33 + +1
=0.
(28)
2
On the other hand, the LHS of (28) can be written as
X x +
A - +AT (x X3' -
T A.
(29)
By (28) and (29), we have
x X6 - + T X -X xxx0'==== < A
-
(30)
Now we derive lower bounds for the two terms on the LHS of (30). First, we have
A - xTx0) = A XA 2 (1 =
(31)
Moreover,
AT x X x -xx0'= = (X -xXXxXxxxx 33 - - |
(32)
Plugging (31) and (32) in (30), we have
(1 XAI al x|| || X,3* 112 < A
(33)
Moreover, by the definition of degree of nonconvexity in (15),
- 0,' .))lār- , -3r
2 3
3
1r -3a
(34)
2
(22) then follows by (33) and (34).
Proof of Theorem D.3. When hy is convex, then its Frechet differential coincides with its subdif- ferential. As a result, for any u E Öh(s) and v E Öh((), we have (s - t) (u v) Z 0, and follows that
(s T) (u v) s 0.
(35)
20

---

Published as a conference paper at ICLR 2025
With 0, (35) suggests that
Ohg (t, = sup søt
{
[s t|l2 (s ()) -hhx(t))) 50,
(36)
By (22) in Theorem D.2 and (36), setting k. = O, we have
(1 (1- - -
3-
||5-1|x x=
S (8", 3r 50.
(37)
If 18 3 - 3r x
* 0, it follows from (37) that
- - 6 - | llx
(38)
Because the Frechet subdifferential of h is Lm-smooth, namely supucěn(x), ve ||u vll2 v [A]|x ||x 15--yl yl12, it can be veried that 0% (x", x) S with holds with Ln. This is due to the fact that for any (l)(x) and any v E (y),
- (s T) (u - v) - Li ||
-t1/2 s ||s - -tllll/uu v112 Lnl[s t1/2
- | y12 Ln||s
t S 0.
(39)
Therefore,
(s - t) (u v) Lnl[s tl2
0n (t, Lm)
sup SER wEEKsssse..ccch)eeeee
(40)
|s t|/2
holds for arbitrary t. and follows that (x",, L,) < 0. Moreover, since X is nonsingular, ||
31
1
8² 1xx
Plugging the above results (22) of Theorem D.2 and setting x to LR, we have
o (X)
(1 - 3 BB
-=11=-~-"" 1x11111 S (3 L.)1 - B*1l2 + 1 - 3
Lh
|1
1
(41)
X
min
and it follows from (41) that
113- - -3"11x 5
8
||
(1-E)
minn (X)
Proof of Theorem 3.1. This proof mostly follows from the proof of our main Theorem D.2 and Theorem D.3. We first consider the that hy is convex.
Let 3. = =3((). Define A = 3 - B Â = (ōhx(3*) 0h)(B")). By repeating the proof of Theorem D.2 and Theorem D.3, with probability 1-8. 8,
(1 X XA 2
X1,3*
B
S A-A
(42)
follows by the proof of Theorem D.3 that XA Â
< 0. As result, follows by (42) that
3 3
3+
< x
E
0r ((1-1)
(43)
E
x
For a constant 0 < p < 1, by choosing E E
p in (43), we have p+1
||300 -3 s pp|03 gr g 1)
(44)
x
for any t 2 1. It follows that
|[aLV] - x S 11 l|x
(45)
21

---

Published as a conference paper at ICLR 2025
with (00) O.
A similar proof is applied for the case that h2 is Smooth and X has full column rank with C (X) < E. It can be verified that (42) still holds, and it follows from (34) in the proof of
Theorem D.2, (39) and (40) in the proof of Theorem D.3 that
- S (3, Ln)
8r
11 + Ln 3 8r
1-
La o (X)
(46)
It follows from (42) and (46) that
3 - 3- X
11(11((111)
(47)
La (X)
x
For constant O < p < 1, by choosing S p(1 p(1-Ln/omin (X)) in (47), we still have ||3(0) -
1x11x S
p+1
p||33 3((-1)| for any & 2 1. follows that || - 3r 1lx S 11
D.3 PROOFS FOR SECTION 4: SKETCHING FOR SPARSE CONVEX LEARNING
In Theorem 4.1, we showed that for low-rank data matrix X with ran r < n, then the Iterative ROS described in Algorithm applied on the sketched problem (2) achieves the parameter estima- tion error of the order O ( (válog d//1) under Assumption 1. As explained in (Yang et al., 2016), Assumption is weaker than the Restricted Isometry Property (RIP) in compressed sensing (Candes & Tao, 2005a). We show that there exists low-rank data matrix X satisfying Assumption 1. We first show by Theorem D.4 that there exists a low-rank data matrix X which satisfies RIP(5, s) for 5 E (0, 1) and s E N with RI s) defined in Theorem 4.4(b).
We define the necessary notations in the following text. Let A be a matrix and S be a set, we denote by Ag the submatrix of A with columns indexed by S. Similarly, for a vector v, Vs is vector formed by elements of v indexed by S.
Theorem D.4. Let 6 (0, 1) and s E N. There exists a data matrix X E Raxd with rank not greater than Cn for a (0, 1) such that RIP(ō, s) holds with probability at least 1 2d (1 + 8)* exp (6)) 2d (1 + })² (-p"0) where og (0, is arbitrary
positive constant, (1)) is positive constant depending on e₁ and 8. Here 2 (0(s log d)) RIP(5, 8) means that for all v E RRdd || S
(1 8) 2 < vX X S (1+ 1)
Proof. We construct the data matrix by
x= UU Ω
U E Raxr , Rad r==
(48)
where U is an orthogonal matrix and UTU I, all the elements of Ω are i.i.d. Gaussian random variables with 2. ~ 1/r) for E [m].j E [d]. It is clear that the rank of X is bounded by nyn.
We define the set
F
U |||
Fs,
Fs fue Rd ||un|| = 1, supp (u) C CS}.
Given set S C [d] [S] s, let V E Fs. define functions
F(v) c1 Av
1
UU JUTAvI? Av
g(x)= = 1 | x x|
where A V7 and the elements of A are i.i.d. standard Gaussian random variables. It is clear that F(v) = g(Av/|lAv]))) and g is 2/ -Liischht function. Moreover,
1
E Ex-Unit 1) [g(x)]
E Ex-Unif(3> 1) [UUT xx ]UU]]
C1
22

---

Published as a conference paper at ICLR 2025
11
= - Av/|Avll then x ~ Unif(s" and F(v) g(x). It follows by Lemma D.9 that
Pr(1o(x) E. [x(x)] > t - exp (-neft²/8)
(49)
It follows by (49) that for a given E Fs, Pr F (v) 1| < f 2 1 eex (-ncit?/8)
On the other hand, v xx = 1/r | T Av : and v x Xv
|Av n.. F(v). Not- ing that ||Av|l2 is x², it follows by standard concentration on x2 that | | 1
S (69))
when n 2 no(6, oo). where no (6 oo) is positive constant depending on 8 and og- Let t = ( in (49) w.h.p. (with a high probability) then [F(v)- -0 1|
< O(8²) w.h.p. By choosing proper constants in @(d²) and choosing the constant no (6, an) accordingly, we have |Av|2/ F(v) -1 - 82/4 w.b.p. In particular, for a given v E Fs. with probability at least 1- (-xee(=))))))) 2 exp (-n*)), we have |V Xx - 1| - 6 /4, and |||v [| 1 6/2.
It follows from (Vershynin, 2012, Lemma 5.2) that there exists an 6/4-net Noya(Fs, 11-112) S Fs of Fs such that (Fss |1-1122 I (1 )) Using the union bound, with probability least 1
2 (1 + 8)* (-pc- (6) 2 (1 + )) exp (-n""), the event that ||Vll 1 I 8/2 holds for
all E N5/4 21)) happens. Define this event as As, and the following argument conditioned
on As.
We define A as the smallest number such that |Xv|l S 11+A for all v E Fs. For any v Fs. there exists v' E No)a(FFs, (1-112) such that ||v v'11 S 8/4. result,
8 + (1+ A)
Xvll2 < [ 2 + |X(v - (x)lvvv)ll - + 2
4'
follows by the definition of A that S 8/2 + (1 + A)6/4, so A
S
36/4
S 8. We then have
1-6/4
[Xvll2 I 1 1++ 5 for all v E Fs. On the other hand,
8
Xxv 2 Xv'l2 - |X - 122l2 2
2 - (1 5) 4
2 11-8. 5, Vv Fs.
As a result, conditioned on the event As for a set S [d. Ss| s, || 1 S 8 holds for all v E Fs. Because [F] I dd, using the union bound, with probability specified in this theorem, [||xv|22 - 1 S holds for all v E R2, l|vllo Ss. 8.
Low-Rank Matrix X Satisfying Assumption 1. It is proved in Theorem D.4 that the low-rank data matrix X constructed by (48) satisfies RIP(6, s) for 8 (0, 1) and N. By making og - 1, the lower bound for n is (0(s log 2/ao which can be close to the sample optimal ( log d). As indicated by (Yang al., 2016), The condition (11) in Assumption 1 is weaker than RIP. To see this, (11) holds with k = (s / if RIP s) holds with s = 58 and = 1/3.
An Alternative Construction of A Low-Rank Matrix Satisfying s)) It is remarked that one can also construct the low-rank matrix X XUA where U E Raam is sampled from the Stiefel manifold Vr (R²) comprising all the
m matrices of orthogonal columns with n. 2 m, and all the elements of A E Rd are i.i.d. Gaussian random variables with Aij ~ _O0 1/m) for i E [m].] j E [d]. Then rank(x) < m, and it follows by (Baraniuk et al., 2008 Theorem 5.2) that when m > ( log d), then A satisfies RIP(6, s). Since X = A A, it follows that w.h.p. X also satisfies RIP s). The latter construction can admit the optimal size n x O(s log d). On the other hand, rank(X) + as d + oo in latter construction, while the construction in Theorem D.4 allows for arbitrarily specified rank of the constructed X.
We need the following lemma for the proof of Theorem 4.1.
Lemma D.5 ((Yang et al., 2016, Lemma 5)). For any v E Rdd and any index set S S [d]] with |S| 5. Let J be the set of indices of the largest k* elements of v. in absolute value and let
23

---

Published as a conference paper at ICLR 2025
I= J.JUS. Here á and k- are the same those in Assumption 1. Assume that |/s=l11 S 111vs for some 7 > 0. Then we have l|vll2 I (1+ 22.. and
vX vX Xv Pc, (IvEll2- 1 v pc.+
(8 2 1/|vsl|) ||
(50)
Proof of Theorem 4.1. We consider the upper bound for the quadratic form
V(((*) VC(3), 3 B) x where 3 B(x) and A = 3 B. We
define S supp (3). Let be vector, denote by vss the vector formed by elements of in the set S.
We have
A X XA
(V((T) V2 -B)
(V((3)) ). 3- - -3) + ||V[(() |All
1
log d
(V((3)) - VC(B)) 3r - B) + -V -3)+ + +20
|
n
VC(0) Ve( || |A \145 + +1/AAsl1+ + 2 -|al
>p/lAl1 111 A| - -M1AA1
--2 --1(1-10 -1- -
2) | + +1 11 n + 2) ||sslI..
(51)
Here ! follows by Lemma D.8, and PK |||||| 21|ا0111 11x S Ap in @
It follows by (52) that ||As~11, ||, S ((1 + - 2/c) (1 - - 2/c)) 1|
2/c). It fol- lows by Lemma D.5 that || ll < (1 + |اZZ| Moreover, follows by Assumption that PC.+ p/c.) (2k. + 8) S 0.5k /3. Plugging this inequality in (50), we have
We now apply Lemma D.5 with v = A and = (1 -1- 2/c)/(1
AX > pc, - (5)
- 1||As|12 | | - 3// V (k.,
2 Pc.- (5 + k*)
(1 (v.5) |1
(52)
It follows from (51) that A XA
S > (1 + / 2) ||sl|| $ A(1 + 2) V Azl12 It
follows by this inequality and (52) that
(1+ + (1+ VEA
|lll2 S (1 (1+1)1A4Z12+
Pc. (z. (8+ (1 (1-7v0.5)
which proves (12).
D.4 SKETCHING FOR SPARSE NONCONVEX LEARNING
Proof of Corollary 4.2. We have hx3 \|[B||, + Qx()). For any s E Rd, t E Rd. and let u (h)(s), V E (t), then u =1 + (s)(s) and v = & + VQ)(t) with x₁ E (A(ssl,, and
X2 E θ (A/ )). We have
(() -(s -ss- - t) (u - v) = -(s- t)T (&I - -)) - (s- - T)T (VQQ((s)) - -Vx(())-VQ(())
1
< -s ((--)) T)T (v) vQa(t))
24

---

Published as a conference paper at ICLR 2025
Ç- ||s tl|2:
(53)
where ① follows from the convexity of A|I-III and @ follows from the regularity condition (b) in Assumption 2.
follows by (53) that the degree of nonconvexity 0n, (-) 2 O. Using the upper bound for ň in the given condition, plugging th, (t, (-) = (22) and setting Ç-, we have
(1 - = 3 x
-e cell g 11 (3" Ln) 0 B
5- 3
<< 3 3r 3112
(54)
By the definition of sparse cigenvalues in Definition 4.1, we have
3
3
2 PL, (s)
3 3
X
3
B*
S PC,+ Pc,+(s)
3 B
x
Applying the above inequalities (54), we have
(- s²1. se se (c)
+ +c|100 -3-
(1 - (_-))pc-(s))
which leads to (13).
Definition D.1. (s-net) Let (X, be metric space and let 0. A subset N& d) is called an e-net of X if for every point æ E X, there exists some point y E Ne(X, d) such that d(æ; y) S s. The minimal cardinality of an E-net X, if finite, is called the covering number of X at scale
Theorem D.6 (revised version of (Woodruff, 2014, Theorem 2.1) with explicit constant in the bound for ū). Let 0 < 6, < and P E IR RR be a Gaussian subspace embedding defined in Defini- tion 2.2. Then if ñ 32s-2 log(25o/ ()) P is Johnson-LLindenstrauss Transform, JLT(s, So)- That is, for any set V with fo elements and all v, v.ve e V, with probability at least 1 8, it holds that (Pv, Pv') (v, v'l < =||v||||||v/|
Lemma D.7. Let & E [4. 8 2 2, < 8,8 < 1, and P E Râxa be Gaussian subspace embed-
ding defined Definition 2.2. I 2 coE 2 (log(2/0) + s log d + s log + 1/d"-1) where eo is positive constant, then with probability at least 1 - 6, the following inequalities hold:
PE. (s) S Pc.+ (8) + t S.
PE, (s) 2 Pc.-(s) =V53
(55)
Vi(B) 06
VC(3) |I + +
(56)
Proof of Lemma D.7. Define the set
F
Js.
Fs = {u Rd supp (u) CS).
SCId Sd
Then |F| = (9) < d We now consider the subspace
Uls = u Xv
||ا|| = 1, Xv for some v E Fs}. S S [d]. [| s.
can be verified that the dimension of Us is not greater than s. Let y > 0, follows by (Vershynin, 2012, Lemma 5.2), there exists 7-net (Us, l1-112) Us of Us such that (N, 11-11221 s
(1+2)
Define the set
V =
U -S
21
U
U N (1,2 (1.11)) iE(d]
25

---

Published as a conference paper at ICLR 2025
d where e is the subspace spanned by {e',8) where {e') i= is the standard basis of R As a result of the above argument, fo := [/.l v (9) 5 + 25d. It follows by standard calculation that (2)) - s log d + log 1/d"-1
log(2fo/0) /0). It then follows by Theorem D.6 that when n 2 coc 2 (10g(2/0) + s log d + s log + + 1/d--1)) 2 coe (o=22 (og(2fo/6) with Co 512, P is JLT(e/4 4, 6, fo). Therefore, with probability at least 1 6, P is a (1 = e/4) e-embedding for V..
For any u E Ms, there exists a n' E (Uss, (1-I11)) such that ||u n'|12 S y. We now use the simpler notation (Pu', Pv') = (1 E)) (u', v²) to indicate (Pu', Pv') (u', v'1 s e||u/||2||v'||2 for any two numbers u', v' in the following text.
We follow the construction in the proof of (Woodruff, 2014, Theorem 2.3), that is, we build 1/2- net / (1-111 S Us of Us. Given any S [d], [S] = 8, we now show in the sequel that P is a (1 + e/4) L2 eembeedding for N1,2((4s, (1-111)) that is. (Pu', Pv') = (1 + e/4) (u', v') for all u', v' E (2, l1-112)) then P is also a (1 + a) -eeebedding for Us, that is, (Pu, Pv) =
(1 + E) (u, v) for all u, v E Ug To see this, any u E Us can be expressed by
20
12112 S z.
1
u E 11/12)
(57)
(57) can be proved by induction. By the definition of 1/2-net, there exists un E N1/2 11-112
and u such that ||u - u ||, S 1/2
= u² + (u - -u²). Also, there exists u E 21/2 (1-112)
such that [[((u=u))/lll ))/l u²)
- -u"1 u²112 111 S 1/2, so that u = u + u² + (u (u-w* u - u²)
with u' || u²)ll ll)", u'
2 S
1/2. and ||u u -u'll S 1/2².
As the induc-
k
tion step, if u =
Σ
ui
+
u Σ w for k 2 1 such that || ll2 S
27 for all j E
1=
[0, k] and
u
Σg
u
1/2kt1,
Then there exists t+ E
(2, 11-112)
such that
j=1
& u
k
k+1
+
Σ
u'
/
u1
Σ
w
n++1
S 1/2. As a result, u =
Σ
x+| +
u
Σ
u
1-0
j=l
b+1
where u+1
u
u
1
k+1
<
ui
< 1/2 and
u
Σ
5
j=1
1
1/2k+2.
follows by (57) that
x
|ull
P
u'
1
Pu
1 +2 Σ
Pu' Pu!)
Σ
(1
||00
12- +2 Σ
(u', u') +
1|2 1 112
0=
Kj
Kj
x Σ 1=0
Σ
1 l
+
(u v2)
+ 6
u
2 2
+ >
|u 1al||11
1
112
4
Kj
i<3
2|u1/ 2
+
$
|
1/2
te.
(58)
follows by (58) that Pis (1+)) c eembedding for for Recall that P is c1+)/4) 2 embedding for V. 2 Usc 2N1/((4s, 11-112). By the above argument, P is also a (1 + c) e embedding for Us for any S C [d].
S
= 8.
26

---

Published as a conference paper at ICLR 2025
For any Rd such that l|vllo I 8, l|vl22 Xv/I Xv la E Us. As a result,
1, there must exists set S [d].[S] such that
x v Xv S = SEVE,
(59)
where the last inequality follows by max;e[d] X ll2 S 1. Therefore, (8) S (x)+(() + t and P2,-(6)
(8) 2 (6) -eV8.
Because is a (1 + e/4) e-embedding for V, 2 USen (11(ee)),11112)) is embedding for ( for all i [d]. Therefore, we have
is also (1 8) 62-
sup e² iE
[ X3 - xxxxxxx
B s Xc:ll2 X
so that
VE(B)-
= -| x
X,3 X x
supe' (x ic(d)
1 xTx) B
< Xe
Xe'
X
S
Proof of Theorem 4.4. It follows by (55) Lemma D.7 that
P2. (s) Pc, (s) ev > 0
with 80 = 8 + 28. Moreover, it also follows by (55) that
C² (3+ 2 C' (p 23) - =V3 28 2 25-.
In addition, by (55) have
R¹ PC.+ + 50 St (20) - -St
Pc.- E /80 - C- PE. (80) -
with ă specified in Assumption 4. Therefore, if (144x/2 12 + 250m') 5 (144%2 + 2508) Čss which completes the first part of the claim.
< 5, we have
Now we need to verify that either condition (a) or condition (b) can lead to the following conditions:
(c.) //50
(60)
Ç- < C² (pc,- - -EV80)
(61)
(144h²² 250k') 8 < 8, n¹ = (pc.+ (80) + EV800 (-)/ - 8V300 (-).
(62)
For condition (a), with log d/n "030 0, == Clgod/// we have "= 0. It can be verified that R "=3"" Ki, and (60)-(62) holds with sufficiently large n when Assumption holds.
For condition (b), with Ç- = Copc. (s)), / s (s),, C2+C3s < and C2 S C1-)-3s), (60)-(61) hold. Moreover, we have
R<' Pc.+ (So) + 50 S+ (c,)(so) 30 5- As result. 3 (144k] 250mg) leads (62).
< Ca+c, < (a) + +0)
(1 C2 Cs) (1 C2 Cs)(1 = Ki-
Proof of Theorem 4.5. It follows by (56) in Lemma D.7 and Lemma D.8 that
V < |Vc33) + + < (Civ3| + 20)
log d
(63)
27

---

Published as a conference paper at ICLR 2025
Let Augi - 8
B112 + 20) V logd Because Assumption 4 holds, we can apply the approx- n
imate path following method described in (Wang al., 2014, Algorithm 1) to solve the original
problem (1) and the sketched problem (2) obtain 3 and 3 such that 3 is an critical point of
problem (1) and 3 is an critical point of (2) with X PX and nonconvex regularizer Aay Let
= supp (3). We can repeat the proof for (Wang et al., 2014, Theorem 5.5) and conclude that
1 l1 S 8,
|
- 3.
The above inequalities show that supp (x 3:) -3- U supp Usupp (3r) S 80 = 3 + 23. then follows by Corollary 4.2 that
E/ PC,+
0 -
$ (1 - =)pc. 5- |1
(64)
In addition, it follows by (Wang et al., 2014, Theorem 4.7, Theorem 4.8) that the parameter estima- tion enror of 3 satisties
3 - (21/8)//ppcc (-) VoNggi-
(Pc.-
(65)
It follows by (65) and (64) that
E c (5 + p)
( - 1/111- S
-
11,3
(1 + C2)/2 PC, (80)
Ç-
E/ (3 + 3) pc)
E (3 3)pc,+(50)
||
(21/8)/ (pc. - 5-) V
(1 + C²) /2 PC, (50)
(1 C2)/2 12. PC. (80) 6-
8/ (8 + 8) Mc,+ (80)
V
|3
(1 + C²)/2 PC, (80) 5
8 (pcc (80) 5-)
C1 | / (1 pL (80)
$ $logd d
Vodigt
- (1 + / Pc, (su) -5-
+ 8 (pc.-(88)) - -5-)
(66)
(14) then follows by (65) and (66).
Lemma D.8 ((Zhang, 2010c, Lemma 5)). Under the linear model in Section 4, that is, X,3 + where E is noise vector of i.idd sub-gaussian elements with variance proxy o². Let X X VT,
= 8/ Vn, and C(3) = 1/2 B X33 yy XB. Then with probability at least for any
n E (0, 1).
log log(2d/n)
|V S V20V
(67)
11
Lemma D.9 (Aubrun & Szarek, 2017, Proposition 5.20)). Let d > 2. If 8d8d111 - as 1- Lipschitz function, then for any >>
Pr [r[ E [[())] > 4 exp (-di² 12)
(68)
where x is drawn uniformly from the unit sphere gd-1 in Id..
28


Reviews:
[{"review_id": "uWGMdYKmzm", "reviewer": "Reviewer_2raj", "summary": "The paper introduces an extension of the Iterative Hessian Sketch from Pilanci and Wainwright to the regularized setting. The authors first show convergence of the algorithm for sparse signal estimation (i.e. the LASSO) for both the traditional l1 norm as well as for a non convex penalty. In both cases, under various assumptions,  they are able to derive a minimax error  bound on the deviation between the N^th iterate of the single step algorithm (which they call SRO and which amounts to a minimization of the sketched formulation) and the groundtruth. They then extend their result to a general convex setting and show how to improve convergence by means of an iterative version of the SRO algorithm which is essentially an extension of the IHS algorithm from P and W to regularized formulations.", "questions": "- line 30 “Sketching algorithms has been used to approximately” —>  “Sketching algorithms have been used to approximately”\n- line 62, Equation (30) the lines 129-131 should appear way earlier. In particular, you want to better motivate the fact that the sketching is restricted to the quadratic term. I understand that restricting the sketching to the quadratic term might improve convergence but is that really necessary? If you still need to compute the product y^TX when do you the gradient descent, isn’t that equivalent to the X^TX*\\beta ? I.e. in the latter you just have 2 more applications of a vector to the matrix X.\n- line 68, you give the definition of the semi-norm ||u||_X twice \n- line 116 I would use the cardinality of the support to denote the number of non zero elements of a matrix X instead of introducing the notation nnz. I.e. |supp(X)|. It is a detail though\n- line 123: “It is comprised of ” —> “It consist of”\n- lines 125-127 are quite obvious to me. I think you could just remove them\n- line 136-140, in the Definition 2.1. is there any reason you use \\ell^2 instead of \\ell_2 ?\n- line 142, Definition 2.2. looks more like a proposition (Lemma  perhaps) to me. \n- line 151 : “Taking derivative with respect to” —> “taking the derivative with respect to”?\n- line 189-190 “is a more accuracy” —> “is a more accurate”\n- line 170 “consectively” —> “consecutively” or “iteratively/alternatively”?\n- The structure of the proof sketch for Theorem 3.1. is good but your exposition of formulations (5) (6) and (7) is unclear. You should either keep the formulation from (6) to (7) (aside from the sketching) or provide at least a to (short) sentence indicating that (7) is obtained by moving the \\beta^{(t-1)} out of the quadratic term to the linear term.\n- Lines 295-296, Statement of Assumption 3, is the concavity parameter \\zeta_- that you introduce in Assumption 3 the same as the zeta_- that you use in Assumption 2? if so it should be clarified in Assumption 2 (i.e. you could say something like “where zeta_- is known as the concavity parameter” or slightly modify Assumption 3 by saying “The concavity parameter \\zeta_- introduced in Assumption 2…”)\n- In the statements of Theorem 4.1, Corollary 4.2, Theorem 4.5 (this is especially true for Theorem 4.5), I would remove the explicit constants. The relation between the values you get for \\tilde{n} and the constants is not clear anyways so those should go (keep the \\varepsilon/1-\\varepsilon for Corollary 4.2). If you really want you can add a one line sentence for Corollary 4.2. indicating how they depend on \\rho_{\\mathcal{L}, +} and \\rho_{\\mathcal{L}, -}. \n- I recommend that you change the statement of Theorems 4.1, 4.5 and 5.2. so that they look more like the statement of Corollary 4.2. in terms of how you introduce the \\tilde{n}. I.e. the lower bounds on \\tilde{n} should not be introduced as a side comment. \\tilde{n} should appear before you introduce \\tilde{\\beta}. E.g. Let \\tilde{\\beta} denote the solution to (5) with a sketching operator of size \\tilde{n}\\times n (or even better “for the sketching parameter \\tilde{n}…”)\n- I’m not sure Figure 1 is really meaningful. It only indicates a constant reduction in the relative error. What is more interesting is a bound such as (8)\n- Lines 403-407, Definition 5.2. From what I understand, the degree of non convexity for a particular value of kappa gives you a measure of whether the function is more convex than the function \\kappa \\|x\\|^2 ? I.e \\theta_h will give you a negative value if the Hessian of the function is more psd than -\\kappa I and positive otherwise? Remark 5.1. could be clearer\n- Lines 416-420, in the statement of Theorem 5.2., what do you mean by an “oblivious” \\ell^2 subspace embedding? Are you referring to an embedding that satisfies Definition 2.1. ? Then why not just say it like that? If you use space to introduce Definition 2.1, leverage it. \n- line 424 - 426 : “by arbitrary critical point ” —> “by any arbitrary critical point”\n- lines 428-431, from what I understand \\theta_{h_\\lambda} is lower bounded by \\kappa? it might be good to add even a short clarifying sentence\n- The sentence on line 430 does not make sense. Do you mean that “if the if the subdifferential is Lipschitz or if \\kappa can be set to 0 then you get an admissible error bound?” If so, this is not what Theorem 5.4. states.  \n- Statement of Theorem 5.4., I would remove the sentence following Equation (17) as it refers to a result that does not appear? \n- I think I would reorganize sections 5.1. and 5.2 . At the end of the day, the two Theorems 5.2. and 5.4 are really steps towards the proof of Theorem 3.1. I would add a one paragraph below this last theorem explaining how you use the degree of non convexity to prove it. This would make it possible to remove the statements of Theorems 5.1 and 5.2\n- general question: wouldn’t it be more efficient to draw a new sketch at each iteration in the iterative SRO algorithm ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well written on the whole. The beginning of the paper remains very close to the paper “Iterative Hessian Sketch: Fast and Accurate Solution Approximation for Constrained Least-Squares” from Pilanci and Wainwright. In particular compare Equation (5) with Equation (25) in this last paper, or (24) with (7).  From what I understand, the main difference lies in the use of a regularizer. An incremental result is not necessarily a bad result but I’m still not fully decided about whether it is sufficiently original to be accepted.", "weaknesses": "The paper is not bad but it should clearly be reorganized. The distinction between the solution of the sketched program and the final iterate of the SRO/iterative SRO algorithms is not very clear. Does \\tilde{\\beta} represent a critical point of (2) or the N^th iterate of Iterative SRO ? This is especially unclear for section 4.2. where the meaning of \\tilde{\\beta} is not clarified in the statements of Corollary 4.2., and Theorem 4.5. but is mentioned as a critical point in the statement of Theorem 5.2.\n\nAlso your key contribution is the sketching step so the \\tilde{n} should appear more clearly in all your statements (see my comments below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gVApsWpYVs", "reviewer": "Reviewer_X44j", "summary": "The paper presents an approach called Sketching for Regularized Optimization (SRO), which can tackle a broad class of regularized optimization problems by employing sketching techniques. This method is applicable to both convex and nonconvex forms of regularization. To address potential approximation errors in SRO, this paper introduces an enhanced variant, that is, Iterative SRO, which systematically reduces these errors at a geometric rate.  A unified theoretical framework is also proposed to establish the minimax rates for sparse signal estimation in both convex and nonconvex settings.", "questions": "Please see the weeknesses part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work addresses a wide range of optimization problems using sketching techniques, effectively handling both convex and nonconvex regularizations.\n2. The introduction of SRO and its refined version demonstrate a well-thought-out approach that balances efficiency and accuracy in solving complex optimization tasks.\n3. This work presents a unified framework that derives minimax rates for sparse signal estimations, solidifying the method's effectiveness for both convex and nonconvex settings.", "weaknesses": "1. This work appears to be a specific case of the work proposed by Yang and Li, ISIT (2021). The similarities include the theoretical framework (such as the general bound in Theorem 5.2),  the algorithmic approach (the SRO and Iterative SRO), experimental design and results (the findings presented in Figure 1 is exactly the same), and even the writing style. Please clarify the differences between these two works.\n2. Please provide more explanation regarding Definition 5.2. For convex functions, the value of theta is less than or equal to 0. So what about the impact of nonconvex functions on this value? For example, what range might it fall within? Additionally, could you provide some examples of nonconvex functions?\n3. It seems that the assumption of full column rank in the explanation below Theorem 3.1 is not realistic for practical applications. In other words, if the smallest singular value is relatively small, would the smoothness constant become very small or even approach zero?\n4. Some numerical experiments on nonconvex regularization should be conducted.\n\nReferences\n[1] Yang, Y., & Li, P.  FROS: Fast Regularized Optimization by Sketching. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 2780-2785.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "HfSd6n14zp", "reviewer": "Reviewer_Y2Sn", "summary": "The article is concerned with the solution of sketch-based solution of regularized least squares problems, i.e. problems of the form $\\min 1/2 \\Vert X\\beta-y \\Vert^2 + f(\\beta)$, where $X$ is a matrix and $f$ is a regularization term. If $X$ is of low rank, it can be well approximated via a sketch, i.e a matrix $\\widetilde{X}=PX$, where $P$ is a random projector. The idea of sketching is to use this fact to reduce the complexity of the optimization problems.\n\nConcretely, the authors propose the iterative SRO method. In SRO, the quadratic term $\\langle X\\beta, X\\beta\\rangle$ of the loss function is exchanged with a term based on a sketch, i.e $\\langle \\widetilde{X}\\beta, \\widetilde{X}\\beta\\rangle$. Since $\\widetilde{X}$ is a matrix of smaller dimension than $X$, the latter problem is less expensice to solve. In iterative SRO, this procedure is repeated to obtain a better and better estimate of the true solution $\\beta_*$.\n\nThe main result of the paper says that as soon as $P$ is an $\\ell_2$-subspace embedding for the random matrix $X$, the iterative SRO will converge at a linear rate towards the true solution $\\beta_*$. The authors also prove a result about applying the method to do sparse regularization - they show that with a moderate amount of iterations, the iterative SRO achieves the minimax sampling rate when solving the LASSO problem.", "questions": "- In the beginning of section D.2, is $O(s\\log(d)/n)$ a typo (should there not be a square root there)?\n- Can the matrix in Theorem D.2 be constructed as I have outlined above, i.e. $X=UA$ with $U$ in the Stiefel manifold (and hence isometric) and $A$ a standard RIP matrix?\n- In the formulation of Theorem 3.2, it is stated that $n\\ll d$ and $\\log(d) \\ll n^\\alpha_0$ -- it is unclear what this means and how it is used later in the proof.\n- Can the authors provide some more details in their proof of their main theorem?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "This article has many positive sides. The research questions of this article are sound, as is the algorithm it proposes. Its results are relevant and the proofs are modulo typos correct. The experimental verification is also reasonable. \nI would like to highlight the generality of the results (there is much freedom to choose both the regularization term and the sketching matrix $P$). I am also fond of the fact that the authors take the time to prove that there indeed are matrices $X$ that are both of low rank (making their sketching approach viable) but still has the RIP.", "weaknesses": "A big problem with this article is its presentation. Let me address some of the problems, in order of appearance.\n- It takes some effort to sort out the relations between the problems (2), (5) and (6) in Section 3 (they are all equivalent - but it is non trivial to realize this due to the notation). Some ironing out of this would be good, possibly with an explicit calculation in an appendix.\n- Many of the arguments in the beginning of proof of Theorem 5.2 are written down in an unnecessarily complicated: Since the vector in (25) is zero, there is no need to apply the Cauchy-Schwarz inequality to arrive at the inequality (26)\n- In equation 35, $\\kappa$ is still present although $\\kappa$ has been set to 0 just before.\n- There are many steps in the proof of the main result that are only sketched, in particular for $L_h$-smooth $h$ -- I think that I can reproduce the steps, but I really think that the proof of the main result of the paper deserves to have this step written out. *This is in my opinion the most pressing issue*.\n- The sentence \"We show that RIP($\\delta,s$)\" has appearantly lost its ending.\n- Reference to equation (45) in the proof of Theorem 4.1 seems to be spurious.\n- The term JLT in Theorem D.4 is undefined - I suppose it has something to do with a Johnson Lindenstrauss embedding. The meaning of $f_0$ is also unclear.\n- Theorem D.6 has no statement.\n\nAnother weakness of the paper, in my opinion, is Theorem D.2. Due to the appearance of the term $\\alpha_0$ in its current form, one needs to use $n\\geq C(s\\log(d))^{1/\\alpha_0}$ to get a sparse recovery, which, due to the unknown size of $\\alpha_0$, could be arbitrarily far away from the sample optimal $s\\log(d)$. This question should at least be discussed.\n\nHowever, I suspect that theorem D.2. can be made stronger. Would it not suffice to just set $X= UA$ where $U\\in \\mathbb{R}^{n,m}$ is in the Stiefel manifold (with $m=cn$) and $A\\in \\mathbb{R}^{m,d}$ Gaussian with $m\\sim s\\log(d)$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "PCwNGUip0C", "reviewer": "Reviewer_HrLh", "summary": "This paper proposes a sketching method for convex and nonconvex regularized least squares and sharp theoretical guarantees are provided for the algorithms.", "questions": "1. This work appears to be a straightforward extension of (Pilanci & Wainwright, 2016) with the addition of a regularization term. Authors should clarify the unique difficulties and challenges introduced by this regularization term. It does mention some differences like sampling the projection matrix only once. However, can this be easily adjusted in (Pilanci & Wainwright, 2016)? In addition, what are the primary obstacles to applying traditional analyses of convex and nonconvex regularizations in a least squares setting without sketching? What are the difficulties by extending the analysis in (Pilanci & Wainwright, 2016)? What are the new techniques introduced in this paper to study the error bound? \n\n2. The notations are not very clear. In the paper, $\\tilde{\\beta}^*$ represents the critical point of the objective function (2). When studying the theoretical properties, is it the solution of SRO algorithm or the solution to iterative SRO algorithm? What are the errors bound for solution of SRO and what are the error bounds for iterative SRO? \n\n3. In Section 3 about iterative SRO, it only concerns the convex regularization for $h_\\lambda(\\beta)$. Is there any particular reason that it cannot be applied to nonvex regularization? How about the error bound for the nonconvex regularization with iterative SRO?\n\n4. The organization of the theoretical guarantees and proof sketch is not very clear. For instance, Corollary 4.2 is introduced before introducing Theorem 5.2, while Corollary 4.2 needs the conditions in Theorem 5.2. \n\n5. In Table 1, why the running time for SRO is longer than those iterative algorithm? The first step of iterative SRO is somehow equivalent to SRO?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of the method is clear and easy to follow.\n2. The motivation is clearly conveyed.", "weaknesses": "Please see following questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)