Convergence of the mini-batch SIHT algorithm
Authors: Saeed Damadi
Jinglai Shen
Venue: Submitted to ICLR 2023 (2023)
Keywords: mini-batch gradient
sparse optimization
iterative hard thresholding
IHT
SIHT
mini-batch

Abstract: The Iterative Hard Thresholding (IHT) algorithm has been considered extensively as an effective deterministic algorithm for solving sparse optimizations. 
The IHT algorithm benefits from the information of the batch (full) gradient at each point and this information is a crucial key for the convergence analysis of the generated sequence. However, this strength becomes a weakness when it comes to machine learning and high dimensional statistical applications because calculating the batch gradient at each iteration is computationally expensive or impractical. Fortunately, in these applications the objective function has a summation structure that can be taken advantage of to approximate the batch gradient by the stochastic mini-batch gradient. In this paper, we study the mini-batch Stochastic IHT (SIHT) algorithm for solving the sparse optimizations. As opposed to previous works where increasing and variable mini-batch size is necessary for derivation, we fix the mini-batch size according to a lower bound that we derive and show our work. To prove stochastic convergence of the objective value function we first establish a critical sparse stochastic gradient descent property. Using this stochastic gradient descent property we show that the sequence generated by the stochastic mini-batch SIHT is a supermartingale sequence and converges with probability one. Unlike previous work we do not assume the function to be a restricted strongly convex. To the best of our knowledge, in the regime of sparse optimization, this is the first time in the literature that it is shown that the sequence of the stochastic function values converges with probability one by fixing the mini-batch size for all steps.

