Gradient Properties of Hard Thresholding Operator
Authors: Saeed Damadi
Jinglai Shen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Sparse optimization
Hard thresholding
Iterative hard thresholding
HT-stationary point
HT-stable point
HT-unstable point

Abstract: Sparse optimization receives increasing attention in many applications such as compressed sensing, variable selection in regression problems, and recently neural network compression in machine learning. For example, the problem of compressing a neural network is a bi-level, stochastic, and nonconvex problem that can be cast into a sparse optimization problem. Hence, developing efficient methods for sparse optimization plays a critical role in applications. The goal of this paper is to develop analytical techniques for general, large size sparse optimization problems using the hard thresholding operator. To this end, we study the iterative hard thresholding (IHT) algorithm, which has been extensively studied in the literature because it is scalable, fast, and easily implementable. In spite of extensive research on the IHT scheme, we develop several new techniques that not only recover many known results but also lead to new results. Specifically, we first establish a new and critical gradient descent property of the hard thresholding (HT) operator. Our gradient descent result can be related to the distance between points that are sparse. However, the distance between sparse points cannot provide any information about the gradient in the sparse setting. To the best of our knowledge, the other way around (the gradient to the distance) has not been shown so far in the literature. Also, our gradient descent property allows one to study the IHT when the stepsize is less than or equal to 1/L, where L>0 is the Lipschitz constant of the gradient of an objective function. Note that the existing techniques in the literature can only handle the case when the stepsize is strictly less than 1/L. By exploiting this we introduce and study HT-stable and HT-unstable stationary points and show no matter how close an initialization is to a HT-unstable stationary point (saddle point in sparse sense), the IHT sequence leaves it. Finally, we show that no matter what sparse initial point is selected, the IHT sequence converges if the function values at HT-stable stationary points are distinct, where the last condition is a new assumption that has not been found in the literature. We provide a video of 4000 independent runs where the IHT algorithm is initialized very close to a HT-unstable stationary point and show the sequences escape them.

