Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees

## Abstract

Abstract Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose a fast sketching algorithm for least square problems regularized by convex or nonconvex regularization functions, Sketching for Regularized Optimization (SRO). Our SRO algorithm first generates a sketch of the original data matrix, then solves the sketched problem. Different from existing randomized algorithms, our algorithm handles general Frechet subdifferentiable regularization functions in an unified framework. We present general theoretical result for the approximation error between the optimization results of the original problem and the sketched problem for regularized least square problems which can be convex or nonconvex. For arbitrary convex regularizer, relative-error bound is proved for the approximation error. Importantly, minimax rates for sparse signal estimation by solving the sketched sparse convex or nonconvex learning problems are also obtained using our general theoretical result under mild conditions. To the best of our knowledge, our results are among the first to demonstrate minimax rates for convex or nonconvex sparse learning problem by sketching under a unified theoretical framework. We further propose an iterative sketching algorithm which reduces the approximation error exponentially by iteratively invoking the sketching algorithm. Experimental results demonstrate the effectiveness of the proposed SRO and Iterative SRO algorithms.

## I Introduction

Efficient optimization by randomized algorithms is an important topic in machine learning and optimization, and it has broad applications in numerical linear algebra, data analysis and scientific computing. Randomized algorithms based on matrix sketching or random projection have received a lot of attention [, , , , ], which solve sketched problems of much smaller scale. Sketching algorithms has been used to approximately solve various large-scale problems including least square regression, robust regression, low-rank approximation, singular value decomposition and matrix factorization [, , , , , , , , ]. On the other hand, regularized problems with convex or nonconvex regularization, such as the well-known $\ell^{1}$ or $\ell^{2}$-norm regularized least square estimation, also known as Lasso or ridge regression, play essential roles in machine learning and statistics. While most existing research works demonstrate the potential of random projection and sketching on problems with common convex regularization [] or convex constraints [], few efforts are made in the analysis of regularized problems with general convex or nonconvex regularization.

In this paper, we study efficient sketching algorithm for a general class of optimization problems with convex or nonconvex regularization, which is presented as follows:

$$ $\displaystyle\min_{\bm{\beta}\in\mathbb{R}^{d}}f(\bm{\beta})=\frac{1}{2}{\left\|\mathbf{y}-\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+h_{\lambda}(\bm{\beta}).$ (1) $$

$\mathbf{X}\in\mathbb{R}^{n\times d}$ is the data matrix or design matrix for regression problems, $h_{\lambda}\colon\mathbb{R}^{d}\to\mathbb{R}$ is a regularizer function and $\lambda$ is a positive regularization weight. When $h_{\lambda}(\cdot)=\lambda{\left\|\cdot\right\|}_{2}^{2}$ or $h_{\lambda}(\cdot)=\lambda{\left\|\cdot\right\|}_{1}$, ([1](#S1.E1)) is the optimization problem for ridge regression or $\ell^{1}$ regularized least square estimation (Lasso).

We study the regime that $n\gg r={\rm rank}(\mathbf{X})$ where $r$ is the rank of $\mathbf{X}$ in most results of this paper, and it is a popular setting for large-scale problems such as fast least square estimation by sketching []. For example, matrix $\mathbf{X}$ in sparse linear regression is usually low-rank or approximately low-rank in practice. However, our results for sparse nonconvex learning in Subection [V-B](#S5.SS2) hold for $\mathbf{X}$ not necessarily low-rank.

Optimization for ([1](#S1.E1)) is time consuming when $n$ is large, and such large-scale regularized optimization problems are important due to increasing interest in massive data. To this end, we propose Sketching for Regularized Optimization (SRO) in this paper as an efficient randomized algorithm for problem ([1](#S1.E1)). With $\tilde{n}<n$ where $\tilde{n}$ is the target row number of a sketch of the data matrix $\mathbf{X}$, SRO first generates a sketched version of $\mathbf{X}$ by ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$, then solves the following sketched problem,

$$ $\displaystyle\min_{\bm{\beta}\in\mathbb{R}^{d}}\tilde{f}(\bm{\beta})=\frac{1}{2}\bm{\beta}^{\top}{{\tilde{}\mathbf{X}}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}-\left\langle\mathbf{y},\mathbf{X}\bm{\beta}\right\rangle+h_{\lambda}(\bm{\beta}).$ (2) $$

One hopes that the optimization result of the sketched problem ([2](#S1.E2)), denoted by $\tilde{}\bm{\beta}^{*}$, is a good approximation to that of the original problem ([1](#S1.E1)), denoted by $\bm{\beta}^{*}$. The optimization and theoretical computer science literature are particulary interested in the solution approximation measure defined as the semi-norm induced by the data matrix $\mathbf{X}$, i.e. ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}={\left\|\mathbf{X}(\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*})\right\|}_{2}$ where ${\left\|\mathbf{u}\right\|}_{\mathbf{X}}\coloneqq{\left\|\mathbf{X}\mathbf{u}\right\|}_{2}$ for any vector $\mathbf{u}$. Existing research, such as Iterative Hessian Sketch (IHS) [], prefers relative-error approximation to the solution of the original problem in the following form:

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\rho{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}},$ (3) $$

where $0<\rho<1$ is a positive constant. With the relative-error approximation ([3](#S1.E3)), IHS proposes an interesting iterative sketching method to reduce the approximation error ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ geometrically in the iteration number.

### I-A Contributions and Main Results

First, we prove that SRO for a general class of optimization problems in the form of ([1](#S1.E1)) enjoys an universal approximation error bound for arbitrary regularization function $h$ which is Frechet subdifferentiable, that is,

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq Q_{h_{\lambda}},$ (Theorem III.2 ) $$

where $\varepsilon\in(0,1)$ is a small positive number which appears in the approximation error bound to be presented. $Q_{h}$ is a quantity depending on the degree of nonconvexity of $h$. In particular, $Q_{h}=0$ for arbitrary convex regularization function $h$, leading to a preferred relative-error approximation essential to Iterative SRO to be explained soon, that is,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (4) $$

With a small positive $\varepsilon$, the relative-error approximation ([3](#S1.E3)) is achieved. Furthermore, if $h$ is strongly convex, we prove in Theorem [III.6](#S3.Thmtheorem6) that the relative-error approximation also applies to ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}$, the gap between the actual optimization results of the original problem and the sketched problem. If $h$ is nonconvex but not “very” nonconvex with limited $Q_{h}$, we prove that sketching still admits a form of relative-error approximation bound in Corollary [III.3](#S3.Thmtheorem3). Our theoretical results convey a clear message that relative-error approximation “favors” convex regularization, and show how convexity and nonconvexity of regularization affect the accuracy of sketching by the quantity $Q_{h_{\lambda}}$ .

Based on SRO, we present an iterative sketching algorithm termed Iterative SRO which provably reduces the approximation error ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ geometrically in an iterative manner. Albeit being bounded, the approximation error of one-time SRO is still not small enough for various applications. To this end, Iterative SRO iteratively calls SRO to approximate the residual of the last iteration so as to further reduce the approximation error, given the relative-error approximation ([3](#S1.E3)).
More details are introduced in Section [IV](#S4) and Section [VII](#S7).

Second, we study the sparse signal estimation problem by sketching in Section [V](#S5). Using the general result in Theorem [III.2](#S3.Thmtheorem2), for sparse convex or nonconvex learning problems where $h_{\lambda}$ is convex or nonconvex,
we obtain minimax rates of the order ${\cal O}\left(\sqrt{\bar{s}\log d/n}\right)$ for sparse signal estimation by solving the sketched problem where $\bar{s}$ is the support size of the unknown sparse parameter vector to be estimated. Our proofs are based on the general result in Theorem [III.2](#S3.Thmtheorem2). To the best of our knowledge, our analysis provides the first unified theoretical result for sharp error rates for sparse signal estimation using sketching based optimization method.

There are two key differences between Iterative SRO and IHS []. First, using the subspace embedding as the projection matrix $\mathbf{P}$, Iterative SRO does not need to sample $\mathbf{P}$ and compute the sketched matrix ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$ at each iteration, in contrast with IHS where a separate $\mathbf{P}$ is sampled and ${\tilde{}\mathbf{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 a unified framework. For example, we show that Generalized Lasso [] can be efficiently and effectively solved by Iterative SRO in Section [VII](#S7).

### I-B Notations

Throughout this paper, we 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 a matrix, i.e. $\mathbf{X}^{i}$ indicates the $i$-th column of matrix $\mathbf{X}$. ${\left\|\cdot\right\|}_{p}$ denotes the $\ell^{p}$-norm of a vector, or the $p$-norm of a matrix. $\sigma_{t}(\cdot)$ is the $t$-th largest singular value of a matrix, and $\sigma_{\min}(\cdot)$ and $\sigma_{\max}(\cdot)$ indicate the smallest and largest singular value of a matrix respectively. ${\rm tr}(\cdot)$ is the trace of a matrix. $f_{1}(n)=\Theta(f_{2}(n))$ if there exist constants $k_{1},k_{2}>0$ and $n_{0}$ such that $k_{1}f_{(}n)\leq f_{1}(n)\leq k_{2}f_{2}(n)$. We use $\mathbf{X}\succcurlyeq\mathbf{Y}$ to indicate that $\mathbf{X}-\mathbf{Y}$ is a positive semi-definite matrix, and $\mathbf{I}_{d}$ indicates the $d\times d$ identity matrix. ${\rm rank}(\mathbf{X})$ means the rank of a matrix $\mathbf{X}$. $\mathbb{N}$ denotes the set of all the natural numbers, and we use $[m\ldots n]$ to indicate numbers between $m$ and $n$ inclusively, and $[n]$ denotes the natural numbers between $1$ and $n$ inclusively. ${\textsf{nnz}}(\mathbf{X})$ indicates the number of nonzero elements of a matrix $\mathbf{X}$. $\left|\cdot\right|$ denotes the cardinality of a set, and $\textup{supp}\left(\cdot\right)$ denotes the set of indices of nonzero elements for a vector.

## II The SRO Algorithm

In order to improve the efficiency of optimization for ([1](#S1.E1)), we propose Reguarlzied Optimization by Sketching (SRO) in this section. The key idea is to sketch matrix $\mathbf{X}$ in the quadratic term of ([1](#S1.E1)) by random projection. It is comprised of two steps:

- Step 1. Project the matrix $\mathbf{X}$ onto a lower dimensional space by a linear transformation $\mathbf{P}\in\mathbb{R}^{{\tilde{n}}\times n}$ with $\tilde{n}<n$, i.e. ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$. $\tilde{n}$ is named the sketch size.
- Step 2. Solve the sketched problem ([2](#S1.E2)).

Sketching the matrix $\mathbf{X}$ only in the quadratic term ${\left\|\mathbf{X}\bm{\beta}\right\|}_{2}^{2}$ is proposed in [] for constrained least square problems with convex constraints. SRO adopts this idea for regularized least square problems admitting a broad range of regularizers.

The linear transformation $\mathbf{P}$ is required to be a subspace embedding [] defined in Definition [II.1](#S2.Thmdefinition1). The literature [, , ] extensively studies such random transformation which is also closely related to the proof of the Johnson-Lindenstrauss lemma [].

###### Definition II.1 .

Suppose ${\cal P}$ is a distribution over $\tilde{n}\times n$ matrices, where $\tilde{n}$ is
a function of $n$, $d$, $\varepsilon$, and $\delta$. Suppose that with probability at least $1-\delta$, for
any fixed $n\times d$ matrix $\mathbf{X}$, a matrix $\mathbf{P}$ drawn from distribution ${\cal P}$ has the
property that $\mathbf{P}$ is a $(1\pm\varepsilon)$ $\ell^{2}$-subspace embedding for $\mathbf{X}$, that is,

$$ $\displaystyle(1-\varepsilon){\left\|\mathbf{X}\bm{\beta}\right\|}_{2}^{2}\leq{\left\|\mathbf{P}\mathbf{X}\bm{\beta}\right\|}_{2}^{2}\leq(1+\varepsilon){\left\|\mathbf{X}\bm{\beta}\right\|}_{2}^{2}$ (5) $$

holds for all $\bm{\beta}\in\mathbb{R}^{d}$. Then we call ${\cal P}$ an $(\varepsilon,\delta)$ oblivious $\ell^{2}$-subspace embedding.

###### Definition II.2 .

(Gaussian Subspace Embedding, [, Theorem 2.3]) Let $0<\varepsilon,\delta<1$, $\mathbf{P}=\frac{\mathbf{P}^{\prime}}{\sqrt{\tilde{n}}}$ where $\mathbf{P}^{{}^{\prime}}\in\mathbb{R}^{\tilde{n}\times n}$ is a matrix whose elements are i.i.d. samples from the standard Gaussian distribution ${\cal N}(0,1)$. Then if $\tilde{n}={\cal O}((r+\log{\frac{1}{\delta}})\varepsilon^{-2})$, for any matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ with $r={\rm rank}(\mathbf{X})$, with probability $1-\delta$, $\mathbf{P}=\frac{\mathbf{P}^{\prime}}{\sqrt{\tilde{n}}}$ is a $(1\pm\varepsilon)$ $\ell^{2}$-subspace embedding for $\mathbf{X}$. $\mathbf{P}$ is named a Gaussian subspace embedding.

###### Definition II.3 .

(Sparse Subspace Embedding) Let $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$. For each $i\in[n]$, $h(i)\in[\tilde{n}]$ is uniformly chosen from $[\tilde{n}]$, and $\sigma(i)$ is a uniformly random element of $\{1,-1\}$. We then set $\mathbf{P}_{h(i)i}=\sigma(i)$ and set $\mathbf{P}_{ji}=0$ for all $j\neq i$. As a result, $\mathbf{P}$ has only a single nonzero element per column, and it is called a sparse subspace embedding.

Lemma [II.1](#S2.Thmtheorem1) below, also presented in [], shows that the sparse subspace embedding defined above is indeed a subspace embedding with a high probability.

###### Lemma II.1 ( [ 23 , Theorem 2.1] ) .

Let $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a sparse embedding matrix with $\tilde{n}={\cal O}(r^{2}/(\delta\varepsilon^{2}))$ rows. Then for any fixed $n\times d$ matrix $\mathbf{X}$ with $r={\rm rank}(\mathbf{X})$, with probability $1-\delta$, $\mathbf{P}$ is a $(1\pm\varepsilon)$ $\ell^{2}$-subspace embedding for $\mathbf{X}$. Furthermore, $\mathbf{P}\mathbf{X}$ can be computed in ${\cal O}({\rm nnz}(\mathbf{X}))$ time, where ${\rm nnz}(\mathbf{X})$ is the number of nonzero elements of $\mathbf{X}$.

###### Definition II.1 .

###### Definition II.2 .

###### Definition II.3 .

###### Lemma II.1 ( [ 23 , Theorem 2.1] ) .

### II-A Error Bounds

The solutions to the original problem ([1](#S1.E1)) and the sketched problem ([2](#S1.E2)) by typical iterative optimization algorithms, such as gradient descent for smooth $h$ or proximal gradient method for non-smooth $h$, are always critical points of the corresponding objective functions under mild conditions []. Therefore, the analysis in the gap between $\tilde{}\bm{\beta}^{*}$ and $\bm{\beta}^{*}$ amounts to the analysis in the distance between critical points of the objective functions of ([2](#S1.E2)) and that of ([1](#S1.E1)), which is presented in Section [III](#S3). In the sequel, $\tilde{}\bm{\beta}^{*}$ is a critical point of the objective function ([2](#S1.E2)) and $\bm{\beta}^{*}$ is a critical point of the objective function ([1](#S1.E1)), if no confusion arises. More details about optimization algorithms are deferred to supplementary.

## III Approximation Error Bounds

We present an universal approximation error bound for SRO on the general problem ([1](#S1.E1)) in Section [III-A](#S3.SS1). We then apply this universal result to problems with convex, strongly convex and nonconvex regularization and derive the corresponding relative-error approximation bounds. Before stating our results, the definition of Frechet subdifferential, critical point, strong convexity and degree of nonconvexity are introduced below, which are essential to our analysis.

###### Definition III.1 .

(Subdifferential and critical points)
Given a nonconvex function $f\colon\mathbb{R}^{d}\to\mathbb{R}\cup\{+\infty\}$ which is a proper and lower semi-continuous function,

- •
for a given $\mathbf{x}\in{\rm dom}f$, its Frechet subdifferential of $f$ at $\mathbf{x}$, denoted by $\tilde{\partial}f(\mathbf{x})$, is
the set of all vectors $\mathbf{u}\in\mathbb{R}^{d}$ which satisfy
$\displaystyle\liminf\limits_{\mathbf{y}\neq\mathbf{x},\mathbf{y}\to\mathbf{x}}\frac{f(\mathbf{y})-f(\mathbf{x})-\langle\mathbf{u},\mathbf{y}-\mathbf{x}\rangle}{{\left\|\mathbf{y}-\mathbf{x}\right\|}_{2}}\geq 0.$
- •
The limiting-subdifferential of $f$ at $\mathbf{x}\in\mathbb{R}^{d}$, denoted by $\partial f(\mathbf{x})$, is defined by
$\displaystyle\partial f(\mathbf{x})=\{\mathbf{u}\in\mathbb{R}^{d}$
$\displaystyle\colon\exists\mathbf{x}^{k}\to\mathbf{x},f(\mathbf{x}^{k})\to f(\mathbf{x}),\tilde{}\mathbf{u}^{k}\in{\tilde{\partial}f}(\mathbf{x}^{k})\to\mathbf{u}\}.$

The point $\mathbf{x}$ is a critical point of $f$ if $\mathbf{0}\in\partial f(\mathbf{x})$.

Note that Frechet subdifferential generalizes the notions of Frechet derivative and subdifferential of convex functions. If $f$ is a convex function, then $\tilde{\partial}f(\mathbf{x})$ is also the subdifferential of $f$ at $\mathbf{x}$. In addition, if $f$ is a real-valued differentiable function with gradient $\nabla f(\mathbf{x})$, then $\tilde{\partial}f(\mathbf{x})=\{\nabla f(\mathbf{x})\}$.

###### Definition III.2 .

(Strongly convex function)
A differential function $h\colon\mathbb{R}^{d}\to\mathbb{R}$ is $\sigma$-strongly convex for $\sigma>0$ if for any $\mathbf{y},\mathbf{x}\in\mathbb{R}^{d}$,

$$ $\displaystyle h_{\lambda}(\mathbf{y})\geq h_{\lambda}(\mathbf{x})+\langle\nabla h_{\lambda}(\mathbf{x}),\mathbf{y}-\mathbf{x}\rangle+\frac{\sigma}{2}{\left\|\mathbf{y}-\mathbf{x}\right\|}_{2}^{2}.$ (6) $$

In order to analyze the relative-error approximation bound, we need the following definition of degree of nonconvexity in terms of the Frechet subdifferential in Definition [III.1](#S3.Thmdefinition1). It is an extension of the univariate degree of nonconvexity presented in [] used to analyze the consistency of nonconvex sparse estimation models with concave regularization.

###### Definition III.3 .

The degree of nonconvexity of a function $h\colon\mathbb{R}^{d}\to\mathbb{R}$ at a point $\mathbf{t}\in\mathbb{R}^{d}$ is defined as

$$ $\displaystyle\theta_{h}(\mathbf{t},\kappa)\coloneqq\sup_{\mathbf{s}\in\mathbb{R}^{d},\mathbf{s}\neq\mathbf{t},\mathbf{u}\in{\tilde{\partial}h}(\mathbf{s}),\mathbf{v}\in{\tilde{\partial}h}(\mathbf{t})}\frac{-(\mathbf{s}-\mathbf{t})^{\top}(\mathbf{u}-\mathbf{v})-\kappa{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}}{{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}},$ (7) $$

where $\kappa\in\mathbb{R}$. We abbreviate ([7](#S3.E7)) as $\theta_{h}(\mathbf{t},\kappa)\triangleq\sup_{\mathbf{s}\in\mathbb{R}^{d},\mathbf{s}\neq\mathbf{t}}\{-\frac{1}{{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}}(\mathbf{s}-\mathbf{t})^{\top}({\tilde{\partial}h}(\mathbf{s})-{\tilde{\partial}h}(\mathbf{t}))-\kappa{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}\}$ in the following text.

###### Remark III.1 .

It can be verified that the degree of nonconvexity of any convex function $h$ is zero with $\kappa=0$, that is, $\theta_{h}(\mathbf{t},0)\leq 0$ when $h$ is convex. If $h$ is $\sigma$-strongly convex and $h$ is twice continuously differentiable, then $\nabla^{2}h(\mathbf{x})\succcurlyeq\sigma\mathbf{I}_{d}$ for any $\mathbf{x}\in\mathbb{R}^{d}$, and $\theta_{h}(\mathbf{t},-\sigma)\leq 0$ with $\kappa$ set to $-\sigma$ in ([7](#S3.E7)).

###### Definition III.1 .

###### Definition III.2 .

###### Definition III.3 .

###### Remark III.1 .

### III-A General Bound

###### Theorem III.2 .

Suppose $\tilde{}\bm{\beta}^{*}$ is any critical point of the objective function in ([2](#S1.E2)), and $\bm{\beta}^{*}$ is any critical point of the objective function in ([1](#S1.E1)). Suppose $0<\varepsilon<\varepsilon_{0}<1$ where $\varepsilon_{0}$ is a small positive constant, $0<\delta<1$, $\mathbf{P}$ is drawn from an $(\varepsilon,\delta)$ oblivious $\ell^{2}$-subspace embedding over $\tilde{n}\times n$ matrices. Then with probability $1-\delta$,

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\theta_{h_{\lambda}}(\bm{\beta}^{*},\kappa){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}+\kappa{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}.$ (8) $$

In particular, if $\mathbf{P}$ is a Gaussian subspace embedding, then $\tilde{n}={\cal O}((r+\log{\frac{1}{\delta}})\varepsilon^{-2})$. If $\mathbf{P}$ is a sparse subspace embedding, then $\tilde{n}={\cal O}(r^{2}/(\delta\varepsilon^{2}))$.

$\kappa$ in the definition of degree of nonconvexity and the general approximation error bound ([8](#S3.E8)) reflects how “nonconvexity” of $h$ affects the accuracy of sketching. The following corollary shows that if the Frechet subdifferential of $h$ is Lipschitz continuous with limited Lipschitz constant, or $\kappa$ equivalently, the degree of nonconvexity can be set to 0 0, rendering a desirable relative-error approximation bound.

###### Corollary III.3 .

Under the conditions of Theorem [III.2](#S3.Thmtheorem2), suppose $\mathbf{X}$ has full column rank and $h_{\lambda}$ is nonconvex. If the Frechet subdifferential of $h_{\lambda}$ is $L_{h}$-smooth, i.e.
$\sup_{\mathbf{u}\in\tilde{\partial}h_{\lambda}(\mathbf{x}),\mathbf{v}\in\tilde{\partial}h_{\lambda}(\mathbf{y})}{\left\|\mathbf{u}-\mathbf{v}\right\|}_{2}\leq L_{h}{\left\|\mathbf{x}-\mathbf{y}\right\|}_{2}$. If
$\sigma_{\min}^{2}(\mathbf{X})>L_{h}$ and $0<\varepsilon<1-\frac{L_{h}}{\sigma_{\min}^{2}(\mathbf{X})}$, then

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{(1-\varepsilon)-\frac{L_{h}}{\sigma_{\min}^{2}(\mathbf{X})}}\cdot{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (9) $$

###### Remark III.4 .

To the best of our knowledge, ([9](#S3.E9)) is among the very few results in theoretical guarantee of sketching for nonconvex regularization.
If $h$ is twice continuously differentiable, the condition about $L_{h}$-smoothness is reduced to $\nabla^{2}h_{\lambda}(\bm{\beta})\succcurlyeq-L_{h}\mathbf{I}_{d}$ for all $\bm{\beta}\in\mathbb{R}^{d}$. The corollary above states that if $h$ is nonconvex but not “very” nonconvex with a limited $L_{h}$ or the regularization weight $\lambda$ is small enough, i.e. $L_{h}<{\sigma_{\min}^{2}(\mathbf{X})}(1-\varepsilon)$, then we have the relative-error approximation bound ([9](#S3.E9)).

###### Theorem III.2 .

###### Corollary III.3 .

###### Remark III.4 .

### III-B Relative-Error Approximation Bound with Convex Regularization

It can be verified that the degree of nonconvexity vanishes with $\kappa=0$ when $h$ is convex. As a result, we have relative-error approximation bound for ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ shown in Theorem [III.5](#S3.Thmtheorem5) below.

###### Theorem III.5 .

If $h_{\lambda}$ is convex, then under the conditions of Theorem [III.2](#S3.Thmtheorem2), with probability $1-\delta$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (10) $$

When $h_{\lambda}$ is strongly convex, more fine-grained approximation error bound in terms of the actual gap between $\tilde{}\bm{\beta}^{*}$ and $\bm{\beta}^{*}$ is presented in the following theorem.

###### Theorem III.6 .

If $h$ is $\sigma$-strongly convex, then under the conditions of Theorem [III.2](#S3.Thmtheorem2), with probability $1-\delta$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\leq\frac{\varepsilon^{2}}{4\sigma(1-\varepsilon)}\cdot{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2},$ (11) $$

and when ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\neq 0$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}-\frac{\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}}{(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}}.$ (12) $$

###### Remark III.7 .

Comparing ([12](#S3.E12)) with ([10](#S3.E10)), we observe that sketching for strongly-convex regularization renders tighter approximation error than that for the general convex case when ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\neq 0$. This indicates the benefit of using strongly-convex regularizers for sketching.

###### Theorem III.5 .

###### Theorem III.6 .

###### Remark III.7 .

## IV Iterative SRO

Figure: Algorithm 1 Iterative SRO

Inspired by Iterative Hessian Sketch [], we introduce an iterative sketching method for SRO so that the gap between solutions to the original problem and the sketched problem can be further reduced. The key idea is to iteratively apply SRO to generate a sequence $\{\bm{\beta}^{(t)}\}_{t=1}^{N}$ such that $\bm{\beta}^{(t)}$ is a more accuracy approximation to $\bm{\beta}^{*}$, the solution to the original problem ([1](#S1.E1)), than $\bm{\beta}^{(t-1)}$. Consider the optimization problem

$$ $\displaystyle\min_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|\mathbf{X}(\bm{\beta}+\bm{\beta}^{(t-1)})\right\|}_{2}^{2}-\mathbf{y}^{\top}\mathbf{X}\bm{\beta}+h_{\lambda}(\bm{\beta}+\bm{\beta}^{(t-1)}),$ (14) $$

then $\bm{\beta}^{*}-\bm{\beta}^{(t-1)}$ is an optimal solution to ([14](#S4.E14)). We apply SRO to problem ([14](#S4.E14)) and suppose $\widehat{}\bm{\beta}$ is an solution to the sketched problem, i.e.

$$ $\displaystyle\widehat{}\bm{\beta}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|{\tilde{}\mathbf{X}}\bm{\beta}\right\|}_{2}^{2}-\left\langle\mathbf{y}-\mathbf{X}\bm{\beta}^{(t-1)},\mathbf{X}\bm{\beta}\right\rangle+h_{\lambda}(\bm{\beta}+\bm{\beta}^{(t-1)}).$ (15) $$

$\widehat{}\bm{\beta}$ is supposed to be an approximation to $\bm{\beta}^{*}-\bm{\beta}^{(t-1)}$. If $\widehat{}\bm{\beta}$ admits the relative-error approximation bound ([3](#S1.E3)), then $\bm{\beta}^{(t)}=\widehat{}\bm{\beta}+\bm{\beta}^{(t-1)}$ becomes a more accurate approximation to $\bm{\beta}^{*}$ than $\bm{\beta}^{(t-1)}$ by a factor of $\rho$. This can be verified by noting that ${\left\|\bm{\beta}^{(t)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}={\left\|\widehat{}\bm{\beta}-(\bm{\beta}^{*}-\bm{\beta}^{(t-1)})\right\|}_{\mathbf{X}}\leq\rho{\left\|\bm{\beta}^{*}-\bm{\beta}^{(t-1)}\right\|}_{\mathbf{X}}$. By mathematical induction, we have Theorem [IV.1](#S4.Thmtheorem1) below showing that the approximation error of Iterative SRO, which is formally described by Algorithm [1](#alg1), drops geometrically in the iteration number. It should be emphasized that Theorem [IV.1](#S4.Thmtheorem1) also handles certain nonconvex regularization.

###### Theorem IV.1 .

Under the conditions of Theorem [III.2](#S3.Thmtheorem2), with probability at least $1-\delta$ with $\delta\in(0,1)$, the output of Iterative SRO described by Algorithm [1](#alg1) satisfies

$$ $\displaystyle{\left\|\bm{\beta}^{(N)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\rho^{N}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ (16) $$

for a constant $0<\rho<1$ if $h$ is convex, or the Frechet subdifferential of $h$ is $L_{h}$-smooth and $\mathbf{X}$ has full column rank with $\frac{L_{h}}{\sigma_{\min}^{2}(\mathbf{X})}<(1-\varepsilon)$. In particular, if $\mathbf{P}$ is a Gaussian subspace embedding, then $\tilde{n}={\cal O}\left(\left(r+\log{\frac{1}{\delta}}\right)\cdot(\rho+1)^{2}/\rho^{2}\right)$. If $\mathbf{P}$ is a sparse subspace embedding, then $\tilde{n}={\cal O}\left(r^{2}/\delta\cdot(\rho+1)^{2}/\rho^{2}\right)$. Here $r={\rm rank}(\mathbf{X})$.

###### Theorem IV.1 .

## V 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, $\bar{}\mathbf{y}=\bar{}\mathbf{X}\bar{}\bm{\beta}+\bm{\varepsilon}$ where $\bm{\varepsilon}$ is a noise vector of i.i.d. sub-gaussian elements with variance proxy $\sigma^{2}$, and $\bar{}\bm{\beta}$ is the sparse parameter vector of interest. Following the standard analysis for parameter estimation in the literature such as [, ], we assume $\max_{i\in[d]}{\left\|\bar{}\mathbf{X}^{i}\right\|}_{2}\leq\sqrt{n}$, and it follows that $\max_{i\in[d]}{\left\|\mathbf{X}^{i}\right\|}_{2}\leq 1$. The statistical learning literature has extensively studied the approximation to $\bar{}\bm{\beta}$ by the M-estimator obtained as a globally or locally optimal solution to problem ([1](#S1.E1)) with $\mathbf{X}=\bar{}\mathbf{X}/\sqrt{n}$, $\mathbf{y}=\bar{}\mathbf{y}/\sqrt{n}$. That is, one hopes to approximate $\bar{}\bm{\beta}$ by the globally or locally optimal solution to problem ([1](#S1.E1)) with a suitable sparsity-inducing regularizer $h_{\lambda}$. In Subsection [V-A](#S5.SS1), we show that the Iterative SRO described in Algorithm [1](#alg1) achieves the minimax parameter estimation error of the order $\sqrt{{\bar{s}}\log d/n}$ where ${\bar{s}}={\left\|\bar{}\bm{\beta}\right\|}_{0}$. In Subsection [V-B](#S5.SS2), we prove that SRO achieves the minimax parameter estimation error of the order $\sqrt{{\bar{s}}\log d/n}$ for sparse nonconvex learning, where the nonconvex regularizer $h_{\lambda}$ is the sum of a concave penalty function $q_{\lambda}$ and $\lambda{\left\|\cdot\right\|}_{1}$.

### V-A Sketching for Sparse Convex Learning

We define ${\cal L}(\bm{\beta})\coloneqq 1/2\cdot\bm{\beta}^{\top}\mathbf{X}^{\top}\mathbf{X}\bm{\beta}-\mathbf{y}^{\top}\mathbf{X}\bm{\beta}$ and $\tilde{\cal L}(\bm{\beta})\coloneqq{1/2\cdot{\tilde{}\mathbf{X}}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}-\mathbf{y}^{\top}\mathbf{X}\bm{\beta}$. We introduce the following definition of sparse eigenvalues widely used in sparse signal estimation literature.

###### Definition V.1 .

(Sparse Eigenvalues)
Let $s$ be a positive integer. The largest and smallest $s$-sparse eigenvalues of the Hessian matrix $\nabla^{2}{\cal L}(\bm{\beta})=\mathbf{X}^{\top}\mathbf{X}$ is

$$ $\displaystyle\rho_{{\cal L},+}(s)$ $\displaystyle\coloneqq\sup\left\{\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}\colon{\left\|\mathbf{v}\right\|}_{0}\leq s,{\left\|\mathbf{v}\right\|}_{2}=1,\mathbf{v}\in\mathbb{R}^{d}\right\},$ (17) $\displaystyle\rho_{{\cal L},-}(s)$ $\displaystyle\coloneqq\inf\left\{\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}\colon{\left\|\mathbf{v}\right\|}_{0}\leq s,{\left\|\mathbf{v}\right\|}_{2}=1,\mathbf{v}\in\mathbb{R}^{d}\right\}.$ (18) $$

$\rho_{\tilde{\cal L},+}(\cdot)$ and $\rho_{\tilde{\cal L},-}(\cdot)$ are defined in a similar manner with $\mathbf{X}$ replaced by $\tilde{}\mathbf{X}$.

The following assumption is frequently used in the sparse signal estimation literature with the convex sparsity-inducing penalty, $\lambda{\left\|\cdot\right\|}_{1}$.

###### Assumption 1 .

(Assumption in [, ] for sparse signal estimation)
$\rho_{{\cal L},+}(s)<\infty,\rho_{{\cal L},-}(s)>0$ are positive constants. Moreover,
for ${\bar{s}}={\left\|\bar{}\bm{\beta}\right\|}_{0}$, there exists a $k^{*}\in\mathbb{N}$ such that
$k^{*}\geq 2{\bar{s}}$ and

$$ $\displaystyle\rho_{{\cal L},+}(k^{*})/\rho_{{\cal L},-}(2k^{*}+{\bar{s}})\leq 1+0.5k^{*}/{\bar{s}}.$ (19) $$

We study the sparse signal estimation problem by solving the sketched Lasso problem with $h_{\lambda}(\bm{\beta})=\lambda{\left\|\bm{\beta}\right\|}_{1}$ in
the original problem ([1](#S1.E1)) and the sketched problem ([2](#S1.E2)) using our Iterative SRO algorithm. We have the following sharp bound for the parameter estimation error.

###### Theorem V.1 .

Suppose Assumption [1](#Thmassumption1) holds. Let $\lambda=c\sigma\sqrt{\log d/n}$ where $c$ is a positive constant.
Suppose Algorithm [1](#alg1) returns $\tilde{}\bm{\beta}^{*}=\bm{\beta}^{(N)}$ with $\rho\in(0,1)$ in ([16](#S4.E16)), and the iteration number $N$ is chosen as $N=1+\log\left({\left\|\mathbf{X}\right\|}_{2}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}/(\lambda\mu)\right)/\log(1/\rho)$. Then with probability at least $1-\delta-2/d$ with $\delta\in(0,1)$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}\leq\frac{\left(c+\mu c+2\right)}{\rho_{{\cal L},-}({\bar{s}}+k^{*})\cdot\left(1-\gamma\sqrt{0.5}\right)}\sqrt{\frac{\bar{s}\log d}{n}},$ (20) $$

where $\mu$ is a positive constant, $\gamma=(1+\mu+2/c)/(1-\mu-2/c)$, and $\mu$ and $c$ are chosen such that $\gamma\sqrt{0.5}<1$.
In particular, if $\mathbf{P}$ is a Gaussian subspace embedding, then $\tilde{n}={\cal O}\left(\left(r+\log{\frac{1}{\delta}}\right)\cdot(\rho+1)^{2}/\rho^{2}\right)$. If $\mathbf{P}$ is a sparse subspace embedding, then $\tilde{n}={\cal O}\left(r^{2}/\delta\cdot(\rho+1)^{2}/\rho^{2}\right)$. Here $r={\rm rank}(\mathbf{X})$.

Theorem [V.1](#S5.Thmtheorem1) shows that our Iterative ROS described in Algorithm [1](#alg1) applied on the sketched problem ([2](#S1.E2)) achieves the parameter estimation error, which is ${\left\|\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}$, of the order $\sqrt{{\bar{s}}\log d/n}$. Such estimation error rate is not improvable and it is the minimax error rate for standard Lasso. With the rank $r\ll n$, Iterative ROS obtains the solution $\tilde{}\bm{\beta}^{*}=\bm{\beta}^{(N)}$ efficiently with a small sketch size $\tilde{n}$ and the iteration number $N$ is only of a logarithmic order.

###### Definition V.1 .

###### Assumption 1 .

###### Theorem V.1 .

### V-B Sketching for Sparse Nonconvex Learning

We now study sparse signal estimation by sparse nonconvex learning where the regularizer $h_{\lambda}$ is nonconvex in
the original problem ([1](#S1.E1)) and the sketched problem ([2](#S1.E2)), that is, $h_{\lambda}(\bm{\beta})=\lambda{\left\|\bm{\beta}\right\|}_{1}+Q_{\lambda}(\bm{\beta})$ where $Q_{\lambda}(\bm{\beta})\coloneqq\sum\limits_{j=1}^{d}q_{\lambda}(\beta_{j})$, $q_{\lambda}$ is a concave function and $\beta_{j}$ is the $j$-th element of $\bm{\beta}$. We have $h_{\lambda}(\bm{\beta})=\sum\limits_{j=1}^{d}\left(\lambda\left|\beta_{j}\right|+q_{\lambda}(\beta_{j})\right)$. Following the analysis of sparse parameter vector recovery in [],
$\lambda\left|\cdot\right|+q_{\lambda}(\cdot)$ is a nonconvex function which can be either
smoothly clipped absolute deviation (SCAD) [] or minimax
concave penalty (MCP) []. More details about the nonconvex regularizer $h_{\lambda}$ are deferred to Section [A](#A1)
of the supplementary.
The following regularity conditions on the concave function $q_{\lambda}$ are used in [].

###### Assumption 2 .

(Regularity Conditions on Nonconvex Penalty in [] for sparse signal
recovery)

- (a)
$q^{\prime}_{\lambda}(\beta_{j})$ is monotone and Lipschitz continuous. For $\beta^{\prime}_{j}>\beta_{j}$, there exist two constants $\zeta_{-}\geq 0,\zeta_{+}\geq 0$ such that
$-\zeta_{-}\leq\frac{q^{\prime}_{\lambda}(\beta^{\prime}_{j})-q^{\prime}_{\lambda}(\beta_{j})}{\beta^{\prime}_{j}-\beta_{j}}\leq-\zeta_{+}$.
- (b)
$q_{\lambda}(-\beta_{j})=q_{\lambda}(\beta_{j})$ for all $\beta_{j}\in\mathbb{R}$. Also, $q_{\lambda}(0)=q^{\prime}_{\lambda}(0)=0$.
- (c)
$q^{\prime}_{\lambda}(\beta_{j})\leq\lambda$ for all $\beta_{j}\in\mathbb{R}$, and $\left|q^{\prime}_{\lambda_{1}}(\beta_{j})-q^{\prime}_{\lambda_{2}}(\beta_{j})\right|\leq\left|\lambda_{1}-\lambda_{2}\right|$ for all $\lambda_{1}>0,\lambda_{2}>0$.

The following assumption is the standard assumption in [] for sparse signal estimation with the minimax error rate, that is, ${\left\|\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}\leq{\cal O}\left(\sqrt{\bar{s}\log d/{n}}\right)$.

###### Assumption 3 .

(Assumption in [] for sparse signal estimation)
Let ${\bar{s}}={\left\|\bar{}\bm{\beta}\right\|}_{0}$. There exist an integer
$\tilde{s}$ such that $\tilde{s}>C{\bar{s}}$ such that
$\rho_{{\cal L},+}({\bar{s}}+2\tilde{s})<\infty,\rho_{{\cal L},-}({\bar{s}}+2\tilde{s})>0$ are two absolute constants. The concavity parameter $\zeta_{-}$ satisfies
$\zeta_{-}\leq C^{\prime}\rho_{{\cal L},-}({\bar{s}}+2\tilde{s})$ with constant $C^{\prime}\in(0,1)$.
Here $C=144\kappa^{2}+250\kappa$ with
$\kappa=(\rho_{{\cal L},+}({\bar{s}}+2\tilde{s})-\zeta_{+})/(\rho_{{\cal L},-}({\bar{s}}+2\tilde{s})-\zeta_{-})$.

The following corollary shows that when the support size of $\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}$ is bounded by $s_{0}$, then the nonconvex sparse learning problem ([1](#S1.E1)) with $h_{\lambda}$ being the nonconvex regularizer specified in this subsection still enjoys relative-error approximation. It is worth noting that this corollary follows from our general
result in Theorem [III.2](#S3.Thmtheorem2), and it is employed to prove our main result of minimax estimation error rate by sketching in Theorem [V.5](#S5.Thmtheorem5).

###### Corollary V.2 .

Under the conditions of Theorem [III.2](#S3.Thmtheorem2) and
Assumption [3](#Thmassumption3), let $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a Gaussian subspace embedding and suppose that
$\left|\textup{supp}\left(\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right)\bigcup\textup{supp}\left(\bm{\beta}^{*}\right)\bigcup\textup{supp}\left(\tilde{}\bm{\beta}^{*}\right)\right|\leq s_{0}$ for some integer $s_{0}\in[d]$. Let $\tilde{n}\geq c_{0}\varepsilon^{-2}\left(\log(2/\delta)+s_{0}\log d+s_{0}\log 5\right)$ for $\delta\in(0,1)$ and $\varepsilon\in(0,1-C^{\prime})$ where $c_{0}$ is a positive constant. Then
with probability at least $1-\delta$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}\leq\frac{\varepsilon\sqrt{\rho_{{\cal L},+}(s_{0})}}{(1-\varepsilon)\rho_{{\cal L},-}(s_{0})-\zeta_{-}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (21) $$

The following assumption, Assumption [4](#Thmassumption4), is necessary to achieve the minimax parameter estimation error by sketching, and the subsequent Remark [V.3](#S5.Thmtheorem3) explains that Assumption [4](#Thmassumption4) is mild. That is, if Assumption [3](#Thmassumption3)
holds, then Assumption [4](#Thmassumption4) also holds under mild conditions.

###### Assumption 4 .

(Assumption in [] for sparse signal estimation)
Let $\tilde{s},C^{\prime}$ be the parameters specified in
Assumption [3](#Thmassumption3) such that Assumption [3](#Thmassumption3)
holds. Then it is assumed that $\rho_{\tilde{\cal L},+}({\bar{s}}+2\tilde{s})<\infty,\rho_{\tilde{\cal L},-}({\bar{s}}+2\tilde{s})>0$ are two absolute constants. In addition, $\zeta_{-}$ satisfies
$\zeta_{-}\leq C^{\prime}\rho_{\tilde{\cal L},-}({\bar{s}}+2\tilde{s})$, and $\tilde{s}>\tilde{C}\bar{s}$ where $\tilde{C}=144\tilde{\kappa}^{2}+250\tilde{\kappa}$ with $\tilde{\kappa}\coloneqq(\rho_{\tilde{\cal L},+}({\bar{s}}+2\tilde{s})-\zeta_{+})/(\rho_{\tilde{\cal L},-}({\bar{s}}+2\tilde{s})-\zeta_{-})$.

###### Remark V.3 (Assumption 4 is mild) .

We provide theoretical justification that Assumption [4](#Thmassumption4) is mild.
The following theorem, Theorem [V.4](#S5.Thmtheorem4), shows that if the standard Assumption [3](#Thmassumption3) holds, then
Assumption [4](#Thmassumption4) also holds with high probability under very mild conditions: either $\varepsilon$ is set to the order of
$\sqrt{\log d/n}$ with sufficiently large $n$, or the Restricted
Isometry Property (RIP) [] holds. It is well known that RIP holds for various choices of the design matrix $\mathbf{X}$, and [] also uses RIP to justify that the standard Assumption [3](#Thmassumption3) is weaker than RIP.

Figure: Figure 1: Approximation error of Iterative SRO vs. SRO for GLasso with respect to different sketch size $\tilde{n}$. Iterative SRO and SRO are equipped with either sparse subspace embedding (left) or Gaussian Subspace Embedding (right).
Refer to caption: /html/2311.01806/assets/x1.png

###### Theorem V.4 .

Suppose Assumption [3](#Thmassumption3)
holds with $\tilde{s}$ and $C^{\prime}$ specified in
Assumption [3](#Thmassumption3), and let
$s_{0}={\bar{s}}+2\tilde{s}$.
Let $0<\varepsilon,\delta<1$, $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a Gaussian subspace embedding defined in Definition [II.2](#S2.Thmdefinition2), and
$\tilde{n}\geq c_{0}\varepsilon^{-2}\left(\log(2/\delta)+s_{0}\log d+s_{0}\log 5+1/d^{s_{0}-1}\right)$ where $c_{0}$ is a positive constant.
If $\rho_{{\cal L},-}(s_{0})>\varepsilon\sqrt{s_{0}}$, $\zeta_{-}\leq C^{\prime}\left(\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}\right)$ and $\left(144\kappa^{\prime 2}+250\kappa^{\prime}\right){\bar{s}}<\tilde{s}$ with $\kappa^{\prime}=(\rho_{{\cal L},+}(s_{0})+\varepsilon\sqrt{s_{0}}-\zeta_{+})/(\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}-\zeta_{-})$, then with probability at least $1-\delta$, Assumption [4](#Thmassumption4) holds.
In particular, Assumption [4](#Thmassumption4) holds with probability at least $1-\delta$ if any one of the following two conditions holds:

- (a)
$\log d/n\overset{n\to\infty}{\longrightarrow}0$, $\varepsilon=C_{1}\sqrt{\log d/n}$ with $C_{1}$ being a positive constant and $n$ sufficiently large;
- (b)
There exists $s^{\prime}\geq s_{0}$ such that $\textup{RIP}(\delta,s^{\prime})$ holds for $\delta\in(0,1)$,
$\zeta_{+}=0$,
$\zeta_{-}=C_{2}\rho_{{\cal L},-}(s_{0})$, $\varepsilon\sqrt{s_{0}}\leq C_{3}\rho_{{\cal L},-}(s_{0})$, $\tilde{s}>\left(144\kappa_{0}^{2}+250\kappa_{0}\right)\bar{s}$ with $\kappa_{0}=\left((1+C_{3})(1+\delta)\right)/\left((1-C_{2}-C_{3})(1-\delta)\right)$. Here the positive constants $C_{2},C_{3}$ satisfy $C_{2}+C_{3}<1$ and $C_{2}\leq C^{\prime}(1-C_{3})$.
$\textup{RIP}(\delta,s)$ for $\delta\in(0,1)$ and $s\in\mathbb{N}$ is the Restricted
Isometry Property (RIP) [] under which
$1-\delta\leq\rho_{{\cal L},-}(s)\leq\rho_{{\cal L},+}(s)\leq 1+\delta$ holds.

It is shown in Section [A](#A1) that $\zeta_{+}=0$ and $\zeta_{-}=C_{2}\rho_{{\cal L},-}(s_{0})$ can be easily achieved by setting the hyperparameter of MCP when MCP is used as the nonconvex regularizer $h_{\lambda}$. We have the following sharp bound for the parameter estimation error with sparse nonconvex learning by sketching in Theorem [V.5](#S5.Thmtheorem5). We note that the approximate path following method described in [, Algorithm 1] is used to solve the original problem ([1](#S1.E1)) and the sketched problem ([2](#S1.E2)) to obtain $\tilde{}\bm{\beta}^{*}$ and $\tilde{}\bm{\beta}^{*}$ such that
$\bm{\beta}^{*}$ is an critical point of problem ([1](#S1.E1)) and $\tilde{}\bm{\beta}^{*}$
is an critical point of ([2](#S1.E2)). We use $\lambda=\Theta\left(\sqrt{\bar{s}\log d/n}\right)$ for both ([1](#S1.E1)) and ([2](#S1.E2)) at the final stage of the path following method [, Algorithm 1].

###### Theorem V.5 .

Let $\delta\in(0,1)$ and $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a Gaussian subspace embedding defined in Definition [II.2](#S2.Thmdefinition2), and $\varepsilon=\min\left\{C_{1}\sqrt{\log d/n},\varepsilon_{0}\right\}$ with $C_{1},\varepsilon_{0}$ being positive constants and $\varepsilon\in(0,(1-C^{\prime})/2)$. Suppose
Assumption [3](#Thmassumption3) and
Assumption [4](#Thmassumption4) hold, $d\geq 5$, and let $s_{0}={\bar{s}}+2\tilde{s}$. Then under the conditions of Theorem [III.2](#S3.Thmtheorem2), with probability at least $1-4/d$,

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}\leq\frac{C_{1}{\left\|\bar{}\bm{\beta}\right\|}_{2}\sqrt{(1+\tilde{s}/\bar{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}\sqrt{\frac{\bar{s}\log d}{n}}+\frac{22\left(C_{1}\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}+2\sigma\right)}{\rho_{{\cal L},-}(s_{0})-\zeta_{-}}\sqrt{\frac{\bar{s}\log d}{n}}.$ (22) $$

Moreover, let $C_{1}=\sqrt{c_{0}792s_{0}/789}C_{3}$ with $C_{3}>1$ being a positive constant. Then ([22](#S5.E22)) holds
with $\tilde{n}\geq n/C_{3}^{2}$ for $n\geq\Theta(1)$.

It is noted that we can choose $\tilde{s}=\Theta(\bar{s})$. When ${\left\|\bar{}\bm{\beta}\right\|}_{2}$ is a constant, we have
the parameter estimation error ${\left\|\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}\leq{\cal O}\left(\sqrt{\bar{s}\log d/{n}}\right)$, which is the minimax estimation error according to []. Moreover, with
$C_{1}=4\sqrt{792s_{0}/789}C_{3}$, we can enjoy a small sketch size $\tilde{n}=n/C_{3}^{2}$ with a potentially large $C_{3}>1$, and this is at the expense of having a large constant factor $C_{1}$ in the parameter estimation error ${\cal O}\left(\sqrt{\bar{s}\log d/{n}}\right)$.

###### Assumption 2 .

###### Assumption 3 .

###### Corollary V.2 .

###### Assumption 4 .

###### Remark V.3 (Assumption 4 is mild) .

###### Theorem V.4 .

###### Theorem V.5 .

## VI Time Complexity

We compare the time complexity of solving the original problem ([1](#S1.E1)) to that of solving the sketched problem ([2](#S1.E2)) with Iterative SRO, which is deferred to Section [B](#A2) of the supplementary.

## VII Experimental Results

We provide empirical results in this section to justify the effectiveness of the proposed SRO and Iterative SRO.

### VII-A Generalized Lasso

We study the performance of Iterative SRO for Generalized Lasso (GLasso) [] in this subsection. The optimization problem of an instance of GLasso studied here is $\bm{\beta}^{*}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|\mathbf{y}-\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+\lambda\sum\limits_{i=1}^{d-1}|\bm{\beta}_{i}-\bm{\beta}_{i+1}|$, which is solved by Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) [], an accelerated version of PGD. $\bar{}\mathbf{X}=\sqrt{n}\mathbf{X}\in\mathbb{R}^{n\times d}$ have i.i.d. standard Gaussian entries with $n=80000$ and $d=600$, and all the elements of $\bar{}\mathbf{y}=\sqrt{n}\mathbf{y}$ are also i.i.d. Gaussian samples. Figure [1](#S5.F1) illustrates the approximation error of SRO and Iterative SRO, which are $\frac{{\left\|\bm{\beta}^{(1)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$ and $\frac{{\left\|\bm{\beta}^{(N)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$ respectively, for different choices of sketch size $\tilde{n}$ with $\tilde{n}=\bar{\gamma}d$. We set $N=10$ and employ either sparse subspace embedding or Gaussian subspace embedding. The average approximation errors are reported over $100$ trials of data sampling for each $\bar{\gamma}$. It can be observed that Iterative SRO significantly reduces the approximation error and its approximation error is roughly $\frac{1}{3}$ of that of SRO, demonstrating the effectiveness of Iterative SRO. In our experiment, due to the significant reduction in the sample size, for example, $\frac{{\bar{\gamma}}d}{n}=0.03$ when $\bar{\gamma}=4$, the running time of Iterative SRO is always less than half of that required to solve the original problem with small $\bar{\gamma}$.

We also report the running time of GLasso with sparse subspace embedding in Table [I](#S7.T1). We use $M=10000$ iterations for FISTA, and the running time is reported for $\bar{\gamma}=4$ on a CPU of Intel i5-11300H. Iterative SRO-IHS is the “IHS” version of Iterative SRO where a new sketch matrix $\mathbf{P}$ is sampled and the sketched data ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$ is computed at each iteration. We observed that both Iterative SRO-IHS and Iterative SRO achieve the same approximation error, while Iterative SRO is faster than Iterative SRO-IHS because the former only samples the linear transformation $\mathbf{P}$ once and computes the sketched matrix ${\tilde{}\mathbf{X}}$ once.

**TABLE I: Running time (in seconds) of SRO, Iterative SRO with $\bar{\gamma}=4$ and Iterative SRO-IHS for GLasso. The number in the bracket is the approximation error.**
| SRO | Iterative SRO | Iterative SRO-IHS |
| --- | --- | --- |
| $11.57s$ | $4.91s(0.031)$ | $5.32s(0.031)$ |

### VII-B Additional Experiments

We defer more experimental results to the Section [C](#A3) of the supplementary. In particular, experimental results for ridge regression and sparse signal estimation by Lasso are in Section [C-A](#A3.SS1) and Section [C-C](#A3.SS3) respectively, and
more details about GLasso are in Section [C-B](#A3.SS2). We further apply SRO to subspace clustering using Lasso in Section [C-D](#A3.SS4).

## VIII Conclusion

We present Sketching for Regularized Optimization (SRO) which efficiently solves general regularized 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 are obtained for both convex and nonconvex sparse learning problems. Experimental results evidence that Iterative SRO can effectively and efficiently approximate the optimization result of the original problem.

## Checklist

The checklist follows the references. For each question, choose your answer from the three possible options: Yes, No, Not Applicable. You are encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description (1-2 sentences).
Please do not modify the questions. Note that the Checklist section does not count towards the page limit. Not including the checklist in the first submission won’t result in desk rejection, although in such case we will ask you to upload it during the author response period and include it in camera ready (if accepted).

In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.

- 1.
For all models and algorithms presented, check if you include:
(a)
A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes]
(b)
An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes]
(c)
(Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes]
- 2.
For any theoretical claim, check if you include:
(a)
Statements of the full set of assumptions of all theoretical results. [Yes]
(b)
Complete proofs of all theoretical results. [Yes]
(c)
Clear explanations of any assumptions. [Yes]
- 3.
For all figures and tables that present empirical results, check if you include:
(a)
The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes]
(b)
All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes]
(c)
A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes]
(d)
A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes]
- 4.
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:
(a)
Citations of the creator if your work uses existing assets. [Not Applicable]
(b)
The license information of the assets, if applicable. [Not Applicable]
(c)
New assets either in the supplemental material or as a URL, if applicable. [Not Applicable]
(d)
Information about consent from data providers/curators. [Not Applicable]
(e)
Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable]
- 5.
If you used crowdsourcing or conducted research with human subjects, check if you include:
(a)
The full text of instructions given to participants and screenshots. [Not Applicable]
(b)
Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable]
(c)
The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

## Appendix A Nonconvex Penalty

We introduce more details about the nonconvex regularizer $h_{\lambda}$
for sparse nonconvex learning in Subsection [V-B](#S5.SS2).
$h_{\lambda}=\sum_{j=1}^{d}p_{\lambda}(\beta_{j})$, and $p_{\lambda}$ can be either smoothly clipped absolute deviation (SCAD) [] or minimax concave penalty (MCP) [].
When $p_{\lambda}$ is SCAD, we have

$$ $\displaystyle p_{\lambda}(\beta_{j})=\lambda\int_{0}^{\left|\beta_{j}\right|}\left({\rm 1}\kern-2.5pt{\rm I}_{\left\{z\leq\lambda\right\}}+\frac{(a\lambda-z)_{+}}{(a-1)\lambda}{\rm 1}\kern-2.5pt{\rm I}_{\left\{z>\lambda\right\}}\right){\rm d}z,\quad a>2.$ $$

When $p_{\lambda}$ is SCAD, we have

$$ $\displaystyle p_{\lambda}(\beta_{j})=\lambda\int_{0}^{\left|\beta_{j}\right|}\left(1-\frac{z}{\lambda b}\right)_{+}{\rm d}z,\quad b>0.$ $$

## Appendix B Time Complexity

We compare the time complexity of solving the original problem ([1](#S1.E1)) to that of solving the sketched problem ([2](#S1.E2)) with Iterative SRO. We employ Proximal Gradient Descent (PGD) or Gradient Descent (GD) in our analysis, which are widely used in the machine learning and optimization literature. If $\mathbf{P}$ is a Gaussian subspace embedding in Definition [II.2](#S2.Thmdefinition2), it takes ${\cal O}(\tilde{n}nd)$ operations to compute the sketched matrix ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$ and then form the sketched problem ([2](#S1.E2)). Let $C(\tilde{n},d)$ be the time complexity of solving the sketched problem ([2](#S1.E2)), and suppose iterative sketching is performed for $N$ iterations, then the overall time complexity of Iterative SRO in Algorithm [1](#alg1) is ${\cal O}\left(\tilde{n}nd+NC(\tilde{n},d)\right)$. If $\mathbf{P}$ is a sparse subspace embedding in Definition [II.3](#S2.Thmdefinition3), then it only takes ${\cal O}\left({\textsf{nnz}(\mathbf{X})}\right)$ operations to compute the sketched matrix ${\tilde{}\mathbf{X}}$. In this case, the overall time complexity of Iterative SRO is ${\cal O}\left({\textsf{nnz}(\mathbf{X})}+NC(\tilde{n},d)\right)$. Suppose PGD, such as that analyzed in [], or GD, is used to solve problem ([1](#S1.E1)) and ([2](#S1.E2)) with maximum number of iterations being $M$. Then $C(\tilde{n},d)={\cal O}\left(M\tilde{n}d\right)$. If a sparse subspace embedding is used for sketching, then the overall time complexity of Iterative SRO is ${\cal O}\left({\textsf{nnz}(\mathbf{X})}+NM\tilde{n}d\right)$. In contrast, because IHS [] needs to sample an independent sketch matrix at each iteration, the time complexity of IHS using the fast Johnson-Lindenstrauss sketches (that is, the fast Hadamard transform) is ${\cal O}\left(Nnd\log{\tilde{n}}+NM\tilde{n}d\right)$ which is higher than that of Iterative SRO with sparse subspace embedding. Noting that $N\leq\log n$ [] and in many practical cases $N$ is bounded by a constant, and $\tilde{n}\ll n$, the complexity of Iterative SRO, ${\cal O}\left({\textsf{nnz}(\mathbf{X})}+NM\tilde{n}d\right)$, is much lower than that of solving the original problem ([1](#S1.E1)) with the complexity of ${\cal O}(Mnd)$.

## Appendix 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](#S1.E1)), which include ridge regression where $h(\bm{\beta})={\left\|\bm{\beta}\right\|}_{2}^{2}$, Generalized Lasso where $h(\bm{\beta})=\sum\limits_{i=1}^{d-1}|\bm{\beta}_{i}-\bm{\beta}_{i+1}|$, and Lasso where $h(\bm{\beta})={\left\|\bm{\beta}\right\|}_{1}$. We further show the application of SRO in subspace clustering.

Figure: Figure 2: Approximation Error of Iterative SRO with respect to different sketch size $\tilde{n}$ for ridge regression. The first row corresponds to sparse subspace embedding defined in Definition [II.3](#S2.Thmdefinition3) and the second row is produced by Gaussian subspace embedding defined in Definition [II.2](#S2.Thmdefinition2).
Refer to caption: /html/2311.01806/assets/x2.png

Figure: Figure 3: Logarithm of approximation error of Iterative SRO with respect to different sketch size $\tilde{n}$ for ridge regression. The first row corresponds to sparse subspace embedding and the second row is produced by Gaussian subspace embedding.
Refer to caption: /html/2311.01806/assets/x3.png

Figure: Figure 4: Approximation error of Iterative SRO with respect to different sketch size $\tilde{n}$ for ridge regression. The first row corresponds to sparse subspace embedding and the second row is produced by Gaussian subspace embedding.
Refer to caption: /html/2311.01806/assets/x4.png

### C-A Ridge Regression of Larger Scale

We employ Iterative SRO to approximate solution to Ridge Regression in this subsection, whose optimization problem is $\bm{\beta}^{*}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|\mathbf{y}-\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+\lambda{\left\|\bm{\beta}\right\|}_{2}$. We assume a linear model $\bar{}\mathbf{y}=\bar{}\mathbf{X}\bar{}\bm{\beta}+\mathbf{w}$ where $\mathbf{X}=\bar{}\mathbf{X}/\sqrt{n}$, $\mathbf{y}=\bar{}\mathbf{y}/\sqrt{n}$, $\mathbf{w}\sim{\cal N}(\mathbf{0},\mathbf{I}_{n})$ is the Gaussian noise with unit variance. The unknown regression vector $\bar{}\bm{\beta}$ is sampled according to ${\cal N}(\mathbf{0},\mathbf{I}_{d})$. We randomly sample $\bar{}\mathbf{X}\in\mathbb{R}^{n\times d}$ of rank $r=\frac{n}{100}$ with $n=5000$ and $d=10000$. Let $\bar{}\mathbf{X}=\mathbf{U}\bm{\Sigma}\mathbf{V}^{\top}$ be the Singular Value Decomposition of $\bar{}\mathbf{X}$ where $\bm{\Sigma}\in\mathbb{R}^{r\times r}$ is a diagonal matrix whose diagonal elements are the singular values of $\bar{}\mathbf{X}$. $\mathbf{U}\in\mathbb{R}^{n\times r}$ is sampled from the uniform distribution over the Stiefel manifold $\mathbbm{V}_{r}(\mathbb{R}^{n})$, $\mathbf{V}\in\mathbb{R}^{d\times r}$ is sampled from the uniform distribution over the Stiefel manifold $\mathbbm{V}_{r}(\mathbb{R}^{d})$, the diagonal elements of $\bm{\Sigma}$ are i.i.d. standard Gaussian samples. We set $\lambda=\sqrt{\log d/n}$. Figure [2](#A3.F2) illustrates the logarithm of approximation error $\frac{{\left\|\bm{\beta}^{(i)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$ with respect to the iteration number $i$ of Iterative SRO for different choices of sketch size $\tilde{n}$, and the maximum iteration number of Iterative SRO is set to $N=10$. We let $\tilde{n}=\bar{\gamma}{\rm rank}(\mathbf{X})$ where $\bar{\gamma}$ ranges over $\left\{12,14,16,18,20\right\}$, and sample $\bar{}\mathbf{X},\bar{}\mathbf{y}$ and $\mathbf{w}$ $100$ times for each $\bar{\gamma}$. The average approximation errors are illustrated in Figure [2](#A3.F2). It can be observed from Figure [2](#A3.F2) that the convergence rate of approximation error drops geometrically, or its logarithm drops linearly, evidencing our Theorem [IV.1](#S4.Thmtheorem1) for Iterative SRO. Moreover, as suggested by Theorem [III.2](#S3.Thmtheorem2), larger $\tilde{n}$ leads to smaller approximation error.

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 $\tilde{n}=\bar{\gamma}{\rm rank}(\bar{}\mathbf{X})$ where $\bar{\gamma}$ ranges over $\{12,14,16,18,20\}$, and sample $\bar{}\mathbf{X},\bar{}\bm{\beta}$ and $\mathbf{w}$ $100$ times for each $\bar{\gamma}$. Figure [3](#A3.F3) illustrates the logarithm of approximation error, which is $\log{\frac{{\left\|\bm{\beta}^{(i)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}}$, with respect to the iteration number $i$ of Iterative SRO for different choices of sketch size $\tilde{n}$, 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 [4](#A3.F4) illustrates the approximation error of Iterative SRO in red curve for ridge regression, which is $\frac{{\left\|\bm{\beta}^{(i)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$. The blue bar represents standard deviation caused by the random data sampling and the random sketching. A single projection matrix $\mathbf{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) [] which samples a projection matrix matrix for each iteration of the iterative sketch procedure.

### C-B Generalized Lasso

In this subsection, we add more details to Section [VII-A](#S7.SS1) of the paper for Generalized Lasso (GLasso) []. The optimization problem of GLasso studied here is $\bm{\beta}^{*}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|\mathbf{y}-\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+\lambda\sum\limits_{i=1}^{d-1}|\bm{\beta}_{i}-\bm{\beta}_{i+1}|$, which is solved by Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) []. We construct $\mathbf{D}\in\mathbb{R}^{(d-1)\times d}$ by setting $\mathbf{D}_{i,i}=-1$, $\mathbf{D}_{i,i+1}=1$ for all $i\in[d-1]$, then $\sum\limits_{i=1}^{d-1}|\bm{\beta}_{i}-\bm{\beta}_{i+1}|={\left\|\mathbf{D}\bm{\beta}\right\|}_{1}$. Let $\mathbf{D}^{\rm ext}=\left[{\begin{array}[]{*{20}{c}}{\mathbf{D}}\\
{0,\ldots,1}\end{array}}\right]$ with $\mathbf{D}_{dd}^{\rm ext}=1$. Denote $\mathbf{u}=\mathbf{D}^{\rm ext}\bm{\beta}$, then $\bm{\beta}=\left(\mathbf{D}^{\rm ext}\right)^{-1}\bm{\beta}$ because $\mathbf{D}^{\rm ext}$ is nonsingular. The instance of GLasso considered above is then rewritten as $\bm{\beta}^{*}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2n}{\left\|\mathbf{y}-\mathbf{X}\left(\mathbf{D}^{\rm ext}\right)^{-1}\mathbf{u}\right\|}_{2}^{2}+\lambda\sum\limits_{i=1}^{d-1}\left|\mathbf{u}_{i}\right|$ which can be solved by FISTA.

### C-C Signal Recovery by Lasso

We present experimental results for signal recovery/approximation by Lasso in this subsection. In this experiment we assume a linear model $\bar{}\mathbf{y}=\bar{}\mathbf{X}\bar{}\bm{\beta}+\mathbf{w}$ where $\mathbf{X}=\bar{}\mathbf{X}/\sqrt{n}$, $\mathbf{y}=\bar{}\mathbf{y}/\sqrt{n}$, $\mathbf{w}\sim{\cal N}(\mathbf{0},\mathbf{I}_{n})$ is the Gaussian noise with unit variance. The optimization problem of Lasso considered here is $\bm{\beta}^{*}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2}{\left\|\mathbf{y}-\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+\lambda{\left\|\bm{\beta}\right\|}_{1}$. We set $\lambda=0.1\cdot\sqrt{\bar{s}\log d/n}$, sparsity $\bar{s}=\left\lfloor 3\log{d}\right\rfloor$, and choose the unknown regression vector $\bar{}\bm{\beta}$ with its support uniformly sampled with entries $\pm\frac{1}{\sqrt{s}}$ with equal probability. We randomly sample $\bar{}\mathbf{X}\in\mathbb{R}^{n\times d}$ of rank not greater than $r=\frac{n}{100}$ with $n=5000$ and $d=100000$ using ([53](#A4.E53)) so that $\bar{}\mathbf{X}$ is a low-rank matrix satisfying RIP. That is, $\mathbf{X}=\mathbf{U}\mathbf{U}^{\top}\bm{\Omega}$ with $\mathbf{U}\in\mathbb{R}^{n\times r}$ and $\bm{\Omega}\in\mathbb{R}^{n\times d}$. $\mathbf{U}$ is sampled from the uniform distribution over the Stiefel manifold $\mathbbm{V}_{r}(\mathbb{R}^{n})$, the elements of $\bm{\Omega}$ are i.i.d. Gaussian random variables
with $\bm{\Omega}_{ij}\sim{\cal N}(0,1/r)$ for $i\in[n],j\in[d]$.
We let $\tilde{n}=\bar{\gamma}{\rm rank}(\bar{}\mathbf{X})$ where $\bar{\gamma}$ ranges over $\left\{12,14,16,18\right\}$, and sample $\bar{}\mathbf{X},\bar{}\bm{\beta}$ and $\mathbf{w}$ $100$ times for each $\gamma$. Figure [5](#A3.F5) illustrates the approximation error of SRO and Iterative SRO, i.e. $\frac{{\left\|\bm{\beta}^{(1)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$ and $\frac{{\left\|\bm{\beta}^{(N)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{n}$ respectively, for different choices of sketch size $\tilde{n}$ with different $\bar{\gamma}$. It can be observed that Iterative SRO significantly and constantly reduces approximation error of SRO.

Table [II](#A3.T2) shows the error of approximation to the true unknown regression vector $\bar{}\bm{\beta}$ by SRO, Iterative SRO and the solution $\bm{\beta}^{*}$ to the original problem ([1](#S1.E1)).
The error of approximation to $\bar{}\bm{\beta}$ is the $\ell^{2}$-distance to $\bar{}\bm{\beta}$, for example, the error of approximation to $\bar{}\bm{\beta}$ for $\bm{\beta}^{*}$ is ${\left\|\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}$.
Standard deviation 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 $\tilde{n}$ being a fraction of $n$, especially with Gaussian subspace embedding. More importantly, Iterative SRO and $\bm{\beta}^{*}$ have very close error of approximation to $\bar{}\bm{\beta}$,
justifying our theoretical analysis. This is because that our theoretical prediction in Theorem [V.1](#S5.Thmtheorem1) for the error of approximation to $\bar{}\bm{\beta}$ by Iterative SRO is $\Theta\left(\sqrt{\bar{s}\log d/n}\right)$, which is the same order as the error by $\bm{\beta}^{*}$.

Figure: Figure 5: Approximation error of Iterative SRO and SRO for Lasso with respect to different sketch size $\tilde{n}=\gamma{\rm rank}(\mathbf{X})$. Iterative SRO and SRO are equipped with either sparse subspace embedding (left) or Gaussian Subspace Embedding (right).
Refer to caption: /html/2311.01806/assets/x5.png

**TABLE II: Approximation error to the true unknown regression vector $\bar{}\bm{\beta}$ by SRO, Iterative SRO and the solution $\bm{\beta}^{*}$ to the original problem ([1](#S1.E1)) for Lasso.**
|  | Error<br>$\bar{\gamma}$ | $12$ | $14$ | $16$ | $18$ |
| --- | --- | --- | --- | --- | --- |
| Sparse Subspace Embedding | SRO | $0.115\pm 0.149$ | $0.063\pm 0.023$ | $0.059\pm 0.010$ | $0.025\pm 0.054$ |
| Iteratie SRO | $0.010\pm 0.017$ | $0.009\pm 0.009$ | $0.004\pm 0.002$ | $0.008\pm 0.005$ |  |
| $\bm{\beta}^{*}$ | $0.008\pm 0.002$ | $0.007\pm 0.006$ | $0.003\pm 0.001$ | $0.006\pm 0.004$ |  |
| Gaussian Subspace Embedding | SRO | $0.067\pm 0.092$ | $0.043\pm 0.066$ | $0.044\pm 0.038$ | $0.046\pm 0.030$ |
| Iteratie SRO | $0.008\pm 0.003$ | $0.008\pm 0.007$ | $0.004\pm 0.002$ | $0.003\pm 0.004$ |  |
| $\bm{\beta}^{*}$ | $0.007\pm 0.001$ | $0.006\pm 0.003$ | $0.003\pm 0.001$ | $0.002\pm 0.002$ |  |

### C-D Application in Lasso Subspace Clustering

We demonstrate application of SRO in subspace clustering in this subsection. Given a data matrix $\bar{}\mathbf{X}\in\mathbb{R}^{n\times d}$ comprised of $d$ data points in $\mathbb{R}^{n}$ which lie in a union of subspaces in $\mathbb{R}^{n}$, classical subspace clustering methods using sparse codes, such as Noisy Sparse Subspace Clustering (Noisy SSC) [], recovers the subspace structure by solving the Lasso problem

$$ $\displaystyle{\bm{\beta}^{i}}=\operatorname*{arg\,min}_{\bm{\beta}\in\mathbb{R}^{d}}\frac{1}{2n}{\left\|\bar{}\mathbf{X}^{i}-\bar{}\mathbf{X}\bm{\beta}\right\|}_{2}^{2}+\lambda{\left\|\bm{\beta}\right\|}_{1},\quad\bm{\beta}_{i}=0,$ (23) $$

for each $i\in[d]$. $\bar{}\mathbf{X}^{i}$ is the $i$-th column of $\bar{}\mathbf{X}$, which is also the $i$-th data point, $\lambda>0$ is the weight for the $\ell^{1}$ regularization. Under certain conditions on $\bar{}\mathbf{X}$ and the underlying subspaces, it is proved by [, ] that nonzero elements of $\bm{\beta}^{*}$ correspond to data points lying in the same subspace as $\bar{}\mathbf{X}^{i}$, and in this case $\bm{\beta}^{*}$ 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 ([23](#A3.E23)) for all $i\in[d]$, we have a sparse code matrix $\bm{\beta}=[{\bm{\beta}^{1}},{\bm{\beta}^{2}},\ldots,{\bm{\beta}^{d}}]\in\mathbb{R}^{d\times d}$, and a sparse similarity matrix $\mathbf{W}$ is constructed by $\mathbf{W}=\frac{|\mathbf{X}|+|\mathbf{X}^{\top}|}{2}$. Spectral clustering is performed on $\mathbf{W}$ to produce the final clustering result of Noisy SSC. Two measures are used to evaluate the performance of different clustering methods, i.e. the Accuracy (AC) and the Normalized Mutual Information (NMI) []. In this experiment, we employ SRO to solve the sketched version of problem ([23](#A3.E23)) with $\tilde{n}=\frac{n}{15}$. Note that SRO is equivalent to Iterative SRO with $N=1$, and we do not incur more iterations by Iterative SRO since SRO produces satisfactory results. Figure [6](#A3.F6) and Figure [7](#A3.F7) illustrate the accuracy (left) and NMI (right) of sketched Noisy SSC by SRO with respect to various choices of the regularization weight $\lambda$ 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\times 32$ taken under different illuminations for each subject, and $\bar{}\mathbf{X}$ is of size $1024\times 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) [] and SSC by Orthogonal Matching Pursuit (SSC-OMP) []. It can be observed that SRO-GSE and SRO-SSE outperform other competing clustering methods by a notable margin, and they perform even better than the original Noisy SSC for most values of $\lambda$, due to the fact that sketching potentially reduces the adverse effect of noise in the original data.

Figure: Figure 6: Accuracy with respect to different values of $\lambda$ on the Extended Yale-B Dataset
Refer to caption: /html/2311.01806/assets/x6.png

Figure: Figure 7: NMI with respect to different values of $\lambda$ on the Extended Yale-B Dataset
Refer to caption: /html/2311.01806/assets/x7.png

## Appendix D Proofs

We present proofs of theoretical results of the original paper in this section.

### D-A Proofs for Section III and
Section IV

Before presenting the proof of Theorem [III.2](#S3.Thmtheorem2), the following lemma is introduced which shows that subspace embedding approximately preserves inner product with high probability.

###### Lemma D.1 .

Suppose $\mathbf{P}$ is a $(1\pm\varepsilon)$ $\ell^{2}$-subspace embedding for $\mathbf{X}$, and let ${\cal C}(\mathbf{X})$ denote the column space of $\mathbf{X}$. Then with probability $1-\delta$, for any two vectors $\mathbf{u}\in{\cal C}(\mathbf{X})$, $\mathbf{v}\in{\cal C}(\mathbf{X})$,

$$ $\displaystyle\left|\mathbf{u}^{\top}\mathbf{P}^{\top}\mathbf{P}\mathbf{v}-\mathbf{u}^{\top}\mathbf{v}\right|\leq{\left\|\mathbf{u}\right\|}_{2}{\left\|\mathbf{v}\right\|}_{2}\varepsilon.$ (24) $$

###### Proof.

If $\mathbf{u}=\mathbf{0}$ or $\mathbf{v}=\mathbf{0}$, then ([24](#A4.E24)) holds trivially. Otherwise, let $\mathbf{u}^{\prime}=\frac{\mathbf{u}}{{\left\|\mathbf{u}\right\|}_{2}}$, $\mathbf{v}^{\prime}=\frac{\mathbf{v}}{{\left\|\mathbf{v}\right\|}_{2}}$, and $\mathbf{u}^{\prime},\mathbf{v}^{\prime}\in{\cal C}(\mathbf{X})$. According to the definition of $(1\pm\varepsilon)$ $\ell^{2}$-subspace embedding for $\mathbf{X}$, with probability $1-\delta$,

$$ $\displaystyle(1-\varepsilon){\left\|\mathbf{u}^{\prime}+\mathbf{v}^{\prime}\right\|}_{2}^{2}\leq{\left\|\mathbf{P}(\mathbf{u}^{\prime}+\mathbf{v}^{\prime})\right\|}_{2}^{2}\leq(1+\varepsilon){\left\|\mathbf{u}^{\prime}+\mathbf{v}^{\prime}\right\|}_{2}^{2},$ (25) $\displaystyle(1-\varepsilon){\left\|\mathbf{u}^{\prime}-\mathbf{v}^{\prime}\right\|}_{2}^{2}\leq{\left\|\mathbf{P}(\mathbf{u}^{\prime}-\mathbf{v}^{\prime})\right\|}_{2}^{2}\leq(1+\varepsilon){\left\|\mathbf{u}^{\prime}-\mathbf{v}^{\prime}\right\|}_{2}^{2}.$ (26) $$

Subtracting ([26](#A4.E26)) from ([25](#A4.E25)), we have

$$ $\displaystyle\left|\mathbf{u}^{\prime\top}\mathbf{P}^{\top}\mathbf{P}\mathbf{v}^{\prime}-\mathbf{u}^{\prime\top}\mathbf{v}^{\prime}\right|\leq\varepsilon,$ (27) $$

and ([24](#A4.E24)) holds by scaling ([27](#A4.E27)) by ${\left\|\mathbf{u}\right\|}_{2}{\left\|\mathbf{v}\right\|}_{2}$.
∎

###### Proof of Theorem III.2 .

By the optimality of $\tilde{}\bm{\beta}^{*}$, we have

$$ $\displaystyle{\left\|{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-\mathbf{y}^{\top}\mathbf{X}+\mathbf{v}\right\|}_{2}=0$ (28) $$

for some $\mathbf{v}\in{\tilde{\partial}h_{\lambda}}(\tilde{}\bm{\beta}^{*})$. In the sequel, we will also use ${\tilde{\partial}h}(\cdot)$ to indicate an element belonging to ${\tilde{\partial}h_{\lambda}}(\cdot)$ if no special note is made.

By the optimality of $\bm{\beta}^{*}$, we have

$$ $\displaystyle{\left\|\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}-\mathbf{y}^{\top}\mathbf{X}+\mathbf{u}\right\|}_{2}=0,$ (29) $$

where $\mathbf{u}\in{\tilde{\partial}h_{\lambda}}(\bm{\beta}^{*})$.

Define $\Delta\coloneqq\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}$, $\tilde{\Delta}\coloneqq\big{(}{\tilde{\partial}h_{\lambda}}(\tilde{}\bm{\beta}^{*})-{\tilde{\partial}h_{\lambda}}(\bm{\beta}^{*})\big{)}$. By ([28](#A4.E28)) and ([29](#A4.E29)), we have

$$ $\displaystyle{\left\|{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}+\mathbf{v}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}-\mathbf{u}\right\|}_{2}$ $\displaystyle={\left\|{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}+\tilde{\Delta}\right\|}_{2}=0$ (30) $$

By Cauchy-Schwarz inequality,

$$ $\displaystyle\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}+\tilde{\Delta}\right)\leq{\left\|\Delta\right\|}_{2}{\left\|{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}+\tilde{\Delta}\right\|}_{2}=0.$ (31) $$

On the other hand, the LHS of ([31](#A4.E31)) can be written as

$$ $\displaystyle\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}+\tilde{\Delta}\right)=\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}\right)+\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}\right)+\Delta^{\top}\tilde{\Delta}.$ (32) $$

By ([31](#A4.E31)) and ([32](#A4.E32)), we have

$$ $\displaystyle\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}\right)+\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}\right)\leq-\Delta^{\top}\tilde{\Delta}$ (33) $$

Now we derive lower bounds for the two terms on the LHS of ([33](#A4.E33)). First, we have

$$ $\displaystyle\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\tilde{}\bm{\beta}^{*}-{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}\right)=\Delta^{\top}{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\Delta={\left\|{\tilde{}\mathbf{X}}\Delta\right\|}_{2}^{2}\geq(1-\varepsilon){\left\|\mathbf{X}\Delta\right\|}_{2}^{2}.$ (34) $$

Moreover,

$$ $\displaystyle\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\bm{\beta}^{*}-\mathbf{X}^{\top}\mathbf{X}\bm{\beta}^{*}\right)=\Delta^{\top}\left({\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}-\mathbf{X}^{\top}\mathbf{X}\right)\bm{\beta}^{*}\geq-\varepsilon{\left\|\mathbf{X}\Delta\right\|}_{2}{\left\|\mathbf{X}\bm{\beta}^{*}\right\|}_{2}.$ (35) $$

Plugging ([34](#A4.E34)) and
([35](#A4.E35)) in ([33](#A4.E33)), we have

$$ $\displaystyle(1-\varepsilon){\left\|\mathbf{X}\Delta\right\|}_{2}^{2}-\varepsilon{\left\|\mathbf{X}\Delta\right\|}_{2}{\left\|\mathbf{X}\bm{\beta}^{*}\right\|}_{2}\leq-\Delta^{\top}\tilde{\Delta}.$ (36) $$

Moreover, by the definition of degree of nonconvexity in ([7](#S3.E7)),

$$ $\displaystyle-\Delta^{\top}\tilde{\Delta}\leq\theta_{h}(\bm{\beta}^{*},\kappa){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}+\kappa{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}.$ (37) $$

([8](#S3.E8)) then follows by ([36](#A4.E36))
and ([37](#A4.E37)).

∎

###### Proof of Corollary III.3 .

Because the Frechet subdifferential of $h$ is $L_{h}$-smooth, that is,

$$ $\sup_{\mathbf{u}\in\tilde{\partial}h_{\lambda}(\mathbf{x}),\mathbf{v}\in\tilde{\partial}h_{\lambda}(\mathbf{y})}{\left\|\mathbf{u}-\mathbf{v}\right\|}_{2}\leq L_{h}{\left\|\mathbf{x}-\mathbf{y}\right\|}_{2},$ $$

it can be verified that $\theta_{h_{\lambda}}(\bm{\beta}^{*},\kappa)\leq 0$ with holds with $\kappa=L_{h}$. This is due to the fact that for any $\mathbf{s}\in\mathbb{R}^{d}$, $\mathbf{t}\in\mathbb{R}^{d}$, and let $\mathbf{u}\in\tilde{\partial}h_{\lambda}(\mathbf{s})$, $\mathbf{v}\in\tilde{\partial}h_{\lambda}(\mathbf{t})$, then we have

$$ $\displaystyle-(\mathbf{s}-\mathbf{t})^{\top}(\mathbf{u}-\mathbf{v})-L_{h}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}$ $\displaystyle\leq{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}{\left\|\mathbf{u}-\mathbf{v}\right\|}_{2}-L_{h}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}$ $\displaystyle\leq L_{h}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}-L_{h}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}=0.$ (38) $$

Therefore,

$$ $\displaystyle\theta_{h_{\lambda}}(\mathbf{t},L_{h})=\sup_{\mathbf{s}\in\mathbb{R}^{d},\mathbf{s}\neq\mathbf{t}}\{-\frac{1}{{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}}(\mathbf{s}-\mathbf{t})^{\top}({\tilde{\partial}h}(\mathbf{s})-{\tilde{\partial}h}(\mathbf{t}))-L_{h}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}\}\leq 0.$ (39) $$

Moreover, since $\mathbf{X}$ is nonsingular, ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\leq\frac{{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}}{\sigma_{\min}^{2}(\mathbf{X})}$.

Plugging the above results in ([8](#S3.E8)) and setting $\kappa$ to $L_{h}$, we have

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ $\displaystyle\leq\theta_{h}(\bm{\beta}^{*},L_{h}){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}+L_{h}{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}$ $\displaystyle\leq\frac{L_{h}}{\sigma_{\min}^{2}(\mathbf{X})}\cdot{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2},$ (40) $$

and ([9](#S3.E9)) immediately follows from ([D-A](#A4.Ex9)).
∎

###### Proof of Theorem III.5 .

When $h$ is convex, then its Frechet differential coincides with its subdifferential. As a result, for any $\mathbf{u}\in\tilde{\partial}h(\mathbf{s})$ and $\mathbf{v}\in\tilde{\partial}h(\mathbf{t})$, we have
$(\mathbf{s}-\mathbf{t})^{\top}(\mathbf{u}-\mathbf{v})\geq 0$, and it follows that

$$ $\displaystyle-(\mathbf{s}-\mathbf{t})^{\top}(\mathbf{u}-\mathbf{v})\leq 0.$ (41) $$

With $\kappa=0$, ([41](#A4.E41)) suggests that

$$ $\displaystyle\theta_{h_{\lambda}}(\mathbf{t},0)=\sup_{\mathbf{s}\in\mathbb{R}^{d},\mathbf{s}\neq\mathbf{t}}\{-\frac{1}{{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}}(\mathbf{s}-\mathbf{t})^{\top}({\tilde{\partial}h_{\lambda}}(\mathbf{s})-{\tilde{\partial}h_{\lambda}}(\mathbf{t}))\}\leq 0,$ (42) $$

By ([8](#S3.E8)) in Theorem [III.2](#S3.Thmtheorem2) and ([42](#A4.E42)), setting $\kappa=0$, we have

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\theta_{h_{\lambda}}(\bm{\beta}^{*},\kappa){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}+\kappa{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\leq 0$ (43) $$

If ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\neq 0$, it follows from ([43](#A4.E43)) that

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (44) $$

∎

###### Proof of Theorem III.6 .

For strongly convex function $h$, we have

$$ $\displaystyle-(\mathbf{s}-\mathbf{t})^{\top}\big{(}\nabla h_{\lambda}(\mathbf{s})-\nabla h_{\lambda}(\mathbf{t})\big{)}\leq-\sigma{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2}.$ (45) $$

Therefore, the degree of nonconvexity $\theta_{h_{\lambda}}(\mathbf{t},\kappa)\leq 0$ with $\kappa=-\sigma$. Setting $\kappa=-\sigma$ in ([8](#S3.E8)), we have

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ $\displaystyle\leq\theta_{h_{\lambda}}(\bm{\beta}^{*},-\sigma){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}-\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}$ $\displaystyle\leq-\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}.$ (46) $$

([D-A](#A4.Ex10)) indicates that the equation
$(1-\varepsilon)x^{2}-\varepsilon{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}x+\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}=0$ has a real root for $x$, so that we have

$$ $\displaystyle 4\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\cdot(1-\varepsilon)\leq\varepsilon^{2}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}$ $\displaystyle\Rightarrow{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\leq\frac{\varepsilon^{2}}{4\sigma(1-\varepsilon)}\cdot{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}.$ (47) $$

If ${\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\neq 0$, it also follows from ([D-A](#A4.Ex10)) that

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}-\frac{\sigma{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}}{(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}}.$ (48) $$

∎

###### Proof of Theorem IV.1 .

This proof mostly follows from the proof of our main Theorem [III.2](#S3.Thmtheorem2), Theorem [III.5](#S3.Thmtheorem5) and Corollary [III.3](#S3.Thmtheorem3).

Let $\tilde{}\bm{\beta}^{*}=\bm{\beta}^{(t)}$.
Define $\Delta\coloneqq\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}$, $\tilde{\Delta}\coloneqq\big{(}{\tilde{\partial}h_{\lambda}}(\tilde{}\bm{\beta}^{*})-{\tilde{\partial}h_{\lambda}}(\bm{\beta}^{*})\big{)}$. By repeating the proof of Theorem [III.2](#S3.Thmtheorem2) and Theorem [III.5](#S3.Thmtheorem5), with probability $1-\delta$,

$$ $\displaystyle(1-\varepsilon){\left\|\mathbf{X}\Delta\right\|}_{2}^{2}-\varepsilon{\left\|\mathbf{X}\Delta\right\|}_{2}{\left\|\mathbf{X}(\bm{\beta}^{*}-\bm{\beta}^{(t-1)})\right\|}_{2}\leq-\Delta^{\top}\tilde{\Delta}.$ (49) $$

It follows by the proof of Theorem [III.5](#S3.Thmtheorem5) that
$\lambda\Delta^{\top}\tilde{\Delta}\leq 0$. As a result, it follows by
([49](#A4.E49)) that

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\frac{\varepsilon}{1-\varepsilon}{\left\|\bm{\beta}^{*}-\bm{\beta}^{(t-1)}\right\|}_{\mathbf{X}}$ (50) $$

For a constant $0<\rho<1$, by choosing $\varepsilon\leq\frac{\rho}{\rho+1}$ in ([50](#A4.E50)), we have

$$ $\displaystyle{\left\|\bm{\beta}^{(t)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\rho{\left\|\bm{\beta}^{*}-\bm{\beta}^{(t-1)}\right\|}_{\mathbf{X}}$ (51) $$

for any $t\geq 1$. It follows that

$$ $\displaystyle{\left\|\bm{\beta}^{(N)}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\rho^{N}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ (52) $$

with $\bm{\beta}^{(0)}=\mathbf{0}$. The same proof is applied for the case that $h$ is $L_{h}$-smooth and $\mathbf{X}$ has full column rank with $\frac{L_{h}}{\sigma_{\min}^{2}(\mathbf{X})}<1-\varepsilon$.
∎

###### Lemma D.1 .

###### Proof.

###### Proof of Theorem III.2 .

###### Proof of Corollary III.3 .

###### Proof of Theorem III.5 .

###### Proof of Theorem III.6 .

###### Proof of Theorem IV.1 .

### D-B Proofs for Section V : Sketching for Sparse Convex Learning

In Theorem [V.1](#S5.Thmtheorem1), we showed that for a low-rank data matrix $\mathbf{X}$ with ran $r\ll n$, then the Iterative ROS described in Algorithm [1](#alg1) applied on the sketched problem ([2](#S1.E2)) achieves the parameter estimation error of the order ${\cal O}\left(\bar{s}\log d/n\right)$ under
Assumption [1](#Thmassumption1).
As explained in [], Assumption [1](#Thmassumption1)
is weaker than the Restricted Isometry Property (RIP) in compressed sensing []. We show that there exists low-rank data matrix $\mathbf{X}$ satisfying Assumption [1](#Thmassumption1).
We first show by Theorem [D.2](#A4.Thmtheorem2) that there exists a low-rank data matrix
$\mathbf{X}$ which satisfies $\textup{RIP}(\delta,s)$ for $\delta\in(0,1)$
and $s\in\mathbb{N}$ with $\textup{RIP}(\delta,s)$ defined in Theorem [V.4](#S5.Thmtheorem4)(b).

We define the necessary notations in the following text. Let $\mathbf{A}$ be a matrix
and ${\cal S}$ be a set, we denote by $\mathbf{A}_{{\cal S}}$ the submatrix of $\mathbf{A}$ with columns indexed by ${\cal S}$. Similarly, for a vector $\mathbf{v}$, $\mathbf{v}_{{\cal S}}$ is a vector formed by elements of $\mathbf{v}$ indexed by ${\cal S}$.

###### Theorem D.2 .

Let $\delta\in(0,1)$
and $s\in\mathbb{N}$. There exists a data matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ with rank not greater than $c_{1}n$ for $c_{1}\in(0,1)$
such that $\textup{RIP}(\delta,s)$ holds with probability at least
$1-2d^{s}\left(1+\frac{8}{\delta}\right)^{s}\exp\left(-nc_{1,2}(\delta)\right)-2d^{s}\left(1+\frac{8}{\delta}\right)^{s}\exp\left(-n^{\alpha_{0}}\right)$, where $\alpha_{0}\in(0,1/2)$ is a positive constant, $c_{1,2}(\delta)$ is a positive constant depending on $c_{1}$ and $\delta$. Here $n\ll d$, $\log d\ll n^{\alpha_{0}}$. $\textup{RIP}(\delta,s)$ means
that for all $\mathbf{v}\in\mathbb{R}^{d},{\left\|\mathbf{v}\right\|}_{0}\leq s$,

$$ $\displaystyle(1-\delta){\left\|\mathbf{v}\right\|}_{2}^{2}\leq\mathbf{v}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}\leq(1+\delta){\left\|\mathbf{v}\right\|}_{2}^{2}.$ $$

###### Proof.

We construct the data matrix by

$$ $\displaystyle\mathbf{X}=\mathbf{U}\mathbf{U}^{\top}\bm{\Omega},\quad\mathbf{U}\in\mathbb{R}^{n\times r},\Omega\in\mathbb{R}^{n\times d},r=c_{1}n,$ (53) $$

where $\mathbf{U}$ is an orthogonal matrix and $\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_{r}$,
all the elements of $\bm{\Omega}$ are i.i.d. Gaussian random variables
with $\bm{\Omega}_{ij}\sim{\cal N}(0,1/r)$ for $i\in[n],j\in[d]$.
It is clear that the rank of $\mathbf{X}$ is bounded by $c_{1}n$.
We show that $\textup{RIP}(\delta,s)$

Define the set

$$ $\displaystyle{\cal F}\coloneqq\bigcup_{\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s}{\cal F}_{\mathbf{S}},\quad{\cal F}_{\mathbf{S}}\coloneqq\left\{\mathbf{u}\in\mathbb{R}^{d}\mid{\left\|\mathbf{u}\right\|}_{2}=1,\textup{supp}\left(\mathbf{u}\right)\subseteq\mathbf{S}\right\}.$ $$

Given a set $\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s$, let $\mathbf{v}\in{\cal F}_{\mathbf{S}}$ ,
we define functions

$$ $\displaystyle F(\mathbf{v})\coloneqq\frac{1}{c_{1}{\left\|\mathbf{A}\mathbf{v}\right\|}_{2}^{2}}{\left\|\mathbf{U}\mathbf{U}^{\top}\mathbf{A}\mathbf{v}\right\|}_{2}^{2},\quad g(\mathbf{x})\coloneqq\frac{1}{c_{1}}{\left\|\mathbf{U}\mathbf{U}^{\top}\mathbf{x}\right\|}_{2}^{2}.$ $$

where $\mathbf{A}=\sqrt{r}\bm{\Omega}$ and the elements of $\mathbf{A}$ are i.i.d. standard
Gaussian random variables. It is clear that
$F(\mathbf{v})=g(\mathbf{A}\mathbf{v}/{\left\|\mathbf{A}\mathbf{v}\right\|}_{2})$, and
$g$ is a $2/c_{1}$-Lipschitz function. Moreover,

$$ $\displaystyle\mathbb{E}_{\mathbf{x}\sim\textup{Unif}(\mathbb{S}^{n-1})}\left[g(\mathbf{x})\right]$ $\displaystyle=\frac{1}{c_{1}}\mathbb{E}_{\mathbf{x}\sim\textup{Unif}(\mathbb{S}^{n-1})}\left[\mathbf{U}\mathbf{U}^{\top}\mathbf{x}\mathbf{x}^{\top}\mathbf{U}\mathbf{U}^{\top}\right]$ $\displaystyle=\frac{c_{1}n}{c_{1}n}=1.$ $$

Let $\mathbf{x}=\mathbf{A}\mathbf{v}/{\left\|\mathbf{A}\mathbf{v}\right\|}_{2}$, then
$\mathbf{x}\sim\textup{Unif}(\mathbb{S}^{n-1})$, and $F(\mathbf{v})=g(\mathbf{x})$.
It follows by
Lemma [D.8](#A4.Thmtheorem8) that

$$ $\displaystyle\textup{Pr}\left[\left|g(\mathbf{x})-\mathbb{E}\left[g(\mathbf{x})\right]\right|>t\right]\leq 2\exp\left(-nc^{2}_{1}t^{2}/8\right),$ (54) $$

It follows by ([54](#A4.E54))
that for a given $\mathbf{v}\in{\cal F}_{\mathbf{S}}$,
$\textup{Pr}\left[\left|F(\mathbf{v})-1\right|\leq t\right]\geq 1-2\exp\left(-nc^{2}_{1}t^{2}/8\right)$.

On the other hand, $\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}=1/r\cdot{\left\|\mathbf{U}\mathbf{U}^{\top}\mathbf{A}\mathbf{v}\right\|}_{2}^{2}$. Noting that
${\left\|\mathbf{A}\mathbf{v}\right\|}_{2}^{2}$ is $\chi^{2}$, it follows by standard concentration on $\chi^{2}$ that for a given $\mathbf{v}\in{\cal F}_{\mathbf{S}}$, with probability at least
$1-2\exp\left(-nc_{1,2}(\delta)\right)-2\exp\left(-n^{\alpha_{0}}\right)$, we have
$\left|\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}-1\right|\leq\delta/2$, and
$\left|{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}-1\right|\leq\delta/2$.

It follows by [, Lemma 5.2], there exists an $\delta/4$-net $N_{\delta/4}({\cal F}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\subseteq{\cal F}_{\mathbf{S}}$ of ${\cal F}_{\mathbf{S}}$ such that $\left|N_{\delta/4}({\cal F}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\right|\leq\left(1+\frac{8}{\delta}\right)^{s}$. Using the union bound, with probability at least
$1-2\left(1+\frac{8}{\delta}\right)^{s}\exp\left(-nc_{1,2}(\delta)\right)-2\left(1+\frac{8}{\delta}\right)^{s}\exp\left(-n^{\alpha_{0}}\right)$,
the event that $\left|{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}-1\right|\leq\delta/2$ holds for all
$\mathbf{v}\in N_{\delta/4}({\cal F}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ happens. Define this event as ${\cal A}_{\mathbf{S}}$, and the following argument is conditioned on ${\cal A}_{\mathbf{S}}$.

We define $A>0$ as the smallest number such that
${\left\|\mathbf{X}\mathbf{v}\right\|}_{2}\leq 1+A$ for all $\mathbf{v}\in{\cal F}_{\mathbf{S}}$.
For any $\mathbf{v}\in{\cal F}_{\mathbf{S}}$, there exists $\mathbf{v}^{\prime}\in N_{\delta/4}({\cal F}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ such that ${\left\|\mathbf{v}-\mathbf{v}^{\prime}\right\|}_{2}\leq\delta/4$. As a result,

$$ $\displaystyle{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}\leq{\left\|\mathbf{X}\mathbf{v}^{\prime}\right\|}_{2}+{\left\|\mathbf{X}(\mathbf{v}-\mathbf{v}^{\prime})\right\|}_{2}\leq 1+\frac{\delta}{2}+(1+A)\frac{\delta}{4}.$ $$

It follows by the definition of $A$ that $A\leq\delta/2+(1+A)\delta/4$,
so $A\leq\frac{3\delta/4}{1-\delta/4}\leq\delta$. We then have
${\left\|\mathbf{X}\mathbf{v}\right\|}_{2}\leq 1+\delta$ for all $\mathbf{v}\in{\cal F}_{\mathbf{S}}$. On the other
hand,

$$ $\displaystyle{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}\geq{\left\|\mathbf{X}\mathbf{v}^{\prime}\right\|}_{2}-{\left\|\mathbf{X}(\mathbf{v}-\mathbf{v}^{\prime})\right\|}_{2}\geq 1-\frac{\delta}{2}-(1+\delta)\frac{\delta}{4}\geq 1-\delta,\quad\forall\mathbf{v}\in{\cal F}_{\mathbf{S}}.$ $$

As a result, conditioned on the event ${\cal A}_{\mathbf{S}}$ for a set $\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s,\left|{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}-1\right|\leq\delta$ holds for all $\mathbf{v}\in{\cal F}_{\mathbf{S}}$. Because $\left|{\cal F}\right|\leq d^{s}$, using the union bound, with probability specified in this theorem,
$\left|{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}-1\right|\leq\delta$ holds for all $\mathbf{v}\in\mathbb{R}^{d},{\left\|\mathbf{v}\right\|}_{0}\leq s$.

∎

Low-Rank Matrix $\mathbf{X}$ Satisfying Assumption [1](#Thmassumption1)
It is proved in Theorem [D.2](#A4.Thmtheorem2) that the low-rank data matrix $\mathbf{X}$ constructed by ([53](#A4.E53)) satisfies $\textup{RIP}(\delta,s)$
for $\delta\in(0,1)$ and $s\in\mathbb{N}$. As indicated by [],
The condition ([19](#S5.E19)) in Assumption [1](#Thmassumption1) is weaker than RIP. To see this, ([19](#S5.E19))
holds with $k^{*}=(s-\bar{s})/2$ if $\textup{RIP}(\delta,s)$ holds with $s=5\bar{s}$ and $\delta=1/3$.

We need the following lemma for the proof of
Theorem [V.1](#S5.Thmtheorem1).

###### Lemma D.3 ( [ 26 , Lemma 5] ) .

For any $\mathbf{v}\in\mathbb{R}^{d}$ and any index set ${\cal S}\subseteq[d]$
with $\left|{\cal S}\right|={\bar{s}}$. Let ${\cal J}$ be the set of indices of the largest
$k^{*}$ elements of $\mathbf{v}_{{\cal S}^{c}}$ in absolute value and let ${\cal I}={\cal J}\bigcup{\cal S}$. Here ${\bar{s}}$ and $k^{*}$ are the same as those in
Assumption [1](#Thmassumption1). Assume that
${\left\|\mathbf{v}_{{\cal S}^{c}}\right\|}_{1}\leq\gamma{\left\|\mathbf{v}_{{\cal S}}\right\|}_{1}$ for some $\gamma>0$. Then we have ${\left\|\mathbf{v}\right\|}_{2}\leq(1+\gamma){\left\|\mathbf{v}_{{\cal I}}\right\|}_{2}$, and

$$ $\displaystyle\mathbf{v}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}\geq\rho_{{\cal L},-}({\bar{s}}+k^{*})\cdot\left({\left\|\mathbf{v}_{{\cal I}}\right\|}_{2}-\gamma\sqrt{{\bar{s}}/k^{*}}\sqrt{\rho_{{\cal L},+}(k^{*})/\rho_{{\cal L},-}({\bar{s}}+2k^{*})-1}{\left\|\mathbf{v}_{{\cal S}}\right\|}_{2}\right){\left\|\mathbf{v}_{{\cal I}}\right\|}_{2}.$ (55) $$

###### Proof of Theorem V.1 .

We consider the upper bound for the quadratic form
$\left\langle\nabla{\cal L}(\tilde{}\bm{\beta}^{*})-\nabla{\cal L}(\bar{}\bm{\beta}),\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\rangle=\Delta^{\top}\mathbf{X}^{\top}\mathbf{X}\Delta$, where $\tilde{}\bm{\beta}^{*}=\beta^{(N)}$ and $\Delta\coloneqq\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}$. We define
${\cal S}=\textup{supp}\left(\bar{}\bm{\beta}\right)$. Let $\mathbf{v}$ be a vector, we denote by $\mathbf{v}_{{\cal S}}$ the vector formed by elements of $\mathbf{v}$ in the set ${\cal S}$.

We have

$$ $\displaystyle\Delta^{\top}\mathbf{X}^{\top}\mathbf{X}\Delta$ $\displaystyle=\left\langle\nabla{\cal L}(\tilde{}\bm{\beta}^{*})-\nabla{\cal L}(\bar{}\bm{\beta}),\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\rangle$ $\displaystyle\leq\left\langle\nabla{\cal L}(\tilde{}\bm{\beta}^{*}),\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\rangle+{\left\|\nabla{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}{\left\|\Delta\right\|}_{1}$ $\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}\left\langle\nabla{\cal L}(\tilde{}\bm{\beta}^{*})-\nabla{\cal L}(\bm{\beta}^{*}),\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\rangle+\left\langle\nabla{\cal L}(\bm{\beta}^{*}),\tilde{}\bm{\beta}^{*}-\bar{}\bm{\beta}\right\rangle+2\sigma\sqrt{\frac{\log d}{n}}{\left\|\Delta\right\|}_{1}$ $\displaystyle\leq{\left\|\nabla{\cal L}(\tilde{}\bm{\beta}^{*})-\nabla{\cal L}(\bm{\beta}^{*})\right\|}_{\infty}{\left\|\Delta\right\|}_{1}-\lambda{\left\|\Delta_{{\cal S}^{c}}\right\|}_{1}+\lambda{\left\|\Delta_{{\cal S}}\right\|}_{1}+\frac{2}{c}\lambda{\left\|\Delta\right\|}_{1}$ $\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}\lambda\mu{\left\|\Delta\right\|}_{1}-\lambda{\left\|\Delta_{{\cal S}^{c}}\right\|}_{1}+\lambda{\left\|\Delta_{{\cal S}}\right\|}_{1}+\frac{2}{c}\lambda{\left\|\Delta\right\|}_{1}$ $\displaystyle=-\lambda\left(1-\mu-\frac{2}{c}\right){\left\|\Delta_{{\cal S}^{c}}\right\|}_{1}+\lambda\left(1+\mu+\frac{2}{c}\right){\left\|\Delta_{{\cal S}}\right\|}_{1}.$ (56) $$

Here \raisebox{-.8pt}{1}⃝ follows by Lemma [D.7](#A4.Thmtheorem7), and $\rho^{N}{\left\|\mathbf{X}\right\|}_{2}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}\leq\lambda\mu$
in \raisebox{-.8pt}{2}⃝.

It follows by ([D-B](#A4.Ex24)) that
${\left\|\Delta_{{\cal S}^{c}}\right\|}_{1}\leq\left((1+\mu+2/c)/(1-\mu-2/c)\right){\left\|\Delta_{{\cal S}}\right\|}_{1}$.

We now apply Lemma [D.3](#A4.Thmtheorem3) with $\mathbf{v}=\Delta$
and $\gamma=\left((1+\mu+2/c)/(1-\mu-2/c)\right)$. It follows by Lemma [D.3](#A4.Thmtheorem3)
that ${\left\|\Delta\right\|}_{2}\leq(1+\gamma){\left\|\Delta_{{\cal I}}\right\|}_{2}$. Moreover,
it follows by Assumption [1](#Thmassumption1)
that $\rho_{{\cal L},+}(k^{*})/\rho_{{\cal L},-}(2k^{*}+{\bar{s}})\leq 1+0.5k^{*}/{\bar{s}}$. Plugging this inequality in ([55](#A4.E55)), we have

$$ $\displaystyle\Delta\mathbf{X}^{\top}\mathbf{X}\Delta$ $\displaystyle\geq\rho_{{\cal L},-}({\bar{s}}+k^{*})\cdot\left({\left\|\Delta_{{\cal I}}\right\|}_{2}-\gamma\sqrt{{\bar{s}}/k^{*}}\sqrt{\rho_{{\cal L},+}(k^{*})/\rho_{{\cal L},-}({\bar{s}}+2k^{*})-1}{\left\|\Delta_{{\cal S}}\right\|}_{2}\right){\left\|\Delta_{{\cal I}}\right\|}_{2}$ $\displaystyle\geq\rho_{{\cal L},-}({\bar{s}}+k^{*})\cdot\left(1-\gamma\sqrt{0.5}\right){\left\|\Delta_{{\cal I}}\right\|}_{2}^{2}.$ (57) $$

It follows from ([D-B](#A4.Ex19))
that $\Delta^{\top}\mathbf{X}^{\top}\mathbf{X}\Delta\leq\lambda\left(1+\mu+\frac{2}{c}\right){\left\|\Delta_{{\cal S}}\right\|}_{1}\leq\lambda\left(1+\mu+\frac{2}{c}\right)\sqrt{{\bar{s}}}{\left\|\Delta_{{\cal I}}\right\|}_{2}$. It follows by this inequality and
([D-B](#A4.Ex24)) that

$$ $\displaystyle{\left\|\Delta\right\|}_{2}\leq{\left\|\Delta_{{\cal I}}\right\|}_{2}\leq\frac{\left(1+\mu+\frac{2}{c}\right)\sqrt{{\bar{s}}}\lambda}{\rho_{{\cal L},-}({\bar{s}}+k^{*})\cdot\left(1-\gamma\sqrt{0.5}\right)},$ $$

which proves ([20](#S5.E20)).

∎

###### Theorem D.2 .

###### Proof.

###### Lemma D.3 ( [ 26 , Lemma 5] ) .

###### Proof of
Theorem V.1 .

### D-C Sketching for Sparse Nonconvex Learning

###### Proof of Corollary V.2 .

We have $h_{\lambda}(\bm{\beta})=\lambda{\left\|\bm{\beta}\right\|}_{1}+Q_{\lambda}(\bm{\beta})$. For any $\mathbf{s}\in\mathbb{R}^{d}$, $\mathbf{t}\in\mathbb{R}^{d}$, and let $\mathbf{u}\in\tilde{\partial}h_{\lambda}(\mathbf{s})$, $\mathbf{v}\in\tilde{\partial}h_{\lambda}(\mathbf{t})$, then
$\mathbf{u}=\xi_{1}+\nabla Q_{\lambda}(\mathbf{s})$ and $\mathbf{v}=\xi_{2}+\nabla Q_{\lambda}(\mathbf{t})$
with $\mathbf{x}_{1}\in\partial\left(\lambda{\left\|\mathbf{s}\right\|}_{1}\right)$ and $\mathbf{x}_{2}\in\partial\left(\lambda{\left\|\mathbf{t}\right\|}_{1}\right)$. We have

$$ $\displaystyle-(\mathbf{s}-\mathbf{t})^{\top}(\mathbf{u}-\mathbf{v})$ $\displaystyle=-(\mathbf{s}-\mathbf{t})^{\top}(\xi_{1}-\xi_{2})-(\mathbf{s}-\mathbf{t})^{\top}\left(\nabla Q_{\lambda}(\mathbf{s})-\nabla Q_{\lambda}(\mathbf{t})\right)$ $\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}-(\mathbf{s}-\mathbf{t})^{\top}\left(\nabla Q_{\lambda}(\mathbf{s})-\nabla Q_{\lambda}(\mathbf{t})\right)$ $\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}\zeta_{-}{\left\|\mathbf{s}-\mathbf{t}\right\|}_{2}^{2},$ (58) $$

where \raisebox{-.8pt}{1}⃝ follows from the convexity of $\lambda{\left\|\cdot\right\|}_{1}$, and \raisebox{-.8pt}{2}⃝ follows from the regularity condition (b) in
Assumption [2](#Thmassumption2).

It follows by ([D-C](#A4.Ex26)) that the degree of nonconvexity
$\theta_{h_{\lambda}}(\mathbf{t},\zeta_{-})\leq 0$. Using the upper bound for $\tilde{n}$ in the given condition, plugging $\theta_{h_{\lambda}}(\mathbf{t},\zeta_{-})\leq 0$ in
([8](#S3.E8)) and setting $\kappa$ to $\zeta_{-}$, we have

$$ $\displaystyle(1-\varepsilon){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}-\varepsilon{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}$ $\displaystyle\leq\theta_{h}(\bm{\beta}^{*},L_{h}){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}+\zeta_{-}{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}$ $\displaystyle\leq\zeta_{-}{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}.$ (59) $$

By the definition of sparse eigenvalues in Definition [V.1](#S5.Thmdefinition1), we have

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}\geq\rho_{{\cal L},-}(s){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2},$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{\mathbf{X}}^{2}\leq\rho_{{\cal L},+}(s){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}.$ $$

Applying the above inequalities in ([D-C](#A4.Ex28)), we have

$$ $\displaystyle(1-\varepsilon)\rho_{{\cal L},-}(s){\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}\leq\varepsilon\sqrt{\rho_{{\cal L},+}(s)}{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}+\zeta_{-}{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}^{2}$ $$

which leads to ([21](#S5.E21)).
∎

###### Definition D.1 .

($\varepsilon$-net) Let $(X,d)$ be a metric space and let $\varepsilon>0$. A subset $N_{\varepsilon}(X,d)$ is called an $\varepsilon$-net of $X$ if for every point $x\in X$, there exists some point $y\in N_{\varepsilon}(X,d)$ such that $d(x,y)\leq\varepsilon$. The minimal cardinality of an $\varepsilon$-net of $X$, if finite, is called the covering number of $X$ at scale $\varepsilon$.

###### Theorem D.4 (revised version of [ 18 , Theorem 2.1] with explicit constant in the bound for $\tilde{n}$ ) .

Let $0<\varepsilon,\delta<1$ and $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a Gaussian subspace embedding defined in Definition [II.2](#S2.Thmdefinition2). Then if
$\tilde{n}\geq 32\varepsilon^{-2}\log(2f_{0}/\delta)$, $\mathbf{P}$ is a $\textup{JLT}(\varepsilon,\delta,f_{0})$. That is, for any $f_{0}$-element set ${\cal V}$ and all $\mathbf{v},\mathbf{v}^{\prime}\in{\cal V}$, with probability at least $1-\delta$, it holds that $\left|\left\langle\mathbf{P}\mathbf{v},\mathbf{P}\mathbf{v}^{\prime}\right\rangle-\left\langle\mathbf{v},\mathbf{v}^{\prime}\right\rangle\right|\leq\varepsilon{\left\|\mathbf{v}\right\|}_{2}{\left\|\mathbf{v}^{\prime}\right\|}_{2}$.

###### Lemma D.5 .

Let $s\in[d]$, $s\geq 2$, $0<\varepsilon,\delta<1$, and $\mathbf{P}\in\mathbb{R}^{\tilde{n}\times n}$ be a Gaussian subspace embedding defined in Definition [II.2](#S2.Thmdefinition2). If
$\tilde{n}\geq c_{0}\varepsilon^{-2}\left(\log(2/\delta)+s\log d+s\log 5+1/d^{s-1}\right)$ where $c_{0}$ is a positive constant, then with probability at least $1-\delta$, the following inequalities hold:

$$ $\displaystyle\rho_{\tilde{\cal L},+}(s)\leq\rho_{{\cal L},+}(s)+\varepsilon\sqrt{s},\rho_{\tilde{\cal L},-}(s)\geq\rho_{{\cal L},-}(s)-\varepsilon\sqrt{s},$ (60) $\displaystyle{\left\|\nabla\tilde{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}\leq{\left\|\nabla{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}+\varepsilon\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}.$ (61) $$

###### Proof of Lemma D.5 .

Define the set

$$ $\displaystyle{\cal F}\coloneqq\bigcup_{\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s}{\cal F}_{\mathbf{S}},\quad{\cal F}_{\mathbf{S}}\coloneqq\left\{\mathbf{u}\in\mathbb{R}^{d}\mid\textup{supp}\left(\mathbf{u}\right)\subseteq\mathbf{S}\right\}.$ $$

Then $\left|{\cal F}\right|={d\choose s}<d^{s}$. We now consider the subspace

$$ $\displaystyle{\cal U}_{\mathbf{S}}\coloneqq\left\{\mathbf{u}=\mathbf{X}\mathbf{v}\mid{\left\|\mathbf{u}\right\|}_{2}=1,\mathbf{u}=\mathbf{X}\mathbf{v}\textup{ for some }\mathbf{v}\in{\cal F}_{\mathbf{S}}\right\},\quad\mathbf{S}\subseteq[d],\left|{\cal S}\right|=s.$ $$

It can be verified that the dimension of ${\cal U}_{\mathbf{S}}$ is not greater than $s$. Let $\gamma>0$, it follows by [, Lemma 5.2], there exists an $\gamma$-net $N_{\gamma}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\subseteq{\cal U}_{\mathbf{S}}$ of ${\cal U}_{\mathbf{S}}$ such that $\left|N_{\gamma}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\right|\leq\left(1+\frac{2}{\gamma}\right)^{s}$.

Define the set

$$ $\displaystyle{\cal V}_{s}\coloneqq\bigcup_{\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s}N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\bigcup\left(\bigcup_{i\in[d]}N_{1/2}(\mathbf{e}^{(i)},{\left\|\cdot\right\|}_{2})\right),$ $$

where $\mathbf{e}^{(i)}$ is the subspace spanned by $\left\{\mathbf{e}^{i},\bar{}\bm{\beta}\right\}$
where $\left\{\mathbf{e}^{i}\right\}_{i=1}^{d}$ is the standard basis of $\mathbb{R}^{d}$. As a result of the above argument, $f_{0}\coloneqq\left|{\cal V}_{s}\right|\leq{d\choose s}\cdot 5^{s}+25d$. It follows by standard calculation that $\log(2/\delta)+s\log d+s\log 5+1/d^{s-1}\geq\log(2f_{0}/\delta)$. It then follows by
Theorem [D.4](#A4.Thmtheorem4) that when
$\tilde{n}\geq c_{0}\varepsilon^{-2}\left(\log(2/\delta)+s\log d+s\log 5+1/d^{s-1}\right)\geq c_{0}\varepsilon^{-2}\log(2f_{0}/\delta)$ with $c_{0}=512$, $\mathbf{P}$ is a $\textup{JLT}(\varepsilon/4,\delta,f_{0})$. Therefore, with probability at least $1-\delta$, $\mathbf{P}$ is a $(1\pm\varepsilon/4)$ $\ell^{2}$-embedding for ${\cal V}_{s}$.

For any $\mathbf{u}\in{\cal U}_{\mathbf{S}}$, there exists a $\mathbf{u}^{\prime}\in N_{\gamma}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ such that ${\left\|\mathbf{u}-\mathbf{u}^{\prime}\right\|}_{2}\leq\gamma$. We now use the simpler notation $\left\langle\mathbf{P}\mathbf{u}^{\prime},\mathbf{P}\mathbf{v}^{\prime}\right\rangle=(1\pm\varepsilon)\left\langle\mathbf{u}^{\prime},\mathbf{v}^{\prime}\right\rangle$ to indicate $\left|\left\langle\mathbf{P}\mathbf{u}^{\prime},\mathbf{P}\mathbf{v}^{\prime}\right\rangle-\left\langle\mathbf{u}^{\prime},\mathbf{v}^{\prime}\right\rangle\right|\leq\varepsilon{\left\|\mathbf{u}^{\prime}\right\|}_{2}{\left\|\mathbf{v}^{\prime}\right\|}_{2}$ for any two numbers $\mathbf{u}^{\prime},\mathbf{v}^{\prime}$ in the following text.

We follow the construction in the proof of
[, Theorem 2.3], that is, we build a $1/2$-net $N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})\subseteq{\cal U}_{\mathbf{S}}$ of ${\cal U}_{\mathbf{S}}$. Given any $\mathbf{S}\subseteq[d],\left|{\cal S}\right|=s$, we now show in the sequel that if $\mathbf{P}$ is a $(1\pm\varepsilon/4)$ $\ell^{2}$-embedding for $N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$, that is, $\left\langle\mathbf{P}\mathbf{u}^{\prime},\mathbf{P}\mathbf{v}^{\prime}\right\rangle=(1\pm\varepsilon/4)\left\langle\mathbf{u}^{\prime},\mathbf{v}^{\prime}\right\rangle$
for all $\mathbf{u}^{\prime},\mathbf{v}^{\prime}\in N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$, then $\mathbf{P}$ is also a $(1\pm\varepsilon)$ $\ell^{2}$-embedding for ${\cal U}_{\mathbf{S}}$, that is,
$\left\langle\mathbf{P}\mathbf{u},\mathbf{P}\mathbf{v}\right\rangle=(1\pm\varepsilon)\left\langle\mathbf{u},\mathbf{v}\right\rangle$ for all
$\mathbf{u},\mathbf{v}\in{\cal U}_{\mathbf{S}}$. To see this, any $\mathbf{u}\in{\cal U}_{\mathbf{S}}$ can be expressed by

$$ $\displaystyle\mathbf{u}=\sum\limits_{j=0}^{\infty}\mathbf{u}^{j},\quad{\left\|\mathbf{u}^{j}\right\|}_{2}\leq\frac{1}{2^{j}},\mathbf{u}^{j}\in N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2}).$ (62) $$

([62](#A4.E62)) can be proved by induction. By the definition of $1/2$-net, there exists $\mathbf{u}^{0}\in N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ such that
${\left\|\mathbf{u}-\mathbf{u}^{0}\right\|}_{2}\leq 1/2$ and $\mathbf{u}=\mathbf{u}^{0}+(\mathbf{u}-\mathbf{u}^{0})$. Also, there exists $\mathbf{u}^{\prime 1}\in N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ such that
${\left\|((\mathbf{u}-\mathbf{u}^{0}))/{\left\|(\mathbf{u}-\mathbf{u}^{0})\right\|}_{2}-\mathbf{u}^{\prime 1}\right\|}_{2}\leq 1/2$, so that $\mathbf{u}=\mathbf{u}^{0}+\mathbf{u}^{1}+\left(\mathbf{u}-\mathbf{u}^{0}-\mathbf{u}^{1}\right)$ with $\mathbf{u}^{1}={\left\|(\mathbf{u}-\mathbf{u}^{0})\right\|}_{2}\mathbf{u}^{\prime 1}$,
${\left\|\mathbf{u}^{1}\right\|}_{2}\leq 1/2$, and ${\left\|\mathbf{u}-\mathbf{u}^{0}-\mathbf{u}^{1}\right\|}_{2}\leq 1/2^{2}$.
As the induction step, if $\mathbf{u}=\sum\limits_{j=0}^{k}\mathbf{u}^{j}+\left(\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right)$ for $k\geq 1$ such that ${\left\|\mathbf{u}^{j}\right\|}_{2}\leq\frac{1}{2^{j}}$ for all $j\in[0,k]$ and ${\left\|\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right\|}_{2}\leq 1/2^{k+1}$. Then there exists $\mathbf{u}^{\prime k+1}\in N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$ such that ${\left\|\left(\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right)/{\left\|\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right\|}_{2}-\mathbf{u}^{\prime k+1}\right\|}_{2}\leq 1/2$. As a result,
$\mathbf{u}=\sum\limits_{j=0}^{k+1}\mathbf{u}^{k+1}+\left(\mathbf{u}-\sum\limits_{j=1}^{k+1}\mathbf{u}^{j}\right)$ where $\mathbf{u}^{k+1}={\left\|\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right\|}_{2}\mathbf{u}^{\prime k+1}$,
${\left\|\mathbf{u}^{k+1}\right\|}_{2}\leq{\left\|\mathbf{u}-\sum\limits_{j=1}^{k}\mathbf{u}^{j}\right\|}_{2}\leq 1/2^{k+1}$ and ${\left\|\mathbf{u}-\sum\limits_{j=1}^{k+1}\mathbf{u}^{j}\right\|}_{2}\leq 1/2^{k+2}$.

It follows by ([62](#A4.E62)) that

$$ $\displaystyle{\left\|\mathbf{P}\mathbf{u}\right\|}_{2}^{2}$ $\displaystyle={\left\|\mathbf{P}\left(\sum\limits_{j=0}^{\infty}\mathbf{u}^{j}\right)\right\|}_{2}^{2}$ $\displaystyle=\sum\limits_{j=0}^{\infty}{\left\|\mathbf{P}\mathbf{u}^{j}\right\|}_{2}^{2}+2\sum\limits_{i<j}\left\langle\mathbf{P}\mathbf{u}^{i},\mathbf{P}\mathbf{u}^{j}\right\rangle$ $\displaystyle=\sum\limits_{j=0}^{\infty}\left(1\pm c\right){\left\|\mathbf{u}^{j}\right\|}_{2}^{2}+2\sum\limits_{i<j}\left\langle\mathbf{u}^{i},\mathbf{u}^{j}\right\rangle\pm\frac{\varepsilon}{4}\sum\limits_{i<j}{\left\|\mathbf{u}^{i}\right\|}_{2}{\left\|\mathbf{u}^{j}\right\|}_{2}$ $\displaystyle=\left(\sum\limits_{j=0}^{\infty}{\left\|\mathbf{u}^{j}\right\|}_{2}^{2}+2\sum\limits_{i<j}\left\langle\mathbf{u}^{i},\mathbf{u}^{j}\right\rangle\right)\pm\frac{\varepsilon}{4}\left(\sum\limits_{j=0}^{\infty}{\left\|\mathbf{u}^{j}\right\|}_{2}^{2}+2\sum\limits_{i<j}{\left\|\mathbf{u}^{i}\right\|}_{2}{\left\|\mathbf{u}^{j}\right\|}_{2}\right)$ $\displaystyle={\left\|\mathbf{u}\right\|}_{2}^{2}\pm\varepsilon{\left\|\mathbf{u}\right\|}_{2}^{2}=1\pm\varepsilon.$ (63) $$

It follows by ([D-C](#A4.Ex35)) that $\mathbf{P}$ is a $(1\pm\varepsilon)$ $\ell^{2}$-embedding for ${\cal U}_{\mathbf{S}}$.
Recall that $\mathbf{P}$ is a $(1\pm\varepsilon/4)$ $\ell^{2}$-embedding for ${\cal V}_{s}\supseteq\bigcup_{\mathbf{S}\subseteq[d],\left|{\cal S}\right|=s}N_{1/2}({\cal U}_{\mathbf{S}},{\left\|\cdot\right\|}_{2})$. By the above argument, $\mathbf{P}$ is also a $(1\pm\varepsilon)$ $\ell^{2}$-embedding
for ${\cal U}_{\mathbf{S}}$ for any $\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s$.

For any $\mathbf{v}\in\mathbb{R}^{d}$ such that ${\left\|\mathbf{v}\right\|}_{0}\leq s,{\left\|\mathbf{v}\right\|}_{2}=1$, there must exists a set $\mathbf{S}\subseteq[d],\left|\mathbf{S}\right|=s$ such that
$\mathbf{X}\mathbf{v}/{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}\in{\cal U}_{\mathbf{S}}$. As a result,

$$ $\displaystyle\left|\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{v}-\mathbf{v}^{\top}{\tilde{}\mathbf{X}}^{\top}{\tilde{}\mathbf{X}}\mathbf{v}\right|\leq\varepsilon{\left\|\mathbf{X}\mathbf{v}\right\|}_{2}^{2}\leq\varepsilon\sqrt{s},$ (64) $$

where the last inequality follows by $\max_{i\in[d]}{\left\|\mathbf{X}^{i}\right\|}_{2}\leq 1$. Therefore, $\rho_{\tilde{\cal L},+}(s)\leq\rho_{{\cal L},+}(s)+\varepsilon\sqrt{s}$, and $\rho_{\tilde{\cal L},-}(s)\geq\rho_{{\cal L},-}(s)-\varepsilon\sqrt{s}$.

Because $\mathbf{P}$ is a $(1\pm\varepsilon/4)$ $\ell^{2}$-embedding for ${\cal V}_{s}\supseteq\bigcup_{i\in[d]}N_{1/2}(\mathbf{e}^{(i)},{\left\|\cdot\right\|}_{2})$, $\mathbf{P}$ is also $(1\pm\varepsilon)$ $\ell^{2}$-embedding for $\mathbf{e}^{(i)}$ for all $i\in[d]$. Therefore, we have

$$ $\displaystyle\sup_{i\in[d]}{\mathbf{e}^{i}}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\bar{}\bm{\beta}-{{\tilde{}\mathbf{X}}}^{\top}{\tilde{}\mathbf{X}}\right)\bar{}\bm{\beta}\leq\varepsilon{\left\|\mathbf{X}\mathbf{e}_{i}\right\|}_{2}{\left\|\mathbf{X}\bar{}\bm{\beta}\right\|}_{2},$ $$

so that

$$ $\displaystyle{\left\|\nabla\tilde{\cal L}(\bar{}\bm{\beta})-\nabla\tilde{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}$ $\displaystyle={\left\|\mathbf{X}^{\top}\mathbf{X}\bar{}\bm{\beta}-{{\tilde{}\mathbf{X}}}^{\top}{\tilde{}\mathbf{X}}\bar{}\bm{\beta}\right\|}_{\infty}=\sup_{i\in[d]}{\mathbf{e}^{i}}^{\top}\left(\mathbf{X}^{\top}\mathbf{X}\bar{}\bm{\beta}-{{\tilde{}\mathbf{X}}}^{\top}{\tilde{}\mathbf{X}}\right)\bar{}\bm{\beta}$ $\displaystyle\leq\varepsilon{\left\|\mathbf{X}\mathbf{e}^{i}\right\|}_{2}{\left\|\mathbf{X}\bar{}\bm{\beta}\right\|}_{2}\leq\varepsilon\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}.$ $$

∎

###### Theorem D.6 .

###### Proof of Theorem V.4 .

It follows by ([60](#A4.E60)) in Lemma [D.5](#A4.Thmtheorem5) that

$$ $\displaystyle\rho_{\tilde{\cal L},-}(s)\geq\rho_{{\cal L},-}(s)-\varepsilon\sqrt{s}>0$ $$

with $s=s_{0}={\bar{s}}+2\tilde{s}$.
Moreover, it also follows by ([60](#A4.E60)) that

$$ $\displaystyle C^{\prime}\rho_{\tilde{\cal L},-}({\bar{s}}+2\tilde{s})\geq C^{\prime}\left(\rho_{{\cal L},-}({\bar{s}}+2\tilde{s})-\varepsilon\sqrt{{\bar{s}}+2\tilde{s}}\right)\geq\zeta_{-}.$ $$

In addition, by ([60](#A4.E60)) we have

$$ $\displaystyle\kappa^{\prime}=\frac{\rho_{{\cal L},+}(s_{0})+\varepsilon\sqrt{s_{0}}-\zeta_{+}}{\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}-\zeta_{-}}\geq\frac{\rho_{\tilde{\cal L},+}(s_{0})-\zeta_{+}}{\rho_{\tilde{\cal L},+}(s_{0})-\zeta_{-}}=\tilde{\kappa}$ $$

with $\tilde{\kappa}$ specified in
Assumption [4](#Thmassumption4).
Therefore, if $\left(144\kappa^{\prime 2}+250\kappa^{\prime}\right){\bar{s}}<\tilde{s}$, we have $\left(144\tilde{\kappa}^{2}+250\tilde{\kappa}\right)\bar{s}=\tilde{C}\bar{s}<\tilde{s}$
which completes the first part of the claim.

Now we need to verify that either condition (a) or condition (b) can lead to the following conditions:

$$ $\displaystyle\rho_{{\cal L},-}(s_{0})$ $\displaystyle>\varepsilon\sqrt{s_{0}},$ (65) $\displaystyle\zeta_{-}$ $\displaystyle\leq C^{\prime}\left(\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}\right),$ (66) $\displaystyle\left(144\kappa^{\prime 2}+250\kappa^{\prime}\right){\bar{s}}$ $\displaystyle<\tilde{s},\quad\kappa^{\prime}=(\rho_{{\cal L},+}(s_{0})+\varepsilon\sqrt{s_{0}}-\zeta_{+})/(\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}-\zeta_{-}).$ (67) $$

For condition (a), with $\log d/n\overset{n\to\infty}{\longrightarrow}0$, $\varepsilon=C_{1}\sqrt{\log d/n}$, we have
$\varepsilon\overset{n\to\infty}{\longrightarrow}0$. It can be verified that $\kappa^{\prime}\overset{n\to\infty}{\longrightarrow}\kappa$, and
([65](#A4.E65))-([67](#A4.E67))
holds with sufficiently large $n$ when Assumption [3](#Thmassumption3)
holds.

For condition (b), with $\zeta_{-}=C_{2}\rho_{{\cal L},-}(s_{0})$, $\varepsilon\sqrt{s_{0}}\leq C_{3}\rho_{{\cal L},-}(s_{0})$, $C_{2}+C_{3}<1$ and $C_{2}\leq C^{\prime}(1-C_{3})$,
([65](#A4.E65))-([66](#A4.E66))
hold. Moreover, we have

$$ $\displaystyle\kappa^{\prime}=\frac{\rho_{{\cal L},+}(s_{0})+\varepsilon\sqrt{s_{0}}-\zeta_{+}}{\rho_{{\cal L},-}(s_{0})-\varepsilon\sqrt{s_{0}}-\zeta_{-}}\leq\frac{(1+C_{3})\rho_{{\cal L},+}(s_{0})}{(1-C_{2}-C_{3})\rho_{{\cal L},-}(s_{0})}\leq\frac{(1+C_{3})(1+\delta)}{(1-C_{2}-C_{3})(1-\delta)}=\kappa_{0}.$ $$

As a result. $\tilde{s}>\left(144\kappa_{0}^{2}+250\kappa_{0}\right)\bar{s}$ leads to ([67](#A4.E67)).

∎

###### Proof of Theorem V.5 .

It follows by ([61](#A4.E61)) in
Lemma [D.5](#A4.Thmtheorem5) and
Lemma [D.7](#A4.Thmtheorem7) that

$$ $\displaystyle{\left\|\nabla\tilde{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}\leq{\left\|\nabla{\cal L}(\bar{}\bm{\beta})\right\|}_{\infty}+\varepsilon\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}\leq\left(C_{1}\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}+2\sigma\right)\sqrt{\frac{\log d}{n}}.$ (68) $$

Let $\lambda_{\textup{tgt}}=8\left(C_{1}\sqrt{{\bar{s}}}{\left\|\bar{}\bm{\beta}\right\|}_{2}+2\sigma\right)\sqrt{\frac{\log d}{n}}$. Because Assumption [4](#Thmassumption4) holds, we can apply the approximate path following method described in
[, Algorithm 1] to solve the original problem ([1](#S1.E1)) and the sketched problem ([2](#S1.E2)) to obtain $\tilde{}\bm{\beta}^{*}$ and $\tilde{}\bm{\beta}^{*}$ such that
$\bm{\beta}^{*}$ is an critical point of problem ([1](#S1.E1)) and $\tilde{}\bm{\beta}^{*}$
is an critical point of ([2](#S1.E2))
with ${\tilde{}\mathbf{X}}=\mathbf{P}\mathbf{X}$ and nonconvex regularizer $h_{\lambda_{\textup{tgt}}}$. Let ${\cal S}=\textup{supp}\left(\bar{}\bm{\beta}\right)$.
We can repeat the proof for [, Theorem 5.5] and conclude that

$$ $\displaystyle{\left\|\bm{\beta}^{*}_{{\cal S}^{c}}\right\|}_{0}\leq\tilde{s},\quad{\left\|\tilde{}\bm{\beta}^{*}_{{\cal S}^{c}}\right\|}_{0}\leq\tilde{s}.$ $$

The above inequalities show that $\left|\textup{supp}\left(\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right)\bigcup\textup{supp}\left(\bm{\beta}^{*}\right)\bigcup\textup{supp}\left(\tilde{}\bm{\beta}^{*}\right)\right|\leq s_{0}=\bar{s}+2\tilde{s}$. It then follows by
Corollary [V.2](#S5.Thmtheorem2) that

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}\leq\frac{\varepsilon\sqrt{\rho_{{\cal L},+}(s_{0})}}{(1-\varepsilon)\rho_{{\cal L},-}(s_{0})-\zeta_{-}}{\left\|\bm{\beta}^{*}\right\|}_{\mathbf{X}}.$ (69) $$

In addition, it follows by [, Theorem 4.7, Theorem 4.8] that the parameter estimation error of $\bm{\beta}^{*}$ satisfies

$$ $\displaystyle{\left\|\bm{\beta}^{*}-\bar{}\bm{\beta}\right\|}_{2}\leq(21/8)/\left(\rho_{{\cal L},-}(s_{0})-\zeta_{-}\right)\sqrt{\bar{s}}\lambda_{\textup{tgt}}.$ (70) $$

It follows by ([70](#A4.E70))
and ([69](#A4.E69)) that

$$ $\displaystyle{\left\|\tilde{}\bm{\beta}^{*}-\bm{\beta}^{*}\right\|}_{2}$ $\displaystyle\leq\frac{\varepsilon\sqrt{(\bar{s}+\tilde{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}{\left\|\bm{\beta}^{*}\right\|}_{2}$ $\displaystyle\leq\frac{\varepsilon\sqrt{(\bar{s}+\tilde{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}{\left\|\bar{}\bm{\beta}\right\|}_{2}+\frac{\varepsilon\sqrt{(\bar{s}+\tilde{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}\cdot(21/8)/\left(\rho_{{\cal L},-}(s_{0})-\zeta_{-}\right)\sqrt{\bar{s}}\lambda_{\textup{tgt}}$ $\displaystyle\leq\frac{\varepsilon\sqrt{(\bar{s}+\tilde{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}{\left\|\bar{}\bm{\beta}\right\|}_{2}+\frac{\sqrt{\bar{s}}\lambda_{\textup{tgt}}}{8\left(\rho_{{\cal L},-}(s_{0})-\zeta_{-}\right)}$ $\displaystyle\leq\frac{C_{1}{\left\|\bar{}\bm{\beta}\right\|}_{2}\sqrt{(1+\tilde{s}/\bar{s})\rho_{{\cal L},+}(s_{0})}}{(1+C^{\prime})/2\cdot\rho_{{\cal L},-}(s_{0})-\zeta_{-}}\sqrt{\frac{\bar{s}\log d}{n}}+\frac{\sqrt{\bar{s}}\lambda_{\textup{tgt}}}{8\left(\rho_{{\cal L},-}(s_{0})-\zeta_{-}\right)}$ (71) $$

([22](#S5.E22)) then follows by ([70](#A4.E70))
and ([D-C](#A4.Ex47)).

∎

###### Lemma D.7 ( [ 40 , Lemma 5] ) .

Under the linear model in Section [V](#S5), that is, $\mathbf{y}=\bar{}\mathbf{X}\bar{}\bm{\beta}+\bm{\varepsilon}$ where $\bm{\varepsilon}$ is a noise vector of i.i.d. sub-gaussian elements with variance proxy $\sigma^{2}$. Let $\mathbf{X}=\bar{}\mathbf{X}/\sqrt{n}$, $\mathbf{y}=\bar{}\mathbf{y}/\sqrt{n}$, and ${\cal L}(\bm{\beta})=1/2\cdot\bm{\beta}^{\top}\mathbf{X}^{\top}\mathbf{X}\bm{\beta}-\mathbf{y}^{\top}\mathbf{X}\bm{\beta}$. Then with probability at least $1-\eta$ for any $\eta\in(0,1)$,

$$ $\displaystyle{\left\|\nabla L(\bar{}\bm{\beta})\right\|}_{\infty}\leq\sqrt{2}\sigma\sqrt{\frac{\log(2d/\eta)}{n}}.$ (72) $$

###### Lemma D.8 ( [ 41 , Proposition 5.20] ) .

Let $d>2$. If $f\colon\mathbb{S}^{d-1}\to\mathbb{R}$ is a 1-Lipschitz function, then for any $t>0$,

$$ $\displaystyle\textup{Pr}\left[\left|f(\mathbf{x})-\mathbb{E}\left[f(\mathbf{x})\right]\right|>t\right]\leq 2\exp\left(-dt^{2}/2\right),$ (73) $$

where $\mathbf{x}$ is drawn uniformly from the unit sphere $\mathbb{S}^{d-1}$ in $\mathbb{R}^{d}$.

###### Proof of Corollary V.2 .

###### Definition D.1 .

###### Theorem D.4 (revised version of [ 18 , Theorem 2.1] with explicit constant in the bound for n ~ ~ 𝑛 \tilde{n} ) .

###### Lemma D.5 .

###### Proof of Lemma D.5 .

###### Theorem D.6 .

###### Proof of Theorem V.4 .

###### Proof of Theorem V.5 .

###### Lemma D.7 ( [ 40 , Lemma 5] ) .

###### Lemma D.8 ( [ 41 , Proposition 5.20] ) .

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: - line 30 “Sketching algorithms has been used to approximately” —>  “Sketching algorithms have been used to approximately”
- 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.
- line 68, you give the definition of the semi-norm ||u||_X twice 
- 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
- line 123: “It is comprised of ” —> “It consist of”
- lines 125-127 are quite obvious to me. I think you could just remove them
- line 136-140, in the Definition 2.1. is there any reason you use \ell^2 instead of \ell_2 ?
- line 142, Definition 2.2. looks more like a proposition (Lemma  perhaps) to me. 
- line 151 : “Taking derivative with respect to” —> “taking the derivative with respect to”?
- line 189-190 “is a more accuracy” —> “is a more accurate”
- line 170 “consectively” —> “consecutively” or “iteratively/alternatively”?
- 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.
- 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…”)
- 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}, -}. 
- 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}…”)
- 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)
- 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
- 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. 
- line 424 - 426 : “by arbitrary critical point ” —> “by any arbitrary critical point”
- 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
- 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.  
- Statement of Theorem 5.4., I would remove the sentence following Equation (17) as it refers to a result that does not appear? 
- 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
- general question: wouldn’t it be more efficient to draw a new sketch at each iteration in the iterative SRO algorithm ?
soundness: 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.
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.
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.

Also your key contribution is the sketching step so the \tilde{n} should appear more clearly in all your statements (see my comments below)

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see the weeknesses part.
soundness: 3
strengths: 1. This work addresses a wide range of optimization problems using sketching techniques, effectively handling both convex and nonconvex regularizations.
2. The introduction of SRO and its refined version demonstrate a well-thought-out approach that balances efficiency and accuracy in solving complex optimization tasks.
3. 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.
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.
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.
2. 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?
3. 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?
4. Some numerical experiments on nonconvex regularization should be conducted.

References
[1] Yang, Y., & Li, P.  FROS: Fast Regularized Optimization by Sketching. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 2780-2785.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 1
questions: - In the beginning of section D.2, is $O(s\log(d)/n)$ a typo (should there not be a square root there)?
- 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?
- 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.
- Can the authors provide some more details in their proof of their main theorem?
soundness: 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. 
I 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.
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.

Concretely, 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_*$.

The 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.
weaknesses: A big problem with this article is its presentation. Let me address some of the problems, in order of appearance.
- 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.
- 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)
- In equation 35, $\kappa$ is still present although $\kappa$ has been set to 0 just before.
- 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*.
- The sentence "We show that RIP($\delta,s$)" has appearantly lost its ending.
- Reference to equation (45) in the proof of Theorem 4.1 seems to be spurious.
- 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.
- Theorem D.6 has no statement.

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

However, 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)$?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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? 

2. 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? 

3. 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?

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

5. 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?
soundness: 3
strengths: 1. The introduction of the method is clear and easy to follow.
2. The motivation is clearly conveyed.
summary: This paper proposes a sketching method for convex and nonconvex regularized least squares and sharp theoretical guarantees are provided for the algorithms.
weaknesses: Please see following questions.

Meta-review: Dear Authors,

Thank you for your valuable contribution to the ICLR and the ML community. Your submitted paper has undergone a rigorous review process, and I have carefully read and considered the feedback provided by the reviewers.

This paper introduces an extension of the Iterative Hessian Sketch to the regularized setting. The methods Sketching for Regularized Optimization (SRO) and its iterative version can handle convex and non-convex regularizers. A theoretical framework is also presented to establish minimax rates. Overall, the paper received mostly positive response from the reviewers (8,6,6,6) scores.

Given this positive assessment, I am willing to recommend the acceptance of your paper for publication.

I would like to remind you to carefully review the reviewer feedback and the resulting discussion. While most reviews were positive, the reviewers have offered valuable suggestions that can further strengthen the quality of the paper. Please take another careful look a the 'weaknesses' section of each reviewer comment. I encourage you to use this feedback to make any necessary improvements and refinements before submitting the final version of your paper.

Once again, thank you for submitting your work to ICLR.

Best,
Area Chair

Decision: Accept (Poster)