PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Stage Multi-Task Feature Learning

Pinghua Gong, Jieping Ye, Changshui Zhang

arXiv:1210.5806v1stat.ML

TL;DR

Existing multi-task sparse feature learning methods commonly use convex regularization, which can be a loose approximation to ℓ0-type sparsity. This paper introduces a capped-ℓ1,ℓ1 non-convex formulation and the MSMTFL algorithm, reporting improved theoretical parameter-estimation error bounds and effectiveness on synthetic and real-world data.

  • Problem

    Existing multi-task sparse feature learning algorithms commonly use convex regularization, whose approximation of an ℓ0-type regularizer can be suboptimal.

  • Method

    The paper uses a capped-ℓ1,ℓ1 non-convex formulation and solves it with the Multi-Stage Multi-Task Feature Learning algorithm.

  • Results

    Theoretical analysis gives MSMTFL a better parameter estimation error bound than the convex formulation, while experiments on synthetic and real-world data demonstrate effectiveness against state-of-the-art methods.

  • Takeaways & Limitations

    MSMTFL provides a non-convex multi-task feature-learning approach that jointly models task-specific and shared features.

  • Takeaways & Limitations

    The paper leaves conditions for obtaining a globally optimal solution with MSMTFL for future work.

Abstract

from arXiv · show

Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated as a convex sparse regularization problem, which is usually suboptimal, due to its looseness for approximating an $\ell_0$-type regularizer. In this paper, we propose a non-convex formulation for multi-task sparse feature learning based on a novel non-convex regularizer. To solve the non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature Learning (MSMTFL) algorithm; we also provide intuitive interpretations, detailed convergence and reproducibility analysis for the proposed algorithm. Moreover, we present a detailed theoretical analysis showing that MSMTFL achieves a better parameter estimation error bound than the convex formulation. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of MSMTFL in comparison with the state of the art multi-task sparse feature learning algorithms.

1. Introduction

Multi-task feature learning seeks shared and task-specific features, but common convex sparse regularization can be restrictive and loose for approximating ℓ0-type sparsity. The paper proposes a non-convex alternative with an associated multi-stage algorithm and theoretical analyses.

  • Multi-task feature learning aims to learn task-specific features alongside features shared among tasks.
  • Requiring relevant features to be shared by every task is too restrictive for real-world applications.
  • The dirty model permits features to be shared by some tasks without requiring sharing across all tasks.
  • The proposed work introduces a capped-ℓ1,ℓ1 non-convex regularized model for jointly learning task-specific and common features.
  • MSMTFL solves the non-convex optimization problem and is analyzed for interpretation, convergence, reproducibility, and parameter estimation error.
  • The paper organizes its analysis around formulation and optimization, convergence and reproducibility, error bounds, proofs, experiments, and conclusions.

2. The Proposed Formulation and the Optimization Algorithm

The paper formulates multi-task feature learning with a non-convex regularizer and solves it using the multi-stage MSMTFL algorithm. The section develops locally linear and block-coordinate interpretations, discusses convergence, and relates MSMTFL to iterative weighted Lasso refinement.

  • 2.1 A Non-convex Formulation: The formulation learns a weight matrix for m linear predictive models from task-specific training data.Each task has data matrix X_i, response y_i, and weight vector w_i.
  • 2.1 A Non-convex Formulation: The capped-ℓ1, ℓ1 penalty promotes zero rows while allowing nonzero rows to contain task-specific zeros, supporting partially shared features.This structure permits features to be shared by some tasks rather than all tasks.
  • 2.2 Optimization Algorithm: MSMTFL addresses the non-convex optimization problem through an algorithm whose key subproblem combines differentiable loss with non-differentiable regularization and is solved using FISTA.The algorithm is presented as a multi-stage procedure for the proposed formulation.
  • 2.2.1 Locally Linear Approximation: The locally linear approximation replaces the difficult non-convex objective with a convex upper-bound minimization at each iteration.The resulting subproblem can be solved efficiently, and the construction is closely related to the Concave Convex Procedure.
  • 2.2.1 Locally Linear Approximation: The surrogate objective yields a monotonic decrease in objective value across iterations, but monotonic decrease alone does not establish algorithm convergence.The paper defers formal convergence analysis to a later section.
  • 2.2.2 Block Coordinate Descent: Using the conjugate representation of the concave regularizer, the optimization can also be expressed as a block coordinate descent procedure.The auxiliary-variable update corresponds to a sub-gradient, while the weight update corresponds to the algorithm’s optimization step.
  • 2.2.2 Block Coordinate Descent: The block coordinate descent interpretation is intuitive, but its convergence behavior is non-trivial to analyze.The paper states that convergence analysis is presented in Section 3.1.
  • 2.2.3 Discussions: With one stage, MSMTFL reduces to ℓ1-regularized multi-task feature learning, while additional stages adapt row penalties using the preceding solution.The paper characterizes the method as a sequence of weighted Lasso problems that refines the initial solution and theoretically improves parameter-estimation error bounds stage by stage.

3. Convergence and Reproducibility Analysis

The analysis establishes convergence to a critical point and reproducibility under continuous-design assumptions. Although global optimality is not guaranteed, the algorithm's generated solution is unique with probability one.

  • Convergence Analysis: The convergence result relies on interpreting the algorithm as a block coordinate descent procedure.
  • Convergence Analysis: The objective sequence is monotonically decreasing, and every limit point of the generated sequence is a critical point of the non-convex objective.Boundedness ensures at least one limit point for bounded initial points.
  • Reproducibility Analysis: Consequently, the solution generated by the multi-stage algorithm is reproducible under the stated uniqueness condition.
  • Reproducibility Analysis: For continuously distributed design entries, each stage's optimization problem has a unique solution with probability one.The proof uses general-position columns and strict convexity of the reduced objective.
  • Reproducibility Analysis: The solution need not be globally optimal, but the paper shows that it has a favorable parameter-estimation error bound.

4. Parameter Estimation Error Bound

The paper derives a high-probability parameter-estimation error bound for MSMTFL under sub-Gaussian noise and sparse-eigenvalue assumptions. As the number of stages increases, the bound improves and can become substantially better than convex baselines in large problems.

  • Assumptions: The analysis assumes independent sub-Gaussian noise and a sparse eigenvalue condition, with the latter slightly weaker than an RIP condition.
  • Main Bound: Theorem 8 gives a parameter-estimation error bound for MSMTFL with probability larger than 1−η under the paper's assumptions.The analysis assumes equal task sample sizes for simplicity and can be extended to unequal sizes.
  • Comparison Across Stages: When ℓ=1, corresponding to Lasso, the first term of the bound has the stated Lasso-order dependence.
  • Comparison Across Stages: The first term of the error bound shrinks exponentially as ℓ increases and tends to zero when ℓ is sufficiently large in the stated order.
  • Comparison Across Methods: When dm is large and the ground truth has few sparse rows, MSMTFL's ℓ2,1-norm bound is significantly better than the Lasso and Dirty-model bounds.
  • Relation to Prior Work: The proposed multi-task analysis extends capped-ℓ1 regularization beyond its single-task special case by exploiting relationships among tasks and across matrix rows and columns.

5. Proof Sketch of Theorem 8

The proof sketch builds Theorem 8 from residual-correlation bounds, support-set decompositions, and recursive stagewise inequalities. These components control error outside the true support and establish the shrinkage behavior across stages.

  • Proof Components: Lemma 13 bounds residual correlations with the underlying weight matrix under the noise assumptions and connects them to the tuning and error-bound conditions.
  • Proof Components: Lemma 14 controls estimation error outside the true support when the relevant threshold exceeds the residual-correlation magnitude.
  • Recursive Bound: Lemma 15 combines prior inequalities to produce an ℓ2,1-norm error bound at every stage using the selected coefficient indices.
  • Recursive Bound: Lemma 16 supplies the recursive relationship between consecutive-stage errors, which is crucial for the shrinkage term in Theorem 8.
  • Completion of the Proof: The proof repeatedly applies the stagewise inequalities, the condition s ≥ r̄, and the theorem's assumptions before substituting the resulting bound into Theorem 8.

6. Experiments

The experiments evaluate MSMTFL on synthetic MRI and Isolet data against three competing multi-task feature-learning methods. MSMTFL shows lower parameter-estimation and prediction errors, with stagewise improvement on synthetic data and stronger performance across training ratios on real-world data.

  • Experimental setup: MSMTFL is compared with Lasso, L1,2, and DirtyMTL using the same quadratic loss function.The comparison covers parameter-estimation error on synthetic data and prediction error on real-world data.
  • Synthetic data: The synthetic experiments generate sparse multi-task weights with 90% zero rows and additional within-row sparsity.Each task uses Gaussian features, while the underlying weights and noise are sampled from specified distributions.
  • Synthetic data: The parameter-estimation error decreases quickly across MSMTFL stages and converges in a few stages.The reported stagewise decrease is consistent with the paper’s theoretical stage-improvement result.
  • Synthetic data: MSMTFL has the smallest parameter-estimation error among the four algorithms across the tested parameter settings.At sufficiently large λ, all methods produce zero solutions and therefore converge to the same estimation error.
  • Real-world data: The real-world evaluation uses MRI and Isolet tasks with random training/test splits, 10 repetitions, and three-fold cross-validation for parameter tuning.The MRI data contain six MMSE prediction tasks, while Isolet contains five letter-classification tasks.
  • Real-world data: On MRI and Isolet, MSMTFL achieves the smallest nMSE, aMSE, and standard deviations among the compared algorithms.MRI performance remains comparable between 15% and 25% training ratios, while Isolet performance improves as the training ratio increases.

