Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

(1) Novelty of Our Results and Their Significant Difference from [Pilanci2016]

We respectfully point out that the claim “This work appears to be a straightforward extension of [Pilanci2016] with the addition of a regularization term…” in this review is a factual misunderstanding. Our results are novel and significantly different from those in [Pilanci2016], which is detailed in line 437-459 of the revied paper and copied below for your convenience. It is remarked that [Pilanci2016] only handles convex constrained least square problems of the form $\min _ {\mathbf X \in \mathcal C} || \mathbf X \mathbf \beta-\mathbf y ||^2$ where the constraint set $\mathcal C$ is a convex set, while our results cover regularized convex and nonconvex problems with minimax optimal rates. It is emphasized that the techniques in [Pilanci2016] can never be applied to the regularized problems considered in this paper. [Pilanci2016] heavily relies on certain complexity measure of the constraint set $\mathcal C$, such as the Gaussian width. It shows that the complexity of such constraint set $\mathcal C$ is bounded, so that sketching with such constraint set $\mathcal C$ of limited complexity only incurs a relatively small approximation error. However, there is never such constraint set in the original problem (Eq. (1)) or the sketched problem (Eq. (2)), so that such complexity based analysis for sketching cannot be applied to this work. Furthermore, as mentioned in Section 1.1, Iterative SRO does not need to sample the projection matrix and compute the sketched matrix at each iteration, in contrast with IHS [Pilanci2016] where a separate projection matrix is sampled and the sketched matrix is computed at each iteration. As evidenced by Table 1 in Section 7.1, Iterative SRO is more efficient than its “HIS” counterpart where sketching is performed at every iteration while enjoying comparable approximation error.

(2) Improved Presentation

”The notations are not very clear. …represents the critical point of the objective function (2) ...".

The meaning of …$\tilde {\mathbf \beta}^*$ has been clearly indicated in every theoretical result in the revised paper. In particular, when using Iterative SRO for sparse convex learning in Section 4.1, it is clearly stated in Theorem 4.1 that $\tilde {\mathbf \beta}^* = \mathbf \beta^{(N)}$ (line 262-263 of the revised paper or line 254-255 of the original submission). When using SRO for sparse nonconvex learning in Section 4.2, it is clearly stated in Theorem 4.2 that $\tilde {\mathbf \beta}^*$ is the optimization result of the sketched problem (Eq. (2)) in line 368-369 of the revised paper. To make the meaning of $\tilde {\mathbf \beta}^*$ even clearer, it is stated in line 237-238 of the revised paper that “In Section 4.1, $\tilde {\mathbf \beta}^*$ is obtained by Algorithm 1 through $\tilde {\mathbf \beta}^* = \mathbf \beta^{(N)}$. In Section 4.2, $\tilde {\mathbf \beta}^*$ is the optimization result of the sketched problem (2)” (Section 4.1 in line 238 should be Section 4.2).

(3) "…iterative SRO, it only concerns the convex regularization for $h_{\lambda}(\mathbf \beta)$. Is there any particular reason that it cannot be applied to nonvex regularization?..."

We respectfully point out that it is a factual misunderstanding that Iterative SRO cannot be applied to nonconvex regularizer. Theorem 3.1 (in both original submission and the revised paper) shows that iterative SRO can handle nonconvex regularizer $h = h_{\lambda}(\cdot)$ as long as the Frechet subdifferential of $h$ is $L_h$-smooth, and please refer to line 215-216 for the definition of $L_h$-smoothness. It is remarked that a $L_h$-smooth function $h$ can definitely be nonconvex.

(4) "organization…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."

We have improved the organization of the theoretical results. In particular, Theorem 5.2 and Theorem 5.4 (which now become Theorem D.2 and Theorem D.3 of the revised paper), as the intermediate steps for the proof of Theorem 3.1, have been moved to Section D of the revised paper, following the suggestion of Reviewer 2raj for the improved clarity of this paper. Now all the results presented before Theorem D.2 in the revised paper, including Corollary 4.2, do not depend on the conditions of the original Theorem 5.2 (or Theorem D.2 of the revised paper).

(5) "…why the running time for SRO is longer than those iterative algorithm?..."

The reason that the running time of SRO is longer than that of Iterative SRO is explained in line 511-518 of the revised paper, which is copied below for your convenience. In summary, the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) is used as the optimization algorithm to solve the original and the sketched problems, and Iterative SRO can use much less iterations of FISTA compared to SRO, explaining that Iterative SRO takes less running time than SRO in Table 1.

