An Adaptive Half-Space Projection Method for Stochastic Optimization Problems with Group Sparse Regularization
Authors: Yutong Dai
Tianyi Chen
Guanyi Wang
Daniel Robinson
Venue: Accepted by TMLR ()

Abstract: Optimization problems with group sparse regularization are ubiquitous in various popular downstream applications, such as feature selection and compression for Deep Neural Networks (DNNs). Nonetheless, the existing methods in the literature do not perform particularly well when such regularization is used in combination with a stochastic loss function. In particular, it is challenging to design a computationally efficient algorithm with a convergence guarantee and can compute group-sparse solutions. Recently, a half-space stochastic projected gradient (HSPG)  method was proposed that partly addressed these challenges. This paper presents a substantially enhanced version of HSPG that we call AdaHSPG+ that makes two noticeable advances. First, AdaHSPG+ is shown to have a stronger convergence result under significantly looser assumptions than those required by HSPG. This improvement in convergence is achieved by integrating variance reduction techniques with a new adaptive strategy for iteratively predicting the support of a solution. Second, AdaHSPG+ requires significantly less parameter tuning compared to HSPG, thus making it more practical and user-friendly. This advance is achieved by designing automatic and adaptive strategies for choosing the type of step employed at each iteration and for updating key hyperparameters. The numerical effectiveness of our proposed AdaHSPG+ algorithm is demonstrated on both convex and non-convex benchmark problems. The source code is available at https://github.com/tianyic/adahspg.

Published in Transactions on Machine Learning Research (06/2023)
An Adaptive Half-Space Projection Method for Stochastic Optimization Problems with Group Sparse Regularization
Yutong Dai*
ynd ynd8199lehigh.edu
Department of Industrial and Systems Engineering
Lehigh University
Tianyi Chen"
tiachen@miicrsoott..omm com
Microsoft
Guanyi Wang
Guanyi. Wünus edu.sg
Department of Industrial Systems Engineering and Management National University of Singapore
Daniel P. Robinson
daniel. wrb.ep..rroonssonneehhh.
Department of Industrial and Systems Engineering
Lehigh University
Reviewed OpenReview: https: https:///penreeviaw openreview. net/ ser/formm id= KBhSyBBeed
Abstract
Optimization problems with group sparse regularization are ubiquitous in various popu- lar downstream applications, such as feature selection and compression for Deep Neural Networks (DNNs). Nonetheless, the existing methods in the literature do not perform par- ticularly well when such regularization used in combination with a stochastic loss function. In particular, it is challenging to design a compulationally efficient algorithm with conver- gence guarantee and can compute group-sparse solutions. Recently, half-space stochastic projected gradient (HSPG) method was proposed that partly addressed these challenges. This paper presents a substantially enhanced version of HSPG that we call AdaHSPG+ that makes two noticeable advances. First, AdaHSPG+ shown to have a stronger convergence result under siguificantly looser assumptions than those required by HSPG. This improvement in convergence achieved by integrating variance reduction techniques with new adaptive strategy for iteratively predicting the support of solution. Second, AdaHSPG+ requires significantly less parameter tuning compared to HSPG, thus making it more practical and uscr-fricnnt friendiy This advance is achieved by designing automatic and adaptive strategics for choosing the type of step employed at each iteration and for updating key hyperparam- eters. The numerical effectiveness of our proposed AdaHSPG+ algorithm is demonstrated on both convex and non-convex benchmark problems. The source code is available at
1 Introduction
In many machine learning tasks, people not only want to compute solutions with small predic- tion/ sonn/eneeraization errors but also seek casier-to-interpret models by identifying essential problem structures
and filtering redundant parameters {Lin et al. 2019 Wen et al. 2016 Chen et al. 2020a 2023b One popu-
lar technique to achieve this goal is the use of structured sparsity-inducing regularization (Bach al., 2012b;
Jenatton et al. 2010 that encodes the model architecture. When this type of regularization is combined with appropriate loss function,
is able to recover structured sparse solutions (Delen & Bengio
2021
These authors contributed equally to this work.

---

Published in Transactions on Machine Learning Research (06/2023)
The non-overlapping group-sparse regularizer Yuaan & Lin 2006) has proved useful in machine learning applications. It. also plays an essential role for more general structured sparse learning tasks since problems with overlapping group sparsity (Bach et al. 20122)) or hierarchical sparsity (Jenatton et al. 2011] are often solved by converting them into an equivalent non-overlapping group-sparse problem (c.g., by introducing latent variables (Bach et al.] 2012b) ). In general, structured sparsity has found numerous applications computer vision (Elhamifar et al. 2012); signal processing (Chen Selesnick] 2014)) medical imaging (Liu
et al. 2018); and deep learning (Scardapane al., 2017 Li et al. 2020 Chen et al. 2021b 2023a
1.1 Problem Formulation
In this paper, we study the group-sparse regularization problem (sometimes called the mixed / problem)
N
(M(x) = EER"
min
[((())
+
Ag ||
(1)
959
f(w)
r(w)
where ||-|| denotes the fz-norm, f is the average of N continuously differentiable functions f; - R, is
set of disjoint subsets of = (1, 21,22....,7 (each g E G represents group of variables), X, > 0 is the weight for group 9, and r(z) is the mixed f norm Larger values for >g result in greater group sparsity but may produce more model bias. In practice, 0g is usually tuned to achieve an acceptable balance between sparsity and model generalizability.
1.2 Literature review
Problem 11) has been well studied in deterministic optimization, and there are many algorithms capable of returning sparse approximate solutions (Yuan & Lin 2006 Roth & Fischer 2008 Huang et al. 2011 Ndiaye el al. (017). Proximal methods are popular approaches for solving the structured non-smooth optimization problem (I). These methods include the mroximal-gradiens (PG) method, which only uses first-order derivatives. When N is huge, stochastic methods become essential because they use small subsets of the data at each iteration, whereas deterministic methods perform costly evaluations using the entire
dataset.
The proximal stochastic gradient method (Prox-SG) (Duchi & Singer 2009) is the natural (stochastic) extension of the PG method. The regularized dual-averaging method (RDA) (Xiao 2010 Yang et al. 2010 applies the dual averaging scheme from (Nesterov) 2009] to Prox-SG. There exists a set of incremental gradient methods inspired by stochastic average gradient (SAG) [Roux et al. 2012) that utilize the average of accumulated past gradients improve the convergence rate. For example, the proximal stochastic variance- reduced gradient method (Prox-SVRG) [Xiao & Zhang 2014) and proximal spider (Prox-Spider) (Zhang) & Xiao 2019) multi-stage schemes based on the well-known variance reduction technique proposed in SVRG (Johnson & Zhang 2013) and Spider (Fang et al. 2018). SAGA (Defazio et al. 2014) is blend of ideas from SAG and -VRG.
Compared to deterministic methods, the above stato-of-the-art stochastic algorithms for solving problem 11 have weaknesses (Chen el al.) 2021aa b). In particular, these stochastic algorithms typically struggle to achieve near-optimal solutions that are also group sparse because of the randomness in the algorithm and the limitations in ensuring sparsity.
To address the drawbacks of stochastic proximal methods, two-stage algorithm HSPG (half-space stochas- tic projected gradient method) was recently proposed with the aim of improving numerical performance, specifically to improve solution sparsity (Chen et al. 2020b 2021b). In the first stage, a subgradient algo- rithm is run to seek an estimate of a solution. The sccond stage uses the solution estimate from the first stage define a certain half-space that is used to improve the sparsity of the solution returned the first stage. Although HSPG was shown to perform well in initial testing, it has limitations. First, since HSPG is two-stage method, it unable to converge when an insufficietlly accurate solution estimate is provided
"The name fi/fz norm stems from the fact it can the norm of some subvectors (indexed by induced g) to zero, hence is equivalent to selecting a subset. of group of variables that are nanzero.
2

---

Published in Transactions on Machine Learning Research (06/2023)
from the first stage. This is not ideal from both theoretical and numerical performance perspective since much computational effort is likely wasted in stage one in an attempt to ensure accurate enough solution estimate. Second, the analysis provided for HSPG does not extend to the mixed f1/l2 problem since it is not Lipschitz continuous in a neighborhood of the origin. Third, the numerical performance HSPG relies heavily on luning couple of crucial hyperparameters, which is typically quite time-consuming. The focus of our research is address the weaknesses of the HSPG approach, as we describe in the next section.
1.3 Our contributions
We overcome the weaknesses of HSPG discussed above by proposing an adaptive half-space stochastic projected gradient method (AdaHSPG+). Our main contributions can be summarized follows.
Improved algorithmic design and convergence theory. Our proposed approach AdaHSPG+ is a significance improvement upon HSPG, First, unlike HSPG, our AdaHSPG+ not a two-stage method and therefore does not roquire a "good enough" solution estimate to be provided from first stage. Second, although we use a similar half-space projection scheme to enhance solution sparsily, our strategy for choosing the groups that define the half-space is significantly differrnt from that used in HSPG. Consequently, unlike HSPG, we establish a convergence theory that holds for problems that are not Lipschitz continuous in a neighborhood of zero, such as the group sparse problem ① considered in this paper. Even though the HSPG theory does not hold in our setting, it is interesting to note that the theory provided for HSPG (for other types of regularizers) an expectation-type result that holds with a certain probability. In contrast, the convergence theory we present is a pure expectation- type result akin to standard results for stochastic gradient methods. The key to achieving these improvements over HSPG is an automatic and adaptive strategy that decides the iterations for which the half-space projection scheme should be used.
Numerical performance. We numerically demonstrate the effectiveness of AdaHSPG+ on com- monly tested convex (logistic regression) and nonconvex (deep neural networks (DNNs)) problems. In the convex setting, AdaHSPG+ performs similarly to HSPG and significantly outperforms Prox-SG and Prox-SVRG. For the nonconvex setting, AdaHSPG+ significantly outperforms all of the methods, including HSPG, especially in terms of solution sparsity. These numerical gains are due to the combi- nation of the en enhanceeents described above and a new aulomatic and adaptive strategy for defining a key hyperparameter that defines the half-space projections.
1.4 Preliminaries and notations
Unless specified otherwise, ||||l represents the l norm, and |A| denotes the cardinality of a set A. [N] is the index set 21,2. ,N} and N4 and R4 are the set of positive integers and positive real numbers, respectively. For a nonempty set B C [N,, we define the batch function induced by the set B
fs(#)
Σ [a())) and vo((a) == fb(Φ)) + r(x)) B
iEB
For any vector x E R and E G, [xly E TRlst is the subvector obtained by restricting to the elements in g. For any [xlg * 0, the partial gradient of & over [æ], is defined as Vytb(()) = V fofn(()) (x) + V Vxr(x) In other words, V (2x) = (x)(z))0(zz) For any r > O, the proximal operator induced by r is defined as Prox,r (x) == arg min - f|u x: + r(u), which has a closed-form solution (Beck) 2017 Example
6.19), d.e., [Prox,r (x)1g (1 max][==|]..)))) [z]g. Furthermore, define the proximal gradient step over the index set B as
sg(#; = Prox, (x - 7/ f((x)) - x.
(2)
and when B [N], we simply write s(a; and s(x;)) is the negative of gradient mapping defined in (Beck) 2017] Definition 10.5) The quantity [|s(;; m))l is a stationarity measure for problem ① (Beck 2017 Theorem
10.7). Since solution sparsity is of great interest in this paper, we define the concept of support.
Definition 1.1. The support of point x E R with respect to G is Supp(æ) = [g E G [x], #0).
3

---

Published in Transactions on Machine Learning Research (06/2023)
2 A Algorithm
In this section, propose Adaptive Half-Space Stochastic Projected Gradient (AdaHSPG+) method for solving problem ① that uses optimal support prediction, space decomposition, and half-space projections. An overview of the algorithm is presented in Section 2.1 For every epoch, either an Enhanced Half-Space step or a Prox-SVRG step is performed based on an automatic switching mechanism. In general, the Prox-SVRO step guides how we cstimate the solution support (the non-2ero groups of variables), and the Enhanced Half-Space step is designed to improve the sparsity of the iterates. These two sleps work together along with the switching mechanism to drive the convergence of the iterates generated by AdaHSPG+
2.1 Main algorithm
Algorithm AdaHSPG+ for solving (1).
1: Input: Zo E R2, > 0, e 1), (ao, E R4, (ma, mps 6) E N4.
2: for epoch h = 0,1,, Randomly sample an index set Bg C [N], and then compute V Vʃs, (ars) and step 88s, (ark: 1)) as
do
Compute I and IHu using 4
Compute the measures Xk sts (æx, n)12ا|| and X
[|[ (#h, 21)2
6:
HS 2 μxa then
Call Algorithm
2 get the next iterate: 21+1 f EHS( Og C, KG, m.)-
else
Call Algorithm 3 to get the next iterate: # PSVRG(m*; VBB. (mx), mp: b).
10:
end if
11: Set ax+1 (e.g., constant or diminishing step size).
12:
end for
At the beginning of the kth epoch, we partition the groups variables into two sets. To form these sets, let choose a constant к o0) and define the function
|ل4يع| 2
I(x, B) == g g
g G
| # 0. + sy(æ, m)la # 0, V VV (x)]
(3)
which we use to define the sets
TH = I(rk, BB) and IN = G 7
(4)
These sets aid in identifying the zero zero/nonzer, /ooneero groups at solution. In particular, the groups of variables in 7E are input to the Enhanced Half-Space step computation to explore further whether they should remain nonzero. This makes sense since _ for the given Ty and minibatch By if and only the following conditions hold: (i) æg is nonzero over the group (i.e., || ||وو|g||| * 0); (ii) the batch proximal gradient step over B& predicts that group g the solution support (i.e, (my + 8B, (at m)), * 0), and (iii) the restriction of F& group g is sufficiently far from the origin (i.e., |||>]]||| x V v.B. (xx)).),, which noeded for our convergence analysis.
The switching mechanísm that we have designed uses x and X in line 5 of Algorithm I to decide which one the two spaces of variables we should currently explore further. This makes sense since the sizes of x and X Stx indicate the amount of progress one might expect to achieve by continuing to optimize over the variables in T (Enhanced Half-Space step) and I (Prox-SVRG step), respectively. If x 2 μх Nes the algorithm proceeds with the Enhanced Half-Space step; otherwise, the algorithm performs the Prox-SVRG step and then generates new partition of the groups The value chosen for μ gives preference to either the Enhanced Half Half-Space step Prox-SVRG step.
ss
4

