Optimization over Sparse Restricted Convex Sets via Two Steps Projection

Dear Reviewer cMSm, we sincerely appreciate your support for our paper, even amid a challenging medical emergency.

Thank you for your insightful review and appreciation of our work.

Your comment: At present there is no proof outline, which makes it difficult to understand the novelty in the proof technique compared to the literature.

Our response: Thank you for your suggestion, we have added a proof outline for Theorem 1 in the main paper, and additional explanations on the key parts of our proofs at the beginning of Appendix E.1 and E.3 (from the new revision).

Your comment: In the experiments, there is currently no comparison with existing methods. I think this would have been nice to illustrate on synthetic data, and would also provide an empirical validation of the theoretical results.

Our response: In our experiment from the main paper (Section 5) about the portfolio optimization problem, we compared our algorithm with a naive algorithm: a projected gradient descent with only $\Gamma$ as constraint, followed by a hard-thresholding at the last iteration. In the new revision, we also added an additional baseline which is IHT followed, after its last iteration, by Euclidean projection onto $\Gamma$. Indeed, with the constraint $\Gamma$ from this experiment, there is, up to our knowledge, no closed-form for the Euclidean projection (EP) onto our mixed constraint, which is why there are no other baselines to compare our algorithm with. Regarding more synthetic experiments to illustrate our theoretical results, we compared the TSP and EP in our section F.2 which also includes some discussions on our theoretical results and the role of $\rho$ (we have updated that section to match our new Assumption 3 in the new revision), and following your suggestion, we have added a new section in Appendix F.4 with more synthetic experiments to specifically discuss our novel bounds and their dependence on $\rho$.

Your comment: I think the statement of assumption 3 is currently written in the form of a definition.

Our response: Thank you, we have rewritten all assumptions in an assumption form.

Your comment: In Remark 1, the fourth bullet should ideally be the second bullet, just to introduce the notion of convex symmetric sets first.

Our response: Thank you, we have updated our Assumption on $\Gamma$ as described above per your suggestion, as well as the following Remark and this has fixed such problem.

Your question: Shouldn't the index set $S$ be a subset of $[n]$? Also in the summation index $i_t$, it should be instead of $i$?

Our response: Thank you, you are right, we have replaced $\mathcal{S}$ by $[n]$ and fixed the index $i$ into $i\_t$ in the new revision.

Your question: The convergence results pertain to the objective value, but can something be said for the convergence of the iterates to the global minimum? (provided there is a unique global minimum of course)

Our response: Yes, actually, convergence in terms of $\\|\boldsymbol{w} - \bar{\boldsymbol{w}} \\|$, with $\bar{\boldsymbol{w}} = \arg\min\_{\boldsymbol{v} \in \mathbb{R}^d ~ \text{s.t.} ~ \\| \boldsymbol{v} \\|\_0 \leq \bar{k}} R(\boldsymbol{v})$, in our extra constraints setting, can be immediately obtained from the result without extra constraint, for an even simpler algorithm which just projects onto $\Gamma$ at the last step. Indeed, suppose one runs vanilla IHT (or any variant such as the stochastic or zeroth-order one), without the extra projection step, to obtain a bound of the form $\\|\boldsymbol{\hat{w}\_T} - \bar{\boldsymbol{w}} \\|^2 \leq A\_T + B$ for some $A\_T$ and $B$, with $\boldsymbol{\hat{w}}\_T$ the output ($A\_T$ is usually a decreasing term, and $B$ a system error (in red in Table 1)). Then, one can simply consider $\boldsymbol{\hat{z}\_T} = \Pi\_{\Gamma}(\boldsymbol{\hat{w}\_T})$, i.e. the projection of the output onto $\Gamma$. Since projection onto a convex set is non-expansive, one will then have $\\|\boldsymbol{\hat{z}\_T} - \bar{\boldsymbol{w}} \\|^2 \leq \\|\boldsymbol{\hat{w}\_T} - \bar{\boldsymbol{w}} \\|^2 \leq A\_T + B$, and therefore the bound will remain unchanged. Note that this cannot be improved in general, since if it could be, one would take $\Gamma = \mathbb{R}^d$ and one would obtain better bounds even in the case without extra constraints $\Gamma$. This is why we did not consider convergence in terms of $\\|\boldsymbol{w} - \boldsymbol{\bar{w}} \\|$ in our paper: such result is somehow trivial as it does not require any analysis. As an intuitive explanation, we could say that adding an extra constraint will restrict the space even further, therefore it is easy to see that iterates will only get closer to $\bar{\boldsymbol{w}}$: however, what is more interesting and needs to rethink the whole proof of convergence is the impact that such extra constraints have on the risk $R$: this is what we tackle in our paper.

