Nonconvex Theory of $M$-estimators with Decomposable Regularizers
Authors: Weiwei Liu
Venue: ICML 2025 poster (2025)
Keywords: $M$-estimators
Nonconvex Theory
Primary area: theory->learning_theory

Abstract: High-dimensional inference addresses scenarios where the dimension of the data approaches, or even surpasses, the sample size. In these settings, the regularized $M$-estimator is a common technique for inferring parameters. (Negahban et al.,
2009) establish a unified framework for establishing convergence rates in the context of high-dimensional scaling, demonstrating that estimation errors are confined within a restricted set, and revealing fast convergence rates. The key assumption underlying their work is the convexity of the loss function. However, many loss functions in high-dimensional contexts are nonconvex. This leads to the question: if the loss function is nonconvex, do estimation errors still fall within a restricted set? If yes, can we recover convergence rates of the estimation error under nonconvex situations? This paper provides affirmative answers to these critical questions.

Nonconvex Theory of M M-estimators with Decomposable Regularizers
Weiwei Liu
Abstract
well as new methods in high-dimensional regimes.
figh-dimensional inference addresses scenarios where the dimension of the data approaches, or even surpasses, the sample size. In these settings, the regularized M-estimator is common tech- nique for inferring parameters. (Negahban et al., 2009) establish a unified framework for estab- lishing convergence rates in the context of high- dimensional scaling, demonstrating that estima- tion errors are confined within restricted set, and revealing fast convergence rates. The key as- sumption underlying their work is the convexity of the loss function. However, many loss func- tions in high-dimensional contexts are nonconvex. This leads to the question: if the loss function is nonconvex, do estimation errors still fall within a restricted set? yes, can we recover convergence rates of the estimation error under nonconvex sit- uations? This paper provides affirmative answers to these critical questions.
The regularization M-estimator technique has gained signif- icant attention as means of estimating model parameters within high-dimensional contexts (Liu, 2023). (Negahban et al., 2009) introduce a comprehensive framework for the regularized -eestimmtoor, This framework not only consol- idates and extends prior findings but also introduces fresh insights into consistency and convergence rates within the high-dimensional situation. Their work further document- ed in the seminal textbook on high-dimensional statisties authored by (Wainwright, 2019). Specifically, (Negahban et al., 2009) develop two pivotal properties of the regular- ized Meestimator: Firstly, they establish the decomposabil- ity property of the regularizer; Secondly, they introduce the concept of restricted strong convexity for the loss func- tion. When the loss function is convex and the regularizer exhibits decomposability, their analysis reveals that the er- ror vector between any global optimum of the regularized M -Mestimator and the unknown ground truth parameter falls within a tightly constrained set. Additionally, in cases where the loss function demonstrates convexity and complies with the conditions of restricted strong convexity, and the reg- ularizer is decomposable, one of their principal theorems establishes the convergence rates for the estimation error under high-dimensional scaling.
1. Introduction
Recently, the emerging trends of high feature dimensionality have been studied in (Mitchell et al., 2004; Fan et al., 2009; Zhai et al., 2014; Liu & Tsang, 2015; 2017; Liu et al., 2017b; 2019b;a; Liu & Tsang, 2016). For example, quintillion bytes of data are generated by the Web on a daily basis (Zikopoulos et al., 2012; Zhai et al., 2014; Liu et al., 2017a; 2018; Liu & Shen, 2019; Gong al., 2023b;a; 2021). This surge in data has led situations where the dimensionality of features (d) approaches even surpasses the size of the sample size (n). In such regimes, classical "large n. fixed d" theory often fails to provide useful predictions, and the performance of standard methods will also be significantly degraded. Thus, it is imperative to develop new theory as
The principal premise underpinning their primary findings relies on the convexity of the loss function. However, in high-dimenn nigh-dimensional settings, many loss functions exhibit non- convex characteristics. For example, mixture models and high-dimensional sparse linear regression models with noisy and/or missing data are nonconvex, which will be described in details in subsequent sections. This motivates to ask the following questions:
When the loss function is nonconvex, do estimation errors still fall within a constrained set?
'Scoool of Computer Science, National Engineering Research Center for Multimedia Software. Institute of Artificial Intelligence and Hubei Key Laboratory of Multimedia and Network Communi- cation Engineering, Wuhan University, Wuhan, China. Correspon- dence to: Weiwei Liu <liuweiwei863 gmail.com>.
2. If yes, can we recover the convergence rates of the estimation error under nonconvex regimes?
This paper provides affirmative answers to these questions.
Contributions. This paper advances the theory of regu- larized M -stimmtto with decomposable regularizers from convex to nonconvex. Our main results show that the esti-
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
mation errors still lie in restricted set and we can recover the convergence rates of the estimation error when the loss function is nonconvex. Moreover, we apply our main results to two nonconvex models: corrected linear regression and l fi-penalized I Lasso estimator. Our key technical analysis of two examples is to prove that with high probability, a form of the restricted strong convexity (RSC) condition and dual norm bound hold.
for the derivatives of the empirical cost function. Through- out the paper, assume that the loss function is differen- tiable, and that the regularizer & is a norm.
2.1. Decomposable Regularizers
The decomposability of the regularizer is introduced by (Negahban et al., 2009; Wainwright, 2019) to analyze the estimation error bound for convex loss functions. We as- sume that the space R is endowed with an inner product ( 1), and we use || || to denote the norm induced by this inner product.
Related Work. (Loh & Wainwright, 2015) is a seminal work, which presents the nonconvex results of regularized M-estimator. (Loh & Wainwright, 2015) focus on the non- convex regularizers, which are defined in Assumption 1 of (Loh & Wainwright, 2015). Specially, nonconvex SCAD and MCP regularizers are studied by (Looh & Wainwright, 2015). This work focuses on the decomposable regularizers, which are defined in Definition 2.1 of our paper. Becasue the definitions of nonconvex regularizers and decomposable regularizers are totally different, the main results of (Loh & Wainwright, 2015) can not be extended to decomposable regularizers.
The notion of a decomposable regularizer is defined in terms of pair of subspaces M C M of R We define the or- thogonal complement of the space MI as MI- := {o E I f) = 0, E M]. The definition of the decompos- ability is provided as below:
Definition 2.1 (Decomposability) Given a pair of sub- spaces M C M. a norm-based regularizer is decompos- able with respect to (M, M if
(a + B) = ((a) + (()), Va E M. e M+
(2)
2. Problem Formulation
Let Z be random variable with distribution IP taking values in set Z. Suppose that we observe a collection of n sam- ples Z = =Z (Zi..., Zn), where each sample Z; is drawn in an independent and identically distributed (i.i.d.) manner from P. Consider a loss function Cn Rd x z + R. The value L, (0: ZT) measures the fit between a parameter vector 0 RRd and the observed data Zp. Its expectation defines the population cost function:
The & norm is the canonical example of a decomposable norm. There are some other norms that also share this property, such as the group Lasso norm and the nuclear norm.
Given a vector 0 E Rd and a subspace S of Rd, we use 0g to denote the projection of f onto S: 6g == arg minges ||0 0|12. Consider any norm +b Rdd - IR its dual norm is defined as +0(v) == sup (u, v). We define G(Xn): == (VL,,, S An.
[() = E 2
The decomposability plays an important role in the M- estimation. The following Proposition introduced by (Wain- wright, 2019) shows that the error vector â Å- 8" between any global optimum of the optimization problem (1) and the unknown parameter 0 lie in very restricted set.
Suppose that the cost function has an additive decomposition of the form C, (0; )T) = Ein [(; Zz), where L Rd x 2 - R is the cost defined on a single sample. Then, the population cost function does not depend on the sample size n. The target parameter vector 8 E Idd is defined as the minimum of the population cost function:
Proposition 2.2. Let Cn : Rd x Z" - R be convex function, let the regularizer क Bd + [0, oo) be norm, and consider a subspace pair (M, M-) over which & is decomposable. Then conditioned on the event G(mn), the error Å = i - 8" belongs to the set
0" arg min C(0) DERd
Our goal to estimate the unknown parameter 0* from the observed samples ZT. In order to do so, we combine the empirical cost function with regularizer or penalty function & Idd + R. The regularized Messtimator is based on solving the following optimization problem:
Co. (M, := (A R (A)))) S (4())) + +40(0%))) )}
(3)
This key property of decomposability is based on the con- vexity of the loss function, which prompts us to ask the first question:
i E arg min (C. 2 X, (()) BERd
(1)
where An > 0 is a user-defined regularization parameter. For ease of notation, we adopt C,,(8) as a shorthand for f. (0; 2T) in the sequel. We also adopt the same notation
Whether the results of Proposition 2.2 still hold if the loss function is nonconvex?
2

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
This paper provides an affirmative answer this question.
Theorem 2.7 (Bounds for general models). Under Assump-
tions 2.5 and 2.6, consider the regularized Meestimator (1)
2.2. Restricted Strong Convexity
conditioned the event ((x)),
Given any differentiable loss function, the first-order Taylor- series error is defined as:
(i) Any optimal solution satisfies the bound
En (4) == (0 + A) - (0* (V),.
$ - 8*) = ( - 1 + ((f
(7)
This error term is always guaranteed to be nonnegative if the loss function is convex. The strong convexity is used
S (i) For any subspace pair (M, - such that n (M))
k/64 and en (ML,, M S R. we have
to ensure that function not too flat and defined as (A) || for all A E Rd. (Wainwright, 2019) show that the strong convexity cannot hold for generic high-dimensional problem. However, for decomposable regularizers, Proposition 2.2 shows that the error vector must lie within a restricted set, and (Wainwright, 2019) use this fact to define the notion of restricted strong convexity as follows.
110 0-1 S e (M,
(8)
The proof of Theorem 2.7 in (Wainwright, 2019) shows that (7) does not depend on the convexity of the loss function, while (8) depends on the convex assumption of the loss function, which prompts us to ask the second question:
Definition 2.3 (Restricted Strong Convexity (Wainwright, 2019)). For a given norm ||. and regularizer (-)) the loss function satisfies restricted strong convexity (RSC) condition with radius R 0, curvature and tolerance T if
Can we recover the convergence rates of the error ||0 00 (8) the loss function is nonconvex?
This paper provides an affirmative answer to this question.
(A) 2 x/2 - - (A) E BR)
(4)
3. Main Results
where B(R) is the unit ball defined by the given norm
||-
This section turns to the statements of our main statistical guarantees, which applies to any vector 0 Rd that satisfies the first-order necessary conditions to be local minimum of (1):
The following results involve the subspace Lipschitz con- stant.
Definition 2.4 (Subspace Lipschitz Constant). For any sub- space S of Rdd the subspace Lipschitz constant with respect to the pair (Ø. ||- I1) is given by
(o) Am Vo. 0) 2 0,0 E Rd
(9)
Such vectors ē satisfying the condition (9) are also known as stationary points.
(S) = sup (uu)
(5)
wES) [|||
Our main statistical results are based on the weaker RSC condition (Loh & Wainwright, 2015) than (4), which shows below:
Consider the following assumptions:
Assumption 2.5. The loss function is convex, and satisfies the local RSC condition (4) with curvature k, radius R and tolerance 7. with respect to an inner-product induced norm ||- ||.
(V + A) V (0'). (O,) A) 2 A/2
(10)
< AA B(R)
For any vector E TR satisfies the first-order necessary con- ditions (9), we define ( (VV..
Assumption 2.6. There is pair of subspaces MI C M such that the regularizer decomposes over (M, M)-)
=
< Xn/2
Theorem 3.1. Let the regularizer &b Rd + [0, oo) be norm, and consider subspace pair (M, M-) over which T is decomposable. Consider any vector á E Rd satisfies the first-order necessary conditions (9), conditioned on the event G G(an), ) the error A = 0 Or belongs to the set
Based on these assumptions, (Wainwright, 2019) present the key bounds for the general models. We first define the quantity involved in the bounds:
(M,, = 9
2
(M) + (Am (00
Co- M+ (A IR T S 3
R2
(6)
(11)
+ +167,0 (Oiz)) }}
+40 )}
3

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
Remark. Theorem 3.1 shows that the results of the Propo- sition 2.2 in (Wainwright, 2019) still hold for any stationary points.
Theorem 3.3. Let the regularizer + IRd + [0, oo) be norm, and consider subspace pair (M, M-) over which & is decomposable. Suppose the loss function satisfies the RSC condition (10). Consider any vector E R satisfies the first-order necessary conditions (9), conditioned on the event G(),). for any subspace pair (M4, M-- such that
The proof of Theorem 3.1 uses the following Lemma.
Lemma 3.2. For any decomposable regularizer and param- eters 8 and A, we have
7 v (M S 128 we huve
Φ +-) - ((0)) 2 (A D(Asa) - (0
110 E
(19)
(12)
Remark. Theorem 3.3 shows that the convergence rates of the eπror ||0 112 (8) in (Wainwright, 2019) still hold for any stationary points. The main results (Theorem 1) of (Loh & Wainwright, 2015) build on the class of nonconvex regularizers and nonconvex loss functions. Specially, they focus on the nonconvex SCAD and MCP regularizers, while our Theorem 3.3 is based the decomposable regularizers. Moreover, Theorem 1 of (Loh & Wainwright, 2015) uses l and Eg norms to measure the error, while our Theorem 3.3 applies for any norms.
The proof of Lemma 3.2 can be found in (Wainwright, 2019).
Proof. (of Theorem 3.1) Suppose vector & E R satisfies the first-order necessary conditions (9). Since 0 is feasible, (9) implies that
(V) + An V -6) 20
(13)
Rearranging (13) yields
Proof. Let Å = Ô- - 0" Combining the RSC condition (10) and first-order necessary condition (9) yields
(O), + (An, (O)), 50
(14)
|/ (A)
Applying the Hölder's inequality with the regularizer and its dual, we have
$ (VL. (0) VL,(0)),
(10)
(O), (VVC..
-V (V))
2 2 + +
An
(15)
I (An (0))), 0- - 0) (VC,
(14)
where the final step uses the assumed bound x' (O) I 2 and the triangle inequality. Using the convexity of the regularizer, we have
An ($(0)) +()) (V',
(the convexity of 4)
S An ( + 200()/2)) ) $ 4 )) - (VC,(
O + 0*) - -00)) V (V + A)
(16)
(Lemma 3.2)
3
$ (1Ax)) 2A,, ((6ggL)
Combining (16) with Lemma 3.2, we obtain
(20)
(An () = (An V4 +0)
where the final step of (20) uses the Hölder's inequality, assumed bound 4" (V., I Xn/2 and the triangle inequality. (7) implies that
2 Am 2 ( 0²) (00))
2 Am ( - -(AR) 20((%))) ))
(17)
Φ² 32 (M)))1)) + (20)(()))))
(21)
Combining (14), (15) and (17) yields
The definition 2.4 of subspace Lipschitz constant implies that
0 02. ( Φ (Axx) - 2 (0%g))
An (a(Az)) + (
.(Á < (M))
(22)
(18)
2
Combining (20), (21) and (22), we have
An ( ( - -30))-33(3300 (Az)) - (0Ga))
(k/2- 3-,,, 2 (Ml) Á1| 3)n
2
(M))IÁ]
2
(23)
This completes the proof of Theorem 3.1.
- -3 (0 + 2A,, T (
4

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
using the assumed bound 32 12 (M) S k/4, have
(27) involves different choices of the pair (f,5) that adapted to the cases of noisy and/or missing data.
7 ||
31 1/ (M)
(24)
For the case of noisy or missing data, the most natural choice of the matrix is not positive semidefinite, hence the quadratic loss appearing in the problem (27) is nonconvex. Furthermore, when I' has negative eigenvalues, the objective in (27) is unbounded from below. Hence, we make use of the following regularized estimator:
- 2 ) 2A, (0 )) 0
Note that the left-hand side of (24) is 2-degree polynomial in ||l To be non-positive, requires (19) to hold, which concludes the proof.
The remainder of this paper is devoted to illustrations of the consequences of Theorem 3.3 for various nonconvex loss functions.
i E arg min
1 o' (5.0) + Am1101113 10
(28)
Let y (V1...., VnY R" and X E IR. with x as its i-th row. Suppose we observe Z X + W, where W is random matrix independent of X, with rows w; drawn independent and identically distributed (i.i.d.) from a zero-mean distribution with known covariance Ew (Loh & Wainwright, 2012) consider the pair
4. Examples
This section illustrates the application of Theorem 3.3 to two nonconvex models: corrected linear regression and f penalized Lasso estimator.
4.1. Corrected Linear Regression
f Z'Z Ew: and 7
Z'y n2
(29)
We consider the case of high-dimensional linear regression with systematically corrupted observations. Suppose that observe a collection of samples (I y1) E Rd x R.
n
Note that when En, = 0 (corresponding to the noiseless case), the estimators (29) reduce to the standard Lasso. When En, + O, the matrix I is not positive semidefinite in the high-dimensional regime. Since the matrix Z'Z has rank at most the subtracted matrix En may cause f to have a large number of negative eigenvalues. Let Amin (E.z) be the minimum eigenvalue of matrix X.
We consider the following linear model
y: = (ci, )-) + Ci, for i = 1,2,....,
n.
(25)
where the regression vector 0" E Rd is unknown and e E IR observation noise, independent of 24. A line of past work (Rosenbaum & Tsybakov, 2010; Loh & Wainwright, 2012) assume that we instead observe pairs {(z,, y.) Y where the 2,'s s are systematically corrupted versions of the corresponding ','s. This setup applies to various corrup- tion mechanisms, including the additive noise: We observe 24 = 24 + wi, where w; E Rd is a random vector indepen- dent of 24, say zero-mean with known covariance matrix E... We consider high-dimensional framework that allows the feature dimensions d to grow and possibly exceed the sample size
Definition 4.1. We say that a random matrix X E guxd is sub-Gausee Gob-Gaussian with parameters (E, o²) if:
each row at E RRd is sampled independently from zero-mean distribution with covariance Σ, and
2. for any unit vector E Rd, the random variable u'z, is sub-Gaussian with parameter at most a.
(Wainwright, 2019) have shown the decomposability of the & norm regularizer. The following theorem shows the estimation error bound for any stationary point of the nonconvex program (28).
We denote the transpose of the vector/matrix by the super- script ' ||- llr represents the e norm (r 2 1). Let Σ, be the covariance matrix of the covariates, and consider the l reggularrizd quadratic program
Theorem 4.2. Suppose we have i.i.d. observations { yo from corrupted linear model with addi- tive noise, where the random matrices X, W E TRuxd are uub-Gaussian with parameters (Ez, 0²)) and (Ew:o?d) respectively. And let be an i.i.d. sub-Gaussian vector with parameter Te- Let o² =oZ + oz. Suppose the true regression vector 4e is supported a subset S of cardinality Assume 2 masma (02+02)²
Ô E arg min ( 1- (E,00,0) + An )011) 2
(26)
8E3d
In practice, we may not know the covariance matrix D and Eed". Given a set of samples {(4, y1) b we propose to use Î E idddd and & E d to estimate V and ,,,", respectively. The corrected linear regression estimator is given by
mmin (5.) 1) log d, >n= co B( + a.0e + owaz + + + (1 stationary point Ô of the nonconvex program (28) satisfies
log Any n
i E arg min 1 1 (5 1m110113 BER4 (2
(27)
5

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
the estimation error bounds
Lemma 4.5 (Dual norm bound). Under the conditions of
Theorem 4.2, there are universal positive constants e; such that
110 11
Co + + ow oo || (2) Vlog
Amin En)vn
|15 1 I An/2
(30)
with probability at least 1 - exp( log d), where An
with
probability
at
least
1
co + t.00 + Owox + o + 1| V logd
ei exp(-c2n) C2n min(
(oot 1)) ci exp(-c2 02 log d).
Remark. The bounds of Theorem 4.2 agree with bounds previously established in Theorem of (Loh & Wainwright, 2012) and Corollary 1 of (Loh & Wainwright, 2015).
Proof. Combining = z'2 Ew. 7 Z'y and X + e,, we have
Lemma 4.3 (RSC condition). Under the conditions of Theorem 4.2, there are universal positive constants C2 such that the loss function satisfies the RSC condi- tion (10) with parameters K Amin (Ex) and T = (22 Lydmin(2is, max( X (2x) 11) logd
T' (VL..
= 115 - -1o1l0c
2'(X0' + - L2Z
-1-- Em 10
n
a
Z'X0" Z'c Z'Z
D2 + E, -Ew)0l 100
ATA K 2/21 HA
n
X'X0
W'X0"
ZL
22' -E,)0
with
probability
at
least
1
+
n
C1 exp( C2n min
Aman (E.) ( 1))-
- (E2 - En)0ll
= X'X6'
W'X6" Z'c
Proof.
The loss function of (28) is (0) = -0000 0). So we have (O) = ñ 5. and (V" + A) (O"), A} = A' The conclusion follows easily from Lemma in Appendix A of (Loh & Wainwright, 2012).
Σ20''
T
n1
7:7 -E,)0
+ Ex - -A)1
X'X0"
200'000 +11 W'X0"
11
Z'c 1o00 + +|1(
Z'Z
The following Lemma in (Loh & Wainwright, 2012) plays the key role the remainder of our proof.
+
E2)0 + +11En(00
1111
(34)
Lemma 4.4. XX RRaxd is a zero-mean sub-Gaussian matrix with parameters oZ), then for any fixed (unit) vector E R4. we have
For the first term in the right hand of (34), we note that cov(x; 20,0%) Ez," Assume c' log d, applying (33)
with (X, X0)), we have
X E
X 12 nt)
1 t
(31)
P X'X0"
log d E10º co02|10 12y
S 22exp min
d o
n
(35)
S C1 exepppee c2 log d)
Moreover, Y E Raax2 is zero-mean sub- sub-Gaussian ma- trix with parameters (E a.), then
Similarly, we have
P(I| Y'X cov x 2:) 2
W X0*
log d
n
P
1l00 2 200 2000001100112
(32)
< dd exp(-cn min(
S ci exp(-c22 C2 log d)
0z0
P Z'e
Z'c
1log d
where yi and zi are the i-th rows of X and Y. respectively. In particular, n 2 d' log d, then
1 2 c00 1/
(36)
71
S c1 exp(
(c2 log d)
Y'X n
log d
P
cou 1lcc 2 Co0
(33)
7 P (16
Σ.)0 loc 2 c,02110112
log d n
n
< ci eexp(=c2llgg0
1i exp( -cg log d)
6

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
Using the Hölder's inequality, we have
We know that the & norm regularizer is decomposable. The following theorem shows the estimation error bound for any stationary point (0, of the nonconvex program (40).
|| (0 - 1o S |0 - 0)1l2 - 1|21112110"
0|12 (37)
Theorem 4.6. Suppose we have i.i.d. observations from Gaussian linear model, where the random matrix X E Rnxd is sub-Gaussian with param- eters (Ez,o%). Suppose the true regression vector 0* is supported on a subset S of cardinality s. Assume of
Setting B- = |10 then we have |10'1/2 < 110 = B
and |001 |2 S |0]]1 I B. (34), (35), (36) and (37) imply the results.
n 2 66s max( (Z,)( 1) log d, An = ca + aza" + || >> (12) logd Any stationary point (0, Q) of the noncon- vex program (40) satisfies the estimation error bounds
Proof. (of Theorem 4.2). We prove the bound (30) via an application of Theorem 3.3. (Wainwright, 2019) have shown the dccomposability of the & norm regularizer with subspaces
11(0 0-, 0"'0-"")1 0z)ll BVBol + +xx0 + +1[Eal12) (41) Amin (Ez)vn
08 = 0 for all j S M = M= = 10 10
M = (0 E 10, = O for all jE Ss
With this choice, note that we have (Ml) the target parameter 8" is contained within a subspace M. Lemma 4.3 shows that the RSC condition (10) holds with high probability. Lemma 4.5 shows that the even- t G(a,) holds with high probability. The assumption (o 2 c1s max( X (x,,) 1) log d implies (M)) S r2s- Thus, we complete the proof of Theorem 4.2.
and
with
at least C2n min( (m)) 1)) - e1 exp( 02 log
probability
C1 exp(
Lemma 4.7 (RSC condition). Under the conditions of Theorem 4.6, there are universal positive constants C₁ such that the loss function satisfies the RSC condi- tion (10) with parameters K. Amin (2i) and T
11
AmAmin (Ei) max( o² Amar (Fa))
1) logd
4.2. ( penalized Lasso Estimator
A 1 , (a" + D2)0 </21 -1
Suppose that we observe a collection of n samples (r;, vk) E Rd x R. We consider the following Gaussian linear model
72
with
probability
at 1)).
least
X0" +
(38)
Ci eexp(=cpp c2n min( Aman
where the regression vector 8" E Rd is unknown, é (f1....,<<) 'x)' RD is the noise and 6 are drawn independent and identically distributed (i.i.d.) from Gaussian distribution (O0, 2) with zero mean and standard deviation o². The l ee-enaalzedd Lasso estimator is defined as
Proof. The loss function of (40) is C, = log(o) +
lly - X0llg/2n. So we have V.,, (0) (-X'(y
X0) X0)/n,1/o)) 1/o). Let A = (A1,A2) where A E Idd and
A2 E R-. We have
Ô E arg min {lly X2 An 10]1 BER
(V + +11, + +A2) VL, (0"')"),,))
(39)
- (o* + =A200*
A3
(42)
We can see that the standard Lasso estimator (39) does not provide an estimate of the nuisance parameter =²
n
From Lemma in Appendix A of (Loh & Wainwright, 2012), we know that
Having a good estimator of ox* plays vital part in mix- ture models and the role of the scaling with the variance parameter is much more important than in homogeneous regression models. Hence, it is important to take x² into the definition and optimization of the penalized maximum likelihood estimator. We consider the following estimator:
1 A/X'X
72
Amin (Ex)
(43)
2
(0, à) E arg min (log(o) + 11y X
Co- (Ex)
max
02 Amin (2n))
1)
log d
|
BB,
(40)
+A, 10111}
holds with
probability Amin (
at Let
least
Note that the loss function (40) is non-convex.
C1 exp(-c2n min
1)).
Amin (Ex)
7

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
and = codmin (oz) max
Amin (Ez)) 1) logd
The
Similarly, we have
following inequality
X'c 2 P(l
log d
1l 2 cua n
S a exp(-c2
1 XXX
A
n
(47)
7
(a+ + 22)0
Using the Hölder's inequality, we have
K 2
A
10" - -11lo I ||_ - 0) = |Ex112100 -
(ar + A2)0
K
1
K
A
2
A3
(48)
2
2
2
(0" + -2)0
Setting B = ||0"|1, then we have 110 S 1100111 = B
2
K
1
2
+
1
)33 -11A
and ||0112 < ||0]] < B. Combining (45), (46), (47) and (48) derives the results.
(o+
+ A2)0*
N 2
1
2
+
(o"
+ +2)0
||A - 1
Proof. (of Theorem 4.6). We prove the bound (41) via an application of Theorem 3.3. The proof of Theorem 4.2 has shown that 1/2 (MI) = s and the target parameter 0* is contained within a subspace M. Lemma 4.7 shows that the RSC condition (10) holds with high probability. Lemma 4.8 shows that the event G())) holds with high probability.
|
2
(
+ +TIAA|I
2
(44)
holds
with
probability Amazn (2
at
least
1
C1 min(
1)).
The assumption n 2 6 max( Amnin (x,)) 1) log d implies
T (M S 128 Thus, we complete the proof of Theorem 4.6.
Lemma 4.8 (Dual norm bound). Under the conditions of Theorem 4.6, there are universal positive constants c; such that
5. Conclusion
IK
& An/2
This paper extends the theory of M-estimators with decom- posable regularizers from convex to nonconvex. Theorem 3.1 recovers the results of the Proposition 2.2 in (Wain- wright, 2019) for any stationary points. Theorem 3.3 re- covers the convergence rates of the error || - 11 (8) in (Wainwright, 2019) for any stationary points. Moreover, we use two simple nonconvex examples to illustrate our main results.
with probability at least 1 Ci exp(-cx 2 log d), where An co Bo + 0z00 + +1|Ex|12) logd
Proof. Using y X0 e, we have
x- (0,,,(00,6)
= =II(-X'(u (VV-XX(xXO0/nn)))
Acknowledgements
=I((-X(XX0 + +c//n+ 1o0
This work is supported by the Key R&D Program of Hubei Province under Grant 2024BAB038, the National Key R&D Program of China under Grant 2023YFC3604702, the Fun- damental Research Funds for the Central Universities under Grant 2042025k10045.
= (1X'X(0-0)/nn>0) 1/0) x
1I(X''/nnE2))) 07) ( 0*)
X'e/n,1/o)ll
= max(1l(X X//n - (0 - 8*) 1| + x'ee/nllo
Impact Statement
+ [[ 8-) l0, 1/0}
(45)
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
For the first term in the right hand of (45), we note that coo(24, (0 - 0*)) En, - 0²). Assume n 2 log d, applying (33) with YX = (X, ( (Ō- - 8))), we have
References
X x - Ar)
En 8r) ||
Fan, J., Samworth, R., and Wu, Y. Ultrahigh dimensional feature selection: Beyond the linear model. JMLR, 10: 2013-2038, 2009.
n
(46)
log d
2 200 - 01
S 6 expl-cc2 log
n
8

---

Nonconvex Theory of M-estimators with Decomposable Regularizers
Gong, X., Yuan, D., and Bao, W. Understanding partial multi-labe learning via mutual information. In NeurlPS, pp. 4147-4156, 2021.
Loh, P. and Wainwright, M. Regularized m-estimators with nonconvexity: statistical and algorithmic theory for local optima. Journal of Machine Learning Research, 16: 559-616 2015.
Gong, X., Yuan, D., and Bao, W. Discriminative metric learning for partial label learning. IEEE Transactions Neural Networks and Learning Systems, 34(8):4428 4439, 2023a.
Mitchell, T. M., Hutchinson, R. A., Niculescu, R. S., Pereira, F,, Wang, X., Just, M. A., and Newman, S. D. Learning to decode cognitive states from brain images. Machine 2004.
Learning, 57(1-2):145
Gong, X., Yuan, D., Bao, W. and Luo. unifying probabilistic framework for partially labeled data learn- ing. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(7):8036-804) 2023b.
Negahban, N., Ravikumar, P., Wainwright, M. J., and Yu, B. A unified framework for high-dimensional analysis of SmS-estimators with decomposable regularizers. In NeurlPS, pp. 1348-1356 2009.
Liu, W. Improved bounds for multi-task learning with trace norm regularization. In COLT, volume 195, pp. 700-714, 2023.
Rosenbaum, M. and Tsybakov, A. B. Sparse recovery under matrix uncertainty. Annals Statistics, 38(5):220--2611, 2010.
Liu, W. and Shen, X. Sparse extreme multi-label learning with oracle property. In ICML, volume 97, pp. 4032- 4041, 2019.
Wainwright, M. Hligh-iimensional statistics; A non- asymptotic viewpoint. Cambridge University Press, 2019.
Liu, W. and Tsang, W. On the optimality classifier chain for multi-label classification. In NeurIPS, pp. 712-720, 2015.
Zhai, Y., Ong, Y.-S., and Tsang, I. W. The emerging "big dimensionality". IEEE Computational Intelligence Mag- azine, 93)):4-226, 2014.
Liu, W. and Tsang, I. Sparse perceptron decision tree for millions of dimensions. In AAAI, pp. 1881-1887, 2016.
Zikopoulos, P. C., deRoos, D., Parasuraman, K., Deutsch, T., Corrigan, D., and Giles, J. Harness the Power of Big Data - The IBM Big Data Platform Megraw-Hill, New York, 2012.
Liu, W. and Tsang, I. W. Making decision trees feasible in ultrahigh feature and label dimensions. Journal of Machine Learning Research, 18:81:1-81:2 2017.
Liu, W., Shen, X., and Tsang, I. W. Sparse embedded k-means clustering. In NeurIPS, pp. 3319-3327, 2017a.
Liu, W. Tsang, I. W. and Müller, K. An easy-to-hard learning paradigm for multiple classes and multiple labels. Journal of Machine Learning Research, 18:94:1-94:33 2017b.
Liu, W., Liu, Z., Tsang, I. W., Zhang, W., and Lin, X. Doubly approximate nearest neighbor classification. In AAAI, pp. 3683-3690, 2018.
Liu, W., Shen, X., Du, B., Tsang, I. W., Zhang, W., and Lin, X. Hyperspectral imagery classification via stochastic hhsvms. JEEE Transactions on Image Processing, 28(2): 577-588, 2019a.
Liu, W., Xu, D., Tsang, I. W., and Zhang, W. Metric learn- ing for multi-output tasks. IEEE Transactions on Pat- tern Analysis and Machine Intelligence, 41(2):408-422 2019b.
Loh, P. and Wainwright, M. J. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Annals of Statistics, 4066),1637-1664 2012.


