Smooth Bilevel Programming for Sparse Regularization
Authors: Clarice Poon
Gabriel Peyré
Venue: NeurIPS 2021 Poster (2021)
Keywords: Sparse regularisation
Lasso
Basis pursuit
iterative reweighted least squares
bilevel

Abstract: Iteratively reweighted least square (IRLS) is a popular approach to solve sparsity-enforcing regression problems in machine learning. State of the art approaches are more efficient but typically rely on specific coordinate pruning schemes. In this work, we show how a surprisingly simple re-parametrization of IRLS, coupled with a bilevel resolution (instead of an alternating scheme) is able to achieve top performances on a wide range of sparsity (such as Lasso, group Lasso and trace norm regularizations), regularization strength (including hard constraints), and design matrices (ranging from correlated designs to differential operators). Similarly to IRLS, our method only involves linear systems resolutions, but in sharp contrast, corresponds to the minimization of a smooth function. Despite being non-convex, we show that there is no spurious minima and that saddle points are "ridable'', so that there always exists a descent direction.  We thus advocate for the use of a BFGS quasi-Newton solver, which makes our approach  simple, robust and efficient. We perform a numerical benchmark of the convergence speed of our algorithm against state of the art solvers for Lasso, group Lasso, trace norm and linearly constrained problems. These results highlight the versatility of our approach, removing the need to use different solvers depending on the specificity of the ML problem under study.

Smooth Bilevel Programming for Sparse Regularization
Clarice Poon,
Gabriel Peyrét
Abstract
Iteratively reweighted least square (IRLS) is popular approach to solve sparsity- enforcing regression problems in machine learning. State of the approaches are more efficient but typically rely on specific coordinate pruning schemes. In this work, we show how a surprisingly simple re-parametrization of IRLS, coupled with bilevel resolution (instead of an alternating scheme) is able to achieve top performances on a wide range of sparsity (such as Lasso, group Lasso and trace norm regularizations), regularization strength (including hard constraints), and design matrices (ranging from correlated designs to differential operators). Similarly to IRLS, our method only involves linear systems resolutions, but in sharp contrast, corresponds to the minimization of a smooth function. Despite being spurious minima and that saddle points are
non-convex, show that there "ridable", so that there always exists a descent direction. We thus advocate for the use of BFGS quasi-Newton solver, which makes our approach simple, robust and efficient. We perform a numerical benchmark of the convergence speed of algorithm against state of the art solvers for Lasso, group Lasso, trace norm and linearly constrained problems. These results highlight the versatility of our approach, removing the need use different solvers depending the specificity of the ML problem under study.
Introduction
Regularized empirical risk minimization is workhorse of supervised learning, and for linear model, it reads
min R(3) + 1 ((X3.)) PER"
(Px)
where X E m is the design matrix (n being the number of samples and m the number of features), L : IRm R [0, oo) the loss function, and : R [0, 20) the regularizer. Here is the regularisation parameter which is typically tuned by cross-validation. and in the limit case À = 0. (Po) is a constraint problem ming R(3) under the constraint L(X v) 0.
In this work, we focus our attention to sparsity enforcing penalties, which induce some form of structure the solution of P the most celebrated examples (reviewed in Section 2 being the Lasso, group-Lasso and trace norm regularizers. All these regularizers, and much more (as detailed in Section), can be conveniently re- re-written reviews more general formulations, this so-called "quadratic variational form" is especially simple in the case of block-separable functionals (such Lasso and group-Lasso), where one has
infimum of quadratic functions. While Section
R(3) min MERE
1
Σ
13,11
h(n).
2
DEG
'Department of mathematical sciences, University of Bath, Bath BA2 7AY, UK cmshp200bath. ac uu i CCNRS and DMA, Ecole Normale Supérieure, PSL University, 45 rue U'U,, F-75230 PARIS cedex 05. FRANCE, gaarriel.peyreeess....
peyreeens...... fr
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where G is partition of nI.....n.. k = 9 is the number of groups and h R - [0. oo). An important example is the group-Lasso, where R(3)= EE 18 is group- norm, in which case h(n) = >. The The special case of the Lasso, corresponding to the L norm is obtained when 9 = {i} for i = ..... and k = n. This quadratic variational form (T) is at the heart of the Iterative Reweighted Least Squares (IRLS) approach, reviewed in Section 1.1 We refer to Section 2 for an in-depth exposition of these formulations.
Sparsity regularized problems (Px) are notoriously difficult to solve, especially for small X, because R is non-smooth function. is the non-smoothness of R which forces the solutions of (Px) to belong to low-dimensional spaces (or more generally manifolds), the canonical example being spaces of sparse vectors when solving a Lasso problem. We refer to Bach et al. [201T] for an overview of sparsity-enforcing regularization methods. The core idea of our algorithm is that a simple re- parameterization of (1] combined with bi-level programming (i.e. solving two nested optimization problems) can turn (Px x into a smooth program which is much better conditioned, and can be tackled using standard but highly efficient optimization techniques such as quasi-Newton (L-BFGS). Indeed, by doing the change of variable (igg Ug) (vTg. 8g/ /Tg) in
PP
is equivalent
min f(v) PERA
where f(v)= _ min G(u,v) MER"
(2)
G(u, v) - 1
( Og u).
1
(3)
Throughout, we define to be the standard Hadamard product and for v R and u R" we define 3g u E IR" to be such that (u Og ") = ug'lg. Provided that + h(w o v) is differentiable and L( 3) is a convex, proper, lower semicontinuous function, the inner minimisation problem has a unique solution and f is differentiable. Moreover, in the case of the quadratic loss L(2, y) A 2/|z - yl.. the gradient of f can be computed in closed form, by solving a linear system of dimension m or n. This paper is thus devoted study the theoretical and algorithmic implications of this simple twist on the celebrated IRLS approach.
Comparison with proximal gradient To provide some intuition about the proposed approach, the figure on the right contrasts the iterations of a gra- dient descent on f and of the iterative soft thresholding algorithm (ISTA) on the Lasso. We consider a random Gaussian matrix X E RR 10x20 with A = |X 110 The ISTA trajectory is non-smooth when some feature crosses 0. In particular, if a coefficient (such as the red one on the figure) is initialized with the wrong sign, it takes many iteration for ISTA to flip sign. In sharp contrast, the gradient flow of f does not exhibit such a singularity and exhibits smooth geometric convergence. We refer to the appendix for an analysis of this phenomenon.
ISTA
Grad. flow
Contributions Our main contribution is a new versatile algorithm for sparse regularization, which applies standard smooth optimization methods to minimize the function I' in 2 We first propose in Section a generic class of regularizers R that enjoy quadratic variational form. This section recaps existing results under a common umbrella and shows the generality of our approach. Section 3.1 then gathers the theoretical analysis of the method, and in particular the proof that while being non-convex, the function f has no local minimum and only "ridable" saddle points. As a result, one can guarantee convergence to global minimum for many optimisation schemes, such as gradient descent with random perturbations [Lee et al. 2017 Jin et al.) [017]] or trust region type methods [Pascanu et al., 2014]. Furthermore, for the case of the group Lasso. show that is an infinitely differentiable function with uniformly bounded Hessian. Consequently, standard solvers such as Newton's method/BFGS can be applied and with superlinear convergence guarantee. Section 4 performs a detailed numerical study of the method and benchmarks it against several popular competing algorithms for Lasso, group-Lasso and trace norm regularization. Our method is consistently amongst the best performers, and is in particular very efficient for small values of X, and can even cope with the constrained case 0.
1.1 Related works
State of the art solvers for sparse optimisation Popular approaches to nonsmooth sparse optimi- sation include proximal based methods. The simplest instance is the Forward-Backward algorithm

---

[Lions and Mercier 1979 Daubechies et al. [004] which handles the case where L is smooth func- tion. There are many related inertial based acceleration schemes, such as FISTA [Beck and Teboulle 2009] and particularly effective techniques that leads to substantial speedups are the adaptive use of stepsizes and restarting strategies [O (O'oooghuue and Candes] [015]. Other related approaches are
proximal quasi-Newton and variable metric methods [Combettes and Vū 2014 Becker et al. (201)]
which incorporate variable metries into the quadratic term of the proximal operator. Another popular approach, particularly for the Lasso-like problems are coordinate descent schemes [Friedman et al. 2010]. These schemes are typically combined with support pruning schemes [Ghaoui et al. 2010
Ndiaye al.) 2017 Massias et al. 2018). In the case where both the regularisation and loss terms nonsmooth (e.g. in the basis pursuit setting), typical solvers are the primal- -unal [Chambolle and Pock 2011], ADMM (Boyd et al. 2 and Douglas- Rachffod algorithms (Douglas and Rachford 1956.. Although these schemes are very popular due to their relatively low per iteration complexity, these methods have sublinear convergence rates in general, with linear convergence under strong convexity.
The quadratic variational formulation and IRLS Quadratic variational formulations such as ! have been exploited in many early computer vision works, such as Geiger and Yuille| [1991] and Geman and Reynolds 1992]. One of the first theoretical results can be found in Geman and Reynolds [1992]. see also] Black and Rangarajan [996] which lists many examples. Our result in Theorem
can be seen generalisation of these early works. Norm regularizers of this form were introduced in Micchelli et al. [2013]. and further studied in the monograph Bach et al.) [011] under the name of subquadratic norms. The main algorithmic consequence of the quadratic variational formulation in the literature is the iterative reweighted least squares (IRLS) algorithm. When L(2, y) = b/2= y/3 the quadratic loss, natural optimisation strategy is alternating minimising. However, due the 1/1,, term, one needs to introduce some regularisation to ensure convergence. One popular approach is to add? & Eg "g to the formulation (I) which leads to the IRLS algorithm (Daubechies et al. 2010]. The s-term can be seen as a barrier to keep 72 positive which is reminiscent of interior point methods. The idea of IRLS is to do alternating minimisation over & and 7), where the minimisation with respect to 3 is a least squares problem, and the minimisation with respect to r) admits a closed form solution. A nuclear norm version of IRLS has been used in Argyriou et al. [0088] where an alternating minimisation algorithm was introduced. Finally, we remark that although nonconvex formulations for various low complexity regularizers have appeared in the literature, see for instance Rennie and Srebro (2005). HHasti et al. (2015), Mardani and Giannakis (2015). Hoff (2017) for the case of the & and nuclear norms, they are typically associated with alternating minimisation algorithms.
Variable projection/reduced gradient approaches IRLS methods are quite slow because the resulting minimization problem is poorly conditioned. Adding the smoothing term á Σg My only partly alleviates this, and also breaks the sparsity enforcing property of the regularizer R. We avoid both issues in ( by solving a "reduced" problem which is much better conditioned and smooth. This idea of solving bi-variate problem by re-casting it as a bilevel program is classical, we refer in particular to [Rockafellar and Wets, 2009 Chap. 10] for some general theoretical results on reduced gradients. and also Danskin's theorem (although this is restricted to the convex setting) in Bertsekas (197]. Our formulation falls directly into the framework of variable projection [Ruhe and Wedin 1980 Golub and Pereyra 22003, introduced initially for solving nonlinear least squares problems. Properties and advantages of variable projection have been studied in Ruhe and Wedin (1980), we
refer also to Hong al. [2017). Zach and Bourmaud [2018) for more recent studies. Nonsmooth variable projection is studied in van Leeuwen and Arav kin (016). although the present work is in the classical setting of variable projection due to our smooth reparametrization. Reduced gradients have also been associated with the quadratic variational formulation in several works [Bach et al. 2011 Pong al. 2010 Rakotomamonij al. 2008). The idea to apply descent methods over g(n) ming Ro (7) 3) 2|x3 - v1á- Although the function over 77 and / is discontinuous, the function g over 77 is smooth and one can apply first order methods, such as proximal gradient descent to minimise g under positivity constraints. While quasi-Newton methods can be applied in this setting with bound constraints, we show Section Ihht this approach typically less effective than our nonconvex bilevel approach. In the setting of the trace norm, the optimisation problem is constrained on the set of positive semidefinite matrices, so one is restricted to using first order methods (Pong et al. 2010
3

---

2 Quadratic variational formulations
We describe in this section some general results about when a regulariser has quadratic variational form. Our first result brings together results which are scattered in the literature: it is closely related to Theorem in Geman and Reynolds] [1922] but their proof was only for strictly concave differentiable functions and did not explicitly connect to convex conjugates, while the setting for norms have been characterized in the monograph Bach et al. [2011] under the name of subquadratic norms.
Theorem 1. Let R IR - IR. The following are equivalent:
(i) R(33) = (B à (3) where yp is proper, concave and upper semi-continuous, with domain Rd (ii) There exists a convex function vo for which R(3) = =nf - 2, + 1/()..
Furthermore, 1b(2) = (-4)" (-z/2) is defined via the convex conjugate (-4)" of -p. leading to ① using the change of variable n 1/2 and h(n) (1/n). When R is a norm, the function h can be written in terms of the dual norm R as h(n) = maX E: wim, Moreover, R(B)² inf
[, m,
h((n)= 11
See Appendix B for the proof this Theorem. Some additional properties of ab are derived in Lemma of Appendix B one property is that if R is coercive, then |=|- (z) +oo, so the function f is coercive (see also remark
2.1 Examples
Let us first give some simple examples of both convex and non-convex norms:
Euclidean norms: for R | 12, making use of R stated in Theorem I has h | llac
- Group norms: for G is partition of (I....,,), n.), the group norm R(B) = Egeg ||3, l. Using the previous result for the Euclidean norm, one has h(n)) = Egeg 1(%)ieglo.- This expression
can be further simplified to obtain ( with a reduced vector v in [ in place of R" by noticing that the optimal v is constant in each group g.
(a (quasi) norms: For R(B) |3]e where E (0, 2), one has (p()) wa/2 and one verifies that h(n) =an where Cg (2 (2-9), Note that for q > G. u + h(v²) v² for y is differentiable. Analysis and numerics for this nonconvex setting can be found in Appendix
Matrix regularizer The extension of Theorem | to the case where 3 B is matrix can be found in the appendix. When R = (BBBT) is a function on matrices, the analogous quadratic variational formulation is
EDO(B Z- + h(Z),
R(B) = min min ZES BER
(4)
where St. denotes the set of symmetric positive semidefinite matrices and h(2) = 2((=)))--( Letting U B and V z1/2, have B VU and the equivalence
1
min R(B) + B
2x IA(B) v12
(5)
min f(V) A min 1 ) VER=Xa
JUB + 2 MVT + 2X
1 IA(VU) 212.
(6)
UERax
where A : Raxr + T is linear operator. Again, provided that V - haV is differentiable, f is a differentiable function with VS(V) = Val(V V) + 1.4' (A(VU) u) and U such that XU + VT A (AVVV) - y) 0. For the trace norm, R(B) tr( br(VBBB B), have h(Z) tr(Z)
and dh(Z)- = ld. Note that, just in the vectorial case, one could write the inner minimisation problem over the dual variable a e R and handle the case of X 0.
3 Theoretical analysis
Our first result shows the equivalence between P and smooth bilevel problem.

---

Theorem 2. Denote Ly - L(-.v) and let I; denote the convex conjugate of Ly. Assume that Ly a convex, proper, lower semicontinuous function and R takes the form The problem (P is equivalent to
h v) min f(u) - min VER
|u|2 X Ly (X(u 0g u)) 1 (Aa)
(7)
WER"
2 1(v (() OER
max
_ og (x (xTa)ll
(8)
where v Og u _ (UgWg)gess The minimiser 3 to PA and the minimiser v to 7 are related by 3 = u Og u = -v² Og XTa a. Provided that u + h(v O v) is differentiable, the function f is differentiable with gradient
Vf(e)= = -ooh(c") (1x al)) where a E argmax - (ā)
1 ,1000(X' a)12 (9)
Note that f f is uniquely defined even if a is not unique. I > and Lg is differentiable, then we have the additional formula, with u E argming 1 + (X Og ú)),
+ ((ug) x (X Og u))) 9E9
(10)
Proof. The equivalence between Px) and 7 is simply due to the quadratic variational form of R. and the change of variable 19 = Mg. and Ug = /////Tg- The equivalence to follows by convex duality on the inner minimisation problem, that is
1 1ul + 1 " (0ll0gg1) og u))
f(v) = min G (v,
_ 2 h(v2) +
min 2 h(o²) マ |u|2 , where = == X(v u)
uiz
min max 2 h(v²)) +
_ lul2 2 + ス Lx(()) - -a, 2) + (a, X (v Oguu)
1
u,
2
1 |u|2 |u|
+ (a. X(v Og u]) - 1 - {)(())).
max min 2 h((09)
Using the optimality condition over u. we obtain u Gg x T a and hence.
[(e) = max G2 a))
- h(0²) 2
v Og xTa X I (Axr)
2
By [Rockafellar and Wets 2009 Theorem 10.58), if the following set
S(v) A {2, ai) = v - Og (Ixx) al2) \ a E argmin, G2(v,a)}
is singled valued, then f is differentiable with ()(v) = 0,G2((, a) for E argmin G2(U, a). Observe that even if argmin, G2(U, a) is not single valued, since G2 is strongly convex for v a, S(o) is single-valued and hence, f is differentiable function.
In the case where Ty is differentiable, we can again apply (Rockafellar and Wets 2009 Theorem 10.58), to obtain Vf(c) = v @ ōh(v²) + (,, v) with u = argmin, Gi u) (noting that G1 (v. ) is strongly convex and has unique minimiser) which is precisely the gradient formula (10)
For the Lasso and basis pursuit setting, the gradient of f can be computed in closed form:
Corollary 1. If R has a quadratic variational form and I,y(2) ž vIžz then 0Ly(2) y.
La) = (y, a) + 1 ||ox] 2/2 and the gradient of f can be written as and additionally (T)) when
X > O. Furthermore, a E Rm in (9) and u E I in (10) solves
(X diag(t")x + Ald)a = = and (diag(v)X X diag(v) + xldu= = (xTv), v). (II)
where T R= is defined as 0 uu (vgug)oEg for all E R" and ld denotes the identity matrix.
This shows that our method caters for the case = with the same algorithm in a seamless manner. This is unlike most existing approach which work well for >> 0 (and typically do not require matrix inversion) but fails when is small, whereas solvers dedicated for might require inverting a linear system, see Section 4.4 for an illustrative example.
5

---

3.1 Properties of the projected function f
In this section, we analyse the case of the group Lasso. The following theorem ensures that the projected function f has only strict saddle points or global minima. We say that v is second order stationary point if f(v) = and V f(t) ž We say that e strict saddle point (often called "ridable") if it is stationary point but not second order stationary point, One can thus always find direction of descent outside the set of global minimum. This can exploited to derive convergence guarantees to second order stationary points for trust region methods [Pascanu et al. [014] and gradient descent methods [Lee et al. 2017 Jin et al. [017].
Theorem 3. In the case h(z) = E, 2 and L(z, = 2 yl3 the projected f is infinitely continuously differentiable and for e E RR, ff(v) U and u solves the inner least squares problem for v. Let J denote the support v, by rearranging the columns and rows, the Hessian of f can be written as the following block diagonal matrix
(5(2) where En XX, (X(u@u) -))
v2u(w)= = (diag(1 1kg12) + AUTWU
0
(12)
diag(1 (1 - 15gl
+ (Td,) and U is the block diagonal matrix with blocks (Eg)ges, with maxges 1Eal2 & C and [V² < 1 30 where C - lyle maxgeg ||x //x. Moreover, all stationary points of f are either global minima or strict saddles. At stationary points, the eigenvalues of the Hessian of f are most 4 and is at least
where W A Id A ((V XT
min 4(1 1/1-1/(A+ d)), min(1 - -Ksl?))
8EJ
where ē is the smallest eigenvalue of (vg. Xn,hh)
The proof can be found in Appendix C We simply mention here that by examining the first order 0g that B is minimizer if and only if & satisfies -cg 1 for all g E (3) and 16g12 & 1 for all g E G. The first condition on the support of is always satisfied at stationary points of the nonconvex function (2). and by examining 122. the second condition is also satisfied unless the stationary point is strict.
condition of (PA).
Remark (Example of striet saddle point for our f). One can observe that v = 0 a strict saddle point, the solution to the associated linear system yields u 0 and hence V ff(v) 0. If A > |X yl then u = V = 0 corresponds to global minimum, otherwise, it is clear to see that there exists such that - 16, < 0 and v = 0 a strict saddle point.
Remark 2. Since f C it is Lipschitz smooth on any bounded domain. As mentioned, f is coercive when It is coercive, and hence, its sublevel sets are bounded. So. for any descent algorithm, we can apply results based on V*J being Lipschitz smooth for all
Remark The nondegeneracy condition that 1sgl22 outside the support of v and invertibility of (X Xx) ghhe is often used derive consistency results [Bach] 2008 Zhao and Yu 2006). By Proposition 1, we see that this condition guarantees that the Hessian of f positive definit at the minimum, and hence, combining with the smoothness properties of f explained in the previous remark, BFGS is guaranteed to converge superlinearly for starting points sufficiently close to the optimum Nocedal and Wright 2006 Theorem 6.6].
4 Numerical experiments
In this section, we use L-BFGS [yrd et al. 1995) to optimise our bilevel function f and we denote the resulting algorithm "Nonevx-Pro". Throughout, the inner problem is solved exactly using either full or a sparse Cholesky solver. One observation from our numerics below is that although Nonevx- Pro is not always the best performing, unlike other solvers, it is robust for example, our solver is mostly unaffected by the choice of while one can observe in Figures and 2 that this has a large impact on the proximal based methods and coordinate descent. Moreover, Noncvx-Pro is simple to code and rely on existing robust numerical routines (Cholesky/ conjugate gradient + BFGS) which naturally handle sparse/implicit operators, and we thus inherit their nice convergence properties. All numerics are conducted on 2.4 GHz Quad-Core Intel Core i5 processor with 16GB RAM. The code to reproduce the results of this article is available online"
wide range of settings:
https: tht.b com/ gpwgre/eeye21111 0

---

loukemia
(38,7129)
mnist (60000.687 (036683)
A
2
Max
Amax
50
Amax
Figure Lasso comparisons with different regularisation parameters.
4.1 Lasso
We first consider the Lasso problem where R(3) = Σi= |3:].
Datasets.
We tested on 8 datasets from the Libsvm repository These datasets are mean subtracted and normalised by m.
Solvers. We compare against the following 10 methods:
O-mem SRI: a proximal quasi newton method [Becker et al. 2019
FISTA w/ BB: FISTA with Barzilai- Barzilai-Borwein stepsize Barzilai and Borwein [988 and restarts
O0 O'donoghue and Candes 2015].
3. SPG/SpaRSA: spectral projected gradient (Wright al. 2009
CGIST: active set method with conjugate gradient iterative shrinkage/thresholdingg Goldstein
and Setzer 2010).
5. Interior point method: from Koh et al. [207]].
6. CELER: a coordinate descent method with support pruning [Massias et al. 2018
7. Non-cox-Alleevaating--ee alternating minimisation of and in G from
Hoff 2017
8. Non-cvx-LBFGS: Apply L-BFGS to minimise the function (u, v) + G(u, in 3).
9. L-BFGS-B Byrd et al 1995 apply L-BFGS-B under positivity constraints min,, E; 24
Σ, 1u 23 X(u v. This is the standard approach for L-BFGS to & minimisation and corresponds splitting 3 into its positive and negative parts.
10. :aadivaaiational:: Based
knowledge novel) approach is to apply L-BFGS-B to the bilevel formulation of (I) without nonconvex reparametrization. Indeed, by applying (I and using convex duality, the Lasso
idea of Nonevx-Pro, another natural (and
solved by minimizing (n) - max,.eR 1 Σ, ni la| 1 Σ, ni (I;, a) + (a, y). The gradient of g()) I a22 where 12 and we apply L-BFGS-B B with positivity constraints to minimise g.
pointwise sense and maximises the inner problem,
Experiments. The results shown in Figure (with further experiments in the appendix). We show comparisons at different regularisation strengths, with X, being the regularisation parameter found by 10 fold cross validation on the mean squared error, and Amax = ||X ylloo is the smallest parameter at which the Lasso solution is guaranteed to be trivial.
Group Lasso
The multi-task Lasso Gramfort et al. 2012 is the problem 7 where one minimises over 3 E Raxq the observed data y E [gmixy and R(B)) Σ
ビ= 1 la with 3 denotes the jth row of the matrix 3 and the loss function is - Sll X | in terms of the the Frobenius norm.
httpps:/wwwr csie. ntu. edu. htt.at/wwwwggg//////bt/t//////te

---

10 max
20 max
50
max
100 Amxx
Figure 2: Comparisons for multitask Lasso on MEG/EEG data
Datasets. We benchmark our proposed scheme on joint MEG/EEG data from Ndiaye et al. [2015] X denotes the forward operator with 22494 source locations, and is constructed from 301 MEG sensors and 59 EEG sensors, so that m = 360. The observations E Rmxx represent time series measurements m sensor with q 181 timepoints each. The 3 corresponds to the source locations which are assumed to remain constant across time.
Solvers. We perform a comparison against FISTA with restarts and BB step, the spectral projected gradient method SPG/SpaRSA, A, and CELER. Since n is much larger than and m, we use for NonCvx- Pro the saddle point formulation (8) where the maximisation over a E Rmxx,, Computation of a in (f(v) involves solving (Idm.
diag(v?) X y. that is, q linear systems each of size m.
Experiments. Figure displays the objective convergence plots against running time for different X: À = Amax/r r with Amax max; |X, yll2 for 10, 20, 50, 100. We observe substantial performance gains over the benchmarked methods: In MEG/EEG problems, the design matrix tends to exhibit high correlation of columns and proximal- -based algorithms tend to perform poorly here. Coordinate descent with pruning is known to perform well here when the regularisation parameter large Massias et al. 2018|, but its performance deteriorates À increases.
4.3 Trace norm
In multi-task feature learning (Argyriou et al. 2008 for each task f = 1,,.. ,, we aim to find fe R" R given training examples (Izz Ve.s) E. E for I,..., One approach to jointly solve these T regression problems by minimising (5) where R is the trace norm (also called "nuclear norm"), = T, y (yo)_= A(B) (X, with X, being the matrix with ith row Z₁,5 and B, being the hh column of the matrix B. Note that letting u, R" denote the 8th column of U, the computation of U in VS(V) involves solving T linear systems (AId, + V X,TxX,VV X,V)u, = VT x,T V/. Here, the trace norm encourages the tasks to share small number of linear features.
Datasets, We consider the three datasets commonly considered in previous works. The Schools dataser from Argyriou et al. (2008) consists of the scores of 15362 students from 139 schools. There therefore T = 139 tasks with 15362 E, my data points in total, and the goal is to map 27 student attributes to exam performance. The SARCOS dataser [6] [Zhang and Yang 2021 Zhang and Yeung 2012) has 7 tasks, each corresponding to learning the dynamics of a SARCOS anthropomorphic robot arms. There shared across all tasks. The Parkinsons dataser [asaas et al. 2009 which is made up of m = 5875 datapoints from T 42 patients. The goal is map n biomarkers Parkinson's disease symptom scores for each patient.
21 features and m 48, 933 data points, which
Solvers. Figure reports a comparison against FISTA with restarts and IRLS. The IRLS algorithm
for (5) is introduced in /Argyriou et al. [2008] (see also Bach et al. (2011)) and applies alternate
minimisation after adding the regularisation term eA tr )/2 to (4) The update of simple
least squares problem while the update for Z is Z + [BB + +Ild) F. Our nonconvex approach has
httpe://hone.tiii.cceaaaaarar// ics
http://wwww.guussiaapooooo org/ hpmm/dmtaaaaaaaaaa

---

1
Schools
Parkinsons
SARCOS
Figure 3: Comparisons for multi-task feature learning, IRLS-d corresponds to IRLS with 10-d.
the same per-iteration complexity IRLS, but one advantage is that we directly deal with 5 without any regularisation.
Remark -aad-variational mentioned in Section 4.1 does not extend to the trace norm case, since the function would be minimised over S4, for which the application of L-BFGS-B is unclear. For this reason, bilevel formulations for the trace norm Pong al. 2010 have been restricted the use of first order methods.
Experiments. For each dataset, we compute the regularisation parameter X. by 10-fold cross- validation on the RMSE averaged across 10 random splits. Then, with this regularisation parameter, we compare Non-convex-pro FISTA and IRLS with different choices of E. The convergence plots are show in 3 We observe substantial computational gains for the Schools and Parkinson's 's dataset. For the SARCOS dataset, IRLS performed the best, and even though Nonconvex-po is comparatively less effective here, although we remark that the number of tasks much smaller (7 = and the recorded times are much shorter (less than 0.2s). Further numerical illustrations with synthetic data are shown the appendix our method is typically less sensitive to problem variations.
4.4 Constraint Group Lasso and Optimal Transport
A salient feature of our method is that it can handle arbitrary small regularization parameter À and can even cope with the constrained formulation, when O, which cannot be tackled by most state of the art Lasso solvers. To illustrate this, consider the computation of an Optimal Transport (OT) map, which has recently gained a lot of attention ML [Peyré et al.) 2019]. We focus on the Monge problem, where the ground cost is the geodesic distance either graph surface (which extends original Monge's ' problem where the cost is the Euclidean distance). This type OT problems has been used for instance to analyze and process brain signals in M/EEG [Gramfort al. 2015)] for application in computer graphics (Solomon et al.] 2014] and now being applied to genomic datasets (Schiebinger et al. 2019). As explained for instance in (Santambrogio, 2015 Sec.4.2), the optimal transport between two probability measures a and on a surface can be computed by advecting the mass along vector field v(x) R (tangent to the surface) with minimum vectorial _ norm f [[[x)]]d (where da is the surface area measure) subject to the conservation of mass div(u)
b. Once discretized Lasso problem (Po) where 3, E I& is a discretization of v(2,) at some vertex 2g of the mesh, X is finite element discretization of the divergence using finite elements and y c-b. b. The same applies on graph, in which case the vector field is aligned with the edge of the graph and the divergence the discrete divergence associated the graph adjacency matrix, see Peyré al. [2019] This formulation is often called "Beckmann problem".
3-D mesh, this boils down solving a constrained group
Datasets. We consider two experiments: (i) following Gramfort et al. [2015] on a 3-D mesh of
the brain with 20000 vertices with localized Gaussian-lin distributions a and b (in blue and red), (ii) 5-nearest neighbors graph in 7-dimensional space of gene expression (corresponding to different time steps) of baker's yeast, which the dataset from DeRisi et al. 1997]. The n 614 nodes correspond to the most active genes (maximum variance across time) and this results in graph with 1927 edges. The distributions are synthetic data, where a a localized source whereas is more delocalized.

---

Figure 4: Resolution of Beekmann problem on graph (left) and 3-D mesh (right). The probability distributions and b are displayed in blue and red and the optimal flow 3 is represented as green segments (on the edge of the graph and on the faces of the mesh). The convergence curves display the decay of lo - 3 (1) during the iterations of the algorithms (DR=Douglas Rachhadd PD=Primal-Duss
function of time t second.
Solvers. We test method against two popular first order schemes: the Douglas- Rachford
Douglas-Rachford (DR)
algorithm [Lions and Mercier 1979 Combettes and Pesquet 2007] (DR) and the primal-dual scheme of Chambolle and Pock [201]] DR used in its dual formulate ation (the Alterntting Direction Method of Multipliers - ADMM) but on a re-parameterized problem in Solomon et al. (2014). The details of
these algorithms given in Appendix E
Experiments. Figure 4 shows the solution of this Beckmann problem in these two settings. While DR has the same complexity per iteration as the computation of the gradient of (resolution of linear system), a chief advantage of PD is that it only involves the application of X and X et each iterations. Both DR and PD have stepping size parameters (denoted ş and o)) which have been tuned manually (the rightmost figure shows two other sub-optimal choices of parameters). In contrast, our algorithm has no parameter to tune and is faster than both DR and PD on these two problems.
Conclusion
Most existing approaches to sparse regularisation involve careful smoothing of the nonsmooth term, either by proximal operators or explicit regularisation as in IRLS. We propose a different direction: simple reparameterization leads smooth optimisation problem, and allows for the use of standard numerical tools, such as BFGS. Our numerical results demonstrate that this approach is versatile, effective and can handle wide range of problems.
We end by making some remarks on possible future research directions. The application of our method to other loss functions requires the use of an inexact solver for the inner problems, and controlling the impact of its approximation an interesting avenue for future work. Furthermore, is possible that one obtain further acceleration by combining with screening rules active set techniques.
Acknowledgments
The work of G. Peyré supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' avenir" program, reference 0001 (PRAIRIE 3IA Insti- tute) and by the European Research Council (ERC project NORIA).
References
A. Argyriou, T. Evgeniou, and M. Pontil. Convex multi-task feature learning. Machine learning, 73 (3):243-272, 2008
F. Bach, R. Jenatton, J. Mairal, and G. Obozinski. Optimization with sparsity-inducing penalties. arXiv preprint arXiv: 000.8.07..0000 2011.
R. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9(6), 2008
10

---

J. Barzilai and J. M. Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141-148, 1988.
A. Beck and M. Teboulle. A fast iterative shrinkage-thresholdingg algorithm for linear inverse problems. SIAM journal on imaging sciences, (()::183-202 2009.
S. Becker, J. Fadili, and P. Ochs. On quasi-newton forward-backwer splitring: Proximal calculus and convergence. SIAM Journal Optimization, 29(4):2445-2481) 2019.
D. P. Bertsekas. Nonlinear programming. Journal of the Operational Research Sociery, 48(3): 334-334, 1997.
M. J. Black and A. Rangarajan. the unification line processes, outlier rejection, and robust statisties with applications in early vision. International journal of computer vision, 19(1):57-91, 1996.
S. Boyd, N. Parikh, and E. Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 1665):1100-1208 1995.
A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1): 145, 2011.
P. L. Combettes and J.-C. Pesquet. A douglas-rachforr splitting approach to nonsmooth convex variational signal recovery. IEEE Journal of Selected Topics Signal Processing, 1(4):564-574, 2007.
L. Combettes and B. C. Vū. Variable metric forward-backward splitting with applications to monotone inclusions in duality. Optimization, 63(9): 2014.
I. Daubechies, M. Defrise, and C. De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute Mathematical Sciences, 57(11):1413-14 2004.
1. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntürk. Iteratively reweighted least squares minimization for sparse recovery. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 1-11:1138,, 2010.
J. L. DeRisi, V. R. Iyer, and P. O. Brown. Exploring the metabolic and genetic control of gene expression on a genomic scale. Science, 278(5338)6680-686, 1997.
J. Douglas and H. H. Rachford. On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American mathematical Society, 82(2):421-439, 1956.
J. Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.
D. Geiger and A. Yuille. A common framework for image segmentation. International Journal of Computer Vision, 6(3):227-243, 1991.
D. Geman and G. Reynolds. Constrained restoration and the recovery of discontinuities. IEEE Transactions on pattern analysis and machine intelligence, 14(3):367333,, 1992.
L. F. Ghaoui, V. Viallon, and T. Rabbani. Safe feature elimination for the lasso and sparse supervised learning problems. arXiv preprint 1009.42/0 2010.
Goldstein and S. Setzer. High-order methods for basis pursuit. UCLA CAM Report, pages 10-41, 2010.
G. Golub and V. Pereyra. Separable nonlinear least squares: the variable projection method and its applications. Inverse problems, 19(2):R1, 2003.

---

A. Gramfort, M. Kowalski, and M. Hämäläinen. Mixed-norm estimates for the m/eeg inverse problem using accelerated gradient methods. Physies in Medicine & Biology. 57(7):1937, 2012.
A. Gramfort, G. Peyré, and M. Cuturi. Fast optimal transport averaging of neuroimaging data. In International Conference on Information Processing in Medical Imaging, pages 261-272, Springer, 2015.
T. Hastie, R. Mazumder, J. D. Lee, and Zadch. Matrix completion and low-rank svd via fast alternating least squares. The Journal of Machine Learning Research, 16(1):3367-3422, 2015.
P. D. Hoff. Lasso, fractional norm and structured sparse estimation using hadamard product parametrization. Computaaionnll Statistics & Data Analysis, 115:186-198, 2017.
H. Hong, C. Zach, and A. Fitzgibbon. Revisiting the variable projection method for separable nonlinear least squares problems. In 2017 IEEÉ Conference on Computer Vision and Pattern Recognition (CVPR), pages 5939-5947 IEEE, 2017.
C. Jin, R. Ge. Netrapalli, S. M. Kakade, and M. I. Jordan. How escape saddle points efficiently. In International Conference on Machine Learning, pages 1724 1732. PMLR, 2017.
K. Koh, S.-J. Kim, and S. Boyd. An interior- interior-point method for large-scale 11 I1-regularized logistic regression. Journal of Machine learning research, 159- 2007.
J. D. Lee, Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht. First-order methods almost always avoid saddle points. arXiv preprint
2017.
P.-L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964-979, 1979.
M. Mardani and G. B. Giannakis. Estimating traffic and anomaly maps via network tomography. IEEE/ACM transactions on networking, 1533-155344 2015.
M. Massias, A. Gramfort, and J. Salmon. Celer: a fast solver for the lasso with dual extrapolation. In International Conference Machine Learning, pages 3315-3324. PMLR, 2018
C. A. Micchelli, J. M. Morales, and M. Pontil. Regularizers for structured sparsity. Advances in Computational Mathematics, 38(3):455-489, 2013.
E. Ndiaye, O. Fercoq, A. Gramfort, and J. Salmon. Gap safe screening rules for sparse multi-task and multi-class models. arXiv preprint arXiv: 2015.
E. Ndiaye, O. Fercoq, A. Gramfort, and J. Salmon. Gap safe screening rules for sparsity enforeing penalties. The Journal of Machine Learning Research, 18(1):4671-4003 2017.
J. Nocedal and S. Wright. Numerical optimization. Springer Science & Business Media, 2006.
B. O' d'donoghue and E. Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 15(3):715-732, 2015.
R. Pascanu, Y. N. Dauphin, S. Ganguli, and Y. Bengio. On the saddle point problem for non-convex optimization. arXiv preprint arXiv: 1005.4604, 2014.
G. Peyré, M. Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355-677, 2019.
T. K. Pong. P. Tseng, S. Ji, and J. Ye. Trace norm regularization: Reformulations, algorithms, and multi-task learning. SIAM Journal on Optimization, 20(6):3465-348) 2010.
A. Rakotomamonjy, F. Bach, Canu, and Y. Grandvalet. Simplemkl. Journal of Machine Learning Research, 9:2491-2521, 2008.
J. D. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning, pages 713-719, 2005.
R. Rockafellar and R. J.BB. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
12

---

A. Ruhe and P. Á. Wedin, Algorithms for separable nonlinear least squares problems. SIAM review, 22(3):318-337, 1980.
Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94, 2015.
G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V. Subramanian, A. Solomon, J. Gould, S. Liu, S. Lin, P. Berube, al. traimol-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4):928 993,,993,3000 2019.
Solomon, R. Rustamov, L.. Guibas, and A. Butscher. Earth mover's distances on discrete surfaces.
ACM Transactions on Graphics (TOG), 33(4):1-12, 2014.
A. Tsanas, M. Little, McSharry, and L. Ramig. Accurate telemonitoring of parkinson's 's disease progression by non non-invasive speech tests. Nature Precedings, pages 1-1, 2009.
T. van Leeuwen and A. Aravkin. Non-smooth variable projection. arXiv preprint arXiv: 160.00011, 2016.
S. J. Wright, R. D. Nowak, and M. A. Figueiredo. Sparse reconstruction by separable approximation. IEEE Transactions signal processing, 57(7):2479-249) 2009.
C. Zach and G. Bourmaud. Descending, lifting smoothing: Secrets of robust optimization. In Proceedings of the European Conference on Computer Vision (ECCV), pages 547-562, 2018.
Y. Zhang and Q Yang. A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering. 2021.
Zhang and D.-Y. Yeung. A convex formulation for learning task relationships multi-task learning. arXiv preprint arXiv: 1203.353,, 2012.
P. Zhao and B. Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 12241-25633 2006.
13


Reviews:
[{"review_id": "RY28rVM6R9Y", "reviewer": "Reviewer_Nz5H", "summary": "The authors propose a bilevel optimization approach for solving regularized empirical risk minimization. The considered minimization problem ($\\cal{P}_{\\lambda}$) refers to a linear model with parameters $\\beta$ that are regularized in terms of a sparsity enforcing term $R(\\beta)$. More specifically, the authors treat regularizers $R$ that can be recast in a so-called quadratic variational form. Therewith, a reparametrization of the original problem can be regarded as a bilevel program with smooth inner problem. Subsequent to the introduction, the authors provide a characterization of regularizers that have a quadratic variational form, followed by a theoretical analysis and numerical experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of my knowledge, the described approach to reformulate and reparametrize the regularized objective is novel. Also, I find the presented idea interesting because the smoothed objective allows for applying efficient algorithms like L-BFGS. Indeed, the reported numerical results indicate that the method is competitive and especially robust with respect to the choice of the regularization parameter. As far as I can see, the manuscript is technically correct. And finally, the authors provide extensive supplementary material.\n\nOn the other hand, I think that the scope of the paper is limited to linear models and a few specific (although common) regularizers, and there exist a variety of solvers that can handle these kind of problems. Therefore, although I think that this is basically a good paper, I am not sure whether it will gain high significance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MNFxUcnFPmX", "reviewer": "Reviewer_j7tM", "summary": "This paper proposes a reparametrization of common objective functions in the sparse estimation literature (for linear models). This allows rewriting LASSO, group LASSO, low-rank estimation as a smooth bilevel problem, and then applying fast methods for smooth problems such as L-BFGS. Critically, the gradient to the outer problem has a simple form to compute. The smooth problem is shown to have no spurious saddles, although it is nonconvex. The paper then shows impressive empirical results on multiple problems of interest stemming from this simple reparametrization.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and clear. It showcases impressive speedups thanks to the proposed reparametrization for a variety of problems. It takes an unusual route, by examining how a non-smooth convex problem can be written as a smooth, non-convex problem without spurious saddles.  \n\nThe proposed method shows strong results, in particular ones which are robust across different problems. The proposed reparametrization is elegant and seems efficient. It is directly applicable to sparse linear models which are very much used in practice. It is easy to implement, since it relies on readily available smooth optimizers + linear solvers. The method would also directly benefit from improvement in these types of solvers. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "LoGQLRTYpBr", "reviewer": "Reviewer_tRPK", "summary": "The authors study regularized regression with a sparsity inducing constraint. (In the appendix also the extension to the low-rankness inducing case is considered.) The authors propose a new non-convex formulation, which is optimized via BFGS. The non-convex formulation is motivated by the well-known IRLS (Iteratively Reweighted Least Squares) algorithm.\nExtensive numerical simulations are conducted on a wide variety of problems and the proposed algorithm is compared with a number of state-of-the-art approaches. While the proposed algorithm does not always perform best, it is in all cases at least competitive to the best performing approach.\nMoreover, the authors prove that the induced non-convex function, which is optimized in their approach, is ridable -- meaning that all local minima are global minima and the Hessians of all saddle points have at least one negative eigenvalue. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is well-written and easy to read (although there are some typos, see below). The authors propose a new algorithm and demonstrate in experiments its versatility for a diverse set of problems. I clearly see the strengths of the paper on the empirical side. As the algorithm is new and appears to work well compared to a large class of existing algorithms on a wide set of problems (as it has been examined thoroughly in the paper), I would recommend acceptance.\n\nI feel that the results on the theoretical side are a bit weaker. The authors cite Lee et al., which guarantees convergence from almost every starting point. However, it is known this convergence guarantee does not give any rates. (In particular, the convergence might take exponentially long in the accuracy.) Hence, it is not so clear what the impact is of the theoretical results I feel that this should be pointed out by the authors.\nOf course, it might be interesting to have some bounds on the computational complexity of the presented algorithm (or on the convergence rate), but I feel that it might be difficult to derive those (especially in the very general setting as presented in this paper). Can one derive such bounds in the setting where for example $R (\\beta) = \\Vert \\beta \\Vert_{\\ell_1} $? It could be interesting if the authors could comment on these issues in their paper.\n\nQuestions:\n-In l. 238 the authors define Non-cvx-LBFGS. How is this algorithm different to Noncvx-Pro. Is it not exactly the same? What am I missing?\n-The authors motivate their algorithm by IRLS. It is known that IRLS works especially well in the non-convex case, i.e. one consider the $\\Vert \\cdot \\Vert_{\\ell_p} $-norm with $p<1$. Have the authors compared their algorithm to the non-convex IRLS formulation?\n\nNitpicks:\n- l. 11: minima->minimum\n-l. 66 detail->detailed\n-l. 180 approach(es)\n-l. 185 global minimums->minima", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "60bv9QAEPCX", "reviewer": "Reviewer_eSTH", "summary": "Authors proposed a re-parametrization of the variational form of usually sparsity enforcing penalties (including the Lasso and its variations).\nThe proposed variational re-parametrization leads to a non-convex but smooth bilevel optimization problem, that authors propose to solve using usual L-BFGS.\nIn addition to an extensive benchmark, authors show that the potential saddle points of the new minimized function are not \"pathological\".", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea seems significantly new to me. Experiments are extensive and this work appears as a solid  and promising tool for the field of composite optimization. The general idea is very clear, however the paper could explain more the implementation details, in particular the bilevel approach.\n\n- l21, the types of problems consider does not seem to include the (dual of the) SVM, is it possible to extend your work to also solve it?\n- l80 you mentioned support pruning techniques, and works relying on working sets. Could your approach be combined with such techniques in order to gain speedups? This could be especially useful since the bilevel proposed approach, which requires solving a $\\min(m,n)$ linear system.\n- l220 You mention the conjugate gradient algorithm. Do you solve the linear system exactly? If not at which tolerance do you solve it? Do you use warm start on it? Does the algorithm explode in time in $n$ and $m$ are too large?\nHow \"robust\" is it to approximation? Because it is known that L-BFGS with approximate gradients can fail.\n- l238 Non-cvx L-BFGS approach, what do you mean exactly by \"solving (2) by L-BFGS\", you consider the problem as a function of 2 variables $u$ and $v$ and apply L-BFGS on it? Could authors clarify?\n- l240 it is written $\\min_{u, v} ... ||X(u - v) - y||^2$, do you mean $\\min_{u, v} ... ||X(u \\odot v) - y||^2$ ?\n- in order for the paper to be more pedagogical and instantly implementable by practitioners, I would recommend to detail the proposed algorithms on the Lasso in appendix, at least the computation of the gradient.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers found the reformulation interesting and appreciated the thorough experimental comparison. Remaining concerns include the (heavy) restriction to the least-square loss and the limited theoretical convergence guarantee. The authors' response acknowledged these issues and explained possible alleviations/extensions. Overall, there seems to be enough merit in the authors' approach and hopefully it could be further extended in the future. 

Please incorporate the review, response and promised changes in the final revision. I would also suggest the authors refrain from using the term "bi-level programming," since the main theorem is simply a dualization of the loss, resulting in a standard min-max problem. 
Decision: Accept (Poster)