Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: ===== Update after author response

Thanks for the clarifications and edits in the paper.

I recommend acceptance of the paper.

Other comments:
Definition 1 in the updated version is still too vague ("difference of what?" -- function values? distance in norm between iterates?) -- this should be clarified.

========

This paper considers the problem of sparsity-constrained ERM and asks whether one can design a variant of the stochastic hard thresholding approaches where the hard-thresholding complexity does not depend on a (sparsity dependent) condition number, unlike all previous approaches (Table 1). It proposes a method which combines SVRG-type variance reduction, with block-coordinate updates, leaving the hard thresholding operation outside the inner loop, to accomplish this goal. It provides a convergence analysis which significantly improves the previous best rates (by having both the sparsity level shat which is significantly lower (kappa_shat vs. kappa_stilde^2) as well as a condition number independent hard thresholding complexity (Table 1). An asynchronous and sparse (in the features) variant is also proposed, with even better complexity. Some standard experiments on sparse linear regression and sparse logistic regression is presented showing an improvement in both number of iterations as well as CPU time.

I think the clarity of the paper should be quite improved (see detailed comment), hence why I think the paper is borderline, but I am leaning towards an accept given the significant theoretical improvements over the past literature (and positive empirical results), even though the algorithmic suggestion is somewhat incremental.

The proposed Algorithm 1 seems very close to the one of Chen & Gu (2016), the paper should be more clear about this. There seems to be mainly two changes: a) extending the support projection of the gradient to the union of the sampled block with the one of the support of the reference parameter wtilde (vs. just the sampled block in Chen & Gu (2016) and b) moving the hard-thresholding iteration outside of the SVRG-inner loop. These small tweaks to the algorithm yield a significant theoretical improvement, though.

== Detailed comments ==

Clarity: the number of long abbreviations with only one letter change make it hard to follow the different algorithms; perhaps a better more differentiating naming scheme could be used. Moreover, I think more background on the sparse optimization setup should be provided in the introduction or at least in the preliminaries, as I do not think the wider ICLR community is very familiar with it (in particular, no cited paper was at ICLR). For example, define early the separation in optimization error and statistical error; and point out that F(w_t) might even be lower than F(w*) as the sparsity threshold s might be much higher than s*. This will make Table 1 more concrete and less abstract for people who not are not yet experts on this particular analysis framework.

- Table 1: I would suggest to put the rate for S2BCD-HTP instead on the last row and mention instead that the rate for ASBCD is similar under conditions on the delay; as it is interesting to already have a better gradient complexity for S2BCD vs. SBCD.

** Questions:  **
1) In Corollary 1, how is the gradient oracle complexity defined or computed? And more specifically, how does one compare fairly the cost of doing a gradient update in Algorithm 1 on the *bigger set* S = Gtilde U G_jt vs. just G_jt for the Chen & Gu ASBCD algorithm? Is this accounted in the computation?

2) In Figure 1, which "minimum" is referred to and how is it found? I suspect it is not F(w*) (as it could be higher than F(w_t)), i.e. it is *not* the minimum of (1) with s*. One natural guess is that it might be min_w F(w) s.t. ||w||_0 <= s, though I do not see any guarantee in the main paper that running the algorithm would make F(w_t) converge to such a value (i.e. all we know from Thm 1 is that F(w_t) might be within O(||nabla_Itilde F(w*)||^2) of F(w*) ultimately. Please explain and clarify!

== Potential improvement ==

The current result in Theorem 1, which is building on a similar proof technique as the original SVRG paper, has the annoying property of requiring the knowledge of the condition number in setting the size of the inner loop iteration. I suspect that this is an artifact of using an outdated version of the SVRG algorithm. This has been solved since then by considering a "loopless" version of SVRG which implicitly defines the size of the inner loop in a random manner using a quantity *which does not depend on the condition number*. This was proposed first by Hofmann et al. [2015], and then re-used by Lei & Jordan [2016] and more recently by Kovalev et al. [2019] e.g. Note that Leblond et al. (2017) that you cited profusely also used this variant of SVRG. I suspect that this technique could be re-used in your case to obtain a similar result with a loopless variant (which also gives cleaner complexity results). (Though I only skimmed through your proof.)

Caveat: the sensibility of the theory in the main paper seems reasonable, but I did not check the proofs in the appendix.

= References:
- Hofmann et al. [2015]: Variance Reduced Stochastic Gradient Descent with Neighbors, Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien and Brian McWilliams, NeurIPS 2015
- Lei & Jordan [2016]: Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method, Lihua Lei and Michael I. Jordan, AISTATS 2016
- Kovalev et al. [2019]: Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop, Dmitry Kovalev, Samuel Horvath and Peter Richtarik, arXiv 2019

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper introduces a new optimization algorithm for convex functions with sparsity constraints, based on hard thresholding to enforce sparsity. It is argued that applying hard thresholding in every step is the computational bottleneck of previous works based on hard thresholding, and the paper proposes a variant that alleviates previous works’ convergence problems. This is achieved by having an inner and outer loop in which the hard thresholding is applied only in the outer loop, and in the inner loop block coordinate descent is used  (ie. applying updates to only a subset of the solution’s variables). The paper shows that the convergence bounds of the algorithms compares favourably to previous hard thresholding algorithms convergence bounds, and empirical results show the effectiveness of the algorithm compared to previous ones.

It is always exciting to see improvements in optimization algorithms as they can lead to improvements in many different problems. Yet, I have the following concerns:
-The algorithm is strongly based on previous optimization algorithms as the main difference with them is applying the hard thresholding less frequently. This sounds incremental and I think the paper could emphasize much more why this idea is a significant advancement over previous works.
-The paper could make a better job motivating the sparsity constraints, as it cites papers from 10 years ago which are not representative of state-of-the-art.
-The paper focuses on optimization time but not on generalization. Note that converging faster to the objective does not imply better generalization. I would have expected at least a discussion about this in the paper. Does the algorithm lead to better generalization accuracy or worse?
-The proof contains an assumption that it is unclear that has been explained in the paper. In the supplementary material, after eq. 25, the factor sigma is being introduced and the paper says “we assume that there exists a constant factor sigma making this inequality true”. 
-Definition 1 does not really define hard thresholding. 

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes a semi-stochastic block coordinate descent hard thresholding pursuit (SBCD-HTP) algorithm for solving l0 sparsity-constrained minimization with decomposable convex objective. The key idea is to introduce BCD into SVRG type of algorithm to speed up the convergence as well as the hard thresholding operation. The paper is well written and easy to follow. The theoretical analysis is strong, I think. However, my main concern of the paper is the experimental part.

1. The test functions are simple (i.e. logistic and linear regression), and the data sets are simple as well. I'd like to see more experiments using more complex problems with more realistic data. 

2. There are two stronger assumptions in the paper, but they are never verified in the experiments. What else functions are following such functions? Any example?

3. There are no validation experiments for Thm. 1. Are all the assumptions mild in practice? Is it possible to plot the upper bound in Eq. 4?

4. I do not understand the usage of Def. 1.

review_title: Official Blind Review #2

Meta-review: All the reviewers reach a consensus to reject the current submission. 

In addition, there are two assumptions in the proof which seemed never included in Theorem conditions or verified in typical cases. 

1) Between Eq (16) and (17), the authors assumed the 'extended restricted strong convexity’ given by the un-numbered equation. 

2) In Eq. (25), the authors assume the existence of \sigma making the inequality true.

However those assumptions are neither explicitly stated in theorem conditions, nor verified for typical cases in applications, e.g. even the square or logistic loss. The authors need to address these assumptions explicitly rather than using them from nowhere.
Decision: Reject