Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees

Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions.

Regarding examples of problems satisfying the assumptions, note that we provide in Appendix G.2 and G.3 several examples, and also write there why such examples verify our assumptions.

Regarding the assumptions, actually, by definition, we will always have $L_s \geq \nu_s$ (and we can never have $\nu_s < L_s$), as the (restricted) smoothness characterizes an upper bound on the function and the (restricted) strong convexity characterizes a lower bound on the function. Therefore we believe that there is no such degenerate case as you mention and we believe our analysis still remains relevant.

Regarding the end of your comment, we note that $\bar{k}$ is not actually the sparsity of the optimal solution of the original problem (with k-sparse constraints): $\bar{k}$ is actually an arbitrary number (smaller than k) that is found such that the condition on $k$ is valid, typically $\bar{k}$ is taken as large as can be, but not larger. We agree that such results with $k$ and $\bar{k}$ are more complex than usual results in optimization, but such compromise with $k$ and $\bar{k}$ is unavoidable for IHT-like algorithms as proven recently by Axiotis & Sviridenko (2021; 2022), and it is standard in the literature of IHT (see Table 1). Please see also the end of the answer to reviewer EgPU on how to read and interpret such results.

Regarding the weaknesses:

In the case where there is no constraint $\Gamma$ (but note that there is still the sparsity constraint, which makes this case still far from trivial), we still improve upon the state of the art: in the stochastic case our constants are better than Zhou et al., and in the zeroth-order case we are the first to be able to obtain a bound on $R$ without system error, improving upon de Vazelhes et. al. (2022). Regarding RSC and RSS, we agree that these are somewhat restrictive, but our experimental section with the details on why we verify such assumptions, and the fact that there is a large literature on RSC and RSS problems, should make our setting still relevant.

Finally, regarding the length of the paper, we agree that it is long especially in the appendix, however this is just for sake of completeness, for the case where one would want to reuse (as we hope so), some of our proofs or tools, without needing to piece many things together as would be the case if our proofs were factorized too much. But actually, the main theoretical ingredients are somewhat succinct, (though, we believe, important enough), and many long parts in the appendix are actually standard derivations from usual optimization proofs.

Regarding the abstract, we will shorten it in the next revision, thanks for your suggestion.

Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions.

Regarding terminology and prior work, by “global convergence” we don’t mean convergence to a global minimizer (which is intractable due to NP-hardness), but rather a global optimality guarantee—a bound on $R(w)$ for iterates of sparsity $k$, in terms of $R(\bar{w})$, where $\bar{w}$ is a global optimum under sparsity $\bar{k}$ (with $k > \bar{k}$, as standard and necessary per Axiotis and Sviridenko, 2022). We agree the term “global convergence guarantees'' is misleading and will replace it by "global optimality guarantees"

Regarding the theoretical claims:

1. You're right that one can derive results on the iterates with system error from guarantees on $R$ without system error, but the reverse is not true. So in IHT literature, results on $R$ without system error are considered stronger — e.g., Zhou et al. use complex support analysis to get such bounds. A main contribution of our work is to (a) simplify their proof and improve constants, and (b) extend it to the zeroth-order setting, which is harder due to gradient bias, using a new three-point lemma framework (also adaptable to extra constraints).
2. We agree it's helpful to add sample complexity bounds (in terms of $k$), e.g. for Gaussian designs. We’ll add this in the appendix using known results like those after Theorem 3 in Jain et al. (2014). Since our conditions on $k$, $\bar{k}$, and $\kappa_s$ are as good or better than prior work (see Table 1), our sample bounds will follow. 3 and 4: Thanks — we will revise the theorems (as noted also by reviewer Rh51), and add the missing sign constraint: $l_i \leq 0$, $u_i \geq 0$.
3. Regarding the three-point lemma: in the convex case, multiple versions exist (e.g., with Bregman divergences). But in the non-convex setting (e.g., sparsity projections), the literature is more limited. We cite Foygel-Barber et al., who discuss expansiveness (related to your mention of firm quasi-expansiveness), but their results are in deterministic settings with simple sparsity constraints. We extend this to extra constraints $\Gamma$ and to stochastic and ZO cases, with new tweaks (e.g., handling variance and bias in ZO gradients, combining inequalities to control the tradeoff via $\rho$). If there is relevant operator theory literature handling non-convex expansive operators, we’d be very interested and happy to revise our claims accordingly. We’ll briefly mention the operator theory connection when introducing the lemma, but note that expansiveness is a key challenge in our setting. Thanks for suggesting the Blumensath citation — we’ll add it in the revision.