The maximum iteration number of FISTA for Iterative SRO ($2000$) is much smaller than that for SRO ($10000$). This is because Iterative SRO uses an iterative sketching process where the approximation error is geometrically reduced with respect to the iteration number $t$ in Algorithm 1, so that each iteration of Iterative SRO is only required to have a moderate approximation error which can be larger than the approximation error of SRO thus a smaller iteration number of FISTA suffices for each iteration of Iterative SRO. Such analysis also explains the fact that Iterative SRO is much faster than SRO, and in our experiment the maximum iteration number $N$ for Iterative SRO described in Algorithm 1 is always not greater than $5$.

References

[Pilanci2016] Pilanci et al. Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 2016.

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

(1) Improved Presentation

"It takes some effort to sort out the relations between the problems (2), (5) and (6)…"

Herein we provide a detailed description of problems (2), (5) and (6). Problem (2) is the sketched problem corresponding to the original problem (1), where the data matrix $\mathbf X$ is replaced by its sketched version $\tilde {\mathbf X}$ in problem (2).

Problem (5) is the intermediate problem at every iteration of the Iterative SRO described in Algorithm 1. The solution to problem (5), $\mathbf \beta^{(t)}$, is supposed to approximate the original solution $\mathbf \beta^*$ better than its predecessor, $\mathbf \beta^{(t-1)}$ obtained at the previous iteration of the Iterative SRO. Theorem 3.1 shows that $\mathbf \beta^{(t)}$ is geometrically close to $\mathbf \beta^*$ (by Eq. (8)).

Problem (6)-(7) are used to explain the proof of Theorem 3.1, in particular, why $\mathbf \beta^{(t)}$ can be geometrically close to $\mathbf \beta^*$. In particular, at the $t$-th iteration of Iterative SRO, the solution to problem (6) is in fact the gap between $\mathbf \beta^*$ and $\mathbf \beta^{(t)}$, or $\mathbf \beta^* - \mathbf \beta^{(t)}$ . We then solve the sketched version of problem (6), which is problem (7), so that the solution $\hat {\mathbf \beta}$ to problem (7) is an approximation to $\mathbf \beta^* - \mathbf \beta^{(t)}$. If such approximation can have a relative-error approximation error in Eq. (3), that is, $\hat {\mathbf \beta} – (\mathbf \beta^* - \mathbf \beta^{(t)}) \le \rho (\mathbf \beta^* - \mathbf \beta^{(t)})$, then since $\mathbf \beta^{(t)} = \mathbf \beta^{(t-1)} + \hat {\mathbf \beta}$, we have $|| \mathbf \beta^{(t)} - \mathbf \beta^*|| _ {\mathbf X} = || \hat {\mathbf \beta} – (\mathbf \beta^* -\mathbf \beta^{(t-1)}) || _ {\mathbf X} \le \rho || \mathbf \beta^* -\mathbf \beta^{(t-1)} || _ {\mathbf X}$. As a result, by mathematical induction, we have $|| \mathbf \beta^{(t)} - \mathbf \beta^*|| _ {\mathbf X} \le \rho^{t} ||\mathbf \beta^*|| _ {\mathbf X}$ for all $t \ge 0$. We will put the above detailed description in the final version of this paper.

"…proof of Theorem 5.2 are written down in an unnecessarily complicated…", "$\kappa$ is still present … set to $0$".

We have revised the proof of this Theorem following your suggestions (now it becomes Theorem D. 2 of the revised paper). Please kindly refer to the “Proof of Theorem D.2” in Section D of the appendix of the revised paper. In addition, we have removed the term with $\kappa$ in this equation (now Eq. (37) of the revised paper).

"There are many steps in the proof of the main result that are only sketched, in particular for $L_h$-smooth $h$...".

The detailed steps for $L_h$-smooth $h$ are provided in the revised paper, and please kindly refer to line 1080-1100 in the proof of Theorem D.3, and line 1121-1133 in the proof of Theorem 3.1 for these detailed steps.

"The term JLT in Theorem D.4 is undefined…".

In Theorem D.6 of the revised paper, it is now clearly mentioned that JLT refers to the Johnson–Lindenstrauss Transform, and it is defined in line 1307-1308.

