Path following algorithms for $\ell_2$-regularized $M$-estimation with approximation guarantee
Authors: Yunzhang Zhu
Renxiong Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: regularization
optimization
tuning parameter selection
TL;DR: We propose a novel grid point selection scheme and an adaptive stopping criterion for $\ell_2$ penalized $M$-estimation problem using any optimization algorithm that produces an approximated solution path with approximation error guarantee.

Abstract: Many modern machine learning algorithms are formulated as regularized M-estimation problems, in which a regularization (tuning) parameter controls a trade-off between model fit to the training data and model complexity. To select the ``best'' tuning parameter value that achieves a good trade-off, an approximated solution path needs to be computed. In practice, this is often done through selecting a grid of tuning parameter values and solving the regularized problem at the selected grid points. However, given any desired level of accuracy, it is often not clear how to choose the grid points and also how accurately one should solve the regularized problems at the selected gird points, both of which can greatly impact the overall amount of computation. In the context of  $\ell_2$-regularized $M$-estimation problem, we propose a novel grid point selection scheme and an adaptive stopping criterion for any given optimization algorithm that produces an approximated solution path with approximation error guarantee. Theoretically, we prove that the proposed solution path can approximate the exact solution path to arbitrary level of accuracy, while saving the overall computation as much as possible. Numerical results also corroborate with our theoretical analysis.

Path following algorithms for lz-regularized M-estimation with approximation guarantee
Yunzhang Zhu Department of Statistics Ohio State University Columbus, OH 43015 zhu 219.2190ss.. edu
Renxiong Liu"
Statistics and Data Science team
Nokia Bell Labs
Murray Hill, NJ 07974
renxiong biulnnoaelllttkkeaeeeeeellll -lass. com
Abstract
Many modern machine learning algorithms are formulated regularized M- estimation problems, in which a regularization (tuning) parameter controls trade- off between model the training data and model complexity. To select the "best" tuning parameter value that achieves good trade-off, an approximated solution path needs to computed.
practice, this is often done through selecting a grid of tuning parameter values and solving the regularized problem at the selected grid points. However, given any desired level of accuracy. is often not clear how to choose the grid points and also how accurately one should solve the regularized problems at the selected gird points, both which can greatly impact the overall amount of computation. In the context of eg-regularized M-estimation problem, we propose a novel grid point selection scheme and an adaptive stopping criterion for any given optimization algorithm that produces approximated solution path with approximation error guarantee. Theoretically. we prove that the proposed solution path approximate the exact solution path arbitrary level of accuracy, while saving the overall computation as much as possible. Numerical results also corroborate theoretical analysis.
Introduction
Modern machine learning algorithms are often formulated as regularized M-minimization problems,
0(A) arg min L,, (0) Ap(O),
(I)
where (t) denotes an empirical loss function, p(f) denotes regularization function, and À is tuning parameter that controls the trade-off between model fit and model complexity. Varying the tuning parameter leads collection of models, among which one of them may chosen as final model. This requires solving a collection of related optimization problems, whose solutions are often referred as the solution path (We refer readers Figure $4 and S5 in the supplementary material for some examples of solution paths).
Very often the exact solution path 0()) can not be computed, and path-following algorithms are usually used to obtain a sequence of solutions at some selected grid points to produce an approximated solution path. Existing path-following algorithms [see, e.g., Hastie et al., 2004, 2007] typically choose set of equally-spacee grid points (often on log-scale), and choose certain algorithm to solve the minimization problem the selected grid points. Warm-start strategy is often used leverage the fact that the minimizers at two consecutive grid points may be close. However, there is paucity of literature on how to choose these grid points and how accurately one should solve the optimization
Work done when Renxiong Liu is PhD student the Ohio State University.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

problem at the selected grid points, both of which would influence the overall computational cost and approximation accuracy.
In the context of l2 fz-regularized M-estimation where p(0) = (1/2)1013- we propose a novel grid point selection scheme and an associated stopping criterion each grid point for any optimization method. The proposal is motivated by first proving that the approximation error of a solution path is governed by two important quantities, one depending on how finely the grid points are spaced and the other depending on how accurately one solves the regularized problem at the selected grid points. We refer these two quantities as interpolation error and optimization error. Given any optimization algorithm (that solves a single regularized problem), a stopping criterion can be constructed so that the optimization error is comparable the interpolation error, which ensures that there is no wasteful computation at each selected grid point. Then a novel grid point selection scheme is constructed to balance the approximation errors over the entire solution path.
Theoretically, we first show that the approximation error of the proposed solution path can be upper bounded by the sum of the interpolation error and the optimization error. Given any optimization algorithm, we show that the proposed stopping criterion ensures that the optimization error is dominated by the interpolation error (see Theorem 1). We then establish a global approximation-erro bound for the solution path (see Theorem 2). Optimizing this global approximation-erron bound by using the proposed grid point selection scheme, we also prove that the proposed solution path can approximate the exact solution path to an arbitrary level of accuracy (see Theorem 3). Finally, we establish that the total number of grid points required for the proposed algorithm achieve an e-suboptimality is most Oe 1/2) (see Theorem 4).
Path-following techniques have been used in many optimization algorithms. For instance, it is used in the interior point methods, which is one of most popular algorithm to solve general convex optimization problems [see, e.g., Chapter 1.3 of Nesterov and Nemirovskii, 1993]. However, the focus is often the limit of the path rather than the entire solution path. In statistics/machine learning literature, Osborne [1992] and Osborne et al. [2000] applied the homotopy techniques to obtain piecewise linear solution paths for quantile regression and LASSO, respectively. Later Efron et al. [2004], Hastie et al. [2004], and Rosset and Zhu [2007] used similar ideas to derive the solution path for a family of regularized M-estimation problems. Subsequent developments include Friedman et al. [2007]. Hoetling [2010]. Arnold and Tibshirani [2016], among many others. Path following algorithms for more general types of f-rreuuarlization are also available. For example, Tibshirani and Taylor [] used dual path algorithm to compute the solution path of generalized LASSO problem. In the context of order weight E model, Bao et al. [2019] proposed an efficient approximate solution path algorithm by using primal-dual method. These works often leverage the piecewise linearity of the solution path so that an exact path- following algorithm can be explicitly derived. For situations where the solution paths are not piecewise linear, a path-following algorithm based on Newton method was considered in Rosset [2004]. However, Rosset [2004] used a simple grid point selection scheme and only established pointwise closeness to the solution path. Subsequent research on situations where the solution paths are not piecewise linear includes the work of Garrigues and Ghaoui [2008], which introduced a homotopy algorithm tailored for solving the LASSO problem using online (sequential) observations, and the work of Qu et al. [2022], which approximates the piecewise smooth path in self-paced learning for generalized self-paced regularizer.
To the best of our knowledge, there is paucity of research on the impact of grid points selection and how to set stopping criterion to save computation. One line of related works use a piecewise constant interpolation scheme to approximate the solution path to an arbitrary level of accuracy [see, e.g.. Giesen et al., 2010, 2012, 2014, Ndiaye et al., 2019]. Most relevant to our work here are the works of Giesen et al. [2012] and Ndiaye al. [2019]. Giesen et al. [2012] proposed a generic algorithm to compute a piecewise constant approximate solution path for a family of optimization problems parameterized concavely² in a single hyperparameter. They showed that the number of grid points needed to achieve suboptimality is at most O(1/Ve) However, their proposed method relies on the existence of a moblemmddepedden oracle, which for any chosen hyperparameter produces both an e-approximate solution at that hyperparameter and concave polynomial that is used to compute the step size. Except for special examples like standard SVM, it not clear how to implement the oracle for general problems.
'It requires that the object function is concave with respect to the hyperparameter for any fixed value of parameters. This includes most regularized machine learning problems special cases.
2

