New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

Dear reviewer 7pPP, we extend our sincere gratitude for dedicating your valuable time to reviewing our paper and for expressing your appreciation and support for our work. In the following, we will provide a comprehensive response to your review comments.

Your comment: The paper [1] considers a stochastic optimization setting while the current paper studies finite-sum optimization. Can there be a way to reduce the variance for [1]'s setting?

Our response: Indeed, while [1] considered a general stochastic setting, in our framework, we consider the finite-sum setting, in order to use recent advances in variance-reduction for the finite-sum setting. However, we believe it would be hard to reduce the variance in general, i.e. for the general stochasticity introduced in [1], since we are unaware of the existence of such technique, even in the much simpler case of vanilla stochastic (non-finite-sum) first order optimization. This is an interesting question however, and we leave this for future work.

Your comment: In the experiments, I think the authors can add more comparison on computational cost and also comparisons with first-order methods or other methods as well, to highlight the benefits of using zeroth order optimization. I'm not an expert in zeroth order optimization, so I think adding such comparisons could make your results more convincing.

Our response: Regarding the computational cost, we have added a few precisions regarding the meaning of IZO and NHT in our paper: IZO stands for Iterative Zeroth-Order Oracle, that is, the number of calls to a function $f\_i$, and NHT stands for the number of Hard-Thresholding operations: as such, one can directly use those two metrics to know the computational complexity of the algorithm: for a function $f\_i$ which is costly to evaluate, one would rather seek to minimize the IZO, but for simple functions $f\_i$, the hard-thresholding operation may become the bottleneck and one will then care more about NHT. Regarding the benefit of zeroth-order methods compared to first order methods, actually, if one has access to the gradient, then first order methods will always be superior to ZO methods (since ZO gradient estimation introduces a lot of errors, in particular for high-dimensional problems): what we consider in our paper is a case where, due to constraints on the experimental setting (for instance, privacy constraints), one cannot access the gradient of the function, i.e. the function is a black box, which is why we do not compare to first order methods. In other words, we do not study zeroth-order method as an improvement over first-order methods, but rather as a fixed constraint of the problem. In the literature however, some methods inspired by zeroth-order methods, such as [10], can have an advantage in terms of computational memory over first-order methods, but such aspects are beyond the scope of our paper.

[10] David Silver, Learning by directional gradient descent, ICLR, 2021

Your comment: The paper lacks a proper related work section, which makes it challenging for readers to quickly grasp the background and understand the previous works. It is crucial to include a comprehensive discussion on related works, especially regarding the variance-reduced ZO hard-thresholding algorithm and the variance reduction aspect. The paper suffers from a lack of necessary references, such as papers on SAGA, SARAH, and SVRG methods. When these methods are initially mentioned, it is essential to provide corresponding references. Additionally, there are errors in the appendix due to bibtex errors, which should be carefully reviewed and corrected.

Thank you for your comment, it is true that some proper introduction to some of the exposed methods in the paper were missing. We have revised our paper to include references on the methods that we discuss. Additionally, we added an extra section in Appendix which sums up, in a table, all variance reduced algorithms, their original first-order counterpart and computational complexity, and links to the corresponding section in the paper where we analyze them. Finally, thank you for noticing the bibtex errors, we have now corrected them in the new revision.

Your comment: The presentation of baselines and experimental settings in the main text is not well-organized. It is recommended to reorganize this information to improve clarity, especially for readers who are unfamiliar with the baselines and adversarial attacks. Providing a cross-reference to the appendix can also help readers gain a better understanding.

Our response: Thank you for your comment, regarding the baselines, we have revised the paper accordingly to add to the corresponding references from the literature, and wrote an additional section in Appendix to sum-up all our variance reduction algorithms. In the main body of the paper, we have added some cross-references to the corresponding sections from the Appendix (for instance, we linked to the corresponding Appendix section for the proof of SARAH-SZHT). Regarding more precisions about the Adversarial Attacks setting, we have added a reference to the first paper which introduced such a setting: [8] (Appendix 11). We hope this can clarify such experimental setting and the motivations behind it.