We would also like to mention that Theorem D.2 and Theorem D.3, as the intermediate results for the proof of Theorem 3.1, have been moved to Section D of the revised paper, following the suggestion of Reviewer 2raj for the improved clarity of this paper. All the other presentation issues have either been fixed in the revised paper, such as $\mathcal O(\sqrt{\bar s \log d/n})$ instead of $\mathcal O(\bar s \log d/n)$ in the beginning of Section D.3, or will be fixed in the final version of this paper (such as the reference to Eq. (51) instead of (52) in line 1253).

(2) Improved Theorem D.2 (now Theorem D.4 in the revised paper).

We have revised Theorem D.4 and provided more details in its proof in the revised paper. Now $n$ should satisfy $n \ge (\Theta(s\log d))^{1/\alpha_0}$ where $\alpha_0$ is is an arbitrary positive constant such that $\alpha_0 \in (0,1)$. It is noted that we need $n \ge (\Theta(s\log d))^{1/\alpha_0}$ so that $\textup{RIP}(\delta,s)$ in Theorem D.4 happens with probability arbitrarily close to $1$ as $n \to \infty$.

We have also discussed the impact of $\alpha_0$ and the alterative construction of the low-rank matrix suggested in this review, and the trade-off between our construction and the suggested construction in line 1209-1223 of the revised paper. In particular, we show that the low-rank matrix constructed by the suggested way in fact satisfies $\textup{RIP}(\delta,s)$ with the optimal size $n \asymp \Theta(s \log d)$.

First, by letting the constant $\alpha_0 \to 1$, the lower bound for $n$ is $(\Theta(s \log d))^{1/\alpha_0}$ in Theorem D. 4, which can be close to the sample optimal $\Theta(s \log d)$. Furthermore, one can also construct the low-rank matrix $\mathbf X = \mathbf U \mathbf A$ where $\mathbf U \in {\mathbb R}^{n \times m}$ is sampled from the Stiefel manifold $V_{m}({\mathbb R}^{n})$ comprising all the $n \times m$ matrices of orthogonal columns with $n \ge m$, and all the elements of $\mathbf A \in {\mathbb R}^{m \times d}$ are i.i.d. Gaussian random variables with $\mathbf A_{ij} \sim \mathcal N(0,1/m)$ for $i \in [m], j \in [d]$. Then $\textup{rank}(\mathbf X) \le m$, and it follows by Theorem 5.2 of [Baraniuk2008] that when $m \ge \Theta(s \log d)$, then $\mathbf A$ satisfies $\textup{RIP}(\delta,s)$. Since $\mathbf X^{\top} \mathbf X = \mathbf A^{\top} \mathbf A$, it follows that w.h.p. (with high probability) $\mathbf X$ also satisfies $\textup{RIP}(\delta,s)$. The latter construction can admit the optimal size $n \asymp \Theta(s \log d)$. On the other hand, $\textup{rank}(\mathbf X) \to \infty$ as $d \to \infty$ in latter construction, while the construction in Theorem D.4 allows for arbitrarily specified rank of the constructed $\mathbf X$.

References

[Baraniuk2008] Baraniuk et al. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 2008.

We would like to provide further clarification regarding the "Ethics Concerns" provided in the updated review, and we respectfully point out that the "Ethics Concerns" contain several factually wrong statements which result in the wrong conclusion for the raised research integrity issue.

"The ideas of the paper are also more or less identical..." This statement is factually and completely wrong. We would like to emphasize that while [YangLi2021] also studies sketching for regularized optimization problem with an iterative sketching algorithm, the focus and results of this work are completely different from that in [YangLi2021], with a detailed discussion in Section 5 of the revised paper. In particular, due to our novel results in the approximation error bounds in Theorem D.2 and Theorem D.3, the proposed iterative sketching algorithm, Iterative SRO, does not need to sample a new projection matrix and compute the sketched matrix at every iteration, in a strong contrast to [YangLi2021]. Moreover, the focus of this work is to establish minimax optimal rates for sparse convex and nonconvex learning problems by sketching, which has not been addressed by existing works in the literature including [YangLi2021]. While [YangLi2021] only focuses on the optimization perspective, that is, approximating the solution to the original optimization problem by the solution to the sketched problem, the focus of this work needs much more efforts beyond the efforts made in [YangLi2021] for optimization only: we need to show that the solution to the sketched problem can still enjoy the minimax optimal rates for estimation of the sparse parameter vector for both sparse convex and nonconvex learning problems. Such minimax optimal results are established in a highly non-trivial manner. For example, to the best of our knowledge, Theorem 4.1 is among the first in the literature which uses an iteratively sketching algorithm to achieve the minimax optimal rate for sparse convex learning. Furthermore, Theorem 4.5 shows that sketching can also lead to the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems is still considered difficult and open in the literature.