Under review as a conference paper at ICLR 2023
GRADIENT PROPERTIES OF HARD THRESHOLDING OPERATOR
Anonymous authors
Paper under double-blind review
ABSTRACT
Sparse optimization receives increasing attention in many applications such as compressed sensing, variable selection in regression problems, and recently neural network compression in machine learning. For example, the problem of compress- ing a neural network is a bi-level, stochastic, and nonconvex problem that can be cast into sparse optimization problem. Hence, developing efficient methods for sparse optimization plays a critical role in applications. The goal of this paper is to develop analytical techniques for general, large size sparse optimization problems using the hard thresholding operator. To this end, we study the iterative hard thresholding (IHT) algorithm, which has been extensively studied in the literature because it is scalable, fast, and easily implementable. In spite of extensive research on the IHT scheme, we develop several new techniques that not only recover many known results but also lead to new results. Specifically, we first establish a new and critical gradient descent property of the hard thresholding (HT) operator. Our gradient descent result can be related to the distance between points that are sparse. However, the distance between sparse points cannot provide any information about the gradient in the sparse setting. To the best of our knowledge, the other way around (the gradient to the distance) has not been shown so far in the literature. Also, our gradient descent property allows one to study the IHT when the stepsize is less than or equal to 1/L, where L>0 is the Lipschitz constant of the gradient of objective function. Note that the existing techniques in the literature can only handle the case when the stepsize is strictly less than 1/L. By exploiting this we introduce and study HT--ttble and HT- stationary points and show no matter how close an initialization is to HT-unstable stationary point (saddle point in sparse sense), the IHT sequence leaves it. Finally, we show that no matter what sparse initial point is selected, the IHT sequence converges if the function values at HT-sstble stationary points are distinct, where the last condition a new assumption that has not been found in the literature. We provide video of 4000 independent runs where the IHT algorithm initialized very close to a HT-unstable stationary point and show the sequences escape them.
INTRODUCTION
Solving sparse problems has gained increasing attention in the fields of statisties, finance, and engineering. These problems emerge in statistics variable selection in linear regression problems Fan Li (200T); Zou & Hastie (2005); Chun & Keles (2010); Desboulets 2018), mixed-integer programs Bourguignon et al. (2015) y Liu et al. (2017) ; Dedieu et al. (2021), portfolio optimization in finance Brodie et al. (2009); Chang et al. (2000), compressed sensing in signal processing Foucart & Rauhut (2013) Eldar & Kutyniok (2012). and compressing deep neural networks in machine learning Damadi et al. (2022): Molchanov et al. (2017): Gale et al. (219), just to name a few. Due to the use of (o-(pseudo) norn!" these problems are discontinuous and nonconvex. The form case have been addressed by the hard thresholding (HT) techniques specially the iterative HT (IHT) scheme Blumensath & Davies (2008); Beck & Eldar 2013); Lu (2014); Zhou et al. (2021). The Lasso-type, Basic Pursuit(BP) (tP)-type, and BP denoising (BbsssnnggBDNNyytyer problems consider -n-rrrm as a convex approximation of no-mr Tibshirani (1996); Mousavi & Shen (2019). Nonconvex
approximation of fo-momm as (pseudo) norm (0 < p < 1) has also been studied well Chartrand
fo is not mathematically norm hecause for any norm and E IR, ||a@|| |o| [0]] while ||a0||o
|o|||0||o if and only if [a]]

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The iterative hard thresholding (IHT)
Require; x² I2 such that ||x*Ilo I s and stepsize y > 0.
I: x x+1 E (x* 7V fxx")x) )) for h 1,
(2007 : Foucart & Lai 2009); Lai Wang 2011]; Wang al. (2011 ) Zheng al. (2017); Won et al. (2022). Sparse optimization problems can also be formulated as mixed-integer programs Burdakov et al. (2016). Intrinsic combinatorics involved in sparse optimization problems makes it an NP-hard problem (even for quadratic loss Davis (994); Natarajan (1995) it is difficult to find global minimizer. However, greedy algorithms have developed to find local minimizers. To this end, following the ideas of matching pursuit (MP) and orthogonal MP (OMP) Mallat & Zhang (1933;; Pati et al. (993) as greedy algorithms, numerous other greedy algorithms have been developed such stagewise OMP (StOMP) Donoho et al. (2012), regularized OMP (ROMP) Needell & Vershynin (2009) 2010), Compressive Sampling MP (CoSaMP) Needell & Tropp 2209). and Gradient Support
Pursuit (GraSP) Bahmani et al. (2013). It should be noted that sparse optimization not restricted
to finding sparse vector. For example Fornasier et al. 2) Haeffele et al. (2014); Davenport & Romberg 2016), finding a low-rank matrix considered. The problem of finding low-rank matrix
is counterpart to finding a sparse vector when it comes applications dealing with matrices. In addition to devising algorithms for solving sparse optimization problems, developing first and second order optimality conditions have also been addressed well Pan et al. (2017a); Bauschke et al. (2014);
Beck & Hallak (2016); Li & Song (2015): Lu (2015) Pan et al. (2015); Bucher Schwartz (2018)
The general sparse optimization problem is the following:
min fxx s.t. n
where C. = fx R" |x||o S $} (sparsity constraint) is the union of finitely many subspaces of dimension such that lower bounded and continuously differentiable, i.e., C In this paper we address a special case of Problem (T) where X R follows:
n, X' is a constraint set in RR,, and the objective function : RR" IR
min f(x) s.t. X E C.
(P)
(2)
To address Problem 2 the following fundamental questions arise:
(Q1) What are the necessary/sufficient conditions for local/global minimizer of Problem
(Q2) What are the characteristics of accumulation points of algorithms solving Problem p
(Q3) Under what condition(s) does an accumulation point become a local/global minimizer?
(Q4) If accumulation point a local/global minimizer, what the rate of convergence?
By considering the IHT algorithm, we will answer the above questions. This algorithm has been extensively studied in the literature. It was originally devised for solving compressed sensing problems in 2008 Blumensath & Davies (2008 2009). Since then, there has been large body of literature studying the IHTT-tppe algorithms from different standpoints. For example, [Bck & Eldar (2013); Lu [2014] 2015):[Pa Pan et al. (201 7b); Zhou et al. (2021) consider convergence of iterations, Jain et al. 2014); Liu & Foygel Barber (2020) study the limit of the objective function value sequence,
Liu et al.
2017):
; Zhu et al. (2018) address duality, Zhou al. (2020); Zhao al. (2021) extend
to Newton s-type IHT, & Gu (2016); Li et al. (2016) Liang et al. (2020): /Zhou et al. (2018
consider the stochastic version, Blumensath (2012); | 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.
SUMMARY OF CONTRIBUTIONS
By considering the IHT Algorithm T for Problem 2 we develop the following results:
We establish a new critical gradient descent property of the hard thresholding (HT) operator that has not been found in the literature. Our gradient descent result can be related to
2

---

Under review as a conference paper at ICLR 2023
the distance between points that are sparse. However, the distance between sparse points cannot provide any information about the gradient in the sparse setting. To the best of our knowledge, the other way around (the gradient to the distance) has not been shown far in the literature. This property allows one to study the IHT when the stepsize is less than or equal to 1/T, where T. >> 0 is the Lipschitz constant of the gradient of an objective function. Note that the existing techniques in the literature can only handle the case when the stepsize is strictly less than 1/ As an example, one can refer to Liu & Foygel Barber (2020) that needs the stepsize to be greater than or equal to 1/L.
We introduce the notion of HT HT-stabbeemmstablee stationary points. Using them we establish the escapability property of HT stationary points (saddle point the sparse sense) and local reachability property of strictly HT-stable stationary points. We provide a video of 4000 independent runs where the IHT algorithm is initialized very close to HTT-unstable stationary point and show the sequences escape them.
We also show that the IHT sequence converges globally under a new assumption that has not been found in the literature. In addition, Q-linearly convergence of the IHT algorithm towards a local minimum when the objective function is both RSS and restricted strictly convex is shown.
According to our results, we address (Q1) and (Q2) by establishing a new gradient descent property of the hard thresholding (HT) operator and introducing the notion of HT-stablleunstaable stationary points. By considering RSS, restricted strictly convex, and RSC properties we address (Q3) and (Q4). Table is provided to compare our results with those in the literature. It shows what has been done chronologically and demonstrates our results.
2 RELATED WORK
To answer (Q1) Beck & Eldar (013) introduces L-stationarity property as a necessary condition for an optimal solution of Problem The L-stationarity property is defined when the gradient of the objective function is Lipschitz. Also. Beck & Eldar (2013) addresses (Q2) by showing any accumulation point of the IHT algorithm is L-stationary. Lu in Lu (2014) restricts the objective function to be convex and shows that the IHT sequence converges to local minimum when the objective function is regularized by fo-norm and X' is box constraint. Jain et al. Jain et al. (2014) put more restriction on the objective value function and show that the objective value function sequence generated by the IHT algorithm converges to a value attained under a more restricted sparsity constraint. The restrictions used in Jain et al. (2014) are Restricted Strong Smoothness (RSS) and Restricted Strong Convexity (RSC). The RSS and RSC properties are introduced by Negahban et al. (2012) and first used by Bahmani et al. (2013) for sparsity optimization problems. Currently, they have become standard restrictions for analyzing sparsity optimization problems. Under RSS and RSC properties for the objective function, one is able to address (Q3) and (Q4).
Finding a closed-form expression for Pc.nx when X' is an arbitrary set is difficult. However, Beck & Hallak (2016) shows orthogonal projection of a point onto C, n X can be efficiently computed when X' is a symmetric closed convex set. In this context, tWo types of sets are of interest: nonnegative symmetric sets and sign free sets. To address (Q1) in more generalized setting, Beck and Hallak Beck & Hallak (0016) characterize L-stationary points of Problem (1] when X' is either nonnegative symmetric set or sign free. Also, Lu in Lu (2015) considers the same setting as Beck & Hallak (016)) and introduces a new optimality condition that is stronger than L-stationary. Hc devises a Nonmonotone Projected Gradient (NPG) algorithm and shows an accumulation of the NPG sequence is the global optimal of Problem (]. Pan et al. [aan et al.] (2017a) consider Problem (I) when X RR. They develop an Improved IHT algorithm (IIHT) that employs the Armijo-type stepsize rule. They show when the objective function is RSS and RSC, the IIHT sequence converges to a local minimum. A recent work by Zhou et al. Zhou et al. (2021) develops Newton hard--Treeholding Pursuit (NHTP) for solving problem (2) They show that when accumulation points of the NHTP sequence are L-stationary and are isolated, the sequence converges with a locally Q-quadratic rate. Table compares current results in the literature.
3

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of results for the deterministic type algorithms.
Paper
Objective functicn
Comstrinnts
Stepaize
Optimality conditions
Mothod Convergence
Rack
Ficter
[(:]: L.LG
X
0 <. 1/7.
Hu(x" (
accumalation point the sequence satisfies x' H,(x" V (e 3.I).
2013
L6 2014
Fax voevex
[tx) - A|sile
X S X
U. 1/2
Local minimizer
The IHT soguence converges a local minimizer. (Theorem 3.3)
Beck
Hallak
[3g:: LAGG
K C, nxx X nonnggaiiv symmetric sign
1/2
Basic feasibility
BPS
The sequence of BFS converges to bosic fcusible point (Lemma 7.1).
La 2015
[3) LLLG
x t'ss nonnggaiive symmetric or sign free
Palrxex" - (
NPG
An accummlation point NPG sequense saristies the opsimalitt condition (Theorem 433).
2037b
R,5 aRC
flxt
E Painnr (x* (V
L.,sttiiooary
WHT
Any accumulation point UIT sequence canverges Eu-staaionay point (Thoorem
The UIIT sequence convergees to a local mininizer ('heocem 3.2). If [[x"' ll < then
Pan al 20176
L, RSS & 3,-RSC
((4)
X nEC,
D. 1/2,
x (o HV
DET
x is global minimizer. When [*'l
the lilI sequence converges (-iinarll (Thoorum 3.41.
fiw) RSS
XEC,
0.6 < 1/1,,
NHTP
Any accumnlation paint x of NHIP sequence an I.. L..sstaionury point 1'x is isolated, the entire sequence converges.
2021
ot Lissttooonuryy
flad) I.,-R55 & A.-RSC
X Ra(x" -V/(x)))
The NHTP sequence converges to Lttstooionryy point (Thoorem 10).
Zoou
et
al.
& Resuiived llessian X C, is Lipichitz
y x/2, Losntionnry
NHIP
2011
Locally, it converges quadraticall.
If fix)) A fly") for lirall x" x',y" IfT-tabll puintss puints, statting x converges to some HT-smable points.
Ours
Fix) RSS
xeC.
R. - or IIT--aablee
sequenee
Corollary global convergence
all HT-smble points are isolated. by stating from x C, the IHT sequence converges some HT-stable points. Corollay global cuneeggence
Oura
f(x) L,-S55
x C
x E Ha(x* (.(()))) Ht
IHT
[(x) RSS
H.ix" VV("))
By starting x 8ix" 8) nCC sequence converpes to MT-ariclly stable x" point lineurly (Proposition))
Oura
Strictly corvex on Sy with [/] -
D<ys $17,
or HT-smeelly stale
3 DEFINITIONS
We provide some definitions that will be used throughout the paper. These definitions are the HT operator (HTO) and HTO inequality, RSS and RSC functions.
Definition (Restricted Strong Smoothness (RSS)). A differentiable function f : R2" - IR is said to be restricted strongly smooth with modulus Lg
is L,-RSS if
f(y) S [xx + (VI(x), - x) lly x12 Vx,y y E TR" such that ||x||o S 8, lly S 8. (3)
Definition 2 (Restricted Strong Convexity (RSC)). differentiable function : IR. - IR is said to be restricted strongly convex with modulus B. 0 or is B.-RSC if
Bg f(y) 2 fxx + (Vf(x). x) lly
Vx,y RR" such that ||x|lo s, llyllo I s. (4)
Definition 3 (The HT operator). The HT operator H.(:) denotes the orthogonal projection onto multiple subspaces of Re with dimension 1 S s < n, that is,
Hx(x) E arg min x||2- [elloS
(5)
Claim 1. The HT operator keeps the largest entries of its input in absolute values.
For vector E R", I3 C [[l...,,] _ denotes the set of indices corresponding to the first largest
elements of x in absolute values. For example [[[[1,33, ) is either 03-3, 1]" or [1, 11,-3,0 3,0] where Σ (2, 3} and I {1, 2), respectively. Therefore, the output of it may not be unique. This clearly shows why HTO is not a convex operator and why there is an inclusion in (5) not an inequality.
4 RESULTS
We consider solving Problem (2) using the IHT Algorithm | and develop results on the HT operator. Using them, the behavior of the IHT sequence generated by Algorithm T is characterized. Towards
4

---

Under review as a conference paper at ICLR 2023
this end, statements of the main results provided and all the technical proofs postponed to the Appendix for the reviewers.
4.1 GRADIENT DESCENT PROPERTY
First, we establish new and critical gradient descent property of the hard thresholding (HT) operator.
Theorem 1. Let f R - R be differentiable function that is Lg-RSS, y H2(x (x)) with any D and 0 < < E. and x be a sparse vector such that ||x|lo S s with any T. Then,
2 LL ff S f(x) f(y)
(6)
where VIyuzz f(x) is the restriction of the gradient vector to the union of the index sets IV and TV
Theorem I provides a lower bound on the difference between the current function value evaluated at x and the one evaluated at the updated point provided by the HTO, i.e., y. Note that, y may not be a unique vector that has nonzero elements. Nonetheless, stated in Theorem [ Inequality (T) holds for any y that might be the output of the HTO. As one clearly see, the descent can only be characterized by looking at the entries of the gradient that are restricted the union of the largest elements in both x and y. The rest of the gradient can be ignored. Since one may be interested in characterizing the descent using the distance between x and y, we provide the following corollary.
Corollary 1. Assume all the assumptions in Theorem 7 hoold then,
- x11 - 7 (1- L,>)I L.>L,>>l f(x) f(x) f(x) s(x) fly) 1 L I 67
The above result shows the superiority of our gradient result because our gradient result can be related to the distance of points that are sparse. However, the distance between sparse points cannot provide any information about the gradient. To the best of our knowledge, the other way around (the gradient to the distance) has not been shown so far in the literature.
Algebraically speaking, characterizing a descent of the function value solely with the information of the current iterate, i.c., is of more interest. To this end, we provide another corollary to Theorem ! that ties the descent to x only.
Corollary Assume all the assumptions Theorem 7 Thold. Then, the norm of the gradient restricted to any D/ can be bounded as follows:
V f < f(x f(y)
(8)
By this point, we have shown that applying the HTO once, can result in smaller function value provided the gradient over the largest entries of x are nonzero. This can be utilized show the sequence generated by the IHT algorithm is nonincreasing. Specially, if the generated sequence has an accumulation point, the objective value function sequence converges to the objective value of the accumulation point.
Corollary 3. Let f R" + R. be bounded below differential function that is L.-RSS and (x*) k20 nonincreasing and converges.
be the IHT sequence (x*) k20 with < 7 S +., Then, (f(x*)
k20
Also, if is an accumulation point of (x*) k20 then (F(x²t) k200
f(x)).
Next, we look at basic stationary points of Problem and show their properties.
4.2 OPTIMALITY CONDITION BASED ON THE HT PROPERTIES
In this subsection, we will show that not all basic stationary points of Problem 2 are reachable when the IHT algorithm is run. To do so, the notion of HT stationary points are introduced as follows.
A sequence may not converge hut it may have accumulation point. For example 1, 11,1 1, -1,-,... is not convergent sequence but it has accumulation points.
5

---

Under review as a conference paper at ICLR 2023
4.2.1 HT stationary POINTS
Definition 4. For a given constant 7 say that a sparse vector Cg HT-stable stationary point of Problem (2) associated with Y if V xupp(>)) f fxx") 0, and
min (aail: : 2 max (1Vzf(x') supp(x))) 7 ( (supp(xc f(xx)
(9)
(Note that min ( |a;]| i E I3¹) is unique and does not depend on the choice Ig If
smpp(x-) (oppxx)((xx f(xx)((xxx)))))))()) but (9) fails, we say that x" is HT-unstable stationary point with 7,- More-
over, V supp(x-) [xx) - U and ( holds strictly, namely,
min (Ia:l: > >7 (IV [vxf(x') & supp(x"))
(10)
we say that x" is a strictly HT-stable stationary point associated with
Note that when ||x*|lo = 8, I is unique and equals supp(x") such that supp(x") in the above definition can be replaced by I Moreover, if x" is a strictly HT-stable stationary point, then we must have Isx supp(x") (or equivalently ||x = s) because otherwise, -min (xx]
I
> (x=pp(x=))= f("))=((" oloo which is impossible.
Remark 1. As stated in the Definition 4 basic stationary point is a point whose gradient is zero over the nonzero elements. For example, suppose X = [0, 4, 0, 2] E R is basic stationary point. Then V f = [e1. O, C2, 0j where C1, C2 are scalars. The main idea of the HT-stable stationary point is that it has to be basic stationary point. In other words x can be basic stationary point but not a H'T-stalle stationary point. This is the analogue of the non-sparse optimization where a point & whose gradient zero, ie., ((x 0 may be necessary a local or global minimizer. It can be saddle point.
The main message of Definition 4 is the following: "only by looking at the gradient restricted to the nonzero entries of basic feasible point, cannot say whether it is local minimizer of Problem (2) or not".
Remark 2.
An HT-stable stationary point associated with 7 equivalent the 4-stationary point of Problem 2
defined in (Beck & Eldar 2013 Definition 2.3). Thus, by (Beck & Eldar 2013 Lemma 2.2), x" IS HT-stable point if and only if x" (x - >Vx(x*)) The notion of a HTT-usttblle stationary point is novel and a key point for proving Theorem 2. Theorem is the foundation for the proof of part b) of Theorem 3 as well as Theorem 4 which characterizes the accumulation point of the IHT sequence. In addition, we have introduced another stationary point, namely strictly HT-stable stationary which is crucial concept for local convergence of the IHT sequence.
In the following, we present a result that characterizes a HT-unstable stationary point. essence, the following result shows that there always exists neighborhood around sparse HT-unstable stationary point whose gradient zero over the nonzero elements and one can decrease the function value by going towards the direction of any nonzero coordinates.
Theorem 2. Suppose f R." -> R is C² and I. -SS. Given any 0 <T +,, if vector x & C. f())
such that supp(5) f (*x
and min ([žg]: E IX) < 7IV (supp(8))= f llo. for some IV then
there exist a constant v > and a neighborhood N of such that f(y) S f(x) 1/ for any x E N i C, and any H. - f
The above result leads to the following necessary optimality conditions for global minimizer of Problem ( in terms of hard thresholding operator H., For the case where 7 = 1/LL, i.c.. part b), one needs to use Theorem Indeed, to the best of our knowledge, no proof has not been found for in the literature. Essentially, establishing the result in part b) is one of our contributions. For the < I/L, it is proven that x* (x (x*(x*)), Note that the condition for 0 < < I has been obtained in (Beck & Eldar 2013 Theorem 2.2) without using gradient properties of the HT operator.

---

Under review as a conference paper at ICLR 2023
Theorem 3. Suppose f IR" is Lg RSS and x" is global minimizer. Then, x" is a HT-sttable (or - stationary point for any < $ L. Particularly, the following hold:
For any <9 L. x" H2(x" - -Vf(xx)).
For 7
T- = -, x* H2(x -V/[<")](**)
The following result shows that any accumulation point of an IHT sequence must be HT-stable stationary point.
Theorem 4. Let f RR R be Lg-RSS and C' function. Suppose f is bounded below on C..
Consider an IHT sequence (x*) k20 associated with an arbitrary E (0, Ž,}. and let x" be an
accumulation point of (x*) k20' Then, x" is a HT-stable stationary point of Problem (2).
The above theorem shows that any accumulation point of an IHT sequence is HT-sttble stationary point of Problem (2). Since each HT-stable stationary point must be a basic stationary point, one can observe that any accumulating point x" of an IHT sequence must satisfy V supp(())) fxx"
Remark 3.
when xx lo or V f(x") = O when ||x" llo 8.
The following result pertains to the objective function values of HT-stable and HT-unstable stationary points.
Corollary 4. Let f: R - R be I.-RSS and C function. Suppose that every (nonempty) sub-level set of f contained in C. is bounded, i.e., for any a R. {I Czlf(x) a} is bounded (and closed). Consider an arbitrary 7 E (0, T. For any HT-unstable stationary point x" associated with 7, there exists HT-stable stationary point X* associated with y such that f(x*) f(x*).
Based on the above corollary, easy to see that if there are finitely many HT-unstable stationary points (happens when the function is RSC), then there is HT-stable stationary point x such that f(x*) f(x)) for any HT-unstable stationary pointx" x".
The following result provides sufficient conditions for the convergence of an IHT sequence. Corollary aims to remove any restrictions on the initial condition. This corollary shows that no matter what iniiil condition in C, is selected, the IHT sequence will converge
HT-stable stationary point. Note that we say a #TTsttable/unstablle stationary point x" associated with y E (0, + isolated there exists a neighborhood, N of x" such that N does not contain any HT stationary point other than x"
Corollary 5. Let ; R" + +R be R.- and C function. Suppose that every (nonempty) sub-level set of f contained in C2 is bounded. Consider an arbitrary 7 E (0, ł.1. Assume that
A.1 For any two distinct HT-stable stationary points x" and y" associated with 7, f(x") + f(y"). Then, for any x² E Cs, the IHT sequence (x** (x*)220 k20 converges to HT-stable stationary point associated with ry. This convergence results also hold under the following assumption:
A.2 when 0 <T<< +., each HT-stable stationary point associated with 7y isolated.
The following corollary shows that any IHT sequence always "escape" from HTT-unstable stationary point.
Corollary 6. Let f: I= R be L L.- and C' function. Suppose f is bounded below on C.. For any given 7 E (0, 1.] and any HT-unsiable stationary point x" associated with there exists neighborhood N of x" such that for any IHT sequence starting from any x" E C., there exists N E N such that x & N.CC, all k 2 N.
The next result shows the attraction towards a strictly HT-stable stationary point in a neighborhood of such a stationary point. In what follows, for each index subset I with |J| = subspace SJ := {x T xz=} associated with I is defined. Clearly, C, the union of Sy's for all I's
with J s. Proposition 1. f :: Ra + R. be L, and C¹ function. Suppose f is bounded below on C, and f is strictly convex on 3 for any index subset J with [J] Let x" be strictly HT-stable
7

---

Under review as a conference paper at ICLR 2023
stationary point associated with any given y E (0, 1. Then there exists neighborhood B of x" such that for every x" E n C., the IHT sequence (x*)>0 converges to x". Moreover, if is strongly convex I for every index subset I with [J] 8, then x E BB CCC, the IHT sequence (x*) k20 Q-linearly converges to x*.
Next, we provide an example to show the escapability property of HT-unstable points.
SIMULATION
To elaborate on theoretical results including Corollary Theorem 2 the notion of HT-stationary points, Corollary which shows escapability property HT-uustable stationary points, and Propo- sition which shows Reachability to HT-stable stationary points, we use a quadratic function fxx mp 2i=1
-| m || bl1² where A Rmxx" Aie is the i-th row of A, IK" is the optimization variable, and y E 1 is the target. This function is both RSS and RSC so both 6 and Proposition Mactiioonoool follow. To better visualize the process, we let m
and Therefore, there are six #TT-statonarry points where the gradient over the nonzero elements is zero. We use Pytorch (Paszke et al. 2019) to select the matrix A and y. By setting the random seed be 45966 we draw a 4 x 4 matrix A whose elements are standard normal. Keeping the same seed, we generate y. The following would be A and y:
Corollary
1.0655
0.2249
-0.0897
0.1876
1.7861
1.1627
-..1229
-0.0823
-0.3059
-0.3556 y
A =
0.2011
0.5342
-0.0551
-1.3459
,
-0.188
0. 0.2308
-0.6404
-0.7468
0.0378
0.3896
The restricted Lipschitz constant, i.c.. L.. for the above quadratic function 2 X Amar (AT m where Amaz is the maximum eigenvalue of A Thus, for the above choice of y, the maximum allowable stepsize is 7 t. 0.06. Once, y is fixed, one determine stability of each stationary HT ata-statinaay points along with their stability status well as the gradient status of each HT sttstaaionyry point. As you can see, the gradient corresponding to nonzero elements in HT-stationary point are zero:
point. The following
Noo
I2
23
91
92
93
94
HT stability
1.3474
1.0331
0
0.2060
-03916
strictly HT-stable
2
0.6278
0
0.0177
0
0
-0.3843
0
-0.1070
HT-unstable
0.6387
0
0.1123
0
-0.4199
-0.0029
0
strictly HT-stable
4
0
-0.1758
0.0008
0
0.6506
0
0.0106
HT-unstable
5
0
00.776
0.0013
0.6473
0
-0.0010
0
HTT-unstable
0
0
-0.1608
0.0259
0.7994
0.1297
0
HT-unstable
where Ti, 22, TA four coordinates of each HT-stationary point and where 91 92-92. 93, 91 the four gradient entries corresponding to each HT-stationary point. Since HT-stationary points are vectors in Rdd, there is no way show all of them where each plane shows only two coordinates of HT--statioaayy points. On each 2-d plain we have different points, each one associated with one of the HT HT-stationary points shown in particular 2-d plain with specified coordinates. In Figure the points with red stars are I/T-unstable ones, and the blue ones are the //T-stable ones. For example, the first 2-d plain (first row-first column) including coordinates
2-d plane. Thus,
six 2-d plains
I2 shows the æ1. By coordinates of all of the six HT-stationary points. On the first row-first column 2-d plain, the first HT-stationary point is more distinct because is the only one that has two nonzeros elements associated with with 22 = 0, two of which are HT-unstable points and one is HTT-unstable one. This more clear, one looks at the column 22 in HT-stationary points matrix above. Also, is clear that we have three HT-unstable points with xi = on the first 2-d plane.
#2 coordinates. We also can see three points
We perturb nonzero coordinates of all H/T points with normal random noise with mean zero and standard deviation of a = 0.5 to create 4,000 different initialization points. These points create four clouds around HT-umstable points which are shown in Figure 2 Then for 400 steps. After 300 steps, all of these initializations escape from those HT-unstable points and converge to either of the HT-stable stationary points on Φ1 22 æ 34 2-d planes. In fact, these
the IHT algorithm
8

---

Under review as a conference paper at ICLR 2023
X2
Ag
X3 X4
N1 A1
X1 X4
X2
X4
X5
X4
X4
Xg
Figure 1: Illustration of HT-stationary points on 2-d plains.
Figure 2: Illustration 4,000 initialization close to four HT-unstable stationary points.
X2
X
Figure Illustration 4,000 IHT sequenees initialized close to four HT-unstable stationary points after 400 steps (please refer to the vidco of all 400 steps).
two HT-stable stationary points are sparse local minimizers. 3 shows the 300-th step of IHT algorithm. There is video in the supplementary materials that shows 400 steps of applying IHT algorithm for 4,000 different runs. These numerical results corroborate our theoretical results as expected. By looking at the video, one can easily see escapability property of //T-unstable stationary points, and Reachability to HTT-stable stationary points.
CONCLUSION
This paper provide theoretical results that help to understand the IHT algorithm. These theoretical results include a critical gradient descent property of the hard thresholding (HT) operator which is used to show the sequence of the IHT algorithm is decreasing and by doing over and over get smaller objective value. This property also allows one to study the IHT algorithm when the stepsize is less than equal 1/L,, where I., is the Lipschitz constant of the gradient of an objective function. We introduced different stationary points including HT-stable and HTT-unstable stationary points and show no matter how close initialization is a HT-uustable stationary point, the IHT sequence leaves it. We provided a video of 4000 independent runs where the IHT algorithm initialized very close a HT-unstable stationary point and showed the sequences escape them. This property is used to prove that the IHT sequence converges to a HT-stable stationary point. Also, we established a condition for HT-stable stationary that a global minimizer with respect to 7 1/T., Finally, we showed the IHT sequence always converges if the function values of H'T-stable stationary points are distinct, this a new assumption that has not been found in the literature.
9

---

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(Ma1):807-841, 2013.
Heinz H Bauschke, D Russell Luke, Hung M Phan, and Xianfu Wang. Restricted normal cones and sparsity optimization with affine constraints. Foundations Computational Mathematics, 14(1): 63-83, 2014.
Amir Beck and Yonina C Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on Optimization, 23(3): 1480-1099-1 2013.
Amir Beck and Nadav Hallak. On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms. Mathematics of Operations Rexearch, 41(1):196-225 2016.
Thomas Blumensath. Accelerated iterative hard thresholding. Signal Processing, 92(3):752-756. 2012.
Thomas Blumensath and Mike E Davies. Iterative thresholding for sparse approximations. Journal of Fourier analysis and Applications, 14(5):629-653) 2008
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 27(3):265-277 274, 2009.
Sébastien Bourguignon, Jordan Ninin, Hervé Carfantan, and Marcel Mongeau. Exact sparse approxi- mation problems via mixed-integer programming: Formulations and computational performance. IEEE Transactions on Signal Processing, 64(6))1405-1419 2015.
Joshua Brodie, Ingrid Daubechies, Christine De Mol, Domenico Giannone, and Ignace Loris. Sparse and stable markowitz portfolios. Proceedings of the National Academy of Sciences, 106(30): 12267-12272, 2009.
Max Bucher and Alexandra Schwartz. Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems. Journal of Optimization Theory and Applications, 178(2):383-410, 2018.
Oleg P Burdakov, Christian Kanzow, and Alexandra Schwartz. Mathematical programs with cardinal-
ity constraints: reformulation by complementarity -typ conditions and regularization method. SIAM Journal on Optimizatioon, 26(1):397-425, 2016.
T-J Chang, Nigel Meade, John E Beasley, and Yazid M Sharaiha. Heuristics for cardinality constrained portfolio optimisation. Computers & Operations Research, 27(13)11211-130, 2000.
Rick Chartrand. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters, 14(10):707-71, 2007.
Jinghui Chen and Quanquan Gu. Accelerated stochastic block coordinate gradient descent for sparsity constrained nonconvex optimization. In UAI, 2016.
Hyonho Chun and Sündüz Keleş. Sparse partial least squares regression for simultaneous dimension reduction and variable selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(1):3-25. 2010.
Saeed Damadi, Erfan Nouri, and Hamed Pirsiavash. Amenable sparse network investigator. arXiv preprint arXiv:2202.09284 2022.
Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 10(4):608-622 2016.
Geoffrey Mark Davis. Adaptive nonlinear approximations. PhD thesis, New York University, 1994.
Antoine Dedieu, Hussein Hazimeh, and Rahul Mazumder. Learning sparse classifiers: Continuous and mixed integer optimization perspectives. Journal of Machine Learning Research, 22(135): 1-47, 2021.
10

---

Under review as a conference paper at ICLR 2023
Loann David Denis Desboulets. A review variable selection in regression analysis. Econometrics, 6(4):45, 2018.
David L Donoho, Yaakov Tsaig, Iddo Drori, and Jean-Luc Starck. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit. IEEE transactions Information Theory, 58(2):0094-112) 2012.
Yonina C Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 138456):1348-136) 2001.
Massimo Fornasier, Holger Rauhut, and Rachel Ward. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal on Optimization, 2144):111--1640, 2011.
Simon Foucart and Ming-Jun Lai. Sparsest solutions of underdeterminnd linear systems via 6g- minimization for 0 < q S 1. Applied and Computational Harmonic Analysis, 26(3):395 407,
2009.
Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sensing. pp. 1-39. Springer, 2013.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint (CCiv:9902.0955 2019.
Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing. In International conference machine learning, pp. 2007-2015. PMLR, 2014.
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 Intelliencce and Staristics, pp. 188-198. PMLR, 2018.
Ming-Jun Lai and Jingyue Wang. An unconstrained b, minimization with 0 < << 1 for sparse solution of underdetermined linear systems. SIAM Journal Optimization, 21(1):82-101 2011.
Xingguo Li, Raman Arora, Han Liu, Jarvis Haupt, and Tuo Zhao. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint 1OXiv:1605.022 2016.
Xue Li and Wen Song. The first-order necessary conditions for sparsity constrained optimization. Journal of the Operations Research Society of China, 3(4):521 -535, 2015.
Guannan Liang, Qianqian Tong, Chunjiang Zhu, and Jinbo Bi. An effective hard thresholding method based on stochastie 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 Machine Learning, pp. 2179-2187. PMLR, 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-923 2020.
Zhaosong Lu. Iterative hard thresholding methods for ly regularized convex cone programming. Mathematical Programming, 147(1): 2014.
Zhaosong Lu. Optimization over sparse symmetric sets via nonmonotone projected gradient method.
arXiv: Optimization and Control, 2015.
Stéphane G Mallat and Zhifeng Zhang. Matching pursuits with time-frequency dictionaries. lEEE Transactions signal processing, 41(12)3337-3415, 1993.
11

---

Under review as a conference paper at ICLR 2023
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In International Conference on Machine Learning, PP. 2498-2507. PMLR, 2017.
Jorge J. Moré and D. C. Sorensen. Computing a trust region step. SIAM Journal on Scientific and Statistical Computing, 4(3):553-572, 1983.
Seyedahmad Mousavi and Jinglai Shen. Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained l minimization. ESAIM: Control, Optimisa- fion and Calculus of Variations, 25:56, 2019.
Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal computing, 24(2):227-25 234, 1995.
Deanna Needell and Joel A Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and computational harmonic analysis, 26(3):301-33) 2009.
Deanna Needell and Roman Vershynin. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Foundations of computational mathematics, 9(3)3117 334, 2009.
Deanna Needell and Roman Vershynin. Signal recovery from incomplete and inaccurate measure- ments via regularized orthogonal matching pursuit. IEEE Journal of selected topics in signal processing, 4(2):310-316, 2010.
Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. A unified framework for high- nigh-dimensiioal analysis of m-estimators with decomposable regularizers. Statistical science, 27(4):538- 557, 2012.
Li-Li Pan, Nai-Hua Xiu, and Cheng-Long Zhou. On solutions of sparsity constrained optimization. Journal of the Operations Research Society of China, 3(4):421 1499, 2015.
LiLi Pan, NaiHua Xiu, and Jun Fan. Optimality conditions for sparse nonlinear programming. Science China Mathematics, 60(5):759-776, 2017a.
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, 2017b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint 19Xivv1912.00
2019.
Yagyensh Chandra Pati, Ramin Rezaiffar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pp. 40-44. IEBE, 1993.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Trung Vu and Raviv Raich. Accelerating iterative hard thresholding for low-rank matrix completion via adaptive restart. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2917-2921. IEEE, 2019.
Meng Wang, Weiyu Xu, and Ao Tang. On the performance of sparse recovery via e,- miniiiiiiottion < & 1. IEEE Transactions on Information Theory, 57(1) 1):7555-7278, 2011.
Rui Wang. Naihua Xiu, and Shenglong Zhou. Fast newton method for sparse logistic regression. arXiv, (1901.02763) 2019.
Joong-Ho Won, Kenneth Lange, and Jason Xu. A unified analysis of convex and non-convex Ip-ball projection problems. arXiv preprint arXiv:2203.00566 2022.
Fan Wu and Wei Bian. Accelerated iterative hard thresholding algorithm for lo regularized regression problem. Journal of Global Optimization, 76(4))819-840, 2020.
12

---

Under review as a conference paper at ICLR 2023
Chen Zhao, Naihua Xiu, Houduo Qi, and Ziyan Luo. A lagrange newton algorithm for sparse nonlinear programming. Mathematical Programming, pp. 1-26, 2021.
Le Zheng, Arian Maleki, Haolei Weng, Xiaodong Wang, and Teng Long. Does éy-minimization outperform E--minimization? IEEE Transactions on Information Theory, 63(11))686666935, 2017.
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 le-regularized 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(12):1-45, 2021.
Wenxing Zhu, Zhengshan Dong, Yuanlong Yu, and Jianli Chen. Lagrange dual method for sparsity constrained optimization. IEEE Access, 6:28404-28416, 2018.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2):301-320, 2005.
13


Reviews:
[{"review_id": "gF0i4l6MmA", "reviewer": "Reviewer_kzNB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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 paper studies the stability properties of the hard thresholding operator in gradient descent framework and introduces several new concepts such as HT-stable and HT-unstable stationary points. Moreover, the paper aims to answer four fundamental questions regarding the local/global minimizers and accumulation points of a sparse recovery problem. In the numerical experiments, the authors intend to use some synthetic data sets to justify the proposed theoretical results. However, the paper has limited novelty and lacks real data experiments from applications. ", "summary_of_the_review": "Although the paper proposes some new theories for discussing the gradient properties of hard-thresholding operators, the novelty and application outreach are limited. ", "strength_and_weaknesses": "Strengths: \n1. The paper has attempted to dig out theoretical properties of a classical hard-thresholding operator with some theoretical results. \n2. The new concepts - HT-stable/HT-unstable stationary points - may be useful for other related discussions or studies.\n3. The simulation results verified the proposed theories. \n\nWeaknesses:\n1. There are some minor language issues, and some statements are confusing.\n2. It is not clear how the new concepts are valid and could be used for other studies.\n3. The simulation section is not clearly organized. Since the data matrix is randomly generated, it would be great to check the average performance after many trials. No real applications are involved which would limit the applicability of theories. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XOhN5we0Sxy", "reviewer": "Reviewer_raL8", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This work studies the well known iterative hard thresholding (IHT) algorithm for sparse optimization. The algorithm works as follows: In each iteration of this algorithm, a gradient step is taken, and then the hard thresholding operator is applied, which restricts the solution vector to its top $s$ entries in absolute value. The results of the paper are convergence properties for smooth functions. Specifically, the authors prove that the algorithm converges to a stationary fixed point and characterize the properties of such fixed point. ", "summary_of_the_review": "In summary, the theoretical analysis is sound but I have concerns over its novelty that are not addressed by the manuscript. Therefore I cannot recommend acceptance until the contribution of this paper with respect to previous work is clearer.", "strength_and_weaknesses": "Strengths:\n- The theoretical analysis is sound.\n- The results are presented in a clear and intuitive way.\n- A numerical simulation of the IHT algorithm is presented.\n\nWeaknesses:\n- My main concern is novelty, which I will explain more about in the next section.\n- The numerical simulation only consists of one random linear regression instance. It would be better to have an analysis multiple instances in order to account for the variance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SJhnD4Y6dxF", "reviewer": "Reviewer_F4td", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "In this paper, the authors study the extensively-studied iterative hard thresholding (IHT) algorithm. They establish a new and critical gradient descent property of the hard thresholding (HT) operator, which is related to the distance between sparse points. In addition, they introduce the notion of HT-stable/unstable stationary points, and establish the escapability property of HT-unstable stationary points and the local reachability property of strictly HT-stable stationary points. Moreover, they show that the IHT sequence converges globally under the assumption that the function values at HT-stable stationary points are distinct. Such an assumption is novel and has not been found in the literature. Finally, some simple simulation results are provided for synthetic data.", "summary_of_the_review": "It is nice to see some new technical results for the iterative hard thresholding (IHT) algorithm. But it is a pity that from the current submission, I cannot see how meaningful/interesting these new results/assumptions are to the machine learning community. \n\nFrom the current submission, my impression is that this is a pure optimization paper, and is better submitted to an optimization journal, rather than a machine learning conference. ", "strength_and_weaknesses": "Strength:\n\nThis paper seems to be technically sound.\n\nWeaknesses:\n\nThis seems to be a pure optimation paper. For example, almost all the closely relevant papers listed in Table 1 are published in optimization journals. In addition, the simulation results are weak and rather limited, and are not related to any practical machine learning/deep learning tasks. \n\nThe authors mention in the abstract that \"the IHT sequence converges if the function values at HT-stable stationary points are distinct, where the last condition is a new assumption that has not been found in the literature\". But from this paper, I cannot see how impactful/meaningful will this new assumption be. \n\nSome minor comments:\n\nIn the abstract, using latex notation of the Lipschitz constant $L$.\n\nWrite down the full name of RSS when it first appears on page 3.\n\nClaim 1 may be better written in ordinary text as it is a very simple and widely-used property, instead of highlighting it as a separate claim.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1Z4OO4L4ExZ", "reviewer": "Reviewer_BYNJ", "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": "This paper presents a set of descent and optimality properties for the gradient hard-thresholding (GHT) operator widely used in sparse optimization algorithms such as iterative hard-thresholding. Regarding the descent property, the authors establish in Theorem 1 a gradient-norm descent property of GHT for restricted strongly smooth objectives. In terms of the optimality property, the authors mainly show in Theorem 2&3 that the HT-stability condition (as defined in Definition 4) is necessary for a global sparse minimizer, and for any accumulation point of an IHT sequence as well. A simulation study on sparsity recovery with quadratic loss is carried out to verify the theoretical predictions.", "summary_of_the_review": "Based on the above comments, it is assessed that this paper in the current form is not strong enough to be published. ", "strength_and_weaknesses": "# Strength:\n\n 1. The main theoretical claims made in this paper are correct and mathematically sound.\n \n2. The paper is in general well organized and the technical details are clearly presented .\n\n\n# Weaknesses\n\n1. The motivation behind this study looks not clear enough. The theoretical properties proved in the current work are fairly standard, and as admitted by the authors are well-addressed in the previous analysis of iterative hard-thresholding. I cannot see any particular reason why the present study about proving these prior results would be of any benefit for advancing the related lines of research. \n\n2. The technical novelty of the main results is quite limited. More specifically, the gradient-norm descent property as summarized in Theorem 1 has already been developed in the proof of Jain et al. (2014, Theorem 1). With regard to the stability of hard-thresholding, some results identical to Theorem 2&3 have been established by Beck and Eldar (2013), and Yuan et al. (2014, Lemma 21)\n\n\n# References:\n\nP. Jain, A. Tewari, and P. Kar. On iterative hard thresholding methods for high-dimensional m-estimation. NIPS, 2014.\n\nA. Beck and Y. C Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIOPT, 2013.\n\nX. Yuan, P. Li and T. Zhang, Gradient Hard Thresholding Pursuit, JMLR, 2014.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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