Your comment: The introduction of SAGA-SZHT is missing from the paper, and it cannot be found. It is necessary to either locate the missing information or add it during the rebuttal phase.

Our response: As we briefly mention at the end of page 5, SAGA-SZHT is actually a specific instantiation of pM-SZHT, where we only need to let $J \in \\{\\{1\\}, ..., \\{n\\}\\}$ and $p=1$. Thank you for your comment, we agree that this point was not highlighted enough: in the new revision, we also included a bibliographic reference to SAGA at the beginning of page 6 for clarity, and additional references about SAGA in Appendix 1. Additionally, we did not separately provide a proof of convergence for SAGA-SZHT since it falls within the pM-SZHT framework, but we used SAGA as our main example to analyze algorithms within the pM framework.

[...Continued below...]

Dear reviewer wexC, 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: My first concern is on the usefulness of zeroth-order oracles. From experiments in this paper, it seems that we have easy access to gradient information in all these applications. Therefore, why do we need to emphasize zeroth-order algorithms? The authors may consider some other applications where gradient information is hard to obtain.

Our response: Thank you for your question. First, we would like to highlight that our experiments on universal adversarial attacks are in the black-box setting: such attacks are a real-life example of setting where one does not have access to the gradient of the objective function. Indeed, in a typical setting, one would seek to attack a machine learning service which could only be accessed through an API, processing the input image and returning, say, the probabilities of each class for the image, which is exactly the inputs and outputs which we consider in our task. Second, regarding our experiments with ridge regression, we have actually considered them as they are a very common task in the optimization literature, since those cost functions verify the (restricted) strong convexity and (restricted) smoothness assumptions, and as such, they can illustrate precisely the performance of our algorithms and verify the validity of our theoretical results. However, it is worth noting that, even for such experiments, one could still think of a setting where gradients would be inaccessible: the setting of private distributed learning. Indeed, in one variant of such setting, a central server is only allowed to receive a scalar value from each of the workers: one way to address such setting is for each worker to send the value of its directional derivative for a given random direction: there, the full gradient is therefore inaccessible to the central server, who can only construct a zeroth-order approximation of it (see e.g. [4], [5]).

Your comment: Another concern is on the setting of L0 regularization. While there exist many other approaches on obtaining sparse solutions (e.g., LASSO), the authors may need to justify the necessity of using L0 regularization here.

Our response: Thank you for your question, we believe that the main advantage of pursuing $\ell\_0$ optimization directly through the hard-thresholding operator rather than using convex relaxations (such as $\ell\_1$ optimization) is regarding the control that one has on the sparsity of the iterates. Indeed, ensuring a specific level of sparsity $k$ is very tedious with $\ell\_1$ regularization: one has to tune the strength of the regularization $\lambda$ through an extensive grid-search, to find the $\lambda$ which gives a solution of sparsity exactly $k$. On the other hand, when using hard-thresholding, one only needs to specify $k$ at the beginning of the algorithm, and the algorithm can then be run once, without any grid-search. Specifying a given $k$ is important in various real-life tasks, for instance the few-pixels adversarial attacks task that we consider in our experiments (Sec. 5): there, one typically seeks to attack an image using a given number $k$ of perturbed pixels. A second example is in portfolio optimization, where one, due to budget limitations, one is only allowed to invest in a maximum of $k$ examples to optimize its return [6] . Finally, a last example is in compressed sensing, where one seeks to recover a vector of sparsity known to be exactly $k$ [7]. In all of these examples, hard-thresholding algorithms are especially adapted to the task, as they can control such $k$ explicitly.

Your comment: I am a bit confused on the key contribution of this work. The authors introduced two algorithms, pM-SZHT and VR-SZHT. What is the key difference of these two algorithms? Moreover, pM-SZHT is not compared in experiments, but SARAH/SAGA-SZHT is compared. This is also very confusing and may need some explanations.

