Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization

Jun Liu; Shuiwang Ji; Jieping Ye

Source-linked AI summary

Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization

Jun Liu, Shuiwang Ji, Jieping Ye

arXiv:1205.2631v1May 9, 2012cs.LGcs.CVstat.ML

TL;DR

Joint feature selection across related tasks benefits from shared sparsity, but ℓ2,1-norm regularization creates a challenging nonsmooth optimization problem. The paper replaces it with two equivalent smooth convex reformulations solved by Nesterov’s method, with efficient projections and empirical evidence supporting algorithmic efficiency. Its broader comparisons and applications remain future work.

Problem
Joint feature selection across related tasks needs a formulation that exploits shared sparsity while addressing the difficult nonsmooth optimization induced by ℓ2,1-norm regularization.
Method
The paper uses two equivalent smooth convex reformulations of the ℓ2,1-norm problem and solves them with Nesterov’s first-order black-box method, using Euclidean projections as a key building block.
Results
The first reformulation’s Euclidean projection is analytic, the second is computable in linear time, and experiments on several data sets verify the proposed algorithms’ efficiency.
Takeaways & Limitations
Equivalent smooth reformulations provide an efficient way to solve ℓ2,1-norm regularized problems with smooth loss functions.
Takeaways & Limitations
The authors note that fair comparisons are difficult because implementations, algorithm parameters, and stopping criteria differ, and they leave comparisons with coordinate gradient descent for future work.

Abstract

from arXiv · show

The problem of joint feature selection across a group of related tasks has applications in many areas including biomedical informatics and computer vision. We consider the l2,1-norm regularized regression model for joint feature selection from multiple tasks, which can be derived in the probabilistic framework by assuming a suitable prior from the exponential family. One appealing feature of the l2,1-norm regularization is that it encourages multiple predictors to share similar sparsity patterns. However, the resulting optimization problem is challenging to solve due to the non-smoothness of the l2,1-norm regularization. In this paper, we propose to accelerate the computation by reformulating it as two equivalent smooth convex optimization problems which are then solved via the Nesterov's method-an optimal first-order black-box method for smooth convex optimization. A key building block in solving the reformulations is the Euclidean projection. We show that the Euclidean projection for the first reformulation can be analytically computed, while the Euclidean projection for the second one can be computed in linear time. Empirical evaluations on several data sets verify the efficiency of the proposed algorithms.

1 Introduction

The paper targets joint feature selection across related tasks, where shared sparsity is useful but the ℓ2,1-norm formulation is difficult to solve efficiently. It introduces two smooth reformulations solved with Nesterov’s method and reports efficient algorithms.

Multi-task learning exploits shared information among related tasks and has applications including medical diagnosis, character recognition, conjoint analysis, and text classification.
The ℓ2,1-norm groups each feature’s coefficients across tasks, encouraging predictors to share similar sparsity patterns.
Existing iterative methods for the nonsmooth convex problem may converge slowly, and no known global convergence rate had been established.
The proposed approach reformulates the nonsmooth problem into two equivalent smooth convex problems and applies Nesterov’s optimal first-order black-box method.The method uses function values and (sub)gradients only.
The first reformulation has an analytically computable Euclidean projection, while the second has a projection computable in linear time.The resulting smooth-loss problem has time complexity O(1/ε(mn + nk)), with m, n, k, and ε denoting samples, dimensionality, tasks, and desired accuracy.

2 A Probabilistic Framework for Multi-task Feature Learning

The probabilistic framework models multiple task-specific linear predictors jointly, using a prior on feature rows to capture task relatedness. Under shared-parameter assumptions, maximum posterior estimation yields an ℓ2,1-norm regularized regression problem.

For k tasks, the data matrices and targets are combined into A and y, while task weight vectors form W ∈ R^n×k.Each column of W is the weight vector for one task.
The model assumes each task target has a Gaussian distribution with mean f_j(a_j) and precision σ_j > 0.
A prior is placed on each feature row w_i across tasks to capture task relatedness, with an exponential form controlled by hyperparameter δ_i > 0.
Combining the likelihood and prior produces a maximum posterior estimation problem for W, which becomes an ℓ2,1-norm regularized least-squares problem under shared σ and δ assumptions.
The generalized formulation combines a smooth convex loss with ℓ2,1-norm regularization, including least-squares and logistic losses.
With multiple tasks, grouping each feature’s task weights through the ℓ2-norm encourages feature selection based on joint strength across tasks.