Thank you for your insightful review. We sincerely hope that the main concerns raised in the review can be clarified by the following responses.

Your comment: The work is very much similar to literature (Jain et al., 2014; Nguyen et al., 2017; Li et al., 2016; Shen & Li, 2017; de Vazelhes et al., 2022).

Our response: As we elaborate upon in the global rebuttal, our work adds some significant contributions to the previous works in IHT:

1. Even in the case of no extra constraints $\Gamma$, our developed three-point lemma allows to greatly simplify the previously existing proofs of Jain et al. (2014) (Proof of Theorem 1, Appendix B.1), and Zhou et al. (2018) (Proof of Theorem 2, Appendix B.3): those proofs use intricate observations on the support sets of the iterates, which as such are hardly applicable and extendable. But our corresponding proofs (Proof of Theorem 4 followed by Proof of Theorem 1, and Proof of Theorem 5 followed by Proof of Theorem 2, and finally Proof of Theorem 6 followed by Proof of Theorem 3), are much simpler using more standard tools, which are similar to the ones from convex optimization (three-points lemma, telescopic sums etc), and as such are more extensible to future settings. As an example of such power of extensibility, even in the case of no extra $\Gamma$, in addition to simplifying and improving existing proofs, we can also provide a new result in the zeroth-order case (Theorem 6, cf. Table 1, described in more details in our Appendix E.3.2): such result is a significant improvement over the result of de Vazelhes et. al. (2022), since it provides a convergence in risk $R(\boldsymbol{w}\_t)$, without system error (i.e. without the term in red in Table 1). In the IHT litterature, such type of results are usually harder to obtain than results in terms of $\\| \boldsymbol{w} - \bar{\boldsymbol{w}} \\|$, which also exhibit an impractical system error.

2. In terms of technical challenge, since we use a new tool for the proof (the three-points lemma), our work have necessitated to fully rethink the proofs of those variants of IHT, which therefore we believe is a significant contribution to the IHT literature.

3. And finally, as a main example of the power of our framework, and our main contribution, we provide the novel convergence results that we do in the case of extra constraint $\Gamma$.

Your comment: The referee is afraid that adding an extra constraint $\Gamma$ of the regression coefficients making any fundamental difference.

Our response: First, before addressing your concern regarding extra constraints $\Gamma$, we would like to mention, as described above, that our work already provides significant contributions to the literature even in the case where there is no extra constraint. With that in mind, when we consider the case with extra constraints and try to build upon our previously introduced techniques, an important new difficulty arises, since the simpler version of our three-point lemma (i.e. Lemma 3 in Appendix) is not valid anymore (it is valid only for a vanilla $\ell\_0$ constraint) : this lead us to derive our Lemma 1, which is a three-point lemma which can take into account the extra constraints. This new lemma is key to our analysis and combined with a novel analysis which introduces the trade-off variable $\rho$, leads to our new results. Additionally, independently of our three-point lemma technique, even trying to directly extend the previous original proofs of convergence for IHT, for convergence in risk without system error, i.e. as in Jain et. al (2014), and Zhou et. al. (2018), in the case of extra constraints, would pose a challenge (for convergence in terms of $\\|\boldsymbol{w}-\boldsymbol{\bar{w}}\\|$ it would indeed not change much, as mentioned in the response to Reviewer LAEA Q.4, which is why we focus on convergence in risk). Indeed, the proof of Jain et. al (2014) and Zhou et. al. (2018) crucially rely on a specific lemma (Lemma 1 in Jain et al. (2014), called Lemma 2 in Zhou et. al. (2018)), which does not hold anymore in the case of extra constraint. More precisely, such lemma states that, for a $\bar{k}$-sparse $\bar{\boldsymbol{w}}\in \mathbb{R}^d$ and for any $\boldsymbol{w} \in \mathbb{R}^d$: $\\|\mathcal{H}\_k(\boldsymbol{w}) - \boldsymbol{w} \\|^2 \leq \frac{d-k}{d-\bar{k}} \\| \bar{\boldsymbol{w}} - \boldsymbol{w}||^2$. However, if we denote our mixed constraints set by $M$ ($= \mathcal{B}\_0 \cap \Gamma$ ), it does not hold in general that, for a $\bar{k}$-sparse $\bar{\boldsymbol{w}} \in M: \\|\Pi\_{M}(\boldsymbol{w}) - \boldsymbol{w} \\|^2 \leq \frac{d-k}{d-\bar{k}} \\| \bar{\boldsymbol{w}} - \boldsymbol{w}\\|^2$ (one can see this for instance in the case where $d=3$, $\bar{k} =1$, $k = 2$, $\Gamma$ is the $\ell\_{\infty}$ unit ball, $\boldsymbol{w} = (10, 10, 0)$ and $\boldsymbol{\bar{w}} = (1, 0, 0)$). [...Continued below...]