Our response: We apologize for the lack of necessary explanations and have made revisions to the rebuttal version. In our convergence analysis using the p-Memorization (pM) framework, which includes many variance reduce algorithms, we define the update method for parameter $a$ in pM-SZHT as follows:

Regarding the difference between VR-SZGT and pM-SZHT, actually, our paper can cover two possible variants of VR-SZHT, the first one being an instantiation of pM-SZHT, and which can be described as follows: we fix $p > 0$ and draw in each iteration $r \sim U[0; 1)$. If $r < p/n$, a complete update, $\hat a^+\_j=\hat\nabla f\_i(\theta),\forall j$ is performed, otherwise, they are left unchanged. [...Continued below...]

[...Continuing from above...]

Our response: Thank you, following your suggestion, we have run more experiments on the adversarial attacks setting: we considered 3 more classes: ‘airplane’, ‘ship’, and ‘bird’ (in addition to the original ‘dog’ class) which results we provide in the revised supplemental (note that we have now put the class ‘dog’ instead in Appendix, and replaced it by ‘airplane’ in the main body): those confirm even further the advantage of variance reduction in ZO hard-thresholding: in Figure 3 one can see that in terms of objective value, SARAH-SZHT and SAGA-SZHT outperform all other algorithms. And in terms of attack success rate (Table 1), SARAH-SZHT outperforms other algorithms (by successfully attacking 7/10 images). Similar observations can be done on the other classes (‘ship’, ‘bird’, and ‘dog’), which we show in the revised Appendix. Regarding the small number of images per class, and the fact that for each experiment, images are of the same class, this constraint comes from the fact that we consider universal adversarial attacks rather than vanilla adversarial attacks. More precisely, since one same perturbation must be used to attack all images at once, taking more images or images of mixed classes would make the task much harder and erratic in practice. Therefore, we follow the protocol of taking a small batch of images of the same class, which is what is usually done in the litterature (see e.g. Appendix A.11 in [8]).

[4] Zhang, Qingsong, et al. Desirable companion for vertical federated learning: New Zeroth-order gradient based algorithm. Proceedings of the 30th ACM International Conference on Information \& Knowledge Management, 2021

[5] Gratton, Cristiano, et al. Privacy-preserved distributed learning with zeroth-order optimization. IEEE Transactions on Information Forensics and Security, 2021

[6] Bertsimas, Dimitris, and Ryan Cory-Wright. A scalable algorithm for sparse portfolio selection. Informs journal on computing, 2022

[7] Foucart, Simon, et al. An invitation to compressive sensing. Springer New York, 2013.

[8] Sijia Liu, Zeroth-order stochastic variance reduction for nonconvex optimization. NIPS, 2018

Dear reviewer iAcw, we extend our sincere gratitude for dedicating your valuable time to reviewing our paper and for expressing your appreciation and support for our work. In the following, we will provide a comprehensive response to your review comments.

Your comment: Out of curiosity, when applying variance reduction to SZOHT, are there any major technical difficulties in the analysis or major new techniques used in the work?

Our response: Indeed, in our work which applies variance reduction techniques to zeroth-order hard-thresholding, there are several technical challenges that arise, which necessitate the use of new techniques, departing from traditional techniques in variance reduction from both the first-order IHT case, and the zeroth-order convex case, as we describe below:

• New Perspective on Resolving Conflicts Between Zeroth-Order Methods and Hard-Thresholding. First, the conflict between hard-thresholding and the ZO gradient estimate is unique to the specific combination of (i) ZO and (ii) hard-thresholding (HT), since the ZO error is related to the sparsity of the iterates ($k$) (contrary to, say, the error of first-order algorithms, which is related to the batch-size, independent from $k$), and such $k$ already has specific constraints dictated by the convergence analysis from Iterative Hard Thresholding. As such, analyzing how variance reduction reduces the error in the ZO gradient is very specific to the combination of (i) ZO and (ii) HT, and results in particular in a novel multi-parameter analysis, which we describe below.