---

Published in Transactions on Machine Learning Research (06/2023)
2.2 An enhanced half-space step
Algorithm Enhanced Half-Space step (EHS).
1: Input: 36 _R,, or > 0, E (0,1), ma > 0, and k > 0.
Initialize Ł2.0 2k.-
for t= 0....................... m
do
Randomly sample an index set B C [N]. Form 4,, I( BR.)) and T = G "R,t'
6: Compute V It,, B'B (#x,1), which is well defined.
Compute a trial iterate &x,r+1 as [ < [0x,d aq V L. (#x.1), R. 9: Set εA,(+1 f Projzz, (2x,141:08..) using
@BR,0+1lzgg + [ 2ee
k.
end for 11:
10:
return 1k+1 +- Bk.ma
If the Enhanced Half-Space step (EHS) is computed during the kth epoch of AdaHSPG+, then the goal is to explore group sparsity with respect to the current candidate support set. Specifically, in Algorithm 2 we form the partial stochastic gradient of d over groups of variables in I where It, = I( Bx,)), &x and B are the tth iterate and mini-batch Algorithm | and I(: is defined in (3), and then take a stochastic gradient step (see line in Algorithm 2 to obtain 1x.++1- For O, the gradient. f computed over Bg as part of the switching mechanism in Algorithm [ can be reused. Next, a half-space projection operator
if [ [zy] S < ||| and E otherwise
Projj (z)x)),
(5)
[z],
is performed on db.e41 to obtain 0g.441- A graphical illustration of the projection procedure is presented in Figure 1 The intuition behind the above projection is to project groups of variables to zero when the stochastic gradient step crosses over the boundary of the hyperplane Hg = (2, E IRle [ |||=]]]] = 0} depicted in Figure 1] The parameter in (5) determines the distance between the boundary of Hg and the origin, and therefore controls how aggressively sparsity sought. Larger values of
more likely to lead to solutions with greater group sparsity. For convenience, we let IPROJ as the index set of the groups of
variables that are projected onto zero via 5 and I I \ IPROJ as the index set for the remaining complementary groups in T
Snarell v Raal
(N)
An illustration of the proposed half-space projection. (a) The restriction of the current iterate to group g, namely (arrlg is not sufficiently far from the origin. The Enhanced Half Half-Space step does not perform an update. (b) Here, [āv.lg is sufficiently far from the origin, and a stochastic gradient step does not cross the boundary of the hyperplane Hg. The projection leaves [øg, unchanged. (c) Here, [ is sufficiently far from the origin, and the stochastic gradient step crosses the boundary of Hg. The projection sets [ = 0, thus creating a sparser solution estimate.
Figure 1:
5

---

Published in Transactions on Machine Learning Research (06/2023)
2.3 A Prox-SVRG step
When Algorithm chooses compute the Prox-SVRG step during the kth epoch, we simply perform my updates of basic Prox-SVRG method described in Algorithm
Algorithm Prox-SVRG step (PSVRG).
1: Input: E R", > O, mp O, and fBB (xx).
2: Set 02.0 f- Ft.-
3: for t= 0. .......... ..m...m mp -1 do
4: Randomly sample an index set Bx.t C [N] such that [Brrl] = b.
Tk&t - EieBr. (Vf(((x,)) Vf(((=)) fB. (ax)
6: Tk,1+1 + Prox (#t.e 170k,t)
7: end for
return 21+1 +- Fg,mp
Prox-SVRR SVRG extends Prox-SG by adding a variance reduction technique (see Johnson & Zhang 2013 Xiao
& Zhang (014)), which has been frequently studied in Reddi al. (2016): Li & Li (2018) Compared Prox-SG, Prox-SVRG enjoys a stronger convergence theory and often performs better on convex experi-
ments, although this numerical advantage oflen disappears on non-convex problems such those in various
DNN applications (Defazio & Bottou 2019
Although the proximal gradient operator is known to identify the solution support (asymptotically and under certain assumptions) in the deterministic setting, the story is different in the stochastic regime. In fact, stochastic methods applied in our setting typically return dense solution estimates (e.g., see Chen et al. (2021b)) AdaHSPG+, however, the Prox-SVRG step complemented by the Enhanced Half-Space step to promole sparse solutions.
3 Convergence Analysis
In this section, we describe the convergence results for the proposed AdaHSPG+ algorithm; all proof may be found in the appendix. We assume the following hold throughout.
Assumption 3.1. The function fo IR" + R continuously differentiable and has an L-Lipschitz continuous gradient for all E (1,2, N), i.e., fa L-smooth. It follows that is also L-smooth.
Assumption 3.2. The function v is bounded below, i.c., (xx) > vb for all E R and some TR.
Assumption 3.3. The step size sequence {ax} satisfies Ex ag = oo and Σx= at cc.
Assumption 3.4. The iterate sequence } is bounded, i.e., | < M for all k and some M 0.
Assumption 3.1 and Assumption 3.2 are standard in the literature (iao & Zhang 2014 Johnson & Zhang
2013 Rosasco et al. 2019 Assumption 3.3 and Assumption 3.4 are used in (Ljung) 1977] to analyze the convergence behavior of stochastic gradient descent. Assumption 3.4 is reasonable our setting since the regularizer penalizes the magnitude of variables, and [|| remained bounded in our numerical tests.
We can prove that the Enhanced Half-Space step has the following sufficient decrease property. Lemma 3.5. If the Enhanced Half-Space step is computed during the kth epoch of Algorithm 1 then the tth iterate kk.41 computed in Algorithmm 2 satisfies
Es, (a..[V@Re.c (#)()))) Tb.1] S ((xx.)))
(-ee
11)
|| [ I Tma - 0k (1- Lerk
|
|| V (
2
+
Amax
Σ
[|
+
Lako IT
< <N)
Re2e
2/Bk.el
where the expectation taken with respect Br and conditioning on Tt.t. I(-) is the indicator function,, and Amax maxx (>g 9). Purthermore, o² is the bounded variance constant satisfying E. [[[Vf((x) vf(x)]

---

Published in Transactions on Machine Learning Research (06/2023)
o², with the expectation taken with respect to randomly sampled i. (The eristence of the constant o² follows from the finile-sum structure of J [() the uniform sampling scheme, and Assumplions 3.1 and 3.4
Lemma 3.5 shows that for step size ar sufficiently small and [Bx, sufficiently large, the Enhanced Space step is expected to decrease the objective function sb.
For completeness, we present the sufficient decrease property of Prox-SVRG from Li & Li 2018 pg. 14). Lemma 3.6. If the Prox-SVRG step is computed during the kth epoch of Algorithm and [Bg] S N, 13,rl = min(m), N); mp(mp - 1/2) S b, and n S ह then
I([Bg] < NNno
[[b(<x)] S E ()(==11)-
|| [|s( 36L
|
Lemma 3.6 shows that when the batch size Bg is sufficiently large, the Prox-SVRG step is expocted to yield a decrease the objective function sh.
We are now ready to state the main convergence theorem.
Theorem 3.7. Under Assumptions 3.1 3.4 and with E (0,1), 17 (0, rtll as <min| 20-c) 11 [x = N
for all k. mp(mp-117 < b, and |B min(m), N) for all ls and L, then Algorilhm generates sequence of iterates {æa]KEN such that lim liminfx B[| O.
Theorem 3.7 shows that if the sequence {æEJKEN computed by Algorithm I has a limit point, then that limit point will be a stationary point in expectation. We remark that this theorem only establishes the asymptotic convergence result, whereas the previous works (Li & Li 2018 Pham et al. 2020) establish the complexity bounds. The main challenge that prevents us from establishing such a convergence result is the diminishing stepsize used in the Enhanced Half-Space step. We conjecture that with additional variance reduction integrated into the Enhanced Half-Space step one might be able establish such a result. Here, we avoid the variance reduction technique in the Enhanced Half-Space step because the practical performance deep learning tasks is significantly better.
We then reveal the sparsity identification property of AdaHSPG+ as stated in Theorem 3.8 which requires a non-degeneracy assumption, which is similar to (Chen et al. 2018 Nutini et al. 2019 Define
0 8
min inf (A [[V lll)) (x) BCln!
(6)
Theorem 3.8. Given any lo E N4, if the kth epoch performs an Enhanced Half-Space step with as S 1/LL, then for any 1 E (0...., mp - 1} salisfying [ - x=1| 1aae-x=ll and k S mingez"(we)) ||al [|ll/ll[[vB. (1x it holds that AdaHSPG+ yields (x)") S I (ix, where (x) collects groups of variables that 0 at x.
S T-e+ooL. ( + s(mx, ( # O,
2016
Remark 3.9. Theorem 3.8 shows that if øg. falls into an ball centered at x" with radius no greater than 20y8 I-etayL, then AdaHSPG+ identifies the sparsity pattern over the groups on which proximal method fails to identify, i.e., [#x, + s a (n==e))))))))))). * O. Comparing with the radius min(ō/L, agd} required from 20,5 > min agō} as Prox-SG (Lemma A.1 AdaHSPG+ requires an balb with larger radius, i.c., 1-etazL
0g < 1/L and e (0, )) thereby is superior to Prox-SG in terms of sparsity identification.
Remark 3.10 (AdaHSPG+ versus HSPG). We provide a more detailed comparison between AdaHSPG+ and HSPG. The HSPG algorithm is two-stage algorithm. In the first stage, subgradient descent steps are computed for fixed number of epochs (denoted by Kswiteh). The second stage uses the nonzero groups of the solution estimate computed in the first stage to define a half-space similar to, but different from, ours (more on this below). The rest of the second stage involves the repeated computation of stochastic subgradient steps followed by projections defined using the half-space. Such a design has two drawbacks. First, the switching constant Kswtchh determined offline. In practice, for each new problem, users need spend significant time tuning this constant to get acceptable results. Second, by only performing iterations based on the half-space
7

---

Published in Transactions on Machine Learning Research (06/2023)
after Kywitch epochs (I.e., no longer allowing stochastic proximal gradient steps to be performed), it is more likely that HSPG will predict groups to be zero while they are in fact nonzero at the solution. This is because, in the second stage, only nonzero groups of variables are updated. To avoid this unfortunate possibility in their convergence analysis, the authors make rather strong assumptions that are either unlikely to hold in practice or impossible to verify practice (e.g., they require the point computed during the first stage to be close enough to the solution, which is typically unknown in practice). Morcover, the analysis for HSPG requires the regularizer to be differentiable with Lipschitz continuous gradient, which does not hold at the origin for the group regularizer considered in this paper; thus, the analysis does not apply in our setting.
To overcome the drawbacks of HSPG, we proposed an automatic and adaptive switching mechanism that avoids the need for a two-stage algorithm, thus avoiding the challenge of finding good value for Kswitch- To overcome the strong smoothness assumption required by HSPG, our AdaHSPG+ uses a more sophisticated definition of the set I used to compute the Enhanced Half-Space step. In particular, for a group 9 to be included in I our definition requires [axlg be sufficiently far from the origin (sce (3). This is in contrast to HSPG, wherein every nonzero group is included in I This difference, in some sense subtle, is crucial in establishing our stronger convergence theory under weaker assumptions on the regularizer. For
additional aspects related to our contributions with respect to HSPG, see our contributions in Section L.3
4 Numerical Experiments
In this section, we demonstrate the effectiveness of AdaHSPG+ on non-convex problems. The experimental results validate that AdaHSPG+ significantly outperforms proximal methods in terms of significantly better group sparsily exploration and maintaining competilive objective function convergence. In Appendix ??, we also include a convex experiments comparison.
4.1 Implementation details
We first describe the hyperparameters used in Algorithm [ We designed an adaptive update for c. At the end of an epoch, if (i) an Enhanced Half-Space step was computed during the previous and current epoch, (ii) the group sparsity of the iterate did not improve compared to the iterate at the beginning of the previous epoch, and (iii) the optimality measure is sufficiently small, then we consider enlarging by setting + min 0.999). Anytime any of (i)- do not hold, we consider reducing by setting + max (0.001, 0.5e). We set x <- 10-4 to favor the inclusion of more groups from G into ZF5. We set +- to give equal preference to the Enhanced Half-Space step and the Prox-SVRG step. Prior testing showed that our numerical results are rather insensitive to except when >> 1, which would significantly favor Prox-SVRG step. The mani-batchha size [Bx,r] for all & and t is set to the same number b, whose definition will change for the convex and non-convex problem sottings (these will be discussed in their corresponding sections below). We set [Bal N, which is the total number of data samples. my and my are both set as the ratio between the total number of samples and the mini-batch size. The choice of r and hyperparameters for Prox-SG, Prox-SVRG, and HSPG are discussed separately below for the convex and non-convex experiments.
4.2 Image classification via convolutional neural network
We now consider popular Deep Neural Networks (DNNs) for image classification tasks to demon- strate the effectiveness of AdaHSPG+ on non-convex problems. Specifically, we use the popular benchmark DNN architectures VGG16 (Simonyan & Zisserman 2014). ResNet18 (He et al.] 2016). and MobileNetV1 (Howard al. 2017) on the two commonly tested datasets CIFARIO (Krizhevsky & Hinton 2009) and Pashion-MNIST (Xiao et al. 2017). As in (Li et al. 2020 Chen et al. 2021b), we conduct all experiments using 300 epochs with mini- choose Ag = 10-3 for all g E G as in Chen ct al. (2021b). We remark that X, 10-3 is the best regular- izer coefficient among the power of len alter line-tuning with balancing the model performance and group sparsity. If A, is too large, then the performance would significantly deteriorate; if X, is too small, then no group sparsity is yieldod. The step size 0g is initialized as 0.1, and then decreased by a factor of 0.1 every 75 epoch. The variables of each filter in the convolutional layer and each row of weighting matrix in the linear layer are clustered as one group following Deleu & Bengio (021). In Table 1 we report the same metrics
of size b = 128 on GeForce RTX 2080 Ti GPU. We
8

---

Published in Transactions on Machine Learning Research (06/2023)
for the convex experiments, wherein all results are averaged by three runs with the best values marked bold.
Table I demonstrates the superiority of AdaHSPG+ in the non-convex setting. In particular, AdaHSPG+ com- putes significantly higher group sparsity levels than all competing methods. Prox-SVRG does not perform well compared to the other methods since the variance reduction techniques may not work as desired for deep learning applications (Defazio & Bottou, 2019). Finally, we note that all methods perform comparably in terms of generalization error the validation set.
Results of non-couvex problems with various neural network architectures and datasets, where we report numbers in the form of final v/ group sparsity ratio validation accuracy for non-convex problems.
Table 1:
Model
Datases
Prox-S6
Proz-
USPg
AdallPPg
CIFARIO
0.553
54.0%
90.6%
0.525
14.7%
89.4%
0.591
0.591
76.1%
91.0%
VGG16
Pashion-MNIST
0.544
19.1%
93.0%
0.613
/ 0.55%
92.7%
0.541
39.7%
93.0%
0.539
51.2%
92.9%
CIPARIO
0.323
26.5%
T9
003361
7 2.8%
7 91.2%
0.312
41.6%
94.4%
0.311
42.1%
94.5%
ReaKet18
Fashion-MNIST
0.127
0.0%
94.8%
0.145
0.0%
94.8%
0.120
10.4%
94.9%
0.119
43.9%
94.9%
CIPARIO
0.401
59.1%
51.7%
0.652
29.2%
99.7%
0.403
65.4%
92.0%
6.402
71.5%
91.8%
YobileNetV1
Rashion-MNIST
0.229
62.656
94.25
0.246
42.0%
94.2%
0.230
74.3%
94.3%
0.241
78.9%
94.6%
Remark 4.1. One might ask whether may replace Prox-SVRG step with vanilla Prox-SG? We remark that, first, Prox-SVRG step allows for a better theoretical convergence guarantee. Second, although Prox-SVRG performs worse than Prox-SD for deep learning tasks as stand-alone algorithms, AdaHSPG+ performs better when using the Prox-SVRG step because of its ability to better identify the solution support; consequently, the majority of steps in AdaHSPG+ are Enhanced Half-Space steps.
Remark 4.2. It is also interesting to compare the testing accuracy of different neural network architectures trained by sparsity-induccnn algorithms and popular algorithms used in the deep learning community. Specif- ically, we use the stochastic gradient descent with momentum (SGD + M) and AdaHSPG+ as an example, and report the results in Table 2 including two metrics. One accuracy difference, which defined as the pre- diction accuracy achieved by AdaHSPG+ minus the prediction accuracy achieved by SGD + M). And the other is model compression rate. One can obscrve that, in most cascs, for neural networks trained by AdaHSPG+, there is little or even loss in the lesting accuracy while the model sizes are reduced by at least 45%. This phenomenon brings benefits like faster inference and the potential deployment of models edge devices.
Table 2: Accuracy difference and model compression rate achieved by AdaHSPG+ and stochastic gradient descent with momentum on different neural networks and datasets.
Dataset
Metric
VGG16
ReaNet11
MobileNettV
Accuracy Difference
(t)
-1.6%
1.5%
-2.6%
Cifar10
Model Compression Rate (1)
76.1%
42.1%
71.5%
Accuracy Difference (t)
-0.6%
0.0%
-0.4%
Fashion-MINST
Model Compression Rate (1) 51.2%
43.9%
78.9%
We then investigate the evolution of our evaluation metrics during the training process. The results are shown in Figure 4 and Figure 5] which include the objective function v group sparsity ratio, and validation F
accuracy. AdaHSPG+ performs better than the other methods in terms of group sparsity since it consistently exhibits a higher group sparsity ratio in the majority of training epochs.
We next sweep the regularizer coefficient À over {10 2, 10-3,033000 -3 10-4). As shown in Figure 2 AdaHSPG+ con- sistently exhibits the frontiers of the Pareto curves over CIFAR10 experiments, which demonstrates the superiority of HSPG-family methods over better group sparsity exploration and competitive objective con- vergence in practice compared with proximal methods.
9

---

Published in Transactions on Machine Learning Research (06/2023)
100
+
190)
+
100
+
80-
Prox-SC
Validiation Accuracy (36)
80
Prus SVRG
Pros-GG
40
SVRG
Pros-SG
Validation Accurary
Validalion Accurscy
00
PVacSVRGG
00
c
10
40
10
2- 30"
10-1
10-4
20
10
30
10
80
100
10
811
100
20
AD
100
Group Spucsity (5)
Group Spursity (%)
Group Sparrily (9)
(a) VGC16 CIFARIO
(b) ResNet118 CIFARI0
(c) MobileNetVi on CIFARIO
Figure 2: Validation accuracy versus group sparsity under varying regularizer coefficient As.
We end this section by fine-
tuning the step size (learn- ing rate) by considering multi-
100
100
AdaHISPG-
Pro--SG
AdaHSPG
Validou.on Accurssy (%)
Validacion Accurecy (%)
step (MultiStep) scheduler
Pro--VRG
60)
Prox-SVRG
and cosine annealing sched- uler (Cosine) (Loshchilov & Hutter 2016) with differ-
ent starting value Op from 0.10,0.1, 0.01). For the multi-
10
10
step scheduler, we divide the step size by 10 for every [1/47], i.e., on 0.1 0.1447(025))), where T is the total number of epochs. For Cosine scheduler, we use the default parameters provided by Pytorch with the period length as the max- imum epoch T. The results are presented in Figure 3 We observe that for different step size schedulers and initial step sizes, AdaHSPG+ consistently exhibits the frontier among all Patero curves. The results val- idate the superiority HSPG-family methods over group sparsity exploration and achieving models with competitive generalization performance compared with proximal methods.
40
100
60
100
Group Sparsity (%)
Group Sparsity (%)
ag
(a) Multi-Step Scheduler
(b) Cosine Annealing Scheduler
Figure 3: Validation accuracy versus group sparsity under varying step sizes.
4.3
Question and answering via large-scale transformer
We follow (Chen el al.] 2021b) lo show the scalability of AdaHSPG+ by training and pruning the large-scale transformer Bert (Vaswani al. 2017), evaluated on SQuAD, question-answering benchmark (Rajpurkar et al. 2016). The structures inside Bert consist of embodding layers, fully connected layers, and multi-head attention layers. For fairness, we do not prune the embedding layers following the prior Bert compression works (Deleu & Bengio 2021). b. As (Chen et al. 2021bb, we selected Ag as 10-3 for all groups g E 9 with 10% and 30% group sparsity upper bound constraints. We compared with the best results of an adaptive proximal method ProxSSI presented in (Deleu & Bengio 2021h.
As shown Table 3 AdaHSPG+ significantly outperforms ProxSST (Deleu Bengio, 2021 in terms of achieving better exact match rate and Fl-score and higher group sparsity levels. In particular, with similar Fi-score of around 82%, HSPG-family methods could reach 1.8x higher group sparsity (30% versus 16.5%). Furthermore, if the proximal method yielded more group sparsity from 16.5% to 23.9%, their model performance dramatically regressed to 77.5% F1-score, which was not comparable with the 82%-84% Fl-scores of HSPG-family methods. The reason proximal methods are not. working well for deep learning applications that their group sparsity exploration heavily relies on the selection of the regularizer coefficient X and the learning rate a. The proximal method has to increase either À or a to yield satisfactory group sparsity, which may noticcably deteriorate the model performance. In sharp contrast, HSPG-family methods feature Half-Space projector that provides novel mechanism for producing group sparsity which explores
10

---

Published in Transactions on Machine Learning Research (06/2023)
8
100
100
AccHSPS+
Ada (SG
7
(%)
80
modd
80
PradhTIC
5
60
60
3
40
Validation
40
2
20
20
1575
Pracs
01
75
150
225
300
0
75
150
225
300
0
75
150
225
300
Epoch
Epoch
(a)
CIFARIO
100
100
5
1870
AdMiStGe
80
80
4
Prxdvvn
Sparsity
Objective
60
60
3
2
40
Validation
40
1
20
20
Priesi
0
04
75
150
225
75
75
300
Epoch
Epoch
Epoch
(b) ReaNet18 CIFARI0
100
100
8
Ads ISAG
RSPS
HSTS
Validation (%)
80
80
Objective
6
60
60
4-
40
40
20
20
RSPO
PriSS
75
150 Epoch
225
300
0
75
150
225
300
75
150
225
300
Epoch
Epoch
(c) NobileNettV on CIFARI0
Figure 4: The evolution of v) group sparsity ratio, and validation accuracy over the epochs.
Table 3: Pruning Bert on SQuAD.
Method
Group Sparsity
Exact
F1-score
86
AdaHSPG
Baseline
0%
81.0%
88.3%
ProxSSI
Deleu & Bengio
2021
16.5%
72.3%
82.0%
F1-Score (5%
84
ISPC
AdaHSPG
ProxSSI
Deleu & Bengio
2021
23.9%
66.2%
77.5%
80
HSPG
Chen al.
2021b
10.0%
75.0%
84.1%
Prodist
DISP
HSPG
Chen et al.
2021b
30.0%
72.3%
82.1%
AdaHSPG+
10.0%
75.2%
84.3%
AdaHSPG+
30.0%
72.6%
82.5%
20 Group Spariity (%)
group sparsity without such heavy dependency over and a, thereby typically achieving solutions with competitive performance but remarkably higher group sparsity levels.
11

---

Published in Transactions on Machine Learning Research (06/2023)
8
100
100
AdaISTG1
7
HSPS
(%)
80
Phaddc
80
hrodiinc
5
60
60
3
40
Validation
40
2
20
20
1575
AddisPS
1
Procdo
75
150
225
300
0
75
150
225
300
0
75
150
225
300
Epoch
Epoch
Epoch
Fashion-
100
100
5
1870
AdMiSPce
Validation (%)
treess Frecsvi
80
80
4-
Fressvie
Sparsity
Objective
3-
60
60
40
40
1
20
20
Fress Precoitc
0
0
150
225
75
75
225
300
Epoch
Epoch
Epoch
(b) Reallet18 Fashion-MND MNIST
100
100
8
Validation (%g
hrods
80
80
Objective
6
Sparsity
60
60
4-
40
40
20
20
Prossc Proddvt
Procic
0
75
150
225
300
75
150
300
150 Epoch
300
Epoch
Epoch
(c) MobiletfetVi Rashion-MNIST
Figure 5: The evolution of v) group sparsity ratio, and validation accuracy the epochs.
5 Conclusion
In this paper, proposed AdaHSPG+, which is significant upgrade of the recently proposed algorithm HSPG, to solve optimization problems with group sparse regularization. AdaHSPG+ takes advantage of variance re- duction techniques and is equipped with a novel adaptive strategy for estimating the support of a solution. We showed that AdaHSPG+ has a much stronger convergence result under milder assumptions when com- pared with HSPG. Numerically, thanks to new adaptive and automatic hyperparamoter tuning strategy and switching mechanism, AdaHSPG+ requires fewer hyper-parameler fine-tuning efforts compared to HSPG. Finally, the proposed AdaHSPG+ outperforms popular stochastic proximal methods the non-convex deep neural network benchmark problems in terms of various performance measures that include final objective function value, solution group sparsity ratio, and generalization error.
Acknowledgments
Guanyi Wang supported by the NUS under AcRF Tier-1 grant A-8000607-00-00. Yutong Dai and Daniel P. Robinson were supported by the US National Science Foundation grant DMS-2012248. We are grateful for the support from Lehigh University, Mierosoft, and the National University of Singapore. Finally, we thank anonymous reviewers and editors for helpful feedback.
12

---

Published in Transactions on Machine Learning Research (06/2023)
References
Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Optimization with sparsity- inducing penalties. Foundations and Trends& in Machine Learning, 4(1):1-106, 2012a.
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, al. Structured sparsity through convex optimization. Statistical Science, 27(4):450-463 2012b.
Amir Beck. First-order methods in optimization, volume 25. SIAM, Philadelphia, PA, 2017.
Chih-Chung Chang and Chib-Jen Lin. Libsvm: Data repository. ACM transactions on intelligent systems and technology (TIST), 2(3):1 27, 2011.
Po-Yu Chen and Ivan W Sclesnick. Group-sparsc signal denoising: non-convex regularization, convex opti- mization. IEEE Transactions Signal Processing, (2(13))4464-3478 2014.
Tianyi Chen. A Past ReduucedSppees Algorithmic Prumework for Sparse Oplimization. PhD thesis, Johns
Hopkins University, 2018.
Tianyi Chen, Frank E Curtis, and Daniel P Robinson. Farsa for l--regularized convex optimization: local convergence and numerical experience. Optimization Methods and Software, 2018
Tianyi Chen, Bo Ji, Yixin Shi, Tianyu Ding, Biyi Fang, Sheng Yi, and Xiao Tu. Neural network compression via sparse optimization. arXiv preprint (Xxi::001100486: 2020a.
Tianyi Chen, Guanyi Wang, Tianyu Ding, Bo Ji, Sheng Yi, and Zhihui Zhu. Half-space proximal stochastic gradient method for group-sparsity regularized problem. ar preprint Stt::2000120070 2020b.
Tianyi Chen, Tianyu Ding, Bo Ji, Guanyi Wang, Yixin Shi, Jing Tian, Sheng Yi, Xiao Tu, and Zhihui Zhu. Orthant based proximal stochastic gradicnt method for f-rrgularized optimization. In Machine Learning and Knowledge Discovery in Dalabases: European Conference, ECML PKDD 2020, Ghenl, Belgium, September 14-18, 2020, Proceedings, Part III, pp. 57-73. Springer, 2021a.
Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang, Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, and Xiao Tu. Only train once: A one-shot neural network training and pruning framework. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021b.
Tianyi Chon, Luming Liang, Tianyu Ding, and Πya Zharkov. Towards automatic noural architecture search within general super-networks. Xixe preprint urXiv:2305. 18030, 2023a.
Tianyi Chen, Luming Liang, Tianyu Ding, Zhihui Zhu, and Ilya Zharkov. Otov2: Automatic, generic, user-friendly. In Eleventh International Conference on Learning Representations, 2023b.
Frank E Curtis, Yutong Dai, and Daniel P Robinson. A subspace acceleration method for minimization involving group sparsity-inducing regularizer. arXiv preprint or xrx::20077.1400 2020.
Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. In Advances in Neural Information Processing Systems, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with sup- port for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
Tristan Deleu and Yoshua Bengio. Structured sparsity inducing adaptive optimizers for deep learning, 2021.
John Duchi and Yoram Singer. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research, 10(Dec):2899 2934, 2009.
Ehsan Elhamifar, Guillermo Sapiro, and Rene Vidal. See all by looking at a few: Sparse modeling for finding representative objects. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. IEFE, 2012.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimiza- tion via stochastic path-integrated differential estimator. In Advances in Newral Information Processing Systems, pp. 689 699, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andrcetto, and Hartwig Adam. Mobilencts: Efficient convolutional neural networks for mobile vision applications. Xiv preprinl orXiv: 00111744444..1. 2017.
Junzhou Huang, Tong Zhang, and Dimitris Metaxas. Learning with structured sparsity. Journal of Machine Learning Research, :2(Nov):3371 337-33133771-4 2011.
Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29: 1145-1153, 2016.
Rodolphe Jenatton, Guillaume Obozinski, and Francis Bach. Structured sparse principal component analysis. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 366 373, 2010.
Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, and Francis Bach. Proximal methods for hierar- chical sparse coding. The Journal of Machine Learning Research, 12:2297-2334 22344, 2011.
Ric Johnson and Tong Zhang. Accolerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315 323, 2013.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, Universily of Toronlo, 2009.
Yawei Li, Shuhang Gu, Christoph Mayer, Lue Van Gool, and Radu Timofte. Group sparsity: The hinge between filter pruning and decomposition for network compression. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 8018-8022 2020.
Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. arXiv preprint Xixi 1802. 04477, pp. 5564-5574, 2018.
Shaohui Lin, Rongrong Ji, Yuchao Li, Cheng Deng, and Xuelong Li. Toward compact convnets via structure- sparsity regularized filter pruning. IEEE transactions neural networks and learning systems, 31(2): 574-588, 2019.
Shujun Liu, Jianxin Cao, Hongqing Liu, Xichuan Zhou, Kui Zhang, and Zhengzhou Li. Mri reconstruction via enhanced group sparsity and nonconvex regularization. Neurocomputing, 272:108-122 -21, 2018.
Lennart Ljung. Analysis of recursive stochastic algorithms. IEEE transactions on automatic control, 22(4): 551 551-575, 1977.
lyya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arxio preprinl arXiv:1608.0000 2016.
Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Gap safe screening rules for sparsity enforcing penalties. The Journal of Machine Learning Research, 18(1):4611-4703, 2017.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 2009.
Julie Nutini, Mark Schmidt, and Warren Hare. "active-set complexity" of proximal gradient: How long does
it take to find the sparsity pattern? Optimization Letters, 13(4):645 10666555555666 2019.
Nhan H Pham, Lam M Nguyen, Dzung T Phan, and Quoc Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. J. Mach. Learn. Res., 21 (1(10)):144 2020.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint Xiv: 1606 05250, 2016.
Lorenzo Rosasco, Silvia Villa, and Bang Công Vü. Convergence of stochastic proximal gradient algorithm. Applied Mathematics 8 Optimization, pp. 1-27, 2019.
Volker Roth and Bernd Fischer. The group-lasso for generalized linear models: uniqueness of solutions and efficient algorithms. In Proceedings of the 25th international conference on Machine learning, pp. 848 855, 2008.
Nicolas L Roux, Mark Schmidt, and Francis R Bach. A stochastic gradient method with an exponential convergence rale for finite training sets. In Advances in newral information processing systems, pp. 2663- 2671, 2012.
Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini. Group sparse regularization for deep neural networks. Neurocomputing 241:81- 89, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXic:1409. 1556, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is you need. In Advonces in newral information processing systems, pp. 5998-6008, 2017.
Wei Wen, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. arXie preprint orXiv:1608. 035.006606636,, 2016.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist. novel image dataset for benchmarking machine learning algorithms. arXiv preprint 108.0077777777 2017.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(Oct))2543 2554225666 2010.
Lin Xiao and Tong Zhang. proximal stochastic gradient method with progressive variance reduction.
SIAM Journal on Optimization, 24(4):2057 2075, 2014.
Haiqin Yang, Zenglin Xu, Irwin King, and Michael R Lyu. Online learning for group lasso. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 1191-1198, 2010.
Minghan Yang, Andre Milzarek, Zaiwen Wen, and Tong Zhang. A stochastic extra-step quasi-newton method for nonsmooth nonconvex optimization. arXiv preprint arXio:1910.0099 2019.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the
Royal Statistical Society: Series B (Statistical Methodology), 68(1):49-6)) 67, 2006.
Junyu Zhang and Lin Xiao. Multi-level composite stochastic optimization via nested variance reduction.
arXiv preprint Xixi 1 1908. 1 11468, 2019.
15

---

Published in Transactions on Machine Learning Research (06/2023)
A Proofs.
A.1 Proof of Lemma 3.5
Lemma 3.5 If the Enhanced Half-Space step is computed during the kth epoch of Algorithm the 1th iterate 0x,441 computed in Algorithm satisfies
1
then
(1- ( Ouk
2
(1 (1-
Lak
|| (
BB. (3xx,,4))))
#x,. S ((x,,))))
04k
A
Lago2T(
Bi.el < N)
+
||
2
where the expectation is taken with respect to Be and conditioning on TR,t, I(.) is the indicator function,
Amax max 1 E g},
((r,, -al V ()), (ma, (Feerll
PPRJJ k
{gg
Ix,
ct.
I BBAD
I
I
and o² the bounded variance constant satisfying
V\()
with the expectation taken with respect to randomly sampled i. (The existence of the constant o² follows from the finite-sum structure of f()), the uniform sampling scheme, and Assumptions 3.1 and 3.4
Proof. We first prove the existence of a. By Assumption 3.4 and Lipschitz continuity Vi(()), one can see that [[)) is uniformly bounded by some constant C. By definition
N-1
|)<0)|| NZ
[V((
V((x))V\1(())
1=++1
Therefore,
E f((2) [f(=)]/ = -
N
2 N-1 N
N Σ |V)(2)1
Σ Σ V(()))V\1(()
$ (N 1)C² + 2 N-1
Σ
Σ
Vf [+)
for some 0.
Next, prove the main result. An Enhanced Half-Space step can be written as T2.411 Zx.t -agda.t where
V V94B,, (iv.e)
if k,1
[ds,.] =
|Tulo/ax
k if E 7B0J
(7)
g THS k,t
16

---

Published in Transactions on Machine Learning Research (06/2023)
Let Ekis (r(0k,)) and Ek,C-1 E @r(zx,(+1). Therefore
((xx(++1) ( 1 axdr,e)
f(āk,t andr,) + r( andx,r)
< ((xk.)) OA V ( dx + // || r( - 0
2
(8)
I.
= =v(Øk.) - 0. V f ( ) dx + ||dx,ell - on 156,041 - Exge + Ex,e) dua
x
2
= - az (* [R,]] du, + L
2 a ||d on [EK, - Emettl 1)t de
where the only inequality holds by the convexity of r, Assumption 3.1 and Since the and Exæ41 are arbitrary, consider the following specific choices:
X L ex re Au Fr. dell Aglulg:
if E Ihe
( A Lo To (gg
if g Iht and EE04119 = if g E Ih
[5x.el9
if g I k if g Ihe n DIR341
where I/c = {g E G [ # 0}, Ih.- tg E [ = 0}, Mg E RRaa and |u 1
For any E I by definition E k and g E 2h,441 it follows that
Ek [s, for all g Ih,t
(9)
If we define pl <11(2x,1ggl1 then it follows that
[R [|| [|[
[
[5x, - Ek,t2a dx.+= = Σ
Lgldk,
|| [[
ge Toue
p2, [aacee
Ph. (7x,
Σ
Xg
ph.
[
9
||@a.elo - [x.e-1oo1l [ldk
Σ BEZOND
Xn
|I[da.lall" Pk.t
ak a
PR.
gEZOME
where the first equality holds by (9) the second incquality holds by Cauchy-Schware inequality, and the third inequality holds by the non-expansiveness of the Euclidean projection and the fact that [[ 2 Pl. and [1 2 Ph. for all g E IERAD. We would like to point out for the third inequality that it holds as fl [āech [ea. and of (e..tll are the projections of [#x,1g and [#x.4+1lg onto the ball centered at the origin with [
radius ph.,, respectively. Since [øv,r] and [#x,1+1ly are outside the ball, for all g E 7 the result follows from the non-expansiveness of projections. Combining this incquality with (8) we obtain
L
16 ((2,0++1) S (((.))))) - on [V)()x.)) + Ex,e' du,t + a ||da.ell + au [EN,e - Ix,e+1) du.t
2
L
S {((a)))) (V)()))) Ex,e" da.t +
Idd..el' 112 + af
Σ Ag
2
= =((()))) - on (v I +( T [dr.
L
111d
(10)
+
a
[ddk 1:00
+ a
Σ
Ag
2
Ph.
< ((0,..)) az (Vzze ((22,)) (dueel
a
L
2
A a
Σ
||
2
2
gEIBND
17

---

Published in Transactions on Machine Learning Research (06/2023)
where the only equality holds from
Notice that for any E IPROJ by defnitiin,, one has ((0x,19 ax V (ix,)) T [av,elo I < <11[
k.t
Taking expectation with respect to BR it follows that ([0s,1ls a& [ I c <||[0,,,]gl'* Re- arranging terms, one gets
(V (( [ I (c - 1) 1|
Summing over all g E I for the above inequality, one has
ag (v Vi T [ax,ol2g0 S (c (c- 1) 1)|(18881
(11)
Note that
-ak (vrov(an)) [dk, = -ark ramn (āxxe)
[dk, Ork (V (Zzann (aannbb((xa (āx.e)) Idd.ellzgn
T
-akk
Virno 2b (xx,e)
V Zonn B., (#x.1) - Virpa [ zzzuo BB, (#x,t)
V Viguooi (tx.e)
1-6
Oik
Okk
(12)
where the second equality holds by
7 Now, taking the expectation with respect to Be on
12
one has
(Vzz
((BL))) [dk:slapp) < -ak
1-6 é | Izpps
ag E
(13)
a&
Similarly,
2
- Izzin 2'BB.. (#x. (2x..) ||
[du.elzm
(14)
a
Since for any random vector Y, B[I|Y [[[]|| TEI - by taking the expectation with respect to BR one obtains
E
V ronr W's (#x.1)
V remi dh (t
V raun th75,. (00x.t)
Vr ( |
V Tam do (+)
+ E
V VES.. -V
kit
(15)
V Vi ob (#t..)
+ +
Σ (V)((E).)) (ffiia.))-(((...)))))
||
iEBr.
0²1(( 11((BR.. < NN)
Vzgno vb (
|Bkr
where 1(-) is the indicator function. Again, taking the expectation with respect to B on
4
together
with 15 one has
E
da. 1zz
27
B < N)
Be,r
+
| (znue ((x,,))
+
=
a
@x,elzma
(16)
18

---

Published in Transactions on Machine Learning Research (06/2023)
Finally taking expectation over the entire history over
10
together with
13 and 16 one concludes
EB., ((0,(,, &x.ec S (
ax
| (2xx, (x. ( Tmua
[
Ol1
+
La
[ Bx,el < N)
+
V TonD rb (a)k,e)
11+ +
[ 1zg0
+
maxx
Σ
||
2
|B,cc|
x2c
( - a1x(1
Lack
V Vzzi V (Tck,t) ||
11-001--- 2/)
(1-6
||
||
ack
Amax
La (Baae
< .N
Σ
|| +
6
2/
gE2t.
which completes the proof.
A.2 Proof of Theorem 3.7
Theorem 3.7 Under Assumptions 3.1 3.1 and with e E (0, E (0, a au S min ((1-c) 1 and
[& N for all k, mp(mp- 1/2) S b, and Ba,l min(m N) for all & and t, then Algorithm generates sequence of iterates {#R JAEN such that lim on ([))(())))ll 0.
Proof. We first introduce the index sets
Kp {k: kth epoch proceeeds Prox-SVRG step} and Kh {k: kth epoch proceeeds Enhanced Half-Space step).
(17)
(18)
Summing over the first. epochs and laking expectation over all past history, we have
E [(x)( = E (b(o)) +
(Wb())))) - ((x=-11))
#=1
E (xx0) + Σ (b(()) (((x=1))) + Σ (b(()) ((L-1))
(19)
kEKw
kEKP
< ((()))
Σ
E
an
(1
Lac
V gana th (#xK,))
2
+
+(1-
1-E
1200
2
2
k,
kEKN
t=0
Amar
Lodez ax
mp
E
[
+
E
(20)
RPE
2|Brrr
36L
REKC
gEZ240
kEKP
holds since the index set (1......) can be partitioned into two disjoint sets Kr and K.p. When k E KH; we upper bound the 1T [+(x)) - ( using Lemma 3.5 similarly we use
19
Lemma
3.6 for k E Kp.. Then, we the Law of Total Expectation to get [(((x)) (xxx-1)]
E
E
18.. >T (ax))) - 1)) I]] for the next inequality, which leads to the upper bound presented 20
in
Using Assumption 3.4 yields
S (xx)))
Σ REKW
E
Lark
A raw (
+
(1-e
L)
[7]
2
2
1=0
22
T
mp
+
E (1s(
(21)
x2C
2b
36
kEK
1=0
kEKP
1=
19

---

Published in Transactions on Machine Learning Research (06/2023)
where ng = [g]. Now let I + oo, by the Assumption 3.2 and the Assumption 3.3 one concludes that
Σ
OK
E
V
00;
(22)
k
1=U
Σ
1 1-
2
|
< <0;
(23)
2
kEK
1=0
mp
m)]l < 0o.
(24)
kEK
By the design of the algorithm, we consider three cases.
Case-1. [Kpl = oo and [rrrl co. From 24 we conclude lim infx E [[|s(<
m)ll O.
Case-2. |Kpl < oc and |Kr]] cc. Since
2 + [1<00 7) 1) ||
[|s( w)) = (as w)]
(25)
in order to show that lim inf E [|s( r)ll
= 0, it is sufficient to show that 0 holds simultancously.
lim inf to E [s
m) 1 and lim in [s(ax:; m1
+ We first prove lim inf
[s m)lzz Since KKHl = co and E a = co, we conclude from
O. Notice that once a group of variables being projected to O, that group will never be included in the computation of the Enhanced Half-Space step anymore based on the design of AdaHSPG+. Hence, there cxits a >> 0 that for all k: 2 K,t e
22 that lim in Em 1
EE Vigan (
(O...., my 1), IORAD
IHs holds, which implies lim inf t=
-1 E
V Ta (#x..) 0. By
Lemma 2.4 in Curtis et al. (2020), we have
V ((x+) [s(
(26)
holds for all k and & {0, (O...... .......,.... ma 1}. Since $x,0 = Lk:
Igrad
T and 26 we have
m
in
1s Is m)zz
lim inf
IB
Vies ( 0,
1=
hence lim in to
[s 7)l zm E
0.
We then prove lim on
[s(cow M2zzqe
0. By the line Algorithm 1
MHS X.k
Xk 4
1
||<(
m)
1 > [V
(27)
where the final inequality holds from that
26
Taking expectation and liminf on both side concludes
lim inf E
[s 1zzz
lim in
| (ab()))) 0.
(28)
8-000
/ k-000
Case-3. [Krl = oc and [Knr co, then the result follows from the Case 1.
20

---

Published in Transactions on Machine Learning Research (06/2023)
A.3 Proof of Theorem 3.8
In this section, we compare the group sparsity identification properly of AdaHSPG+ and Prox-SG. First, recall the non-degeneracy assumption
0<8==
min inf (A [[ gE2" (()) BCIn]
# O, (29)
Given any k E N+, if the kth epoch performs an Enhanced Half-Space step with ag S 1/L, then for any E {O...., my -1 satisfying 16 - x=I| S r-etout [ s( m) and 6 I (=)) [[[=x,)]g]] |I ||[v.... (ool it holds that AdaHSPG+ yields I (xx" C I ( where (x) collects groups of variables that are 0 at
Theorem 3.8
2056
Proof. First, if 9 E (x))) (I then we have [0x, 0, which implies I Thus [āa, [ = 0 as the kth epoch perform Enhanced Half-Space step, and therefore g E I (x* (2*) (TT(Ex)44)
Now, if (x² [ for any inner-iteration (O...., my 1}, there are three cases to consider.
Case-1. g E 7 (x') n k.t
Case-2. g (x=) n I ( g
[#x, + [s( 7)}g 0}.
Casc-3. g I I ( g || K|| y (#),
Based on the conditions provided above for Theorem 3.8 the Case-2 does not hold due to condition (#r, + (s( # O, and the Case-3 does not hold due to condition k. S mingez"(e>)) || V[[V (aal)) Therefore, it is sufficient to consider g E (xx" n I
[#x, a V Br, (#K.1) [ ||(
|| 1|2 - oxl V V...A. ( (#x.11g e|
V [BB... (#x gg + > [ēn,tla T
= (1 <) 11 an
[
[
(30)
=(1 (1 <) [| az
V fB., (# 11% [Rtee] a > [
<(1 <) || - on || /B.. (xx,))))
[x xx
[ {(1 - | aa ||| (fx.
By the Lipschitz continuity of Vf, we have that for each & I (xx") 1I
||[ fB. (#x,) v fB.. (xx) Moll < L || - x "lllll L ||
(31)
fi.. (#x, )oll S L || + ||[v fIS.. (x }lal
Combining with the definition of 6, which implies that ||[ fB.. (x }l, || < A - 26 that
[| (#x,))l91 < L |[ + X - 28.
(32)
Hence combining with (1 S 1-cta, T
200
30
can be further written as
[ - ag VuBB.. (Tx,t) Ig [ - <|[@x,tlgl1
[ {(1 <) [1 a | fb., (#x,1)loll axa]
< | {(1- - e) ||
+ L ||| | + and - 22 a4
|| {(1 - e + L)
||| || || - 20
(33)
2
<
| (1 (1-
e + aax
1 - + arL 2ayd
||[ (204-5 -2045) =0,
21

---

Published in Transactions on Machine Learning Research (06/2023)
which shows that [āg. ag VVB,, ( [ I =|||l,, Hence the group projection operator is triggered on g to map the variables to wero, then y E (m),+t)) i.e., [#R,i+1g = 0. Therefore, the group sparsity of æ can be successfully identified by Half Half-Space step, i.e., (x)) ) _ I (#x,(+1).
We show the generic sparsity identification property of Prox SG for any mixed & /ll regularization for 2 1. Lemma A.1. If æ x²I1p S min ax,), where 1/p + 1/p' = ( oo if p 1), then the Prox-SG gields that for each y (x=", [2x+ 1lg holds, i.e., (xx" C T (*2+1).
Proof. It follows from the reverse triangle inequality, basic norm inequalities, Lipschitz continuity of Vf(x)) and the assumption of this lemma that for any g 9,
fB (*x)lll -llVe (= "sll,,
I ||[ (ax))
V TfB (2"))llll))
V Vi, (mtx)
VSs. (a 11p
(34)
8
$ L | x²1,,
S L 6. L
By 34 we have that for any g (z)"),
S IlV.BB (*x)lll,,
) + S 25 2
(35)
where the final inequality holds due to [[ Sss (a* Illllp S X 25 by the definition of ā proposed before. Combining (35 and the assumption of this lemma, the following holds for any ar 0 that
| ar V SB, (awx)lllly ||awwlllor + ||a V.s, (aw))llll S and + anlA 5) =ard
(36)
which further implies that the Euclidean projection yields that
Enclidean Proj (x))) ([= - as V ff.. (#x)la) = [ - a& V (xx)lo-
(37)
Combining with 37 the fact that proximal operator is the residual of identity operator subtracted by Euclidean project operator onto the dual norm ball and [x = 0 for any E (x") (Chen 2018), we have
[#x+1lg- = Prox AlI-11, (LEx ap fB. (xx))a)
I
Enclidean [x as fis (Ixx)]g Proj ProjB(Il-I,:a.A))
(38)
Fh On VIS (2x))
-( - Cr V SB, (2xx) = 0,
consequently (x=") E (xx+1), which completes the proof.
B
Additional Experiments
B.1 Convex setting
As in (Xiao & Zhang 2014 Curtis et al.) 2020), we first consider the convex logistic regression problem with mixed & reggerregulaiizttionn for binary classification. Given data samples (di, (dv, Iv), where d, e R" and 4 (-1,1) 13 denote the feature vector of the ith data sample and the corresponding ground truth label, respectively, the problem is formulated as
log(1 +e 4:== d((b) + Σ> ||x0)|||
min (#:))R
N
9Eg
where E R is the bias. We consider different regularization strengths by choosing >, from (10-2, 10-3, 10-4) for g E and lead different levels of sparsity in the obtained solutions, correspondingly. To form g. sequentially go through the variables collecting them into 100 groups
22

---

Published in Transactions on Machine Learning Research (06/2023)
We select all datasets from the LIBSVM repository (Chang & Lin 2011 that (i) have at least 100 features so that the formulation of 9 is well defined, (ii) have at least 102 samples so that a stochastic approach is appropriate, (ii) can be stored in main memory (16 GB); and (iv) have an accompanying test set so that the testing error can be computed to evaluate the models obtained. Based on these criteria, we ended up with the four publicly available large-scale datasets a9a, kdda, rev1, and w8a (see Table 4 for more details). All convex experiments are conducted on a 64-bit operating system with an Intel 17-7700K CPU @ 4.20 GHz and 16 GB random-access memory.
Table 4: Summary of datasets.
Dataset
# of Training Samples
of Testing Samples
of Features
Attribute
89a
3.26 x 10"
1.63 x 10"
1.23 10"
binszy {0, 1}
kdda
8.41 x 109
5.10 x 10
2.02 107
real [-1, 4]
rov1
2.02 x 104
6.77 10
4.72 10
unit-length
w8a
4.97 10
1.50 10*
3,00 10a
binary (0, 1}
All algorithms tested were run for maximum of 100 epochs. The mini-batch size b is set to min (256, [0.1NN] suggested in (Yang et al. 2019). The step size og is set following the approach in (Xiao) & Zhang 2014 wherein an upper bound for the Lipschitz constant L is computed as max; ||d: 1| /4, and then ag = 4/ max; ||, for Prox-SG, Prox-SVRG, HSPG, and AdaHSPG+, For HSPG set t 0 and switch to the Half-Space step after 50 epochs (these are the default values for HSPG).
We use the final objective value of 4,, group sparsity ratio, and testing accuracy as metrics to evaluate the performance of an algorithm. The group sparsity ratio is the ratio between the number of zero groups in the solution returned and the total number of groups. All metrics are obtained by averaging across five independent runs. We report the results for Ag E {10-2 10-3, 10-4] for all g E 9 in Table 5) where we mark the best values in bold font to facilitate comparison. As shown in the tables, larger values for Xg result in greater group sparsity ratios and worse final objective values and testing accuracy. One also can observe that the solutions with X₂ 10-2 are zeros for the dataset revl and the solutions with Ag = 10-3 and X = 10-3 are full dense for some datasets, This is indeed expected behavior since, for a given problem, there are two thresholds À > 0 and À > O. Whenever Ag 2 A, the solution becomes 0, i.c., the group sparse ratio 100%; on the other hand, when >g S 2, the solution becomes fully dense, i.e., group sparse ratio 0%. X and À varies from one problem the other.
AdaHSPG+ and HSPG clearly perform the best in terms of the group sparsity ratio over the test problems, and all of the algorithms perform similarly in terms of the objective function value and testing accuracy.
Table 5: Results convex problems for X, (10-2, 10-3, 10-3,10-1) for all g G, where report numbers in the form of final v group sparsity ratio / testing accuracy.
Dataset
Prox-S0
Prox-SVRG
BSPG
AdaHSPG+
Ag = 10
39a
0.438
73.0%
83.6%
0.1s3
86.0%
83.7%
0.4388
86.0%
33.7%
0.438
86.0%
783.7%
kdda
0.183
98.0% / 87.1%
0.183
99.0%
87.1%
0,184
99.0%
86.9%
0.183
99.0%
87.1%
revl
0.693
100.0% / 47.5%
0.693
100.0%
47.5%
0.693
/ 100.0%
/ 47.5%
0.693
100.0%
/ 47.5%
w8a
0.167
78.0% 97.0%
0.166
97.0% 99.0%
0.166 99.0%
97.0%
0.166
99.0%
97.0%
10-3
0.347
755.0%
85.0%
0.347
7 58.0%
85.0%
0.347 7 60.0% / 36.0%
0.347
38.0%
86.0%
kdda
0.133
0.0%
89.3%
0.133
0.0%
89. 2%
0.133
0.0%
89.3%
0.133
0.0%
89.3%
revl
0.461
0.0%
93.2%
0,461
41.2%
93.2%
0.461
93.2% 36.0%
47.0%
0.461
47.0%
93.2%
w8a
0.118
3.0%
97.2%
0.119
16.5%
97.2%
0.113
97.2%
0.113
36.0%
97.2%
Xg 10
395
0.327
33.6% 7 55.0%
0.327
7 15.0%
85.0%
0.3277
25.0%
85.0%
0.327
25.00 25.0%
885.0%
kdda
0.112
0.0%
89.5%
0.112
0.0%
89.5%
0.112
/ 0.0%
89.5%
0.112
0.0%
89.5%
rovl
0.164
0.0%
95.9%
0.176
0.0%
95.8%
0.164
0.0%
95.9%
0.164
0.0%
95.9%
w8a
0.097
0.0%
97.5%
0.096
0.0%
97.5%
0.097
0.0%
97.5%
0.096
0.0%
97.5%
23


Reviews:
[{"review_id": "p6lvqga3Wv", "reviewer": "Reviewer_dnVZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* To my knowledge, the methodology is novel, and the problem that the authors study is interesting.\n* The numerical comparison looks appropriate, and the improvement in terms of obtained sparsity (in the non-convex case) seems significant.\n\n## Weaknesses\n\n* I'm afraid there are details that I still don't fully grasp, in part (probably) because of a lack of clarity, notation inconsistencies lack of justification of specific steps (see below).\n* Given the results presented in the paper, I believe the qualitative description of these are often exaggerated (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a new stochastic optimization methods for structured $\\ell_1$ minimization problems. The authors based their method by combining previous ideas while leveraging a new switching strategy, providing asymptotic convergence in expectation for convex problems. Empirically, the authors demonstrate their algorithm in convex and non-convex problems, showing superior performance in terms of the obtained degree of sparsity - particularly in the non-convex application of training sparse neural networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Main concerns:\n* I have some trouble understanding some parts of this algorithm. More specifically, while the authors do explain that some of the benefits of their approach relies on replacing the 2-parts algorithm by an automatic switching strategy, is not quite clear why this is indeed beneficial. Moreover, it is also unclear to me why the projection step in Eq 5 is needed; naturally, probably this is clear to those readers who are already very familiar with HSPG, but I can't pin exactly to the conceptual reason this step is beneficial to the minimization of Eq. (1).x\n\n* I find some statements throughout the manuscript exaggerated. For example, the authors refer to their \"significant improvements\" over HSPG, which might be true for the improved sparsity, but the presented converge result is weaker (it's only an asymptotic result). In other places (e.g. page 2) the authors mention that HSPG depends on heavily tuning some hyper-parameters, alluding to the fact that their method seemingly gets around this problem. Yet, the proposed method also has a large number of hyperparameters that need to be manually defined, and seem to arbitrary values (see Implementation details in Sect 4.1).\n\n* The results reported in the tables clearly indicate that the presented method is superior in terms of the final achieved sparsity (at least in the non-convex case). However, once looking at the training curves in Fig 2 and 3, these are often very erratic, and the final numbers clearly depend on how long the optimization algorithm is run for. This weakens the observation that their results are homogeneously better. \n\n* Notation and nomenclature needs to be improved. Very often $x$ and $\\mathbf{x}$ are used interchangeably (see e.g. Eq 3). Moreover, what the authors refer to as \"proximate gradient step\" (in Eq 2) is in fact a gradient mapping operator - please see [Beck, Amir. First-order methods in optimization, 2017,] Chapter 10. The gradients $\\nabla_g\\psi_\\mathcal{B}(x)$ are confusing as it seems that the gradient is taking w.r.t. the assignment of the group, $g$. \n\n* There authors often generally mention that, unlike other methods, theirs obtains a better degree of sparsity (E.g. in Sec 1.2). I would encourage the authors to stress that this is true in the non-convex case. In the case convex, the solution is typically unique whp, and so the degree of sparsity depends not on the algorithm but on value of the regularization parameter.\n\n* I'm unsure about Assumption 3.4. More precisely, I understand why this is needed, but it seems to me that the authors should be able to derive this condition under assumptions 1-3, employing the fact that the projection is a non-expansive map and that the step size is chosen appropriately. Thus, is it really necessary?\n\n* In commenting on Lemma 3.5, the authors state that if the stepsizes are chosen small enough, and the batch size sufficiently large, then EHS decreases the function value. Yet, from the expression in Lemma 3.5, I believe it's also true that, regardless the value of the batch size, this can be made to decrease if $\\alpha_k$ is chosen small enough, no?\n\n* Commenting on their experiments, the authors mention in passing that the provided relative runtimes (in appendix) shows that their methods is competitive w.r.t HSPG. It is true that the runtime is in the same order of magnitude, but it's also true that the runtime is consistently higher. The authors should state this, and moreover, comment on the sources for this (slight but consistent) increase.\n\n* The authors could make their conclusions more precise, by instead of saying \"... AdaHSPG+ significantly outperformes HSPG [..] in terms of various performance metrics...\", saying that the improvement is obtained in terms of the resulting sparsity in non-convex problems, at the expense of slightly different theoretical guarantees and slightly increased runtime.\n\n## Smaller concerns\n* Use of  \"quotations'' should be fixed, as they are consistently incorrect - use `` and ' '.\n* Abstract: \"employed each iteration\" -> employed at each iteration.\n* The first paragraph in the introduction is all about the use of structured sparsity in machine learning. Yet, referenced literature is only from 2016 onward. This disregards a huge amount of work on Lasso, Group Lasso, Hierarchical Lasso and its variants. I understand that the objective of this work is different from those contributions, but I find it incorrect to refer to these topics and not cite these contributions.\n* SAG seems undefined on Page 2?\n* \"HSPG [...] clearly has limitations\". It's unclear to the reader why it is specifically stated that \"clearly\" HSPG has limitations, particularly because all methods have limitation. Just state what those limitation are.\n* I think $\\nabla_\\mathcal{I}^{grad}$ in Lemma 3.5 seems undefined, as it's defined later. It'd be much clearer if its definition was moved up.\n* Missing capitalization before Theorem 3.7\n* what is $\\lim \\inf_{k\\to\\infty}$ in Them. 3.7?\n* \"stand-a-alone\" -> \"stand-alone\"\n", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kqXSAfYaWH", "reviewer": "Reviewer_jnWn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* Excellent/clear explanation (with illustrations) of the algorithmic mechanisms\n* Introduced hyperparameters are intuitive and their affects are discussed (except the sensitivity of kappa)\n* Overcoming the limitation of HSPG that once it zeroes out a group, it does not get re-updated. \n* Little to no effect on wallclock runtime\n* Good breadth of experiments\n\n# Weaknesses\n* A notation error regarding $N$ (unless I am just confused)\n* For the convex problem: hyperparameter sweeps for the convex methods seem necessary for an interesting comparison. Table 1 seems to only verify that they converge. When do the two main competitors differ? Maybe a robustness test would be interesting.\n* Although justification is given, complexity analysis is not hashed out. It's probably better to do this anyway, even if in the numerical experiments you explore the practical tweak (variance reduction in EHS)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors address the challenge of combining group-sparse regularization with stochastic optimization algorithms, which is famously challenging (challenging to have convergence guarantees, be computationally efficient, and provide group-sparse solutions). The authors propose a new algorithm that has faster convergence than a previously published algorithm due to integration of a variance reduction technique with a novel strategy for adaptively estimating the support of a potential solution.\n\nThe algorithm is iterative and at each iteration, one of two types of steps is performed based on an automatic selection method. Specifically, the set containing groups that are both predicted to remain nonzero after a batch prox-gradient step and are sufficiently far from the origin, is isolated. The prox-gradient steps for that and its complementary partition are computed; whichever partition's corresponding step is larger in magnitude is the set of variables that is focused on (how much \"larger\" being tunable by an algorithm parameter). If the former (support group) can yield a larger step then the Enhanced Half-Space (EHS) step is activated to explore whether those groups should remain nonzero. Otherwise some steps of Prox-SVRG are performed (proximal stochastic variance-reduced gradient method).\n\n \nProofs are provided to show that under specific conditions,\n* EHS decreases the objective function\n* Prox-SVRG decreases the objective function if batch-size is sufficiently large\n* A stationary point will be achieved by the overall algorithm if one exists. Asymptotic convergence is proved, while complexity bounds are not established (although insights are to provided for how they might be, it is avoided due to practical performance limitations).\n\nThe algorithm is demonstrated to outperform its primary competitor (HSPG: half space projected gradient algorithm) and their consitutent algo predecessors (proxSG, proxSVRG) on convex and non-convex problems. Performance is compared in terms of loss function value, group-sparsity ratio, and accuracy. Visual comparison of metrics as they evolve with training is provided for non-convex (deep neural network training) examples.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Critical to securing my recommendation:\n\n1. At times it seems clear that $N$ is the number of samples, but the summation over $f_i(x)$ also runs to $N$ in multiple places. I think you need a different variable the number of functions and number of samples... I think it would go a long way to denote an explicitly stochastic version of (1) in the same section.\n\n2. SAG is not defined in lit review (Sec 1.2)\n\n3. Above Eqn (2), you claim that Prox_r has a closed-form solution. However, you don't provide this formula and the reference you cite there does not either. I think since $\\mathbf{x}$ is in disjoint groups it's just soft thresholding applied to each $||\\mathbf{x}_g||$? I suggest you just say what it is (or provide a more specific reference).\n\n4. A hyperparameter sweep for more comprehensive comparison (see 2nd point in Weaknesses)\n\n# Simpler suggestions:\n\n## Sec 1.1\n* Perhaps one more sentence explaining pros/cons of overlapping vs non-overlapping group sparsity. i.e., time-invariance, sensitivity to group-size\n* It might be nice to have a sentence explaining why GS is referred to as L1/L2 norm (i.e., because it's equivalent to the L1 norm of a vector of L2 norms, and hence induces sparsity on that vector, removing some groups and keeping others).\n## Sec 1.3\n* In the first bullet point on improvements, please explain more explicitly what is the difference between \"an expectation-type result\" and \"a pure expectation-type result\"\n## Sec 2.1\n* paragraph break before \"The *switching mechanism...*\"\n* Also, that sentence could be rewritten backward to increase readibility.. i.e., explain first... \"The switching mechanism proceeds according to which set of variables, I^HS or I^NHS, is expected to yield more progress after a step of optimization, via EHS or PSVRG, respectively. This is gauged by their size...\" (or so). All that being said, is it trivial as to why the energy of the partition indicates potential improvement (more energy $\\Rightarrow$ more possible improvement) or is there more to it that is going unexplained? One sentence of explanation would go much further than \"it makes sense\".\n* Something is wrong with your quotes around \"projection\" above Eqn (5)\n* Accidental indentation in line 12 of Algorithm 2?\n## Sec 4.2\n* Since there is little effective difference between HSPG and AdaHSPG+ in the convex setting, it might be more useful to show results for a setting or metric that reveals a difference (e.g. 50 epochs, or \"epochs to convergence\").\n## Sec 4.3\n* Why isn't there a comparison with Adam? This optimizer is a go-to for many/most ML publications.", "broader_impact_concerns": "I don't have any concerns regarding ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QH3MUvaJbM", "reviewer": "Reviewer_riu1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- This paper shows the convergence of AdaHSPG+ to a stationary point for the group-sparse regularization (i.e., mixed $\\ell_1/\\ell_2$ problem), whereas the convergence guarantee of HPSG has not been provided for this problem.\n\n- AdaHSPG+ can find sparse solutions for deep learning models, maintaining the test performance achieved by the other methods such as Prox-SG, HSPG, and momentum method.\n\n**Weaknesses**\n\n- A major concern is a lack of convergence rate analysis shown for the other proximal methods. Because of this, we cannot see a certain separation from the deterministic method. Theorem 3.7 allows us to choose $m_h=m_p=1$. Then, the complexity per iteration under this setting is the same as the deterministic optimization methods (e.g., Prox-GD) because $|\\mathcal{B}_k|=N$. Therefore, Theorem 3.7 cannot distinguish the performance between the stochastic update of AdaHSPG+ and the deterministic update setup above. And hence, I suspect that the convergence of AdaHSPG+ suggested by Theorem 3.7 basically relies on the deterministic update.  \nThis point would be important to justify the claim that the proposed method does not suffer from randomness and does not struggle to obtain group-sparse solutions, which are raised as weaknesses of the past stochastic proximal methods in Section 1.2.\nIn addition, the lack of convergence rate analysis makes it impossible to suggest better hyperparameter settings to converge fast.  \nIt would be nice if the authors could show the theoretical benefit of the proposed method based on the convergence rate analysis.\n\n- Assumption 3.4 requires the boundedness of the iterations. Basically, this kind of a-posteriori assumption is not preferred. If the authors adopt this assumption, It would be better to give sufficient conditions or specific examples to satisfy it.\n\nMinor comments:\n\n- In Algorithm 2: Should $\\mathcal{B}_k$ be added to the input of Algorithm 2 because it is used on line 2?\n\n- In Algorithm 2: The indent of lines 10 and 11 should be corrected.\n\n- In Experiment: How were groups of the fully connected layer in CNN models made? I could find an explanation for convolutional filters, but could not find it for fully connected layers.\n\n- In the proof: The proof of the existence of $\\sigma$ on page 15 is incorrect (maybe typos) and redundant.  If we make use of boundedness $||\\nabla f_i(x)||\\leq C$, then the variance can be immediately upper bounded by this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new method (AdaHSPG+) for nonconvex stochastic optimization problems under the group-sparse regularization (i.e., mixed $\\ell_1/\\ell_2$ problem). AdaHSPG+ resolves the several limitations of the most relevant method (HSPG) summarized below: \n\n(i) HSPG is a two-stage method where the second stage requires a sufficiently accurate solution provided by the first stage to achieve better performance, resulting in the costly tuning of switching time. \n\n(ii) The convergence of HSPG is not guaranteed for mixed $\\ell_1/\\ell_2$ problem because it is not Lipschitz continuous in a neighborhood of the origin.\n\n(iii) Limited empirical performance due to the expensive tuning cost of crucial hyperparameters. \n\nThe proposed method (AdaHSPG+) is not a two-stage method and the paper shows the convergence for mixed $\\ell_1/\\ell_2$. The improved empirical performance is also verified on the convex and nonconvex optimization problems. Especially, this work empirically verifies that the sparse solutions obtained by AdaHSPG+ are comparable to or better than those by Prox-SG, Prox-SVRG, and HSPG in the test performance for deep learning models on image datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be nice if the authors could give the convergence rate analysis and could show the theoretical benefit of stochastic setting (i.e., sufficiently large $m_h, m_p$ with small batch sizes) against the almost deterministic setup ($m_h=m_p=1$). See weaknesses for the detail.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TV99mhKf5a", "reviewer": "Reviewer_Xfq1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The authors analyzed the convergence of the proposed method. \n2. The authors also compared the proposed method with related methods on both convex problems and non-convex problems. Results show that it converged to a better sparse solution than compared methods. \n\nWeaknesses\n1. It is easy to combine multiple tricks and apply it for convex or non-convex optimization. Therefore, it is critical to provide the theoretical convergence rate showing that the proposed method does converges faster than compared methods. However, this paper only proved convergence and it is weak.\n2. The experimental comparison is also a bit weak. Since the authors did not show any convergence analysis for the convex problem, it is better to focus on the non-convex problem only.  The improvement in Table 1 is also not significant. \n3. The  hyper-parameter details in the experiments for compared methods are not clear and using default value is not fair either. For a fair comparison, a sweep of hyper-parameter for all methods are required. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed an Adaptive Half-Space Projection Method for composite optimization. In the paper, authors analyzed the convergence of the proposed algorithm and proved that it can converge to a stable point finally. The authors also compared the proposed method with related methods on both convex problems and non-convex problems. Results show that it converged to a better sparse solution than compared methods. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. A more compressive theoretical analysis is required. The authors should show the convergence rate of the proposed method at least and converging faster than compared methods.\n\n2. For a fair comparison, a sweep of hyper-parameter for all methods are required. More details about how these values are selected should be clear in the paper.\n\n3. If considering the convex setup in the experiment, it is better to provide theoretical analysis in the paper too. A faster convergence rate should be achieved compared to the non-convex setup. Otherwise, it is better to focus on the non-convex setup and perform more experiments. From the existing figures, it is hard to believe that the proposed method outperform other methods consistently. ", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors combine a group-sparse regularization with stochastic optimization algorithms, and employ a new switching strategy. They also provided an asymptotic convergence in expectation for convex problems. After the revision, the authors also provide sufficient numerical experiments to support using their algorithm, and all the reviewers agreed the paper should be accepted. 
Decision: Accept (poster)