"In particular, if the authors of this article have applied a different strategy to draw the random sketches compared to [YangLi2021] to generate Figure 1, I find it highly unlikely that they arrive at the exact same error bounds." This statement is factually and completely wrong. As mentioned above and in Section 5, we rigorously prove in Theorem 3.1 that the new sampling strategy used in our Iterative SRO achieves the approximation error in Eq. (8), which is the same theoretical guarantee in Theorem 3 of [YangLi2021]. However, our new sampling strategy is novel and efficient as explained above and in Section 5 of the revised paper. We would like to respectfully point out that we obtained the same Figure 1 because we used the same data as that in [YangLi2021] in the original Figure 1, which has already been mentioned in our response to Reviewer X44j. However, Figure 1 has been updated with different data in the experiment in the revised paper.

"Since [YangLi2021] was not cited in the submitted version of the paper, this raises ethical concerns in my view". We would respectfully point out that [YangLi2021] was not cited initially due to negligence, and we cited [YangLi2021] with a detailed discussion about the novelty of our results and their significant differences from [YangLi2021]. Such detailed discussion has been acknowledged by Reviewer X44j, but unfortunately missed in this review.

Finally, as mentioned in this comment, applied mathematical results admit common and standard description. To this end, we provide as follows a revised abstract and revised introduction for this paper, which will replace the corresponding and existing parts in the abstract and introduction of the current version of this paper and solve the overlapping text issue. We sincerely hope this reviewer would reconsider the raised "research integrity issue" which was based on all the factual misunderstandings described above.

I thank the reviewers for the update. It in large addresses the issues of the presentation I had with the first version of the paper - with the exception of the two below concerns.

First, the improved theorem D.2 is still not entirely clear to me -- the $\alpha_0$-constant now seems to be a constant that can be chosen freely. However, \alpha_0 only appears (without specification) when concentration of $\xi_2$-variables is applied. This makes it look like alpha_0 is the dimensions-of-freedom parameter of the $\chi_2$-variable? Is this the case? Then, $\alpha_0$ can not be arbitrariliy chosen. Also, in the proof, $n$ is still required to be larger than a threshold with unclear dependence of $\alpha_0$. This can and should still be made clearer in my opinion.

Also, reviewer X44j makes a good point that the paper has a significant overlap with [YangLi2021]. I am not entirely convinced that the 'only-one-sketch' aspect of the work at hand is significant enough to claim novelty - while the algorithm in [YangLi2021] specifies that the random projections should be redrawn, it does not appear that this is used in their analysis. In my opinion, there are however still enough new theoretical results and proofs in the paper at hand compared to [YanLi2021] to justify a publication. However, I cannot fairly judge how large of an issue the overlap is given the information I have, and have therefore flagged the paper for an ethical review to make sure a fair judgement is made.

All in all, the authors have made an effort to increase the readability of the paper, and addressed my concerns. Leaving the potential issue with the overlap aside, I will therefore raise my score to a 6.

New Abstract (to replace the current Abstract)

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

New Introduction (to replace the corresponding parts in the current Introduction Section)

Randomized algorithms for efficient optimization are a critical area of research in machine learning and optimization, with wide-ranging applications in numerical linear algebra, data analysis, and scientific computing. Among these, matrix sketching and random projection techniques have gained significant attention for solving sketched problems at a much smaller scale (Vempala, 2004; Bout- sidis & Drineas, 2009; Drineas et al., 2011; Mahoney, 2011; Kane & Nelson, 2014). These methods have been successfully applied to large-scale problems such as least squares regression, robust regression, low-rank approximation, singular value decomposition, and matrix factorization (Halko et al., 2011; Lu et al., 2013; Alaoui & Mahoney, 2015; Raskutti & Mahoney, 2016; Yang et al., 2015; Drineas & Mahoney, 2016; Oymak et al., 2018; Oymak & Tropp, 2017; Tropp et al., 2017). Regularized optimization problems with convex or nonconvex regularization, such as the widely used in $\ell^1$ or $\ell^2$-norm regularized least squares commonly known as Lasso and ridge regression, play a fundamental role in machine learning and statistics. While prior research has extensively explored random projection and sketching methods for problems with standard convex regularization (Zhang et al., 2016b) or convex constraints (Pilanci & Wainwright, 2016), there has been limited focus on analyzing regularized problems with general convex or nonconvex regularization frameworks.

We would like to emphasize that while [YangLi2021] also studies sketching for regularized optimization problem, the focus and results of this work are completely different from that in [YangLi2021], with a detailed discussion deferred to Section 5. In particular, due to our novel result in the approximation error bound (Theorem D.2-Theorem D.3), the proposed iterative sketching algorithm, Iterative SRO, does not need to sample a new projection matrix and compute the sketched matrix at every iteration, in a strong contrast to [YangLi2021]. Moreover, the focus of this work is to establish minimax optimal rates for sparse convex and nonconvex learning problems by sketching, which has not been addressed by existing works in the literature including [YangLi2021]. While [YangLi2021] only focuses on the optimization perspective, that is, approximating the solution to the original optimization problem by the solution to the sketched problem, the focus of this work needs much more efforts beyond the efforts made in [YangLi2021] for optimization only: we need to show that the solution to the sketched problem can still enjoy the minimax optimal rates for estimation of the sparse parameter vector for both sparse convex and nonconvex learning problems. Such efforts and results in minimax optimal rates for sparse convex and nonconvex learning problems by sketching have not been offered by previous works including [YangLi2021], which are provided in Section 4 of this paper. Such minimax optimal results are established in a highly non-trivial manner. For example, to the best of our knowledge, Theorem 4.1 is among the first in the literature which uses an iteratively sketching algorithm to achieve the minimax optimal rate for sparse convex learning. Furthermore, Theorem 4.5 shows that sketching can also lead to the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems is still considered difficult and open in the literature.

(3) Assumption of full column rank in Theorem 3.1

We would like to emphasize that Theorem 3.1 holds for either of the two cases: (1) the regularizer $h = h_{\lambda}$ is convex, or (2) $\mathbf X$ is of full rank. Throughout this paper, we only apply Theorem 3.1 for convex regularizer $h$, such as the proof of the minimax optimal rates by sketching for sparse convex learning in Theorem 4.1, and in such applications of Theorem 3.1 we do not require $\mathbf X$ to have full rank. In summary, all the theoretical and empirical results of this paper using Theorem 3.1 do not need $\mathbf X$ to have full rank.

On the other hand, Theorem 3.1 can also be applied to nonconvex regularizer $h$. In order to ensure that the Iterative ROS algorithm can also enjoy the exponential decay of the approximation error (In Eq. (8) of Theorem 3.1), we need a full rank $\mathbf X$. It is still open in the sketching literature that how iterative sketching can render the same guarantee for nonconvex functions as that for convex functions, and our Theorem 3.1 gives a partial solution to this open problem with the condition that $\mathbf X$ is of full rank.

(4) Numerical Results for Nonconvex Regularization

Thank you for your suggestion, and we present the empirical study of SRO for sparse nonconvex learning with capped-$\ell^1$ regularization in Section C.5 of the revised paper.

References

[YangLi2021] FROS: fast regularized optimization by sketching. In IEEE Interna tional Symposium on Information Theory, 2021.

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.

(1) Novelty of Our Results and Their Significant Difference from [YangLi2021]

In Line 437-495 of the revised paper, we explain the novelty of our Results and their significant difference from [YangLi2021], which is copied below for your convenience.

