{'fraction_non_alphanumeric': 0.058934279942732745, 'fraction_numerical': 0.02061228892506227, 'mean_word_length': 3.841435624762628, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 41, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact Penalization at D-Stationary Points of Cardinality- or Rank-Constrained Problem

This paper studies the properties of d-stationary points of the trimmed lasso (Luo et al., 2013, Huang et al., 2015, and Gotoh et al., 2018) and the composite optimization problem with the truncated nuclear norm (Gao and Sun, 2010, and Zhang et al., 2012), which are known as tight relaxations of nonconvex optimization problems that have either cardinality or rank constraints, respectively. First, we extend the trimmed lasso for broader applications and conduct a unified analysis of the property of the generalized trimmed lasso. Next, the equivalence between local optimality and d-stationarity of the generalized trimmed lasso is shown under a suitable assumption. More generally, the equivalence is shown for problems that minimize a function defined by the pointwise minimum of finitely many convex functions. Then, we present new results of the exact penalty at d-stationary points of the generalized trimmed lasso and the problem with the truncated nuclear norm penalty under mild assumptions. Our exact penalty results are not only new, but also intuitive, so that we can see what properties of the problems play a role for establishing the exact penalization. Lastly, it is shown that existing algorithms that yield a d-stationary point always converge to a solution that satisfies the cardinality or rank constraint.


Introduction
Optimization problems that pursue sparsity or low-rank structures of the solutions frequently appear in practice. One of the basic forms comes with the cardinality or rank constraint, which aims at directly constraining the number of non-zero elements of the vector of decision variables or the rank of the matrix, respectively. While such constrained problems have a broad range of applications, they are computationally intractable in general due to their nonconvexity and discontinuity. One of the most popular ways to overcome the intractability is the relaxation of the cardinality and rank with the ℓ 1 norm and nuclear norm, respectively [37,21]. In particular, the former approximation is known as lasso when it applies to least square estimation. In order to reinforce the sparsity of solution, approximations of the ℓ 0 norm such as the ℓ p -approximation with 0 < p < 1, SCAD [11], and MCP [43] have been proposed by employing nonconvex regularizers in place of the ℓ 1 norm. However, their solution does not always satisfy the cardinality since all of those approaches are based on an approximation of the cardinality of the solution vector.
In recent years, nonconvex tight relaxations of the problem with the cardinality constraint and the one with the rank constraint have been proposed [12,44,31,20,14]. In this paper, we focus on the tight relaxations using the trimmed ℓ 1 norm and truncated nuclear norm, which are both nonconvex but continuous functions unlike the cardinality of vector and the rank of matrix. More specifically, we add those functions to the objective function instead of the cardinality constraint and rank constraint so that the trimmed ℓ 1 norm and truncated nuclear norm play a role of a penalty function on the violation of the cardinality constraint and rank constraint, respectively. The former is called the trimmed lasso [31,20,14]. In Yagishita and Gotoh [41], the trimmed lasso has been extended to be applicable to a structured sparsity.
Interestingly, it has been shown that under some conditions the penalty functions defined by the trimmed ℓ 1 norm and truncated nuclear norm can be "exact" for the (structured) sparsity and rank constraints, respectively [7,14,1,6,26,32,2,41,35,30]. Here, by "a penalty function is exact" we mean that a certain kind of solution of the penalized problem satisfies the (structured) sparsity or rank constraint under suitable assumptions. It is noteworthy that the existing results of the exact penalization have been established under strong assumptions which do not seem to be confirmed easily in practice. For example, some statements are only valid at globally optimal solutions, but due to the nonconvexity of the relaxations, it is generally difficult to obtain a guaranteed global optimum in practice. In that sense, the exact penalty result at globally optimal solutions is not practical. In addition, while there are other results valid at stationary points that are attainable by practical algorithms (e.g., those described in Section 5), unfortunately, the problems to which the results can be applied are limited in practice.
To fill the gap between the assumption for exact penalization and practice, we first extend the trimmed lasso for broader applications and refer to it as the generalized trimmed lasso. Since the generalized trimmed lasso includes all existing variations of the trimmed lasso, it enables us to analyze their properties in a unified manner. As will be clear, some results are reinforced by the refinement of the analysis based on this generalization. Next, we derive a sufficient condition for a d-stationary point of the generalized trimmed lasso to be a locally optimal solution so as to associate the following results with local optimality. In addition, a condition is given for a more general class of optimization problems. Then, new results of exact penalization at d-stationary points of the generalized trimmed lasso and the penalized problem by the truncated nuclear norm are presented under mild assumptions. Our results are proven in a different way from the existing ones, leading to intuitive and stronger implications. Finally, we see that with existing algorithms that yield a d-stationary point, it is guaranteed that the obtained solution satisfies the (structured) sparsity or rank constraint.
Contributions of our work are summarized as follows: • For optimization problems with the trimmed ℓ 1 norm, we clarify the class of optimization problems for which locally optimal solutions and d-stationary points are equivalent. Within that class, any dstationary point is proven to be locally optimal. It is noteworthy that while using the information of the second order derivative of objective function is a common strategy, our result does not depend on the second order information and is established despite the inclusion of the nonsmooth regularizers.
• We extend the trimmed lasso for broader applications and conduct a unified analysis of the property. While the existing results of exact penalization for the context we are interested in have been established assuming different conditions in each context, the unified analysis leads us to an essential assumption for the trimmed ℓ 1 norm to be an exact penalization at d-stationary points. Our analysis for the trimmed ℓ 1 norm is extended to the truncated nuclear norm. Our results can apply to the problems for which the exact penalization has not yet been established. In particular, to the best of our knowledge, the exact penalization at d-stationary points for composite problems with the truncated nuclear norm is first presented in this paper. For general nonlinear programming, the exact penalty results at stationary points were given by Demyanov et al. [10] and Cui and Pang [8]. However, due to the generality of nonlinear programming, it is not obvious to check whether the assumption in their results holds for problems we deal with. In addition, the corresponding results of Demyanov et al. [10] and Cui and Pang [8] assumed that the objective function is Lipschitz continuous, but we do not.
• From our exact penalty result, it is shown that existing algorithms converge to a d-stationary point satisfying the (structured) sparsity or rank constraint. Th result fulfills a theoretical gap in the existing studies where exact penalization at globally optimal solutions is demonstrated but only a stationary point can be obtained at most.
The rest of this paper is organized as follows. The remainder of this section is devoted to notation and preliminary results. Section 2 introduces the generalized trimmed lasso and shows an exact penalty result at d-stationary points. Extensions to the exact penalty results for the problem with the truncated nuclear norm and the problems with some additional constraints are shown in Sections 3 and 4, respectively. In Section 5, we summarize existing algorithms for obtaining a d-stationary point and point out that they provide a solution that satisfies the cardinality constraint. Finally, Section 6 concludes the paper with some remarks.

Notation and Preliminaries
For an integer n, the set [n] is defined by [n] := {1, . . . , n}. Let 1 and e i denote the all-ones vector and the vector whose i-th element is 1 and 0 otherwise, respectively. The standard inner product of x, y ∈ R n is denoted by x ⊤ y. The ℓ 1 norm, ℓ 2 norm, and ℓ ∞ norm of x ∈ R n are defined by x ⊤ x, and x ∞ := max i∈[n] |x i |, respectively. For a vector x ∈ R n , x 0 denotes the number of nonzero elements.
Let I denote the identity matrix of appropriate size. By diag(x 1 , . . . , x n ) we denote the diagonal matrix whose i-th diagonal element is x i . The standard inner product of matrices X, Y ∈ R m×n is defined by X •Y := tr(X ⊤ Y ), where tr(Z) is the trace of a square matrix Z. The Hadamard product is denoted by X •Y . The Frobenius norm of X ∈ R m×n is defined by X F := √ X • X. We denote the i-th largest singular value of X ∈ R m×n by σ i (X) for i = 1, . . . , min{m, n}. The smallest nonzero singular value of a nonzero matrix X is denoted by σ min (X). For a matrix X ∈ R m×n , we define X 1 := i∈[m] j∈[n] |X i,j |, X 2 := σ 1 (X), and X * := min{m,n} i=1 σ i (X). Let rank(X) and ker(X) denote the rank and kernel of a matrix X, respectively. The largest eigenvalue of a square matrix X is denoted by λ max (X). The set of symmetric matrices of order n is denoted by S n . For X ∈ S n , X 0 means that X is a positive semidefinite matrix. For a linear subspace L of finite-dimensional inner product space, L ⊥ denotes its orthogonal complement.
The gradient of a function f at a point x is denoted by ∇f (x). The vector ∇ x l f (x) denotes the subvector of ∇f (x) corresponding to x l , where x l is a subvector of x. A continuous differentiable function f on an open Besides, we present some results on the optimization problem: where C ⊂ R n (or C ⊂ R m×n ) is a convex set and F : C → R is directionally differentiable on C, that is, the directional derivative of F at x ∈ C in direction y − x, exists for all x, y ∈ C. Formulation (1) is a more general problem than the ones we will address in the next section and beyond.
We call x * ∈ C a d(irectional)-stationary point of (1) if F ′ (x * ; y − x * ) ≥ 0 holds for all y ∈ C. Obviously, any locally optimal solution of (1) is a d-stationary point of the problem. The converse argument holds under a certain assumption. Under the following lemmas (from Delfour [9] with slight modifications), we will show it.
Lemma 1 (cf. proof of [9,Theorem 4.5,p.130]). Let C ⊂ R n (or C ⊂ R m×n ) be a convex set and f : C → R is convex and directionally differentiable on C. The inequality holds for all x, y ∈ C.
Lemma 2 (cf. [9,Theorem 3.4,p.103]). Let C ⊂ R n (or C ⊂ R m×n ) be a convex set, f i : C → R be directionally differentiable on C for i = 1, ..., M < ∞, and F (x) := min i∈[M] f i (x). For any x, y ∈ C, the directional derivative of F at x ∈ C in direction y − x is given by is continuous, convex, and directionally differentiable on C. If x * ∈ C is a d-stationary point of (1), then x * ∈ C is locally optimal to (1).
Proof. We will derive a contradiction by assuming that x * ∈ C is not a locally optimal solution. From this assumption, there is a sequence holds for any t ≥ t ′ , i ∈ I(x * ), and j / ∈ I(x * ), which implies that I(x t ) ⊂ I(x * ) for t ≥ t ′ . Thus, we have where the second and third inequalities follow from Lemma 1 and the d-stationarity of x * , respectively, and the second equality from Lemma 2. Therefore, x * is a local minimizer of (1).
Proposition 1 ensures that under the assumption any d-stationary point is also locally optimal without information about second order derivatives. Noting that a convex function is continuous and directionally differentiable at the interior points of its domain, it is sufficient to assume only convexity of f i so as to ensure the equivalence especially when C = R n (or C = R m×n ). Thus, roughly speaking, Proposition 1 implies that the d-stationarity and the local optimality are equivalent in the problems that minimize a function defined by the pointwise minimum of finitely many convex functions. The minimization problem we will deal with in the next section has this property.
With this in mind, let us mention the relation to an existing result. Ahn et al. [1,Proposition 2.1] showed that a d-stationary point of (1) must be a local minimizer if C is closed convex and F is given by where G is convex, h i is convex and differentiable, and H is piecewise affine. By Proposition 4.4.6 of Cui and Pang [8], there exist finitely many affine functions {ĥ i } i∈ [M] such that H(x) = max i∈[M]ĥi (x) because H is piecewise affine and convex. As a result, it holds that Since G(x) −ĥ i (x) is convex, we see that Proposition 1 is a generalization of Proposition 2.1 of Ahn et al. [1].

Unconstrained Problem Penalized by Trimmed ℓ 1 Norm
In this section, we introduce a unified framework of trimmed ℓ 1 penalized problem and show the equivalence with the corresponding structured sparsity constrained problem.

Trimmed ℓ 1 Norm
Before describing the formulations, let us start with the key component that plays a significant role in those formulations. For z = (z ⊤ 1 , . . . , z ⊤ m ) ⊤ ∈ R mp with z 1 , . . . , z m ∈ R p , the trimmed group ℓ 1 norm [41] is defined by where K ∈ {0, . . . , m}. It is not hard to see that (2) is equal to the sum of the smallest m − K components of the m-dimensional vector ( z 1 2 , . . . , z m 2 ). Accordingly, the trimmed group ℓ 1 norm with K = 0 is the group ℓ 1 norm, namely, T 0,m,p (z) = m i=1 z i 2 . Note also that when p = 1, the function T K,m,p is known as the trimmed ℓ 1 norm, namely, the sum of the smallest m − K components of a vector (|z 1 |, . . . , |z m |) [31,20,14]. In the following, "group" in the term "trimmed group ℓ 1 norm" is omitted for simplicity.
It is easy to see that T K,m,p (z) ≥ 0 for any z, and that T K,m,p (z) = 0 if and only if ( z 1 2 , . . . , z m 2 ) 0 ≤ K.
These facts motivate us to use the trimmed ℓ 1 norm as a penalty function of the cardinality constraint (3). The idea of using the trimmed ℓ 1 penalty was first utilized by Gotoh et al. [14], whereas the equivalence with the cardinality constraint was pointed out earlier in the proof of a proposition of Hempel and Goulart [16]. In the following, we will use (2) as the penalty function as a surrogate of the corresponding cardinality constraints.
Noting that the function z → i∈Λ z i 2 is directionally differentiable on R mp and Lemma 2, we readily see that T K,m,p is directionally differentiable on R mp . A more specific expression than the one in Lemma 2 of the directional derivative of T K,m,p is given as follows.
Lemma 3 (Yagishita and Gotoh [41,Lemma 3]). Let Λ 1 = {i | z i 2 < z (K) 2 } and Λ 2 = {i | z i 2 = z (K) 2 }. The directional derivative of T K at z ∈ R mp in the direction d ∈ R mp is given by This representation for p = 1 was given by Amir et al. [2,Lemma SM2.6] and later extended to p > 1 by Yagishita and Gotoh [41]. Lemma 3 will be used later in this section to show the equivalence between our proposed formulation and the corresponding structured sparsity constrained problem, both of which will be given below.

Formulation of Generalized Trimmed Lasso
We are now ready to present the formulation to be examined in this paper.
With the trimmed ℓ 1 norm, we consider the following minimization problem, which we refer to as the generalized trimmed lasso: where γ l > 0, c l ∈ R m l p l , and D l = 0 is an m l p l × n l matrix. For simplicity, we ignore the subscripts when L = 1. The first term of the objective function of (4) is usually a loss function for fitting models to some data, and the second term is the sum of penalty functions of the corresponding structured sparsity constraints. The coefficients of the trimmed ℓ 1 penalty terms, γ l 's, look like hyperparameters to take the balance among the first term and the (multiple) trimmed ℓ 1 penalties. As will be discussed later in detail, however, those can be treated as exact penalties under some conditions and may not actually need to be calibrated.
Although the generalized trimmed lasso (4) includes the nonconvex nonsmooth functions, T K l ,m l ,p l , in its objective, we can see that the equivalence between the d-stationarity and the local optimality holds if the first term is convex.
Proposition 2. d-stationary points and local minimizers of (4) are equivalent if f is convex.
As mentioned in the previous subsection, since the trimmed ℓ 1 norm is reduced to the ℓ 1 norm if K = 0, the generalized trimmed lasso (4) is also an extension of the generalized lasso [38,36]. Hence, in addition to Example 1, the generalized trimmed lasso (4) has many applications of trimmed ℓ 1 penalty that have not yet been addressed.
Example 2 (Sparse linear regression with power 1 [2]). For b ∈ R q and A ∈ R q×n be given in the same manner as in Example 1, Amir et al. [2] considered the following sparse regression problem with power 1: While only difference is in the first term of the objective from Example 1, this case satisfied the Lipschitz continuity.
denote, respectively, the binary label and attribute vector of the j-th sample. To conduct the logistic regression with variable selection, Gotoh et al. [14] considered the following problem: The difference from Examples 1 and 2 is only at the first term, called logistic loss, and this case has a Lipschitz gradient and Lipschitz continuity. Lu and Li [27] and Nakayama and Gotoh [32] also treated this problem.
given in the same manner as in Example 3, Gotoh et al. [14] also considered the following problem: The first term, called hinge loss, is Lipschitz continuous but is not differentiable.
Example 5 (Sparse robust regression [32]). Let b ∈ R n2 and A ∈ R n2×n1 be given in the same manner as in Examples 1 and 2, Nakayama and Gotoh [32] considered the following problem: minimize x1∈R n 1 ,x2∈R n 2 While the first trimmed ℓ 1 penalty term is for variable selection, the second trimmed ℓ 1 penalty is for removing the outlying samples. Here, the variable x 2 serves to absorb residuals of outliers.
Example 6 (Minimizing constraints violation). Let b ∈ R n , c ∈ R m and D ∈ R m×n be a surjective matrix. We consider the following problem: Li and Pong [25] dealt with the corresponding cardinality constrained problem.
Example 7 (Estimation of piece-wise linear trend). Let b ∈ R n be a vector of time series data samples. To estimate a piecewise linear function to approximate the data points b 1 , ..., b n , consider the following problem: where D (2,n) ∈ R (n−2)×n denotes the second-order difference matrix defined by The formulation (11) is an extension of ℓ 1 trend filtering [22] by the trimmed ℓ 1 norm.
The above examples are for p = 1 only, but it is natural to extend to p > 1 in each. The network trimmed lasso [41] is such a kind and it pursues both clustering data samples and fitting the models to the samples simultaneously. See Yagishita and Gotoh [41] for more details.
It is a natural question to ask how the relationship between solutions of the generalized trimmed lasso and the following structured sparsity constrained problem: Due to the property explained above (3), any optimal (resp. locally optimal) solution of the generalized trimmed lasso (4) satisfying the constraint (13) is optimal (resp. locally optimal) to the problem (12)- (13). On the other hand, as γ l is larger (while leaving the other components the same), the term (4), and one might expect T K l ,m l ,p l (D l x * l −c l ) = 0 holds for a sufficiently large γ l . In fact, for special cases of generalized trimmed lasso, several studies [14,1,6,32,2,41,30] have derived thresholds γ l such that if γ l > γ l , then any globally optimal (or locally optimal) solution ( , a structured sparse solution satisfying (13) can be obtained by solving the generalized trimmed lasso (4) with γ l > γ l for l ∈ [L]. Such γ l 's are called exact penalty parameters.
Assumptions of the existing results are briefly summarized in Table 1 1 . The weakness of the previous results can be concisely summarized as follows: • Since the trimmed ℓ 1 norm is a nonconvex function (unless K = 0), it is generally difficult to ensure the global optimality in practice, and the implication of obtained solutions for the corresponding cardinality constrained problems would be unclear even when the exact penalty parameters at globally optimal solutions such as in the result [14,6,32,30] are employed.
• At first glance, the propositions in the papers [14,1,32,41] seem to cover a number of cases, but they all assume the "boundedness" of the set of solutions and it is not necessarily fulfilled or difficult to ensure the fulfillment in many cases.
• The convexity of f is assumed in all the existing studies for establishing the exact penalty result at locally optimal solutions.
To mitigate the drawback in the first bullet, we will show the exact penalties at d-stationary points. As for the second and third bullets, we will remove or relax the assumptions. In addition, since it seems difficult to apply the proof approaches used to derive the existing results to the generalized trimmed lasso (4), we will build a novel unified approach for the generalized framework.

Exact Penalties for Generalized Trimmed Lasso
In the remainder of this section, we derive exact penalty parameters at d-stationary points of the generalized trimmed lasso (4) under milder conditions than the existing results. Since our proof does not rely on the convexity of f , we see that the assumption of convexity is not essential in deriving exact penalty parameters at practically attainable solutions (d-stationary points in our analysis) of the generalized lasso (4). In addition, we will see later that our results are stronger than some existing ones, even though the proof is for a more general formulation.
To derive exact penalty parameters for the generalized trimmed lasso (4), we present the following lemma.
corresponding to Λ by (D) Λ , and the positive constant depending on D is defined as follows: We remark that σ K,m,p (I) = σ min (I) = 1.
Lemma 4. Let f be directionally differentiable and (x * 1 , . . . , x * L ) be a d-stationary point of (4). Suppose that the following assumptions hold for l ∈ [L]: Then, holds. When p l = 1, D l = I, c l = 0, and f (x 1 , . . . , x L ) = g(x 1 , . . . , x L ) + l∈[L] η l x l 1 with η l ≥ 0 hold, the left hand side of (14) can be replaced by Proof. To derive a contradiction, we assume that for any d l ∈ R n l because of the d-stationarity of (x * 1 , . . . , x * L ). By Lemma 3, we see that where the third inequality follows from Lemma 6 and the third equality from the definition of σ K l ,m l ,p l . Then, from the positive homogeneity of the directional derivative and the assumption (A2), we have which contradicts the inequality (15).
where the third inequality follows from Lemma 6 and the forth one from the definition of σ K l ,m l ,p l . The contradiction to (15) is derived just as when D l is surjective. Lastly, we consider the case where p l = 1, D l = I, c l = 0, and f (x 1 , . . . , x L ) = g(x 1 , . . . , x L ) + l∈[L] η l x l 1 with η l ≥ 0 hold. We assume that T K l ,n l ,1 (x * l ) > 0. By Lemma 3 and the d-stationarity of (x * 1 , . . . , x * L ), it holds that By this inequality, we obtain that which contradicts the inequality γ l > Γ l .
Note that the assumption (A1) is established whenever c l = 0 or D l is surjective. On the other hand, considering the case where L = 1 and f is differentiable, we have From this, we see that the assumption (A2) can be interpreted as "a boundedness assumption for the gradient of f at stationary points," and is a natural one. Banjac and Goulart [3] found a condition similar to the assumption (A2) in a limited case, but they were not aware that the boundedness of the gradient of f at local minimizers can guarantee the existence of the exact penalty parameter. No propositions have revealed such an essential and intuitive assumption on f in the previous papers [14,1,6,32,2,41,30]. We will now use Lemma 4 to derive exact penalty parameters of the generalized trimmed lasso (4). Theorem 1. Suppose that the assumption (A1) holds and f is M -smooth. Let (x * 1 , . . . , x * L ) be a d-stationary point of (4) and C l > 0 be constants such that x * l 2 ≤ C l for all l ∈ [L]. Then, (x * 1 , . . . , x * L ) satisfies the constraint (13) if holds for all l ∈ [L]. The right hand side of (18) can be replaced by where the first inequality follows from the Cauchy-Schwarz inequality, the second one from the triangle inequality, the third one from the M -smoothness of f , and the fourth one from the assumption x * l 2 ≤ C l . Thus, the assumption (A2) holds with Γ l = ∇ x l f (0, . . . , 0) 2 + M l∈[L] C 2 l . From Lemma 4, we have the desired result. When p l = 1, D l = I, and c l = 0 hold, since we can evaluate as In [14]: Assume that f is M -smooth, L = 1, p = 1, D = I, and c = 0. Let x * be an optimal solution of (4) and C > 0 be a constant such that x * 2 ≤ C. Then, x * satisfies the constraint (13) if γ > ∇f (0) 2 + 3 2 M C holds.
In [1]: Assume that f is M -smooth and convex, L = 1, p = 1, D = I, and c = 0. Let x * be a d-stationary point (i.e., locally optimal solution) of (4) and C > 0 be a constant such that x * 2 ≤ C. Then, x * satisfies the constraint (13) Our exact penalty parameter ∇f (0) ∞ + M C is not only derived under weaker assumptions for each case, but also smaller than both. Then, we also make a comparison with the results of Nakayama and Gotoh [32, In [32]: Let (x * 1 , x * 2 ) be an optimal solution of (4) with L = 2, p 1 = p 2 = 1, D 1 = I, D 2 = I, c 1 = 0, and c 2 = 0. Assume that f is M -smooth, and there exist C 1 , C 2 > 0 such that x * 1 2 ≤ C 1 and We see that our exact penalty parameters from Theorem 1 are ∇ x1 f (0, 0) ∞ +M C 2 1 + C 2 2 and ∇ x2 f (0, 0) ∞ + M C 2 1 + C 2 2 , which are smaller than ∇ x1 f (0, 0) 2 + M (C 1 + C 2 ) and ∇ x2 f (0, 0) 2 + M (C 1 + C 2 ), respectively, indicating a stronger result than Nakayama and Gotoh [32]. 2 Looking at Ahn et al. [1], it may appear at first glance that their result is a different claim, but with the appropriate parameter transformations, we can see that their result is the same one. 3 Looking at Nakayama and Gotoh [32], it may appear at first glance that their result is a slightly stronger. However, since their argument is a bit wrong, their result is the same one essentially.
Although Theorem 1 is a stronger result than previous studies, it seems difficult to guarantee "boundedness" without assuming, for example, the strong convexity on f . In particular, f is always not strongly convex in Example 5. Motivated by this, below we derive exact penalty parameters under two more practical assumptions. We first consider assumptions that include the case where f is non-differentiable.
Theorem 2. Suppose that the assumption (A1) holds, and that f is directionally differentiable and Lipschitz continuous with constant M under the ℓ 2 norm. Then, any d-stationary point (x * 1 , . . . , x * L ) of (4) satisfies the constraint (13) if Corollary 1 (exact penalty parameter for Example 2: sparse linear regression with power 1). Let x * be a d-stationary point of (6). If γ > max j∈[n] a j 2 holds, then x * satisfies T K,n,1 (x * ) = 0, where a j denotes the jth column of A.
If γ > j∈[q] a j ∞ holds, then x * satisfies T K,n,1 (x * ) = 0. Corollary 1 is equivalent to the result by Amir et al. [2,Theorem 2.2]. We note that it is the first time that an exact penalty parameter of (7) is given concretely. In addition, an exact penalty parameter of (8) is also derived in the concrete form for the first time.
Next, we derive an exact penalty parameter for one of the most commonly used loss functions, which is not Lipschitz continuous.
A l x l 2 holds for all l ∈ [L].
(b) Assume that p l = 1, D l = I, c l = 0, and f (x 1 , . . . , Since f is convex, combining the inequality (20), Lemma 1, and non-negativity of T K l ,m l ,p l yields Then, for all d l such that d l 2 = 1, we obtain where the first inequality follows from the Cauchy-Schwarz inequality. Thus, the assumption (A2) holds with Γ l = A l 2 b − l∈[L] A l x l 2 . From Lemma 4, we have the desired result.
To show the statement (b), we note that b − l∈[L] A l x * l 2 ≤ b 2 can be obtained in a similar way as in the proof of statement (a). Then, we can evaluate as A l x * Corollary 4 (Exact penalty parameter for Example 1: sparse linear regression). Let x * be a d-stationary point of (5). If γ > max j∈[n] a j 2 b 2 − η holds, then x * satisfies T K,n,1 (x * ) = 0, where a j denotes the jth column of A.
Corollary 6 (Exact penalty parameter for Example 6: minimizing constraints violation). Let x * be a dstationary point of (10). The point x * satisfies T K,m,1 (x * ) = 0 if γ > b−x 2 σmin(D) holds, where x is a point that satisfies Dx = c.
Note that exact penalty parameters of (9), (10), and (11)  Finally, let us reconsider Example 7 (piece-wise linear trend estimation). we can obtain a more tractable exact penalty parameter of (11), not using Lemma 4 directly, but slightly modifying its proof. Note that the second-order difference matrix D (2,n) can be expressed as D (2,n) = D (1,n−1) D (1,n) , using the first-order difference matrix Using σ min (D (1,n) ) = 2(1 − cos π n ) [23, Theorem 2.2], we can derive an exact penalty as follows. See Appendix B for the proof.
Theorem 4 (More tractable exact penalty parameter for Example 7: piece-wise linear trend estimation). Let x * be a d-stationary point of (11), (1−cos π n )(1−cos π n−1 ) holds, then x * satisfies T K,n−2,1 (D (2,n) x * ) = 0. We close this section by mentioning that it is not known whether the exact penalty parameter by Yagishita and Gotoh [41] or the exact penalty parameter derived from Lemma 4 is smaller for the network trimmed lasso [41].

Unconstrained Problem Penalized by Truncated Nuclear Norm
In this section, we consider parallel results to the previous section for the rank constraint.

Truncated Nuclear Norm and Rank-Constrained Formulation
For a matrix X ∈ R m×n , the truncated nuclear norm is defined by where K ∈ {0, . . . , q} and q := min{m, n}. It holds that T K (X) ≥ 0 for any X, and T K (X) = 0 if and only if rank(X) ≤ K.
Thus, we can view that the truncated nuclear norm measures the violation of the rank constraint (21), which was first pointed out by Gao and Sun [12]. Obviously, T K is reduced to the nuclear norm when K = 0. Note also that T K is directionally differentiable since T K is the difference of the nuclear norm and the Ky Fan K norm [14]. We consider the following minimization problem: where γ > 0. This formulation involves a lot of existing unconstrained problems penalized by the truncated nuclear norm [44,18,19,17,33,45,14,30]. To the best of our knowledge, the first penalized problems via the truncated nuclear norm were proposed independently by Gao and Sun [12] (with some constraints) and Zhang et al. [44]. As is the case for the generalized trimmed lasso (4), any optimal (resp. locally optimal) solution of (22) satisfying the constraint (21) (or T K (X) = 0) is optimal (resp. locally optimal) to the problem minimize X∈R m×n f (X) subject to rank(X) ≤ K.
The following remarkable applications are included in the problem (22).
Example 8 (Small rank linear regression [44,18,14]). Gotoh et al. [14] considered the following problem: where b ∈ R p , A 1 , . . . , A p ∈ R m×n and A(X) = (A 1 • X, . . . , A p • X) ⊤ . Zhang et al. [44] and Hu et al. [18] proposed the matrix completion problem that is the special case of this problem with b = (M i,j ) (i,j)∈Ω and Example 9 (Multi-class classification [19]). Let b 1 , . . . , b q ∈ [n] and a 1 , . . . , a q ∈ R m denote, respectively, the class labels and features vectors of q samples. To find n-class classifiers, Hu et al. [19] considered the following problem: where x l denotes the l-th column of X.
We remark that unlike the generalized trimmed lasso (4) the equivalence of the local optimality and the d-stationarity does not hold in the problem (22) even when f is a convex function. To see this, let us consider the special case of (22) minimize For X * = ( 1 0 0 2 ), we have from the result of Lewis and Sendov [24,Subsection 5.1]. This implies that σ 2 is differentiable at the point X * and the gradient is ∇σ 2 (X * ) = ( 1 0 0 0 ), so X * is a d-stationary point of (26). On the other hand, with the direction Y = 2 −1 −1 2 and a step size ξ > 0, consider the perturbed value h(ξ) :=f (X * + ξY ) + γσ 2 (X * + ξY ) where the second equality follows from a simple eigenvalue calculation. Since h ′ (ξ) = − 2γξ √ 4ξ 2 +1 < 0, X * is not a local minimizer of (26). We also see by Proposition 1 that T 1 : R 2×2 → R cannot be represented as the pointwise minimum of a finite number of convex functions. The only existing exact penalty parameters of the problem (22) is for globally optimal solutions by Gotoh et al. [14] and Lu et al. [30]. The same is true for the constrained problem penalized by truncated nuclear norm [7,26,35,30], which version will be addressed in the next section.

Exact Penalties for Problems with Truncated Nuclear Norm
We will derive exact penalty parameters at d-stationary points of the truncated nuclear penalized problem (22) in the remainder of this section. Let us start with the following lemma, which is an analogue of Lemma 4.
Lemma 5. Let f be directionally differentiable and X * be a d-stationary point of (22). Suppose that there exists Γ such that Then, the point X holds.
By the positive homogeneity of directional derivatives with respect to the direction and the assumption (27), we have which contradicts the inequality (28).
Similar to the generalized trimmed lasso (4), we see that "the boundedness assumption for the gradient of f at stationary points" is essential in the problem (22). Using Lemma 5, we will derive exact penalty parameters of the truncated nuclear penalized problem (22). See Appendix B for all the proofs.
Theorem 5. Suppose that f is M -smooth. Let X * be a d-stationary point of (22) and C > 0 be a constant such that X * F ≤ C. Then, X * satisfies the constraint We compare Theorem 5 with the result of Gotoh et al. [14,Theorem 5].
In [14]: Assume that f is M -smooth. Let X * be an optimal solution of (22) and C > 0 be a constant such that X * F ≤ C. Then, X * satisfies the constraint T K (X * ) = 0 if γ > ∇f (0) F + 3 2 M C holds. Theorem 5 is stronger than Theorem 5 of Gotoh et al. [14] in two ways: (i) our exact penalty parameter ∇f (0) 2 + M C is derived at d-stationary points, which is easier to attain than global minimizers; (ii) ours is smaller than theirs. However, the boundedness assumption of the solution set is impractical in a more plausible way than the generalized trimmed lasso (4). For example, for the matrix completion problem, which is a special case of Example 8, f is not strongly convex whenever Ω [m] × [n] holds. Therefore, in the following, we derive exact penalty parameters under realistic assumptions. Theorems 6 and 7 are parallel to Theorems 2 and 3, respectively. See Appendix B for the proofs. Theorem 6 is stronger than the result by Lu et al. [30,Corollary 4.7] for the unconstrained case in the sense that our result is for d-stationary points whereas their result is for global minimizers. Since Theorem 6 does not require the boundedness of the set of optimal solutions but the boundedness of gradients of the first term f , much more practical exact penalties for Examples 9 (multi-class classification) and Example 10 (robust PCA) can be derived as follows.
As for Example 8 (small-rank linear regression), the first term is not Lipschitz continuous, so Theorem 6 does not apply. However, we can obtain a practical exact penalty as follows.
Theorem 7 (Exact penalty parameter for Example 8: small-rank linear regression). Let X * be a d-stationary point of (23). the point X * satisfies the constraint T K (X * ) = 0 if it is holds where A * is the adjoint operator of A and A * 2,2 = sup y 2=1 A * (y) 2 .

Penalized Problems with Additional Constraints
In this section, we derive exact penalty parameters for constrained problems by slightly extending the approach in the previous sections. Roughly speaking, to reach the desired results, what we need is to be careful so that the sum of the stationary point and the direction taken in the proofs of the preceding propositions (e.g., the vector (x * 1 , . . . , x * l + d, . . . , x * L ) appeared in the proof of Lemma 4) does not violate the constraints. Consider the problems and where C is a convex set. From Proposition 1, we have the following equivalence between the d-stationarity and the local optimality of (31).
Proposition 3. d-stationary points and local minimizers of (31) are equivalent if f is continuous, convex, and directionally differentiable on C.
The problems (31) and (32) include the following examples.
Example 11 (Sparse eigenvalue problem [14]). For C = {x ∈ R n | x 2 ≤ 1} and A ∈ S n such that λ max (A) > 0, Gotoh et al. [14] considered the following problem: Example 12 (Sparse portfolio selection [14]). For C = {x ∈ R n | 1 ⊤ x = 1, x ≥ 0}, b ∈ R n and A ∈ S n such that A 0, Gotoh et al. [14] considered the following problem: Example 13 (Sparse nonnegative linear regression). Let b ∈ R q , A ∈ R q×n be given in the same manner as in Examples 1, 2, and 5. For ∅ = I ⊂ [n] and C = {x ∈ R n | x i ≥ 0, i ∈ I}, we consider the following problem: Tono et al. [39] dealt with a problem similar to this problem.
Example 14 (Semidefinite box constrained problem with quadratic objective [26]). Liu et al. [26] considered the following problem: where C = {X ∈ S n | X 0, I − X 0}, A ∈ S n , and H ∈ S n is a weight matrix whose entries are nonnegative. The spherical sensor localization problem and the nearest low-rank correlation problem are included in this problem (see Liu et al. [26,Section 6]).
As below, Theorems 8 through 11 present the exact penalties for (31) and (32) with the constraints exemplified in the above examples. The existing exact penalty parameters presented by Gotoh et al. [14] and Liu et al. [26] of the problems (31) and (32), respectively, are applicable only at globally optimal solutions. As in the previous sections, our exact penalty parameters are stronger in two ways, namely, ours are valid not only at d-stationary points, but also the thresholds are no greater than the existing ones even under weaker assumptions. The proofs can be given with slight modifications from those in the previous sections, but are included in Appendix B for completeness. Theorems 8 and 9 describe results for the problem (31)  In this case, f is Lipschitz continuous with some constant M ′ under the ℓ 2 norm. If γ > √ 2M ′ holds, then x * satisfies the constraint T K,n,1 (x * ) = 0. In addition to the continuous differentiability, suppose that f is M -smooth and 0 ∈ O. Then, the point x * satisfies T K,n,1 ( Theorem 10 describes an exact penalty for Example 13 (sparse nonnegative linear regression).
Theorem 10. Let x * be a d-stationary point of (33). If γ > max j∈[n] a j 2 b 2 holds, then x * satisfies T K,n,1 (x * ) = 0, where a j denotes the jth column of A.
Theorem 11 presents an improved exact penalty from Theorem 3.1 of Liu et al. [26] for the problem (32) with C = {X ∈ S n | X 0, CI − X 0}.
Theorem 11. Let x * be a d-stationary point of (32) with C = {X ∈ S n | X 0, CI − X 0}, where C is a positive number. Suppose that f is a continuous differentiable function on O ⊂ R n×n , where O is an open set such that C ⊂ O. In this case, f is Lipschitz continuous with some constant M ′ under the nuclear norm. If γ > M ′ holds, then X * satisfies the constraint T K (X * ) = 0. In addition to the continuous differentiability, suppose that f is M -smooth. Then, the point x * satisfies T K (X * ) = 0 If γ > min {M ′ , ∇f (0) 2 + √ nM C} holds. 5 The exact penalty parameter by Gotoh et al. [14,Corollary 3] is written as √ 2 ∇f (0) 2 − ( √ 2 + 1)M , but there is a typo; the correct one is √ 2 ∇f (0) 2 + ( √ 2 + 1)M .

Existing Algorithms for Obtaining D-stationary Points
In the previous sections, we have shown that under the mild assumptions any d-stationary point satisfies the cardinality or rank constraint if γ is taken to be large enough. This section summarizes some existing algorithms that can obtain a d-stationary point. The trimmed ℓ 1 norm and truncated nuclear norm are notable in that their proximal mapping are explicitly represented, though they are nonconvex and non-separable unlike ℓ 1 norm. The proximal mapping of g on C is defined as follows. For C ⊂ R n , prox g+ιC (x) := argmin and for C ⊂ R m×n , prox g+ιC (X) := argmin The proximal mappings of γ ′ T K,m,p , γ ′ T K , and γ ′ T K,n,1 + η ′ · 1 on the whole space (R n or R m×n ) have been derived by Yagishita [26,Theorem 4.4] have also derived the proximal mapping of γ ′ T K,n,1 on [−C, C] n and on [0, C] n , and γ ′ T K on {X ∈ S n | X 0, I − X 0}, respectively, where C > 0. On the other hand, the proximal mapping of γ ′ T K,n,1 on {x ∈ R n | x i ≥ 0, i ∈ I} can be obtained as Proposition 4. See Appendix B for the proof.
Proposition 4. Given x ∈ R n , let x ′ ∈ R n be the vector and S * be an index set of size n − K corresponding to the smallest n − K components of (|x ′ 1 |, . . . , |x ′ n |). With the vector z * ∈ R n defined by These explicit formulas of the proximal mappings can be used to construct efficient algorithms for obtaining d-stationary points.

Proximal ADMM
As the first algorithm for solving the generalized trimmed lasso (4), we consider the proximal alternating direction method of multipliers (proximal ADMM) [25]. To apply the proximal ADMM, we rewrite the generalized trimmed lasso (4) as the following equality constrained formulation: subject to z l = D l x l , l = 1, . . . , L.
By setting the problem (34)- (35) can be rewritten as minimize x,z subject to z = Dx.
Denoting the vector of dual variables for the equality constraints (37) by y, we define the augmented Lagrangian function of (36)-(37) as where ρ is a positive parameter. We define the Bregman distance of x and x ′ by for a continuously differentiable function φ on R N , where N = i∈[L] n l . The proximal ADMM for the generalized trimmed lasso (4) is then described as Algorithm 1. With an adequate φ, the subproblem (39) might be reduced to a simple problem. Bertsimas et al. [6] and Yagishita and Gotoh [41] used the proximal ADMM for solving special cases of the generalized trimmed lasso (4).
From Lemma 8, the explicit representation of the proximal mapping of γT K,m,p and the separability of g(z) with respect to z 1 , . . . , z L enable us to obtain a closed form solution of the subproblem (38). On the other hand, whether the solution of the subproblem (39) can be obtained explicitly depends on f and φ. When f is M -smooth and φ is given as φ(x) = M 2 x 2 2 − f (x), the subproblem (39) becomes a convex quadratic minimization problem, which can be reduced to solving a linear equation.
The following result shows the convergence of the proximal ADMM to a d-stationary point and the boundedness of the generated sequence. The statement and its proof are similar to those of Theorems 3 and 4 of Yagishita and Gotoh [41] (see the reference therein for the details).
Combined with Proposition 2, Theorem 12 implies that the proximal ADMM brings a locally optimal solution of the generalized trimmed lasso (4) if f is convex. Note also that even if f is not convex, as far as D is surjective and f is M -smooth and coercive, all the assumptions of Theorem 12 are satisfied if we set φ(x) = M 2 x 2 2 − f (x) and take ρ large enough. See Examples 3 and 5 in Yagishita and Gotoh [41] for the details. Note also that to the problem regularized with truncated nuclear norm (22), the proximal ADMM can be applied and its global convergence result is valid without modification when f is M -smooth.

GIST (Nonmonotone Proximal Gradient Method)
The proximal ADMM for the generalized trimmed lasso (4) not only uses the extra memory when adding variables z and y to x, but also it often requires solving a (possibly, large-sized) linear equation at each iteration, which increases the computational cost as the dimension of x increases. To void that issue, let us consider the proximal gradient method (PGM).
For the generalized trimmed lasso (4), the PGM generates the sequence {x t } by for some {µ t }. From Lemma 8 and the explicit formula of the proximal mapping of γ ′ T K,m,p , each iteration (40) can be efficiently computed if D l D ⊤ l = α l I holds with α l > 0 for all l ∈ [L]. The same is true for the problem (22), (31) with C = {x ∈ R n | x i ≥ 0, ∀ i ∈ I}, and (32) with C = {X ∈ S n | X 0, I − X 0}. Luo et al. [31] and Huang et al. [20] solved the problem (5) by the PGM with a constant µ t and with µ t ≡ 1, respectively.
The general iterative shrinkage and thresholding (GIST) algorithm [40,13] is a method that combines a non-monotone linear search [15] with the Barzilai-Borwein rule [4] to determine the initial step size 1/µ t of the PGM. See Wright et al. [40] for the details on the algorithm. Lu and Li [27] and Nakayama and Gotoh [32], and Liu et al. [26] used the GIST for solving special cases of the generalized trimmed lasso (4) and the problem (32) with C = {X ∈ S n | X 0, I − X 0}, respectively. From Theorem 1 of Nakayama and Gotoh [32], we have the following convergence result for the generalized trimmed lasso (4). 6 Theorem 13. Suppose that f is M -smooth. If the sequence {x t } generated from GIST for the problem (4) is bounded, then any accumulation point of {x t } is a d-stationary point of the problem (4).
Similar to the result of the proximal ADMM, GIST is also guaranteed to converge to a locally optimal solution if f is convex. It is notable that Huang et al. [20] found a convergence result to a local minimizer when applying the PGM with µ t ≡ 1 to the problem (5) under the assumption A 2 < 1. Theorem 13 holds for the problem (22) as well and, assuming that C is a closed convex set, it also holds for the problems (31) and (32). Liu et al. [26] showed an exact penalty result for global minimizers, and that GIST converges to a l(imiting)-stationary point, which is a weaker stationarity notion than d-stationarity, of the problem (32) with f is M -smooth and C = {X ∈ S n | X 0, I − X 0}. While there was an inconsistency between the exact penalty result and the convergence result in Liu et al. [26], Theorems 11 and 13 of this paper fill the gap. The same is true for the inconsistency in Nakayama and Gotoh [32].

Remark on Other Algorithms
Besides the proximal ADMM and PGM, it is known that EDCA [34], EPDCA [29], and NEPDCA [28] can also obtain a d-stationary point (see those papers for the details). However, while those algorithms are also applicable to the problems penalized by the trimmed ℓ 1 norm, it is not clear to us whether they are applicable to the problems with the truncated nuclear norm penalty (22).
A homotopy method proposed by Amir et al. [2] for solving the problem (5) can be extended to for the generalized trimmed lasso (4). However, this algorithm has only yielded convergence results to a d-stationary point or ambiguous point. 7

Concluding Remarks
In this paper, we have extended the trimmed lasso to the generalized trimmed lasso and shown results of exact penalization for the generalized trimmed lasso and the problem penalized by the truncated nuclear norm under weaker assumptions than in the existing studies. The unified analysis for the generalized trimmed lasso reveals the essential assumption on the loss function term for the existence of the exact penalty parameter. In particular, to the best of our knowledge, no exact penalty results at other than globally optimal solutions have been known for the truncated nuclear norm. As a result, we have seen that the existing local search algorithms such as the proximal ADMM and proximal gradient algorithms yield a point that satisfies the (structured) sparsity or rank constraint. On the other hand, we have not been able to derive an exact penalty parameter at d-stationary points for penalized problems that have not-simple constraints such as the one addressed in Gao and Sun [12]. We left the derivation of the exact penalty parameters at stationary points of the constrained problems for future works, although Bi and Pan [7] and Qian et al. [35] have derived exact penalties at globally optimal solutions of some of them. We have also shown the relationship between local optimality and d-stationarity of these problems. By the equivalence result, d-stationary points of the generalized trimmed lasso that are attainable by the existing algorithms are also locally optimal if the loss function f is convex. Furthermore, our equivalence result between local minimizers and d-stationary points is valid also for the more general problem whose objective function is defined by the pointwise minimum of finitely many convex functions, so it might be useful for formulations in other contexts.
In this section, we present some of the lemmas used in the main body of this paper. Thus, Av i = 0 holds for i = r + 1, . . . , n, that is, v 1 , . . . , v r is a basis of ker(A) ⊥ . Thus, any x ∈ ker(A) ⊥ can be expanded as x = r i=1 (x ⊤ v i )v i . Therefore, we have which is the desired result.
Lemma 7. Let C ⊂ R n (or C ⊂ R m×n ) be a convex set and f : C → R is directionally differentiable and Lipschitz continuous on C with constant M under some norm · , that is, |f (x) − f (y)| ≤ x − y holds for all x, y ∈ C. Then, the inequality |f ′ (x; y − x)| ≤ M y − x holds for all x, y ∈ C.
Proof. By the Lipschitz continuity of f with constant M , we have for 1 ≥ ς > 0. Taking the limit ς ց 0 yields which completes the proof.
The following lemma gives a nonconvex version of the formula for the proximal mapping of a composition of a convex function and affine mapping [5, Theorem 6.15].

Appendix B Proofs
In this section, we provide the proofs omitted in the main body of this paper.
By the mean value theorem, there is a point τ j ∈ (0, 1) such that h j (1) − h j (0) = h ′ j (τ j ). We then have a j 2 Y − X * .
From Theorem 6, we have the desired result.
Suppose also that f is M -smooth, then we have which indicates that γ ≤ min {M ′ , ∇f (0) 2 + √ nM C}. This is a contradiction to the assumption of γ.