• Multi Parameter Analysis. Understanding parameter relationships is vital in convergence analysis, especially in explaining how variance reduction techniques alleviate conflicts. Here, we illustrate this point by Comparing SZOHT and VR-SZHT. In SZOHT, attention is primarily on the constraint link between the zeroth-order estimated direction number $q$ and the Hard Thresholding parameter $k$. However, VR-SZHT introduces variance reduction, adding an inner loop parameter $m$, leading to interdependence among these three parameters. Analyzing this relationship poses a notable challenge. To assess if variance reduction algorithms can mitigate conflicts, we explore whether there exists $m$ to make the algorithm converge for any $q$. Analyzing the coefficients in the convergence term of equation (8) yields inequalities involving $k$,$q$,$m$. Ultimately, confirming a positive outcome is achieved through the existence of $m$. For additional insights, refer to Appendix 4.3.

• General Analysis: Finally, the introduction of a general analysis framework is another new technique used in the paper. This framework systematically assesses the performance and behavior of diverse variance-reduced algorithms under $\ell\_0$ constraints and zeroth-order gradient scenarios. Additionally, we have substantiated the theoretical basis for various common VR methods.

Dear reviewer TcW5, 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: There are many symbol error as well as misleading notations in the paper, which requires further correction. E.g., the $k^\*$ should be $s$ in Assumption 1; no introduction of $\mu$ in eq. 3; no explanation for $H\_{2k}$ in page 3 when it appears at the first time; what's the meaning of J in page 5? how to get the i in page 5? and so on. This will make it hard for readers to understand the paper.

Our response: Thank you for pointing out these missing notations and precisions, following your suggestions, we have fixed $k^\*$, introduced $\mu$, $\mathcal{H}\_{2k}$, $J$, and $i$.

Your comment: More details and discussion for experiment section, e.g., the explanation on IZO and NHT in Fig.2,3

Our response: Thank you for your suggestion, we have added the definition of IZO and NHT in the new revision.

Your comment: How to tell VR-SZHT is better in Table 1? More experiments may do a better job in supporting the advantages of the VR-SZHT algorithm. Currently, VR-SZHT seems to be even worse than baselines in some cases, e.g., Fig. 3

Our response: In the new revision, we ran more experiments (3 more classes for the adv. attacks), and those show more clearly the advantage of variance reduction algorithms: we now emphasize the class ‘airplane’ in our revised main body (Figure 3 and Table 1, updated) (and we kept the previous ‘dog’ example in the revised Appendix with the two added examples): in such ‘airplane’ case, we can clearly see the advantage of SARAH-ZHT in the table: it can successfully attack 7 out of the 10 images: this is even further confirmed on the other adversarial attacks settings that we added in the revised supplemental. Regarding VR-SZHT, in some experiments it can be indeed worse than some baselines (perhaps due to instabilities in adversarial attacks, which do not respect the RSC-RSS assumptions and are given for indicative purposes), but it can be seen to perform better than its vanilla stochastic counterpart (SZOHT) e.g. in Figures 5 and 6 in Appendix.

Your comment: Could the authors elaborate more on what's the conflict between the expansionary of hard-theresholding and ZO error about? And how it affects the performance of zeroth-order hard-thresholding algorithms?

Our response: Thank you for your question, we hope to provide here some more explanations on the conflict between expansivity of the hard-thresholding operator, and the errors of the ZO gradient estimator. For clarity, we first start with common knowledge from convex optimization, and then describe why a particular challenge arises when combining zeroth-order and hard-thresholding. From an intuitive perspective, zeroth-order convex constrained optimization convergence relies on a fundamental property: the non-expansivity of the projection operator. Such property ensures that projecting $\theta\_t' := \theta\_t - \eta g(\theta\_t)$ onto the constraints can only make $\theta\_t'$ closer to the optimum. In such case, even if the error of the gradient estimator is high, one can always set the learning rate to some small enough value, to avoid instabilities and ensure (in expectation) convergence of the algorithm (even if such convergence is slow). But in $\ell\_0$ optimization, the hard-thresholding operator (i.e. projection onto the $\ell\_0$ pseudo-ball), is not non-expansive. As such, projecting a vector $\theta\_t'$ onto the $\ell\_0$ pseudo-ball can bring it further away from the optimum. In such case, setting a small learning rate (when the error in gradient estimation is high) may be detrimental to the convergence, since iterates can get further and further away from the optimum. There, one must actually ensure that enough progress is made by $\theta\_t - \eta g(\theta\_t)$ towards the optimum, so that even after hard-thresholding, iterates still get closer (in expectation) to the optimum. As such, the learning rate cannot be taken arbitrarily small, and the gradient error therefore needs to be tackled directly, e.g. by sampling enough random directions, and/or using variance reduction techniques as we propose in our paper.