It is remarked that our results, including the Iterative SRO algorithm in Algorithm 1and its theoretical guarantee in Theorem 3.1, Theorem D.2-Theorem D.3, and the minimax optimal rates by sketching for sparse convex learning in Theorem 3.1 and sparse nonconvex learning in Theorem 4.5, are all novel and significantly different from [YangLi2021] in the following two aspects, although [YangLi2021] also presents an iterative sketching algorithm for regularized optimization problems. First, Iterative SRO does not need to sample a projection matrix $\mathbf P \in {\mathbb R}^{\tilde n \times n}$ and compute the sketched matrix $\tilde {\mathbf X} = \mathbf P \mathbf X$ at every iteration, while the iterative sketching algorithm in [YangLi2021] samples a different projection matrix and computes the sketched matrix at every iteration which incurs considerable computational cost for large-scale problem with large data size $n$. Such advantage of Iterative SRO over [YangLi2021] is attributed to the novel theoretical results in Theorem D.2-Theorem D.3 and Theorem 3.1. In contrast with Theorem 1 in [YangLi2021], the approximation error bound Theorem D.2 is derived for sketching low-rank data matrix by oblivious $\ell^2$-subspace embedding with the sketched size $\tilde n$ clearly specified. As a result, Theorem D.3 presents the approximation error bounds for convex and certain nonconvex regularization by sketching with oblivious $\ell^2$-subspace embedding. Based on such results, Theorem 3.1 shows that a single projection matrix suffices for the iterative sketching process. Second, minimax optimal rates for convex and nonconvex sparse learning problems by sketching are established by our results, while there are no such minimax optimal rates by a sketching algorithm in [YangLi2021]. Theorem 4.1, to the best of our knowledge, is among the first in the literature which uses an iteratively sketching algorithm to achieve the minimax optimal rate for sparse convex learning. Furthermore, Theorem 4.5 shows that sketching can also lead to the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems is still considered difficult and open in the literature.

We would also like to mention that Theorem D.2 and Theorem D.3, as the intermediate steps for the proof of Theorem 3.1, have been moved to Section D of the revised paper, following the suggestion of Reviewer 2raj for the improved clarity of this paper. The presentation style of Theorem D.2 and Theorem D.3 has also been revised. Figure 1 in the original paper coincided with that of [YangLi2021] because we used the same data for the experiment with Generalized Lasso as [YangLi2021]. In the revised paper, new experimental results are reported with different generated data and different $\gamma$ (recall that $\gamma$ decides the sketch size $\tilde n$) so that both Figure 1 and Table 1 have been updated in the revised paper.

(2) More Explanation regarding Definition 5.2

In Remark 5.1 of the revised paper, we provide more explanation regarding the degree of nonconvexity defined in Definition 5.2. In particular, the impact of a nonconvex function $h$ on the degree of nonconvexity is explained as follows. The degree of nonconvexity of a second-order differentiable and nonconvex function $h$ satisfies $\theta_{h}(\mathbf t,\kappa) \le 0$ if $h$ is “more PSD” than $-\kappa || \cdot ||^2$, that is, the smallest eigenvalue of its Hessian is not less than $-\kappa$. In other words, when the smallest eigenvalue of its Hessian of the nonconvex function $h$ is not less than $-\kappa$, then its degree of nonconvexity with $\kappa$, $\theta_{h}(\mathbf t,\kappa)$, is always not greater than $0$.

Two commonly used nonconvex functions for sparse learning, the smoothly clipped absolute deviation (SCAD) and the minimax concave penalty (MCP), are introduced in Section A of both the original paper and the revised paper. These two nonconvex functions satisfy Assumption 2, so there exists a positive concavity parameter $\zeta_{-} > 0$ such that the smallest eigenvalue of its Hessian is not less than $-\zeta_{-} > 0$. As a result, the degree of nonconvexity of both SCAD and MCP satisfies $\theta_{h}(\mathbf t, -\zeta_{-}) \le 0$.

We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper without special notes.

(1) Novelty of Our Results and Their Significant Difference from [Pilanci2016]

We respectfully point out that the claim “An incremental result is not necessarily a bad result…” in this review is a factual misunderstanding. Our results are novel and significantly different from those in [Pilanci2016], which is detailed in line 437-459 of the revied paper and copied below for your convenience. It is remarked that [Pilanci2016] only handles convex constrained least square problems of the form $\min _ {\mathbf X \in \mathcal C} || \mathbf X \mathbf \beta-\mathbf y ||^2$ where the constraint set $\mathcal C$ is a convex set, while our results cover regularized convex and nonconvex problems with minimax optimal rates. It is emphasized that the techniques in [Pilanci2016] can never be applied to the regularized problems considered in this paper. [Pilanci2016] heavily relies on certain complexity measure of the constraint set $\mathcal C$, such as the Gaussian width. It shows that the complexity of such constraint set $\mathcal C$ is bounded, so that sketching with such constraint set $\mathcal C$ of limited complexity only incurs a relatively small approximation error. However, there is never such constraint set in the original problem (Eq. (1)) or the sketched problem (Eq. (2)), so that such complexity based analysis for sketching cannot be applied to this work. Furthermore, as mentioned in Section 1.1, Iterative SRO does not need to sample the projection matrix and compute the sketched matrix at each iteration, in contrast with IHS [Pilanci2016] where a separate projection matrix is sampled and the sketched matrix is computed at each iteration. As evidenced by Table 1 in Section 7.1, Iterative SRO is more efficient than its “HIS” counterpart where sketching is performed at every iteration while enjoying comparable approximation error.

