Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work considers the problem of stochastic optimization in the presence of an L0 ball constraint (i.e. at most k components of the minimizer can be nonzero). This is essentially stochastic optimization in a setting where a sparse solution is sought. In particular, the authors consider this problem in a zeroth-order (ZO) optimization situation where (stochastic) gradients are not available, useful for black-box adversarial attacks and reinforcement learning (for example).

Specifically, the paper proposes to use iterative hard thresholding, a standard method for L0-constrained problems, but with stochastic gradients estimated via gradient smoothing (a form of randomized finite differencing). The gradient smoothing is specifically designed to apply sparse perturbations to the current iterate, unlike standard smoothing. 

They prove a linear convergence rate for their algorithm to a neighborhood of a minimizer under some restricted versions of strong convexity and L-smoothness. The neighborhood of convergence depends on both the variance of the stochastic gradients, and the smoothing parameter used in the gradient estimator. Under full L-smoothness of the objective, they prove a fully dimension-independent convergence rate, which improves on existing sparse ZO optimization based on L1 regularization. A key restriction of this technique is that the convergence theory requires the number of gradient smoothing estimates to be sufficiently large (to ensure the estimated stochastic gradient is sufficiently close to the true stochastic gradient). 

The authors provide numerical experiments for sparse portfolio optimization and adversarial example generation, showing that their proposed method outperforms existing sparse ZO optimization methods.
strengths_and_weaknesses: To my knowledge, this is the first attempt to combine hard thresholding with ZO gradient estimators (although it has already been applied to stochastic gradients). The resulting algorithm is simple and appears to perform well in practice. I note that in practice both the learning rate and the smoothing parameter have to be tuned, which is expensive, but a reasonable cost in this setting. The convergence theory is interesting and the implications for the gradient smoothing accuracy will likely affect any future L0-constrained ZO algorithm development. 

Overall I find this an interesting work. The quality of prose is sufficiently high in most places. 

My main concern is the discussion around the choice of $q$ (particularly Lemma 1) in Section 4. My understanding of Lemma 1 is that first a suitable $q \geq q_{\min}$ is chosen, and that then defines a valid range of $k$. This seems to be the wrong way around - usually we would have a $k$ specified by the problem, and then choose how to construct the ZO gradient estimators with a corresponding restriction on $q$ (depending on $k$). It also appears that the authors require, if the chosen $k$ is too small (although exactly what this means is unclear as per my concern around Lemma 1) that a larger $k$ is chosen. That is, the actual L0 constraint must be changed. This is quite unusual, in that an optimization algorithm requires the solution of a *different* problem than originally specified. 

Minor comments:
- What is footnote 4 in Table 1 (for SZOHT in the second-last row)?
- The variable $q$ is mentioned several times in the introduction, but not defined until later.
- I find Figure 1 extremely unclear and don't think it contributes to the text (lines 174-178). I recommend it be removed.
- Line 298, "proximal algorithms are faster than Frank-Wolfe algorithms". I have not seen this conclusion before (as a non-expert in these methods) - do you have a citation for this?

questions: 1. In the gradient estimator eq (2), is it correct that each u_i has a different support set? In that case, the gradient estimator could have up to q*s_2 nonzero entries. Is this a concern from a computational effort point of view?

2. Throughout Section 4, what is k*? Is this just an upper bound on ||x_0||_0 (in which case if x_0=0 then any k* is acceptable), or something else? 

3. The conditions of Theorem 1, in particular $s \leq d$ implies that we must have $k\leq d/2$. Does this cause any conflict with the other assumption $k \geq k^* \rho^2 / (1-\rho^2)^2$? Any restrictions on the problem constant $k$ should be explicitly given (even though $k\leq d/2$ is not a problematic requirement).

4. It is mentioned in line 219 that Lemma 1 gives conditions for which $\rho \gamma < 1$. However, the lemma's statement does not appear to include this. What specifically does $q \geq q_{\min}$ imply? In particular, does it imply either/both of $k \geq k^* \rho^2 / (1-\rho^2)^2$ or $\rho\gamma<1$?

5. Figure 2b seems to show that there is essentially no reduction of $\|x-x^*\|$ for any value of $q$. Does this mean your choice of problem makes the non-decaying ($\sigma$ and $\mu$) terms in Theorem 1 too large to show useful results in this regard?
limitations: The main limitations are related to problem assumptions and requirements on $q$ and $k$. These are reasonably well described, noting my feedback above. There is no concern about negative societal impact from this work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper describes a zeroth-order version of the hard-thresholding algorithm. Interestingly, the convergence rate (up to system errors) is dimension-independent in the case of smooth functions and full support sampling for the random directions. The paper also provides convergence results in the more general case of restricted smoothness and restricted support for the sampling of random directions. It also discusses an interesting trade-off that arises between the error of the zeroth-order estimate, and the expansivity of the hard-thresholding operator, that results into a minimal value for the number of random directions q. Finally, the authors demonstrate the utility of their method with encouraging  experimental results on synthetic datasets such as a quadratic function, and real-life datasets such as asset management and black-box adversarial attacks.
strengths_and_weaknesses: ## Originality:
The main difference compared to previous work is in tackling both zeroth-order and l0 optimization, which has not been done before (except by the work of [1], but they make stronger assumptions (sparsity of gradients)). The proof for the dimension independence/insensitiveness of zeroth-order hard-thresholding, a consequence of the bounds on the error of the ZO gradient, is novel, and uses interesting results about the surface integration on a sphere, as well as involved combinatorics computations to generalize them to the random support technique. I think it is an interesting contribution to the litterature on ZO optimization. The discussion about the minimal value for q is also very interesting and novel. 

## Quality:
The authors provide detailed self-contained proofs for the main claims in the appendix. They also provide some code to run SZOHT on the toy experiments, as well as an asset management problem and an adversarial attack problem.

## Clarity:
The main results and theorems are discussed in details. Figure 1 convey very well the main message regarding the conflict between expansivity and gradient error.
I believe there are a few typos/missing notations, that could easily be addressed:
- In table 1, note 4 does not appear
- In table 1, I think FO was not defined (though I guess it means "First-order")
- In section 5.1 sensitivity analysis, I think it should be an elementwise product a  * (x - b), not a dot product (otherwise the squared norm would be just a squared number)
 
## Significance :
As zeroth-order optimization is known to suffer from the curse of dimensionality, as described in the introduction of the paper, dimension-insensitive results like the one from this paper are very interesting. In addition, that paper manages to achieve such results with only mild assumptions (namely, RSC and RSS, and without any gradient sparsity assumption). The experiments are extensive, and ran on real-life datasets like adversarial attacks which shows the method also works well in large scale practical machine learning problems.


# References
[1]   "Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates"
  Balasubramanian, Krishnakumar and Ghadimi, Saeed
  Proceedings of the 32nd International Conference on Neural Information Processing Systems 2018


[2] "Linear convergence of stochastic iterative greedy algorithms with sparse constraints",
  Nguyen, Nam and Needell, Deanna and Woolf, Tina
  IEEE Transactions on Information Theory, 2017,

[3] Ac/dc: Alternating compressed/decompressed training of deep neural networks},
  Peste, Alexandra and Iofinova, Eugenia and Vladu, Adrian and Alistarh, Dan},
  Advances in Neural Information Processing Systems
  2021
questions: I believe one aspect that may deserve further discussion is about the system error in Theorem 1, that depends on the norm of the gradient at optimum ||nabla f(x*)||. If this term is large, the upper bound for the convergence rate might become large too. However, this term seems to appear also in other works on hard-thresholding like [2], so I guess it is not really an issue of the work itself, more of an issue intrinsic to the hard-thresholding method and l0 constraint. But I think it might be interesting to elaborate on how large this term can get in practice, and also in which settings it can be small (for instance, it may be interesting to add references on compressed sensing, in which the original parameter vector is assumed sparse, or to related assumptions like assumption (2) in [3], in which it is stated that "the existence of very sparse minimizers is a known property in over-parametrized DNNs").
limitations: Since this algorithm describes a general method for optimization, I don't believe there is any direct negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the $\ell_0$ constrained stochastic optimization problem with zeroth-order oracles only. They proposed a stochastic zeroth-order hard-thresholding algorithm, making use of a novel random support sampling. They provide the convergence guarantees of SZOHT under standard assumptions, and the query complexity of SZOHT has weak/no dependence under different settings.
strengths_and_weaknesses: The paper proposed a new algorithm SZOHT and show that the oracle complexity is dimension independent under some condition without additional gradient sparsity assumption. The ideas and the proposed algorithm are easy to follow. The paper is well organized. The experiments show improvements over previous work. In general, the paper is good.

I have a few comments/questions:

Major Comments:
1. $k$ and $k^*$: I have two questions about $k^*$ and $k$. Based on my understanding, $k^*$ is the actual target sparsity, while $k$ is just a parameter in the algorithm, and each iterate of algorithm maintains $k$-sparsity instead of $k^*$-sparsity. That means each iterate of the algorithm does NOT maintain primal feasibility, is that correct? If that is the case, is there any polishing steps you can do to refine the solution so that it has exact $k^*$ nonzeros? The second question about this is in the algorithm, it says $k=\mathcal{O}(\kappa^4k^*)$, and also in Remark 4, the authors mention that $q$ should be taken so that $k\leq d$. But even with $q=\infty$, $\epsilon_F=2$, there are still chances that $k=\mathcal{O}(\kappa^4k^*)$ will be always greater than $d$, which means the algorithm has limitation on actual target sparsity $k^*$?
2. $\mu$: In the convergence analysis, there is only a linear term in $\mu$ while neither other constants or nor other terms depend on $\mu$. This is a bit counter-intuitive, because that means $\mu$ can be taken arbitrarily small to reduce the error term? Is there any theory to provide guidelines on how to choose $\mu$? What did you choose for $\mu$ in the numerical experiments?
3. Condition number $\kappa$ and $s_2$: in theory, the convergence guarantee and oracle complexity bound depend heavily upon the condition number $\kappa$, which is unknown or hard to compute based on its definition. The convergence guarantee may not hold if the learning rate $\eta$ and/or $q$ are chosen arbitrarily. In practice, one may need to tune heavily on these hyperparams, which the authors did for their experiments. I am wondering if there is any way you can estimate these parameters or any way to avoid large grid of hyperparam tuning? Also there any theory to provide guidelines on how to choose $s_2$? Because $s_2$ might also affect the condition number?

Minor Comments
1. In line 75/94, $q$ is not introduced yet, so it is better to give some descriptions on $q$.
2. In Proposition 1 Theorem 1, Corollary 1 and Corollary 2, the constants are hard to locate. Probably it’s better to have equation number and refer to these equations later on to remind people what these constants are in the theory.

questions: See "Strengths and Weaknesses"
limitations: See "Strengths and Weaknesses"
review_title: null

Meta-review: metareview: The paper considers stochastic optimization in the presence of an L0 ball constraint. All reviewers agree that the theoretical derivations are solid and numerical experiments show promising performance. Although the algorithm might have to be finely tuned to perform well, it contains many novel and interesting elements that warrants its publication.  
confidence: Certain
Decision: Accept