Under review as a conference paper at ICLR 2023
CONVERGENCE OF THE MINI-BATCH SIHT ALGORITHM
Anonymous authors Paper under double-blind review
ABSTRACT
The Iterative Hard Thresholding (IHT) algorithm has been considered extensively as an effective deterministic algorithm for solving sparse optimizations. The IHT algorithm benefits from the information of the batch (full) gradient each point and this information is crucial key for the convergence analysis of the generated sequence. However, this strength becomes weakness when comes to machine learning and high dimensional statistical applications because calculating the batch gradient each iteration computationally expensive or impractical. Fortunately, in these applications the objective function has summation structure that can taken advantage to approximate the batch gradient by the stochastic mini- batch gradient. In this paper, we study the mini-batch Stochastic IHT (SIHT) algorithm for solving the sparse optimizations. As opposed to previous works where increasing and variable mini- batih size is necessary for derivation, the mini-batch size according to a lower bound that we derive and show our work. first establish
fix
To prove stochastic convergence of the objective value function critical sparse stochastic gradient descent property. Using this stochastic gradient descent property we show that the sequence generated by the stochastic mini-batch SIHT is a supermartingale sequence and converges with probability one. Unlike previous work we do not assume the function to be a restricted strongly convex. To the best of our knowledge, in the regime of sparse optimization, this is the first time in the literature that it is shown that the sequence of the stochastic function values converges with probability one by fixing the mini-batch size for all steps.
INTRODUCTION
We consider the following sparse optimization problem:
(P) min f(x, E) = 2/2 EN (0, x E C.
where f(); R2" x i l,..,, N, =. (5 , c(N)), and C. = (x E R" ||x|oo S 8} (sparsity constraint) is the union of finitely many subspaces whose dimension is less than equal to the sparsity level s such that S < n. The importance of the Problem (P) is due to the fact that finding sparse network whose accuracy on par with dense network amounts solving bi-level, constrained, stochastic, nonconvex, and non-smooth sparse optimization problem Damadi ct al. (2022). Thus finding efficient algorithms that solve Problem (P) can be beneficial for addressing compression of deep neural networks.
Among algorithms for solving sparse optimization the Iterative Hard Thresholding (IHT) algorithm has been a very successful one due to the simplicity of its implementation. The IHT algorithm not only has been practically efficient, but also shows theoretical promising results. It was originally devised for solving compressed sensing problems in 2008 Blumensath & Davies (2008) 2009)) Since
then, large body of literature has been studying from different perspectives. For example, Beck & Eldar (2013): Lu
(2014) 2015); Pan et al. (201 Zhou et al. (2021) consider convergence of (2014) Liu & Foygel Barber (2020) study the limit of the objective function value
iterations, Jain et al.
sequence, Liu et al.
(2017) : Zhu et al. (2018 8) address duality, Zhou et al. (2020); Zhao et al. (2021)
extend to Newton's s-type IHT, Blumensth (2112): Khanna & Kyrillidis ( (2018); Vu & Raich (2019); ;
Wu & Bian (2020) address accelerated IHT. and Wang et al. (2019); Bahmani et al. (2013) solve
logistic regression problem using the IHT algorithm. Recently Damadi & Shen (2022) introduced
the concepts of HT-uustable stationary points (saddle points in the sense of sparse optimization) and

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The mini-batch stochastic iterative hard thresholding
Require: x E C₂ such that ||x [lo S 8, stepsize < 7 < +. and S SB E N such that
SB N
for some 0.
1: for k = 0, 1,.... do
2: Construct B* by selecting Sn elements from (1...., .......Ny N) uniformly without replacement such
that |B| = Sn.
3: Calculate the stochastic mini-batch gradient as g( E, B*) = 1 Se EiEB V g())
4: x++1 Hx 70(** E, B*).
showed the escapability property of the HT-unstable stationary points as one the crucial properties of the IHT algorithm. Also, they showed Q-linearly convergence of the IHT algorithm towards strictly HT-stable stationary points. However, these desirable properties, requires to compute the batch (full) gradient at each iteration which is computationally expensive impractical with current GPUs.
On the other hand, almost all training for deep neural networks are done using the mini-bate batch stochastic gradient which is combination of the stochastic approximation Robbins & Monro (951) implemented by the backpropagation algorithm |Rumelhart et al. (1986). By taking the mini-batch stochastic approximation, we consider solving Problem (P) using the mini-batch Stochastic Iterative Hard Thresholding algorithm outlined in Algorithm J Similar to practice where the mini-batch size fixed beforehand, we fix the mini-batch size the beginning which is different from previous work Zhou et (2018) in this area. Also, for showing our theoretical results we directly use the mini-batch batch stochastic gradient and derive our theoretical results which different from previous works Chen & Gu 6) [i et al. (2016) where the batch (full) gradient is used to show the theoretical results. As opposed to other works where restricted strong convexity is necessary for deriving convergence results Liang al. (020);; Zhou et al. (2018) 18, here the only assumption strong smoothness on the objective function not on each individual one. Also, we assume that the objective function is bounded below function which is the case for objective functions used in machine learning applications. Similar to practice where the mini-batch size is fixed beforehand, we fix the mini-batch size at the beginning which is different from previous works Zhou et al. (2018).
make is the restricted
SUMMARY OF CONTRIBUTIONS
By considering the mini-batch SIHT Algorithm for Problem (P), we develop the following results:
We establish new critical sparse stochastic gradient descent property of the hard threshold- ing (HT) operator that has not been found in the literature.
For a given step-size 0 < 7 < +.2 we find a lower bound on the size of the mini-batch that guarantees the expected descent of the objective value function after hardthresholding
Using the sparse stochastic gradient descent property show that the sequence generated by the mini-batch SIHT algorithm is supermartingale and converges with probability one.
We show that for certain class of functions in Problem (P) where f(x, == ( (V.)))) f()) : : -> TR., the sum of norm squared of individual gradients restricted to a set some elements J, i.e., EN y ( evaluated at every point is proportionate to the norm of the batch gradient | fll where the proportionality constant only depends on the data. Moreover, dependency of the proportionality constant on the data restricted the set of I not the entire data.
2 RELATED WORK
In order improve computational efficiency of the IHT algorithm, algorithms based on stochastic hard thresholding try to use the finite-sum structure of problem (P) Nguyen et al.) (2017); 7): Li et al.
2

---