3 Two Equivalent Smooth Reformulations

The paper replaces the nonsmooth ℓ2,1-norm regularized problem with equivalent smooth convex formulations and solves them using Nesterov’s method. The reformulations support efficient projections and yield stated complexity improvements over subgradient-based optimization.

The nonsmooth objective requires O(1/ε^2) iterations for subgradient methods, compared with O(1/ε) for Nesterov’s method on the smooth reformulation.
The First Reformulation (aMTFL1): The first reformulation introduces variables t_i that upper-bound the row norms ∥w_i∥, producing a constrained smooth convex problem over D.
The Second Reformulation (aMTFL2): The second reformulation moves the nonsmooth ℓ2,1-norm term into an ℓ2,1-ball constraint, yielding an equivalent smooth convex optimization problem.
The Main Algorithm: Nesterov’s method iteratively forms affine-combination search points, takes projected gradient steps, and selects stepsizes by an Armijo-Goldstein line search.
Time Complexity: For least-squares or logistic loss, each iteration costs O(mn) flops for evaluation and gradient computation, while projections onto D cost O(nk).
Time Complexity: The resulting solution procedure has time complexity O((mn + nk)/ε) for the first reformulation, with the second reformulation analyzed similarly.

4 Efficient Euclidean Projections

The proposed algorithms reduce both reformulations to Euclidean projection problems. Projection onto D has an analytical solution, while projection onto Z uses dual root finding and remains linear in the matrix size.

Euclidean Projection onto D: Euclidean projection onto D has a unique analytical solution for the auxiliary variables and coefficient matrix.
Euclidean Projection onto D: In the one-dimensional illustration, points inside D remain unchanged, while points in the third region project to the origin.
Euclidean Projection onto D: The projection onto D costs O(nk) flops because row norms and projected variables can each be computed in O(nk) time.
Euclidean Projection onto Z: Projection onto Z is formulated with a Lagrange multiplier for the constraint ∥W∥2,1 ≤ z and solved using primal-dual optimality conditions.
Euclidean Projection onto Z: The dual optimum is zero when ∥U∥2,1 ≤ z; otherwise it is the unique positive root of the specified function, after which the primal solution is obtained analytically.
Euclidean Projection onto Z: The projection onto Z costs O(nk) time, scaling linearly with the size of U.

5 Experiments

Experiments evaluate convergence, computational efficiency, and the behavior of the two smooth reformulations across the School and Letter data sets. The proposed algorithms converge rapidly and outperform the compared methods, while aMTFL1 and aMTFL2 have efficiency that depends on sparsity.

Convergence analysis: Both reformulations decrease the objective rapidly at first and become stable after about 30 iterations on the tested data sets.The experiments use specified regularization parameters for aMTFL1 and set z from the aMTFL1 solution for aMTFL2.
Comparison with competing algorithms: The proposed algorithms are much more efficient than both MTL-FEAT and gradient descent in the School and Letter comparisons.The comparison uses computational time under varying regularization parameters on School and varying training-sample counts on Letter.
Computational cost: Each iteration of aMTFL1 and aMTFL2 costs O(mn + nk) flops and does not involve SVD.Here m, n, and k denote total training samples, sample dimensionality, and number of tasks, respectively.
aMTFL1 versus aMTFL2: aMTFL1 is competitive with aMTFL2 for relatively large ρ but less efficient for relatively small ρ because its distance to the optimal solution set becomes much larger.For large ρ, comparable distances and cheaper projection favor aMTFL1; for small ρ, reduced sparsity increases its distance term.
Computing a sequence of solutions: Warm-starting reduces the work of solving sequences of problems because each previous solution lies in the next problem’s feasible domain.The paper compares cold-start and warm-start iteration counts over sequences of ρ or z values on the School data set.

6 Conclusion

The paper addresses joint feature selection across related tasks using ℓ2,1-norm regularization, whose nonsmooth optimization is difficult to solve. It proposes smooth reformulations and identifies future extensions for improving practical performance and applying the algorithms more broadly.

ℓ2,1-norm regularization encourages predictors from different tasks to share similar sparsity patterns.
The nonsmooth problem is reformulated into two equivalent smooth convex problems solved with Nesterov’s method.
The first reformulation’s Euclidean projection is analytic, while the second reformulation’s projection is computable in linear time.
Empirical evaluations on several data sets demonstrate the efficiency of the proposed algorithms.
Future work includes adaptive line search, comparisons with coordinate gradient descent, and applications to real-world problems.

Appendix A. Proof of Theorem 1

The proof establishes that the auxiliary formulation is a constrained smooth convex optimization problem equivalent to the original formulation. Its feasible set is shown to be closed and convex through a product of ice-cream cones.

D is a closed convex set because it is constructed as a Cartesian product of closed convex ice-cream cones.
The objective in formulation (11) is smooth and convex because it combines the loss with the smooth convex term ρ∑i=1^n ti.
Formulations (9) and (11) are equivalent because optimal auxiliary variables satisfy ti = ∥wi∥ for every i.

Appendix B. Proof of Theorem 2

The proof shows that the second reformulation is a constrained smooth convex optimization problem and is equivalent to the original formulation through the ℓ2,1-norm constraint and Lagrangian duality.

The ℓ2,1-norm sublevel set is closed and convex, so formulation (13) is a constrained smooth convex optimization problem.
The equivalence between formulations (9) and (13) follows from Lagrangian duality.

Appendix C. Proof of Theorem 4

The proof characterizes Euclidean projections for the first reformulation by decomposing the problem into independent cone-constrained subproblems. It verifies feasibility and the variational inequality condition across cases, establishing the proposed solution.

The optimality of a constrained smooth convex problem is characterized by a variational inequality condition.
The Euclidean projection problem has a unique solution because its objective is strictly convex and its domain is closed and convex.
The projection decomposes into independent subproblems over the sets Di = {(ti, wi)|∥wi∥≤ti}.
The proposed solution is feasible because it satisfies ∥w̄i∥≤t̄i for each cone constraint Di.
The variational inequality is verified by considering the three cases ∥ui∥>|vi|, ∥ui∥≤vi, and ∥ui∥≤−vi.
The remaining proof establishes the proposed coordinate solution using strict convexity and subdifferential optimality conditions.
When λ̄=0, the solution is w̄i=ui, completing verification of the subdifferential condition.

Appendix E. Proof of Theorem 6

The proof establishes the sign of the optimal multiplier based on ||U||2,1 relative to z and proves that ω(λ) has a unique root.

Multiplier cases: If ||U||2,1 ≤ z, the proof shows λ̄ = 0 and derives equality conditions from the norm relationships and complementary slackness.The argument uses ||W̄||2,1 ≤ ||U||2,1 together with the active constraint when λ̄ > 0.
Multiplier cases: If ||U||2,1 > z, then the optimal multiplier satisfies λ̄ > 0 by contradiction with the constraint.Assuming λ̄ = 0 would imply W̄ = U and ||W̄||2,1 > z, contradicting the constraint.
Unique root: ω(λ) is continuous and monotonically decreasing, with opposite signs at 0 and max_i ||u_i||, so it has a unique root in that interval.Specifically, ω(0) = ||U||2,1 − z > 0 and ω(max_i ||u_i||) = −z < 0.

Appendix F. Definition of an Appropriate γ

The appendix defines an appropriate γ for convergence analysis and connects the regularized tangent minimization to Euclidean projection onto G.

Definition of an Appropriate γ: The choice of γ is central to analyzing convergence of Nesterov’s method.The appendix introduces γ > 0 as the parameter used in the convergence analysis.
Definition of an Appropriate γ: The quadratic function gγ,x(y) combines the tangent line of g at x with a square-distance regularizer and is strongly convex.This construction yields a quadratic minimization problem over the domain G.
Definition of an Appropriate γ: Minimizing gγ,x(y) over G is equivalent to computing the Euclidean projection onto G.Thus, Euclidean projection is the computational operation associated with minimizing the regularized tangent model.