7. Conclusions

The paper concludes that a capped-ℓ1,ℓ1 non-convex formulation and the MSMTFL algorithm learn both task-specific and shared features. It reports convergence, reproducibility, estimation-error analysis, and empirical effectiveness, while leaving global-optimality conditions for future work.

  • Contributions: The capped-ℓ1,ℓ1 formulation learns features specific to each task together with features shared among tasks.It is proposed as a closer approximation to an ℓ0-type regularizer than the commonly used convex regularizer.
  • Contributions: MSMTFL solves the resulting non-convex optimization problem and is supported by convergence, reproducibility, and parameter-estimation analyses.The paper also provides intuitive interpretations of the algorithm.
  • Theoretical and empirical findings: Under a mild condition, MSMTFL generates a unique solution with a favorable parameter-estimation error bound, although the solution need not be globally optimal.The empirical studies on synthetic and real-world data support the algorithm’s effectiveness relative to state-of-the-art methods.
  • Future work: Future work will identify conditions under which MSMTFL can obtain a globally optimal solution.The authors also plan to study broader non-convex regularization frameworks with different loss functions and derive theoretical bounds.

A.1. Proof of Lemma 13

This appendix section supplies detailed proof steps for Lemma 13, using definitions, probabilistic bounds, and an intermediate inequality to derive the stated result.

  • Proof setup: The proof begins from a coordinate-level expression involving the j-th entry of the noise-related vector.The index j ranges over the feature coordinates.

A.2 Proof of Lemma 14

This appendix section derives Lemma 14 from the optimality condition of the optimization problem, a coordinate decomposition, and bounds on the noise and regularization terms.

  • Optimality condition: The proof starts from the optimality condition of Eq. (3) and rewrites the residual using the estimation error and noise.The sign function and element-wise product are explicitly used in the optimality expression.
  • Error decomposition: Introducing v = Δŵ_i and using Δŵ_ji = ŵ_ji outside the selected feature set yields an intermediate inequality.The substitution connects coordinatewise estimation errors to the matrix support structure.
  • Set decomposition: The proof partitions the coordinate set into G_i, (F̄_i ∪ G_i)^c, and F̄_i before rearranging the inequality.This decomposition is used together with the bound 2∥ε̄_i∥∞ < λ̂_Gi ≤ λ̂_0i.
  • Conclusion: Lemma 14 follows from the rearranged inequality and two additional inequalities stated at the end of the derivation.The final step invokes the preceding bound rather than introducing a new optimization argument.

A.3 Proof of Lemma 15

The proof establishes Lemma 15 at each stage by deriving its inequalities under Eq. (36), then proving Eq. (36) inductively across all stages.

  • Induction across stages: Induction begins from the initial stage, where Eq. (36) holds, and then shows that its validity at stage ℓ implies validity at the next stage.The proof uses the thresholding parameter θ and the definition of G(ℓ) to propagate the condition.
  • Induction across stages: Therefore, Eq. (36) holds at all stages, so both inequalities in Lemma 15 hold throughout the multi-stage procedure.This completes the proof of Lemma 15.

A.4 Proof of Lemma 16

The proof of Lemma 16 bounds the relevant index sets using the thresholding rule, while the surrounding lemmas provide probabilistic control under the model assumptions.

  • Set bounds: Because H̄ contains F̄, the first inequality in Lemma 16 follows directly from H̄ ⊇ F̄.The proof then focuses on establishing the second inequality.
  • Set bounds: For each index in F̄ or H̄ whose estimated weight has ℓ1 norm below θ, Eq. (19) yields the bound needed for Lemma 16’s second inequality.The resulting per-index inequality is applied uniformly over the relevant set.
  • Probabilistic support: The supporting results include a sub-Gaussian concentration lemma and an inequality used in the probabilistic analysis.The assumptions include independent sub-Gaussian components and a high-probability statement under Assumption 1.
  • Index construction: The index construction uses the largest components of w_Gi and defines I_i from the complement of G, linking the set counts to the proof’s sparsity quantities.The passage identifies J_i as the indices of the s_i largest components in absolute value.
Loading 1210.5806v1…