Under review as a conference paper at ICLR 2023
(016); Shen & Li (2017). The StoIHT algorithm is introduced in Nguyen et al. (2017) where each iteration a random element from the sum in Problem (P) is drawn and the associated gradient is calculated. Basically, the gradient is approximated by mini-batch stochastic gradient with size one. The StolHT algorithm defines a sparse subspace and then projects the updated vector into that. To show the theoretical results in Nguyen al. (2017), the restricted strong smoothness condition for each individual function in Problem (P) is required as well as the restricted strong convexity for the objective function. In addition, the StoIHT algorithm needs the restricted condition number be to 4/3 which is hard to meet in practice. The stochastic variance reduced gradient hard thresholding (SVRG-HT) algorithm Li et al. (2016); Shen & Li (2017) tries to mitigate the variance with cost of calculating the (batch) full gradient at some stages. This information of the batch gradient the key for reducing the variance. Similar to the StolHT algorithm, the SVRG-HT algorithm requires the restricted strong smoothness condition for each individual function in Problem (P) as well as the restricted strong convexity for the objective function. The Accelcrated Stochastic Block Coordinate Gradient Descent with Hard Thresholding (ASBCDHT) algorithm in Chen & Gu (2116) is a randomized version of the StolHT algorithm which suffers the drawbacks the StolHT algorithm, Le., calculating the full gradient and requirement of the restricted strong conditions. The Hybrid Stochastic Gradient Hard Thresholding (HSG-HT) algorithm in Zhou et al. (2018) is a variant of stochastic IHT algorithms that uses a mini-batch stochastic gradient at each step. However, from the theoretical perspective, the size of a mini- batih has to increase as the algorithm progresses. This makes the algorithm almost deterministic in calculating the gradient and defeats the purpose of using the mini-br bitih stochastic gradient. The stochastically controlled stochastic gradients (SCSG-HT) algorithm in Liang et al. (2000) uses mini-batch stochastic gradients with large batch size as opposed to the S SVRG-HT and the ASBCDHT algorithms to reduce the variance with less computation, i.e., not calculating the batch gradient at some steps.
We present the mini-batch stochastic IHT algorithm and show that the stochastic sequence of the function value a supermartingale sequence and it converges with probability one. To show our result, we assume the objective function has the restricted strong smoothness property and is bounded below which is the case for objective functions used machine learning applications. Also, to the best of our knowledge, in the regime of sparse optimization, this is the first time in the literature that it is shown that the sequence of the stochastic function values converges with probability one by fixing the mini-batch size for all steps.
3 DEFINITIONS
We provide some definitions that will be used throughout the paper.
Definition (Restricted Strong Smoothness (RSS)). A differentiable function f R -> RR. is said to be restricted strongly smooth with modulus Lg > or is L,-RSS if
L 2
f(y) & f(x) + (Vf(x), x)
Vx,y E R² such that ||x||o S 8, Ilyloo S s. (2)
Definition 2 (The HT operator). The HT operator H.(:) denotes the orthogonal projection onto multiple subspaces of IR" with dimension 1 < 8 < n, that is,
Hx(x) E arg min ||z [z-xxp] x||2- [
Claim 1. The HT operator keeps the largest entries of its input in absolute values.
For vector x R", Ix +1,...,,1 n denotes the of indices corresponding to the first largest
elements of x in absolute values. For example Hz[[1,-3) -3, 1 is either 03-3, 1] or [1, -3, 0] where Σ (2 and Σ {1, 2), respectively. Therefore, the output of may not be unique. This clearly shows why HTO is not a convex operator and why there is an inclusion in ( not an inequality.
Definition (Convergence with probability one). random sequence (xe IR²) ) in a sample space Ω converges random variable x" with probability one if
w E Ω lim (w) x"1 = 0.
k-+00
3

---

Under review as a conference paper at ICLR 2023
4 RESULTS
We consider solving Problem (T) using the mini-batch SIHT Algorithmmaan and develop results that guarantee the convergence of the sequence of function values generated by the SIHT Algorithm. To do so, we present results in two separate subsections. The first part provides stochastic results characterizing expectation of functions involving the sample average of given vectors. Then, in the subsequent subsection stochastic gradient result that is the foundation for the convergence of the function value sequence.
the aforementioned results to show Theorem 3 which establishes
4.1 STOCHASTIC RESULTS FOR SAMPLE AVERAGE
In this subsection, we consider a sample average whose elements are drawn uniformly and without replacement. Then, we prove Lemma that calculates the expected value of the norm squared of the sample average based on the covariance matrix of random vector whose elements are Bernoulli random variable determining elements of the sample average. Next, in Corollary Jsiin Lemma 2 we calculate the expected value of the squared distance between the sample average and the overall average. This result is extended in Theorem T where the expected value is calculated so that one is able to find the mentioned expectation based on each individual vector and the overall average. We start with the following well-known lemma.
Lemma 1 Mathai & Provost (192)). Let A E Raxn be deterministic matrix and & E R. be random vector that is distributed according to some probability distribution P. Then,
Eg
5 Ag Irace(AAoo(E))
E
ABE
To invoke the above lemma, notice that one can define a random vector whose elements are Bernoulli random variables determining whether the associated vector is in the sample average not. Thus we prove the following lemma.
Lemma 2. Let g
g (N) E R be N deterministic vectors and B C (1,.... set. Let == N &E (0) G(B) = 1
NN be random [ ExEBg G g()) g(()] RTxN, and
BBB (x. [B) where (B) is Bernoulli random vuriable such that z,(B) 1 if i E B otherwise 2, (B) f i= l,.... N. Assume Eg [B) = g, then for any random set B with fixed size [B), the following holds:
..... IN
Eg [B) = |B|2
trace (G GCoo(Z((B)) + ||@/
Once the above result is established, it is straightforward show the following by observing the fact that the sample average an unbiased estimator of the overall average, i.e., Es [G[]] = g.
Corollary 1. Assume all the assumptions in Lemma 7 hold. Then for any random set B with fixed size [B), the following holds:
Ep [II -]
B trace (G GCCCC((Z(B))
Finally, we use the above results to prove the following which calculates the expected squared distance between the sample average and the overall average based individual vectors and the overall average. The following result is critical because later we will see that Equation 7 connects the mini-batch stochastic gradient, the batch gradient, and individual gradients in Problem (P).
Theorem Assume all the assumptions in Lemma 7 Thold. If elements of the random set B are drawn uniformly and without replacement, then
B
B
N
Eg [B - -
Σ 1=1
lg
10 1
N N1882
B
BN
N
1=1
4

---

Under review as a conference paper at ICLR 2023
4.2 STOCHASTIC RESULTS FOR HARD THRESHOLDING OPERATOR
The goal of this subsection is to show the random sequence (f(x* )221) generated by the mini-batch SIHT algorithm converges with probability one. To show this we prove that the random sequence of the function value is supermartingale sequence so the expected value of the function value sequence decreasing. To achieve our goal, we prove the following lemma that provides an upper bound on the function value evaluated at a thresholded vector. Notice that the following result does not require the input be an updated vector by the gradient.
Lemma& 3. Let f I= + R be in C¹ and Ls-RSS. Then for fixed x E C. with any I, any Y S I.. and any given vector g E IR", either of the following holds for any y E Ha(x - (g) with any Iy:
f(y) S fxx)
2 (1 - (,7))1827 11
2 2 +
+ 11022,,
(8)
where I = II and =g fx(x).
Observe that in the above lemma the vector g can be any vector in R It need not be the gradient nor the mini-batch gradient. However, in the following lemma we prove that if g is designated to be an unbiased stochastic approximation of the gradient at an arbitrary point, then the following result holds.
Lemma Let f : R" + I be in C and Ls-RSS, Assume g(x, w) be an unbiased stochastic approximation of the gradient at x E R" where w ~ D for some distribution D, i.e Eglg(x, w)) f(x). Then for a fixed x E C2 with any I3 and < << S t., either of the following holds for any - -x((xw)) with any ( y(w) E H.(xx~g(lh
Ellf(Y(W)) - f(x) -
7 (1 (1-L,, L,7) En B (x, 11
E.
2 V2 (x) 2
(w) (9)
where I(w)= = IN (w)) and 8(w) g(x, w) V fxx)
The following Theorem is the climax of our technical results because it establishes stochastic gradient descent property for the expectation of the function value. Later we will see how Inequality
11 used in Theorem to show the sequence of the function values generated by the mini-batch SIHT is a supermartingale sequence.
Theorem 2. Let f(0) R x E + R be in C¹ for i = I,...,N .N and E = {
((N)) be
given set such that ((x, = N/4 Em ((0) (x, (x),))) be an -.,SSS function. Assume there exists
0 such that
N
EJ [4 (1) (x, 11) s [
(10)
for all x E Th and any rundom index set I S. (I....,,)) ,n} with |T| S 8. Let G(x, E, B)
[8 Lier V (x, ) be the mini-batch stochastic gradient at any x E Rn where C {I...., N} be a random set whose elements are drawn randomly and uniformly from {l..... N} without replacement and its size is [B). For a fixed 0 < 7 <. T, assume the size of is fixed such
that [B| 2 (1(11
1-h,7 |1+ N=1) and let Ç :
N N- | for N 2 2. Then for fixed x E C, with
1+1.7
any Is the following holds for any ((B) E H,(x - rg(x. E, B)) with any (B)
E8 [()
< F(x - ? 11)
2
(11)
- 2 +
Lo7) (1
+ (1- c
11 L-L
"I ( )
Byn
E
V fxx
N
where 1 - N
1.y7 1 +
I+L+ < 2 0.
'hhe class consisting of all differentiable functions whose derivative is continuous. In Remark applications
[ we explain why such a always exist for widespread objective functions in machine learning
5

---

Under review as a conference paper at ICLR 2023
A crucial assumption for proving the results in Theorem 11I is the assumption made in Inequality (10). In the following Claim we show that for a certain class of functions с >> 0 always exists and does not depend the function. We will prove that for these special classes of functions the value of e only depends on the data.
Let the given set E in Problem (P) be defined such that = IV....... No where each V. is the i-th row of a given matrix V RNNx. Then the objective function in Problem (P) can be
Claim 2.
defined as f(x, N E f( (V:x)) f(
R x x -
R. and the following holds:
N
2
|Vo (V xI2
(
V)Il2 (12)
max r=l.....N
min (VI Jo Ig. VT)
where (L....,, with [J] S S, IJ. E RIJ xn is a restriction of the Identity matrix whose rows are associated with indices in J, VI I - E V.: Tmin (-) is the smallest singular value, Vo; is the i-th column of V, and (-)J is vector restricted indices J.
Remark 1. The above claim shows that for class of functions constant c. > Theorem Bawways exists and it does not depend on the value of x or its gradient whether it is batch (full) gradient or individual one. For an example of functions belonging to this class one can think of the mean square error loss used for linear regression as follows:
+ (V the
N
1 f(x, V) = N VV - y
E (Vix y1)² N
where V E RNNx Vi is the i-th row of V, E R is the optimization variable, and IRN is the target. Also, the logistic regression loss (binary cross entropy) is a function for which > in Inqquality 12 always exists since it can be written as follows:
1(x, V)
N Σ (- y log (1 + +eeee.vnn vv.x))
where V E NNn whose last column is all one, Vi is the i-th row of V, R" 9 x b] such that w E pn-1 and E IR are the optimization variables, and y( E (0. 1) for = I....,N.
Now we can provide result showing that by fixing a sparse point, one can use the stochastic mini-batch gradient with fixed mani-batch size determined in Theorem 3 and decrease the function value in expectation.
Theorem Assume all the assumptions in Theorem hold. Then for a fixed x E C. with any Ix the following holds for any (B) E H2 - - E,E, B)):
EB [(
x] s (x
VIz (x)
(13)
The above result is the analogue result to (Damadi & Shen 2022
Corollary 1).
Theorem 4. Assume all the assumptions in Theorem 2 hold. Let f be a bounded below differential
function and (xx x=22) be the stochastic IHT sequence. Then, (f(x², x
a
supermartingale sequence and converges random variable f with probability k21
CONCLUSION
We showed the stochastic sequence generated by the mini-batch stochastic IHT is supermartingale sequence converging with probability one. To show this result we used the stochastic gradient descent property that we derived where utilized the property of the mini-batch stochastic gradient the sample sum of a finite sum.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sohail Bahmani, Bhiksha Raj, and Petros T Boufounos. Greedy sparsity-constrained optimization. Journal of Machine Learning Research, 14(Mar):807-841 2013.
Amir Beck and Yonina C Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on Optimization, 23(3):1480-15000 2013.
Thomas Blumensath. Accelerated iterative hard thresholding. Signal Processing, 92(3):552-756, 2012.
Thomas Blumensath and Mike E. Davies. Iterative thresholding for sparse approximations. Journal of Fourier analysis and Applications, 14(5):629-654, 2008.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 27(3):265-227 2009.
Jinghui Chen and Quanquan Gu. Accelerated stochastic block coordinate gradient descent for sparsity constrained nonconvex optimization. In UAI, 2016.
Saeed Damadi and Jinglai Shen. Gradient properties of hard thresholding operator. arXiv preprint arXiv:2209.0822 08247, 2022.
Saeed Damadi, Erfan Nouri, and Hamed Pirsiavash. Amenable sparse network investigator. arXiv preprint arXiv:2202.09284, 2022.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. Advances in neural information processing systems, 27, 2014.
Rajiv Khanna and Anastasios Kyrillidis. Iht dies hard: Provable accelerated iterative hard thresholding. In International Conference on Artificial Intelligence and Statistics, pp. 188-198. PMLR, 201 8.
Xingguo Li, Raman Arora, Han Liu, Jarvis Haupt, and Tuo Zhao. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint 1605.0:605.2111 2016.
Guannan Liang, Qianqian Tong, Chunjiang Zhu, and Jinbo Bi. An effective hard thresholding method based on stochastic variance reduction for nonconvex sparse learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1585-1592, 2020.
Bo Liu, Xiao-Tong Yuan, Lezi Wang, Qingshan Liu, and Dimitris N Metaxas. Dual iterative hard thresholding: From non-convex sparse minimization to non-smooth concave maximization. In International Conference on Machine Learning, pp. 2179-2187. PMIR, 2017.
Haoyang Liu and Rina Foygel Barber. Between hard and soft thresholding: optimal iterative thresholding algorithms. Information and Inference: A Journal of the IMA, 9(4):899-933. 2020.
Zhaosong Lu. Iterative hard thresholding methods for lo regularized convex cone programming. Mathematical Programming. 147(1):125-154 2014.
Zhaosong Lu. Optimization over sparse symmetric sets via a nonmonotone projected gradient method.
arXiv: Optimization and Control, 2015.
Arakaparampil M Mathai and Serge Provost. Quadratic forms in random variables: theory and applications. Dekker, 1992.
Nam Nguyen, Deanna Needell, and Tina Woolf. Linear convergence of stochastic iterative greedy algorithms with sparse constraints. IEEE Transactions Information Theory, 2017.
Lili Pan, Shenglong Zhou, Naihua Xiu, and Houduo Qi. A convergent iterative hard thresholding for sparsity and nonnegativity constrained optimization. Pacific Journal of Optimization, 13(2): 325-353, 2017.
7

---

Under review as a conference paper at ICLR 2023
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088):333-536, 1986.
Jie Shen and Ping Li. A tight bound of hard thresholding. The Journal of Machine Learning Research, 1881),7650-7691 2017.
Trung Vu and Raviv Raich. Accelerating iterative hard thresholding for low-rank matrix completion via adaptive restart. ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2917-2921. IEEE, 2019.
Rui Wang, Naihua Xiu, and Shenglong Zhou. Fast newton method for sparse logistic regression. arXiv, (1901.02768), 2019.
Fan Wu and Wei Bian. Accelerated iterative hard thresholding algorithm for to regularized regression problem. Journal of Global Optimization, 76(4))819-840, 2020.
Chen Zhao, Naíhua Xiu, Houduo Qi, and Ziyan Luo. lagrange-newton algorithm for sparse nonlinear programming. Mathematical Programming, pp. 1-26, 2021.
Pan Zhou, Xiaotong Yuan, and Jiashi Feng. Efficient stochastic gradient hard thresholding. Advances in Neural Information Processing Systems, 31, 2018.
Shenglong Zhou, Lili Pan, and Naihua Xiu. Subspace newton method for the legrluuldd optimiza- tion. arXiv, (2004.05132). 2020.
Shenglong Zhou, Naihua Xiu, and Hou-Duo Qi. Global and quadratic convergence of newton hard-thresholding pursuit. J. Mach. Learn. Res., 22(11): 2021.
Wenxing Zhu, Zhengshan Dong, Yuanlong Yu, and Jianli Chen. Lagrange dual method for sparsity constrained optimization. IEEE Access, 6:28404-28416, 2018.
8


Reviews:
[{"review_id": "_VlOI05VSE", "reviewer": "Reviewer_mF9G", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study mini-batch stochastic iterative hard thresholding (IHT). IHT is a well known algorithm for sparse optimization with extensive literature. IHT is essentially $\\ell_2$-projected gradient descent on the set of s-sparse vectors. Given the ML-wide focus on stochastic optimization algorithms, it is natural to study the guarantees of stochastic IHT.\n\nThe main result of the paper is a martingale convergence result that claims stochastic IHT converges to the optimal function value, although no convergence rate is given.", "summary_of_the_review": "In summary, while I like the problem of minibatch stochastic IHT and the approach, I find that there are significant issues with novelty that should be resolved in the literature review section, as well as my other concerns outlined above. I encourage the authors to continue working on the manuscript since I think this is an important subject. ", "strength_and_weaknesses": "Strengths\n- Advancing the theoretical understanding of stochastic IHT is an important task.\n- The writing is generally easy to follow.\n\nWeaknesses\n- The literature review is quite limited.\n- The proofs are missing, so it is not possible to fully verify the claimed results.\n- In Claim 2, the minimum singular value should be 0, because the matrix is low-rank. If the authors define minimum singular value differently, it is hard to know because the proof is not included.\n- In Claim 2, an upper bound is derived for c (10). Based on this, $c$ seems to be $\\geq N^2$. When I plug that back into Theorem 2, I get a batch size of roughly $N - \\Theta(1)$. This does not seem like a great choice for a batch size, which typically should be much less than $N$. It would be great if the authors could comment on whether I am missing something here.\n- There are no experiments, which could shed light for example on what is the value of c in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Pt1SorQ4Ncg", "reviewer": "Reviewer_HcXm", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of minimising an objective function over all $s$-sparse vectors. In order to solve this non-convex problem, the authors study stochastic mini-batch of version of the well-known iterative hard thresholding algorithm.\n\nThis paper makes the following contributions:\n1. It establishes a stochastic gradient descent property (Theorem 2).\n2. This property is used to show that the objective values at each iteration form a super martingale, which is claimed to imply convergence. \n", "summary_of_the_review": "Due to the shortcomings described above, the paper seems to be very incomplete and I cannot recommend acceptance.", "strength_and_weaknesses": "Unfortunately, the manuscript at hand seems very incomplete. Thus, at its current state it is impossible to assess its contributions. \n\n1. The current paper does not contain a single. Thus, I am not able to see whether some of those statements are correct..\n2. Some of the assumptions for the theoretical statements are too vague and not clearly stated. (I will give some examples below.)\n3. The current paper does not include any simulations. It would be great if the authors could include some numerical experiments to corroborate their theoretical results. This is maybe less important in comparison to the first two points but I also think that a complete submission should also contain numerical experiments.\n\nHere are some more specific points:\n1. Lemma 2: You say that B is a random set. What is the probability distribution? Where is it specified? In a similar vein, what is the probability that the Bernoulli random variable $z_i (B)$ is one? Are the  $z_i (B)$  i.i.d. random variables?\n2. Lemma 3: What is meant by \"either of the following holds\". I only can see one statement.\n3. Theorem 2: What is the distribution of the random set $\\mathcal{J}$?\n4. Theorem 4: How is this random variable $f^{\\star}$ characterized?\n\n\nTypos:\n1. page 1, abstract: \"...we do not assume the function to be (a) restricted strongly convex.\"\n2. Lemma 4: \"Assume $g(x,\\omega)$ be (is) an...\"\n3. Theorem 2: \"where $ B \\subset  {1; ... ; N } $ be (is)\"\n4. Claim 2, definition of $f(x, \\Xi)$: Is there an $f^{(i)}$ too much? Also should $f^{(i)} be $f$ instead?!  \n5. Claim 2: Should \"$VI_J^T I_J=...$\" read \"$ VI_J^T I_J V^T=...$\" instead?\n6. Theorem 4: differential -> differentiable?!", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8TTp2z6AKAV", "reviewer": "Reviewer_jszD", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the mini-batch Stochastic IHT (SIHT) algorithm for solving sparse optimization problems.  A new lower bound is found to help design the mini-batch size. The loss sequence generated by SIHT is proved to be a supermartingale sequence and converges with probability one. ", "summary_of_the_review": "The reviewer assumes the submission is incomplete work. There is a lack of proof in Theorems and lemmas. No experiments to demonstrate the designed method is better/worse than current methods.", "strength_and_weaknesses": "1. A new lower bound is provided.\n2. The designed method is proven to be supermartingale.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject