Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
Authors: William de Vazelhes
Xiaotong Yuan
Bin Gu
Venue: ICML 2025 poster (2025)
Keywords: optimization
sparse optimization
iterative hard-thresholding
three-point lemma
approximate global guarantees
projected gradient descent
stochastic gradient descent
zeroth-order
Primary area: optimization
TL;DR: We simplify and extend convergence proofs for Iterative Hard-Thresholding using a non-convex three-point lemma, improving existing results in standard settings and providing new results under additional constraints.

Abstract: In sparse optimization,  enforcing hard constraints using the $\ell_0$ pseudo-norm offers advantages like controlled sparsity compared to convex relaxations. However, many real-world applications demand not only sparsity constraints but also some extra constraints. While prior algorithms have been developed to address this complex scenario with mixed combinatorial and convex constraints, they typically require the closed form projection onto the mixed constraints which might not exist, and/or only provide local guarantees of convergence which is different from the global guarantees commonly sought in sparse optimization. To fill this gap, in this paper, we study the problem of sparse optimization with extra *support-preserving* constraints commonly encountered in the literature. We present a new variant of iterative hard-thresholding algorithm equipped with a two-step consecutive projection operator customized for these mixed constraints,  serving as a simple alternative to the Euclidean projection onto the mixed constraint. By introducing a novel trade-off between sparsity relaxation and sub-optimality, we provide global guarantees in objective value for the output of our algorithm, in the deterministic, stochastic, and zeroth-order settings, under the conventional restricted strong-convexity/smoothness assumptions.  As a fundamental contribution in  proof techniques, we develop a novel extension of the classic three-point lemma to the considered two-step non-convex projection operator, which allows us to analyze the convergence in objective value in an elegant way that has not been possible with existing techniques. In the zeroth-order case, such technique also improves upon the state-of-the-art result from de Vazelhes et. al. (2022), even in the case without additional constraints, by allowing us to remove a non-vanishing system error present in their work.

Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
William de Vazelhes
Xiao-Tong Yuan 2
Bin Gu
Abstract
niques. In the zeroth-order case, such technique also improves upon the state-of-the art result from (de Vazelhes et al., 2022), even in the case without additional constraints, by allowing us to remove a non-vanishing system error present in their work.
In sparse optimization, enforcing hard constraints using the lo pseudo-norm offers advantages like controlled sparsity compared to convex relax- ations. However, many real-world applications demand not only sparsity constraints but also some extra constraints. While prior algorithms have been developed address this complex sce- nario with mixed combinatorial and convex con- straints, they typically require the closed form pro- jection onto the mixed constraints which might not exist, and/or only provide local guarantees of convergence which is different from the global guarantees commonly sought in sparse optimiza- tion. To fill this gap. in this paper, study the problem of sparse optimization with extra support-preserving constraints commonly encoun- tered in the literature. We present a new variant of iterative hard-thresholding algorithm equipped with a two-step consecutive projection operator customized for these mixed constraints, serving as simple alternative to the Euclidean projec- tion onto the mixed constraint. By introducing a novel trade-off between sparsity relaxation and sub-optimality, we provide global guarantees in objective value for the output of our algorithm, in the deterministic, stochastic, and zeroth- settings, under the conventional restricted strong- convexity/mmoothness assumptions. As a funda- mental contribution in proof techniques, we de- velop novel extension of the classic three-point lemma to the considered two-step non-convex projection operator, which allows us to analyze the convergence in objective value in an elegant way that has not been possible with existing tech-
1. Introduction
In sparse optimization, directly enforcing sparsity with the to pscudo-norm has several advantages over its convex re- laxation counterpart. In compressive sensing for instance (Foucart & Rauhut, 2013), one may seek to recover an un- known vector, which sparsity level is known to be most k. Similarly, in portfolio optimization, due to transaction costs, one may seek to ensure hard constraints on the maximum number of assets invested in (Brodic et al., 2009; DeMiguel et al., 2009). However, in several use cases, one may also seek to enforce additional constraints, such as, for instance, budget constraint in the case of portfolio optimization, which can be enforced through an extra E constraint, in Takeda al. (2013). As another example, in sparse non- negative matrix factorization, when estimating the hidden components, one seeks to enforce at the same time a norm constraint and a sparsity constraint (Hoyer, 2002). The problem of by empirical risk minimization (ERM) with ad- ditional constraints can be formulated as follows, where is an empirical risk function, I' S Rd denotes a convex con- straint set, and || llu denotes the to pseudo-norm (number of non-zero components of vector):
min R(w), s.t. ||w||o I k and w E T. WERP
(1)
We assume throughout this paper that Problem (1) is well- posed, with R being bounded from below and the set of minimizers being non-empty. In the literature, several algo- rithms have been developed to address such a problem with mixed constraints, but they typically require the existence of closed form for the projection onto the mixed constraint, and/or their convergence guarantees are only local, which makes it difficult to estimate the sub-optimality of the output of the algorithm. More precisely, on one hand, some works provide convergence analyses for variants of non-cconvex projected gradient descent, explicitly for mixed sparse con- straints (Metel, 2023; Pan et al., 2017; Lu, 2015; Beck &
'GenBio AI, work done while at MBZUAI, Abu Dhabi, UAE "School of Intelligence Science and Technology, Nanjing University, Suzhou, China "School of Artificial Intelligence, Jilin University. China. Correspondence to: Xiao-Tong Yuan extyuan@nju.cdu.co >, Bin Gu <jsgubin gomi
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimization over Sparse Support-Preserving Sets:
Two-Step Projection
Hallak, 2016), or for general proximal terms (which encom- passes our mixed constraints) (Frankel et al., 2014; Xu et al., 2019b; Attouch et al., 2013; De Marchi & Themelis, 2022; Yang & Yu, 2020; Gu et al., 2018; Yang & Li. 2023; Bolte et al., 2014; Bog et al., 2016; Xu et al., 2019a; Li & Lin, 2015; Bauschke et al., 2017; 2019), but such analyses are only local. On the other hand, several existing works on Iterative Hard Thresholding (IHT) provide global guaran- tees on sub-optimality gap (Jain al., 2014; Nguyen al., 2017; Li et al., 2016; Shen & Li, 2017; de Vazelhes et al., 2022), but they do not apply to the mixed constraint case we consider. In between the two approaches, one can also find (Foygel Barber& & Ha, 2018) and (Liu & Foygel Barber, 2020) which, in the deterministic case, give global guar- antees for general non-convex constraints or thresholding operators, but which do not provide explicit convergence guarantees for the particular mixed constraint setting that we consider: their rates depend on some constants (the relative concavity or the local concavity constant) for which, up to our knowledge, an explicit form is still unknown for the mixed constraints we consider. We present a more detailed review of related works in Appendix B, and an overview of them in Table 1, To fill this gap, we focus on solving problem 1 in the case where I' belongs to a general family of
light a compromise between sparsity and sub-optimality gap specifie to the additional constraints setting: through a free parameter p. one can obtain smaller upper bounds in terms of risk but at the cost of relaxing further the sparsity level of the iterates, or, alternatively, enforce sparser iterates but at the cost of a larger upper bound on the risk.
Contributions. We summarize the main contributions of our paper as follows:
1. We present a variant of IHT to solve hard sparsity prob- lems with additional ing a novel two-step projection operator.
constraints, us-
2. We describe a novel extension of the three-point lemma to such constraint which allows to simplify existing proofs for IHT and provide global convergence guarantees in objective value without system error for the algorithm above, in the RSC/RSS setting, highlighting novel trade- off between sparsity of iterates and sub-optimality gap in such mixed constraints setting.
3. We extend the above algorithm to the stochastic and zeroth-order optimization settings, obtaining similar global optimality guarantees in objective value (without system error) for such mixed constraints setting. In the zeroth-order case, this also provides, up our knowledge, the first convergence result in objective value without sys- tem error for a zeroth-order shrrddtheesolddngg algorithm (with or without extra constraints).
sets, which encompasses many usual sets encountered in the literature. As will be described in more detail in Section 2, such sets are convex sets for which the projection of a s-sprse vector onto them gets its support preserved, such as for instance lp norm balls (for p 2 1), or a broader family of sign-free convex sets deseribed for instance in (Lu, 2015) and (Beck& & Hallak, 2016).
2. Preliminaries
Throughout this paper, we adopt the following notations.
For any E Rd, I1r(w) denotes Euclidean projection of w onto I, that is Ir E arg minzer w| - = =112, and wy denotes the i-th component of w. (k) denotes the 4 pseudo-ball of radius k, i.e. (b) = { (w E R : ||0o|lo I k.,, with ||. llo the to pseudo-norm (i.e. the number of non- zero components of a vector). H4 denotes the Euclidean projection onto (k),, also known as the hard-thresholding operator (which keeps the k largest (in magnitude) com- ponents of vector, and sets the others to 0 (if there are ties, we can break them e.g. lexicographically). || IIp denotes the Ep norm for E (o,) and || || the &z norm (unless otherwise specified). [m] denotes the set {1,..., n} for n E N For any S [ [d]. |S|| denotes its number of elements. For any w E Rd. supp(w) denotes its support, i.c. the set of coordinates of its non-zero components. We also introduce below the usual assumptions on R for IHT proofs, i.e. RSC (Jain et al., 2014; Negahban et al., 2009; Loh & Wainwright, 2013; Yuan et al., 2017; Li et al., 2016; Shen & Li, 2017; Nguyen et al., 2017), and RSS (Jain et al., 2014; Li et al., 2016; Yuan et al., 2017).
Adapted to the properties of such constraints, we propose a new variant of IHT, with a two-step projection operator, which, as a first step, identifies the set S of coordinates of the top At components of a given vector and sets the other components 0 (hard- theehoodrsh..,, and as sec- ond step projects the resulting vector onto I. This two-step projection can offer simpler alternative to Euclidean pro- jection onto the mixed constraint in the cases where there is a closed form for the latter projection, and handle the cases where there is not. We then provide global sub-optimality guarantees without system eтror for the objective value, for such an algorithm as well as its stochastic and zeroth-order variants, under the restricted strong-convexity (RSC) and restricted smoothness (RSS) assumptions, in Theorems 3.7, 4.3, and 4.8. Key to our analysis is novel extension of the three-pont point lemma to such non-convex setting with mixed constraints, which also allows, as byproduct, to simplify existing proofs of convergence in objective value for IHT and its variants. In the zeroth-order case, such technique also allows to obtain, up to our knowledge, the first conver- gence in risk result without system error for zeroth-order hurd-thresholding algorithm. Additionally, our results high-
Assumption 2.1 ((2,, RSC). R is v. restricted strongly convex with sparsity parameter s, ie. is differentiable, and there exists a generic constant 2s such that for all (æz, y) e
2

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Table 1. Comparison of results for Iterative Hard Thresholding with/without additional constraints. 8: symmetric convex sets being sign-fro free or non non-eegative (Lu, 2015), A:: sets verifying Definition 2.3. 2 If a paper reports both ||w w and R(w) R(w), we report only the latter. T: time index of the returned by the method (e.g. T arg minte '7) R(w)) ). w: k-sparse vector in r. A: System error (non-vanishing term which depends on the gradient at optimality (e.g. V.I I[ (see corresponding references))). 4: K.a Le S: Stochastic, Z: Zeroth-Order,
and K2z بيل (cf. corresponding refs. for defs. of a and s'). SM: Lipschitz-smoothh D: Deterministic.
L: Lipschitz continuous. : see also Thm. 3.4, 9 see also Thm. 4.2. 4 Notably, could eliminate A from (de Vazelhes et al., 2022).
Reference
1
Convergence
k:
Setting²
D, RSS, RSC
(Jain et al., 2014)*
Rd
R(w;) S R(w) +E
S, RSS, RSC
(Nguyen et al., 2017)
Rd
B Blwwy- - w0 S & &
S, RSS, RSC
(Li et al., 2016)
Rd
ER(w)) S R(w) + + O(A)
(((2)))
S, RSS, RSC
(Zhou al., 2018)6
Rd
ER(w7) S R(w) +
(de Vazelhes et al., 2022) (Lu, 2015), (Beck & Hallak, 2016)
Z. RSS', RSC
Rd
Elwoy - w S + O(p) (A)
TES
local convergence
D, SM
loo ball
(Metel, 2023)
local convergence
S, Z, L
around (
D. RSS,
IHT-2SP (Thm. 3.7)
DE A
R (ww)) (1 (() +
Ω
RSC
HSG-HT-2SP (Thm. 4.3)
TEA
ER(w;) < (1 R(w) +
Ω
1ith
S. RSS,
RSC
Z, RSS',
HZO-HT (Thm. 4.7)
Rd
B[((w,) - R(w) S 5 0
2(x3,k)
RSC
HZO-HT-2SP (Thm.
Z. RSS',
TEA
BR(())) S + + +())
Ω
4.8)
RSC
Rd with ||æ vllo s: R(y) 2 +(x)+ + (VR(z), 2/
with S and u, 2 0.
5 or
Group-wise separable constraints where the constraint cach group is prreperr-preserving (such as con- straints in Appendix H for the index tracking problem). Sign-free convex sets (Lu, 2015; Beck & Hallak, 2016) (def. in App. D), c.g. by norm-balls.
Assumption 2.2 ((L,, RSS), R L, restricted smooth with sparsity level i.c. it is differentiable, and there exists a generic constant L, such that for all (xc y) E Rd with x y|1o S s: R(y) S R(x) + (VR(2), y x. x y/2
3. Deterministic Case
We then define the notion of support-preserviie will use throughout the paper. It essentially requires that projecting any k-sparse vector w onto I preserves its sup- port. That is, the convex constraint I' should be compatible with the sparsity level constraint ||w||o < k.
set that
3.1. Algorithm
Two-Step Projection. In all the algorithms of this paper, we will make use of a two-step projection operator (2SP), which is different in general from the usual Euclidean pro- jection (EP), in order to obtain, from an arbitrary vector w E Rd, a vector in w E (k) P. We consider such a 2SP instead of EP since it enables the derivation of vari- ant of three-point lemma (Lemma 3.6) which can handle our specific non-convex mixed constraints, and is key to obtaining the convergence analyses we present in Sections 3 and 4. In addition, the 2SP can be more intuitive and efficient to implement than EP (see App. G for more dis-
Definition 2.3 cessuppor-preeervvii set). r C Rdd k- support-pres prepoeritpeeeriingg.... i.e. is convex and for any w e Rdd such that ||o]|o k, supp(IIr (w)) C supp(w).
Remark 2.4. Below we present some examples of usual sets that also verify Definition 2.3 (see Appendix D) for proof of such statements):
Elementwise decomposable constraints, such as box con- straints of the form (w E Rd Vi E [d].4 S w; S w.).
3

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
for p E [1, +x) ), then the two-step projection is actu- ally the closed form of Euclidean projection onto the mixed constraint I' n Bo (k) (see Theorem 2.1 from (Lu, 2015)). Therefore, in such cases, Algorithm 1 is identical to a vanilla (non-convex) projected gradient descent algorithm (for which up to now there was still no global optimality guarantees in such mixed constraints setting in the litera- ture).
r
Hz (w)
(w))
3.2. Convergence Analysis
Before proceeding with the convergence analysis, we first present below a variant of the usual three-point lemma from constrained convex optimization, which plays key role in our proofs. The common three-point lemma for a projection onto a convex set & relates the distance be- tween a point w E Rd, its projection IIg [ww) and any vector v from the set E, through the relation || - z | 2 - w012 Such a three-point lemma is used for instance in a general Bregman divergence form to prove convergence of mirror descent for smooth functions in (Bubeck et al., 2015). Indeed, although proving the con- vergence of projected gradient descent in the non-smooth case only needs the non-expansivity of projection onto a convex set, the proof for the smooth case usually needs such a three-point lemma, which can be seen as a stronger ver- sion of non-expansivity. However, due to the non-convexity of the to pseudo-ball, the convex three-point lemma above does not hold. Fortunately, building upon Lemma 4.1 from (Liu & Foygel Barber, 2020), we can obtain three-point lemma for projection onto the Eo pseudo-ball ball.
Figure 1. Support--reserring set and two-step projection (d = = 1).
[e (w) w|| 2 |[[e (wn)
cussions about 2SP vs EP). The 2SP procedure, which we denote by IT/. is as follows: we first project w onto (k) through the hard-thresholding operator Hg. to obtain a k- sparse vector va = Hr Hx(w). Then, we project en onto r, to obtain a final vector ws (1x() where S supp(ux). Note that consequently, the obtained we is not necessarily the EP of onto (k) n r, that is, we do not neces- sarily have ws = II (()(()))( However, when I' is a k-support-preserving set, we have ws E (o(k) n'r (since, by definition of a --support-preservin set (Definition 2.3), supp(w:, (1)) S supp(wre) and hence ||o S ||v* llo I k), therefore each iteration remains feasible in the constraint. We illustrate such two-step projection Figure 1. We now present our full algorithm in the case where R is a deter- ministic function without further knowledge of its structure. It is similar to the usual (non-convex) projected gradient descent algorithm, that is, a gradient update step followed by a projection step, except that instead of projecting onto TnB,(k) (k)) using the Euclidean projection, we obtain a vector wP E T ' (k) through the two-step projection method described above. We describe the algorithm in Algorithm below.
Lemma 3.2 (fo three-point lemma, proof in App. E.1.2). Consider w, v E Rp with || < k. For any k S k, with
B = & k. it holds that: 1|H6 (uv) w |2 < | w 12
(1 VB) |e - -0|l2
Note that if > R, B + 0 and we approach the usual three- point lemma from convex optimization. This is coherent with the literature on IHT, in which relaxing sparsity (i.e. considering some k >>>>>>/, k) is known make the problem easier to solve (see also Remark 3.5 below). In addition, the inequality in Lemma 3.2 is tight with respect to the coefficient VB, as illustrated by the following lemma.
Algorithm 1: Deterministic IHT with extra constraints (IHT-2SP)
Lemma 3.3 (Tightness, proof in App. E.1.3). Consider an arbitrary pair of integers (k, k) with l. > ie and an arbitrary scalar E (0, 1). Then there exist w and w with || = and || = h such that the following holds: ||we Ha (w)] > w|w w 112 1|H4a (w)) will + PV [1 (w) - w|
Input:
Wo: initial value, my: learning rate, T: number of iterations
for f = to do
w. < I7 (w:-1 - V R(w::1)))
end
Output: WT
Lemma 3.2 allows us to prove the following rate for conver- gence in risk of IHT without system error, which appeared first in (Jain et al., 2014). Our proof, however, is simpler than the original proof from Jain et al. (2014), as we will
Remark 3.1. In the case where I' is a symmetric sign-free convex set (we refer to (Lu, 2015) for the definition of such sets, which include for instance any lp norm constraint set
4

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
discuss below.
(Peste al., 2021), even if Peste et al. (2021) assume R to have k-sparse minimizer which is strong requirement). The proof from (Jain et al., 2014) uses specific properties of the hard- hard-thresholding operator to carefully bound the magnitude of the components of V ())) on various sets of coordinates (the support of wt, W++1, and w. and some intersections and unions of such sets). Using such tech- niques, however, makes difficult to derive proofs of IHT in other settings (stochastic, zeroth-order, extra constraints). However, recently, Liu & Foygel Barber (2020) provided proof of convergence for IHT which avoids such com- plex considerations about the support sets of the gradient, using their Lemma 4.1 on the relative concavity of the hard- thresholding operator. Our work goes in a similar line of work, but we build upon their Lemma 4.1 to prove a three- point lemma for hard-thresholding (our Lemma 3.2) which allows us to obtain simple proof frameworks also for the stochastic case (retrieving the previous from (Zhou et al., 2018)) and the zeroth-order case (obtaining a new result). But perhaps more importantly, we are able to extend our Lemma 3.2 to the case with extra constraints verifying Definition 2.3 (Lemma 3.6 below). Such a lemma will allows us to obtain convergence results in the new extra constraints setting that we consider in this paper (provid- ing three new results, in the deterministic, stochastic, and zeroth-order case). It relates together the four points in- volved in the two step projection (w E Rdd, (wD) IT (w), and i E I'm Bo )
Theorem 3.4. (Equivalent to Thm. from (Jain et al., 2014), see also Thm. 3.1 from (Liu & Foygel Barber, 2020). Proof in App. E.2.1) Assume that r R.. Sup- pose that Assumption 2.1 and Assumption 2.2 hold, for 2k. Let 1) = L., Let in be an arbitrary k-sparse vec- for. Suppose that & 2 4rck with Nig := v.
1.. Then for any
E > 0, the iterate of IHT satisfies R(we)) & R(w) + if
t 2he log [I., v.lluo wIl ){ +1. 1.
2z
Proof Sketch. Using the L.-RSS of R and some algebraic manipulations, and denoting g: = V R()w;)) and vs := Hy(Wi-1 -. (= we when I' = ) we have:
La 11,, 1 + I. g 91-1
R(v,)= S 1(w--1) + _
(2)
119c-111
2T.
(a)
+ Lis
1 R(w)-1)
1100 - wi-1
+
g1- 1|-
(3)
2
L,
Le(1 -VB3)l1e - u8|2
1
|19--112
2
2L
(6)
S R(w)) + Lig - 1/2 |w:-1 -w0l² 20|2
(4)
L, (1 v Vb) w
(5)
2
Lemma 3.6 (Constrained Po-Three-Point, proof in App. E.1.4). Suppose that Definition 2.3 holds for a set r. Consider w. w E Rp with || llo S k and to E r. Then the following holds for any k > k:
where (a) follows from Lemma 3.2, and in (b) we used the RSC of R with some rearrangements. The proof for Theorem 3.4 can be concluded with telescopic sum argu- ments.
[
[0 (w) w012 < w
-wll2
|ILTT (w) w/
Remark 3.5 (Necessity of k= = ()kk²)). Note that the re- laxation of l to (2kkk) in Theorem 3.4 is unimprovable for IHT, as we detail in Appendix E.3 with a counter-example, similar to but slightly simpler than the counter example from Appendix 1 in (Axiotis & Sviridenko. 2022)). Therefore, we highlight that all of the following results in this paper will also be expressed in terms of such a relaxed k: this is fundamental limitation of IHT, and not a limitation of our proof techniques. More details on such relaxation (which is widespread amongst IHT- algorithms as can be seen in Table 1) and how it is natural way to obtain global guar- antees for sparsity enforcing algorithms, can be found in Liu & Foygel Barber (2020); Axiotis & Sviridenko (2021; 2022).
Te
3 H4 w with ,3
Equipped with such lemma, we can now present the conver- gence analysis of Algorithm 1 below, using the assumptions from Section 2, and we will describe how the results give rise to a trade-off between the sparsity of the iterates and the tightness of the sub-optimality bound, specific to our mixed constraints setting.
Theorem 3.7 (Proof in App. E.2.2). Suppose that Assump- tion 2.1 and 2.2 hold with = 2k, that R is non-negative (without loss of generality), and let I be a set verifying Definition 2.3 Let 1) 1. and w be an arbitrary k- sparse vector. Let p E (0, 2 be an arbitrary scalar. Sup- 4(1-0)²
L.
Comparison with Previous Proofs. Perhaps the origi- nal and most widespread proof framework for convergence in risk of IHT without system error is the one from (Jain et al., 2014) Theorem 1. Their proof framework is also used for instance in some stochastic extensions of IHT (see Theorem 2 in (Zhou et al., 2018), or Theorems and 2 in
pose that i 2 T Z LL log (L.-v.)) w00 6l
K. Then for any >> 0, for
p²u²
)1 + =O(x, log(t))
V.
2=(1-P) P)
the iterates of IHT-2SP satisfy:
min R (w:) S (1+ R()) + tE(T)
5

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Further, if is a global minimizer of R over Bu(k)
4.1.1. ALGORITHM
{w : I|wllo S k), then, with p = 0.5 in the expressions of k and I above: minuery R (we) S R(w) +e.
We describe the stochastic variant of our previous Algo- rithm 1 in Algorithm 2 below, which is an extension of the algorithm from (Zhou et al., 2018), to the considered mixed constraints problem setting, using our two-step pro- jection. More precisely, we approximate the gradient of I by a minibatch stochastic gradient with a batch-size increas- ing exponentially along training, and following the gradient step, we apply our two-step projection operator.
Proof Sketch. To obtain the proof for general I, we reiterate similar proof as for Theorem 3.4, but this time, instead of Lemma 3.2, we use our more general Lemma 3.6, adapted to general I' and to our two-step projection technique, to obtain (see the Proof Sketch of Thm. 3.4 for the definition of v.):
Lg V/a
Algorithm 2: Hybrid Stochastic IHT with Extra Con- straints (HSG-HT-2SP)
R(w,) S R(w)= +
Wt-1 -211
2
La wu 20|² 2
+ Lis
Input: wp: initial point, 7y: learning rate, T: number of iterations, {
11 - 211². B VBB 2
(6)
sizes.
for f. = 1 to T do
Finally, taking a convex combination of equations 2 p) and 6 (x(1 - p)) for E 0.5), using the bound ||w,; -
Uniformly sample st indices S, from [r]] replacement
without
wi S |/0 - uö| (non-expansiveness of convex projection onto I'), and carefully tuning & depending on p (resulting in our final trade-off between sparsity and optimality), we can fall back to telescopic sum and conclude the proof. IT
Compute the approximate gradient
1 Enes, V VR., (wi-1)
9:-1 F wT = (w 19t-1);
end Output: vp E arg min (we R(w)
Remark 3.8. Similarly to the work of (Jain et al., 2014), in the setting of linear regression with Lub-Gaussian design, use results from (Agarwal et al., 2010) to find the number of samples needed to verify the assumptions of Theorem 3.4. We provide such analysis in Appendix C. Remark 3.9. Theorem 3.7 therefore provides global con- vergence guarantee in objective value. However, contrary to usual guarantees for IHT algorithms under RSS/RSC condi- tions (which are bounds of the form R(w.) < R(w)= + e for some t), our bound is of the form R (w;) < (1+2p) (++2p))(w))) E. There is a trade-off about the choice of p E (0, 0.5). On one hand, p - 0 is preferred in view of the RHS of above bound. On the other hand, the sparsity-level relaxation con- dition & > 4(1-p)²12 lo prefers p 0.5. We illustrate such p²v?
4.1.2. CONVERGENCE ANALYSIS
Before proceeding with the convergence analysis, we make additional assumption on the population variance of the stochastic gradients, similar to the one in (Mishchenko et al., 2020).
R(w (w))
Assumption 4.1 (Bounded stochastic gradient variance). For any w, the population variance of the gradient estimator is bounded by B: Σ. (R())) - R(ww)] < B.
We now present our convergence analysis, first with I' = IRd, retrieving Theorem 2 from (Zhou et al., 2018).
a trade-off on some synthetic experiments in Appendix H.1.
Theorem 4.2 (Equivalent to Theorem 2 from (Zhou et al., 2018), Proof in App. F.2.2). Assume that r R.d. Sup- pose that Assumption 2.1 and Assumption 2.2 hold with = 3k, and that Assumption 4.1 also holds. Let v be an arbitrary k-sparse vector. Let C' be an arbitrary positive constant. Assume that we run HSG-HT-2SP (Algorithm 2) for T timesteps, with rj = T. and Ki v.
4. Extensions: Stochastic and Zeroth-Order Cases
In this section, we provide extensions of Algorithm to the stochastic and zeroth-order sparse optimization problems, and provide the corresponding convergence guarantees in objective value without system error.
- and denote a := f. +
Le. Suppose that k ' A0?22T. Finally, as- sume that we take the following batch-size: s, == wh with
w := 1 Iakk and == aB C. Then, we have the following convergence rate:
4.1. Stochastic Optimization
In this section, we consider the previous risk minimiza- tion problem, in a finite-sum setting, i.e. with R(w) = 1 E R,w,), as in (Zhou et al., 2018; Nguyen et al., 2017): indeed, stochastic algorithms can tackle more eas- ily large-scale datasets where estimating the full V R(w)) is expensive.
ER(ØT) R(w) S 22²22o LonguT (l (lw--woll woll
(lol=wolf+ +
4 3
Such a Theorem is equivalent to Theorem 2 from (Zhou et al., 2018), however, the proof from (Zhou et al., 2018)
6

---

Optimization over Sparse Support- Sets: Two-Step Projection
based on the same framework (Jain et al., 2014), which makes it more complex. Our proof, on the other hand, is very similar to our proof of Theorem 3.4 above (i.e. closer to convex constrained optimization proof's as discussed above), and simply incorporates the variance of the stochastic gra- dient estimator (exponentially decreasing thanks to the ex- ponentially increasing batch-size) in a properly weighted telescopic sum (with a technique inspired from (Liu & Foygel Barber, 2020)). We believe this makes the proof more readily usable for future extensions of IHT. And in particular, using similar technique as for Theorem 3.7, we can extend our result to the case with an extra constraint verifying Definition 2.3: we present such extension in Theorem 4.3 below.
VR(w) using finite differences. We refer the reader to (Berahas et al., 2021) and (Liu et al., 2020) for overview of ZO methods.
4.2.1. ALGORITHM
In this section, we describe the ZO version of our algorithm. At its core, it uses the ZO estimator from (de Vazelhes et al., 2022). We present the full algorithm Algorithm 3, where Day is uniform probability distribution on the following set B3 of unit spheres supported supports of size 82 S d: B := {w E E ||w llo S $2, ||w||2 S 1]. We can sample from this set by first sampling random support of size 82, and then sampling from the unit sphere on that support. If we choose $2 == d, this estimator simply becomes the vanilla ZO estimator with unit-sphere smoothing (Liu et al., 2020). Choosing $2 < d allows to avoid the full-sm full-snoohhness assumption and can reduce memory consumption by allow- ing to sample random vectors of size 82 instead of d (see (de Vazelhes et al., 2022) for more details on such ZO estimator). The difference with (de Vazelhes et al., 2022) (in addition to the mixed constraint setting and the use of the 2SP) is that in our case we sample an exponentially in- creasing number of random directions, which allows us, for the first time up to our knowledge, to obtain convergence in risk for ZO thrd-thresholding algorithm without any system error (except the unavoidable system error due to the smoothing μ (cf. Remark 5 in (Ajallocian & Stich, 2020))).
Theorem 4.3 (Proof in App. F.2.3). Suppose that Assump- tions 2.1 and 2.2 hold with s = 2k, that 4.1 holds, that R non-negative (without loss of generality), and let I be a set verifying Definition 2.3. Let be an arbitrary k-sparse vector. Let C be an arbitrary positive constant. Assume that we run IISG-IIT-2SP (Algorithm 2) for T timesteps, with 1j = L.+C. and denote a := L.
C + 1 and Kg == Lx v. Suppose that k 2 4a² ki for some p E (0, Finally, assume that we take the following batch-size: 8t == ==:= [ nB C Then, we have the following convergence rale:
p²
with w := Jmtyr and T ==
min R(w.) - + (() [E
$ p(1- p) L (lw-woll woll? + 4
a²
Algorithm 3: Hybrid ZO IHT with Extra Constraints (HZO-HT-2SP)
Input:
wo: initial point, 7y: learning rate, T: number of iterations, $2: size of the random supports, {q. }: number of random directions.
Further, if i is a global minimizer of R over (kk) =
{w: : ||wl|o S K}, then, with p = 0.5:
for t t= 1 to T do
4 min R (w:) (w::)-R(C R(()) S Sa² Lokgo (100- woll + (E[T]
Uniformly sample q:-1 i.i.d. random directions {u 14-1 ~ Doz
3
Compute the approximate gradient 9:
Corollary 4.4 (Proof in App. F.3.). Therefore, the number of calls to a gradient V R. (#IFO), and the number of hard thresholding operations (#HT) such that the left-hand sides in Theorem 4.3 above are smaller than some 0, are re- spectively: #HT = Ox, lo)( and #IFO = O
9t-1 Σ 1 (R(w;-) + puu) Ri( WT 1)) us
w. = (w - 119:-1)
end Output: up E arg w R(wr).
Ke
4.2. Zeroth- Orderr Optimization (700)
4.2.2. CONVERGENCE ANALYSIS
We now consider the zeroth-order (ZO) case (Nesterov & Spokoiny. 2017), in which one does not have access to the gradient Vi(w), but only to function values R(w), which arises for instance when the dataset is private in distributed learning (Gratton et al., 2021: Zhang et al., 2021) or the model is private as in black-box adversarial attacks (Liu et al., 2018), or when computing V w) is too expensive such as in certain graphical modeling tasks (Wainwright et al., 2008). The idea is then to approximate
Assumption 4.5 ((L,, s)- RSS'). (Shen & Li, 2017: Nguyen et al., 2017) is -.grestriceed strongly smooth with sparsity level 8, i.e. is differentiable, and there exist a generic constant L, such that for all (xx y) E Rd with - S s: |V(()) RRyy)) < L. flw--yll yl-
Remark 4.6. Note that if a convex function R is (L,, s)- RSS', then is also (L,, 8)-SSS (this can be proven in the same way as for usual smoothness in convex optimization
7

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
(see Lemma 1.2.3 from (Nesterov, 2003)). However, the converse is not true here, contrary to what holds for usual smooth and convex functions (cf. Theorem 2.1.5 from (Nes- terov, 2003)), as we show through some counter-exampee in Appendix F.1. Assumption 4.5 is indeed slightly more restrictive than Assumption 2.2, but it is necessary when working with Zo gradient estimators (see more details in (de Vazelhes et al., 2022)).
that we run HZO-HH-22S (Algorithm 3) for T timesteps, with 1j = _, at," with == b, + 1. Suppose that k 2 16 take qe random directions at each iteration, with q: == [ with w == 8 8j and T == 16k, EF (a-1). Then, we have the following convergence rate:
p R2gh for some p E 10. Finally, assume that we
E min R(wer) (1 (1+ [E[T]
We now present our main convergence theorem for the ZO setting, first when r = TR..
4 a²
Lookiow"" (110- woll +
1 / [R(
p(1-p) 111-1 p)
3 Rig Les'
Theorem 4.7 (Proof in App. F.4.2). Assume that r = Rdd Let tp be an arbilrary k-sparse vector. Let 8 3k, and 82 E II....d]. Assume that R is (Ing,'') 8')- with 5' = max($2,8), s), and (Va, s)-restricted strongly convex. Denote Kgg = l.s. Let C be an arbitrary positive con- (s-1)(s2-1) +3). Eabs
with 2 = I-p
2 t) + = Further, if i is
a global minimizer of R over Bo(k) {w //wlo lo S k.. then, with p 0.5:
stant, and denote Ep (02+2)
2d
E min R R(w)) R(w) TE(T]
2dL 888
(0-1))(2-1)
+1), and Enp == sd Assume IIZO-IIT-2SP (Algorithm 3) for T timesteps, +
d-1
(1100- - woll 1 1 / [ Rig Lo
that
S 1602Lg
|1:00
C + Suppose L. that 2 16 Finally, assume that we take the fol- lowing number qt of random directions at each iteration: q: := [=]] wwith w := Sak, and T == 16ks eF Then, we have the following convergence rate, with Z
with 7- = L. .Li,. with a= :=
1
+ Zz².
Corollary 4.9 (Proof in App. E.S... Additionally, the num- ber of calls to R (#IZO), and the number of hard threshold- ing operations (#HT) such that the left-hand sides in The- orem 4.8 above are smaller than e 7,,2, for some e >> O are respectively: #IIT O ([))) and #rzo
(a-1))
Ep (2. v. + +2)
Eaba:
ER(ØT) - R((w)
O (Er (..)).. Note that if s2 = d (in which case Assump- tion 4.5 becomes the usual (unrestricted) smoothness as- sumption), we have = = O(s) = Okk), and therefore we obtain a query complexity that is dimension independent.
1 [nll/R(1)))) [1:00 (1:00-00 wol! 12+
< <4a2 Rog
+ 7p²,
3
Kig La
Such novel result illustrates the power of proof techniques based on our three-point lemma. Up to our knowledge, it is the first global convergence guarantee without system error for a ZO -hntthhreso algorithm (see Table 1), and as such, is a sigmificant improvement over the result from (de Vazelhes et al., 2022). Our proof differs from the one in (de Vazelhes et al., 2022): that latter uses a bound on the expansivity of the hard- sandtthresholding operator, and only provides a result in terms of || - wwl, with a non-vanishing system error which depends on V R(w) (cf. Table 1). We now present our Theorem in the case of a general support- preserving convex set I'.
Such a query complexity result also holds when I Rdd (cf. Corollary F.8 in Appendix). (de Vazelhes et al., 2022) also achieved a dimension independent rate, but their con- vergence result exhibited a potentially large non-vanishing system error (cf. Table 1). which we do not have in The- orems 4.7 and 4.8. In strongly convex and smooth ZOO, dimension independent query complexity is impossible to achieve (Jamieson et al., 2012), unless with additional assumptions (Golovin et al., 2019; Sokolov et al., 2018;
Wang et al., 2018; Cai et al., 2022; 2021; Balasubrama- nian & Ghadimi, 2018; Cai et al., 2022; Liu & Yang, 2021;
Jamieson et al., 2012; Nozawa et al., 2024; Yue et al., 2023). Our work confirms that, instead of making extra assump- tions, a possible way to obtain a dimension independent query complexity is to instead consider optimization with Eo constraints.
Theorem 4.8 (Proof in App. F.4.)). Suppose that As- sumptions 2.1, 2.3, and 4.5 hold with s = 3k, that R non-negative (without loss of generality), and let T be set verifying Definition 2.3. Let w be ar- bitrary k-sparse vector. Let 82 (1....d). Denote N2 == Et Let C be an arbitrary positive constant, V.
5. Conclusion
and denote EF == (20+2)
2d
((-1))oo-1) +3). Eabs :=
In this paper, we provided global optimality guarantees for variants of iterative hard thresholding that can handle extra
2dL (s-1)(02-1) 1) +1) +1). and En = 13,dd Assume
8

---

Optimization over Sparse Support- Sets: Two-Step Projection
convex pupport-preserving constraints for sparse learning, via two-step projection algorithm. We provided our anal- ysis in deterministic, stochastic, and zeroth-order settings. To that end, we used variant of the three-point lemma, adapted to such mixed constraints, which allows to sim- plify existing proof' for vanilla constraints (and to provide a new kind of result in the ZO setting), as well as obtaining new proofs in such combined constraints setting. Finally, it broader
Balasubramanian, K. and Ghadimi, S. Zeroth-order (non)- convex stochastic optimization via conditional gradient and gradient updates. Advances in Neural Information Processing Systems, 31, 2018.
Bauschke, H. H., Bolte, J., and Teboulle, M. descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Op- erations Research, 42(2):330-344 2017.
would also be interesting extend this work family of sparsity structures and constraints, for instance, to matrices graphs. We leave this for future work.
Bauschke, H. H., Bolte, J., Chen, J., Teboulle, M., and Wang. X. On linear convergence of non-euclidean gradi- ent methods without strong convexity and lipschitz gra- dient continuity. Journal of Optimization Theory and Applications, 182:1068-1087, 2019.
Acknowledgements
This work was supported by the Special Fund for Key Pro- gram of Science and Technology of Jiangsu Province under Grant No. BG2024042, the Natural Science Foundation of China (NSFC) under Grant U2192049, and Ant Group through CCF-Ant Research Fund under Grant No.20240512. We are grateful to ICML reviewers for their valuable feed- back and suggestions.
Beck, A. and Hallak, N. On the minimization over sparse symmetric sets: Projections, optimality conditions, and algorithms. Mathematics of Operations Research, 41: 196- 196-223,72 2016
Berahas, A. S., Cao, L., Choromanski, K., and Scheinberg. K. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Founda- tions of Computational Mathematics, pp. 1-54, 2021.
Impact Statement
This paper presents work whose goal is to advance the field of sparse optimization for machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Böhning, D. Multinomial logistic regression algorithm. Annals of the Institute of Statistical Mathematics, 44:197- 200, 1992.
Bolte, J., Sabach, S., and Teboulle, M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146:459-494, 2014.
References
Agarwal, A., Negahban, S., and Wainwright, M. J. Fast global convergence rates of gradient methods for high- dimensional statistical recovery. Advances in Neural Information Processing Systems, 23, 2010.
Bot, R. I., Csetnek, E. R., and László, C. An inertial forward backward algorithm for the minimization of the sum of two nonconvex functions. EURO Journal on Computational Optimization, 4:3 2016.
Ajalloeian, A. and Stich, S. U. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008.0000 2020.
Brodic, J., Daubechies, I., De Mol, C., Giannone, D., and Loris, I. Sparse and stable markowitz portfolios. Proceed- ings of the National Academy of Sciences, 106:12267- 12272, 2009.
Attouch, H., Bolte, J., and Svaiter, B. F. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward backwarrd splitting, and regularized gauss seidel methods. Mathematical Pro- gramming, 137:91-129, 2013.
Bubeck, S. et al. Convex optimization: Algorithms and com- plexity. Foundations and Trends0 Machine Learning, 8:231-357, 2015.
Cai, H., Lou, Y., McKenzie, D., and Yin, W. A zeroth- order block coordinate descent algorithm for huge-scale black-box optimization. International Conference on Machine Learning, pp. 1193-1203, 2021.
Axiotis, K. and Sviridenko, M. Sparse convex optimization via adaptively regularized hard thresholding. The Journal of Machine Learning Research, 22(1):5421-546) 2021.
Axiotis, K. and Sviridenko, M. Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. In International Conference on Ma- chine Learning, pp. 1175-1197, 2022.
Cai, H., Mckenzie, D., Yin, W., and Zhang, Z. Zeroth- order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization, 2022.

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Chang, C.-C. and Lin, C.-J LIBSVM: A library for sup- port vector machines. ACM Transactions on Intelligent Systems and Technology, 2:1-27, 2011.
Jamieson, K. G., Nowak, R. D., and Recht, B. Query com- plexity of derivative- optimization. arXiv preprint arXiv:1209.245: 2012.
Damadi, S. and Shen, J. Gradient properties of hard thresh- olding operator. arXiv preprint Sttiv:2209.082477 2022.
Kyrillidis, A., Becker, S., Cevher, V., and Koch, C. Sparse projections onto the simplex. In International Conference on Machine Learning, pp. 235-243, 2013.
De Marchi, A. and Themelis, An interior proximal gradi- ent method for nonconvex optimization. arXiv preprint arXiv:2208. 00799, 2022.
Li, H. and Lin, Z. Accelerated proximal gradient meth- ods for nonconvex programming. Advances in Neural Information Processing Systems, 28, 2015.
de Vazelhes, W., Zhang, H., Wu, H., Yuan, X., and Gu, B. Zeroth-order hard-thresholding: Gradient error vs. expansivity. Advances in Neural Information Processing Systems, 000222289-2220111 2022.
Li, X., Arora, R., Liu, H., Haupt, J., and Zhao, T. Nonconvex sparse learning via stochastic optimization with progres- sive variance reduction. arXiv preprint 115iv:1605.02711, 2016.
DeMiguel, V., Garlappi, L.., Nogales, F. J., and Uppal, R. A generalized approach to portfolio optimization: Im- proving performance by constraining portfolio norms. Management Science, 55:798-812, 2009.
Liu, H. and Foygel Barber, R. Between hard and soft thresh- olding: optimal iterative thresholding algorithms. Infor- mation and Inference: Journal of the IMA, 9:899-933, 2020.
Foucart, S. and Rauhut, H. An invitation to compressive sensing. In A Mathematical Introduction to Compressive Sensing, pp. 1-39. Springer, 2013.
Liu, H. and Yang, Y. A dimension-inssesitive algorithm for stochastic zeroth oooerr optimization. ar preprint arXiv:2104. 110.2 2021.
Foygel Barber, R. and Ha, W. Gradient descent with non- convex constraints: local concavity determines conver- gence. Information and Inference: Journal of the IMA, 7:755 806, 2018.
Liu, S., Kailkhura, B., Chen, P.-Y., Ting, P., Chang, S., and Amini, L. Zeroth-order stochastic variance re- duction for nonconvex optimization. arXiv preprint arXiv: 1805 10367, 2018.
Frankel, P., Garrigos, G., and Peypouquet, J. Splitting methods with variable metric for lojaswwzz functions and general convergence rates. Journal of Op- timization Theory and Applications, 165:874-900, sep 2014.
Liu, S., Chen, P.-Y., Kailkhura, B., Zhang, G., Hero III, A. O., and Varshney, optimization signal processing and machine learning: Principals, recent advances, and applications. IEEE Sig- nal Processing Magazine, 37:43-54, 2020.
primer on zeroth- order
Golovin, D., Karro, J., Kochanski, G., Lee, C., Song, X., and Zhang, Q Gradientless descent: High-dimensional zeroth-order optimization. In International Conference on Learning Representutions, 2019.
Loh, P.-L. and Wainwright, M. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. Advances in Neural Information Processing Systems, 26, 2013.
Gratton, C., Venkategowda, N. K., Arablouei, R., and Werner, S. Privacy-preserve distributed learning with zeroth-order optimization. IEEE Transactions Infor- mation Forensics and Security, 17:265-279, 2021.
Lu, Z. Optimization over sparse symmetric sets via non- monotone projected gradient method. arXiv preprint MrXiv:150.00850 2015.
Gu, B., Wang, D., Huo, Z., and Huang, H. Inexact prox- imal gradient methods for non-convex and non-smoote optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Metel, M. R. Sparse training with lipschitz continuous loss functions and weighted group 10-norm constraint. Journal of Machine Learning Research, 24:1-44, 2023.
Mishchenko, K., Khaled, A., and Richtárik, P. Random reshufiling: Simple analysis with vast improvements. Ad- vances in Neural Information Processing Systems, 33: 17309- 2020.
Hoyer, P. O. Non-negative sparse coding. In Proceedings of the 12th IEEE workshop on neural networks for signal processing, pp. 557-565. IEEE, 2002.
Jain, P., Tewari, A., and Kar, P. On iterative hard thresh- olding methods for high-dimensional m-estimation. Ad- vances in Neural Information Processing Systems, 27, 2014.
Negahban, S., Yu, B., Wainwright, M. J., and Ravikumar, P. A unified framework for high-dimensional analysis of m m-estimators with decomposable regularizers. Advances Neural Information Processing Systems, 22, 2009.
10

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Nesterov, Y. Introductory lectures on convex optimization: A basic course, volume 87. Springer, 2003.
Xu, Y., Qi. Q., Lin, Q. Jin, R., and Yang. T. Stochastic op- timization for de functions and non-smooth non-convex regularizers with non-asymptotic convergence. In Interna- tional Conference on Machine Learning, pp. 2019b.
Nesterov, Y. and Spokoiny, V. Random gradient-fred freee mini- mization of convex functions. Foundations of Computa- tional Mathematics, pp. 527-566, 2017.
Yang. Y. and Li, P. Projective proximal gradient descent for class of nonconvex nonsmooth optimization prob- lems: Fast convergence without kurdykk--loasseewicz (kl) property. arXiv preprint arXiv:2304. 10499, 2023.
Nesterov, Y. et al. Lectures on convex optimization, volume 137. Springer, 2018.
Nguyen. N., Needell, D., and Woolf, T. Linear convergence of stochastic iterative greedy algorithms with sparse con- straints. IEEE Transactions Information Theory, 63: 6869-6895, 2017.
Yang. Y. and Yu, Fast proximal gradient descent for class of non-convex and non-smooth sparse learning problems. In Uncertainty in Artificial Intelligence, pp. 1253-1262, 2020.
Nozawa, R., Poirion, P.-L., and Takeda, A. Zeroth-order random subspace algorithm for non-smooth convex opti- mization. arXiv preprint arXiv:2401. 13344, 2024.
Yuan, X.-T., Li, P., and Zhang, T. Gradient hard thresholding pursuit. Journal of Machine Learning Research, 18:6027- 6069, 2017
Pan, L., Zhou, S., Xiu, N., and Qi. H.-D. A convergent iterative hard thresholding for nonnegative sparsity opti- mization. Pacific Journal of Optimization, 13:325-353, 2017.
Yue, P., Yang, L., Fang. C., and Lin, Z. Zeroth-order op- timization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4429 PMLR, 2023.
Peste, A., Iofinova, E., Vladu, A., and Alistarh, D. Ac/de: Alternating conpresseeddeccomppssedd training of deep neural networks. Advances in Neural Information Pro- cessing Systems, 34:8557-8570, 2021.
Zhang, Q., Gu, B., Dang, Z., Deng, C., and Huang, H. Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 2598-2607, 2021.
Shen, J. and Li, A tight bound of hard thresholding. Journal of Machine Learning Research, 18:7650-7691, 2017.
Zhou, P., Yuan, X., and Feng, J. Efficient stochastic gradi- ent hard thresholding. Advances in Neural Information Processing Systems, 31, 2018.
Sokolov, A., Hitschler, J., Ohta, M., and Riezler, S. Sparse stochastic zeroth-order optimization with an applica- tion bandit structured prediction. arXiv preprint arXiv: (00iv:888..0000 04458, 2018.
Takeda, A., Niranjan, M., Gotoh, J.-y., and Kawahara, Y. Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios. Computational Man- agement Science, 10:21 01:21-49,220 2013.
Wainwright, M. J., Jordan, M. I., et al. Graphical models, ponential families, and variational inference. Foundations and Trends in Machine Learning, 1:1-305, 2008.
Wang, Y., Du. S., Balakrishnan, S., and Singh, A. Stochastic zeroth-order optimization in high dimensions. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1356-1365, 2018.
Xu, Y., Jin, R., and Yang, T. Non-asymptotic analysis of stochastic methods for non-smooth non-convex regular- ized problems. Advances in Neural Information Process- ing Systems, 32, 2019a.

---

Optimization over Sparse Sets: Two-Step Projection
Appendix
Introduction
2
Preliminaries
3
Deterministic Case
3.1 Algorithm
3.2
Convergence Analysis
4
Extensions: Stochastic and Zeroth-Order Cases
6
4.1
Stochastic Optimization...
4.2
Zeroth-Order Optimization (ZOO)
5
Conclusion
8
Notations
14
Related Works
14
B.1 Local Guarantees for Combined Constraints
14
B.2 Global Guarantees for IHT and RSC Functions
14
Sample complexity in sub-Gaussian design
15
Proof of Remark 2.4
15
E
Proofs of Section 3 (Deterministic Optimization)
16
E.1 Proof of Lemmas 3.2 and 3.6..
16
E.2 Proof of Theorems 3.4 and 3.7
17
E.3 Lower Bound on the Sparsity Relaxation
20
Proofs of Section 4 (Stochastic and Zeroth-Order Optimization)
21
F11 Discussion on Restricted Smoothness Assumptions
21
F22 Proof of Theorems 4.2 and 4.3
23
F3 Proof of Corollary 4.4
33
F.4 Proof of Theorems 4.7 and 4.8
34
F.5 Proof of Corollary 4.9
51
Differences Between Two-Step Projection and Euclidean Projection
53
Experiments
53
H.1 Synthetic Experiments: Illustrating the Sparsity/Optimality Trade-Off
54
12

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
H.2
Real Data Experiment: Portfolio Index Tracking...
56
H.3 Real Data Experiment: Multiclass Logistic Regression
58
13

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
A. Notations
Below we aggregate the various notations used throughout the paper, for ease of reference.
Ir (w)) Euclidean projection of onto set T, i.e. [r(w)) E arg minler ||w 21|2-
wy i-th component of w.
||: lo pseudo-norm (number of non-zero components of vector).
(k): to pseudo-ball radius kt i.e. (k)) (w E Rd ||wllo - k).
H4: Euclidean projection onto Bo also known as the hard-thresholding operator (which keeps the largest (in magnitude) components of a vector, and sets the others to (if there are ties, we can break them e.g. lexicographically))
iif: Two-step projection of sparsity onto the set r, i.e (-) = I1 (Hx
Ilp: tp norm for E [1, +00).
|| ||: &g norm.
[n]] set (1,..., n) for E N"
| number of elements of set C [d].
supp(w): support of a vector w E R i.c. the set of coordinates of its non-zero components.
2SP: two-step projection
EP: Euclidean projection
B. Related Works
Below we present a more detailed review of the related works.
B.1. Local Guarantees for Combined Constraints
Among the works considering optimization over the intersection of the Eu pseudo-ball radius k and a set I, (Metel, 2023) analyze the convergence of first-order and zeroth-order stochastic algorithm with a weighted lo group norm constraint (which generalizes the to norm), combined with foo ball constraint. (Pan al., 2017) provide a deterministic algorithm which can tackle extra positivity constraints. (Lu, 2015) and (Beck & Hallak, 2016) analyze the convergence of variants of hard-thresholding in the deterministic case, with extra constraints that are symmetric and sign-free positive. Other line of works such as (Frankel et al., 2014; Xu et al., 2019b; Attouch et al., 2013; De Marchi & Themelis, 2022; Yang & Yu, 2020; Gu et al., 2018; Yang & Li, 2023; Bolte et al., 2014; Bot et al., 2016; Xu et al., 2019a; Li & Lin, 2015; Bauschke et al., 2017; 2019) have a general approach, and analyze the convergence of general proximal algorithms, for composite problems of the form min, R(w) + hww) where is a more general non-convex regularizer which can include the to constraint combined with an additional constraint, as long as the closed form for the projection onto the mixed constraint known (or an approximation of it in the case of (Gu et al., 2018)). However, all of these works only provide guarantees of convergence towards a critical point, at best, local optimum. We provide overview of those works in Table 1. More details about algorithms with local convergence specialized to lo optimization can also be found in Table from (Damadi & Shen, 2022).
B.2. Global Guarantees for IHT and RSC Functions
On the other hand, in the of restricted strongly convex (RSC) and restricted smooth (RSS) functions, existing approximate global guarantees for the IHT algorithm do not apply to problems with such combined constraints. Indeed, several works have considered global optimality guarantees for IHT in various settings: the full gradient (deterministic) setting (IHT (Jain et al., 2014)), the stochastic setting (Nguyen et al., 2017; Li et al., 2016; Shen & Li, 2017), and the zeroth-order setting (de Vazelhes et al., 2022). However, they do not address the case where the extra constraint I' is added the original sparsity constraint. The works (Foygel Barber Ha, 2018; Liu & Foygel Barber, 2020) tackle respectively
14

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
general non-convex thresholding operators, and general non-convex constraints, in the full gradient (deterministic) setting but however they do not provide explicit convergence rates for the particular type of sets that we consider in this paper: their rates depend on some constants (the relative concavity or the local concavity constant) for which, up to our knowledge, an explicit form is still unknown for the sets we consider.
C. Sample complexity in sub-Gaussian design
Similarly to (Jain et al., 2014), we can use (Agarwal et al., 2010), Theorem 22, to find the sample complexity needed to verify the Assumptions of Theorem 3.4, in the setting of sub-Gaussing design. Let consider the sparse linear regression setting, which solves ( with R(w))
1. A| - yll². and where n denotes the number of samples in the dataset (i.e. number of rows of A), and each row of A is a vector of dimension d drawn from sub-Gaussiaa distribution with covariance Σ with Σ& S 1 for all in {l,... d). and where we have for all i in {I,..., n1. 3i = (A..., w) + &t, where A.,. denotes the i-th row of A, and where & is some label noise, sampled from a normal distribution of standard deviation o (that is E ~ ~N(0, ))). As described in (Jain et al., 2014) using Theorem 22 from (Agarwal et al., 2010), R is (V,, 8)-RSC
and (I.,, s)-SSS with probability at least 1 - e0 with Vs = 2 ( -i slog d and I.g = 20x ( (Σ) + 01 slog where min (Σ) and max are the smallest and largest eigenvalues of Σ respectively, and co and 01 are universal constants. Let set 2/ required by Theorem 3.4, and take
4c (ogddd//maa (I) samples. We then obtain
V, 2 min Σ) and I,- I 2.250 E which means that (9u,) S <<E)= == max /mia (E). Thus it is enough to choose k- 4(9k( ) = m24k( k to verify the assumptions of Theorem 3.4 with high probability.
D. Proof of Remark 2.4
Before proceeding with the proof of Remark 2.4, we recall the definition of sign-free convex sets from (Lu, 2015) and (Beck & Hallak, 2016) below. Essentially, sign-free convex sets convex sets that are closed by swapping the sign of any coordinate.
Definition D.1 (LLu, (Beck & Hallak, 2016)). A convex set I' is sign-free if for all y (-1, and for all æ e I, O E I, where @ denotes the element-wis wise vector multiplication (Hadamard product for vectors).
We now proceed with the proof of Remark 2.4.
Proof of Remark 2.4. It is easy to show that any elementwise decomposable constraint such as box constraint is support- preserving (as projection can be done component-wiss, independently). Similarly, for group-wise separable constraints where the constraint on each group is k-support-presere Section H), for a k-sparse vector æ E R2, one can project each group of coordinates independently, and each of such projection will have its support preserved (since each such group of coordinates also contains less than k non-zero elements, i.e. they are k-sparse). Therefore, we analyze in more detail the case of sign-free convex sets. Let I be sign-free convex set, and let æ E Idd be a k-sparse vector. Define z = (I) and assume that supp(z) g supp(æ). This implies that there exist some non-empty set of coordinates S C [d]. such that for all E S: 2; A 0 and x; 0. Define z' such that
(such as the constraint for the index tracking problem in our
z4 e S otherwise
0 if k E S
2/4
Since I' is sign-free, z' E r. Now, define z" such that z =
Since I' is
2 if otherwise
convex and since z" = 22 + 22z we have z" E P. Now, we have:
|
(Ik 2112 = Σ
(ok - )2
k=1
KE kE(
(#k 2662 + Σ
(Ix -1 2= =
(xL - 2x)² = | -= =11
KE[dVS
KES
k=1
Therefore, we encounter a contradiction since we have defined z = [Ir()), and therefore, our assumption supp(=) g supp(1)) is wrong, which means that supp(z) C supp(ar).
15

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
E. Proofs of Section 3 (Deterministic Optimization)
E.1. Proof Lemmas 3.2 and 3.6
E.1.1. USEFUL LEMMAS
We first recall some useful definitions and lemmas from the literature.
Definition E.1 (Relative concavity (Liu & Foygel Barber, 2020)). The relative concavity coefficient Yk.8 of a k-sparse
projection operator Hi. of relative sparsity B == & with k S k is defined as:
y Hx(z) Hz(x))
7k.8 (Ha) = sup
y, E RR Iyllo S Bk, y + Hu(z)
y (z)2))12
Lemma E.2 (Lemma 4.1 (Liu & Foygel Barber, 2020)). When Hy is the hard-thresholding operator at sparsity level k. huve:
vB 1 K
7k,8 (Hx))
2
2
k
Proof of Lemma E.2. Proof in (Liu & Foygel Barber, 2020).
E.1.2. PROOF OF LEMMA 3.2
Proof of Lemma 3.2. We have:
w ii w Hx)21) + (1H)(w) - w0|2 + 2(w [x((w) (.,) Hxx(w) - w
(a) ww He(w))1 + (w)) u6| 2rk, (+((w) - 2 w/ www Hx(w))1 2 (1 27kkp)11H15 (())))((w)))))))))))))) i 1
k (1 (1-V [17(+(w)) 2i 10
w He(w))12
where (a) follows from Definition E.1 and (b) follows from Lemma E.2. Therefore, rearranging, we obtain:
h |1H u 1
[[=)) - w012 S w i
2
The proof is completed.
E.1.3. PROOF OF LEMMA 3.3
Proof of Lemma 3.3. Let V and b et1
2 1p. Consider
1 b... E IR k
w 10 0, a. E R
Then we have (w = [1.... 1. 0, 0....0 and
ww Hz(w))l b²k, || w/l = k (a b)2ki [10) w/ll
k + a²k
It can be verified that
ww H1. (w)) 1|2
ww w/ + (u 1
2abk
by to
k
m
(w)) i
k: + a²k
To
ke
This proves the desired inequality.
16

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
1.4. PROOF OF LEMMA 3.6
Proof of Lemma 3.6. Let us abbreviate Vs (x) It can be verified that
[[]](w) w|l2 = | (w) Uk 2k w|
(w) - m
2
+ 1/ -w11
0kk w ||
|| (w) w0 + 1/w0 w012 (13 11u. - w01
w .i (w) ا|| + ts ub|?
where (a) due to Definition 2.3 and the definition the two-step projection, which imply that II 2y and Uy w have disjoint supporting sets, and (b) uses the three-point-lemmaa for projection onto convex I', as well Lemma 3.2. The proof is completed.
E.2. Proof of Theorems 3.4 and 3.7
E. PROOF OF THEOREM 3.4
In this section, we present the proof of Theorem 3.4 for the convergence of Algorithm without the additional constraint, which mentioned above, is needed for the proof of Theorem 3.7, but also, a byproduct, illustrates how the threc-point lemma simplifies previous proof's of Iterative Hard- Thrd-hhheesh...ng.
Proof of Theorem 3.4. The L,- restricted smoothness of R implies that R(w,)
Lg
<R(W:-1) + (VR(w;-1); wi-1) +
we
w1-1
Ls
1
1
=R(w--1)
ui 11-1 +
V
VR(w:
VR(w:-1)]
2
L
21s
(0)
L
Lg
< R(ww--1)+
+
1 w1-1 + (R(w,-1)
(1
/B)llw; 20|2
2
L.
2
|V
2L.
Lg
Lg
-R(W)-1) + (V -- +
wi-1)
W u0
(1 - V BB|| [/ - 2/1
2
2
(6)
Lg 1/8
Lg
<R(w)
[1:11 - w/12
(1
/ ww w||
2
2
<R(w)
Lg [1i-1
1
2L.
V/8
ww w
2
where (a) uses Lemma 3.2, (b) is due the resteriiete strong-convexity of R. while the last step is implied by the condition on the sparsity level & from the theorem (k: 2 k)), and the definition of 3 (6 / }
41.2
The update rule composed of the gradient step and the projection from Algorithm 1 can be rewritten into the following (given that the learning rate is = +. and by definition of a projection):
1
vR(w(-1)
W. = arg
min
w
wi-1
L.
2 (R((w-1)) ,), w w1-1) + w-wwwaa - w1-1112 2
1
arg
min
V
st Sk Lg
L3
R(w,-1) (VR(w,,)) w wi-1) + Lg w w,-1l? 1|2
arg
min
wo s.t. o Skk
17

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Therefore, by definition of an arg min, we have:
R(w)r11) + (V (V((w(-1); - w1-1) + Lg 2
[lw0, - 11-111
T,
S R(w)-1) + (VR(u ((V(--))(V(((())))))) w011 wx-1) +
||00-1 - w/-111
2
= -((w+-))
(8)
And from the Lg smoothness of R, we also have:
R(w:)= S R(w(-1) (VR(w(-1), wi w(-1) + L. w|w, w1-1l1
La
(9)
2
Therefore, combining equations 8 and 9, we obtain:
R(w)) S R(w:-1).
That is, the sequence (R(w:))oo of risk non non -on-increasin.
Let us now consider
2L log Vs
(L. Uo) Wo w 1
T
We claim that R(w;)= < R(w + for 1 2 T 1. To show this, suppose that 31 E [7] such that R(w.) < R(w) + + Then the claim is naturally true by monotonicity. Otherwise assume that R(w,) > R( ()) + for all f E [T]. Then in view the inequality equation? we know that
21
20
Wr 2
WT-11
21.
V/8
V/2
|10T-1
0/12
2hg
Ve
W0000 2
2
))
exp
T Tlog
1
1/3
||2000 t0/l
2T.g)
2h s
(Tes vs)
Us
S exp
log
+
log
|1w00
1/3
2x
2Lg
1/
exp
22g log
(Lg Vv)
We
28
log
V.
||ur0
2T.g
Vs
28
2T
(a)
Vs
2Ts
log
25
Us
||w0
|
2
(L, Maalluu) 20113
2L,
2s
(b)
2
2T
L U
I,
where (a) follows from the fact that for all in (-o0, 1): log(1 x) < xx and (b) uses the fact that (1-
Me 2h.
1
Then according to equation 7 we must have
L, V
R(wr+1) < R(w) +
2 1wy w1| < R(w) +E,
which implies the desired claim. The proof is completed.
Remark E.3. Theorem 3.4 recovers the result of Jain et al. (2014, Theorem 1). Our proof is shorter yet more intuitive than in that paper.
18

---

Optimization over Sparse Support-Preservnng Sets: Two-Step Projection
E.2.2. PROOF OF THEOREM 3.7
Using the above results, we can now proceed the full proof of convergence of Theorem 3.7 below.
Proof of Theorem 3.7. Denote 22 = "u(ww,> (R(=-11)) for any & E N. Similar to the arguments for equation 7, based on the -ysreestricted smoothness of we can show that:
R(we)
Le
<R(wi-1) + (V R( W: w1) wi -w,-1)
+
ww w,l1
2
L
1
-R(wi-1) +
Wi w + (R(((-1))
VV((w=1))1'
2
L
2L
(0)
La
1 V(((w:-1)
Le
<R(wi-1) +
W1-1
(
wi w 1
L
2
Lo /Bllu, - -ūl2
1
+ 2
V VV((w.-1)
21
Is
Is
=R(w (VR(w,-1), w w,-1)
+
1/
ww
w|
2
La
+
3 1 nا|?
(8)
L,g - U/3
L,g
T,g 2
1 <R(w)) +
Wi - w/
We
10|1
v
8 02
2
2
<R(w) + L V/3
2 W - w/
L
Ww
w|| + pv:
||0 - w||
(10)
2
4(1
where (a) uses Lemma 3.2, (b) due to the Vg restrricd strong- of R, and the last step is due the condition on
()) Te), and the definition of B = =VE
sparsity level k from the theorem (k 2 22
In view of equation 7, which is valid under the given conditions, we know that
R(vx) & R(w) + T Us
2h V 11 - w1
2 1 -
(11)
4
After proper scaling and summing both sides equation 10 and equation 11 yields that
(1 - p)[(w,) + pl(v))
La - V/3
(1 - p)Lb
p(L. vs)
<R(w)) +
l|w, -0122
-20
2
2
Lsg - Vs
Lg pvs
-R(w) +
|
w/|
w -wll
w/1?,
(12)
2
2
where in the second inequality we have used to E T and the non-expansiveness of projection over convex sets.
Let us now consider
2b
(Ls - u2)ll va)llw0 -20 -0012) )
T =
log
(13)
1,
We claim that:
min {(1 ((w):) + pR(())) < R(w) +
(14)
r][++]]
To show this, suppose that 3t E [T] such that (1 (1-p) R( (.)) + pR(,)) < R(w) + Then the claim is naturally true. Otherwise assume that (1 - (--))((w))) + pR(v.) > R(w) + = for all t E [T]. Then in view of the inequality equation 12 we know that
19

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
La 1/8
| - u012 - (1- (1 p)v/'
|ur 2512 -
|| - -
Lg
Lg
(1
p)us
T
28
11200
w012 -
Lg
L,
Then according to equation 12 we must have
(1 p- R(wr+1) + pR((1+11) S R(w) + Lg Us
uTT Tō|2 s R(w) +
(15)
2
which proves the claim from equation 14. Now, recall that we have assumed in the Assumptions of Theorem 3.7, without loss of generality, that R is non-negative (if not, redefine R by adding constant, without modifying the gradient of R. keeping the algorithm untouched), which implies that R (vx) 2 0. Plugging this in equation 14, for
T
2h log (1.-2, 11100 mi
implies that:
2e'(1-))
1
+ E S (1+ 2p) + E 1 p
min R (we) I R(w) [E[T]
(16)
1-p
Plugging the change variable e'
I-p into equation above, and in 13, we obtain that when T 2
2h log (L,-v,)) (.))]lnn una mml=" 1:
21-ppp) }
Til""
min R (wx) & )(w) + +
1E|T]
Further, consider an ideal case where i is a global minimizer R over (b(k) := {w ||w/|o S k}. Then R (v,)
2 R(w))
always true for all 2 1. follows that the bound in equation 14 yields, for T > 2hا log [Lo-vn
-. w| wil2
+1:
28
min ((1 - p) (w:) + pR(wn) S min {(1 ((w.) + pR (v:) < R(w) + (T
[E[T]
which implies: min R (wx) S + In this case, we can simply set p 0.5, and define c
2
T-p" similarly as above. This implies the desired claims. The proof completed.
1-p
E.3. Lower Bound on the Sparsity Relaxation
Consider α 1, p k + 2 and the following defined diagonal matrix A of size p p and vector b of size pt
K
A
12XX
b [1,
E RR.
R2
Clearly, A is k-smooth and 1-strongly convex. Let us consider the following quadratic objective function:
f(w)
マタ ww b)T A(w - b).
Let E [k. k2k] the relaxed sparsity level used for IHT, and being an even number (without loss of generality). Consider the following defined p-dimensional sparse vectors such that ||ã||o k and || k:
v 1, R...,,,
O, E RP, w 0,...,,, K. K.....
k...... O..... w4k-k
0 1 E IRP.
k/2
4/2
h k-b
We next prove the following theorem which shows that l 2 (1271)) is indeed necessary for IHT to converge in some extreme cases for optimizing f.
20

---

Optimization over Sparse Pupport- Sets: Two-Step Projection
Theorem E.4. 1f 2 and S s2 .thn it holds that
k²h f(w) 2 f(w) +
16
while w is fixed point of IHT with sparsity level k. and step-size 11
L 2x i.e.
Mr (w f(w)).
Proof. It can be seen that f(w) 2 and s(w)
15
th
x²
+
x
+
h
=ーk)
k)
2
Therefore
K
f(w)
f(w)
1)
x²
+ 2
-
2
2
1
1
x²
2
2
-
$1 1
k 2
x2
k
2
16
where Çi uses & 2 4, and the last inequality is due to h:
Note that
((ww) A(w b)
O.
k/2
R2k
22
Given 17 =
1. 2x we can show that
w /VW[ = 0..,.... 0.5, ......,h Ki 1, I,..,, 1,0.,/ 0..5
k/2
k/2
k/2
x² n2k-2th/2
which directly yields (as > 1)
w Hz(w - vV
and thus ur is fixed point of IHT with sparsity level l and step-size 전
Remark E.5. The example is inspired by the one from (Axiotis & Sviridenko, 2022), though slightly simpler. A main difference is that in our example the supporting sets of w and v are allowed to be significantly overlapped, while in theirs the supporting sets of the two vectors are constructed to be disjoint.
F. Proofs of Section 4 (Stochastic and Zeroth-Order Optimization)
F.1. Discussion on Restricted Smoothness Assumptions
In this section, we provide additional details on the difference between Assumptions 2.2 and 4.5. First, we recall the standard definition of smoothness:
Definition F.1. A differentiable function f is L-smooth if for all æ, y E (Rd))::
[Vf(x) V s Ll| - yll
We now provide the counter-example below, illustrating that Assumptions 2.2 and 4.5 are not always equivalent, even if is convex (and that those two assumptions are also different from the usual smoothness assumption).
Lemma F22 Let us consider the following convex function f: 122 + IR defined as
((z1, E R f(z1, x2) = x + + 2
has the following regularity properties, with the given constants being each time the smallest possible:
21

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
(i) 3-smooth
(ii) 2-restricted smooth (Assumption 2.2) with sparsity level 1
(iii) Vo-restricted strongly smooth (Assumption 4.5) with sparsity level I
Proof. F.1.1. PROOF OF (1)
The Hessian of is:
2 1
H
2
and its diagonalization is:
H PDP-1
with:
P = 1
1 -1
1
3 0
P
and D
-1
0
Therefore, the smallest I. such that we have T.I2x2 is 3, which implies from Lemma 1.2.2 (Nesterov et al., 2018) that f is smooth with smoothness constant 3.
F.1.2. PROOF OF (IT):
Let us take two in (I2)²² such that | yllo S 1, which therefore implies that: V1 222 1/2 (or both). Let us suppose that (E): 22 = V/. Note that this implies that | yll2 = (x1 y2)² We now need to find the smallest L such that:
L こ x - 2112
f(y) $ f()) + (Vf(z). - x) +
y-
L
vî - v2 + v1 S o + 22 x1 + (2m1 + x2) .1) + (2x2 21) x2)
2 (x) y1)²
L
v + 22 21 S 5 + 21 + (2m: + 22)
x1) + (2x² x1) 12)
(x1 y1)
2
L
v + x
2y 11 <
-
[z) - y112
2
L
( -
2 [-] yn)²
Therefore, the smallest L possible which can verify the above is L = 2. By symmetry, we would have the same chain of equivalence the alternative case where we would replace x2 = y/2 by x1 = V1- Therefore, we need some L that will work for both cases, so again, such smallest is
F.1.3. PROOF OF (II)
Let us take two æ, y such that ||æ vllo & 1, which therefore implies that: æ1 y1 222 = 3/2 (or both). Let suppose that (E): D2 y/. Note that this means that || y1l2 (x) v1)2. What we need to find is the smallest L such that:
[V - 2 - y112
<
+
(2.1 + 52 (2y) + 22))) + (2.rg 31
(2yz + y1))² < L (2 yn
22

---

Optimization over Sparse Support- Sets: Two-Step Projection
(2xr x2 (2y1 xx2))² + (2xg x1 -22r +1)) (2 -v1)²
4(x1 - 11) (21 81)² (21 y1)²
4
5(ø - v1)² S (2 - y11
Therefore, the smallest L possible which can verify the above is L = V5. By symmetry, would have the same chain of equivalence in the alternative where would replace 22 1/2 by æ1 yı. So therefore we need some L that will work for both cases, so again, that smallest L is v5.
F.2. Proof of Theorems 4.2 and 4.3
For the proof of Theorem 4.3, we use similar technique as in Theorem 3.7 to deal with the extra constraint, i.e. we start first from the case I = IRd (Theorem 4.2). Based on our &o three-point lemma (Lemma 3.2), such proof of Theorem 4.2 is simpler than the corresponding proof of (Zhou et al., 2018) (Proof of Theorem 2, Appendix B.3). Also, compared to the deterministic setting, here, we need carefully incorporate the exponentially decreasing error of the gradient estimator into properly weighted telescopic sum containing terms in l|,, le Below we provide several intermediary results needed for the proof of Theorem 4.3. Then, the proof of Theorem 4.3 will be provided in Section F.2.3.
F.2.1. USEFUL LEMMA
Before starting the proof, we present the following lemma from (Mishchenko et al.. 2020), which relates the batch-size St and the error of the gradient estimator:
Lemma F.3 (Mishchenko et al., 2020), Lemma 1). Let Rd. Assume that gi is the sampled gradient in Algorithm 2 and that the population variance of R& (s(w)) is bounded by as in Assumption 4.1. Then the gradient estimate gt is an unbiased estimate of v VR(w)), and its variance as follows:
E flg (R(w;))
<
B n1 St
(17)
Note that the original Lemma from (Mishchenko et al., 2020) written as an equality, in terms of the exact population variance of random variable, denoted o², but we rewrite inequality here for simplicity, in order to have general bound that applies at each iteration.
Proof of Lemma F.3. Proof in (Mishchenko al., 2020).
F.2.2, PROOF OF THEOREM 4.2
Below we now first present a proof for the convergence Algorithm 2 without the additional constraint (Theorem 4.2), which is needed for the proof of Theorem 4.3, and also, as byproduct, illustrates how the three-point lemma simplifies such proof.
23

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Proof of Theorem 4.2. The -sssmootsnesss of R implies that
R(ws)
La
<R(W--1) + (V (VR(w:-1),)) w
ww: w1-1|
Ls
=R(w + (9--1. wi - wx-1) 1) +
[w0-
11 + (VR(w,-1) - -9--1, w, - w.-1)
2
1
=R(w)-1) +
|1/e, (w)-1 -19t-111 1)12 - 1/² (afllg-1 19--1|1 - 1|0, - wr-1112 + 2 10: 11-11
21
+ +VVR(w)-1) - 9:-1, Wi w
1 Le
1 + 21
1
|| w/ (w)-1 - 199111)12
!!
1111-11
n
1w w w
2
2
+ +VR((w)11) 1) - 9t-1, wi w
R(w)-1) +
1
④ (w:-1 1991-))12 (1 - VB)ll -00l=
2012
!7
919--111
2m
2
1
+
7
|| w1-1l1 2 + (VR(w(-1) - 9t-11 wT -We-1)
2
1
1 (1 /3)1
-R(w;-1)
+
[||00 w || 1""1|:9 9 1|/ 2(ng: WP-1 -w/]
2
2m
2n
Lg
1
-2199-111
!
π
|w wi 1|2 (V(ww-1)
9t-11 we w:-1)
2
1
1 (1 - /B) 12,, - -
=R(w:-1)
+
10 Wt 11/ 2- -2(1gt-11, wT-1 -woi]
w1-1
2n
2n
1
+
||w,
Wt- 2 + (VR(w,-1) - 1t-1, wr - w)--1
2
b
R(w--1) 1)
+
1
w:-1 1|2 (g:-11 W::1 w - (1 / w/
21j
2n
L.
C
1
+
7
l|w, w. 2| +
VR(w,,1) -9:-111
2
2C
where (a) follows from Lemma 3.2 and (b) follows from the inequality (a, S Ga² + 12, for any (a, b) E (Rd)² with C' > 0 an arbitrary strictly positive constant.
L. -- ||w, 11 above is O. We now take the conditional |- 2
Let us now assume that 7) T. therefore the term expectation (conditioned on W;-1, which is the random variable which realizations are wi-1),, on both sides, and from Lemma F.3 we obtain the inequality below (we slightly abuse notations and denote E[- (, wi- 1] by [[-/w,,i]]::
1 || w.-1l 2n
([R(w;)) w/-11 S ((((-1)) +
(V (R(Ww-)) Wi-1 w
1
+ B(n -8-
(1
/BJL [[w, 1|1
2n
20sr 1)
1)
(a)
$ R(w,-1)
+
|1 w--1l" 2 R(w) R(w)-1)
- 1/3
W1 20|22
2n
2
1
B
(1
/
[w w
[/ +
2n
2Csr-1
Vs
=R(w) +
17
|
w.11112
(1 VBJB
[|w.
2
2m
24

---

Optimization over Sparse Pupport-Preserving Sets: Two-Step Projection
B 2C
where (a) follows from the RSC condition, and the fact that 8:-1 N We recall that 1 L,+C Let us define a= Le + 1. Then C' = (ex - 1) and 1y at, Also recall that L..
C
_
We can simplify the inequality above into:
1
[
B[R(ww)))w:=l1 - R(w)
11 w, - VBJE [[|u, w
2n
Othis
+ nB
Css-1
We now take the expectation over w of the above inequality (i.e. we take Ew,,, F):: using the law of total expectation [E[:) = Ew, [B[-/w;-1]]] we obtain:
-
1 artis
Elju wi-1l1 (1- VB)Bilw; - w012 + nB
ER(w:) - R(w)=
(18)
-n
Cst-1
Similarly as in (Liu & Foygel Barber, 2020), we now take a weighted sum over t I,... T, to obtain:
T-t
217
B[R(w:)
R(w)
1
/
3
1
nB
Blle0 w1-1l12 2 (1 /B)EEl w0 20|² +
Ottis
Os
1=1
T
1
T-
1
Bllw 1
/BEE w012
VB
0KK
T-t
BB
3
Cst-1
T-1-1
T-t
1
El 1 w:-1
E Fl: - 1||2
VB
1 /B
T-t
BB
ar,
BB
Cst-1
T
1B
3
aN
|
woll2
E.
WT
w 2
0x 3
Cst-1
t=1
1 omw.,
T
T-t
nB
<(1
V3)
11:0- -wol?
+
Σ
/B
1
/B
Cs
(=1
1
T
T
T-t
BB
[
will?
00
(19)
/B
/B
Cs-11
t=1
where (a) follows from simplifying the telescopic sum.
25

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
We now choose k and 8; as follows: choose & 2 4a²n2k, which implies that:
B - 20di
1
3 S 2cri -1
200 2
1 VB2 2
201ksx
200.s
1
206,
ake v3
S 1
(20)
200hi
And choose 8t with
4ax,
and
T
BB
Let us call v == 2om
Note that we have:
V S W.
(21)
And that we have the inequality below:
V
Zo0
400ks - = 1
1
< 1
w.
(22)
4at, - 4an, -
4aks
Tox.
This allows to simplify equation 19 into:
T
T-t
T
E
27
[((..) R(w)] S vn'1 -woll woll? 2 + Σ
v
T-!
1
t=1
=>²|
wol
t=1
WT
w
w
w
10
(
WT
10
1
2
W
SY
4 W
1
wal
w
W
|| wol ||
+
3 w
1-
1
TT
|1@0 - will 2
+
3
4aksw T
[|00 wp 1|2
4
3
where in the left hand side we have used the linearity of expectation, and where (a) uses equation 22, (b) uses the fact that (since 2 and 2 (indeed, from the theorem's 's assumption
Scary --
I, + 1 with C' > 0)), (c)
C
uses equation 21, and (d) uses the fact that < 1 so 1 < T
26

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Let us now normalize the above inequality:
T-t E -1=1
Σ 1=1
2m
R(we)
woll + 3 4ak,w (1/00 1ww0-wll
1-v3
E
R(w)
21
1-
T-t
Ei= 21)
1- tng 1- v3
T-
1-VB
The left hand side above is weighted sum, which is an upper bound on the smallest term of the sum. Regarding the right hand side, we can simplify it using the fact that 0 <
and therefore:
T-t
21 1.
Therefore, we obtain:
(1/20 4a
wip
1 5)
22xx2 Lighighe" (1v0- woll +
E min R(wx)) R(w)) IE (E.....)
21)
Which can be simplified into the expression below, using the definition of wt:
ER(úr) R(w)) 2a Lokgw"" (ILo woll + 4 3)) 33)
The proof is completed.
Corollary F... Under the assumptions Theorem 4.2, let be small enough positive number > 0. To achieve error (R((wr) - R(w) S using Algorithm 2 the number of calls to gradient V Rg (#IFO), and the number of hard thresholding operations (#HT)) are respectively:
#HT O1s, log( (), #IFO 0
Kis Uye
Proof of Comollar E4. Let E T Let us find T to ensure that ER((0T)
R(w)) S c. This will be enforced if:
2a 2 Iigkguu
(100- woll + Se
- Tlog(w) s log
2a² 202Losta (1120 wo 12
2a2 21gTi (1 wn 1|2 + 4
log
log
Therefore, let us take:
wi 1 + 4) 2a LaKK (1100
T :=
log
(23)
log(
We now derive the #IFO and #HT. First, we have hard-threshe theeshhreeholding operation each iteration, therefore #HT= T. 4an, (since by property of the logarithm, for all
Using the fact that [o [log(w]
-log(1- <
(-oo, 1) log(1 x) S --r), we obtain that #HT O log ()))
27

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
We now turn computing the #IFO. At each iteration we have s gradient evaluations, therefore:
T-1
IIFO
Σ
Σ
+1
wr
t=
=T
T
ST+
w
T
T
+
exp
T log
1
2a Lotis (1/20 woll2 + 21
14
log
)
2o.² Lytii (110 -woll wol2 + +
exp
log
log
+ +11
3 log
E
1
2cx² Litis (1/20 wo 11 + 3)
2a Latis (1120 woll +
=1+
log
log(
1
2xx² Lighi (110-
wp 1| + +
2a 2 Ligkis (1 - 1wol + T
=1 + log(
log
(
=1+ log(1)
1
log
woll? 2 + 4) 2a L,No (1100
8a L (1) 1 wi 1|2 + 4)
3
(b)
1
2a Loti (1/00
woll + 4
1 1+
log
log( 1
B
1
8a L. La
1100 woll 1|
4
+
als La - 1)
Va
2a Liti (1/w 2
woll"
21 + +)
8Ba2k, (1|00 - Ww 12 + 4
1
-1
log
3
log
(a: 1)1₂
where (a) follows from equation 23, and for (b) we recall that r nB 17 al, and C = Iu(a 1).
Therefore, overall, the IFO complexity is in O 2
F.2.3. PROOF OF THEOREM 4.3
We now proceed with the full proof of Theorem 4.3.
Proof of Theorem 4.3. Similary as in the proof of Theorem 4.2 in Section F.2.2, let us take: ; T.. and = C + 1.
T.,
Then C (ax - Lg and 1) at.- Recall that Ks : Le Denote v, H4 (w; (/VRR(( for any E N.
28

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Similarly in Section F.2.2, the -sssmoothness of R implies that
Ls 12 - -12-112
R((,,) SR(w)-1) + (VR((w)-1) wt - -w;-1) +
2
- + (gt 1, - w)-1) + La
- -lw0r - w1-1112 + (VR(wi-1) -t w: - -w 1)
2
-R(w:-1) 1
|1/0 - (w!-1 -191-11)l -1 1/11 11? 1|? ||w, - -0,-11?? + Lg |100 w
24
+ +(VR(w(-1)
9c-1, Wi wi-1)
1
Lis 8
-R(w:-1)
We (w²11 19: 11]2
g 1| +
110: wi-1 11
291
2
2
+(VR((0(-1)
g:- 1:-1, Wi w
(0)
S R(20,-1)
+
1 (w:1 79. 19t-1111 11]1 [W - 2012 + v
/ 0
2013
11
g 11
2m
2
Lo
1
[W: w 112 + (V((w:1)) 9t-11 w0 w1111
2
1
1R(w;-1)+
+
[1]t0
112-1122
1| + 17² g 19:-11 111 - 21 11-1 [)) 21
|0,, t0|²
2n
vB
L 17
+
1100
9
1 +
| - w w1-1l1 112 + (V R((w;=1)) - - Wt wi-1)
21
2
2
vB
-)(
+
[||0 w:-1l
2(11:: W;-1 -wi} 2n
|w T0 +
|| n
(24)
2m
2m
1
+
[w/ 1;-1 112 + (V((w:-1) -
-9i- 9t- wz wi-1)
2
(b)
1
1
+ vB
1(w)-11
+
j 11-1113 (g1-1, Wi-1 - w
-
Ww
2
11; w/|
21
21)
21
La
C
+
[ww w.11 + 2C -) 11-1
(25)
2
where (a) follows from Lemma 3.6 and (b) follows from the inequality (a, b) s aaa + b², for any (a. b) E (Rd)² with
C' >> 0 arbitrary strictly positive constant. Let now take 7) ,. therefore the term L. Iw, w |
above is O. We now take the conditional expectation (conditioned on w which is the random variable which realizations are w,,1), on both sides, and from Lemma F33 we obtaín the inequality below (we slightly abuse notations and denote E|- [W-1 w by B[. w1)
1
E B(R(w:))u < R(w: W +
[1 w
W;-1 - w)
2n
1 E [1/12
vB
B(n 8t-1) 20s, 1)
20
[1]
+
E [[|u, - w///111 +
2m
2n
(a)
1
Us |11-1 16|1?
I R(w;-1)
+
| 11-111 + R(w)) - R(w;
2n
2
1
W [1-1] =] + vB
E [|u. w0 1 [11w--1] + B
E [[]lw
2
2m
27
2Cs
1
+ v3
-R(w) +
7
(
wi
2|2
E
B||W;
[w
w
w/2/
1// 1|
E |||e - 2/1
2
2
2n
B
+ 2C's11'
(26)
29

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
where (a) follows from the RSC condition, and the fact that 8t-1 N
Now recall that we have taken 7) C. and let us define C T, + 1. Then C' == (a 1)L2, and 1 at, Also recall
that Kis Le_
We can simplity the inequality above into:
E [[((w))) [,,-1] R(w)
( (1-
1 OtKig/
nBB
1100 w1-1 -
[||,,
w + v BE [lle -0l 2012120
2nj
Cs
We now take the expectation over w of the above inequality (i.e. we take Ew, P:D: using the law of total expectation [B[:) = E.... B[-|w;-1]] we obtain:
[(11-
BBB
ER(w:) R(w)) 2
E1200 w1-1 - w. w|1 /B 2012 +
artis
Cst-1
Additionally, in view of equation 18 applied at vr instead of ws, (since v, here corresponds to the w, from Section F.2.2, i.c. vr is the hard-thresholding of an iterate after gradient step), we know that:
[1--
Ortig -.1
nB
ER(e.) R(w 2n
Bllw0 w.1111- (1 /B)Bl 2
Cs
We now take convex combination similarly as the case without additional constraint (section E.2), for some p E (0, 1).
B(1 R(w:) + pR(vs)
<R(w)= + 2: ( 1 C115
[E| 10 WT 1122 - -(1 -p)BB| w. - w w0
w1-111
+ ((1-)))
(1-p) p) // - -11 vB1p) El(, w//1 + nB
Css--1
RR(w)= + 2/1 ( ar1
E| 1 -w: wi- 111 - (1 p)lB wi - 20
(p v3)
E
:0/l2 +
nB
Cs
1
(
1
R(w))
+
E
W
||
(1
p)
1/
2m
a11
- (p
/
E
1
+
B
Cs
1
(
nB
R(w) +
E
W: w
VB)Ell
w/12+
2n
C11gg
Cs
where in (b), we have assumed that vB < p (later we will verify that our choice of ensures such a condition), and have used the fact that projection onto a convex set is non-expansive (which implics that ||l 20|2 > w|,, - wl( Similarly as in F.2.2, we now take a weighted sum over = 1, 1,... T, obtain:
30

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
T
T-t
21j
46
B[(1 - p){((w.))))))) + pl((o:) R(w))
1
T-
1
nB
aN.
Bil wr-1l1 - (1 /B)BB w0 201² +
1- VB
Othis
Cs
1 1
--t
1
Blle0 wi 11 (1 /B)BBl x012
1 vB
Othis
T-t
nB
B
C
T-1-1
T-t
=(1
ara
E 1 wt
1|
are vB
Blle, ww
E
T-t
B
aN2
VB
C8
t=1
T
T
T-t
(0)
[1
/9)
ON,
[20
woll
0.2,
BB
VB
VB
Cst-1
t=1
1
T
T
T-t
BB
<(1 33)
-
112
+
vB
1
/3
Css-1
t=1
T-t
B
|100
wa
1
Σ t=1
(27)
vB
vB
Cst-1
where (a) follows from simplifying the telescopic sum.
We now choose k and 8, as follows: we choose & 2 4 4 2 which implies that:
p /B (thereby verifying the assumption made earlier), and that:
VB S
20x 7
1
= B <
2a frke
2a KG - 2
1 K2
(0)
1 vB 2 1
2a fis - 1
20 Kg
K,
K4
ak3
< 1
(28)
/3
2a Kis
where (a) follows from the fact that p S 1.
And we now choose 8t : - with w
and T C
4a N.
Let us call = 20
Note that we have:
V S w.
(29)
31

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
And that have the inequality below:
V
2 Ka
4a Ki -2
1
5
1
w.
(30)
4a
Kg
4a Ki p
4a Ki p
Kis
4a Ko
p
This allows us to simplify equation 27 into:
T
1
T-t
EI
2m
06,
[11 - (1-p) - pR((i) - R(w)
1
v3
1=1
T
<V
S
[
-woll 2
+
1
T-I -T-W"--
1=1
T-
woll
w
w
1
v
1/ - wool'
+
w
w
10 2/
lom
2|
(4)
W
1
ST 10
woll
(2)
10
woll
4
18
lom
2 +
w
(d)
W
1
10 wo
112
1
wT
|100 woll +
1-
4a-Ki,u k,,"
(110- woll +
where in the left hand side have used the linearity of expectation, and where (a) uses equation 30, (b) uses the fact that
- (since 2 and (indeed, from the thcorem's 's assumption C with C > 0), so
p
consequently a 1), (c) uses equation 29, and (d) uses the fact that w < 1 so 1 < T
Let us now normalize the above inequality:
T-t (1 R(w,)) + pR(())
ET 2n
nxc 1-v3
4ax Aa-kisw (1120 wo 12 +
R(w)) +
p
T-t
Σt 21
Σ 21
T-vD
The left hand side above is weighted sum, which is an upper bound on the smallest term of the sum. Regarding the right hand side, we can simplify it using the fact that
and therefore:
I- /B
Σ
axa
> 1.
f
32

---

Optimization over Sparse Pupport-Preeerving Sets: Two-Step Projection
Therefore, obtain:
4a n (110- wall 3)
E
min (1 p)l((w:) + pR((vr) R((Ø) _ (E()))))
21)
2a -o (116 woll
(31)
P
We denote by Er the right-hand side above:
eT 2xx - (l00- woll 2 +
We now proceed similarly in the proof of Theorem 3.7 above. Recall that we have assumed in the Assumptions of Theorem 4.3, without loss of generality, that Rt is non-negative, which implies that R (v=) 2 0. Plugging this in equation 31 implies that:
E min R (w, S R(w) + êT < (1 (1+ I-p
(32)
tE[T]
1-p
Plugging the change of variable E7
Fr into equation 32 above, we obtain that: I-p
E min R (wx)) & (1 2p) R(w) + e'r.
tE/21
Further, consider ideal case where w is global minimizer of R over Bo {w ||w/lo S Then R R(v)) 2 R(w) is always true for all t 2 1. It follows that the bound in equation 32 yiclds:
min {(1 (w.) pR(w)) :E(T)
min {(1 1-1-pp1 ()))))(())) pR((v)3 S R(w) + ST, rE(T]
which implies: E min R (wv.) < R(un) + 57
similarly as above.. The proof is completed. 1-p- this case, we can simply set 0.5, and define 5/ Fr 28T
1-p
F.3. Proof of Corollary 4.4
Proof of Corollary 4.4. We proceed similarly as in the proof of Corollary F.4 Section F.2.2:
Let E I Let find T to ensure that E min.g (1 p)R{(w)) pR(v.) R(w) < This will be enforced if:
2a² Longw (I - wo woll 10 + SE
> Tlog(w) log
2a² L Loti (110 woll + 31)
1
2a L ki (1/20 - wi 112 + $
T >
log
log
Therefore, let us take:
2a L.
(1lw0 woll" 112 2)
T := log(?
log
(33)
We can now derive the #IFO and #HT. First, we have one hard-thresholding operation at each iteration, therefore #HT* T. = 4a 4a K2 (since by property of the logarithm, for all
Using the fact that [o log( log(1
<
40 A0
(-oo, 11) log(1 x) S -r)) we obtain that #HT = O(s log (1)
33

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
We now turn computing the #IFO. At each iteration we have s gradient evaluations, therefore:
#IFO
Σ
+1)
WA
--1
T
1
ST +
1-1
T
1
exp
Tlog
(0)
2a 2aztLst (1/20 woll 5
log
log( )
2
[0 - -woll 2 31)
1 log( 2 log
+
1
exp
log
+ 1
E
1
2a Lisis (1/20 woll + 3)
2a Li
(1/2 w0ol
w0ll || + 5
=14 +
1 log
w
log(?
2a 21 2 (1110 wol 11 + 3)
20 T
1
Lighis (1|00 wp 1| + $)
=1+
log
p
log(2] 1)
w
2a 21 LgNi (1|20 woll? + :)
8a 3 1
L n (120 - woll +
1
=1+ +
log
log( =
E
E
2a 2 L
Loki (1/00 - woll +
log
p
log( !
E
B
8a p² Lo
T.a
4
|100 wol! 20
tis
aLg La - 1)
3
22a21 L (1120
woll
2 3)
8Ba² p² No (1|20 woll? 2 + 4)
=1 log
log(!
(a (a-1)//
where (a) follows from equation 33, and for (b) we recall that 7 the IFO complexity is in O n.)).
nB
C .7 al,
and LL(a - 1). Therefore, overall,
F.4. Proof of Theorems 4.7 and 4.8
Our proof for Theorem 4.8 is similar to the one for Theorem 4.3, though needed to refine some results from (de Vazelhes al., 2022) properly express the variance of the ZO gradient estimator and incorporate into the telescopic sum. Before proving the main Theorem 4.8, below we provide several intermediary results needed for the proof of Theorem 4.8. Then, the proof of Theorem 4.3 will be provided in Section F.4.3.
F.4.1. USEFUL LEMMAS
We first recall the following results from (de Vazelhes et al., 2022):
Proposition F.5 (Proposition (i) (de Vazelhes et al., 2022)). Let us consider any support C [d] of size s ({F) = s). For the 700 gradient estimator 9: Algorithm 3 at uns with qe random directions, and random supports of size 82, and
34

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
assuming that R is bgy 82)-RSS', we have, with [u]s denoting the hard thresholding of vector F (that is, all coordinates not in F to 0):
Eg. [VR(w)))el1 & Enjt
(34)
with Ep == Lag sd
Proof of Proposition F5. Proof in (de Vazelhes et al., 2022).
Lemma E.6 (Lemma C.2 (de Vazelhes et al., 2022)). For any (L -2)- function R. using the gradient estimator 9: defined in Algorithm with Qt = we have, for any support F _ [d], with Fl = 8, and F = [d] \ F:
[[ =F [[V +EP- [[V pm Eabalt
(35)
with: 2d
(s-1) (ا=1)(33-1) +
(i) 6 222+2)
6(e7-1)
(ii) Ep == (#2+2)
d-1
(iii) Eabs = 282
(0-1)(19-1) d-1
+ +1)
Proof of Lemma F.6. Proof in (de Vazelhes et al., 2022).
We now use the above lemma to bound the variance of the zeroth-order gradient estimator gt-
Lemma E.7. The gradient estimator gi defined in Algorithm 3 verifies the following properties for any qe E N
E
g.)
E8
[1) <
EF |VR(w)] +
Eabs 2
(36)
Qt
qt
with E and Eabs defined above in Lemma F.6
Proof of Lemma F.7. gt = 1, we have:
2igdell (0)
E [g]F
B||gg |[[g]]|]
(35)
IA3 1/
EF [F][VR[[))]]]] E VrVel////(WWW/rV
Eass
EF V Eaboff?
where (a) follows from the viri-vari formula E||X - E|x]]1 E |E |3 for a multidimensional random variable X, and (b) follows from the fact that
2d
s((2 - 1)
1
2d
ss32 1)
E
+3 d $2 +
Epp
$2 +2 d
d
-
(since 52 < d), and since [[ || 12
[[
[R(w)) w
[) l| (by definition of the Euclidean norm).
Now, if q: 1, know that the variance of average of qi i.i.d. realizations of random variable of total variance a² is
x² (and its expected value remains the same by linearity expectation): indeed, for any random multidimensional random
35

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
variable X, for which we consider the q i.i.d. random variables X; of same distribution, we have:
1
4:
41
1
20
E
X
E
X
EX,,)
q1
48
2
2
1
4
41
(X; EX)))
Σ
(X; EX,)
10
1
1X EX,11
OF
1
>
| - EXI
9i
1
9h
XX - EX
1 || EXI12
qt
where (a) follows from the fact that X; are i.i.d hence for i + j: Cov (X, Xy) B(x,- ((Xx-EXx) (X,-EX,) = 0. Applying this to the random variable which realizations are [9:]e, this concludes the proof.
F.4.2. PROOF OF THEOREM 4.7
Below we now first present some results (and their proofs) for the convergence of Algorithm 3 without the additional constraint, which needed for the proof of Theorem 4.8, and also, as a byproduct, provides, up to our knowledge, the first convergence guarantee in objective value without system error for a zeroth-order hard-thresholding algorithm.
Proof of Theorem 4.7. Let us denote for simplicity: C₁ == غع C2 == مطمك and C3 := Enpr². Moreover, let us denote F := supp w:) U supp(w;-i) U supp(w), where supp denotes the support of vector, i.c. the set of coordinates of its non-zero components. Note that therefore we have |F| < 2k: + 1e < 3k. addition [u]p denotes the thresholding of u to the support F, that is, the vector u with its components that are not in set to 0.
The fact that R is (Igr, R'S-RSS', therefore also (Is', RSS''' implies from the remark in 4.5 that also , & therefore:
R(ws)
<R(w:-1) + (V[(w:-1),ur wi-1) + Le ww w111
2
=R(w,-1) 1) + (gt-1, wt - -W;-1) + Ls
ww
w 1|2 + (VR(w:-1) -
wz - wi--1) La
1
-R(w:-1) +
||w, (w,-1 - 1191-11
1112 -199--)111
1/2 111lg-111 1|2 || - wi-1
l|we w.-
21
2
+ +(VR(w(-1)
9:-11 Wi wi-1)
Lg 1
-R(w,-1) 1) +
1
w. (w:11 19: 1)]1
11
17
||00
w1-1
2m
2
+ +(VR(w:
gt
1 Fr wi w
(0)
R(w--1) +
1
l1 (w, - ng. 11 - (1 - /B) w. -012]
" 2
11:--11
2m
LLg
1
+
|wm
wi- 1 2| + (V (V - gc-1/F,00 w: wi-1)
2
1
1
=R(w:-1)
+
[||00 wi-1l' 2 7 1 g 112 2(ng:-1, W; wi}
(1 /3)1
w. 1/
2m
2n
36

---

Optimization over Sparse Support-Preservnng Sets: Two-Step Projection
Ls
1
!
g1
?
[w w
-
(V - 9t- we -w;-1)
2
2
R(w
+
1
||100- w/
w111 11? 2(111-1: 110-1-10 -wi]
2nj 11(1 (1 /B) 11,, 2/1
1
2m
Tis'
1
+
|w0:
w/-1 1112 ([[[(w:))) - 10,, w: w;-1)
R(w
+
| i w1-1 1|
(g-- W1-1 20) (1 v /3]l - w0
211
21
Lss
1
C
1
+
|10,
w1-1
11
[[V -1- 11-11
20
1
= R((
+
1000
1 12
(VR(w)-1)) W;-1 - - + (1V ([VR(w;;1)) 91-111r,, (5)
21
L,'' 1 +
1
(1 2n
WB)lw,
10|2+
+
- wi-11 +
[[V((w,,)) - gr-11r113
2
20
where (a) follows from Lemma 3.2 and (b) follows from the inequality (a, b) S C + C' > 0 an arbitrary strictly positive constant.
1 b², for any (a, E (I))) with
20
L, L. |,0, - w,-1| || above O. We now take the conditional expectation (conditioned on We-1, which is the random variable which realizations are wi-1), on both sides, and from Lemma F.3 obtain the inequality below (we slightly abuse notations and denote B( [[|[w:1 w;-1] by [E(||m;;1]):
Let us now choose = L therefore the term
2
E B[((w:)/2x)
1
< <R(w;-1) +
| 1---u -w,-111
wt-1 w
2n
1
(1
/B [||. w|| w| + ((V (VV[(,,))) [g:- W: 11] F. Wi-1 w
21
+ E
[VR(w,-1) 9: 11
20
1
R(
+
j 11 v
R
R(ww- w 1), Wi-1 - 2
21
1
(1- - BB)E
E ||
- i
2 w
+
2 [[ E(g.-1/w,, |]]e
2n
1
+
|w:-1
20112
+
E
[R(w:-)) 1:-1|1 11
2G
20
1
1
= R((w-1) +
+
|
1-
(VR(w:-1)) W w
22
2G
1
(1 -
/
||wl
w/
W
+
[[ 1lg
2n
+ EE [[[VR((;,))) -r-
---1
[1
(6)
1
< R[Ww-1) 1) +
+
w.-1 -V - w
2ty
20
1(1 - B) [lwe - w w +
G
[V Elg. |w, 1]] 1|2
21
+ 20
(2][ ( - Elg
w 11
2|11g-11 11g
37

---

Optimization over Sparse Support- Sets: Two-Step Projection
(31)+33))
1
1
1(
+
+
1
wi-1l1 ( w1-1 w
2g
2G
1
(1 - v B) [||l - 2012/00111 + G =C's
21
1
+ 20
(2Cs 22IlVVR((w-)) )]( 2C222²)
(0)
1
S [R(w)-1) 1)+ +
+
1100 wt w 112 - (V w
221
2G
1 (1
w + G C
/B)L |1|0,
w/
21)
+ 20
(20)
(21lV R( W;
[ + +02/2² + +0a)
(1)
1
R(W)-1)+
+
|10 w/ - wi-1 - w
+
22
2G
1 (1
G
BB)E
[|w|
w 21 + ? C3
2T
+ 20
(201
(2L.) 1212:1100-1--00 -0 2 + 2
|R( +
1
-R(w)-1)
+
+
+
10 -
1w-ww-1 w.-1 11 (VR(w, W1- -w)
2n
2G
C
1
G
(1
B
|||m
w [
+
C3 + c
[ + +O2p² + +Cz)
21
(c)
S RR(w)-1) +
1
+
+
20 1
|10 - w 12 2
R(()) R(w)-11 U/ || - -00
2n
2G
C
2
1
(1
vB) B ||||
w/
+ G Cs + c
_ (2CI/V((0) C2p² + Ccs
27
1
1
12
-R(w)
+
1
+
+
| -i--w-1 w ||
2
2G
C
1
G C3 + ī [2C + +Op + C3)
(1
B)
[||e, - 11?/
+
21
2
(
1 1/3
1
2
<R(w)
+
|| (w--1-11 ||
2G
TC
1
G C3 + ā (2C) (2C]|V + C2p² + Ca)
(1 -
/B)E [||e
w| w
+ 2
(37)
2n
where (a) follows from the inequality (a S Ga² 5
/ 122 for any (a, b) (Rd)² with G > 0 an arbitrary strictly positive
constant, (b) and (c) follow from the inequality ||a + b12 - 2||a|| 12 2| for any (a, (I2)) (d) follows from the fact that R is (Lor,'' RRS'' (Assumption 4.5 with sparsity level s'), therefore it is also (Lo, R2S (e) follows from
the RSC condition, and for (f), we recall that C1 = fr, and we define = - for some w > 1 and 7 > 0 that will be
chosen later in the proof. Recall that we have chosen 7) t. Let us define a =
+ 1. Then C = (a - 1) and C E
Also recall that Kg Lx
We will now choose the constant G and C, in order to simplify the inequality above, such that it matches as much as possible the structure of the previous proofs:
We will seek to rewrite:
(=
1 27
413, c8 (a- 1)aE
1 1)
into:
2G
Gab,
ame,
1
for some a' > 0 (we will seek a' x with a dimensionless proportionality constant for simplicity).
2m
38

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Therefore, let us choose G 4. which implies:
(38)
Gal5'
4ass
And let us choose T = 16 (a-1)
which implies:
4L
(39)
(a 1)LL
4crKss
Therefore, using equations 38 and 39, obtain:
Vs
1
2 L2
1
4L2
1
+
2
2G
C
2n1
Goelg
(ax -
1)aTs
0chis
1
+
2n
Acrkss
400ks
1
1
1
2n
2nj
a'Ks
where for simplicity we have denoted a' 2a.
We therefore simplify (37) into:
[
1
1
1
E R((w))
R(w) -
( w-11l1 (1 V 3) 1|10 - 20 20/2/20111
2m
a'ks
G
(2C + C2p2 + Ca)) taa)
+2m
C3
+
2
We now take the expectation w of the above inequality (i.e. take Ew, [:]: using the law of total expectation [E[:) E.... [B]-/w;-]]] we obtain:
(
1
ER(w::- - R(w) S
Eliu0
w.11 (1 /B)BB/ 2011
(40)
27
G
(2C]]VR((0)| C2p + +s))
+2n
C3
+
(41)
C
Let us call == 2020), we now take weighted sum over
= 2n (gCa _ (2C1 2 + C2p² + C3)) for simplicity. Similarly as in (Liu & Foygel Barber, T, to obtain:
27
B[R(w:) R(w)]
1
1
Ellu0 w (1 - V3)B//w, - 20| + A
1- vB
d'Ka/
1 ni
1
T-t
Ell20 w1-1l1 (1
VB))Bll, - 2012
1 VB
a'Kis
T-t
a'k.
A
3B
T-#+1
T-
1 n'
VB)
Σ
a'k.
E w wi w1 1
w. w
V3
1 vB
R.
A
/
39

---

Optimization over Sparse Support- Sets: Two-Step Projection
T
T
T-b
_ -1-- (B) ()
N2
woll² - 1T - x
+
8' K2
A
1
3
[=1
1 a'
T
T
T-1
5(1 /B)
1120 1001?2
Σ
x2
A
vB
vB
t=1
T-t
a'
1100 1|
+
Σ
d'Ka
A
3
1 VB
t=1
T
1
1
T-t
Ka
1100 woll
+
Σ
a'
27
C3 + C
(2C]|VVR(z)| + +O2u² + 0s))
VB
1 VB
t=
T
T
1
T-t
2 FF [R(ww)]2 + Eabasl + C33 )
d'ka
1100 woll
+
d'k.
27
Ca + C
V3
1 vB
t=
T
T-t 2m
n'ka
1100-
woll
d'Na
2
V
[l + Eabsl" 112
3
1- v3
gt
T-t
a' Na
2n/C3
[ 2
G
+ t
Ka
1100 woll 1| +
Σ
T
(1
a'na
1
T-t 21
2
V
(R(w))
1
vB
Ut
C
t=1
T-t
21l1 2
G
)
+
Eads Cqf
1 3
2
n'ma
T
11:0
woll
1|2
Σ
1
N'Na v3
T-t 2m17
2
V
[R(w))
v3
1
Ut
C
t=1
T-t
o' Ka
EN
G
1
+
Eabs
(42)
1
3
2
C
C
where (a) follows from simplifying the telescopic sum. Let us denote for simplicity Ç := 2n(2er | [R(()]
1 |V
R
and Z = En C 2 + Enge
We now choose ie and qi as follows: we choose k 2 2 which implies that:
vB S 20'ks
VB S 20d 20'15. 1
20' 2
1 a'Ka
VB
20'R's Ki
2a' K5x
2n'R,
a'ke vB
< 1 20'Ks
(43)
We recall that we previously defined q
[T]] 1, with 165 (a-1).
We now set the value of w, to w := 1
4ct Ky
Let us call v = 1- 2n'n, Note that we have:
D S w.
(44)
And that we have the inequality below:
40

---

Optimization over Sparse Support-Preeerving Sets: Two-Step Projection
V
2n'na
4a'Ni his -2 1 4a'k, Ki -1 4a'K3 S 1
40'Ka, w.
(45)
1n'm
This allows us to simplify equation 42 into:
T
T-t [R(w,) R(w)]
E
21
a'N,
1 /3
{ T
T-t
< 5r7 </71100 woll +
0' Kg 3
2n/
1=1
1=1
= =/'|u0 w0ol { W T
T
T-t
a'K.
2012
1
1=1
{ (w"
T
1
T-t
= ~00 wool woll
21
7
1 vB
1=1
ww"
1
T
1 0'
T-t
S 2 20o1?
201
T
vB
(0)
S //| w
1
+
d'k.
2 27 2
1-
vB
(6) 3 _T woll
<
T
T-t
+
T
O'Ka
2n
r3
1-W
VB
T-t
+ {4 T
w
[ 1/
woll
2n
73
3
T-t
(4)
w
wol 2 + 54
|100
21
73
/
w2
(1v0- woll + <
+ Σ
n'Ke
2np 2
73
m=1
(1:00 woll2 + 40' kow T
<
+ Σ :=1
T
1
d'R.
T-1
2n)
vB
where in the left hand side we have used the linearity of expectation, and where (a) uses equation 45, (b) uses the fact that (since Kis and a' 2 (indeed, we have a' 2a 2 I, + 1) with C >>> 0)), (c) uses
- S. S -
equation 44, and (d) uses the fact that < 1 so 1 < ----
Let us now normalize the above inequality:
T-t R(w+)
Σ
T
21
1- mta
4a la'n (11e woll2 + $
1=
V-
E
5 ((w)) +
+ Zp.
ΣT= 2m
1--1 1-
T-t
ΣT= 27
1- -- 1-V3
T-t
1-vB
The left hand side above is weighted sum, which is an upper bound on the smallest term of the sum.
41

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Regarding the right hand side, we can simplify it using the fact that 0 <
ofsa
and therefore:
1-v3
T
T-t
Σ
2 1.
v
Therefore, obtain:
Aot Roww" (1100 (11ö-woll*
woll 2 4C
33
E min R(ws) R(w)) s tE()...)
+ +Zp²
21
4a Lei (1100
45 =Zp2.
woll? 21/
3
Which can be simplified into the expression below, using the definition of upT
ER(WT)) - R(w)) S 4a 1 Tigt"gee" (110 woll? + 45 + Z2²-.
+
(46)
3
To simplify the above result, we recall the assumptions made earlier on: we have chosen
16N,EF (a-1) and G 4
Therefore, to sum up, we have:
Z En
G
2
+ Eabs
=E
V4
2
C
+
Eabe
C
1
1
w 1
4a'Ra
Ç 4ne /nErl|VRR [
C
The last inequality implies: Ç
((w)) L, f
[ 18,
Corollary F8. Additionally, the number of calls to the function R. (#IZO), and the number of hard thresholding operations (#IT) such that the upper bound Theorem 4.3 above is smaller than e + Zy, with e >> are respectively: #HT On, log(?) )) and #IZO O (spR)L.). Note that if 82 d, we have EF (()) Ok)), and therefore we obtain query complexity that is dimension independens.
Proof of Corollary F8, Let e E _ Let us find 7 to ensure that ER(wT) - R((1)= S se+ + Zμ This will be enforced
4nl [
2 kiy (100-wo12+
woll +
SE
3 4kgLo.
Tlog(w) 5 log
402 1. |110 - ||ol= + 4 1 R())
4x L,,
2 Lotki
|1
woll + 1 1 [|
1
4n b,a
T>
log
log(
E
42

---

Optimization over Sparse Pupport-Preeerving Sets: Two-Step Projection
Therefore, let us take:
4a LetKig (120 wo 12
V 4e, Toy'
T:
log
(47)
log( 1
We can now derive the #IZO and #HT. First, we have one hard-thresholding operation at each iteration, therefore #HT T. Using the fact that [ [og(ww
Saci (since by property of the logarithm, for all
Tog(l-
Konay
(-o0,
log(1 1 2) S ), and the fact that C is independent of ris. obtain that #HT O(s,, log (3))
L
We now turn to computing the #IZO. At each iteration we have qe function evaluations, therefore:
IIOO Σ
qt
t=0
+1
T +
-1
T
ST
+
1
T
+ 1
exp
T Tlog
4a Lgitig
(110 wpl1 2 + 4 [
(0)
1
log
log(?) 2)
4a Lo (1:00 wil 1| + 4 [|[|]
1 log
3 In,
1
exp
log
l
+1
4ax Log Nis (1100 1/00==oo12
[[w]]]]]]] 4x,
4a Lig
(110 wool
n/ V R(w) 4x,, I.,
= =1+ log(? 1
log
+
4a Lg (I1i woll? 2 +
4a Lg (110 wull 1I? + 3 4xs, E.'
T
=1+ log(1) 1
log
4a LogLy (I10 woll2 2 + L.
32a Lyr [1|0 woll + [[]V](
L,
-1+ log
log
1
where (a) follows from equation 47.
And we recall that r = 16x,Ep 1 which implies that:
32a Lo [1 woll 3/4 27kek,
(5r
EF
1. + : ) vs
Therefore, overall, the IZO complexity is in (EF n² R Lgr).
43

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
F,4.3. PROOF THEOREM 4.8
Using the results above, we can now proceed the proof of Theorem 4.8.
Proof of Theorem 4.8. Let us denote for simplicity: Ci :- SR C2 مate and C3 := Enpr² Moreover, let us denote
F := supp w;) U supp(w;-1) U supp(w), where supp denotes the support of vector, i.c. the set of coordinates of its non-zero components. Note that therefore we have [F] I 2k + k I 3k. In addition [u]r denotes the thresholding of u to the support F, that is, the vector u with its components that are not F set to O. Since RRS- with s' maxx(82 8), R also s-RSS" and s2-RSS', with Lipschitz constant L.".
Denote 22 (w--1 v R(w:-1)) for any N. The fact that R is (Ly, 8') 3'SSS therefore also (Lv, s)-RSS'
implies from the remark in Assumption 4.5 that it is also (Lw, R)-SSS, therefore:
R(w))
Iss llw, - w111l1
<R(W)-1)+ + (V wi - w(-1) +
2
-R(u0-1))+ + (g: 19:-1, w/ w:-1) + L1 | w 1| + (V R( w. 91-1, wt w1(11
Lg
-R(wL-1)+ 21 [w: (w;-1 19. 11)1- n7² f119:: 11 1,,, wi-1
+ 2
1|,, wi-1l
+(VR(u)-11) 11-1; wt w
Tig 11
-R(w +
|lee (wi-1 19 1]
[9: 11 +
| wi-1 11
27
2
2
+(VR(w)-1)
-h- 1] F, We W.-1)
(a)
2 R(w(-1) +
i (wi-1 11 19)-1)112 -1110 - -10112 + /Bll0 w8|2]]
" 2
2n
LLg
1
+
|w w: 1 1| + ((VR(w,)1) - 9c- Ic-1IF, w0 - w)-1)
2
vB
=R(wi-1)+
+
1 - wi-1 1 1 + 1 g:- 1|1 2, wi-1 - w)]
ww - 2012 +
1
2m
2n
2n
Lg
-2
-2119--111
17
|20, w1-1 1 ([V
g 10-1/F, we wi-1)
2
VB
-R(u)-11) +
10 w 1 12 2(119011, w 20, m0
|,00, - 2 12
1/00
21
211
21
Tig 17
|w; W:-1 112 + (VR(w:-1) -9:-1 |,, wT W;-1)
1
vB
R(w)-1) ) + 2n
|10 w. w:-1 2 (gt- Wi-1 - w
ww
12
+
|0 - 17/12
21
2nj
Tig
C
1|,: wi-1 11 20
V [R((w:1)) 1F
2
=R -R(w--1) +
-
||20 - W,-1 1|
(V 1), wi-1 - w + (VR((::1))
-i--1, Wr-1 w
21)
1
vB
Lo
1 +
1
|| ww
w
12
1/2
|
+
|w:, - wi-111
[ [VR(w;,1) 9:-1
21
2n
2
20
where (a) follows from Lemma 3.2 and (b) follows from the inequality (a, < Ga² + 1 b² for any (a. E ((Rd) with C' > 0 an arbitrary strictly positive constant.
20
44

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
1,- - +C 2
Let us now assume that := +. therefore the term expectation (conditioned on W,-1, which is the random variable which realizations are wt-1), on both sides, and from Lemma E.3 we obtain the inequality below (we slightly abuse notations and denote G[-/w,11 = wt-1] 1] by [i-//=;-1DD:
||w, wt-1 2 above is O. We now take the conditional
[[
<R(w:-1)
_
1
110 w
11 (VI((w:-1); w -w)
21j
1
+ vB
E
[|we woll
w0ll/
[0:11
E [||e: 2 [ (VR((w,))) 1//e-1/r--1 (ice-11l---- 11l w w
2q
2n)
+
E
||[ [[ g1-1)=1 1c11
2C
(a)
1
I (()
+
1 w1 2|
(V R W1 10, W:-1 w
2n
1
vp
EE
[1|w0
/ [ 1]
1
+
E |||0
w 12 /w==1] +
2n
27)
G
|
E
- 1t-
1||||
+
W - -0113 + E
[ - 11
2
2G
20
1
R((w;-1)+
+
+
1/ - W 11 ( [VRw 1), w0;1- -t
2n
2G
1
[11e02 2 [1,1 + vB
G
E
E [||e 1 [,
(V Elg:-1 w; 1|
21y
2m
2
1
+ 2C
[[[vR((,,,)) - ---1 1|
(6)
1
1
< R(w,
+
+
|| w1-1l12
w; w
2n
2G
1
vB
1 [ + G
E
[||w=
w0|l|
wil'
[w
+
E |||e
[[V (
21)
2n
2
1
+ 2C
(21[VR(w,,)))
Eig.-1
[. 1/,,,11l1 || + 2 9. - -El--Eg--- w 1]))l
(34)+
1
1
R(w,-1)+
+
|| -,
1| (VR(w:1)) wi-1 w
2m
2G
+ vB
E |||l w W + G
E
||w0
w1|3
Cs
27)
27
2
1
+ 20
(2C's +
20
V
VR(w,,
)|12 + +2222²
(6)
1
1
R(w, w. 1) +
|| 1 2| (VR(w,))) 1), W;-1 w
2m
2G
vB
G
E
[llere u
2
+
E |||0:
2 w + 2 C3
27
2n
1
+ 2C
(2C1
- [K(w)) |2 V + 20'22² + 20₂)
(d)
1
R(w,-1)
+
|| w. 2| (VR(w,1)) w1-1 w
2m
2G
1
vB
G
E [||we [p012/
+
E [[|
の 2 w: 1| + 2 Ca
27
2n
1
+ 20
(2C1 (2L
IP) + +222μ² + 2C²)
45

---

Optimization over Sparse Support- Sets: Two-Step Projection
1
20
R(
+
+
+
||0 w-u-w,111 w,-1l1 (VR(w;-1), W - w
2m
2G
C
1
+ vB
G C3 -
1 Ō (2C]IIVA(E)| + C2 + C2)
E3
|1|20=
-o11//wo-11
E
||| w| [w:1]
+
21
2n
2
(6)
R(w,-1) 1)
+
1
1
+
L
||
w 1 R(w)) R(w;-1)
W 0
21
2G
C
vB
G
1
E
||eee
10/1//00-11
+
E
|||0
2 w w +
C3 +
(2C/ + C2fs² + Cs)
27
21
2
C
1/8
20
= =R(w)
2G +
||:0 w:-1 2
2
C
1
+ vB
G
1
E
W2
1|
[w,1
E
|||0;
2 W W
C3
(2C +222 + C3)
2n
27
2
C
(
V/
2 L3
((w))
7
+
+
|
W1-1 1
2
2G
+C
vB
G
1 2 C
E
[1 1811/100-11
E
[||e,
w [
C3
(2C/I\VR(w) + C2p² + C3) (48)
2n
2m
Where (a) follows from the inequality (a, 6) - Ga² 1 for any (a. b) E (Rd)² with G > 0 an arbitrary strictly positive constant, (b) and (c) follow from the inequality la + b - 22 + b|| for any (a. b) E (Rd)), ?, (d) follows from the fact also (Iag, 8)-SSS (e) follows from the RSC that (Tyg, s')- 3'S-SS (Assumption 4.5 with sparsity level 8'), therefore condition, and for (f), we recall that C1 εæ, and we define q: - for some w > 1 and T 0 that will be chosen later in the proof.
qt
Recall that we have chosen L.' v,
Let us define
C. 1. Then C = (a - 1) and 1 aL," Also recall that E
L
K5
We will now choose the constant G and C, in order to simplify the inequality above, such that it matches as much as possible the structure of the previous proofs:
We will seek to rewrite:
1 2n
+
123 sE 1)24
-.
into
Gal,"
for some a' 0 (we will seek a' x a, with dimensionless proportionality constant for simplicity).
27
Therefore, let us choose G ,,* which implies:
(49)
GaLs
4ars
And let us choose T = 16e,5F (a-1)
which implies:
4L3
(50)
(a 1)LL2
4ax,
Therefore, using equations 49 and 50, we obtain:
V
1
E
L2
1
4L3, sc
1
71
+
2
2G
C
21
Galls
(a
l)a
OKK
1
1 +
2m
4ari
4axs
aK
46

---

Optimization over Sparse Support- Sets: Two-Step Projection
1
1
1
211
200ks
2nj
af
where for simplicity we denote a' 20t.
We can therefore simplify (48) into:
1
(
1
[[R(w))) wr - R(m)) S
110 w1-1|1
E
[1ler
2n
a' Hig
27
vB
+
E
||
w w1//( [1
2n
G
(2C) (2C1 [ + Cap² (u(²-Ca)
+2n
2
C3
+
C
We now take the expectation over W:-1 of the above inequality (i.e. take Ew, PD: using the law of total expectation
[E[:) Ew.., [[]] we obtain:
ER(w,) - R(w) S 2n
[11-a
[
E w wT 11
1 2nj
E [1|w, w [2]
(51)
a a'Kio
+ 21
||0 - =01
(52)
G C3 + C [2 C3s)
+2n
(53)
Let us call = 2n Cg + a/ [
C2p2² C2)) for simplicity.
This gives:
1 [(1- a' Kig 2n
VB
ER(w..) R(w)) S
E Elw wi wi1 112
E wi
1/
Bl
A
(54)
2n
27
Additionally, in view of equation 40 applied at oa instead of wr, (since u, here corresponds to the w, from Section F.2.2, i.c. v, is the hard-thresholding of iterate after gradient step), we know that:
1 S 2n
Ellu w. (1 V //)E//, w. [/| +A] A [(--d/k=)
1
(R(2) R( w
a'Ks
now take convex combination similarly as the case without additional constraint (section E.2), for some P E (0, 1).
EE(1 - p) R(w:)) + pP((v))
1
11-11
[1 -1-
1 1)
<R(w)= +
Bllw0 w;;i-1 11-1112-
p) - w012
2n
a'ris)
+ (11- (1-pp p)V3 - (1- VB)p
Eliv: w1 + A
1
[ [ (1-
=R(w) + 2n
Ele20 w - (1 p) - 2
a'ka
(p vB)
1 + A
E
12
(6)
1
(1- [1--1 a'ris
1
R(w) +
Ellu0
w. 2 - -D)]B// - w012
2n
- (0- vB)
E El|w, - 2
+A]
1 (
1
w- (1 VB)El/ w/ -
=R(( +
Blll0
21
a'ris)
47

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
where in (b), we have assumed that vB S p (later we will verify that our choice of k ensures such condition), and have used the fact that projection onto convex set is non-expansive (which implies that ||0, eō 2 l|w.
Similarly as in (Liu & Foygel Barber, 2020), we now take weighted sum over t = I,.... T, to obtain:
T
T-t
21
a Nx
[I( - ())((w)) + pR((e)) - R((ō)]
vB
T-t
1
Bl wt-1 12 (1 - B E Wi - w1 + A
1 vB
a'tis/
T-t
1
Bl100 20
wt
12 (1 B E wi 1/
vB
a'Ris
T-1
A
1 vB
T-1+1
T-
1 n'ka
/B)
Blu
wt 1|
E wi
101
vB
1 v 3
T-
A
VB
T
T
1 a'k,
T-t
(1
V3)
wol
2
E
UUT
1 12
+
A
1
vB
1 1-
vB
t=1
1 a'x.
T
T
T-1
<(1 (
10
wo
2
a'ka
A
B
vB
1=1
T
T-1
a a'K.
1 woll
A
1
T
1
T-t
GG
a'k.
18 woll3 ++) V3
a'm
2m
C3 + C 2
(20) [
+ +C2f2 + Ca))
T
1
T-t
G
( EF [R(w))2
n'x
|00 wol! |
dl
2m
- C3 +
2
VB
1-
3
2
C
qt
+ C33
a R.
T
1w-
woll2
+
T Σ
a'm.
1
T-t
2n
2
VR(w)]' 1|2 + Sabell?
3
1- v3
C
1=1
T-
{ + 2
G 2
a'm.
27C3
1
v3
T-t
a
1 woll2 2
++)
Σ
am
2n
2
V
VR(w)) ||
v3
1- v3
T
1
a'ka
vB
2qja
E
G
2
+
1
+
Eaba
Cq.
48

---

Optimization over Sparse Hupport-Preservingg Sets: Two-Step Projection
T
T-t
2n
F
[R(w)) 1|
2
woll
C
T-t
20p
Ep
G
1
Eabe
(55)
2
where (a) follows from simplifying the telescopic sum. Let denote for simplicity Ç 2n(2s [VR(0]
ine
[R
and Z == c c +
Ege.
We now choose k and 8n as follows: we choose k 2 a P R2tk, which implies that:
1
VB S
2 Ke
p
1
v s
2 a Kig
1
2 Kg -2
1
1 - 3 2 1
p
2 K2 1
2 Kig
28
ks
<
1
(56)
VB
2 2 Kig
We recall that we previously defined q:
with 16k; (a-1)-
We now set the value of w, to N ==
w
Let us call v ==
Note that we have:
2
V S W.
(57)
And that we have the inequality below:
4 Kgg -2
V/
2
p
1
1
< 1
w.
(58)
0 Kis
1 63
4 Ks
4
This allows us to simplify equation 55 into:
T
E
2m
Kg
[11 p)l(w))) + +pl(v.) R(w)
1
v
t=
T
T
T-t
5 Sv² |
woll? +
5
Σ
R'R.
27
vB
T
T
T--
T-1
= 1' w
212
V3
T-t
w
= 5"
k'ka
20
1 vB
w
T-t
wr
1
1
<
<v'l 1 wall
Kz
211
(
1 VB
t=1
49

---

Optimization over Sparse Support- Sets: Two-Step Projection
T
T-t
11000
wo
11
2n
w
w
VB
T-t
4 T
v² [00
wol 11
a'ka
2112
7
3
T
1
3 w 11
wol
+
K'K
21 ?
1-
w
10 w0ol 11 +
4
5
Σ
T
T-t
21/2,12
1 w
3
1
w
VB
[=]
1 w
w
|1 - woll 2
+
3
4
5
T
a'
vB
T-1
20
T-1
4 a'
nww=
|100- woll +
5
1
FzF vB
2n
P
where in the left hand side we have used the linearity of expectation, and where (a) uses equation 58, (b) uses the fact that
-- 3/z (since Ka 1 and a' 2 (indeed, we have a' 2a
2 + 1) with C >> 0), so
consequently of 2 1), (c) uses equation 57, and (d) uses the fact that is < 1 so 1 < I-w
Let us now normalize the above inequality:
Ei 21
(1- - R(ws) + pR(vv)]
4 p
1 (1100- 5oom-woll 2 + 1
1-V8
E
S R(w))
+ +Zp2.
Σ 21
T-t
Σ 2n
1- T-VB
T-t
V-V
The left hand side above is a weighted sum, which is an upper bound on the smallest term of the sum.
1-
Regarding the right hand side, we can simplify it using the fact that 0
and therefore:
1 V=
T
T-t
Σ
a'
21 1.
/
Therefore, we obtain:
p 1 (1w- woll? (
E min [(1 p)l((w.) + pl((v.) R(w) 5 1E ().
+ Zu2
211
2 To
(110- unol1 + 45
4
+37
+ 7422,
which can be simplified into the expression below, using the definition of WT.
E min (1 pR(( R(w) s 4 2 Lo (Iw- woll2+ 3
45
+
Zp2
(59)
tE(T]
P
To simplify the above result, we recall the assumptions made earlier on: we have chosen
50

---

Optimization over Sparse Pupport-Preeerving Sets: Two-Step Projection
168,5g
and G v,
(a-1)*
Therefore, to up, we have:
abs
2
E Eab
Z Ex
2
+
C
+
0
=
Eg
1/8
+
C
+
C
1
Kig
F
V
C
Ánc [V
The last inequality implics: &
4x,
Let us denote by er the right-hand side term from equation 59:
ET 4 a² p
Lytiowt (l00- woll2 + 4 4 AnIVVR(a)]1 + Zpu
4kgL.'
We now proceed similarly in the proof of Theorem 4.3 above. Recall that have assumed in the Assumptions of Theorem 4.8, without loss of generality, that R is non-negative, which implies that R (v:) 2 0. Plugging this in equation 59 implies that:
E min R (w)) tE|T
Σ R(w)
1
+
ET + (1
12 $ ( 21 R(w)
+
ET
+
(60)
1
1-
1 -
1 -
Plugging the change of variable 5'7 we obtain that:
sT. into equation 60 above, and redefining Z into Z T-p
(Ex
(
2
+ + + Engo
T-p
uy
E min R (w,) < (1 (() + + + Zx².
Further, consider ideal case where ir is global minimizer of R over (k) {w ||ll S k}. Then R (w,)) 2 R(w) is always true for all /. 2 1. It follows that the bound in equation 59 yields:
min {(1 (w:) + p)(w)) S min {(1 p) (w)) + +R S R(w) + ET: LE[2]
tE[2]]
which implies: E minserr R (w.) < R(w) + Sr similarly as above. The proof is completed.
In this case, we can simply set 0.5, and define 5/ Er.
28T
I-p'
I-p
F.5. Proof of Corollary 4.9
Proof of Corollary 4.9. Let E RT. Let find T to ensure that Eming ((x))) -R(w) Set 2p2
This will be enforced if:
4a Lungow (1 woll2+
4nll 4nl [
3
Lti
+ Tlog(w) S log
4a0 Ligkii
|100 - woll2 + 4 n/ V Ri
3 dr, L,r
4a 21 1
p Lo
|120- woll + 1 V
R R(
1
An. E,,'
T>
log
log(
E
51

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Therefore, let us take:
wull 2 4a L (I/ --wll'll'
4 [ Jrc, Aoo'
log
(61)
log 1
We can now derive the #IZO and #HT. First, we have one hard-thresholding operation each iteration, therefore #HT-= T.
Using the fact that Tog( [ log(w) log(1 sa
? (since by property of the logarithm, for all
(-oc, -1) log(1 2) S ). and the fact that L is independent of ri.. obtain that #HT O log (t))
We now turn computing the #IZO, At each iteration we have de function evaluations, therefore:
#IZO
+1
-T
T
ST.
+
w
7
T +
exp
Tlog
(
4a² 2a2
(1m0
woll"
n11 1 [1 4x, F.,'
log
log(2) (
[o021 21 2 (1120 - wol? 2 + 3
[ ax. Ln.
1 log
1 exp
log
log(
w
+1])
4a p Loy 1is (1100 22
v R(w))
T.,'
1 +
log
log( 2)
4a L Ligitig
(1 - woll dr,
4a2 (10- woll
wlll R( Trat.
=1 + log(t)
log
4 1 Locki
[120 woll 2 An,
4a p Li
(110- woll a {(
L,
1 + log( 1 log
32cr p Lovik 2
+
R(
4r
where (a) follows from equation 61.
52

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
And recall that 16%, EF (a-1))
which implies that:
32 1 pa Tiggnig (120 - woll 1 + 2om
EF
Rg + Kig Rig
))
Therefore, overall, the IZO (query complexity) is in O (5 (EE The proof is completed.
G. Differences Between Two-Step Projection and Euclidean Projection
In this section, we describe the differences between the two-step projection and the Euclidean projection onto the mixed constraints P n Bo (k)). One can encounter several possible cases:
Case (i): the two-step projection (2SP) and the Euclidean projection onto I' (ok are identical (see e.g. Remark 3.1): in that case, the contribution of our paper are on the theoretical side: Theorems 3.7, 4.3, and 4.8 give global convergence guarantee which therefore in this case apply to the usual (non-convex) projected gradient descent algorithm with Euclidean projection.
Case (ii): the 2SP and the Euclidean projection onto the mixed constraints are different: this case can declined into several sub-cases as described below:
Case (a): the Euclidean projection onto the mixed constraint n (oo) is unknown: that case, the 2SP can allow fill such gap, since the 2SP only requires the knowledge of the projection onto which often known and easy do.
Case (b): the Euclidean projection onto the mixed constraint I'n Bo (k) is known, but computationally expensive: in that case, the 2SP can provide a simpler and faster alternative to the Euclidean projection, while still enjoying some convergence guarantees as shown in this paper.
Case (c): the Euclidean projection onto the mixed constraint I n Bo(k) is known and is efficient enough (e.g. when I' belongs to the set of positive symmetric sets such as in (Lu, 2015)). In such cases, it is unclear whether the 2SP can improve upon Euclidean projection since, at the iteration level, using the Euclidean projection is optimal (indeed, (Euclidean) projected gradient descent step minimizes a quadratic upper bound on the objective value under constraints (derived from the smoothness of R)), and the 2SP is therefore suboptimal in that sense (at the iteration level).
H. Experiments
In this section, we provide some experiments to validate experimentally our theoretical results. Our experiments take 2h30 in total MacBook Pro with 2.6GHz 6-core Intel Core i7 and 16GB of memory. Before describing our experiments, provide a short discussion about the settings and algorithms that will illustrate. For constraints I' for which the Euclidean projection onto (k) n r has closed form equal to the 2SP, our algorithm is identical to vanilla non-convex projected gradient descent baseline (see Remark 3.1). In such case, our contribution in this paper is on the theoretical side, by providing some global guarantees on the optimization, instead of the local guarantees from existing work (cf. Table 1). Additionally, there are case in which there exists a closed form for projection onto I'n B (A),, different from the 2SP (e.g. when r Rd. cf. (Lu, 2015)). Although our framework allows us get approximate global convergence results when using the 2SP, still, at the iteration level, gradient step followed by Fuclidean projection (not 2SP) is optimal, since it minimizes constrained quadratic upper bound on R. Therefore, may not expect much improvement of the 2SP over the Euclidean projection in such case, except on the computational side. With this in mind, we provide below the outline of our experiments:
In Section H.I, we illustrate on a synthetic example the trade-off between sparsity and optimality that is introduced by the extra constraint I, and that is balanced by the parameter p.
In Section H.2, we consider a portfolio index tracking problem where the goal is to illustrate a real-life application of our methods.
53

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
In section H.3, we consider multi-class logistic regression real life dataset, to illustrate in more details in partieular the stochastic and the zeroth-order versions of method.
For reproducibility, our code is available at https://githui. wttp://www.....o//e/eeeeeeeeeeee
cmmllmmmm 2025.
H.1. Synthetic Experiments: Illustrating the Sparsity/Optimality Trade-Off
In the section below, we provide a synthetic experiment to illustrate our Theorem 3.7, i... the trade-off between sparsity and
optimality that is introduced by the extra constraint r and that is balanced by p E (0, 0.5). We consider the synthetic linear regression example from (Axiotis & Sviridenko, 2022) (Section E), with the risk below:
1
R(w)
X y
and where X is diagonal with:
ifi h
X = VR if l
if 13:
where I = = 12 (1 + I3 [s(K + 1) + +
1,,s(( skk² + K 1)] for some 2 1 and k 2 1 (we choose = 50 and x = 2, which results in having d = 350), n denotes the number of rows of X, and is defined as
if 1 Kv 46
Y: = VEVI
28
if E 12
if E I3
for some small 8 0 used tie-breaking (we set - We chose such an example as used by (Axiotis Sviridenko, 2022) prove a lower bound on the fundamental trade-off between sparsity and optimality proper to IHT: they use it to show that the relaxation of the sparsity k of the order Q(x²k)) (see also Table is in fact unavoidable for IHT-ttpp algorithms.
Case without Extra Constraints. First, we illustrate our Theorem 3.4 which considers vanilla IHT, without extra constraints. In Figure 2, on the one hand, we plot in blue, for every k E [d], the value of R(wx) where i is the result of running vanilla IHT with sparsity & up to convergence. Then, on the other hand, we go through every value of & E [d], and for each them, we plot point (K( [((w)), where K (k)) denotes the value of & required in our Theorem 3.4, i.e.: K (k) == 4x k, and wh == min [R R( R(r)). Therefore, each of such point R(wzg) constitutes an upper bound on the value of R(20 (k)). as we can indeed observe Figure
177
20
125
15
1.00
R(w)
0.75
0.50
Empirical Curve
0.00
Theoretical Bound
100
Figure 2. Illustration of Theorem 3.4 (i.e. I Rd).
54

---

Optimization over Sparse Support- Sets: Two-Step Projection
Case with Extra Constraints. We now illustrate the influence of the constraint I the problem. We consider for T an Lo norm constraint of radius À > that is: T (w Rd Vi [4], |toa S A]. In this new setting, also go through every value of k E [d]. but this time, each of those values actually defines curve parameterized by p. according to our Theorem 3.7: for each we plot the parametric curve (K p). (1 + 2p) R (īg), where, similarly as above, K (K,, p) denotes the required value of according to Theorem 3.7 (i.e., K (K,, p) 4(1-2) ) and wy := wER |lokk Rt w)), and where ranges in (0, 0.5]. We present the results for several values of À in Figure 7 below. Note that a priori, the curves are allowed to cross, f.e. for a given & on the x-axis, one could have a point from curve of small (i.e. lighter shade of red)
which could potentially also belong to a curve of larger & (let us denote it k)) (darker shade of red), which would necessarily have a larger (let us denote it p'), but for which the overall (1 + 2p') ) R(azg))) could equal to (1 + 2p) R(agg) (since the problem will be less constrained with K' than with k). However, interestingly, this is not the case here due to the simplicity
of the structure of the example. We can also observe that similarly in the case where R the bound is bit tighter in the small & regime (i.e. when & [50, 100)).
3.50
20
3.0
3.00
Theoretical bound for each
Theoretical bound each k
15
2.75
2.5
R(w
R(w)
2.0
10
2.25
2.00
1.50
Empirical Curve
Empirical Curve
0
50
100
150
200
250
300
350
50
100
150
200
250
300
350
k
Figure 3. x == 0.1
Figure 4. X 0.5
Empirical Curve
Empirical Curve
20
20
3.0
15
2.5
-15
Theoretical bound for each
2.0
R(w)
Theoretical bound
R(w)
10
1.5
-10
1.-
0.5
50
100
150
200
250
300
350
50
100
150
200
250
300
350
Figure 5. X
=1
Figure 6. X =
Figure 7. Illustration of Theorem 3.4 (with I' an Eoo hall of radius A).
55

---

Optimization over Sparse Pupport- Sets: Two-Step Projection
H.2. Real Data Experiment: Portfolio Index Tracking
We now consider the following index tracking problem, originally presented in (Takeda al., 2013), and used as well (Lu, 2015; Beck & Hallak, 2016). It is also similar to the portfolio optimization problem presented in (Kyrillidis et al., 2013). We seek to reproduce the performance of an index fund (such as S&P5000, by investing only in few key & assets, in order to limit transaction costs. The general problem can be formulated as linear regression problem:
min (EBo(k))T
|| ||w - y/
(62)
where represents the amount invested in each asset. For each i E [n]] denoting timestep the i-th row of A denotes the returns of the d stocks at timestep i, and the return of the index fund. In our scenario, we seek to limit to value D > 0 the amount of transactions each of activity sector (group) of the portfolio (e.g. Industrials, Healthcare, etc.), denoted as G; í E [c]. We ensure such constraint through an & norm constraint on each group: I {w E R ;i E [e]]l/ ll S D). where wG, is the restriction of to group G2 (i.e. for [d], WG. w if j E G, and 0 otherwise). In our case, y denotes the daily returns of a given portfolio index (e.g. S&P500) for given time period (e.g. given year), and A the returns of the corresponding assets (over sectors) of the index during such period.
Baselines. Up to our knowledge, there is no efficient closed form for the Euclidean projection onto (a nT (although such projection could be done by enumerating all sparse supports sets and computing the restricted projection onto those sets, such method would have exponential complexity), but the two-step projection can easily be done by projecting onto the & ball for each sector independently. We compare one. called "TG + finallIg,", ", consists in only ensuring the constraints in r, followed at the end of training by simple hard-thresholding step to keep the k largest components of un in absolute value, and (b) the second one, called (BGD(BB) + finalllr", consists in running vanilla IHT, followed at the end of training by a simple projection onto I' to keep w in r n By We learn the weights of the portfolio on 80% of the considered period, and evaluate the out of sample (test set) performance on the remaining 20% (shaded area in the figure).
algorithm (FG-HT-2SP) to naive baselines: (a) the first
Datasets.
We compare our algorithms on three portfolio indices datasets:
S&P500: We take & 15 and D 50. y denotes the daily returns from January 1, 2021, to December 31, 2022, and A denotes the returns of the corresponding d = 497 assets (over 11 sectors). We plot our results in Figure 8.
HSI: We take & = 15 and D 1000. y denotes the daily returns from January 2021, to December 31, 2022, and A denotes the returns the corresponding 72 assets (over e 4 sectors). We plot our results Figure 9.
CSI300: We take = 15 and = 100. denotes the daily returns from March 1, 2021 (due to missing values in early 2021), to December 31, 2022, and A denotes the returns of the corresponding 291 assets (over c = 10 sectors). We plot our results in Figure 10.
The data for those three indices is scrapped from the web using the beaut i ful soup library to gather information about the index, and the y yfinance? library to scrap the returns of such stocks during the considered time period. We provide in Table 2 below the respective dimensions of the train-sets used for the experiments (which constitutes, as we recall, 80% of the total dataset).
INDEX
d
S&P500
402
497
CS1300
353
291
HSI
394
72
Table Number of samples (n) and dimension (d) of the training sets for the index tracking experiment
htteppe//ppppt.rrrr/ppeees////ss http//gojeeeoe//eeettttttt ful 4/
http:s:///ithhii com wtt..////aaaassss....mmmmmomm http:///ggthttccccca/arrrrs/s///
56

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
Results. As observe Figure 11, overall, the true index (blue curve) is successfully tracked by our method (FG-HT-2SPP, green eurve), on the train-set of S&0000 and CS1300 and the test-set of HSI and CSI300. Additionally, have observed that for S&P500, our algorithm solution non-zero weights spans 9 of the 11 sectors for the S&P500 index, 7 sectors out of 10 for the CS1300 index, and 3 of the 4 sectors the one for the HSI index. Therefore, such portfolios are well diversified, as successfully enforced by our constraint.
32000
4800
30000
4600
28000
4400
24000
W M
22000
4000
3800
HSI index
FG-HT-TSP
18000
PGDLT) finallle,
PGD(T) finalTaa,
3600
16000
BGD( + finalf
PGD(8) finalnr
2021-01
2021-04
2021-07
2021-10
2022-01
2022-04
2022-07
Pr-zo0
7023-01
2021-01
2021-04
2021-07
2021-10
2022-01
2022-04
2022-07
2022-10
2023-01
Figure
S&P500
Figure HSI
5500
5250
5000
4750
4500
4250
CS1300 index
PG XG-HT-TSP
PGD(N finaln
PGD( finaln,
3500
2021-04
2021-07
2021-10
2022-01
2022-04
2022-07
2022-10
2023-01
Figure 10. CST300
Figure 11. Index tracking with constraints for various indices
On the Verification of Assumptions 2.1 to 2.3: Note that such index tracking experiments verify Assumptions 2.1, 2.2 and 2.3:
Assumption 2.1 is verified since the cost function is quadratic, with a design matrix of size n > d (except in the case of S&P500). As can be expected with such matrices in general, the Hessian 2A is positive-definite (we have indeed verified in our code that it is). Therefore the RSC constant bounded below by Amin where Amin the smallest
57

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
eigenvalue of 2A A. Note that for S&P500, strong convexity is verified since d > however, since we take A 15, with high probability (i.e. unless can find 2k 30 columns of A that exactly linearly dependent), RSC should be verified.
Assumption 2.2 and Assumption 4.5 are both verified since the cost function is quadratic, therefore the (strong) RSS constant is bounded above by A|| where || ||s denotes the spectral norm.
Definition 2.3 is verified since projection onto I' can be done group-wise, and for each group the projection is onto an & ball, which is convex symmetric set (which is support-preserving from Remark 2.4), therefore, overall, I is support-pressrvingg.
H.3. Real Data Experiment: Multiclass Logistic Regression
We now consider the multiclass logistic regression problem with class group-wise l norm constraint follows. We have (u(w) = Ei= mu 1 - 1 {y: = j) log exp(x= w/
ET=1 exp a wx) where yi is the target output of æ; e the number of
classes, and wy is the weight vector specific to class j. addition to the sparsity constraint (k),, we enforce the following additional constraint r {w E F Vjj [c] ||wx ll S D}, for some constant D E Rt,, where p X e, with p the number of features of the samples æ;- More precisely, in such multiclass logistic regression, we seek ensure extra regularization not only on the whole global weight vector w (with the used squared & penalty), but also on each weight vector related to each class (through I),, in order to prevent a potential class-wise overfitting.
Up to our knowledge, there is no known closed form for the Euclidean projection onto such T n (k)).. However, the two-step projection (2SP) can be done easily: once the first projection is done (projection onto (k). i.e. hard-thresholding) and the sparse support S is identified as per Section 3. the projection onto restricted can be easily done since class-wise decomposable, and therefore suffices to project, for each j E [c]. each w, onto the Eg ball of radius D.
We have the smoothness constant L below (see (Böhning, 1992) for derivation):
L mmax
1
I Lexe Texe- c lcld @ X 1
+2Iaax
(63)
2n
Where @ denotes the Kronecker product, Tmax the largest singular value of a matrix, Imxm the identity matrix of size m X m for some m, and 1, the vector [I, 1] e RS.
We consider the dna dataset from the LibSVM dataset repository (Chang & Lin, 2011), and we choose = 0.5, == 10. For the stochastic case take B 3e and for the stochastic and 70 case take 2. Note that in the stochastic case, if the growing batch-size required by Theorem 4.3 becomes larger than n, we keep it fixed to n (i.e. in such case take the whole dataset at each step). In the zeroth-order case, we take μ 1E 6. We set set all other hyperparameters as per Theorems 3.7, 4.3 and 4.8. In Figures 15, 19, 23 and 27, we plot the number of calls to gradient V R, (IFO: iterative first order oracle), and number of hard-thresholding operations (NHT), for various values of & and D (for the zeroth-order case, we plot the IZO (number of calls to the function R) instead of the IFO). We can observe that HSG-HT-2SP allows a smaller IFO than FG-HT-2SP in early iterations, since does not need to compute full gradient at each iteration.
In addition, to illustrate the thcoretical improvement of our results on zeroth-order, even the case where there is no additional constraint, compare in Figures 30, 33 and 36 our algorithm HZO-HT with ZOHT (de Vazelhes et al., 2022), choosing for both algorithm an initial number of random direction as prescribed by our Theorem 4.8, and choosing, for the learning rate, in our case the one prescribed by Theorem 4.8, and for ZOHT, the one prescribed by Theorem from (de Vazelhes et al., 2022) (and in both cases we fix s = 3k as per Theorem 4.8): we can see that, in addition to being able to obtain a convergence in risk without system error, contrary to ZOHT (cf. Table 1), our Theorem 4.8 also prescribes a better (larger) learning rate (i.e. less conservative), leading to faster convergence.
58

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
HTTSS 180 40116
1.05
1.90
190
1090
12239
1080
19223
1755
2000
0
21
0.1
Pigure 12, #IFO
Figure #1ZO
Figure 14. #NHT
Figure Multiclass Logistic Regression 2SP, 50, = 0.5
1.00
1390
150-10752
120
HSO-HTTS
1485
1055
1470
1300
1170
12000
12200
2003
23
36
Figure #IFO
Figure 17. #170
Figure 18. #NHT
Figure 19. Multiclass Logistic Regression with 2SP, 150, 0.5
TO
HTT3P
3.904
1000
1000
190
1/04
12500
0150
1334
Figure 20. #IFO
Figure 21. #IZO
Figure 22, #NHT
Figure 23. Multiclass Logistic Regression with 2SP, = 50, D = 0.01
59

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
1040
180 60116
HTTSS
170
1090
1690
270
1030
1832
2502
12291
In80
19223
1755
2000
286
00
105
Pigure 24, #IFO
Figure 25, #IZO
Figure #NHT
Figure 27. Multiclass Logistic Regression with 2SP, 150, = 0.01
IZO
NHT
M20-HT
H20-HT
1.095
1.095
1.900
1.990
1.085
1.080
1080
1.075
1.075
0.2
0.4
0.6
0.8
1.0
1.2
10
20
40
166
Figure 28. #IZO
Figure 29, #NHT
Figure 30. Multiclass Logistic Regression: HZO-HT ZOHT, l: 50
On the Verification of Assumptions 2.1 to 2.3: Note that such logistic regression experiments verify Assumptions 2.1, 2.2, 4.5 and 2.3:
Assumption 2.1 is verified thanks the added squared lg regularization, which makes the problem strongly convex and hence also restricted strongly convex.
Assumption 2.2 and Assumption 4.5 are both verified since the problem is smooth with a constant as described above equation 63, and therefore such constant also a valid (strong) restricted-smoothness constant.
Definition 2.3 is verified since, since, similarly as in the index tracking experiments from Section H.2, projection onto I' can be done group-wise, and for each group the projection is onto an & ball, which is a convex sign-free set (which is cupport-preservee from Remark 2.4), therefore, overall, is support-preserving
60

---

Optimization over Sparse Support-Preserving Sets: Two-Step Projection
1,100
1.100
ZOHT
ZOHT
1.090
1.090
1.085
1.085
1,080
1.075
1.075
1.070
1.070
166
Figure 31. #IZO
Figure 32, #NHT
Figure 33. Multiclass Logistic Regression: HZO-HT
vs. 7OHT, A = 100
1.100
ZOHT
ZOHT
1.95
1095
1.000
1.090
1.085
1.800
1.000
1.070
1.070
186
Figure 34, #1ZO
Figure 35. #NHT
Figure 36. Multiclass Logistic Regression: HZO-HT
vs. ZOHT, A = 150
61


Reviews:
[{"review_id": "560gDsSuXT", "reviewer": "Reviewer_Rh51", "summary": "This paper considers the problem of  minimizing a function subject to a mixed constraints here two. One of the constraint enforces  sparsity via the pseudo-norm $\\ell_0$ which make this constraints nonconvex and hard to deal with. The try to force the solution to belong into a convex set $\\Gamma$. The authors consider a class of set which are support preserving sets. They define such sets are convex sets for which the projection of a k-sparse vector onto them, preserved the support. To solve the problem, they consider the approach of Iterative Hard Thresholding modified with a two-step projection operator. They claimed to provide global sub-optimality guarantees without system error for the objective value, for such an algorithm as well as its stochastic and zeroth-order variants, under the restricted strong-convexity and restricted smoothness assumptions.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions. \n\nQ1: Assumption 2.3\n\nA1: For Assumption 2.3, we will write it as a definition and state in the theorems that our objects verify such definition.\n\nQ2: The regularity of the objective\n\nA2: For the regularity of the objective, we indeed implicitly assume that the gradient is well defined (otherwise our assumption is void), so we will add this explicitly in the new revision.\n\nQ3: The support set is a Riemannian manifold and Riemannian optimization is not so easy.\n\nA3: I need to clarify that the support set defined as the indices of nonzero parameters, is a discrete set, the subspace corresponding to a support set is a Euclidean space, NOT a non-trivial Riemannian manifold. Thus, the optimization defined on the support set which can be optimized easily in the most cases.\n\nQ4: References\n\nA4: Regarding the related references, we are aware that there is an extensive related literature on proximal gradient descent and its generalizations (such as Riemannian optimization), as cited in our introduction (for instance, we already cite Bolte, Sabach, and Teboulle(2014)), and we appreciate the references you recommend, which are indeed relevant and which we will add in the next revision (for instance we can add [1], [2], and other related references by similar authors). Note however that we did NOT elaborate too exhaustively on such literature, as it actually considers local optimization guarantees such as convergence to local minima or stationary points, which are very different from the global optimization guarantees that we derive in our paper. In a way, our paper is much closer (in terms of assumptions, proof techniques, and results) to papers such as Jain (2014), Zhou (2018), or de Vazelhes (2022). \n\nAs mentioned above, we appreciate the reviewer can double-check the contributions of the paper and reconsider the evaluation.\n\n[1] A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Application, Heinz H. Bauschke, Jérôme Bolte, Marc Teboulle\n\n\n[2] On Linear Convergence of Non-Euclidean Gradient Methods without Strong Convexity and Lipschitz Gradient Continuity, Heinz H. Bauschke, Jérôme Bolte, Jiawei Chen, Marc Teboulle, Xianfu Wang", "claims_and_evidence": "This paper modified the Iterative Hard Thresholding to solve the problem of minimizing an objective $R$ subject to a mixed constraint \n(sparsity and suport preserving sets). The analyzes seems based on an extension of the famous three point identity also know in the Bregman setting to the case  of their projections. They provide global convergence guarantees in objective value without system error for the algorithm above, in the RSC/RSS setting, highlighting a novel trade- off between sparsity of iterates and sub-optimality gap in such mixed constraints setting.", "methods_and_evaluation_criteria": "The theoetical part of this paper recquire a better analysis espcially for each algorithms of interest. Thus, the numerical simulation, benchmarks datasets set are not very relevant if the  Theoretical part is not so rigourous.", "theoretical_claims": "We checked the correctness of the  proofs of this paper. The main Claim are stated in Theorem 3.4, 3.7, 4.2, 4.3, 4.7 and 4.8.\nIn line 153, it shoud be written Definition 2.3 instead of Assumption 2.3. The authors of the paper did not provide no direct assumption on the regularity of the objective before starting imposing Lischitz continuity of the gradient or strong convexity. \nThis result are not so general as you claimed. Not that the support set is a Riemannian manifold and Riemannian optimization is not so easy. Each extension  are not so obvious and each time you  take $\\Gamma=\\mathbb{R}^d$ and thus doing Riemmanian optimization.\nYour two step projection is just Alternating projection and you check authors such as  Bauchke.", "experimental_designs_or_analyses": "Not interesting if the theoretical part is not so well proved.", "relation_to_broader_scientific_literature": "Regarding your three point identity you should cite Teboulle, Chen and Bolte.", "essential_references_not_discussed": "Teboulle, Chen and Bolte", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "I strongly suggest to the authors to rewrite the paper and consider to start analysing properly the deterministic case of the problem for one paper.", "questions_for_authors": "Have you consider study in detailed just one case ?", "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": "", "extra_scores": {}}, {"review_id": "v9dBEOvhgm", "reviewer": "Reviewer_EgPU", "summary": "1. This paper considers a variant of IHT that addresses sparse optimization problems while incorporating additional convex constraints.  \n2. The authors propose a two-stage projection gradient method.  \n3. They evaluate the effectiveness of these approaches under both stochastic and non-stochastic settngs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional question.\n \nRegarding the comparison with the coordinate-wise optimization method by Beck et al., we cite that paper in our paper but do not compare our convergence rates in detail with it, as Beck et al. only give local convergence guarantees: they analyze properties of stationary points. Regarding an experimental comparison and whether the algorithm of Beck would be better than our algorithm empirically, we can consider 3 cases: \n1) (See also the related Appendix F, Case (ii, a) and (ii, b)) The sets considered cannot be tackled by the algorithm from Beck. In such a case, it can happen that our algorithm can tackle them: this is the case for instance in our experiments in Appendix G.2. There, our algorithm provides an advantage.\n2) (See Appendix F, Case (ii, c)) The sets considered can be tackled by Beck et al. (such as for sign-free symmetric sets): in such a case, the algorithm from Beck is expected to perform better than our algorithm as it is itself an improvement on projected gradient descent (PGD), and PGD is itself likely to be better than our algorithm at least at the iteration level, as we describe in Appendix F, Case (ii, c). \n3) (See Appendix F, Case (i)) The sets considered are such that the two step projection IS equal to the euclidean projection: similarly, in that case, the algorithm of Beck is expected to be better, at least at the iteration level, as it is an improvement over projected gradient descent.\n\nBut note that in cases 2 and 3 above, the contribution of our paper is still present on the theoretical side: we do not pretend to provide a better algorithm, but rather, we give global guarantees on the result returned by the algorithm. Then one could run both our algorithm and Beck’s algorithm, and if Beck’s algorithm returns a better function value than our algorithm, our global guarantee will also of course also apply (as it is an upper bound on R) to the output of Beck’s algorithm, which can potentially be useful in various applications where having guarantees on sub-optimality is important.\n\nRegarding the relaxation of the sparsity k, note that this presentation of results is classical in the literature of IHT with global guarantees, as in the works of Jain et al. (2014), Zhou et al. (2018), and de Vazelhes et. al. (2022). It was also recently proven in Axiotis & Sviridenko, 2022) that such relaxation is unavoidable for IHT (which makes sense as a “true” global guarantee is impossible to obtain due to the NP-hard nature of the problem), as we recall in our Remark 3.5. However, one way to read the results which is maybe more informative, is to consider the sparsity k of the iterates fixed, but to accept that the right part of the upper bound on convergence contains a term in $R(\\bar{w})$, that is, an “optimum function value” for an iterate $\\bar{w}$ of smaller sparsity. Therefore our bounds (and similar bounds in the literature) are actually bounds on the iterates of our algorithm, but it is just that the “reference point” is an optimum of a more constrained problem: as such it still offers some guarantee on the actual iterates of the algorithm.", "claims_and_evidence": "yes.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I have reviewed certain sections of the proofs.", "experimental_designs_or_analyses": "A comparison with state-of-the-art approaches is lacking.\nI suggest the authors compare their method with the coordinate-wise optimization techniques proposed by Amir Beck et al.", "relation_to_broader_scientific_literature": "This work builds on seminal contributions to sparse optimization, particularly iterative hard-thresholding (IHT) as presented in (Jain et al., 2014; de Vazelhes et al., 2022), which demonstrated strong global convergence guarantees.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**  \n\n1. This paper is generally well-written and provides a clear presentation of the current state of art.  \n\n2. The authors propose a new IHT-style algorithm which is based on two-step projection methods.\n\n3. Their theoretical results establish global convergence of the objective value and provide a new bound on the solution’s sparsity of order $\\mathcal{O}(\\kappa^2 \\bar{k})$, which improves upon existing methods.\n\n  \n\n**Weaknesses**  \n\n1. This work, building on Jain et al. (2014), focuses on deriving tight bounds for the sparsity level $s$ without introducing much error in the objective value. However, there is a noticeable gap between theory and practice. In practical applications, we typically aim to obtain a $k$-sparse solution, where $k$ is a fixed integer specified by the user. As a result, additional objective error is inevitably introduced. This discrepancy makes the theoretical guarantees provided in Theorems 3.7, 4.3, 4.7, and 4.8 less compelling or meaningful in real-world settings.\n\n2. The authors consider a $k$-sparsity constrained problem, but there is no theoretical guarantee on the objective value bounds for a **fixed** sparsity $k$, even when $k$ is allowed to be an arbitrarily large constant.\n\n3. The authors should benchmark their approach against Amir Beck’s coordinate-wise optimization method, a strong baseline, especially for the portfolio index tracking problem.", "other_comments_or_suggestions": "No", "questions_for_authors": "NO", "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": "", "extra_scores": {}}, {"review_id": "f3CaNrDo0p", "reviewer": "Reviewer_A66t", "summary": "This paper studies with the problem of optimizing a convex function over the intersection of a sparsity ($\\ell_0$) constraint and other convex constraints $\\Gamma$. The additional constraints are required to be support-preserving, i.e. such that any orthogonal projection onto $\\Gamma$ preserves the support. This is important, since otherwise projection can blow up the number of non-zeros in the solution.\n\nThe authors present an analysis of an iterative hard thresholding (IHT) variant for the above problem, which applies a two-step projection -- first apply the sparse projection, and then $\\Pi_\\Gamma$. Typical IHT analyses from previous work guarantee a solution with $k = O((L/\\nu)^2 \\bar{k}^2)$ non-zeros (i.e. $||w||_0 \\leq k$), where $L, \\nu$ are the restricted smoothness and strong convexity parameters of the function being optimized and $\\bar{k}$ is the number of non-zeros of the target solution. In addition, the objective value can come arbitrary close to the optimum, i.e. $R(w) \\leq R(\\bar{w}) + \\epsilon$ for any $\\epsilon > 0$.\n\nIn the authors' analysis, adding the support-preserving constraint changes the objective bound to\n$R(w) \\leq (1+\\rho)R(\\bar{w}) + \\epsilon$ with $k = O((L/\\nu)^2 \\bar{k}^2 / \\rho^2)$. In addition, the authors extend their analysis to the stochastic and zero-order optimization settings. The proof technique builds upon the work of Liu & Foygel Barber 2020 by incorporating the additional convex projection at each step.\n\nThe authors present some syntethic and real experiments to validate the benefit of projecting at each step instead of a cruder post-training projection.\n\nOverall, I beileve the direction of incorporating projections into the results from sparse optimization literature is a theoretically and practically relevant question, as I do not believe it is well understood how well sparse projections interact with other projections. On the other hand, the factor $\\rho$ is undesirable and weakens the result. I also like the stochastic extension although I did not read it carefully.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Though we leave a more insightful and in-depth investigation of the tightness of our bound in terms of $\\rho$ to future work, the main reason why there is a dependence in $\\rho$ is that the original three point lemma is not valid anymore, and an extended version needs to be done, which contains an extra term, see our Lemma 3.6 compared to Lemma 3.2. This extension that we come up with, and the corresponding proof technique that we use in Theorem 3.7, comes from the difficulty to directly characterize the expansiveness coefficient of our complex mixed constraints. We don’t know if such a general characterization would be possible though, but we leave that for future work, since we believe this would be beyond the reach of this paper: such characterization would mostly likely be very complex, as already the vanilla $\\ell_0$ three points lemma itself relies heavily on very specific properties of projection onto a sparse constraint. For more details, please check our proof which relies mostly on Lemma 2 from Liu and Foygel Barber, itself making heavy use of the sparsity structure of the set and relying on advanced tools such as the Borsuk-Ulam theorem (cf. proof of Lemma 2 in Liu and Foygel Barber et. al.).\n\nRegarding the SP500 experiment, this baseline is indeed interesting and we will add it in the next revision. \n\n**Other comments and suggestions:**\n\nNon-support preserving projections: this is an interesting question, we believe if one is able to quantify the amount of expansiveness induced by such sets (i.e. the modification of the constants in our three point lemmas), then one will be able to reuse our proofs for the most part.\n\nWe agree that it would be best to mention Axiotis et al in the Intro, we will do so in the next revision. Indeed, it would be interesting to modify the algorithm of Axiotis et al to work with the constraints in our paper, though we leave this for future work.\n\nYou are right, 2-SP is a better name, we will adapt the next revision accordingly.", "claims_and_evidence": "In general the claims look correct to me, although I did not check the stochastic and zero-order sections.\n\nOne observation is about the necessity of $\\rho$. I don't see a fundamental reason why the $\\rho$ dependency on the sparsity should be there. Perhaps this is confirmed by the experiments in the appendix that show that the actual bounds are far from the theoretical predictions. The dependency is undesirable, since to get down to additive $\\epsilon$ error, the sparsity blows up by $(R(\\bar{w}) / \\epsilon)^2$, so practically speaking it's not possible to get to arbitrarily small error. If the authors disagree and have a concrete reason why this dependency is necessary, I would be interested to hear that.\n\nBy the way, another way to rephrase the main result (maybe add as Corollary), is by adding an $\\ell_2$ regularizer to the objective: $(\\rho R(w^*) / ||w^*||^2) ||w||^2$. This will not change the result qualitatively (it will only add additive $\\rho R(w^*)$ error), but allows getting rid of the RSC requirement, since the objective is automatically $(\\rho R(w^*) / ||w^*||^2)$ - RSC.", "methods_and_evaluation_criteria": "This is mainly a theory paper. The synthetic and real tasks (e.g. SP500 sparse prediction) make sense to me.", "theoretical_claims": "I checked the soundness of the claims and skimmed the proofs in Section 4. They look correct to me.", "experimental_designs_or_analyses": "I believe that the baselines used in the SP500 experiments could be improved. For the intersection of $\\ell_0$ and the cartesian product of $\\ell_1$ balls, I believe the following $\\ell_1$-based projection might be worth comparing against: Prune entries iteratively by in each iteration pruning 1) the smallest entry that is in a violated $\\ell_1$ constraint and 2) the smallest entry overall, if there are no violated constraints. I expect that a slight tweak of this method will also be the optimal $\\ell_1$ projection.", "relation_to_broader_scientific_literature": "The authors build on top of a series of works analyzing the IHT algorithm by Jain et al, Liu et al, etc. Their contribution is technical, and has to do with simplifying and modifying the core ideas from these analyses, as well as applying it to stochastic and zero-order applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is very well written and easy to follow.", "other_comments_or_suggestions": "- Are the results extensible to non-support preserving projections under some assumptions? Is it possible to define a soft version of non-support preserving projection and have the analysis still go through?\n\n- The authors could mention the main result of Axiotis et al 2022 somewhere in their intro. While it is not analyzing vanilla IHT, it is relevant enough that it should be added to the context IMO. In the future it could be also interesting to see if the authors' results are compatible with the results from that paper.\n\n- I would optionally suggest naming it 2-SP or 2SP instead of TSP, since the latter points to the traveling salesman problem.", "questions_for_authors": "Added above.", "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": "", "extra_scores": {}}, {"review_id": "uORxOAEBNH", "reviewer": "Reviewer_PBWr", "summary": "- Introduce TSP (projected version of IHT) with iteration rule:\n$$\\omega_{t+1} =  \\Pi_\\Gamma \\circ \\Pi_{B_0 (k)} (\\omega_{t} - \\eta \\nabla R(\\omega_{t}))$$\n- Introduce three-point lemma for hard thresholding $(\\Pi_{B_0 (k)})$:\nIf $\\bar \\omega \\in B_0 (\\bar k)$ then \n$$\\|w-\\bar w\\|^2 \\ge \\|\\Pi_{B_0 (k)} w - w\\|^2 + \\|\\Pi_{B_0 (k)} w - \\bar w\\|^2 - \\sqrt{\\beta}\\|\\Pi_{B_0 (k)} w - \\bar w\\|^2$$\nWhere $\\beta = \\frac{\\bar k}{k}$ and $\\bar k \\le k$\n- Provide global convergence guarantees for different versions of TPS (deterministic, stochastic, zeroth-order) in special settings: restricted strong convexity and restricted strong smoothness on objective (standard), and support-preserving set on constraints (new, says that projection onto $\\Gamma$ can't make a zero-coordinate suddenly non-zero)\n$$supp(\\Pi_\\Gamma w)\\subseteq supp(w)  \\quad  \\forall w\\in B_0(k)$$", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thanks a lot for your review and appreciation of our work. Regarding practical problems which satisfy the new condition but did not satisfy conditions considered previously, actually our example on portfolio optimization (in appendix G.2) with sector-wise constraints, is such an example: it is not a symmetric convex set, as one cannot ensure that a point from the set remains in the set if we swap its coordinates. As we describe in such an example, such a set does not admit a closed form for Euclidean projection onto it, and our two-step projection allows us to tackle it. As for examples of sets which do NOT satisfy the condition of support-preserving sets, a simple example is a hyperplane which does not contain the origin: in such case, the projection of a k-sparse point onto onto $\\Gamma$ can be dense in general, hence the support of the point after projection may not be included in the original support of size k of the initial point.", "claims_and_evidence": "I checked Section D of the Appendix and found no problems there.", "methods_and_evaluation_criteria": "The paper is mainly theoretical, but the empirical validation in Seciton G2 and G3 made sense.", "theoretical_claims": "I checked Section D of the Appendix and found no problems there.", "experimental_designs_or_analyses": "I checked Section G of the Appendix and found no problems there.", "relation_to_broader_scientific_literature": "This work is a generalization of the previous results on sparsity-constrained optimization, which is by itself a subfield of non-convex optimization. \nIt provides with a valuable addition to the family of hard thresholding algorithms. The alternative methods involve regularization-based approaches and approaches through mixed-integer programming. The paper does not make direct comparisons to the methods outside of its realm.", "essential_references_not_discussed": "I am not aware of such literature.", "other_strengths_and_weaknesses": "The work is original, presents an elegant algorithm that is simple to understand and implement. It provides with a readable explanation of complex results.", "other_comments_or_suggestions": "Authors relaxed the assumptions on the constraint set $\\Gamma$ in their guarantees. For me, as a reader, it would be interesting to learn which of the practical problems satisfy the new condition (support-preserving set) but did not satisfy the conditions considered previously (\\ell_\\infty ball, symmetric convex sets). It would also be interesting to understand which of the practical problems do NOT satisfy the condition of support-preserving sets.", "questions_for_authors": "No questions", "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": "", "extra_scores": {}}, {"review_id": "IFQ6cwIOkN", "reviewer": "Reviewer_ezfv", "summary": "This paper studies a variant iterative hard thresholding (IHT) algorithm for minimizing a smooth objective over support-preserving constraints. The constraint is expressed as the k-l_0 pseudo-ball and a support preserving convex set. In the proposed variant of IHT, the orthogonal projector is approached by the composition of the projector on the sparsity l_0 constraint and then that on the support-preserving one. The paper provides convergence guarantees on the objective value in the deterministic and stochastic (with a finite sum structure) settings, as well as with a zeroth-order oracle, relying on the restricted strong convexity (RSC) and restricted smoothness (RSS) assumptions. The main technical result of the result is a firm quasinonexpansiveness result of the approximate (two-step) \"projector\". Once this is done, the proof techniques are rather standard.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions.\n\nRegarding terminology and prior work, by “global convergence” we don’t mean convergence to a global minimizer (which is intractable due to NP-hardness), but rather a global optimality guarantee—a bound on $ R(w)$ for iterates of sparsity $k$, in terms of $R(\\bar{w})$, where $\\bar{w}$ is a global optimum under sparsity $\\bar{k}$ (with $k > \\bar{k} $, as standard and necessary per Axiotis and Sviridenko, 2022). We agree the term “global convergence guarantees'' is misleading and will replace it by \"global optimality guarantees\"\n\nRegarding the theoretical claims:\n\n1. You're right that one can derive results on the iterates with system error from guarantees on $R$ without system error, but the reverse is not true. So in IHT literature, results on $R$ without system error are considered stronger — e.g., Zhou et al. use complex support analysis to get such bounds. A main contribution of our work is to (a) simplify their proof and improve constants, and (b) extend it to the zeroth-order setting, which is harder due to gradient bias, using a new three-point lemma framework (also adaptable to extra constraints).\n2. We agree it's helpful to add sample complexity bounds (in terms of $k$), e.g. for Gaussian designs. We’ll add this in the appendix using known results like those after Theorem 3 in Jain et al. (2014). Since our conditions on $k$, $\\bar{k}$, and $\\kappa_s$ are as good or better than prior work (see Table 1), our sample bounds will follow.\n3 and 4: Thanks — we will revise the theorems (as noted also by reviewer Rh51), and add the missing sign constraint: $l_i \\leq 0$, $u_i \\geq 0$.\n5. Regarding the three-point lemma: in the convex case, multiple versions exist (e.g., with Bregman divergences). But in the non-convex setting (e.g., sparsity projections), the literature is more limited. We cite Foygel-Barber et al., who discuss expansiveness (related to your mention of firm quasi-expansiveness), but their results are in deterministic settings with simple sparsity constraints. We extend this to extra constraints $\\Gamma$ and to stochastic and ZO cases, with new tweaks (e.g., handling variance and bias in ZO gradients, combining inequalities to control the tradeoff via $\\rho$). If there is relevant operator theory literature handling non-convex expansive operators, we’d be very interested and happy to revise our claims accordingly.\nWe’ll briefly mention the operator theory connection when introducing the lemma, but note that expansiveness is a key challenge in our setting.\nThanks for suggesting the Blumensath citation — we’ll add it in the revision.\n\n\nComments and suggestions: \nThank you — we will incorporate them in the next revision.\n\nAnswer to Questions: \n\n1. Yes, Lemma 3.6 is key, but other novelties lie in how we combine inequalities to derive our bounds (see also reply to 5) above).\n2. While we don't detail $L_s$ estimation, one can use the (unrestricted) smoothness constant (when it exists), or indeed, known bounds from random matrix / compressed sensing literature.\n3. In vanilla IHT, $R$ is non-increasing (as gradient step + euclidean projection minimizes the upper bound induced by RSS), so the last iterate is bounded. But with extra constraints (in which in general TSP $\\neq$ EP) or stochastic gradients (which are not the true gradient), we lose this property. Hence, Theorems 3.7+ bound the best iterate. Bounding the last one may be possible with extra work and slightly worse constants, which we leave to future work.\n4. You're right that the assumption (though common in many SGD papers) doesn’t always hold, though it does in common cases like logistic regression or ball-like $\\Gamma$. Relaxing it is a good direction for future work, potentially using recent advances in stochastic optimization.\n5. Although Zhou et al. prove a similar result, we include ours because (a) our constants are better, (b) our proof is simpler and fits our general framework. The batch-size schedule is classical in stochastic IHT, where the learning rate cannot be decreased due to projection expansiveness. Better use of the finite-sum (e.g., via variance reduction) is interesting, but non-trivial in IHT — we leave that for future work.", "claims_and_evidence": "Overall, the claims and proofs are correct as far as I can tell. Some rewriting of the main statements would deserve some rewriting (see below). However, the terminology \"local convergence\" for some cited works (i.e. those based on KL inequality) and \"global convergence\" for the current work are misleading and even unfair. The authors probably mean \"convergence to a global minimizer\" when mentioning \"global convergence\".  Actually, not only the other works are much more general, but they also prove GLOBAL convergence of the iterates to a stationary point, which is not a necessarily a global minimizer. However, they do not need the RSC condition required by the authors, while this condition is known to get rid of spurious critical points. On the other hand, the authors speak of their global convergence guarantees. In fact, they are giving only guarantees on the objective value and more precisely on the best iterate, which is not what is termed global convergence of an optimization algorithm. Moreover, they did not state anything about the convergence of the iterates, though I think this would be straightforward from the RSC.\nThe paper also lacks some motivating examples that justify their generalization beyond sign-symmetric sets, and the discussion in the paper is not compelling in this respect.", "methods_and_evaluation_criteria": "The paper is theoretical and discussion/comparison to related work is comprehensive enough as in Table 1.", "theoretical_claims": "Overall, the claims and proofs are correct as far as I can tell. \n1) One can have statements on the iterates themselves using RSC, though probably with a system error term but this is not done here. In this respect, the discussion to the work of Vazelhes et al., 2022 is not really fair.\n2) The authors should discuss sample complexity bounds under which RSC and RSS hold true (though these are known results).\n3) The statements of most theorems (e.g. Theorem 3.4, Theorem 4.2, 4.3 and others) should be rephrased. Indeed, assumptions are stated before the quantities they use are defined, which is done later, and the assumptions are not stated in the correct order, etc.\n4) Remark 2.4: the first example CANNOT be true in general as the projection can become dense if the hypercube does not contain the origin.\n5) In the beginning of Section 3.2 and throughout the manuscript concerning the \"three-point lemma\": this is known as firm quasiexpansiveness in operator and fixed point theory. The authors state that this is their main theoretical finding (in fact Lemma 3.6), and once this is done, the rest of the proof follows the same pattern as what has been done in the literature. In this respect, I was not convinced by the originality of this paper (which is still 60 page long) especially for a top venue such as ICML.", "experimental_designs_or_analyses": "The paper is only theoretical and no experiments are reported.", "relation_to_broader_scientific_literature": "The discussion of the literature is good enough though one key paper is missing (see hereafter). The relation to theory of (firm) quasinonexpansive operator theory is also missing.", "essential_references_not_discussed": "On of the first (if not the first) papers on IHT is that of Blumensath and Davies in 2008. It is surprising not to cite this seminal work.", "other_strengths_and_weaknesses": "Strengths:\nMostly well written with solid results. \n\nWeaknesses:\nNovelty and lack of motivation.\nOverstatements.", "other_comments_or_suggestions": "1) It would be wise to state that problem (1) is assumed to be well-posed from the very beginning (typically R is bounded from below and the set of minimizers is non-empty).\n2) Algorithm 2: in the last line \"=\" should be an inclusion to remove any ambiguity.\n3) Foygel Barber is also cited as Barber. The former is the appropriate one.\n4) Page 3: \"the derivation a variant\" -> \"the derivation of a variant\".", "questions_for_authors": "1) The \"three-point lemma\" (in fact Lemma 3.6, whose proof is a few lines) is claimed as the main technical finding and the crux of the other proofs. But once this is done, the rest of the proof follows the same pattern as what has been done in the literature. Could the authors argue what is really challenging then ?\n2) How to estimate L_s and thus implement your IHT algorithm as the stepsize \\eta depends on it ? Generally, one can do this with random sampling/design operators using random matrix theory results. \n3) In Theorem 3.7 and others: What is the deep reason behind going from a uniform bound on the iterates to the best iterate here compared to IHT, i.e. the case where \\Gamma is the whole space ?\n4) Assumption 4.1: This is not always realistic, e.g. MSE loss wich is very standard in sparse recovery. \n5) Theorem 4.2: why putting a proof if it is already in Zhou et al., 2018. Moreover, the condition on the batch size is really weird. It means the the batch size has to increase exponentially with iteration, while the objective is in a finite sum. This means that the finite sum structure has no particular interest or role in the analysis. Same for Theorem 4.3. Could the authors comment on this ?", "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": "", "extra_scores": {}}, {"review_id": "1VDEXBgfOP", "reviewer": "Reviewer_2cef", "summary": "Refer to the abstract.\n\n## update after rebuttal:\nFollowing the discussion I updated my recommendation to weak-reject (from rejection).\nI am still not convinced that the contribution is sufficiently solid.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thanks a lot for your comments, we hope the answers below can address them, and we remain at your disposal for any additional questions.\n\nRegarding examples of problems satisfying the assumptions, note that we provide in Appendix G.2 and G.3 several examples, and also write there why such examples verify our assumptions.\n\nRegarding the assumptions, actually, by definition, we will always have $L_s \\geq \\nu_s$ (and we can never have $\\nu_s < L_s$), as the (restricted) smoothness characterizes an upper bound on the function and the (restricted) strong convexity characterizes a lower bound on the function. Therefore we believe that there is no such degenerate case as you mention and we believe our analysis still remains relevant.\n\nRegarding the end of your comment, we note that $\\bar{k}$ is not actually the sparsity of the optimal solution of the original problem (with k-sparse constraints): $\\bar{k}$ is actually an arbitrary number (smaller than k) that is found such that the condition on $k$ is valid, typically $\\bar{k}$ is taken as large as can be, but not larger. We agree that such results with $k$ and $\\bar{k}$ are more complex than usual results in optimization, but such compromise with $k$ and $\\bar{k}$ is unavoidable for IHT-like algorithms as proven recently by Axiotis & Sviridenko (2021; 2022), and it is standard in the literature of IHT (see Table 1). Please see also the end of the answer to reviewer EgPU on how to read and interpret such results.\n\nRegarding the weaknesses: \n\nIn the case where there is no constraint $\\Gamma$ (but note that there is still the sparsity constraint, which makes this case still far from trivial), we still improve upon the state of the art: in the stochastic case our constants are better than Zhou et al., and in the zeroth-order case we are the first to be able to obtain a bound on $R$ without system error, improving upon de Vazelhes et. al. (2022).\nRegarding RSC and RSS, we agree that these are somewhat restrictive, but our experimental section with the details on why we verify such assumptions, and the fact that there is a large literature on RSC and RSS problems, should make our setting still relevant.\n\nFinally, regarding the length of the paper, we agree that it is long especially in the appendix, however this is just for sake of completeness, for the case where one would want to reuse (as we hope so), some of our proofs or tools, without needing to piece many things together as would be the case if our proofs were factorized too much. But actually, the main theoretical ingredients are somewhat succinct, (though, we believe, important enough), and many long parts in the appendix are actually standard derivations from usual optimization proofs.\n\nRegarding the abstract, we will shorten it in the next revision, thanks for your suggestion.", "claims_and_evidence": "Proofs are provided.\nI think that the assumptions are sufficiently restrictive to require some concrete examples of problems that satisfy them.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have several issues with the theoretical claims.\n\nThe first issue, which I also mention in another subsection, concerns the scope of the paper and its results, requiring a 60-page submission (some in double-column) to an ML conference. It is unrealistic to expect a reviewer to thoroughly assess the correctness of such an extensive submission within the reviewing process of the ICML. I cannot recommend acceptance for a paper whose validity I am unable to verify to a reasonable extent.\n\nThe second issue is the assumptions. If I understand correctly (please see my proof sketch below), the RSC and RSS assumptions essentially imply that there is a unique solution to the underlying problem (1) and that any fixed-point of the projected gradient (IHT here) is this optimal solution.\nThis implies that the problem effectively becomes tractable, nullifying the sparsity part from the sparse optimization problem.\nI speculate that by building on this fact one can establish many results from non-sparse optimization.\n\n\n**Claim.** Let $y\\in P_{\\Gamma\\cap B_0(k)}(y-L_s^{-1}\\nabla R(y))$ and suppose that the RSC and RSS assumptions hold true with $s\\geq 2k$. If $\\nu_s > L_s$, then $y$ is the unique optimal solution of Problem (1). Consequently, it is enough to achieve stationarity wrt the sparse gradient projection operator to globally solve the optimization problem (1).\n\n**Proof.** Any optimal solution of (1) must also be a fixed point of the hard thresholding operator, so it is enough to prove that it is the optimal solution.\n\nBy the definition of $y$ we have that\n\n$$y\\in \\argmin_z \\{ \\langle\\nabla R(y), z- y \\rangle+\\frac{L_s}{2}\\|z-y\\|^2 : z\\in \\Gamma \\cap B_0 (k) \\}$$\n\nTherefore, in particular for the optimal solution $x$ of (1) we have that\n\n$$0 \\leq \\langle\\nabla R(y), x- y \\rangle+\\frac{L_s}{2}\\|x-y\\|^2$$\n\nOn the other hand, by the RSC,\n\n$$R(x) \\geq R(y)+\\langle\\nabla R(y), x-y \\rangle+\\frac{\\nu_s}{2}\\|x-y\\|^2$$\n\nCombining the former and latter, and using the optimality of $x$, we obtain that\n\n$$0\\geq R(x)-R(y)\\geq \\langle\\nabla R(y), x-y \\rangle+\\frac{\\nu_s}{2}\\|x-y\\|^2 \\geq \\frac{\\nu_s-L_s}{2}\\|x-y\\|^2$$\n\nThus, if $\\nu_s > L_s$ we obtain that $y=x$.\n\n\nThe third issue, which I am not sure if it is a typo or a more problematic mistake, is the contradiction in the results with respect to $\\nu_s$ and $L_s$.\nEssentially, it is required that $k \\geq 4 \\kappa_s^2 \\bar{k}$ which means that $\\nu_s \\geq 2 L_s \\sqrt{\\bar{k} k^{-1}}$.\nConsidering the plausible scenario where the optimal solution has sparsity $k$, we have that $\\nu_s \\geq 2 L_s > L_s$; this is aligned with the claim above leading to a unique solution.\nOn the other hand, Thm 3.4, Thm 3.7,   take a log on $(L_s - \\nu_s)<0$ which is undefined.", "experimental_designs_or_analyses": "There are some issues listed in other subsections.", "relation_to_broader_scientific_literature": "good", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n- The two projection approach is very interesting with potential\n- The paper is overall well-written\n- If all issues are resolved/justified, then the theoretical contribution on the constrained optimization case is worth publication\n\nWeaknesses:\n- Some results are on unconstrained optimization, which is less interesting\n- RSC and RSS are potentially very restrictive nullifying the sparsity part from the sparse optimization problem\n- Issues with the RSC and RSS parameters \n- The paper is too long to be properly assessed in the framework of this venue\n\nI recommend rejection because I do not believe that the issues above can be corrected in the scope of a rebuttal.\nNonetheless, I like the paper and think that if all the issues are resolved/justified it can be submitted to a journal that accepts papers of this magnitude, or be shorten and resubmitted.", "other_comments_or_suggestions": "In my opinion, the abstract is too long, and too much space is given to results that are less interesting in the context of the main contribution -- a sparse projection method that bypasses the difficulty in projecting onto sparse sets (unconstrained is not interesting since the projection is trivial).", "questions_for_authors": "See comments in previous sections.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission studies an iterative hard thresholding algorithm for minimizing a smooth function over so-called support-preserving constraints. The main development here is how the projection onto the constraint set is handled. The paper provides theoretical results in the form of convergence analysis of the objective function value in the determinstic and stochastic/finite-sum settings. There are also results for a zeroth-order oracle version of the algorithm and eventually some experiments.

The reviewers were split on this paper, with two reviewers giving scores of 4 and four reviewers giving scores of 1 or 2. The primary concerns of the negative reviewers were the incremental nature of the results (the algorithm and its analysis are relatively minor modifications of IHT and prior work) and the potentially strong assumptions used in some of the analysis. In the rebuttal period the authors were successful in convincing a reviewer to change their score from 1 to 2 and they addressed many of the concerns of other reviewers (questions about assumptions, citations to prior work).

For these reasons, I am weakly recommending to accept the paper.
Decision: Accept (poster)