Comments and suggestions: Thank you — we will incorporate them in the next revision.

Answer to Questions:

1. Yes, Lemma 3.6 is key, but other novelties lie in how we combine inequalities to derive our bounds (see also reply to 5) above).
2. While we don't detail $L_s$ estimation, one can use the (unrestricted) smoothness constant (when it exists), or indeed, known bounds from random matrix / compressed sensing literature.
3. In vanilla IHT, $R$ is non-increasing (as gradient step + euclidean projection minimizes the upper bound induced by RSS), so the last iterate is bounded. But with extra constraints (in which in general TSP $\neq$ EP) or stochastic gradients (which are not the true gradient), we lose this property. Hence, Theorems 3.7+ bound the best iterate. Bounding the last one may be possible with extra work and slightly worse constants, which we leave to future work.
4. You're right that the assumption (though common in many SGD papers) doesn’t always hold, though it does in common cases like logistic regression or ball-like $\Gamma$. Relaxing it is a good direction for future work, potentially using recent advances in stochastic optimization.
5. Although Zhou et al. prove a similar result, we include ours because (a) our constants are better, (b) our proof is simpler and fits our general framework. The batch-size schedule is classical in stochastic IHT, where the learning rate cannot be decreased due to projection expansiveness. Better use of the finite-sum (e.g., via variance reduction) is interesting, but non-trivial in IHT — we leave that for future work.

Thanks a lot for your review and appreciation of our work. Regarding practical problems which satisfy the new condition but did not satisfy conditions considered previously, actually our example on portfolio optimization (in appendix G.2) with sector-wise constraints, is such an example: it is not a symmetric convex set, as one cannot ensure that a point from the set remains in the set if we swap its coordinates. As we describe in such an example, such a set does not admit a closed form for Euclidean projection onto it, and our two-step projection allows us to tackle it. As for examples of sets which do NOT satisfy the condition of support-preserving sets, a simple example is a hyperplane which does not contain the origin: in such case, the projection of a k-sparse point onto onto $\Gamma$ can be dense in general, hence the support of the point after projection may not be included in the original support of size k of the initial point.

Though we leave a more insightful and in-depth investigation of the tightness of our bound in terms of $\rho$ to future work, the main reason why there is a dependence in $\rho$ is that the original three point lemma is not valid anymore, and an extended version needs to be done, which contains an extra term, see our Lemma 3.6 compared to Lemma 3.2. This extension that we come up with, and the corresponding proof technique that we use in Theorem 3.7, comes from the difficulty to directly characterize the expansiveness coefficient of our complex mixed constraints. We don’t know if such a general characterization would be possible though, but we leave that for future work, since we believe this would be beyond the reach of this paper: such characterization would mostly likely be very complex, as already the vanilla $\ell_0$ three points lemma itself relies heavily on very specific properties of projection onto a sparse constraint. For more details, please check our proof which relies mostly on Lemma 2 from Liu and Foygel Barber, itself making heavy use of the sparsity structure of the set and relying on advanced tools such as the Borsuk-Ulam theorem (cf. proof of Lemma 2 in Liu and Foygel Barber et. al.).

Regarding the SP500 experiment, this baseline is indeed interesting and we will add it in the next revision.

Other comments and suggestions:

Non-support preserving projections: this is an interesting question, we believe if one is able to quantify the amount of expansiveness induced by such sets (i.e. the modification of the constants in our three point lemmas), then one will be able to reuse our proofs for the most part.

We agree that it would be best to mention Axiotis et al in the Intro, we will do so in the next revision. Indeed, it would be interesting to modify the algorithm of Axiotis et al to work with the constraints in our paper, though we leave this for future work.

You are right, 2-SP is a better name, we will adapt the next revision accordingly.

Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional question.

Regarding the comparison with the coordinate-wise optimization method by Beck et al., we cite that paper in our paper but do not compare our convergence rates in detail with it, as Beck et al. only give local convergence guarantees: they analyze properties of stationary points. Regarding an experimental comparison and whether the algorithm of Beck would be better than our algorithm empirically, we can consider 3 cases:

1. (See also the related Appendix F, Case (ii, a) and (ii, b)) The sets considered cannot be tackled by the algorithm from Beck. In such a case, it can happen that our algorithm can tackle them: this is the case for instance in our experiments in Appendix G.2. There, our algorithm provides an advantage.
2. (See Appendix F, Case (ii, c)) The sets considered can be tackled by Beck et al. (such as for sign-free symmetric sets): in such a case, the algorithm from Beck is expected to perform better than our algorithm as it is itself an improvement on projected gradient descent (PGD), and PGD is itself likely to be better than our algorithm at least at the iteration level, as we describe in Appendix F, Case (ii, c).
3. (See Appendix F, Case (i)) The sets considered are such that the two step projection IS equal to the euclidean projection: similarly, in that case, the algorithm of Beck is expected to be better, at least at the iteration level, as it is an improvement over projected gradient descent.

But note that in cases 2 and 3 above, the contribution of our paper is still present on the theoretical side: we do not pretend to provide a better algorithm, but rather, we give global guarantees on the result returned by the algorithm. Then one could run both our algorithm and Beck’s algorithm, and if Beck’s algorithm returns a better function value than our algorithm, our global guarantee will also of course also apply (as it is an upper bound on R) to the output of Beck’s algorithm, which can potentially be useful in various applications where having guarantees on sub-optimality is important.

Regarding the relaxation of the sparsity k, note that this presentation of results is classical in the literature of IHT with global guarantees, as in the works of Jain et al. (2014), Zhou et al. (2018), and de Vazelhes et. al. (2022). It was also recently proven in Axiotis & Sviridenko, 2022) that such relaxation is unavoidable for IHT (which makes sense as a “true” global guarantee is impossible to obtain due to the NP-hard nature of the problem), as we recall in our Remark 3.5. However, one way to read the results which is maybe more informative, is to consider the sparsity k of the iterates fixed, but to accept that the right part of the upper bound on convergence contains a term in $R(\bar{w})$, that is, an “optimum function value” for an iterate $\bar{w}$ of smaller sparsity. Therefore our bounds (and similar bounds in the literature) are actually bounds on the iterates of our algorithm, but it is just that the “reference point” is an optimum of a more constrained problem: as such it still offers some guarantee on the actual iterates of the algorithm.

Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions.

Q1: Assumption 2.3

A1: For Assumption 2.3, we will write it as a definition and state in the theorems that our objects verify such definition.

Q2: The regularity of the objective

A2: For the regularity of the objective, we indeed implicitly assume that the gradient is well defined (otherwise our assumption is void), so we will add this explicitly in the new revision.

Q3: The support set is a Riemannian manifold and Riemannian optimization is not so easy.

A3: I need to clarify that the support set defined as the indices of nonzero parameters, is a discrete set, the subspace corresponding to a support set is a Euclidean space, NOT a non-trivial Riemannian manifold. Thus, the optimization defined on the support set which can be optimized easily in the most cases.

Q4: References

A4: Regarding the related references, we are aware that there is an extensive related literature on proximal gradient descent and its generalizations (such as Riemannian optimization), as cited in our introduction (for instance, we already cite Bolte, Sabach, and Teboulle(2014)), and we appreciate the references you recommend, which are indeed relevant and which we will add in the next revision (for instance we can add [1], [2], and other related references by similar authors). Note however that we did NOT elaborate too exhaustively on such literature, as it actually considers local optimization guarantees such as convergence to local minima or stationary points, which are very different from the global optimization guarantees that we derive in our paper. In a way, our paper is much closer (in terms of assumptions, proof techniques, and results) to papers such as Jain (2014), Zhou (2018), or de Vazelhes (2022).

As mentioned above, we appreciate the reviewer can double-check the contributions of the paper and reconsider the evaluation.

[1] A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Application, Heinz H. Bauschke, Jérôme Bolte, Marc Teboulle

[2] On Linear Convergence of Non-Euclidean Gradient Methods without Strong Convexity and Lipschitz Gradient Continuity, Heinz H. Bauschke, Jérôme Bolte, Jiawei Chen, Marc Teboulle, Xianfu Wang