Reviews:
[{"review_id": "ZgJwL5Ewec", "reviewer": "Reviewer_fa9A", "summary": "The paper studies the high dimensional M-estimators for non-convex loss functions. The previous classical results only consider the convex cases. It is natural to consider the non-convex loss function in high dimensions. The motivation is strong. The central theoretical questions studied in this paper are whether we can extend the classical results from convex to non-convex cases. The paper shows the positive results which are quite interesting and the proof is easy to follow.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1, What is the main difference between the proof of Theorem 2.7 in (Wainwright, 2019) and Theorem 3.3 in this paper? I think it is better to clarify this question in the paper, then the reader can quickly understand theorems and proofs.\n\nThanks for the question. The main difference between the proof of Theorem 2.7 in (Wainwright, 2019) and Theorem 3.3 in this paper is that the proof of Theorem 2.7 in (Wainwright, 2019) uses the RSC condition (4), while our proof of Theorem 3.3 relies on the  RSC condition (10). The difference between  (4) and (10) contributes the key difference between Theorem 2.7 in (Wainwright, 2019) and Theorem 3.3 in this paper.\n\n\n2, What is the difference between the $\\tilde{\\mathbb{G}}(\\lambda_n)$ defined in this paper and $\\mathbb{G}(\\lambda_n)$ defined in (Wainwright, 2019)? Why not use the original definition of $\\mathbb{G}(\\lambda_n)$ in  (Wainwright, 2019)?\n\nThanks for the question.  The $\\tilde{\\mathbb{G}}(\\lambda_n)$ defined in this paper is for stationary points, while the $\\mathbb{G}(\\lambda_n)$ defined in  (Wainwright, 2019) is for the unknown parameter. The price for recovering the Proposition 2.2 in  (Wainwright, 2019) to nonconvex settings is that we have to redefine the $\\tilde{\\mathbb{G}}(\\lambda_n)$ for stationary points.\n\n3, The first example is corrected linear regression. Why corrected linear regression model is non-convex and why do we need to enforce the constraint for parameter $\\theta$?\n\nThanks for the question.  For the case of noisy or missing data, the most natural choice of the matrix $\\hat{\\Gamma}$ is not positive semidefinite, hence the quadratic loss appearing in the problem is nonconvex.  (Rosenbaum & Tsybakov, 2010; Loh & Wainwright,\n2012) have already shown the nonconvexity of this problem. Furthermore, when $\\hat{\\Gamma}$ has negative eigenvalues, the objective in (27) is unbounded from below. Hence, we  enforce the constraint for parameter $\\theta$.  (Loh & Wainwright,\n2012) have already done like this.", "claims_and_evidence": "The claims made in this paper are well-supported by rigorous mathematical derivations and proofs.", "methods_and_evaluation_criteria": "The methods employed in the paper are mathematically rigorous and appropriate for the problem setting.", "theoretical_claims": "I carefully reviewed key results, including Theorem 3.1 and Theorem 3.3. The derivations are logically sound. The proofs appear correct, assuming the stated assumptions hold.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "(Loh & Wainwright, 2015) present the nonconvex results of regularized M-estimator with non-convex regularizers. This paper considers the nonconvex results of regularized M-estimator with decomposable regularizers.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths\n\nOriginality\n\nThe paper studies the important theoretical questions which are never covered by previous works. This paper is the original research. \n\nQuality\n\nThe decomposable regularizers and restricted strong convexity are two key concepts that play the important roles in the high dimension statistics. The decomposable regularizers enforce that the estimated errors fall into a restricted set. Motivated by this, the restricted strong convexity is defined to show the property of strong convexity only along some directions. The classical results show that one can get the desired convergence rates of the estimated error. The basic assumptions are the convexity of loss functions. The paper aims to break the convex assumption and consider the non-convex settings. To address the questions, the paper is mainly based on the weaker RSC condition (Loh & Wainwright, 2015) than (4). The main results in this paper show that both the Proposition 2.2 and convergence rate of the estimated error in (Wainwright, 2019) still hold for any stationary points. The proof is simple and rigorous. The paper also use two non-convex examples to illustrate the theories. The overall quality is quite impressive.\n\nClarity\n\nThe motivation, the background and the main proofs are well organized and easy to follow. \n\nSignificance\n\nThe main results of this paper are important. They extend our knowledge on high dimensional M-estimators from classical convex to nonconvex cases. The significance is that they may motivate the other researchers to study more challenging non-convex loss functions.\n\nWeaknesses\n\nAlthough the results obtained this paper are important, I still have some questions for the authors:\n1, What is the main difference between the proof of Theorem 2.7 in (Wainwright, 2019) and Theorem 3.3 in this paper? I think it is better to clarify this question in the paper, then the reader can quickly understand theorems and proofs.\n2, What is the difference between the $\\tilde{\\mathbb{G}}(\\lambda_n)$ defined in this paper and $\\mathbb{G}(\\lambda_n)$ defined in  (Wainwright, 2019)? Why not use the original definition of $\\mathbb{G}(\\lambda_n)$ in  (Wainwright, 2019)?\n3, The first example is corrected linear regression. Why corrected linear regression model is non-convex and why do we need to enforce the constraint for parameter $\\theta$?", "other_comments_or_suggestions": "No", "questions_for_authors": "See the Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CfRWfTY22k", "reviewer": "Reviewer_RMP7", "summary": "This paper develops a theoretical framework for analyzing regularized M-estimators with decomposable regularizers. Extending prior work in convex settings, the authors establish that estimation errors remain in a restricted set and that convergence rates can be recovered despite the loss function's nonconvexity.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1, The paper can benefit from a brief discussion on potential algorithmic implementations based on the theoretical results.\n\nThanks for the question. Our theoretical results show that the decomposable regularizers play the key role in facilitating convergence and improving generalization. So, it is important to develop the regularizers for the potential algorithmic implementations.\n\n2, Are there any specific classes of nonconvex loss functions where your framework does not apply? How sensitive are the key theoretical results to violations of the decomposability assumption?\n\nThanks for the question. Our framework applies to a broad class of nonconvex loss functions; however, we require that the nonconvex loss satifies the dual norm bound. If the nonconvex loss does not satisfy the dual norm bound, our results do not hold. The decomposability assumption plays a crucial role in our results. If this assumption is violated, the key bounds and statistical guarantees may no longer hold.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This paper is close to Wainwright (2019) and Loh & Wainwright (2015).", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Provides a significant theoretical extension from convex to nonconvex settings. Uses rigorous mathematical analysis to establish key results. Well-structured and clearly written, making the contributions accessible. Offers practical examples to illustrate the main theoretical findings. I think there is no significant weakness.", "other_comments_or_suggestions": "The paper can benefit from a brief discussion on potential algorithmic implementations based on the theoretical results.", "questions_for_authors": "Are there any specific classes of nonconvex loss functions where your framework does not apply? \nHow sensitive are the key theoretical results to violations of the decomposability assumption?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BkOebEWosX", "reviewer": "Reviewer_UkML", "summary": "This paper studies the theoretical properties of regularized M-estimators with decomposable regularizers under nonconvex loss functions. The authors extend existing results on convex regularized M-estimators to the nonconvex case, demonstrating that estimation errors remain within a restricted set and that convergence rates can still be recovered. They establish key theoretical guarantees, leveraging restricted strong convexity and decomposability conditions. The theoretical results are further supported by two concrete applications: corrected linear regression and the Lasso estimator under nonconvex loss functions. The findings significantly contribute to the understanding of high-dimensional statistical estimation in nonconvex settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Can you comment on whether your results extend to more general forms of nonconvexity beyond those studied in the examples?\n\nThanks for the question. Our framework applies to a broad class of nonconvex loss functions; however, we require that the nonconvex loss satifies the dual norm bound.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I have checked the theories and found no errors.", "experimental_designs_or_analyses": "No experiment", "relation_to_broader_scientific_literature": "This work extends foundational results in high-dimensional statistics, particularly those of Negahban et al. (2009), Wainwright (2019), and Loh & Wainwright (2015). While these prior works focused on convex regularized M-estimators, the present paper generalizes the theory to nonconvex loss functions.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths\n-Theoretical novelty: Extends convex M-estimator results to the nonconvex setting.\n-Strong mathematical foundations: Proofs are detailed and rigorous.\n-Relevance: The results have broad applications in high-dimensional statistics.\n-Clarity: The paper is well-structured and clearly presents key results.\n\nWeaknesses\n-Theoretical focus: Lacks empirical validation, though this is not necessarily a major drawback given the paper's aims. -Assumptions: Some assumptions (e.g., decomposability, restricted strong convexity) may not always hold in practical settings, limiting applicability to certain problems.", "other_comments_or_suggestions": "NO", "questions_for_authors": "-Can you comment on whether your results extend to more general forms of nonconvexity beyond those studied in the examples?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zN16fKjyQa", "reviewer": "Reviewer_p2mm", "summary": "This paper challenges the results of Section 9 of Martin's textbook \"High-dimensional statistics\". Surprisingly, this paper is able to recover the results of Proposition 9.13 and Theorem 9.19 of \"High-dimensional statistics\" for nonconvex loss functions. Moreover, Theorem 3.3 in this paper extends the results of Theorem 1 in Po-Ling's nonconvex m-estimators work to the general norms. They also consider the corrected linear regression and l1-penalized Lasso estimator as two nonconvex samples", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "-Can we consider the other distributions for corrected linear regression?\n\nThanks for the question. (Rosenbaum & Tsybakov, 2010; Loh & Wainwright, 2012) have already studied the corrected linear regression, and they consider the sub-Gaussian parameters. This paper just follow them to use the exiting non-convex eample to illustrate our theory. It is interesting to consider the parameters that follow other distributions. But it is out of the scope of this paper.\n\n\n-Can we use the DNN as the example?\n\nThanks for the question. We have tried DNN as an example. Unfortunately, DNN do not satifies the dual norm bound. Therefore, we can not apply our theory to DNN. One interesting future direction is to study the non-convex theory that can be applied to DNN.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have read the proof of this paper, and believe there are correct.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "1. Based on the definitions of stationary points (9), RSC condition(10) and $\\tilde{\\mathbb{G}}(\\lambda_n)$, Theorem 3.1 in this manuscript recovers the results of Proposition 9.13 of Martin's textbook for any stationary points. Theorem 3.3 in this manuscript is an important result. Because they recover the convergence rate of Theorem 9.19 of Martin's textbook for any stationary points, and improve the Po-Ling's nonconvex results to any norms. Theorem 4.2 also recovers the previous results. Theorems 3.1 and 3.3 are quite novel and of significant to the community due to the importance of nonconvex research.\n\n2. Theorem 4.2 only deals with the sub-Gaussian parameters which may be a weakness of this paper. The DNN is the popular nonconvex structure, but the examples section did not present the DNN case.", "other_comments_or_suggestions": "NA", "questions_for_authors": "-Can we consider the other distributions for corrected linear regression?\n-Can we use the DNN as the example?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission studies the nonconvex theory of M-estimator through decomposable regularizers. The key point that the authors take a step forward in this area is extending the assumption of the convexity of the loss function to the high-dimensional non-convex. The authors provide several principled insights behind this relaxation.

This submission received the comments of four reviewers, who respectively recommended 5, 3, 3, 4. After the rebuttal, two reviewers confirmed the authors' feedback while the other two reviewers only acknowledged without further comments. AC has checked the review and the comments and feel some comments are too short and fall out of consideration. But based on the detailed review of the first reviewer and the last reviewer, AC feel at least there are no negative problems about this submission.

In this case, based on the valid reviewers' suggestion, AC tend to recommend "Acceptance" towards this submission.
Decision: Accept (poster)