Learning Sparse Visual Representations with Leaky Capped Norm Regularizers
Jianqiao Wangni∗

arXiv:1711.02857v1 [cs.LG] 8 Nov 2017

Tsinghua University
Beijing, China
zjnqha@gmail.com

Abstract
Sparsity inducing regularization is an important part for
learning over-complete visual representations. Despite the
popularity of `1 regularization, in this paper, we investigate the usage of non-convex regularizations in this problem. Our contribution consists of three parts. First, we propose the leaky capped norm regularization (LCNR), which
allows model weights below a certain threshold to be regularized more strongly as opposed to those above, therefore
imposes strong sparsity and only introduces controllable estimation bias. We propose a majorization-minimization algorithm to optimize the joint objective function. Second, our
study over monocular 3D shape recovery and neural networks
with LCNR outperforms `1 and other non-convex regularizations, achieving state-of-the-art performance and faster convergence. Third, we prove a theoretical global convergence
speed on the 3D recovery problem. To the best of our knowledge, this is the first convergence analysis of the 3D recovery
problem.

Introduction
The sparse models have been widely applied in machine
learning and computer vision tasks. To encourage sparsity,
the `1 norm is widely adopted as a regularizer, which can
produce reasonable results in various cases. For an example,
to analyse the 3D shape of an object, from a monocular 2D
camera, one can build a dictionary of 3D shape bases from
datasets, and inference the sparse combination weights of
the bases (Zhou et al. 2016). Yet, a number of studies suggested that it is not always the optimal choice, non-convex
regularizers can often lead to better balance between sparsity and accuracy in practice. Particularly, a number of nonconvex regularizers have been explored in previous work,
such as `p norm (Frank et al. 1993), MCP (Zhang 2010a),
SCAD (Fan and Li 2011), Logarithm (Friedman 2012), and
capped norm (Zhang 2010b)(Zhang and others 2013). However, the studied models are mostly restricted to be convex
ones, therefore lack suitability to larger application scope.
This is reasonable since, first, the convex problem with
non-convex regularizers are already difficult to analyse, the
global optima can only be obtained with additional statistical assumptions. The non-convex problem, even without
∗
This work was done when the first author was a visiting research assistant at CUHK.

Dahua Lin

The Chinese University of Hong Kong
Hong Kong, China
dhlin@ie.cuhk.edu.hk

regularizers, is much more difficult to optimize, the solver
for non-convex will converges much slower comparing to
when it applies to convex ones.
In this work, we will concentrate on the learning better
sparse models, with considerations on the running time limitation, which commonly exists, especially in testing stage.
For an example, the aforementioned 3D shape recovery
models have achieved good enough accuracy, but they converge too slow for real-time applications. Although directly
enlarging the `1 regularizer will force more small weights
to be zeros within limited time, but this will certainly compromise the accuracy since the larger and effective weights
are also penalized strongly. In this work, we aim to move
beyond the limitations of existing literatures and develop a
novel regularizer that can achieve high sparsity and high accuracy in learning sparse representations (like other successful applications based on non-convex regularizers), The key
to achieve this goal is to force more smaller weights to zeros by a stronger regularization, but not so far as to leading
larger weights deviating from the ground truth. Following
this idea, we propose a novel non-convex regularizer, called
Leaky Capped Norm, which is a generalization of the capped
norms, but enjoys nice mathematical properties and demonstrates higher performance in experiments. We also derive a
doubly majorization-minimization algorithm, which is suitable for both convex and nonconvex loss functions. We also
take the 3D shape recovery problem for detailed analysis.
By relaxing the objective to a convex one, we can apply
an ADMM solver and get a theoretical global convergence.
We also conducted experiments on sparse neural networks
to show the efficiency in compressing kernel weights.

Leaky Capped `1 Norm
A standard sparse model consists of a loss function L (which
we assume to be differentiable but possibly nonconvex) and
a regularization part H on the weights c
1 X
min
L(xn , c) + H(c).
(1)
c N
n
where {xn } are data points. A popular choice for H is the
`1 norm, due to its convinience for optimization and that it
is good surrogate for `0 norm. There are also some literatures suggesting that the `1 norm is in many case inferior

to non-convex norms for inducing sparsity. To motivate our
new regularizer, we begin with a discussion on the representative capped `1 norm (Zhang 2010b):
X
H(c) = α
min(|ci |, τ ), where α, τ > 0.
(2)
i

As shown in Figure 1, this formulation only regularizes
those weights that are below a certain threshold τ . For those
beyond this value, they can grow arbitrarily without experiencing penalties. It is noteworthy that it is a generalization
of `1 norm. Particularly, it becomes `1 as τ → ∞. Generally, with a finite τ , it approximates `0 better than `1 , and
therefore leads to higher sparsity in some real-world applications. The key feature of capped norm is the lack of penalty

A representative optimization algorithm for solving convex problems with nonconvex regularizer is the multistage algorithm (Zhang 2010b), it is guaranteed to converge
since it is essentially a special case of the majorizationminimization (MM) algorithm (Hunter and Lange 2004). To
be more specific, at the (l + 1)-th stage, the surrogate objective is
H l+1 (c) = |cT | · λl , where λli = αI(|cli | ≤ τ ) + βI(|cli | > τ ),
where cl is the optimal c at the l-th stage, but the surrogate
loss remains the same as original one. We set the initialization parameter λ0i = β, so as to begin with a light regularization for all weights. Based on the algorithm, one can see
that the parameter selection is simpler - one can first search
β for accuracy and then α for sparsity.