Thank you for your insightful review. We sincerely hope that the main concerns raised in the review can be clarified by the following responses.

Your comment: Technically, there are hidden constraints to the main results that could significantly limit the strength of the proposed results. ...So, no guarantee is provided for the important case of fixed sparsity $k$, even if we allow k to be an arbitrarily large constant.

Our response: Thank you for your suggestions. Regarding the requirement $k \geq \frac{1(1 - \rho)^2 L\_s^2}{\rho^2 \nu\_s^2} \bar{k}$, we would like to highlight that such a relaxation of $k$, depending on the condition number $\frac{L\_s}{\nu\_s}$ is present in all the literature of hard-thresholding in the RSC-RSS setting, as can be shown by the references in our Table 1 (column "$k$") (namely, Jain et al. (2014), Nguyen et al. (2017), Li et al. (2016), Zhou et al. (2018), and de Vazelhes et al. (2022)). This stems from the fact that the problem is NP-hard, and even hard to approximate [1] and as such the original problem $\min\_{\boldsymbol{w}} f(\boldsymbol{w}) ~ \text{s.t.} ~ \\| \boldsymbol{w} \\|\_0 \leq k$ cannot be solved in general to global optimality in its original form with a fixed $k$. In fact, it was actually shown in [1] that the $\kappa^2 = \frac{L\_s^2}{\nu\_s^2}$ factor of the sparsity relaxation cannot be improved in the analysis of IHT (Iterative Hard Thresholding). Finally, we highlight that usually hard-thresholding methods are used for very high-dimensional problems, and as such, even relaxing the sparsity by a constant factor provides sparse enough solutions.

Your comment: The main results are rather hard to read due to the fact that many needed notations are defined informally inline in different sections... so they can be easily searched.

Our response: Thank you for your suggestion, we have gathered our notations at the beginning of Section 2 (Preliminaries), and have added a section in the supplemental referencing them, for sake of clarity.

Your comment: For readability, the reviewer suggests that Remarks 3 and 4 should be summarized as a main theorem, then Theorem 1 is presented as a technical result for proving them.

Our response: Thank you for your suggestion. We agree that the result in terms of $R(\boldsymbol{w}\_t)$ is indeed clearer: we have rewritten Theorem 1 so as to display the result in $R(\boldsymbol{w}\_t)$ as per Remark 3 and 4 in the new revision.

Your question: Would it be possible to modify the analysis or the algorithm to extend the results for any large constant k?

Our response: In general, it would not be possible to modify the analysis to extend the result for any large constant $k$, since it is known that $k$ must be in $O(\kappa^2 \bar{k})$, where $\kappa$ is the condition number, and such dependence is not improvable in the analysis of IHT (as described in [1]). This fundamental bottleneck is essentially due to the NP-hardness of such a non-convex optimization problem.

[1] Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime, K. Axiotis and M. Sviridenko, ICML, 2022