---

In view of these limitations, Ndiaye et al. [2019] considered regularized convex optimization problems and proposed general strategies to choose grid points based on primal-dual methods. Again, piecewise constant path is constructed to approximate the solution path. However, their approach can only be applied to special class of loss functions that are composition of "simple" function (whose conjugate can be analytically derived) and affine functions. Moreover, the choice of the grid points depends on some convexity and smoothness parameters associated with the loss, which either are not available except for some special class of functions or require careful tuning due to their great impact on grid points selection. Ndiaye et al. [2019] also showed that to achieve e suboptimality, the number of grid points required is (11/ Vc) for uniformly convex loss of order d [Bauschke et al., 201 I] and O(1vvl (V) for generalized self-concordant functions [Sun and Tran-Dinh, 2017]. In our paper, we show that the number of grid points needed is (1/ VE) for general differentiable convex loss (see Theorem 4). Compared to Ndiaye et al. [2019]. we also demonstrate through simulations that our method produces better approximated solution paths under a fixed computational budget (see Section 4). Moreover, our method can also be applicable to loss functions that are possibly nonconvex (see Section 3).
We also note that Proposition 38 of Ndiaye [2018] shows that under some regularity conditions e- suboptimality along the entire solution path can be achieved by using piecewise linear interploation. However, it not clear how these conditions can be used to construct an algorithm with approximation guarantee. Our proposed algorithm, on the other hand, provides an easily implementable grid point selection scheme and an associated stopping criterion at each grid point, which together ensures that c-suboptimality can be attained through a piecewise linear interploation.
More recently, in the context of fg-regularized convex optimization problems, Zhu and Liu [2021] proposed two path-following algorithms by using Newton method and gradient descent method the basis algorithm seperately. and discuss the grid point selection scheme for each algorithm based on the piecewise linear interpolation. Our paper differs from Zhu and Liu [2021] in twofold. First, the grid-point selection scheme in Zhu and Liu [2021] depends on the basis algorithm. By contrast, in our paper any basis algorithm can be applied at any chosen grid point as long as the stopping criterion is satisfied by the basis algorithm. Next, the path-following algorithms by Zhu and Liu [2021] ] can only be applied to convex optimization problems, while in this article we also consider loss functions that are possibly nonconvex (see Section 3).
The rest of the paper organized as follows. Section 2 introduces the proposed path following algorithm and establish its global approximation-erro bound. Section 3 considers an extension to nonconvex empirical loss. In Section 4, we compare the the proposed scheme to standard path-following scheme through simulated study using ridge regression and ée-reuulrrized logistic regression. We close the article with some remarks Section 5. All proofs are included in the supplementary material.
2 Path following algorithms
We consider an fz-regularized M-estimation problem. More specifically, denote by L,, (0) some empirical loss function, where 0 E IR? denotes a parameter vector. We consider the solution path of an ée-reullarieed M-estimation problem:
((t) = arg min BERP
L))
(2)
Note that as the tuning parameter 1 varies from 0 to oo, the solution 0(L) varies from 0 to a minimizer of L.). We also remark that the choice of et 11 is not essential. In fact, can be replaced by any function C(t) that is strictly increasing and differenniable function, with C(O) 0 and lim;-+oc C(t) = oo. The solution path produced should be independent of C(t). Moreover, we can show that the E norm of the solutions is increasing function of f, and the solution O(t) converges to the minimum & norm minimizer of L,, (f) (if it is finite) as t goes to infinity (see Corollary S1 in the supplementary material).
Suppose that the goal is to approximate the solution path ((1) over a given interval [0, bmxx) for some lmax E (0, ox]. where we allow 4max co. Given set of grid points 0 < 41 <... < iN < co, and approximated solutions (0x ) at these grid points, we construct an approximated solution path over [0, maax through linear interpolation. More specifically, we define piecewise linear solution
3

---

path B(t) as follows
((t) = 1x t/ 1x11
Au-1-f
Og + t-tx 0x+1
for any t E [tx, tx+11, = O, - 1, for any ty < <t S max if ty < fmax
(3)
((t) = NN
where to = and O.- = O. This defines an approximated solution path Ø(1) for any L E [0, (max] which interpolates the approximated solutions at the selected grid points. In view of this definition, may also assume that N1 I mmax. because we do not need (tt over t E [IN-1, [N] if 11 > 6max-
To assess how well (tt approximates ((t). we use the function- value suboptimality of the solution paths defined by supo (())))(()
where fo(0) (1 -e LL) (0) + e [
is a scaled version of the objective function in (2). In what follows, we call supoststmas (ft( f((((t)) the global approximation error of ((t), and stpte (f((O(t)) f((((t))) the local approximation error of (() over [tx. [x+1].
Intuitively, how well (() approximates ((t) depends on how finely spaced the grid points are and the quality of the solutions at the selected grid points (i.e., 0g's 's). Our first main result relates the local approximation error of 0 over [L,, [x+1] to the choice the grid points and the accuracy of the
approximated solutions at the selected grid points measured by the size of the gradients ||V (0x) ||2.
where we assume that L, (0) is differentiable.
Theorem 1. Assume that L, (0) is a differentiable convex function. Let 9k == fi. = (1 e e"x) Ln (0x) + e e-xx6y kyy denote the scaled gradient at 0z. For any 0 < t < t2 < .... < tN < 0o,
we have that
e e )1
(f((((t)) f((0(1)) S max (e" (c11119112.
1
VL, (0) 12. (4)
sup rE(0.Al]
( tuts 2
( -
(F(((()) s,(0(t))) S E max
11 11. 11ttt113
sup (e(1)
{ etk+ || el* 110
+ (c-te - c 2
(5)
((1 (1-e tx) (1 eu1)2
for any = II...., N If we further assume that [10((ma)]l22 < oo, then we have that
sup ty tmax
( -((((())))) S 2(1 - tw 1 2(etN - 1) [10((maxx) 112
e¹N
1
(6)
when iN < Imax-
The proof of Theorem starts with relating the local approximation error to the suboptimality of 0x and 0x+1 at some t E [t,, 11. The suboptimality can then further bounded by the square norm of the grandient leveraging the fact that the objective function is '-strongly convex. Finally, a triangular inequality is used to bound the norm of the grandient by quantities that depend on 119k ll2 and |
We can see from Theorem 1 that the upper bounds for the local approximation error in (4)-(6) consist of two terms, with the first one (depending on gu) being algorithm dependent and the other term stemming from interpolation. We call them optimization error and interpolation error, respectively. Note that the optimization error is roughly of order exx |g which again depends on how accurate the solutions 0₂ are at the selected grid points. And the interpolation error is essentially independent of the quality of the solutions 0% ss as the interpolation error only depends on the spacing of the grid points and the norm of the solutions along the solution path (typically | ll = (t)))) c.f., Lemma S2 in the supplementary material). In other words, the interpolation error irreducible once the grid points are chosen, while the optimization error does depend on the algorithm and it can be pushed to be arbitrarily small if we run the algorithm long enough at each grid point. In this sense, if the goal is to minimize the local approximation error, then both the grid points and optimization algorithm should be designed carefully to strike a balance between these two errors to minimize the overall computations. For instance, it would be wasteful to have the optimization error smaller than the interpolation error, because the additional computation would not improve the overall approximation error (at least in order).

---

Motivated by this observation and the local approximation enror bounds in Theorem 1, we propose novel stopping criterion scheme at the selected grid points for any general optimization algorithm. In particular, for any given algorithm that takes an initializer and solves the problem at grid point 11++1 we can run the algorithm initialized 0g until the optimization error smaller than the interpolation emror for 0g 1, that is
( (1-
E 1 2 fe (0+)l.. (V
e fkl1 max
- -
optimization
e² 18+ 11 e 110 (1-e-t))a² - (1-E-1++) (
S -
max
(7)
interpolation error
where the LHS is the optimization error and the RHS the interpolation error in the bounds in Theorem 1. This condition can be further simplified, under which the upper bounds in Theorem can also be further simplified and combined that we can bound the global approximation error of ((t).
This is established in the following theorem.
Theorem 2. Assume that Tep (0) differentiable and convex. Suppose that 2- ax+1 S 20% Okk S Ommx for some max & In(2), and
(c - (eta - 1) |10x122: 1 15 k S
V. (0x) S So
(8)
for some Co S 1/4. Denote
A = 4(1 + C0 (m + 0mase +1)?),
B= (e 1) 1) I, (0)12
1k 10x11 ac 1)2
1 e max(ax. fmma (x)
C max I
D
max {110 (10 113)
e )2
Then
sup O5t5
{fi(O(t) f < Am.x(B,C,D)
(9)
when IN < tmax and [10 (et(max))l lll 00, and
sup
( s Amax(B,Cy
(10)
OCt11mus Tmax
when -1 S tmax iN for some N 2 1.
The above result provides a practical approach to verify whether the optimization error is dominated by the interpolation error by checking (8). In other words, (8) is sufficient condition for (7) and it can be used as a stopping criterion at each grid point t for any algorithm that computes a solution at f.- We also remark that, using the above bounds, similar approximation-ermo bounds for (lŌ(t) - 0())l2 be derived well (see Corollary $2 in the supplementary material).
Another important implication of Theorem 2 that the established global approximation-ern bound provides a principled approach to choose the grid points so that for any 0 and fmax (0, oo] we have
sup
(i(((()) f.(O(())) Se
(11)
for the solution path generated by algorithm, and at the same time it tries to maximize the speed at which the algorithm explores the solution path from 0 to fmax- In particular, to ensure (11), we propose to use the following step sizes
VE
a1 = minfammm In(1 +
}}
(12)
[V)]
and
0++1 = min In(1 a 1)I[ (0)
(O)l /2 - te amaxx 20% J
(13)
|xx11
5

---

Algorithm A general path following algorithm.
Input: e 0, Co I 1/4, Ci 2 02 0, < Omax S 5-1 and bmax E (0, oo].
Output: grid points {tx [== and an approximated solution path @(t).
1: Initialize: k 1.
2: Compute Qr using (12). Starting from 0, iteratively calculate 81 by minimizing fo, (0) until (8)
is satisfied for & =
3: while (14) is not satisfied, do
4: Compute 0x++1 using (13), update IA+11 ls. + ak+1-
5: Starting from Pz. iteratively compute 0x+1 by minimizing ft (0) until (8) is satisfied.
6: Update k: = k: +
7: Interpolation: construct solution path 8(t) through linear interpolation of (0x 10 k=1 using (3).
and we terminate the algorithm at fn when
L max tmax [y])
02
Se or IN 2 mmax
(14)
enN
where e1 2 c2 > 0, and a'max S 1/5 are absolute constants. Note that the above step sizes and termination criterion are chosen to ensure that the upper bounds in (9) and (10) are at most (c)).
Formally, we show that, given any > 0, the above scheme achieves e-suboptimality (11) for O(t) (up to multiplicative constant).
Theorem 3. Suppose that (0) is differentiable and convex. For any O and mmax E (0, oo). assume that either tmax < 00 or (f(maax) l2 < cc. Then, using the step sizes and the termination criterion specified above in (12), (13), and (14), any algorithm that produces iterates satisfying (8)
for any k 2 terminates finite number of iterations, and when terminated, the solution path (t)) satisfies
sup S
(f(((()) ((((()))((((())))) E.
(15)
Note that when is small enough, we have that a1 In (1 (0]1)) which together with (15) implies that
- ((((())--(00))) -c" (((=-))([V (0)1
sup OStstmax
As result, the approximation error for the solution path is essentially controlled by the initial step size a1. Smaller 01 leads to better approximation. However, smaller a1 also leads to a slower exploration of the solution path and more stringent stopping criterion individual grid points (c.f. (8)). As such, the initial step size controls the trade-off between computational cost and accuracy. Moreover, given 01,
from (13) that how fast the algorithm explore the solution path depends largely on ||0x 1|22 In particular, ||0alla is bounded (e.g.. when 0 finite), then the first term in the min function of (13) increases to increases. Therefore, aggressive step sizes can be taken in this case until it reaches (1)) which will likely lead to fast exploration of the solution path. On the other hand, if [0x]] lla grows quite quickly to infinity increases, then the first term in the min function may go to zero sizes need to decrease to zero eventually, leading to slower exploration of the solution path.
+ Do (say, when |0@lla/e**
oo). This means that the step
We summarize the proposed scheme in Algorithm 1. Again, we emphasize that the above scheme can be applied to any optimization algorithm. Later, we will empirically investigate its performance using Newton method and gradient descent method.
Lastly, we establish an upper bound on the total number of grid points required for Algorithm to achieve essuboptimality.
Theorem 4. Under the assumptions Theorem the total number of grid points required for Algorithm I to achieve an e-suboptimality (15) is most -1/2).

---

Extensions to nonconvex loss functions
So far we assume that the empirical loss convex. Next, we consider a generalization, where we do not assume convexity for L,, (f). Instead, we assume that there exists X(t) > 0 so that
m((0) - (-((()))) & 2X(() VA(()
(16)
for any 2 and 0 E dom(L,)) In the literature. the condition (16) was often referred as the folyak--ojssiwwice (PL) inequality. Polyak [1964] proved the linear rate of convergence for gradient descent method under this condition. Also see Karimi et al. [2016] for discussions of more recent development. Note that if I., (0) is convex, then (16) holds for X(L) e- since (z(0) is e ----ronggll convex. In general, however, T., (0) does not need to convex for (16) hold.
For some technical reasons, we need to consider slightly different interpolation scheme
(() 0x for any / [4,, 1++1), S k N
(17)
((t) N for any tN < max t < &max
where to 0 and 0u 0. As We use the following termination criterion at each t.z
that the approximated solution path is piecewise constant.
1|91 ll I min(Co(e"
L. (0)l2, 1);
1 ll S min(Co c -
(18)
et* - 110112 1), h 1.
We also define slightly new step size scheme follows:
a1 = min min(amaxx In(1 + Vemin(Ag:21))
(19)
and
0.+1 minffamss 20x, In(1 ( VI, (0)l2(et* minn min(Ain )e+1)
}}
(20)
||0x 2 min(Ao, A1)
where A = inf, A(1) 0. Finally, the stopping criterion for the path-following algorithm set to be
C3 S or tN 2 1max
(21)
where c3 > 0 an absolute constant.
Moreover, we need to make some additional assumptions on the loss function.
Assumption (A1). Assume that (0) (0) is differentiable and infę (0) > -00. Moreover, assume that there exists a positive decreasing function g(-) such that A(t) Z g(t) > 0 for any S < cc.
Theorem 5. Suppose that Assumption (A1) holds. For any E > 0 and tmax (0, oo), assume that either max 00 or supoci<tt... [0(t)l2 < cc. Then, using step sizes and termination criterion specified in (19), (20), and (21), any algorithm that produces gradients satisfying (18) terminates after finite number of iterations, and when terminated, the solution path @(t) defined in (17) satisfies
sup OStStmax
{f.(0(t)) -f((((t)) SE.
(22)
The above result can be viewed as a generalization of Theorem 3, because when (0) is convex, we could set X(t) exp(-t) so that both condition (16) and Assumption (Al) are satisfied.
Numerical studies
In this section, we study the operating characteristics of Newton method, gradient descent method and a mixed method in ridge regression and regularard logistic regression, using both the simulated datasets and a real data example. Here the mixed method applies gradient descent method to minimize
7

---

fü, (0) at the beginning and then switch to Newton method when the number of gradient steps exceeds min(n. p). To illustrate the advantages of the proposed grid point selection scheme and stopping criterion, we use a standard implementation of a typical path-following algorithm baseline. In particular, the grid points are equally spaced (on log-scale) for both examples. For lg logistic regression, Newton method is used as the basis algorithm with fixed stopping criterion ft, (0x)]lz < 10-5, while for ridge regression the exact solution can be computed. We refer to this method as the baseline method.
We also compare the proposed methods against the method of Ndiaye et al. [2019]. In particular, we compare our grid points selection scheme (13) with the so-called adaptive umilateral scheme proposed in Ndiaye et al. [2019], where Newton method is used as the basis algorithm at each grid point. Different from the aforementioned methods, adaptive unilateral scheme constructs piecewise constant solution path ((A) over chosen grid points to approximate the solution path ((A) = arg min BERP (f),,, where (x) = (o) (2/2)-1 such that for all À E (Amin; Amax)
Pa(O(A)) (x()()) <c.
(23)
We call this Ndiaye's 's method throughout this section.
All methods considered in the numerical studies are implemented in R using Repp package [Eddel- buettel et al., 2011, Eddelbuettel, 2013].
Example 1: Ridge regression. This example considers ridge regression over a simulated dataset. In this case, the empirical loss function is (0) = || x x0 ( where X E R=* and Y E IR" denote the design matrix and the response vector. In the simulation, the data (X,Y) are generated from the usual linear regression model Y = X0* + é, where ē ~ N(0, Ixx), 8" = (1/ (L., 1/) T, and rows of X are IID samples from (0, Throughout this example, we consider n 1000 and p p= 500, 10000,
Example 2: fz-regularized logistic regression. This example considers éz-regularized logistic regression over simulated dataset. Let X E IR" and Y E {+1, -1)" denote the design matrix and the binary response vector. The empirical loss function for logistic regression is L,, Ei= log(1+ exp(-Y;XX, 0)). We simulate the data (X, Y) from a linear discriminant analysis (LDA) model. More specifically, we sample the components of Y independently from Bermoulli distribution with JPY, = +1) = 1/2; i =1,, 1,2..... n. Conditioned on Y,, X,'s are then independently drawn from N(Y.j,, pxp)) pxxp)) where μ E RD and 0² > O. Note that J and r² controls the Bayes under the 0/1 loss, where o()) is the cumulative distribution function 1/ 1/vp) and 0² = 1 so that the Bayes risk (-1), which approximately 15% Similar to Example 1, two different problem dimension are considered: n 1000 and p 500, 10000.
risk, which is o @-11|u1|22/ of a standard normal random variable. Here we choose == (1/ VP.......
Example 3: Real data example. This example fits an fz-regularized logistic regression using the a9a dataset from LIBSVM [Chang and Lin, 201 1]. This dataset provides information about whether an adult's annual income surpasses $50, 000, along with some specific characteristics of the given adult. It contains a total of 32561 examples with 123 features and I binary response variable.
For all three examples, we use the global approximation error supogest.... (f(t)) - (((tt)) as an evaluation metric, where 0(t) is the linear interpolation of the iterates O& generated by each method. Throughout, we let fmax = 10. Since this metric can not be calculated exactly, we approximate the global approximation error by maxigis 100 (0(s)) - fs, (0ss))), where 81:..., 8100 are uniformly sampled from (0, (max). Here we compute the solutions 0(s:) using the CVX solver [Grant and Boyd, 2014, 2008] for Ez-regularized logistic regression, while calculating ((ss) explicitly for ridge regression.
We compare Newton method, gradient descent method and their mixed version against the baseline method and Ndiaye's 's method. To make fair comparison with Ndiaye's method, we set Amnin 1/(e"0 - 1) to match fmax = 10 in log scale and choose Amax = 100.
Figure 1 presents runtime versus global approximation error for Example and 2 based on 100 replications, as we vary e in (12) for our proposed method and (23) for Ndiaye's method. For the baseline method, we vary the spacing between consecutive grid points instead. Clearly the proposed Newton method outperforms the baseline method and Ndiaye's method in both low dimension and high dimension scenarios, which empirically confirms that the proposed grid point selection scheme
8

---

(c.f. (13)) is more efficient than both the standard equally-spaced grid point scheme and the adaptive unilateral scheme proposed by Ndiaye et al. [2019]. Moreover, gradient descent method performs similarly compared with the mixed method in both setups of Example 1, which suggests that switching does not happen much in those cases. However, in both problem dimensions of Example 2, we do see difference between the mixed method and gradient descent, which is due to the fact that the switching to the Newton update does happen and it can speed up the computation by design. Lastly, as one would expect, Newton method is more efficient than both the gradient descent method and the mixed method when the problem dimension is small, but less so when problem dimension is large.
Figure shows the runtime versus global approximation error tradeoff for our real data example, as we vary for our proposed methods and Ndiaye's method, and change grid point spacing for the baseline method. Again, the Newton method is more efficient than both the baseline method and the Ndiaye's method, which demonstrates the advantage of our proposed grid point selection scheme over the standard equally-spaced grid point scheme and the scheme by Ndiaye et al. [2019].
We also plot the number of iterations each grid point for Newton method and gradient descent method in Figure S1-S3 of the supplementary material. Interestingly, for ridge regression (c.f., Figure S1), the number of iterations by gradient method first increases and then stays flat as 44 grows. Newton method, however, only takes one iteration at each grid point. Moreover, the level of approximation (i.e., seems to have no impact on the number of iterations at each grid point, which is highly desirable. For the fz-regularized logistic regression (c.f., Figure S2 and S3), the number of iterations needed increases as &4 increases for gradient descent method, whereas the Newton method always requires just a constant number of iterations at each 44- Again, the level of approximation (i.e., <) does not seem influence the number of iterations much.
p=500
p=10000
Saenira methed
Eaeniree methes
subontroou
Mexttn
Moutto
-6
0.10
1.00 Runtime (in seconds)
10.00
10.00
100. 000.00
1 000.00
Runtime (in seconds)
p=500
p=10000
Wozd rothad
Subxpimalty
SU 1 mo
Movtan
Easelie rectce
mecke
-8
1.00
Runtime (in secondss 106.00
10.00
1.00
10.00
100.00
1 000.00
10 000.00
Runtime (in seconds)
Figure 1: Runtime v.s. suboptimality for the Newton method, the gradient descent method, the mixed method, the baseline method and Ndiaye's method under two problem dimensions when applied to ridge regression (upper panels) and fz-regularized logistic regression (lower panels). The vertical and horizontal lines at each point represent the standard errors of suboptimality and runtime.
5 Discussion
In this article, we proposed novel grid point selection scheme and stopping criterion for any general fath-following algorithms. A simple solution path was constructed through linear interpolation

---

Suboppinaitt
Baselinc
Nokye
Mewtar
-10
10.00
100.00 Runtime (in seconds)
1.00.000
Figure 2:
Runtime suboptimality for the Newton method, the gradient descent method, the mixed method, the baseline method and Ndiaye's method when applied to fz-regularized logistic regression the a9a real dataset from LIBSVM [Chang and Lin, 2011].
and theoretical approximation-erron bound was derived. A generalization to class of nonconvex empirical loss was also considered. We have not touched on the overall computational complexity analysis for commonly used optimization algorithms. Based some preliminary analysis, conjecture that for gradient descent method and Newton method, the number iterations required are O(E In(e ))) and ( 1/3), respectively. Moreover, lower bound results are also worth investigating, that is, what are the minimum number of gradient Newton steps needed to achieve an e-suboptimality for the entire solution path? Moreover, our current analysis can be readily extended
to general differentiable regularization functions. A more challenging future direction is to investigate the case where the empirical loss function or the regularizer are not differentiable.
Acknowledgments and Disclosure of Funding
The authors are supported in part by the US National Science Foundation (NSF) under grant DMS- 17- 12580, DMS-17 17-21445 and DMS-20. 111S-00-1449. The authors thank the reviewers for valuable comments and suggestions that improved the article.
References
T. B. Arnold and R. J. Tibshirani. Efficient implementations of the generalized lasso dual path algorithm. Journal of Computational and Graphical Statistics, 25(1):1-27, 2016. doi: 10. 10.10000/6111 5. 1008638.
Bao, Gu, and H. Huang. Efficient approximate solution path algorithm order weight 1 I-norm with accuracy guarantee. In 2019 IEEE International Conference on Data Mining (ICDM), pages 958-963. IEEE, 2019.
H. H. Bauschke, P. L. Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
C.-C. Chang and C.-J. Lin. Lihsvm: library for support vector machines. ACM transactions intelligent systems technology (TIST), 2(3)1-27,,2) 2011.
D. Eddelbuettel. Seamlexs and C++ integration with Repp. Springer. 2013.
D. Eddelbucttel, R. François, J. Allaire, K. Ushey, Q Kou, N. Russel, J. Chambers, and D. Bates. Repp: Seamless and c++ integration. Journal of Statistical Software, 40(8):1-18, 2011.
B. Efron, T. Hastie, I. Johnstone, and R. Tishirani. Least angle regression. The Annals of Statistics, 32(2):407- 499, 2004.
Friedman, Hastie, Hofling, and R. Tibshirani. Pathwise coordinate optimization. The Annals of Applied Statistics, 1(2):302-32,, 2007.
P. Garrigues and L. Ghaoui. An homotopy algorithm for the lasso with online observations. Advances in neural information processing systems, 21, 2008.
10

---

J. Giesen, M. Jaggi, and S. Laue. Approximating parameterized convex optimization problems. In European Symposium on Algorithms, pages 524-535. Springer. 2010.
J. Giesen, J. Müller, S. Laue, and S. Swierey. Approximating concavely parameterized optimization problems. In Advances in neural information processing systems, pages 2105 2113, 2012.
J. Giesen, S. Laue, and P. Wieschollek. Robust and efficient kernel hyperparameter paths with guarantees. In International Conference on Machine Learning, pages 1296-1304, 2014.
M. Grant and S. Boyd. Cvx: Matlah software for disciplined convex programming, version 2.1, 2014.
M. C. Grant and S. P. Boyd. Graph implementations for nonsmooth convex programs. In Recent advances in learning and control, pages 95-1 10. Springer, 2008.
T. Hastie, S. Rosset, R. Tishirani, and J. Zhu. The entire regularization path for the support vector machine. Journal of Machine Learning Research, 5:1391 1415, 2004.
T. Hastie, J. Taylor, R. Tibshirani, G. Walther, et al. Forward stagewise regression and the monotone lasso. Electronic Journal of Statistics, 1:1-29, 2007.
H. Hoefling. A path algorithm for the fused lasso signal approximator. Journal of Computational and Graphical Statistics, (9(4):984-1000 2010. doi: 10. 19011999...22200092222
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient -gradient methods under the polyak-tojasiewiczz condition. In Joint European Conference Machine Learning and Knowledge Discovery Databases, pages 795-811. Springer, 2016.
E. Ndiaye. Safe optimization algorithums for variable selection and hyperparameter tuning. PhD thesis, Université Paris-Saclay (ComUE). 2018
B. Ndiaye, T. Le, O. Fercoq, J. Salmon, and I. Takcuchi. Safc grid search with optimal complexity. In International Conference on Machine Learning pages 4771-4780, 2019.
Y. E. Nesterov and A. S. Nemirovskii. Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms. STAM Publications, 1993.
M. Osborne. An effective method for computing regression quantiles. IMA Journal of Numerical Analysis, 12: 151 166, 1992.
M. Osborne, B. Presuell, and B. Turlach. A new approach variable selection least squares problems. IMA Journal of Numerical Analysis, 20(3):389 403, 2000.
B. T. Polyak. Gradient methods for solving equations and inequalities. USSR Computational Mathematics and Mathematical Physics, 4(6):17-3) 1964.
X. Qu, D. Li, X. Zhao, and B. Gu. Gaga: Deciphering path of generalized self- siff-paced regularizer. Advances Neural Information Processing Systems, 35:32025 32038, 2022.
S. Rosset. Following curved regularized optimization solution paths. In Advances in Neural Information Processing Systems, 2004.
S. Rosset and J. Zhu. Piecewise linear regularized solution paths. Ann. Starist., 35(3):1012 1030, 2007. doi: 22440090500000000011113
T. Sun and Q. Tran-Dinh. Generalized self-concordant functions: recipe for newton-type methods. Mathemati- Programming, pages 1-69. 2017.
R. J. Tibshirani and J. Taylor. The solution path of the generalized lasso. The Annals of Statistics, pages 2011.
Y. Zhu and R. Liu. An algorithmic view of Éz-regularization and some path-following algorithms. The Journal of Machine Learning Research, 22(1):6123-618) 2021.


Reviews:
[{"review_id": "8D8979BaWl", "reviewer": "Reviewer_2KPJ", "summary": "The submission 9422 proposed a novel selection scheme for grid search and stopping criterion for a more general path-following algorithms, while not trying to compute/derive the whole solution spectrum. The analysis of the authors indicates that under certain assumptions, their proposed approximate path-tracking algorithm (with linear interpolation) can approximate the exact solution path and provide theoretical boundaries. The theoretical conclusions have been verified to some extent through some simple numerical simulations.", "questions": "- Why not use the vanilla $C(t):=t$ to replace the current $C(t):=e^t-1$ in your analysis?\n\n- I suggest the authors to plot the *path visualization* of $\\tilde{\\theta}(t)$ as well as $\\theta(t)$, to help the readers that may not familiar with the solution path area. also we can observe how the computed path (via algo. 1) approximates the ground truth.", "limitations": "- some technical limitations of the current method were mentioned in some parts of the paper, but there was no detailed/thorough discussion.\n\n- there is no need to discuss potential negative social impacts.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Solution path (hyperparameter optimization) is an interesting and important topic in both theory and application communities of ML.\n\n- The paper is well written and it clearly state its contributions, notation and results. The most part of their derivations are easy to follow (for me).", "weaknesses": "- The numerical simulations of this work is too weak and might not be convincing. \n  - the scale of the experiment is too small. The authors are suggested to consider more objectives since their analysis can be readily extended to general differentiable functions\n  - lack of experiments on real-world benchmark datasets, e.g., UCI, libsvm\n  - the code (currently) has not been submitted and lacks *sufficient* details for reproducibility\n\n- Lack of some existing research work on the situation where the exact paths are not piecewise linear, e.g.,\n\n  - [1] Pierre Garrigues, and Laurent Ghaoui. *An homotopy algorithm for the Lasso with online observations.*  Advances in neural information processing systems 21 (2008).\n\n  - [2] Xingyu Qu, Diyang Li, Xiaohan Zhao, and Bin Gu. *GAGA: Deciphering Age-path of Generalized Self-paced Regularizer.* Advances in Neural Information Processing Systems 35 (2022).\n\n  - ...\n\nI also suggest that the authors further highlight the intrinsic differences from recent work and the technical challenges faced by their settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments and suggestions. \nWe summarize our response as follows.\n\n**Weaknesses**\n\n* Thanks for your suggestions on numerical simulations. Following your suggestion, we have added a real-world data example in our numerical studies section (please see plots in Section 1 of our author rebuttal pdf).  We will make all the code publicly available if the article gets accepted. \n* Thanks for pointing out additional related works. We have included those works and added some additional discussions in our revision.\n\n**Questions**\n* We agree that our current choice of $C(t) = e^t - 1$ is not essential\nand can be replaced by $C(t) = t$.\nThe primary rationale behind choosing $C(t) = e^t - 1$ is that grid points selection are typically equally spaced in the log-scale. \nMoreover, it makes some of the algebra much simpler and cleaner in our theoretical derivations. \n\n* Thanks for the suggestion. We have included the visualization of $\\tilde{\\theta}(t)$ and $\\theta(t)$ of simple examples in the supplementary material in the revision (please see plots in Section 2 of our author rebuttal pdf). We will move this part to the main text if the article gets accepted."}, {"review_id": "BV5bZZoSTw", "reviewer": "Reviewer_5bG4", "summary": "This paper considers this problem of the ($\\ell_2$-regularized) $M$-estimation problem of computing solutions to the regularized objective $(e^t – 1) L(\\Theta) + (1/2) \\| \\Theta \\|_2^2$ for all $t$, denoted $\\theta(t)$. The paper proposes a method for approximating theta(t) for carefully chosen values of t, such that interpolating between these points approximately solves the problem. When $L$ is convex and differentiable the paper proves that (under certain bounds) $1/\\sqrt{\\epsilon}$ values of t suffice to obtain a curve of $\\epsilon$ approximate solution to the regularized objective. The paper discusses how this improves upon prior bounds, how the scheme has desirable properties for implementation, and provides experiments implementing the algorithm. Further, the paper discusses extensions of their work to non-convex optimization.", "questions": "My main question are those raised in the “Weaknesses” category. Additionally, below are some more detailed suggestions, questions, and comments:\n\n* Line 16: “Corroborate with our theoretical” --> “Corroborate our”\n* Line 62 – 99: It would be helpful to know what exactly is hidden in the $O(\\cdot)$ notation.\n* Line 112: why write the $n$ in $L_n$? Does it arise anywhere else in the paper?\n* Theorem 1: some more discussion of the proof strategy would be nice.\n", "limitations": "The paper doesn’t discuss weaknesses and limitations, but the paper is primarily bout the theoretical and empirical analysis of an algorithm for solving a sequence of regularized optimization problems. Consequently, the societal impact is unclear. Further, the weaknesses and questions discussed reflect limitations for which further discussion might be beneficial.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The $M$-estimation problem that the paper considers is a natural and feels fundamental. This paper provides a seemingly useful set of theoretical (algorithms and bounds) and empirical (experiments) on this fundamental problem. Further, the paper argues how they improve upon prior work on this problem. Additionally, the paper is fairly well-written, suggests an interesting direction or future work, and could invite further study of the problem.", "weaknesses": "The problem considered and the approach for it feels quite natural. This is not necessarily an issue except that it isn’t clear from the writing if the results are not what one might obtain by following the first approaches for the problem one might think of. For example, if one simply computes the derivative of the value of the regularized objective minimizer with respect to t and then bounds the terms, does that more or less directly suggest the approach of the paper? More broadly, I think the paper could benefit by discussing their proof strategy and any obstacles that had to be overcome in achieving their result.  \n\nAdditionally, I thought it would be helpful if the paper was a little clearer about what assumptions need to be made to achieve, e.g., the claimed $O(1/\\sqrt{\\epsilon})$. What other quantities does this rate depend on exactly? As discussed briefly in the following “questions” section I think it would be helpful to discuss all the quantities that the proposed method depends on.   \n\nFinally, the $M$-estimation problem seems like one that could be studied in part under different names in a number of different areas. Ultimately, it is in some sense asking to approximately follow a certain induced curve which seems like something that could have arisen in a number of contexts. Consequently, more literature review or discussion to raise confidence in the novelty of the proposed method would be helpful.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments and suggestions. \nWe summarize our responses below: \n\n**Weaknesses**\n\n* Thanks for the suggestion, we have added the proof strategy for Theorem 1. Basically, the proof of Theorem 1 starts with relating the local approximation error to the suboptimality of $\\theta_k$ and $\\theta_{k+1}$ at \nsome $t \\in [t_k, t_{k+1}]$. The suboptimality can then further bounded \nby the square norm of the grandient leveraging the fact that the objective function is \n$e^{-t}$-strongly convex. Finally, a triangular inequality is used \nto bound the norm of the grandient by quantities that depend on $\\|g_k\\|_2$ and $\\|\\theta_k\\|_2$. \n\n* The hidden quantities behind our claimed number of iterations $\\mathcal O(1/\\sqrt{\\epsilon})$ include \nparameters $c_2$, $\\alpha_{\\max}$, $t_{\\max}$, as well as the problem-dependent constants $\\|\\theta(t_{max})\\|_2$ \nand $\\|{\\nabla} L_n(0)\\|_2$.  \n\n* Basically, a larger $c_2$ or $\\alpha_{\\max}$ will lead to fewer number of iterations, while a larger $t_{\\max}$ will require more iterations. \nThe problem-dependent constants $A = \\|\\theta(t_{\\max})\\|_2$ and $B = \\|\\nabla L_n(0)\\|_2$ impact the number of iterations jointly through quantity $\\nu_1 = B/(2(A+B))$. The number of iterations needed will increase as $\\nu_1$ increase. \n\n* Thanks for the suggestion, we have included some additional related works and additinoal discussions in the Introduction section.\n\n**Questions**\n* Fixed. \n* See the response in above **Weaknesses** section. \n* Since the loss function is often formulated based on the training examples, \nwe use notation $L_n$ to reflect that $n$ examples are considered when we define the loss function. \nFor example, in the section 4.2 of our current main text file, we have that the empirical loss function for logistic regression is\n$L_n(\\theta) = n^{-1} \\sum_{i=1}^n \\log(1+\\exp(-Y_i X_i^\\top\\theta))$.\n\n* Thanks for the suggestion, we have added the proof strategy for Theorem 1 in the revision. The basic idea can be found in above **Weaknesses** section. \n"}, {"review_id": "8PMpZrMlHJ", "reviewer": "Reviewer_omjq", "summary": "This paper proposes a new path following algorithm for 2-regularized M-estimation with an approximation guarantee. The algorithm includes a grid point selection scheme and an adaptive stopping criterion to optimize the trade-off between model fit and complexity in machine learning algorithms. The paper also provides a comparison of the proposed scheme to a standard path-following scheme through a simulated study using ridge regression and L2-regularized logistic regression.", "questions": "see weaknesses", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. This paper proposes a new path following algorithm for 2-regularized M-estimation with an approximation guarantee.\n\n2. This work is generally technically sound with rigorous statistical analysis in the work. \n\n3. The article is well written and mathematical derivations are easy to follow.", "weaknesses": "1: The main body does not include the experimental results.\n\n2: The experiments were solely conducted on simulation datasets, and evaluating the method on public datasets could enhance the results.\n\n3: The experiments do not include other baselines on solution path algorithms.\n\n4: Can the proposed method be extended to other regularized M-estimation techniques, such as Lasso or Group Lasso?\n\n5: It is important to discuss relevant existing work on solution path algorithms, including notable studies such as [1], as well as approximate solution path algorithms, like [2].\n\n[1] Ryan Joseph Tibshirani, Jonathan E Taylor, Emmanuel Jean Candes, and Trevor Hastie, \"The solution path of the generalized lasso,\" The Annals of Statistics, 2011.\n\n[2] Runxue Bao, Bin Gu, and Heng Huang, \"Efficient Approximate Solution Path Algorithm for Ordered Weighted L_1-Norm with Accuracy Guarantee,\" ICDM 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments and suggestions. \nWe summarize our responses below: \n\n**Weaknesses and Questions** \n1. Thanks for the suggestion. We have moved all the *runtime versus global approximation error* plot for the simulation studies (Figure S1 and Figure S3 of current supplementary file) to the main text. We may move additional plots in the Appendix to the main text if the paper is accepted.\n\n2. Thanks for your suggestions. We have added a real-world data example in the revision (please see plots in Section 1 of our author rebuttal pdf).\n\n3. Thanks for the suggestion. Our current baseline algorithm selects equally spaced grid points (on a log-scale), which is widely adopted by many popular packages such as glmnet. \n\n4. Unfortunately, it seems that our proposed method can only be easily extended to the differentiable regularizer. Extensions to nonsmooth regularizer seem to be not straightforward, and will be left for future work. \n\n5. Thanks for pointing out additional related works. We have included them and some discussions in the revision. "}, {"review_id": "PePCBrLLUS", "reviewer": "Reviewer_toMd", "summary": "A novel grid point selection scheme and stopping criterion for any general path-following algorithms are proposed in this paper. However, the presentation of this paper is poor, and the contributions are not clear.", "questions": "1. The writing of this paper needs improvement. It is suggested to enhance readability by discussing the definition of \"regularized M-minimization problems\" in the introduction, possibly with some formulation.\n\n2. Lack of clarity regarding the contributions of this paper. Although this work presents some interesting theoretical results, it is recommended that the author explicitly clarify the contributions in the Introduction.\n\n3. Placement of experimental results in the Appendix. Uncertain why the authors chose not to include the results in the main text, especially considering the available space on the ninth page.\n\n4. Non-compliance of the appendix format with NeurIPS requirements. It is advised that the authors make the necessary corrections to adhere to the guidelines.\n\n5. Readability and organization concerns. To enhance the paper's readability, it is suggested to add a \"Related Work\" section to introduce works relevant to this study. Furthermore, the entire paper's structure requires careful modification.", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "A novel grid point selection scheme and stopping criterion for any general path-following algorithms are proposed in this paper.\n\nThis work provides some interesting theoretical results. For example, this work theoretically shows that the approximation error of the proposed solution path can be upper bounded by the sum of the interpolation and optimization error, and establish a global approximation-error bound for the solution path.", "weaknesses": "This work provides some interesting theoretical results, however, I am dissatisfied with the writing and organization of this paper.\n\n1. The writing of this paper is poor. In order to enhance the readability, I suggest the author discuss the definition of \"regularized M-minimization problems\" in the introduction, maybe with some formulation.\n\n2. The contributions of this paper are not clear. This work shows some interesting theoretical results,  I suggest the author clearly clarify the contributions in the Introduction. \n\n3. The experimental results are all put in the Appendix in the current manuscript. I am unsure why the authors did not put the results in the main text, especially considering that there are many empty spaces on the ninth page of the main text.\n\n4. The format of the appendix may not comply with the requirements of NeurIPS. I recommend that the authors make corrections accordingly.\n\n5. To further improve the readability of this paper, I suggest the author add a \"Related Work\" section to introduce some works related to this work. And the organization of this work is poor, I suggest the author carefully modify the whole paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments and suggestions. \nWe summarize our responses below.\n\n**Weaknesses and Questions** \n\n1. Thanks for the suggestion. Following your suggestion, \nwe introduced the definition of regularized $M$-estimation \nearlier in the Introduction section in our revision. \n\n2. Thanks for the suggestion. We have made a few changes to the Introduction section to better highlight our contributions.\nIn particular, the key contributions are summarized in the third and fourth paragraphs in Section 1. \n\n3. Thanks for the suggestion. We now include the *runtime versus global approximation error* plot for the simulation studies  (Figure S1 and Figure S3 of current supplementary file) in the main file. We may move additional plots in the Appendix to the main text if the paper is accepted.\n\n4. Thanks for the suggestion. We now have changed the format of the supplementary material by using the NeurIPS template.\n\n5. Thanks for the suggestion. Most of the discussions of related work can be found in the last few paragraphs of the Instroduction section starting from line 62 of the current main text file. \nThe discussions involve summarizing relevant work as well as highlighting their differences and new contributions of our work \ncompared to existing works. \nAs such, we feel that the contributions of the article should be quite clear to the reader, and a separate Related Work subsection may not be necessary. \n"}]

Author rebuttal:
Thanks for all of your valuable comments and suggestions. 
Following your suggestions,
we have made some changes to our submission, which we feel greatly improved the presentation. 
Main changes include: 

* We moved the formal definition of $M$-estimation earlier in the Introduction section, and made a few changes to the Introduction section to better highlight our contributions.
* We included suggested related literature and added additional discussions of the existing works.
* We moved the *runtime versus global approximation error* plots of our numerical studies into the main file. 
* We added plots to visualize our approximated solution path as well as the ground truth solution in the Appendix (also see plots in Section 2 of our author rebuttal pdf). We will include them in the main file if our paper gets accepted.  
* We added a real data analysis example in Section 4 (also see plots in Section 1 of our author rebuttal pdf). We will place the entire real data analysis section in the allowed additional content page if our paper gets accepted.




Meta-review: I am recommending acceptance but strongly recommend that the authors take into account the comments of the reviewers. As examples of issues brought up by the reviewers:
1. The paper would be more informative with extended results on real data. Simulated data often has nice properties, and some methods that work on simulated data do not work well on real data.
2. Extended discussion of related works and what rates they would achieve, and comparison to suggested baselines in the experiments.

Another line of work that the authors may not be aware of are methods that search along the solution with the goal of finding a particular solution. These were previously popular for L1-regularization, with the two most-impactful works probably being:
- Probing the Pareto frontier for basis pursuit solutions
- A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem
Decision: Accept (poster)