Monocular 3D Shape Recovery
Now we proceed to demonstrating the usage of the proposed
regularizer and algorithms for solving a computer vision
problem, the 3D shape analysis of visual objects. Driven
by the demands arising from real-world applications, 3D
Figure 1: Geometric view of three kinds of norms.
shape recovery from 2D images has received increasing atfor weights whose magnitudes are greater than τ , this featention from the computer vision community in recent years.
ture, however, may become a drawback under some circumA key challenge of this task lies in the fact that different
stances. For examples, in our empirical study on 3D shape
3D shapes can be projected to the same 2D image, resultrecovery, which is introduced later, the capped norm leads
ing in an ill-posed problem. A commonly adopted approach
to unstable optimization procedures and substantially worse
is to restrict the recovered 3D shape to be a linear comsolutions, by the multi-stage algorithm introduced later. Anbination of a set predefined shape bases. A representative
other difficulty shared by both `1 and capped `1 norms is the
model in early ages along this line is the Active Shape Model
parameters selection – it is often very tricky to find a good
(ASM)(Cootes et al. 1995), which relies on a dense combivalue of τ and α that well balances between accuracy and
nation for shape representation. Later advances, like (Hejrati
sparsity. From an optimization perspective, the two parameand Ramanan 2012)(Zia et al. 2013)(Wang et al. 2014))(Xiters are both critical to the most common proximal operator,
ang and Savarese 2012)(Ramakrishna, Kanade, and Sheikh
as
2012)(Lin et al. 2014)however, shows that sparse representation is more effective in real-world applications, of1
arg min ||x − c||2 + H(x) = sign(c) max(|c| − I(c < τ )α, 0), ten demonstrating stronger generalization performance and
x 2
higher robustness against adverse conditions.
where I(·) is the indicator function that equals to one for
The 3D shape, i.e. the 3D locations of p landmarks are
truth and zero for false. As implied by theoretical analystacked as S ∈ R3×p , and its corresponding 2D shape is Y ∈
sis and shown in our experiments, larger values of α and τ
R2×p . We denote the projection matrix as Π. The Active
would yield sparser solutions, but at the same time damage
Shape Models (ASM) (Cootes et al. 1995) proposed training
the larger weights and consequently compromise the accua group of shape bases {Bi }D
i=1 from data by methods like
racy. With the analysis above in mind, we propose the Leaky
principal component analysis, denoting D = {1, · · · , D} as
Capped `1 Norm Regularizer (LCNR) as an improved varia set of subscripts and c as weights of each basis. The 3D-2D
ant:
shape relation is characterized as
X
X
X
H(c) = α
min(|ci |, τ ) + β
max(|ci |, τ ),
(3)
S=
ci Bi , Y = ΠS,
i

i

where 0 < β < α. As shown in Figure 1, the function of
LCNR is piecewise linear and thus is differentiable (except
at a few points). The key difference between the proposed
formulation and the standard `1 norm and the capped norm
is that large weights (i.e. those greater than τ ) are still penalized positively but less heavily. To be more specific, this
generalizes the capped `1 norm, with an additional coefficient β to control how much those large weights are regularized. In particular, when β = 0, it reduces to the regular
capped norm.

where Π =



i∈D

ω
0

0
ω



0
, c ∈ RD , Bi ∈ R3×p
0

(4)

here ω is a parameter depending on physical factors like focal length and view depth. In the test phase, the 2D shape
Y is annotated by regular visual detectors, since the shape
bases B are most likely predefined in a different camera setting other than the test setting, the unknown factors including combination weights c, a relative rotation parameter R
and a translation parameter T should all be considered in the

projection model,
X
Y = Π(R
ci Bi + T ), where R ∈ SO(3), T ∈ R3 (5)
i∈D

where I3 ∈ R3×3 is an identity matrix and SO(3) = {R ∈
R3×3 | RT R = I3 , det(R) = 1}. In addition, (Zhou
et al. 2016) proposed distributing individual rotation matrix Ri ∈ R3×3 to eachPbasis, then the 3D and 2D shapes
are represented as =
i∈D ci Ri Bi . They substitute the
bilinear term composed of Π and R by uniform variables
{Mi ∈ R2×3 }i∈D , that Mi = ci ΠRi which implicitly take
rotation and projection factors into account. Denoting M as
a 3 dimensional tensor stacking {Mi }D
i=1 , we rewrite the objective as
X
1
min F (M, c) = ||Y −
Mi Bi ||2F + H(c), (6)
2
Ri ∈Ω(ci ),c
i∈D

where Ω(ci ) = {Mi ∈ R2×3 |MiT Mi = c2i I2 },

and H(c) is the regularization and I2 ∈ R2×2 is an identity
matrix. In our model of 3D shape recovery, we adopt the
linear formulation as Eq.(6) since it is the best baseline up
until now and has some attractive properties. Our objective
function is same with Eq.(6), H(c) is set to be LCNR as
Eq.(3). The objective with a stage-wise surrogate regularizer
is
X
X
1
Mi Bi ||2F +
λli |ci |,
(7)
F l+1 (M, c) = ||Y −
2
i∈D

i∈D

in the (l + 1)-th stage, where Mi ∈ Ω(ci ). In this optimizer,
the regularization part of F (R, c) is convex in each stage,
however, the surrogate function is still non-convex since
there is an orthogonality constraint on each Mi . To build
the upper bounding function, we make a convex relaxation
on the constraints. As the spectral-norm ball conv(Ω(ci )) =
{X ∈ R2×3 | ||X||2 ≤ ci }, is the tightest convex hull of
the Stiefel manifold Ω(ci ) (Zhou et al. 2016) [(Journée et
al. 2010), Section 3.4], where || · ||2 represents the spectral
norm, which is its largest singular value. Finally, by relaxing
the domain Ω to conv(Ω), and the recalibration rule of λi is
transferred to λli = αI(||M̂il ||2 ≤ τ ) + βI(||M̂il ||2 > τ ),
where M̂il is the optimal Mi in the l-th stage.
Since the function is convexified, We employ the alternate direction method of multiplier (ADMM) (Boyd et al.
2011)(Zhou et al. 2016) algorithm to attain high-precision
solutions. We introduce a tensor V as a copy of M , U as
a dual tensor variable and µ as a stepsize parameter, then
rewrite Eq.(7) in its augmented Lagrangian formulation
X
X
1
Vi Bi ||2F +
λli ||Mi ||2
Fµl+1 (M, V, U ) = ||Y −
2
i∈D
i∈D
X
µX
T
+
Ui (Mi − Vi ) +
||Mi − Vi ||2 (8)
2
i∈D

i∈D

Then the ADMM procedure is applied to solve the subproblem. After the convergence, the multi-stage solver will update the surrogate functions. We denote the inner-iteration

superscript as t. Then M t+1 is update based on the proximal operator on spectral norms [(Parikh, Boyd, and others
2014), Section 6.7.2],
proxλ (Vi0 ) = P diag[σ − λ0i P1 (σ/λ0i )]QT ,

(9)

where Vi0 = Vit − Uit /µ and λ0i = λli /µ. Denoting the solution as proxλ0i (Vi0 ), Vi0 = P diag(σ)QT is the singular
value decomposition of Vi0 , and P1 (·) is the Euclidean projection onto the `1 norm ball. The update on V and U have
closed form solutions,
Vit+1 = (Y BiT + µMit+1 + Uit+1 )(Bi BiT + µI3 )−1 , (10)
Uit+1 = Uit + µ(Mit − Vit ). (11)
The convergence property of this algorithm is well studied in
(Boyd et al. 2011), additionally, we adopt an adaptive policy
for stepsize µ as suggested by [(Boyd et al. 2011), Section
3].

Theoretical Analysis
Generally speaking, the convergence of optimization over
non-convex function is typical hard to prove without a decreasing step size. When combined with nonconvex regularizers, even convex problems need highly specialized proofs,
for each problem. One may see the hardness of by referring to literatures, on the theoretical analysis of capped
norm in different applications, e.g., multi-task feature learning (Gong, Ye, and Zhang 2012)(Tang, Nie, and Jain 2016),
matrix completion (Gao et al. 2015) and (Jiang, Nie, and
Huang 2015)(Sun, Xiang, and Ye 2013)(Han and Zhang
2016)(Zhang 2010b)(Zhang and others 2013). The proof is
harder for our problem since the loss function is already nonconvex. In this section, we theoretically prove that with a
high probability, the recovery error of our multi-stage algorithm decreases at nearly exponential speed against stages.
We assume that the ground truth of the 2D shape Ȳ ∈ R2×p
is expressed as a projection P
of the combined deformation
of 3D shape bases, as Ȳ = i∈D M̄i Bi , where M̄i is the
ground truth of deformation matrix Mi , for 0 ≤ i ≤ D. The
observation model is Y = Ȳ + δ, where δ ∈ R2×p is a
Gaussian noise, i.e. δjk ∼ N (0, σ 2 ). For notational simplicity, we also set γ = α + β.
Assumption 1 For any matrix Mi ∈ Rn×m , we assume that
there exist a constant κi that
κi =

min ||Z − Mi Bi ||F /||Mi ||? > 0,

Mi ∈R(s)

(12)

where the restricted set R(s) is defined as R(s) = {X ∈
Rn×m | rank(X) ≤ s}.

Remark 1 This is the widely used eigenvalue assumption
which can be found in (Lounici et al. 2009).
Theorem 2 Following the common setting of sparse dictionary learning, we assume
each basis Bi are normalized
P that
2
by row `2 norm that k Birk
= φ for all i ∈ D, 1 ≤ r ≤ 3,
2×3
where φ is an constant. For the optimal matrix
√ M̂i ∈ R
in any stage, if we set α, β as (α + β) ≥ φ 3 + e/2, then it

holds
X
X
1
1
||Ȳ −
M̂i Bi ||2F ≤ ||Ȳ −
Mi Bi ||2F
2
2
i∈D
i∈D
X
l
+
(4γ + λi )||Mi − M̂i ||2 ,

(13)

i∈D

with the probability of at least 1 − 2D exp(− 12 (e − 3 ln(1 +
e/3))), where e is a positive scalar.
Proof. Recalling that Y = Ȳ +δ and the property of optimal
point M̂i , then we have
X
X
1
1
||Ȳ −
M̂i Bi ||2F ≤ ||Ȳ −
Mi Bi ||2F (14)
2
2
i∈D
i∈D
X
X
l
+
λi ||Mi − M̂i ||2 +
tr[(Mi − M̂i )Bi δ T ], (15)
i∈D

i∈D

where we use the triangular inequality of spectral norm
||Mi ||2 − ||M̂i ||2 ≤ ||Mi − M̂i ||2 .

(16)

We first establish the upper bound of tr[(M̂i − Mi )Bi δ T ].
We denote a set of random events {Aij } and define a set of
random variables {vijr } as
p

Aij =

{||BiT δj ||2

≤ φγ},

vijr

1X
Birk δjk , (17)
=
φ
k=1

where Birk is the element in the r-th row and k-th column of
Bi . Since Bi is normalized, vijr are i.i.d. Gaussian variables
P3
2
following N (0, 1). Then we can verify that r=1 vijr
is a
chi-squared random variable with d = 3 degree of freedom.
By choosing λ according to Theorem 2, we have
p
3 X
X
1
Birk δjk )2 > 4γ 2 )
P r( ||Bi δjT ||2 > γ) = P r( (
2
r=1
k=1

≤ P r(

3
X

1
2
vijr
> 3 + e) ≤ exp(− θ(e)), (18)
2
r=1

where θ(e) = e − 3 ln(1 + e/3) and the second inequality
is due to the chi-squared distribution (Chen, Zhou, and Ye
T D T2
2011). Denoting A = i=1 j=1 Aij , we also denote Ac
as its complementary set and |A| as its cardinality, then
P r(A) = 1 −

D [
2
[

i=1 j=1

Acij

1
≥ 1 − 2D exp(− θ(e)). (19)
2

Denoting Mir as the r-th row of Mi , we can derive an upper
bound on tr[(M̂i − Mi )Bi δ T ] under the event A,
tr[(Mi − M̂i )Bi δ T ] =
≤

2 X
2
X
r=1 j=1

2 X
2
X
(Mir − M̂ir )T Bi δjT
r=1 j=1

||Mir − M̂ir ||2 ||Bi δjT ||2 ≤ 4γ||Mi − M̂i ||2 , (20)

where we apply the Cauchy-Schwarz inequality and the relation between Frobenius norm and spectral norm. By substituting this back to Eq.(14), we get the proof.

Theorem 3 Let M̂il+1 be the optimal solution at the (l + 1)th stage, and M̂il be the one at the l-th stage accordingly. We
define Wil = M̄i − M̂il , and a function L on set S ⊆ D.
If we choose α, β as in Theorem 1 and choose τ as τ >
(α + β)/κ2 , the following inequality stands
sX
b
l
Ll+1 (D) ≤ a L0 (D) +
, where Ll (S) =
||Wil ||22 ,
1−a
i∈S

with probability of at least 1 −
− 3 ln(1 +
e/3))),
where
a
=
(α
+
β)/(κ
τ
),
and
b
= 5(α +
√
2
β) D/(κ τ ).
2D exp(− 21 (e
2

Proof . We apply Theorem 2 in stage (l+1) and substitute
M by its ground truth M̄ , then get
X
X
1
||Ȳ −
M̂il+1 Bi ||2F ≤
(4γ + λli )||Wil+1 ||2 , (21)
2
i∈D
i∈D
P
where we use Ȳ = i∈D M̄i Bi . We define a set G = {i ∈
D | ||M̂il ||2 ≤ τ } to separate the weights, and
αil = αI(i ∈ G),

βil = βI(i ∈ G c ),

(22)

then there is λli = αil + βil . Then we establish a bound by
Cauchy-Schwarz inequality,
X
X
(λli + 4γ)||Wil+1 ||2 =
(αil + βil + 4γ)||Wil+1 ||2
i∈D

i∈D

√

≤ (4γ D + α

p
p
|G| + β |G c |)Ll+1 (D). (23)

To further bound this term, we first denote that

E = {i ∈ D | ||M̄i ||2 6= 0}, F = {i ∈ D | ||M̄i ||2 ≤ 2τ }, (24)
by the rule of set operation and the definition of G and F,

|G| = |G ∩ F| + |G ∩ F c |, where |G ∩ F| ≤ |F |, (25)
X
||M̄i − M̂il ||22 ≤ L2l (G ∩ F c ); (26)
τ 2 |G ∩ F c | ≤
i∈G∩F c

by the inequality ||M̄i − M̂il ||2 ≥ ||M̄i ||2 − ||M̂il ||2 ≥ τ .
Substituting them back to Eq.(23), we get
q
X
αil ||Wil+1 ||2 ≤ α |F| + L2l (F c )/τ 2 Ll+1 (D) (27)
i∈D

p

α
Ll (F c ))Ll+1 (D), (28)
τ
√
where in the last inequality we use a2 + b2 ≤ a + b for
a, b ≥ 0. A similar result holds for another part of Eq.(23)
as
X
p
β
βil ||Wil+1 ||2 ≤ (β |E| + Ll (E c ))Ll+1 (D). (29)
τ
≤ (α

|F| +

i∈D

Substituting them back to Eq.(21), there is
X
X
1
||Ȳ −
M̂il+1 Bi ||2F ≤
(4γ + λli )||Wil+1 ||2
2
i∈D
i∈D
p
√
1
≤ γ(4 D + max(|E|, |F|) + Ll (D))Ll+1 (D), (30)
τ

Recalling Assumption 1 and substituting Z = M̄i Bi , then
1
||Wil+1 Bi ||2F ,
(31)
2
where we use ||X||F ≤ ||X||2 . Denoting κ = mini κi , then
X
X
X
2κ2
||Wil+1 ||22 ≤
||Wil+1 Bi ||2F ≤ ||
Wil+1 Bi ||2F .
κ2i ||Wil+1 ||22 ≤ κ2i ||Wil+1 ||2? ≤

i∈D

i∈D

i∈D

Substituting this to Eq.(21) and combining for i ∈ D, there
is
√
1
κ2 L2l+1 (D) ≤ (α + β)(5 D + Ll (D))Ll+1 (D). (32)
τ
where we apply max(|E|, |F|) ≤ D. Recalling the definition
of a and b, we obtain
1 − al+1
(33)
1−a
by the pre-setting 0 < a < 1, we obtain the main theorem.
Ll+1 (D) ≤ aLl (D) + b ≤ al+1 L0 (D) + b

Remark 2 Theorem 3 establishes the global convergence
property of the estimation error in terms of a sum of spectral norms, and further implies that the value of Ll (D) is
decaying exponentially after l stages, and the algorithm is
less sensitive to the initial values.

Sparse Neural Networks
The convolutional neural networks (CNN) are powerful models for learning visual patterns from raw images.Generally speaking, the practical networks have too
many parameters to fit in mobile devices or on-chip. The
pursuit of neural networks with fewer parameters draw a
lot of attentions, dating back to many years ago (LeCun,
Denker, and Solla 1990)(Hassibi, Stork, and others 1993).
Although recent advances showed that with a trained network as a warm start, a network can be highly compressed.
But their experiments are mostly done on networks with
large FC layers and many redundant parameters. We will
explore the potential of compressing model weights by directly introducing the sparse regularizer to the loss functions, with a small and compact network, without any warm
start, purely optimizing a regularized function.
For a CNN, denoting an input features map of height h,
width w, and channels ci , as I ∈ Rh×w×ci , the convolutional kernel K is in shape size of s and with co output channels, then K ∈ Rs×s×m×co .

due to the ReLU layers and max-pooling layers, we can calculate the proximal steps based on the subgradient, which is
obtained by back-propagation. Since the weights across different layers are with significantly different statistics, we put
separate regularizer on each layer, with independent threshold and coefficient, to induce sparsity of different degrees.
For neural networks, the data samples are much more than
3D recovery, for the multi-stage algorithm, the local optimal point can not be accessed assuredly, even with a convex
regularizer. Therefore, we proposed a doubly majorizationminimization, which is practical to implement. The algorithm is based on the multi-stage, gradually calibrating the
regularizer into regular `1 regularizers in each stage. While
in each stage, the solver is not required to reach the local optima. The algorithm builds another (stochastic) upper
bounding function g(c, cl,t−1 , St ) for the stage-wise surrogate function L(c) + H l (c), based on the stage-wise initializer point cl,0 and the given subset St . For a smooth objective, g(c, cl,t−1 , St ) can be set to be the following proximal
function,
1 X
g(c, cl,t−1 , St ) =
[L(xn , cl,t−1 )
|St |
n∈St

+ ∇L(xn , cl,t−1 )T (c − cl,t−1 )] +

1
||c − cl,t−1 ||2 .
2η

where St is the selected subset of dataset in the t-th step, and
1/η can be set to the smoothness parameter (if exists). Minimizing the above function can be attained by taking a proximal gradient step, cl,t ← proxH (cl,t−1 − η∇L(xn , cl,t−1 )).
Algorithm 1 (Stochastic) Doubly MM Algorithms
0
0
Input {xn }N
n=1 . Initialize λi = β, l = 0, H = β|c|.
repeat
Update λl+1
as Eq.(4), and set l = l + 1.
i
repeat Solve minc g(c, cl,t−1 , St ) + H l (c) on minibatch Sk using proximal gradient descent.
until Converge

Experiments
Sparse Linear Regression

We implement a sparse linear regression model, for testing the effect of LCNR in inducing sparsity. The dataset
ci X
s X
s
X
is constructed as following, matrix X ∈ RD×N stacks
O(y, x, j) = σ[
K(u, v, i, j)I(y + u − 1, x + v − 1)] N = 1000 random variables of D = 256 dimensions, drew
u
v
i
from a Gaussian distribution, most elements of ground truth
weights w̄ ∈ RD are zero, the others are drew from the
where σ is a nonlinear function like ReLU. We use y to repGaussian distribution, the target vector Y ∈ R1×N is obresent the labels, and denote K as the convolution kernels,
tained by Y = w̄T X plus a Gaussian noise δ. The objective
then the objective function is written as
function is to minimize the 12 ||Y − wT X||2F + H(w), where
N
X
1 X
we set H(w) to leaky capped `1 norm, or regular `1 norm as
L(F(In , K), yn ) +
H(K).
(34)
min
a baseline. We use the multi-stage algorithm, which repeatK N
n=1
edly takes gradient descent step and a proximal step. We set
where L is the loss function, F(In , K) is the output of netthe maximal inner-iterations to be 20 per stage, and 50 stages
work parameterized by K, and H(K) is the LCNR menin total as it converges well. We searched the regularization
tioned earlier. Although the objective is mostly non-smooth
parameters and stepsize that perform best for problem, while

GT

GT

GT

GT

GT

GT

GT

GT

LCNR

LCNR

LCNR

LCNR

LCNR

LCNR

LCNR

LCNR

L1

L1

L1

L1

L1

L1

L1

L1

Capped L1 Capped L1 Capped L1 Capped L1 Capped L1 Capped L1 Capped L1 Capped L1

Figure 2: Performance under different measure. Black: β =
100.0, red: β = 10.0, green: β = 1.0, blue: β = 0.1. (1)
the distance from current estimation to the ground truth
as ||wt − w̄||F , (2) the error of linear regression as ||Y −
X T wt ||F , (3) the ratio of `1 /`2 norm, as ||w||1 /||w||2 , (4)
the nonzero rate as E[I(wit 6= 0)].
not introducing considerable estimation bias, then, we also
test several near parameters by ×1e − 1. For the LCNR, we
set α/β = 300.
We denote wt as the estimated weights in t-th stage. We
measure the performance by four standards. The statistic
numbers change against every stage is plotted in Figure.(2).
As we see from the figure, the proposed model with LCNR
converges to the ground truth with faster speed, achieving
higher accuracy, and yields much sparser solutions than the
`1 norm.

Human 3D Shape Recovery
We conducted the expriments to verify the effectiveness of
leaky capped `1 regularization in learning sparse weights for
3D shape recovery. Our proposed algorithm is implemented
in MATLAB, based on the code generously provided by
(Zhou et al. 2016). We use the CMU motion capture dataset
(moc ) for both training and testing, thousands of frames
of 3D human shapes are contained within the dataset. The
shapes are annotated by 3D locations of 15 landmarks, as
S ∈ R3×15 , and landmarks are at anatomical joints of human, like head, shoulders, elbows, hips, ankles and etc. The
dataset contains various kinds of action. As there are large
external variations across actions, we take each single action into analysis, but using the same shape dictionary. We
use 300 frames of each action as test set. The rest of frames
are used as training set for building shape dictionary. We set
D = 128 to construct an over-complete dictionary by common sparse coding algorithm with `1 regularization, and the
training data are pre-aligned by the Procrustes method used
in (Ramakrishna, Kanade, and Sheikh 2012). The 2D shapes
for test set are synthesized from the ground truth 3D shapes
at different angles across 360 degrees. The recovery error is
measured by the Frobenius norm ||Ŝ − S||F from the recovered 3D shape Ŝ with the ground truth S. We compare
our method to state-of-the-art algorithm (Zhou et al. 2016)
(which has been extensive compared against other methods
in their paper, like Projected Matching Pursuit (Ramakr-

Logrithm

Logrithm

Logrithm

Logrithm

Logrithm

Logrithm

Logrithm

Logrithm

Laplace

Laplace

Laplace

Laplace

Laplace

Laplace

Laplace

Laplace

Figure 3: Recovery results of different kinds of actions, by
using LCNR and other (non)convex regularizations, and the
ground truth shape (GT) on the top row.
ishna, Kanade, and Sheikh 2012) and the alternating manifold minimization method, and proved superiority, therefore we do not compare others). We conducted experiments
comparing the LCNR with other representative (non)convex
regularizations, including ell1 norm, capped ell1 norm, logarithm norm, and Laplace norm, as
(Convex) `1 : R(c; λ) = λ|c|,
capped-`1 : R(c; λ, τ ) = λ min(|c|, τ ),
λ
logarithm : R(c; γ, λ) =
log(γ|c| + 1),
log(γ + 1)


|c|
Laplace : R(c; λ, γ) = λ 1 − exp(− )
γ

We continue to use the doubly MM algorithm to solve the
models, and the constraint on dictionary coefficients c is
transferred to the spectral norm of 3D shapes {Mi }. The
regularization parameters are grid searched for the best final
performance. The computation complexity of calibrating τ
and λli is considerably smaller than the ADMM parts, the
average running time of this part is about 14% of the overall
time of each iteration.
In Figure.(3), we plot the recovered shapes by LCNR regularized and `1 regularized models, and the ground truth
shapes, within a maximum inference iterations of 200. To
test the performance against large noise, we also add matrix [σ ∗ mean(abs(S)) ∗ randn(size(S))] to each 3D shape
S before generating the 2D observation Y . Due to the limited space, we put the results in appendix. The mean errors
for the testing frames of different action types decreasing
against stages are shown in Figure.(4). One can see the proposed model reconstruct much more accurate skeletons than
state-of-the-art model. By comparing the convergence rate
in Figure (4), we see that, the non-convex regularizations
generally converge faster than the `1 because they intro-

6.5

6

5.5

5.5

Error

Error

6

5

5

4.5
4

0

2

4

6

8

4.5

10

0

2

4

walk

6

8

10

6

8

10

run

6

6

5.5

Error

Error

5.5
5

5
4.5
4

0

2

4

6

8

4.5

10

0

2

4

jump

climb

6.5

6.5
6

Error

Error

6
5.5
5
4.5

5.5
5

0

2

4

6

8

4.5

10

0

2

4

box

6

8

10

dance

6

6.5
Leaky capped
L1
capped L1
Logrithm
Laplace

6

Error

Error

5.5
5.5

5
5
4.5

Figure 5: Statistics changing over data passes, and each column shows result of one setting. Red: LCNR regularized
CNN, blue: `1 regularized CNN.

0

2

4

6

8

sit

10

4.5

0

2

4

6

8

10

basketball

Figure 4: Convergence of recovery error with different regularizations. (X-axis: stages (for 10 inner iterations)
duce less estimation bias, so a larger coefficient λ can be
adopted for acceleration. The capped norm induces faster
convergence rate within the beginning 30 iterations, however, in the following iterations the estimation error oscillates up and down, indicating an unstable behavior, this indicates that a very sparse solution doesnot benefit the 3D
recovery problem. The `1 regularization can achieve good
estimation at last, but in the beginning the error decreases
very slow, due to the imbalance between accuracy and speed,
but it outperforms capped `1 , indicating that a certain degree of regularization is critical to larger weights. We can
see for most of the actions, LCNR leads to higher recovery
accuracy comparing opponents, achieveing the same accuracy requirement within much lesser time, this improvement
is significant especially to test phase, which is most the case
since training phase only needs accomplished once.

Sparse Neural Networks
We implement a convolutional neural networks, with 5 convolutional layers of 5 × 5 × 16 and 3 × 3 × 32, three pooling
layers of (2, 2), and a softmax loss layer. We use the CIFAR10 dataset. We compare the proposed LCNR with regular `1 norm regularizer. The training mini-batch size is set to
be 128 per iteration, and set the maximum data passes to be
40 rounds. During each data pass, we calculate the nonzero
rate of model weights, the pure loss function value without
the regularizers, and test the accuracy using the testing set.
For the `1 regularizer, we set parameter to be β = λ0 , and
the parameter of LCNR is set according to α = λ0 ∗ 2.0 and
β = λ0 ∗ 0.1, therefore the penalty on larger weights are sig-

nificantly lighter than smaller ones. We grid search λ0 within
10.0 ∗ 2i for i in range from −8 to 0, obtaining the neural
networks with different sparsity. We use the Adam solver for
optimization. The initial learning rate is set to be 0.02. After
each iteration, we additionally perform the proximal gradient steps xl,t = proxηR (xl,t−1 − η∂L(xl,t−1 ), to ensure the
sparsity of convolutional filters. The proximal gradient steps
are like proxηR (x) = sign(x) max(|x| − ηλ, 0), where
is the element-wise product. We plot the loss function values and sparse rates changing over time in Figure.(5) and
the statistics in the final data pass in Table.(1). We jointly
show the results of two methods in similar sparse rate. We
can see that comparing to the `1 regularizer, the proposed
LCNR achieves better sparsity, without damaging much on
the loss function, and boosting the accuracy by about 2%,
for achieving the same sparsity.
Table 1: Performance Statistics (each column shows result
of one setting).
sparse level
level-1
level-2
level-3

method
LCNR
`1
LCNR
`1
LCNR
`1

accuracy
70.9
68.8
69.2
68.3
55.8
53.2

sparsity
55.2
61.6
24.9
36.2
2.3
2.4

loss
0.40
0.43
67.1
76.0
1.18
1.20

Conclusion
In this paper, we present the leaky capped `1 norm regularizer and its multi-stage optimizer. We apply it in monocular 3D shape recovery problem, obtaining an accuracy improvement and acceleration over state-of-the-art algorithm,
and prove its global convergence, the first rigorous analysis
in relevant literatures and non-convex problems. Auxiliary
empirical studies over sparse linear regression and convolutional neural networks show the LCNR improves upon `1
regularization.

Appendix

6.5

6

6
5.5

5.5

Error

Error

To test the performance against large noise, we also add matrix [σ ∗ mean(abs(S)) ∗ randn(size(S))] to each 3D shape
S before generating the 2D projection. Due to the limited
space, we put the results in Figure 6;7;8;9.

5

5

4.5
4

0

2

4

6

8

4.5

10

0

2

4

walk

GT

GT

GT

GT

GT

LCNR

LCNR

LCNR

LCNR

LCNR

LCNR

6

6

5.5

5.5

0

2

4

6

8

4.5

10

0

2

4

jump

L1

L1

L1

Capped L1

Capped L1 Capped L1 Capped L1

L1

6

Capped L1 Capped L1 Capped L1 Capped L1

Logrithm

Logrithm

Logrithm

Logrithm

Logrithm

8

10

5.5

5

5

4.5

4.5

0

2

4

6

8

10

0

2

4
dance

6

Logrithm

6

6

5.5

box

Logrithm

10

6.5

Error

L1

Error

L1

8

climb

6.5

L1

6

5

LCNR
4.5

L1

10

GT

5

LCNR

8

Error

GT

Error

GT

6
run

6.5
Leaky capped
L1
capped L1
Logarithm
Laplace

Logrithm
6

Error

Error

5.5
5.5

5

Laplace

Laplace

Laplace

Laplace

5

Laplace

Laplace

Laplace

Laplace
4.5

0

2

4

6
sit

Figure 6: Recovery results of different kinds of actions, under noise condition σ = 0.15, by using LCNR and other
(non)convex regularizations, and the ground truth shape
(GT) on the top row.

References
[Boyd et al. 2011] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.;
and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends R in Machine Learning 3(1):1–
122.
[Chen, Zhou, and Ye 2011] Chen, J.; Zhou, J.; and Ye, J.
2011. Integrating low-rank and group-sparse structures for
robust multi-task learning. In Proceedings of the 17th ACM
SIGKDD international conference on Knowledge discovery
and data mining, 42–50. ACM.
[Cootes et al. 1995] Cootes, T. F.; Taylor, C. J.; Cooper,
D. H.; and Graham, J. 1995. Active shape models-their
training and application. Computer vision and image understanding 61(1):38–59.
[Fan and Li 2011] Fan, J., and Li, R. 2011. Variable selection via nonconcave penalized likelihood and its oracle
properties. Journal of the American Statistical Association
96(456):1348–1360.
[Frank et al. 1993] Frank, I. E.; Friedman, J. H.; Wold, S.;
Hastie, T.; and Mallows, C. 1993. A statistical view of
some chemometrics regression tools. discussion. author’s reply. Technometrics 35(2):109–148.
[Friedman 2012] Friedman, J. H. 2012. Fast sparse regression and classification. International Journal of Forecasting
28(3):722–738.

8

10

4.5

0

2

4

6

8

10

basketball

Figure 7: Convergence of recovery error under σ = 0.05
noise, with different regularizations. (X-axis: stages (for 10
inner iterations)
[Gao et al. 2015] Gao, H.; Nie, F.; Cai, W.; and Huang, H.
2015. Robust capped norm nonnegative matrix factorization: Capped norm nmf. In Proceedings of the 24th ACM
International on Conference on Information and Knowledge
Management, 871–880. ACM.
[Gong, Ye, and Zhang 2012] Gong, P.; Ye, J.; and Zhang, C.s. 2012. Multi-stage multi-task feature learning. In Advances in Neural Information Processing Systems, 1988–
1996.
[Han and Zhang 2016] Han, L., and Zhang, Y. 2016. Multistage multi-task learning with reduced rank. In AAAI, 1638–
1644.
[Hassibi, Stork, and others 1993] Hassibi, B.; Stork, D. G.;
et al. 1993. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information
processing systems 164–164.
[Hejrati and Ramanan 2012] Hejrati, M., and Ramanan, D.
2012. Analyzing 3d objects in cluttered images. In Advances
in Neural Information Processing Systems, 593–601.
[Hunter and Lange 2004] Hunter, D. R., and Lange, K. 2004.
A tutorial on mm algorithms. The American Statistician
58(1):30–37.
[Jiang, Nie, and Huang 2015] Jiang, W.; Nie, F.; and Huang,
H. 2015. Robust dictionary learning with capped l1-norm.
In IJCAI, 3590–3596.
[Journée et al. 2010] Journée, M.; Nesterov, Y.; Richtárik, P.;
and Sepulchre, R. 2010. Generalized power method for

6.5

6

6.5

6
5.8

6

5

Error

Error

6

Error

Error

5.5
5.5

5.5

5

2

4

6

8

4.5

10

0

2

4

walk

6

8

5

10

0

2

4

run

6

Error

Error

Error

5.5

5

6

8

5

10

5

0

2

4

6

8

10

0

2

4

jump

6

6

5.8

5.8

5.6

5.6

5.4

6

8

5

4

10

6

8

10

6

8

10

6

8

10

5.4
5.2

0

2

4

climb

6.5

2

run

5.2
4.5

0

walk

6

5.5

4.5

5.4
5.2

0

Error

4.5

5.6

6

8

5

10

0

2

4

jump

climb

6.5

6.5

6.5

6

6

6

5.5

Error

Error

Error

Error

6
5.5

5.5

5.5

5

2

4

6

8

5

10

0

2

4

box

6

8

5

10

0

2

4

dance

6

6.5

5.5

Error

8

5.5

2

4

6
sit

8

10

4

Leaky capped
L1
capped L1
Logarithm
Laplace

6

5

0

2

6.2

5

4.5

0

dance

5.5

5

4.5

5

10

6
Leaky capped
L1
capped L1
Logarithm
Laplace

6

Error

6
box

Error

0

Error

4.5

5.8
5.6
5.4

0

2

4

6

8

10

basketball

4.5

0

2

4

6
sit

8

10

5.2

0

2

4

6

8

10

basketball

Figure 8: Convergence of recovery error under σ = 0.15
noise, with different regularizations. (X-axis: stages (for 10
inner iterations)

Figure 9: Convergence of recovery error under σ = 0.25
noise, with different regularizations. (X-axis: stages (for 10
inner iterations)

sparse principal component analysis. Journal of Machine
Learning Research 11(Feb):517–553.
[LeCun, Denker, and Solla 1990] LeCun, Y.; Denker, J. S.;
and Solla, S. A. 1990. Optimal brain damage. In Advances
in neural information processing systems, 598–605.
[Lin et al. 2014] Lin, Y.-L.; Morariu, V. I.; Hsu, W.; and
Davis, L. S. 2014. Jointly optimizing 3d model fitting
and fine-grained classification. In European Conference on
Computer Vision, 466–480. Springer.
[Lounici et al. 2009] Lounici, K.; Pontil, M.; Tsybakov,
A. B.; and De Geer, S. V. 2009. Taking advantage of sparsity
in multi-task learning.
[moc ] Mocap: Carnegie mellon university motion capture
database. http://mocap.cs.cmu.edu.
[Parikh, Boyd, and others 2014] Parikh, N.; Boyd, S. P.; et al.
2014. Proximal algorithms. Foundations and Trends in optimization 1(3):127–239.
[Ramakrishna, Kanade, and Sheikh 2012] Ramakrishna, V.;
Kanade, T.; and Sheikh, Y. 2012. Reconstructing 3d human
pose from 2d image landmarks. In European Conference on
Computer Vision, 573–586. Springer.
[Sun, Xiang, and Ye 2013] Sun, Q.; Xiang, S.; and Ye, J.
2013. Robust principal component analysis via capped
norms. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining,
311–319. ACM.
[Tang, Nie, and Jain 2016] Tang, M.; Nie, F.; and Jain, R.

2016. Capped lp-norm graph embedding for photo clustering. In Proceedings of the 2016 ACM on Multimedia Conference, 431–435. ACM.
[Wang et al. 2014] Wang, C.; Wang, Y.; Lin, Z.; Yuille, A. L.;
and Gao, W. 2014. Robust estimation of 3d human poses
from a single image. In Proceedings of the IEEE Conference
on Computer Vision and Pattern Recognition, 2361–2368.
[Xiang and Savarese 2012] Xiang, Y., and Savarese, S. 2012.
Estimating the aspect layout of object categories. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE
Conference on, 3410–3417. IEEE.
[Zhang and others 2013] Zhang, T., et al. 2013. Multistage convex relaxation for feature selection. Bernoulli
19(5B):2277–2293.
[Zhang 2010a] Zhang, C. 2010a. Nearly unbiased variable
selection under minimax concave penalty. Annals of Statistics 38(2):894–942.
[Zhang 2010b] Zhang, T. 2010b. Analysis of multi-stage
convex relaxation for sparse regularization. Journal of Machine Learning Research 11(Mar):1081–1107.
[Zhou et al. 2016] Zhou, X.; Zhu, M.; Leonardos, S.; and
Daniilidis, K. 2016. Sparse representation for 3d shape estimation: a convex relaxation approach. IEEE Transactions
on Pattern Analysis and Machine Intelligence.
[Zia et al. 2013] Zia, M. Z.; Stark, M.; Schiele, B.; and
Schindler, K. 2013. Detailed 3d representations for object recognition and modeling. IEEE transactions on pattern
analysis and machine intelligence 35(11):2608–2623.