(2) Improved Presentation

The meaning of …$\tilde {\mathbf \beta}^*$ has been clearly indicated in every theoretical result in the revised paper. In particular, when using Iterative SRO for sparse convex learning in Section 4.1, it is clearly stated in Theorem 4.1 that $\tilde {\mathbf \beta}^* = \mathbf \beta^{(N)}$ (line 262-263 of the revised paper or line 254-255 of the original submission). When using SRO for sparse nonconvex learning in Section 4.2, it is clearly stated in Theorem 4.2 that $\tilde {\mathbf \beta}^*$ is the optimization result of the sketched problem (Eq. (2)) in line 368-369 of the revised paper. To make the meaning of $\tilde {\mathbf \beta}^*$ even clearer, it is stated in line 237-238 of the revised paper that “In Section 4.1, $\tilde {\mathbf \beta}^*$ is obtained by Algorithm 1 through $\tilde {\mathbf \beta}^* = \mathbf \beta^{(N)}$. In Section 4.2, $\tilde {\mathbf \beta}^*$ is the optimization result of the sketched problem (2)” (Section 4.1 in line 238 should be Section 4.2).

We have improved the organization of the theoretical results, and Theorem 5.2 and Theorem 5.4 (which now become Theorem D.2 and Theorem D.3 of the revised paper), as the intermediate result for the proof of Theorem 3.1, has been moved to Section D of the revised paper, following the suggestion of this review for the improved clarity of this paper. We have also fixed the presentation issues or typos mentioned in all the questions in this review.

”…wouldn’t it be more efficient to draw a new sketch at each iteration in the iterative SRO algorithm ?”

As explained in line 443-447 of the revised paper, if we draw a new sketch at each iteration of Iterative SRO, then at each iteration of Iterative SRO a new projection matrix $\mathbf P \in {\mathbb R}^{\tilde n \times n}$ is sampled and a new sketched matrix $\tilde {\mathbf X} = \mathbf P \mathbf X$ is computed, which incurs considerably more computational cost for large-scale problem with large data size $n$ compared to the proposed Iterative SRO described in Algorithm 1 where only a single projection matrix is sampled and a single sketch matrix is computed throughout all the iterations of the Iterative SRO.

References

[Pilanci2016] Pilanci et al. Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 2016.

(cont'd) In particular, due to our novel result in the approximation error bound (Theorem D.2-Theorem D.3), the proposed iterative sketching algorithm, Iterative SRO, does not need to sample a new projection matrix and compute the sketched matrix at every iteration, in a strong contrast to [YangLi2021]. Moreover, the focus of this work is to establish minimax optimal rates for sparse convex and nonconvex learning problems by sketching, which has not been addressed by existing works in the literature including [YangLi2021]. While [YangLi2021] only focuses on the optimization perspective, that is, approximating the solution to the original optimization problem by the solution to the sketched problem, the focus of this work needs much more efforts beyond the efforts made in [YangLi2021] for optimization only: we need to show that the solution to the sketched problem can still enjoy the minimax optimal rates for estimation of the sparse parameter vector for both sparse convex and nonconvex learning problems. Such efforts and results in minimax optimal rates for sparse convex and nonconvex learning problems by sketching have not been offered by previous works including [YangLi2021], which are provided in Section 4 of this paper. Such minimax optimal results are established in a highly non-trivial manner. For example, to the best of our knowledge, Theorem 4.1 is among the first in the literature which uses an iteratively sketching algorithm to achieve the minimax optimal rate for sparse convex learning. Furthermore, Theorem 4.5 shows that sketching can also lead to the minimax optimal rate even for sparse nonconvex problems, while sketching for nonconvex problems is still considered difficult and open in the literature. (end of the new Introduction)

Finally, we will be happy to work with the ethical reviewer and the AC to solve any remaining text overlap issues (if there are any).

Best Regards,

The Authors