Dear reviewer 5xEJ, we extend our sincere gratitude for dedicating your valuable time to reviewing our paper and for expressing your appreciation and support for our work. In the following, we will provide a comprehensive response to your review comments.

Your comment: Typo: It should be $\\|\nabla f\_i(\theta) - \nabla f\_i(\theta')\\| \leq \rho\_s^+ \\| \theta - \theta' \\|$ in the Assumption 2.

Our response: Thank you for your correction, we have fixed such typo.

Your comment: Since the Problem (1) is NP-complete, what is $\theta^\*$ in the convergence analysis? If $\theta^\*$ is the optimal point of Problem (1), why can the proposed algorithm can achieve a linear convergence rate which means it is a polynomial time algorithm that can solve a NP-complete problem?

Our response: Thank you for your question. Since the problem is NP-hard, we indeed do not prove convergence to optimality in polynomial time, and there are two aspects under which our results depart from convergence to optimality.

1. First, our convergence result bound relates $\mathcal{F}(\theta\_t)$ for our iterates $\theta\_t$ of sparsity $k = \Omega(\kappa^2 k^\*)$ (with $\kappa = \frac{\rho\_s^+}{\rho\_s^-}$), to $\mathcal{F}(\theta^\*)$ where $\theta^\*$ is of sparsity $k^\* < k$ and can be taken as $\theta^\* := \arg\min\_{\|\theta\|\_{0} \leq k^\*} \mathcal{F}(\theta)$ (by comparison, a typical convex optimization bound would be written for a $\theta^\*$ of sparsity $k$ (i.e. both the minimum and the iterates would belong to the same constraint set, which is not the case here for us)). Such kind of results may be non-standard from a convex optimization perspective, but it is how all the results in the Iterative Hard Threholding (IHT) literature with RSC and RSS assumptions, are formulated (see e.g. Jain et al. (2014), Nguyen et al. (2017), Li et al. (2016), Zhou et al. (2018), and de Vazelhes et al. (2022)). In fact, it was actually shown in [3] that the factor $\kappa^2$ of the sparsity relaxation cannot be improved in the analysis of IHT. 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.

2. Second, our result exhibit a system error, i.e. we prove results of the form $R(\theta\_t) \leq R(\theta^\*) + \varepsilon + \Delta\_1 \mu^2 + \Delta\_2$ , where $\Delta\_2$ is a constant system error (e.g. in Theorem 2, it is a consequence of the constant $L\_r$). Such system error is also standard in IHT results, see e.g. Li et. al. 2016 (Theorem 3.3), Nguyen et. al. (2014), de Vazelhes et. al. (2022). It is also worth mentioning that when $\mathcal{F}$ has a $k^\*$-sparse unconstrained minimizer, which is often the case in practical applications such as sparse reconstruction or when considering overparameterized deep networks [2], such system error vanishes. And even if $\mathcal{F}$ does not have such minimizer, this error is usually acceptable.)

[1]Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. In Advances in Neural Information Processing Systems, volume 27, 2014.

[2]Alexandra Peste, Eugenia Iofinova, Adrian Vladu, and Dan Alistarh. Ac/dc: Alternating compressed/decompressed training of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.

[3]Axiotis, Kyriakos, and Maxim Sviridenko.Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. International Conference on Machine Learning. PMLR, 2022