nips nips2010 nips2010-172 knowledge-graph by maker-knowledge-mining

172 nips-2010-Multi-Stage Dantzig Selector

Source: pdf

Author: Ji Liu, Peter Wonka, Jieping Ye

Abstract: We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X ∈ Rn×m (m n) and a noisy observation vector y ∈ Rn satisfying y = Xβ ∗ + where is the noise vector following a Gaussian distribution N (0, σ 2 I), how to recover the signal (or parameter vector) β ∗ when the signal is sparse? The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively reﬁnes the target signal β ∗ . We show that if X obeys a certain condition, then with a large probability the difference between the solution ˆ β estimated by the proposed method and the true solution β ∗ measured in terms of the lp norm (p ≥ 1) is bounded as ˆ β − β∗ p ≤ C(s − N )1/p log m + ∆ σ, where C is a constant, s is the number of nonzero entries in β ∗ , ∆ is independent of m and is much smaller than the ﬁrst term, and N is the number of entries of √ β ∗ larger than a certain value in the order of O(σ log m). The proposed method improves the estimation bound of the standard Dantzig selector approximately √ √ from Cs1/p log mσ to C(s − N )1/p log mσ where the value N depends on the number of large entries in β ∗ . When N = s, the proposed algorithm achieves the oracle solution with a high probability. In addition, with a large probability, the proposed method can select the same number of correct features under a milder condition than the Dantzig selector. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. [sent-6, score-0.905]

2 In this paper, we propose a multi-stage Dantzig selector method, which iteratively reﬁnes the target signal β ∗ . [sent-7, score-0.682]

3 The proposed method improves the estimation bound of the standard Dantzig selector approximately √ √ from Cs1/p log mσ to C(s − N )1/p log mσ where the value N depends on the number of large entries in β ∗ . [sent-9, score-0.807]

4 When N = s, the proposed algorithm achieves the oracle solution with a high probability. [sent-10, score-0.296]

5 In addition, with a large probability, the proposed method can select the same number of correct features under a milder condition than the Dantzig selector. [sent-11, score-0.194]

6 1 Introduction The sparse signal recovery problem has been studied in many areas including machine learning [18, 19, 22], signal processing [8, 14, 17], and mathematics/statistics [2, 5, 7, 10, 11, 12, 13, 20]. [sent-12, score-0.423]

7 In the sparse signal recovery problem, one is mainly interested in the signal recovery accuracy, i. [sent-13, score-0.569]

8 , ˆ the distance between the estimation β and the original signal or the true solution β ∗ . [sent-15, score-0.262]

9 If the design matrix X is considered as a feature matrix, i. [sent-16, score-0.085]

10 , each column is a feature vector, and the observation y as a target object vector, then the sparse signal recovery problem is equivalent to feature selection (or model selection). [sent-18, score-0.487]

11 In feature selection, one concerns the feature selection accuracy. [sent-19, score-0.167]

12 Typically, ˆ a group of features corresponding to the coefﬁcient values in β larger than a threshold form the supporting feature set. [sent-20, score-0.468]

13 The difference between this set and the true supporting set (i. [sent-21, score-0.325]

14 , the set of features corresponding to nonzero coefﬁcients in the original signal) measures the feature selection accuracy. [sent-23, score-0.207]

15 Two well-known algorithms for learning sparse signals include LASSO [15] and Dantzig selector [7]: 1 Xβ − y 2 + λ||β||1 (1) LASSO min : 2 β 2 1 Dantzig Selector min : ||β||1 β s. [sent-24, score-0.591]

16 : X T (Xβ − y) (2) ∞ ≤λ Strong theoretical results concerning LASSO and Dantzig selector have been established in the literature [4, 5, 7, 17, 20, 22]. [sent-26, score-0.57]

17 1 Contributions In this paper, we propose a multi-stage procedure based on the Dantzig selector, which estimates ˆ the supporting feature set F0 and the signal β iteratively. [sent-28, score-0.471]

18 In the proposed method, the supporting set F0 starts from an empty set and its size increases by one after each iteration. [sent-30, score-0.346]

19 At each iteration, we employ the basic framework of Dantzig selector and the ˆ information about the current supporting feature set F0 to estimate the new signal β. [sent-31, score-1.041]

20 In addition, we select the supporting feature candidates in F0 among all features in the data at each iteration, thus allowing to remove incorrect features from the previous supporting feature set. [sent-32, score-0.831]

21 2 Related Work Sparse signal recovery without the observation noise was studied in [6]. [sent-37, score-0.293]

22 It has been shown that under certain irrepresentable conditions, the 0-support of the LASSO solution is consistent with the true solution. [sent-38, score-0.135]

23 It was shown that when the absolute value of each element in the true solution is large enough, a weaker condition (coherence property) can guarantee the feature selection accuracy [5]. [sent-39, score-0.267]

24 A comprehensive analysis for LASSO, including the recovery accuracy in an arbitrary lp norm (p ≥ 1), was presented in [20]. [sent-43, score-0.213]

25 In [7], the Dantzig selector was proposed for sparse signal recovery and a bound of recovery accuracy with the same order as LASSO was presented. [sent-44, score-1.086]

26 An approximate equivalence between the LASSO estimator and the Dantzig selector was shown in [1]. [sent-45, score-0.548]

27 In [9], conditions on the design matrix X under which the LASSO and Dantzig selector coefﬁcient estimates are identical for certain tuning parameters were provided. [sent-47, score-0.595]

28 Many heuristic methods have been proposed in the past, including greedy least squares regression [16, 8, 19, 21, 3], two stage LASSO [20], multiple thresholding procedures [23], and adaptive LASSO [24]. [sent-48, score-0.271]

29 It was shown [16] that under an irrepresentable condition the solution of the greedy least squares regression algorithm (also named OMP or forward greedy algorithm) guarantees the feature selection consistency in the noiseless case. [sent-50, score-0.458]

30 A multiple thresholding procedure was proposed to reﬁne the solution of LASSO or Dantzig selector [23]. [sent-54, score-0.659]

31 An adaptive forward-backward greedy algorithm was proposed [18], and it was shown that under the restricted isometry condition the feature √ selection consistency is achieved if the minimal nonzero entry in the true solution is larger than O(σ log m). [sent-55, score-0.506]

32 The adaptive LASSO was proposed to adaptively tune the weight value for the L1 penalty, and it was shown to enjoy the oracle properties [24]. [sent-56, score-0.265]

33 , the signal dimension is much larger than the observation dimension. [sent-60, score-0.177]

34 The observation vector y ∈ Rn satisﬁes y = Xβ ∗ + , where β ∗ denotes ˆ the original signal (or true solution). [sent-63, score-0.187]

35 β is used to denote the solution of the proposed algorithm. [sent-64, score-0.091]

36 F denotes the supporting set of the ¯ original signal β ∗ . [sent-67, score-0.437]

37 In this paper, s is used to denote the size of the supporting set F , i. [sent-72, score-0.302]

38 We use βS to denote the subvector of β consisting of the entries of β in the index set S. [sent-75, score-0.075]

39 T T ¯ ¯ ¯¯ The oracle solution β is deﬁned as βF = (XF XF )−1 XF y, and βF = 0. [sent-77, score-0.267]

40 We assume that s = |supp0 (β ∗ )| < n, the variable number is much larger than T the feature dimension (i. [sent-88, score-0.098]

41 2 The Multi-Stage Dantzig Selector Algorithm In this section, we introduce the multi-stage Dantzig selector algorithm. [sent-101, score-0.548]

42 In the proposed method, ˆ we update the support set F0 and the estimation β iteratively; the supporting set F0 starts from an empty set and its size increases by one after each iteration. [sent-102, score-0.369]

43 At each iteration, we employ the basic 3 framework of Dantzig selector and the information about the current supporting set F0 to estimate ˆ the new signal β by solving the following linear program: min βF0 ¯ s. [sent-103, score-0.989]

44 (6) Since the features in F0 are considered as the supporting candidates, it is natural to enforce them to be orthogonal to the residual vector Xβ − y, i. [sent-106, score-0.377]

45 The other advantage is when all correct features are chosen, the proposed algorithm can be shown to converge to the oracle solution. [sent-110, score-0.301]

46 1 Main Results Motivation To motivate the proposed multi-stage algorithm, we ﬁrst consider a simple case where some knowledge about the supporting features is known in advance. [sent-115, score-0.374]

47 If we assume that the features belonging to a set F0 are known as supporting features, i. [sent-117, score-0.345]

48 This coincides with our motivation that more knowledge about the supporting features can lead to a better signal ˆ estimation. [sent-124, score-0.462]

49 Since β ∗ may not be ˆ a feasible solution of problem (6), it is not easy to directly estimate the distance between β and β ∗ . [sent-126, score-0.081]

50 F F From the analysis in the next section, we can see that the ﬁrst term is the upper bound of the distance ˆ ¯ from the optimizer to the oracle solution β − β p and the second term is the upper bound of the ¯ distance from the oracle solution to the true solution β − β ∗ p . [sent-130, score-0.725]

51 Setting λp = σ 2 log(m/η) (0 < η ≤ 1), with a probability at least 1 − η(π log m)−1/2 , the ˆ solution of the standard Dantzig selector βD obeys 4 ˆ βD − β ∗ 2 ≤ s1/2 σ 2 log(m/η), (9) (2) 1 − δ2s − θA,s,2s (2) (2) where δ2s = max(ρA,2s − 1, 1 − µA,2s ). [sent-136, score-0.742]

52 Theorem 1 also implies a bound estimation result for Dantzig selector by letting F0 = ∅ and p = 2. [sent-137, score-0.605]

53 If follows m that with probability larger than 1 − η(π log m)−1/2 , the following bound holds:   √ 10 1 ˆ  s1/2 σ 2 log (m/η). [sent-139, score-0.184]

54 In the following, we compare the performance bound of the proposed multi-stage method (N > 0) with the one in (10). [sent-142, score-0.084]

55 In this section, we show how ∗ the supporting set can be estimated. [sent-145, score-0.302]

56 Similar to previous work [5, 19], |βj | for j ∈ F is required to be larger than a threshold value. [sent-146, score-0.071]

57 √ ∗ The theorem above indicates that under the given condition, if minj∈J |βj | > O(σ log m) (as(∞) (∞) suming that there exists l ≥ s such that µA,s+l − θA,s+l,l s > 0), then with high probability l the selected |J| features by Dantzig selector belong to the true supporting set. [sent-153, score-1.031]

58 In particular, if |J| = s, then the consistency of feature selection is achieved. [sent-154, score-0.15]

59 The result above is comparable to the ones for other feature selection algorithms, including LASSO [5, 22], greedy least squares regression [16, 8, 19], two stage LASSO [20], and adaptive forward-backward greedy algorithm [18]. [sent-155, score-0.39]

60 In √ ∗ all these algorithms, the condition minj∈F |βj | ≥ Cσ log m is required, since the noise level is √ O(σ log m) [18]. [sent-156, score-0.149]

61 Because C is always a coefﬁcient in terms of the covariance matrix XX T (or the feature matrix X), it is typically treated as a constant term; see the literature listed above. [sent-157, score-0.082]

62 Under the assumption 1, if there exists a nonempty set s (∞) (∞) Ω = {l | µA,s+l − θA,s+l,l > 0} l ∗ and there exists a set J such that |suppαi (βJ )| > i holds for all i ∈ {0, 1, . [sent-159, score-0.109]

63 s−i l 2 log σ m−s η1 2 log m−s η1 + 1 (∞) µ(X T XF )1/2 ,s F σ 2 log(s/η2 ), and N = |J| − 1 into Algorithm 1, the solution after ⊂ F (i. [sent-163, score-0.166]

64 |J| correct features are selected) with probability larger than Assume that one aims to select N correct features by the standard Dantzig selector and the multistage method. [sent-165, score-0.794]

65 These two theorems show that the standard Dantzig selector requires that at least N ∗ of |βj |’s with j ∈ F are larger than the threshold value α0 , while the proposed multi-stage method ∗ requires that at least i of the |βj |’s are larger than the threshold value αi−1 , for i = 1, · · · , N . [sent-166, score-0.792]

66 Since {αj } is a strictly decreasing sequence satisfying for some l ∈ Ω, (∞) αi−1 − αi > 4θA,s+l,l (∞) (∞) l µA,s+l − θA,s+l,l s−i l 2σ 2 log m−s , η1 the proposed multi-stage method requires a strictly weaker condition for selecting N correct features than the standard Dantzig selector. [sent-167, score-0.233]

67 4 Signal Recovery In this section, we derive the estimation bound of the proposed multi-stage method by combing results from Theorems 1, 3, and 4. [sent-169, score-0.122]

68 Under the assumption 1, if there exists l such that (∞) (∞) µA,s+l − θA,s+l,l s (p) (p) > 0 and µA,2s − θA,2s,s > 0, l ∗ and there exists a set J such that |suppαi (βJ )| > i holds for all i ∈ {0, 1, . [sent-171, score-0.083]

69 , |J| − 1}, where the αi ’s are deﬁned in Theorem 4, then (1) taking F0 = ∅, N = 0 and λ = σ 2 log m−s η1 into Algorithm 1, with probability larger ˆ ˆ than 1 − η1 − η2 , the solution of the Dantzig selector βD (i. [sent-174, score-0.708]

70 , the distance from β to the oracle solution β) dominates in the estimated bounds. [sent-180, score-0.286]

71 Thus, the performance of the multi-stage method approximately √ √ improved the standard Dantzig selector from Cs1/p log mσ to C(s − N )1/p log mσ. [sent-181, score-0.693]

72 When p = 2, our estimation has the same order as the greedy least squares regression algorithm [19] and the adaptive forward-backward greedy algorithm [18]. [sent-182, score-0.235]

73 5 The Oracle Solution The oracle solution is the minimum-variance unbiased estimator of the true solution given the noisy observation. [sent-184, score-0.369]

74 We show in the following theorem that the proposed method can obtain the oracle solution with high probability under certain conditions: (∞) (∞) Theorem 6. [sent-185, score-0.368]

75 Under the assumption 1, if there exists l such that µA,s+l − θA,s+l,l s−i > 0, and l ∗ the supporting set F of β ∗ satisﬁes |suppαi (βF )| > i for all i ∈ {0, 1, . [sent-186, score-0.344]

76 , s − 1}, where the αi ’s are deﬁned in Theorem 4, then taking F0 = ∅, N = s and λ = σ (N ) the oracle solution can be achieved, i. [sent-189, score-0.267]

77 2 log m−s η1 into Algorithm 1, ˆ ¯ = F and β (N ) = β with probability larger than The theorem above shows that when the nonzero elements of the true coefﬁcients vector β ∗ are large enough, the oracle solution can be achieved with high probability. [sent-192, score-0.471]

78 Our comparison includes two aspects: signal recovery accuracy and feature selection accuracy. [sent-194, score-0.401]

79 The signal recovery accuracy ˆ ˆ is measured by the relative signal error: SRA = β − β ∗ 2 / β ∗ 2 , where β is the solution of a speciﬁc algorithm. [sent-195, score-0.465]

80 The feature selection accuracy is measured by the percentage of correct features ˆ ˆ selected: F SA = |F ∩ F |/|F |, where F is the estimated feature candidate set. [sent-196, score-0.272]

81 The s−sparse original signal β ∗ is generated with s nonzero elements independently uniformly distributed from 7 n=50 m=200 s=15 σ=0. [sent-200, score-0.166]

82 7 0 2 4 6 8 10 12 14 standard oracle multi−stage 0. [sent-269, score-0.225]

83 88 16 0 N 2 4 6 N 8 10 standard oracle multi−stage 0. [sent-270, score-0.225]

84 We compare the solutions of the standard Dantzig selector method (N = 0), the proposed method for different values of N , and the oracle solution. [sent-273, score-0.844]

85 The starting point of each curve records the SRA (or F SA) value of the standard Dantzig selector method; the ending point records the value of the oracle solution; the middle part of each curve records the results by the proposed method for different values of N . [sent-275, score-0.973]

86 Note that the solution of the ˆ standard Dantzig selector algorithm is equivalent to β (0) with N = 0. [sent-281, score-0.63]

87 Based on β (N ) , we compute the supporting set ˆ β ˆ ˆ (N ) as the index of the N largest entries in β (N ) . [sent-283, score-0.381]

88 Note that the supporting set we compute here F ˆ (N ) is different from the supporting set F0 which only contains the N largest feature indexes. [sent-284, score-0.675]

89 Overall, the recovery accuracy curve increases with an increasing value of N and the feature selection accuracy curve is decreasing with an increasing value of N . [sent-287, score-0.373]

90 5 Conclusion In this paper, we propose a multi-stage Dantzig selector method which iteratively selects the supporting features and recovers the original signal. [sent-288, score-0.949]

91 The proposed method makes use of the information of supporting features to estimate the signal and simultaneously makes use of the information of the estimated signal to select the supporting features. [sent-289, score-0.95]

92 Our theoretical analysis shows that the proposed method improves upon the standard Dantzig selector in both signal recovery and supporting feature selection. [sent-290, score-1.257]

93 In addition, we plan to improve the proposed algorithm by adopting stopping rules similar to the ones recently proposed in [3, 19, 21]. [sent-295, score-0.073]

94 Stable recovery of sparse overcomplete representations in the presence of noise. [sent-346, score-0.189]

95 Sparse recovery in large ensembles of kernel machines on-line learning and bandits. [sent-358, score-0.146]

96 Model selection in gaussian graphical models: High-dimensional consistency of l1 -regularized MLE. [sent-376, score-0.098]

97 Sharp thresholds for noisy and high-dimensional recovery of sparsity using l1 -constrained quadratic programming (Lasso). [sent-394, score-0.163]

98 Adaptive forward-backward greedy algorithm for sparse learning with linear models. [sent-398, score-0.096]

99 On the consistency of feature selection using greedy least squares regression. [sent-402, score-0.26]

100 Some sharp performance bounds for least squares regression with l1 regularization. [sent-406, score-0.091]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('dantzig', 0.583), ('selector', 0.548), ('supporting', 0.302), ('xf', 0.234), ('oracle', 0.205), ('recovery', 0.146), ('lasso', 0.14), ('signal', 0.117), ('sra', 0.099), ('multi', 0.082), ('fsa', 0.073), ('stage', 0.063), ('selection', 0.063), ('solution', 0.062), ('greedy', 0.053), ('feature', 0.052), ('log', 0.052), ('larger', 0.046), ('obeys', 0.044), ('lp', 0.044), ('sparse', 0.043), ('supp', 0.043), ('features', 0.043), ('squares', 0.041), ('sa', 0.039), ('theorem', 0.037), ('irrepresentable', 0.036), ('mul', 0.036), ('reserch', 0.036), ('consistency', 0.035), ('bound', 0.034), ('candes', 0.033), ('curve', 0.033), ('omp', 0.032), ('index', 0.032), ('adaptive', 0.031), ('nonzero', 0.031), ('milder', 0.029), ('proposed', 0.029), ('condition', 0.029), ('entries', 0.028), ('records', 0.028), ('minj', 0.027), ('multistage', 0.027), ('exists', 0.026), ('nonempty', 0.026), ('threshold', 0.025), ('correct', 0.024), ('annals', 0.023), ('accuracy', 0.023), ('true', 0.023), ('estimation', 0.023), ('simulation', 0.023), ('theoretical', 0.022), ('employ', 0.022), ('method', 0.021), ('pursuit', 0.021), ('coef', 0.021), ('cai', 0.02), ('standard', 0.02), ('thresholding', 0.02), ('largest', 0.019), ('select', 0.019), ('distance', 0.019), ('coherence', 0.019), ('electronic', 0.018), ('candidates', 0.018), ('original', 0.018), ('regression', 0.018), ('design', 0.018), ('numerical', 0.018), ('iteratively', 0.017), ('orthogonal', 0.017), ('noisy', 0.017), ('rn', 0.017), ('noise', 0.016), ('assumption', 0.016), ('sharp', 0.016), ('overestimation', 0.016), ('nga', 0.016), ('esti', 0.016), ('least', 0.016), ('transactions', 0.016), ('empty', 0.015), ('holds', 0.015), ('plan', 0.015), ('weaker', 0.015), ('vector', 0.015), ('matrix', 0.015), ('row', 0.015), ('citing', 0.015), ('distri', 0.015), ('arizona', 0.015), ('combing', 0.015), ('subvector', 0.015), ('percentage', 0.015), ('mutual', 0.014), ('observation', 0.014), ('certain', 0.014), ('behind', 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 172 nips-2010-Multi-Stage Dantzig Selector

Author: Ji Liu, Peter Wonka, Jieping Ye

2 0.15037784 265 nips-2010-The LASSO risk: asymptotic results and real world examples

Author: Mohsen Bayati, José Pereira, Andrea Montanari

Abstract: We consider the problem of learning a coefﬁcient vector x0 ∈ RN from noisy linear observation y = Ax0 + w ∈ Rn . In many contexts (ranging from model selection to image processing) it is desirable to construct a sparse estimator x. In this case, a popular approach consists in solving an ℓ1 -penalized least squares problem known as the LASSO or Basis Pursuit DeNoising (BPDN). For sequences of matrices A of increasing dimensions, with independent gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. Our result is the ﬁrst rigorous derivation of an explicit formula for the asymptotic mean square error of the LASSO for random instances. The proof technique is based on the analysis of AMP, a recently developed efﬁcient algorithm, that is inspired from graphical models ideas. Through simulations on real data matrices (gene expression data and hospital medical records) we observe that these results can be relevant in a broad array of practical applications.

3 0.10025932 5 nips-2010-A Dirty Model for Multi-task Learning

Author: Ali Jalali, Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar

Abstract: We consider multi-task learning in the setting of multiple linear regression, and where some relevant features could be shared across the tasks. Recent research has studied the use of ℓ1 /ℓq norm block-regularizations with q > 1 for such blocksparse structured problems, establishing strong guarantees on recovery even under high-dimensional scaling where the number of features scale with the number of observations. However, these papers also caution that the performance of such block-regularized methods are very dependent on the extent to which the features are shared across tasks. Indeed they show [8] that if the extent of overlap is less than a threshold, or even if parameter values in the shared features are highly uneven, then block ℓ1 /ℓq regularization could actually perform worse than simple separate elementwise ℓ1 regularization. Since these caveats depend on the unknown true parameters, we might not know when and which method to apply. Even otherwise, we are far away from a realistic multi-task setting: not only do the set of relevant features have to be exactly the same across tasks, but their values have to as well. Here, we ask the question: can we leverage parameter overlap when it exists, but not pay a penalty when it does not ? Indeed, this falls under a more general question of whether we can model such dirty data which may not fall into a single neat structural bracket (all block-sparse, or all low-rank and so on). With the explosion of such dirty high-dimensional data in modern settings, it is vital to develop tools – dirty models – to perform biased statistical estimation tailored to such data. Here, we take a ﬁrst step, focusing on developing a dirty model for the multiple regression problem. Our method uses a very simple idea: we estimate a superposition of two sets of parameters and regularize them differently. We show both theoretically and empirically, our method strictly and noticeably outperforms both ℓ1 or ℓ1 /ℓq methods, under high-dimensional scaling and over the entire range of possible overlaps (except at boundary cases, where we match the best method). 1 Introduction: Motivation and Setup High-dimensional scaling. In ﬁelds across science and engineering, we are increasingly faced with problems where the number of variables or features p is larger than the number of observations n. Under such high-dimensional scaling, for any hope of statistically consistent estimation, it becomes vital to leverage any potential structure in the problem such as sparsity (e.g. in compressed sensing [3] and LASSO [14]), low-rank structure [13, 9], or sparse graphical model structure [12]. It is in such high-dimensional contexts in particular that multi-task learning [4] could be most useful. Here, 1 multiple tasks share some common structure such as sparsity, and estimating these tasks jointly by leveraging this common structure could be more statistically efﬁcient. Block-sparse Multiple Regression. A common multiple task learning setting, and which is the focus of this paper, is that of multiple regression, where we have r > 1 response variables, and a common set of p features or covariates. The r tasks could share certain aspects of their underlying distributions, such as common variance, but the setting we focus on in this paper is where the response variables have simultaneously sparse structure: the index set of relevant features for each task is sparse; and there is a large overlap of these relevant features across the different regression problems. Such “simultaneous sparsity” arises in a variety of contexts [15]; indeed, most applications of sparse signal recovery in contexts ranging from graphical model learning, kernel learning, and function estimation have natural extensions to the simultaneous-sparse setting [12, 2, 11]. It is useful to represent the multiple regression parameters via a matrix, where each column corresponds to a task, and each row to a feature. Having simultaneous sparse structure then corresponds to the matrix being largely “block-sparse” – where each row is either all zero or mostly non-zero, and the number of non-zero rows is small. A lot of recent research in this setting has focused on ℓ1 /ℓq norm regularizations, for q > 1, that encourage the parameter matrix to have such blocksparse structure. Particular examples include results using the ℓ1 /ℓ∞ norm [16, 5, 8], and the ℓ1 /ℓ2 norm [7, 10]. Dirty Models. Block-regularization is “heavy-handed” in two ways. By strictly encouraging sharedsparsity, it assumes that all relevant features are shared, and hence suffers under settings, arguably more realistic, where each task depends on features speciﬁc to itself in addition to the ones that are common. The second concern with such block-sparse regularizers is that the ℓ1 /ℓq norms can be shown to encourage the entries in the non-sparse rows taking nearly identical values. Thus we are far away from the original goal of multitask learning: not only do the set of relevant features have to be exactly the same, but their values have to as well. Indeed recent research into such regularized methods [8, 10] caution against the use of block-regularization in regimes where the supports and values of the parameters for each task can vary widely. Since the true parameter values are unknown, that would be a worrisome caveat. We thus ask the question: can we learn multiple regression models by leveraging whatever overlap of features there exist, and without requiring the parameter values to be near identical? Indeed this is an instance of a more general question on whether we can estimate statistical models where the data may not fall cleanly into any one structural bracket (sparse, block-sparse and so on). With the explosion of dirty high-dimensional data in modern settings, it is vital to investigate estimation of corresponding dirty models, which might require new approaches to biased high-dimensional estimation. In this paper we take a ﬁrst step, focusing on such dirty models for a speciﬁc problem: simultaneously sparse multiple regression. Our approach uses a simple idea: while any one structure might not capture the data, a superposition of structural classes might. Our method thus searches for a parameter matrix that can be decomposed into a row-sparse matrix (corresponding to the overlapping or shared features) and an elementwise sparse matrix (corresponding to the non-shared features). As we show both theoretically and empirically, with this simple ﬁx we are able to leverage any extent of shared features, while allowing disparities in support and values of the parameters, so that we are always better than both the Lasso or block-sparse regularizers (at times remarkably so). The rest of the paper is organized as follows: In Sec 2. basic deﬁnitions and setup of the problem are presented. Main results of the paper is discussed in sec 3. Experimental results and simulations are demonstrated in Sec 4. Notation: For any matrix M , we denote its j th row as Mj , and its k-th column as M (k) . The set of all non-zero rows (i.e. all rows with at least one non-zero element) is denoted by RowSupp(M ) (k) and its support by Supp(M ). Also, for any matrix M , let M 1,1 := j,k |Mj |, i.e. the sums of absolute values of the elements, and M 1,∞ := j 2 Mj ∞ where, Mj ∞ (k) := maxk |Mj |. 2 Problem Set-up and Our Method Multiple regression. We consider the following standard multiple linear regression model: ¯ y (k) = X (k) θ(k) + w(k) , k = 1, . . . , r, where y (k) ∈ Rn is the response for the k-th task, regressed on the design matrix X (k) ∈ Rn×p (possibly different across tasks), while w(k) ∈ Rn is the noise vector. We assume each w(k) is drawn independently from N (0, σ 2 ). The total number of tasks or target variables is r, the number of features is p, while the number of samples we have for each task is n. For notational convenience, ¯ we collate these quantities into matrices Y ∈ Rn×r for the responses, Θ ∈ Rp×r for the regression n×r parameters and W ∈ R for the noise. ¯ Dirty Model. In this paper we are interested in estimating the true parameter Θ from data by lever¯ aging any (unknown) extent of simultaneous-sparsity. In particular, certain rows of Θ would have many non-zero entries, corresponding to features shared by several tasks (“shared” rows), while certain rows would be elementwise sparse, corresponding to those features which are relevant for some tasks but not all (“non-shared rows”), while certain rows would have all zero entries, corresponding to those features that are not relevant to any task. We are interested in estimators Θ that automatically adapt to different levels of sharedness, and yet enjoy the following guarantees: Support recovery: We say an estimator Θ successfully recovers the true signed support if ¯ sign(Supp(Θ)) = sign(Supp(Θ)). We are interested in deriving sufﬁcient conditions under which ¯ the estimator succeeds. We note that this is stronger than merely recovering the row-support of Θ, which is union of its supports for the different tasks. In particular, denoting Uk for the support of the ¯ k-th column of Θ, and U = k Uk . Error bounds: We are also interested in providing bounds on the elementwise ℓ∞ norm error of the estimator Θ, ¯ Θ−Θ 2.1 ∞ = max max j=1,...,p k=1,...,r (k) Θj (k) ¯ − Θj . Our Method Our method explicitly models the dirty block-sparse structure. We estimate a sum of two parameter matrices B and S with different regularizations for each: encouraging block-structured row-sparsity in B and elementwise sparsity in S. The corresponding “clean” models would either just use blocksparse regularizations [8, 10] or just elementwise sparsity regularizations [14, 18], so that either method would perform better in certain suited regimes. Interestingly, as we will see in the main results, by explicitly allowing to have both block-sparse and elementwise sparse component, we are ¯ able to outperform both classes of these “clean models”, for all regimes Θ. Algorithm 1 Dirty Block Sparse Solve the following convex optimization problem: (S, B) ∈ arg min S,B 1 2n r k=1 y (k) − X (k) S (k) + B (k) 2 2 + λs S 1,1 + λb B 1,∞ . (1) Then output Θ = B + S. 3 Main Results and Their Consequences We now provide precise statements of our main results. A number of recent results have shown that the Lasso [14, 18] and ℓ1 /ℓ∞ block-regularization [8] methods succeed in recovering signed supports with controlled error bounds under high-dimensional scaling regimes. Our ﬁrst two theorems extend these results to our dirty model setting. In Theorem 1, we consider the case of deterministic design matrices X (k) , and provide sufﬁcient conditions guaranteeing signed support recovery, and elementwise ℓ∞ norm error bounds. In Theorem 2, we specialize this theorem to the case where the 3 rows of the design matrices are random from a general zero mean Gaussian distribution: this allows us to provide scaling on the number of observations required in order to guarantee signed support recovery and bounded elementwise ℓ∞ norm error. Our third result is the most interesting in that it explicitly quantiﬁes the performance gains of our method vis-a-vis Lasso and the ℓ1 /ℓ∞ block-regularization method. Since this entailed ﬁnding the precise constants underlying earlier theorems, and a correspondingly more delicate analysis, we follow Negahban and Wainwright [8] and focus on the case where there are two-tasks (i.e. r = 2), and where we have standard Gaussian design matrices as in Theorem 2. Further, while each of two tasks depends on s features, only a fraction α of these are common. It is then interesting to see how the behaviors of the different regularization methods vary with the extent of overlap α. Comparisons. Negahban and Wainwright [8] show that there is actually a “phase transition” in the scaling of the probability of successful signed support-recovery with the number of observations. n Denote a particular rescaling of the sample-size θLasso (n, p, α) = s log(p−s) . Then as Wainwright [18] show, when the rescaled number of samples scales as θLasso > 2 + δ for any δ > 0, Lasso succeeds in recovering the signed support of all columns with probability converging to one. But when the sample size scales as θLasso < 2−δ for any δ > 0, Lasso fails with probability converging to one. For the ℓ1 /ℓ∞ -reguralized multiple linear regression, deﬁne a similar rescaled sample size n θ1,∞ (n, p, α) = s log(p−(2−α)s) . Then as Negahban and Wainwright [8] show there is again a transition in probability of success from near zero to near one, at the rescaled sample size of θ1,∞ = (4 − 3α). Thus, for α < 2/3 (“less sharing”) Lasso would perform better since its transition is at a smaller sample size, while for α > 2/3 (“more sharing”) the ℓ1 /ℓ∞ regularized method would perform better. As we show in our third theorem, the phase transition for our method occurs at the rescaled sample size of θ1,∞ = (2 − α), which is strictly before either the Lasso or the ℓ1 /ℓ∞ regularized method except for the boundary cases: α = 0, i.e. the case of no sharing, where we match Lasso, and for α = 1, i.e. full sharing, where we match ℓ1 /ℓ∞ . Everywhere else, we strictly outperform both methods. Figure 3 shows the empirical performance of each of the three methods; as can be seen, they agree very well with the theoretical analysis. (Further details in the experiments Section 4). 3.1 Sufﬁcient Conditions for Deterministic Designs We ﬁrst consider the case where the design matrices X (k) for k = 1, · · ·, r are deterministic, and start by specifying the assumptions we impose on the model. We note that similar sufﬁcient conditions for the deterministic X (k) ’s case were imposed in papers analyzing Lasso [18] and block-regularization methods [8, 10]. (k) A0 Column Normalization Xj 2 ≤ √ 2n for all j = 1, . . . , p, k = 1, . . . , r. ¯ Let Uk denote the support of the k-th column of Θ, and U = supports for each task. Then we require that k r A1 Incoherence Condition γb := 1 − max c j∈U (k) (k) Xj , XUk (k) (k) XUk , XUk Uk denote the union of −1 c We will also ﬁnd it useful to deﬁne γs := 1−max1≤k≤r maxj∈Uk (k) > 0. 1 k=1 (k) Xj , XUk Note that by the incoherence condition A1, we have γs > 0. A2 Eigenvalue Condition Cmin := min λmin 1≤k≤r A3 Boundedness Condition Dmax := max 1≤k≤r 1 (k) (k) XUk , XUk n 1 (k) (k) XUk , XUk n (k) (k) XUk , XUk −1 . 1 > 0. −1 ∞,1 < ∞. Further, we require the regularization penalties be set as λs > 2(2 − γs )σ log(pr) √ γs n and 4 λb > 2(2 − γb )σ log(pr) √ . γb n (2) 1 0.9 0.8 0.8 Dirty Model L1/Linf Reguralizer Probability of Success Probability of Success 1 0.9 0.7 0.6 0.5 0.4 LASSO 0.3 0.2 0 0.5 1 1.5 1.7 2 2.5 Control Parameter θ 3 3.1 3.5 0.6 0.5 0.4 L1/Linf Reguralizer 0.3 LASSO 0.2 p=128 p=256 p=512 0.1 Dirty Model 0.7 p=128 p=256 p=512 0.1 0 0.5 4 1 1.333 (a) α = 0.3 1.5 2 Control Parameter θ (b) α = 2.5 3 2 3 1 0.9 Dirty Model Probability of Success 0.8 0.7 L1/Linf Reguralizer 0.6 0.5 LASSO 0.4 0.3 0.2 p=128 p=256 p=512 0.1 0 0.5 1 1.2 1.5 1.6 2 Control Parameter θ 2.5 (c) α = 0.8 Figure 1: Probability of success in recovering the true signed support using dirty model, Lasso and ℓ1 /ℓ∞ regularizer. For a 2-task problem, the probability of success for different values of feature-overlap fraction α is plotted. As we can see in the regimes that Lasso is better than, as good as and worse than ℓ1 /ℓ∞ regularizer ((a), (b) and (c) respectively), the dirty model outperforms both of the methods, i.e., it requires less number of observations for successful recovery of the true signed support compared to Lasso and ℓ1 /ℓ∞ regularizer. Here p s = ⌊ 10 ⌋ always. Theorem 1. Suppose A0-A3 hold, and that we obtain estimate Θ from our algorithm with regularization parameters chosen according to (2). Then, with probability at least 1 − c1 exp(−c2 n) → 1, we are guaranteed that the convex program (1) has a unique optimum and (a) The estimate Θ has no false inclusions, and has bounded ℓ∞ norm error so that ¯ Supp(Θ) ⊆ Supp(Θ), and ¯ Θ−Θ ∞,∞ 4σ 2 log (pr) + λs Dmax . n Cmin ≤ bmin ¯ (b) sign(Supp(Θ)) = sign Supp(Θ) provided that min ¯ (j,k)∈Supp(Θ) ¯(k) θj > bmin . Here the positive constants c1 , c2 depend only on γs , γb , λs , λb and σ, but are otherwise independent of n, p, r, the problem dimensions of interest. Remark: Condition (a) guarantees that the estimate will have no false inclusions; i.e. all included features will be relevant. If in addition, we require that it have no false exclusions and that recover the support exactly, we need to impose the assumption in (b) that the non-zero elements are large enough to be detectable above the noise. 3.2 General Gaussian Designs Often the design matrices consist of samples from a Gaussian ensemble. Suppose that for each task (k) k = 1, . . . , r the design matrix X (k) ∈ Rn×p is such that each row Xi ∈ Rp is a zero-mean Gaussian random vector with covariance matrix Σ(k) ∈ Rp×p , and is independent of every other (k) row. Let ΣV,U ∈ R|V|×|U | be the submatrix of Σ(k) with rows corresponding to V and columns to U . We require these covariance matrices to satisfy the following conditions: r C1 Incoherence Condition γb := 1 − max c j∈U (k) (k) Σj,Uk , ΣUk ,Uk k=1 5 −1 >0 1 C2 Eigenvalue Condition Cmin := min λmin Σ(k),Uk Uk > 0 so that the minimum eigenvalue 1≤k≤r is bounded away from zero. C3 Boundedness Condition Dmax := (k) ΣUk ,Uk −1 ∞,1 < ∞. These conditions are analogues of the conditions for deterministic designs; they are now imposed on the covariance matrix of the (randomly generated) rows of the design matrix. Further, deﬁning s := maxk |Uk |, we require the regularization penalties be set as 1/2 λs > 1/2 4σ 2 Cmin log(pr) √ γs nCmin − 2s log(pr) and λb > 4σ 2 Cmin r(r log(2) + log(p)) . √ γb nCmin − 2sr(r log(2) + log(p)) (3) Theorem 2. Suppose assumptions C1-C3 hold, and that the number of samples scale as n > max 2s log(pr) 2sr r log(2)+log(p) 2 2 Cmin γs , Cmin γb . Suppose we obtain estimate Θ from algorithm (3). Then, with probability at least 1 − c1 exp (−c2 (r log(2) + log(p))) − c3 exp(−c4 log(rs)) → 1 for some positive numbers c1 − c4 , we are guaranteed that the algorithm estimate Θ is unique and satisﬁes the following conditions: (a) the estimate Θ has no false inclusions, and has bounded ℓ∞ norm error so that ¯ Supp(Θ) ⊆ Supp(Θ), and ¯ Θ−Θ ∞,∞ ≤ 50σ 2 log(rs) + λs nCmin 4s √ + Dmax . Cmin n gmin ¯ (b) sign(Supp(Θ)) = sign Supp(Θ) provided that 3.3 min ¯ (j,k)∈Supp(Θ) ¯(k) θj > gmin . Sharp Transition for 2-Task Gaussian Designs This is one of the most important results of this paper. Here, we perform a more delicate and ﬁner analysis to establish precise quantitative gains of our method. We focus on the special case where r = 2 and the design matrix has rows generated from the standard Gaussian distribution N (0, In×n ), so that C1 − C3 hold, with Cmin = Dmax = 1. As we will see both analytically and experimentally, our method strictly outperforms both Lasso and ℓ1 /ℓ∞ -block-regularization over for all cases, except at the extreme endpoints of no support sharing (where it matches that of Lasso) and full support sharing (where it matches that of ℓ1 /ℓ∞ ). We now present our analytical results; the empirical comparisons are presented next in Section 4. The results will be in terms of a particular rescaling of the sample size n as θ(n, p, s, α) := n . (2 − α)s log (p − (2 − α)s) We will also require the assumptions that 4σ 2 (1 − F1 λs > F2 λb > s/n)(log(r) + log(p − (2 − α)s)) 1/2 (n)1/2 − (s)1/2 − ((2 − α) s (log(r) + log(p − (2 − α)s)))1/2 4σ 2 (1 − s/n)r(r log(2) + log(p − (2 − α)s)) , 1/2 (n)1/2 − (s)1/2 − ((1 − α/2) sr (r log(2) + log(p − (2 − α)s)))1/2 . Theorem 3. Consider a 2-task regression problem (n, p, s, α), where the design matrix has rows generated from the standard Gaussian distribution N (0, In×n ). 6 Suppose maxj∈B∗ ∗(1) Θj − ∗(2) Θj = o(λs ), where B ∗ is the submatrix of Θ∗ with rows where both entries are non-zero. Then the estimate Θ of the problem (1) satisﬁes the following: (Success) Suppose the regularization coefﬁcients satisfy F1 − F2. Further, assume that the number of samples scales as θ(n, p, s, α) > 1. Then, with probability at least 1 − c1 exp(−c2 n) for some positive numbers c1 and c2 , we are guaranteed that Θ satisﬁes the support-recovery and ℓ∞ error bound conditions (a-b) in Theorem 2. ˆ ˆ (Failure) If θ(n, p, s, α) < 1 there is no solution (B, S) for any choices of λs and λb such that ¯ sign Supp(Θ) = sign Supp(Θ) . We note that we require the gap ∗(1) Θj ∗(2) − Θj to be small only on rows where both entries are non-zero. As we show in a more general theorem in the appendix, even in the case where the gap is large, the dependence of the sample scaling on the gap is quite weak. 4 Empirical Results In this section, we investigate the performance of our dirty block sparse estimator on synthetic and real-world data. The synthetic experiments explore the accuracy of Theorem 3, and compare our estimator with LASSO and the ℓ1 /ℓ∞ regularizer. We see that Theorem 3 is very accurate indeed. Next, we apply our method to a real world datasets containing hand-written digits for classiﬁcation. Again we compare against LASSO and the ℓ1 /ℓ∞ . (a multi-task regression dataset) with r = 2 tasks. In both of this real world dataset, we show that dirty model outperforms both LASSO and ℓ1 /ℓ∞ practically. For each method, the parameters are chosen via cross-validation; see supplemental material for more details. 4.1 Synthetic Data Simulation We consider a r = 2-task regression problem as discussed in Theorem 3, for a range of parameters (n, p, s, α). The design matrices X have each entry being i.i.d. Gaussian with mean 0 and variance 1. For each ﬁxed set of (n, s, p, α), we generate 100 instances of the problem. In each instance, ¯ given p, s, α, the locations of the non-zero entries of the true Θ are chosen at randomly; each nonzero entry is then chosen to be i.i.d. Gaussian with mean 0 and variance 1. n samples are then generated from this. We then attempt to estimate using three methods: our dirty model, ℓ1 /ℓ∞ regularizer and LASSO. In each case, and for each instance, the penalty regularizer coefﬁcients are found by cross validation. After solving the three problems, we compare the signed support of the solution with the true signed support and decide whether or not the program was successful in signed support recovery. We describe these process in more details in this section. Performance Analysis: We ran the algorithm for ﬁve different values of the overlap ratio α ∈ 2 {0.3, 3 , 0.8} with three different number of features p ∈ {128, 256, 512}. For any instance of the ˆ ¯ problem (n, p, s, α), if the recovered matrix Θ has the same sign support as the true Θ, then we count it as success, otherwise failure (even if one element has different sign, we count it as failure). As Theorem 3 predicts and Fig 3 shows, the right scaling for the number of oservations is n s log(p−(2−α)s) , where all curves stack on the top of each other at 2 − α. Also, the number of observations required by dirty model for true signed support recovery is always less than both LASSO and ℓ1 /ℓ∞ regularizer. Fig 1(a) shows the probability of success for the case α = 0.3 (when LASSO is better than ℓ1 /ℓ∞ regularizer) and that dirty model outperforms both methods. When α = 2 3 (see Fig 1(b)), LASSO and ℓ1 /ℓ∞ regularizer performs the same; but dirty model require almost 33% less observations for the same performance. As α grows toward 1, e.g. α = 0.8 as shown in Fig 1(c), ℓ1 /ℓ∞ performs better than LASSO. Still, dirty model performs better than both methods in this case as well. 7 4 p=128 p=256 p=512 Phase Transition Threshold 3.5 L1/Linf Regularizer 3 2.5 LASSO 2 Dirty Model 1.5 1 0 0.1 0.2 0.3 0.4 0.5 0.6 Shared Support Parameter α 0.7 0.8 0.9 1 Figure 2: Veriﬁcation of the result of the Theorem 3 on the behavior of phase transition threshold by changing the parameter α in a 2-task (n, p, s, α) problem for dirty model, LASSO and ℓ1 /ℓ∞ regularizer. The y-axis p n is s log(p−(2−α)s) , where n is the number of samples at which threshold was observed. Here s = ⌊ 10 ⌋. Our dirty model method shows a gain in sample complexity over the entire range of sharing α. The pre-constant in Theorem 3 is also validated. n 10 20 40 Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Our Model 8.6% 0.53% B:165 B + S:171 S:18 B + S:1651 3.0% 0.56% B:211 B + S:226 S:34 B + S:2118 2.2% 0.57% B:270 B + S:299 S:67 B + S:2761 ℓ1 /ℓ∞ 9.9% 0.64% 170 1700 3.5% 0.62% 217 2165 3.2% 0.68% 368 3669 LASSO 10.8% 0.51% 123 539 4.1% 0.68% 173 821 2.8% 0.85% 354 2053 Table 1: Handwriting Classiﬁcation Results for our model, ℓ1 /ℓ∞ and LASSO Scaling Veriﬁcation: To verify that the phase transition threshold changes linearly with α as predicted by Theorem 3, we plot the phase transition threshold versus α. For ﬁve different values of 2 α ∈ {0.05, 0.3, 3 , 0.8, 0.95} and three different values of p ∈ {128, 256, 512}, we ﬁnd the phase transition threshold for dirty model, LASSO and ℓ1 /ℓ∞ regularizer. We consider the point where the probability of success in recovery of signed support exceeds 50% as the phase transition threshold. We ﬁnd this point by interpolation on the closest two points. Fig 2 shows that phase transition threshold for dirty model is always lower than the phase transition for LASSO and ℓ1 /ℓ∞ regularizer. 4.2 Handwritten Digits Dataset We use the handwritten digit dataset [1], containing features of handwritten numerals (0-9) extracted from a collection of Dutch utility maps. This dataset has been used by a number of papers [17, 6] as a reliable dataset for handwritten recognition algorithms. There are thus r = 10 tasks, and each handwritten sample consists of p = 649 features. Table 1 shows the results of our analysis for different sizes n of the training set . We measure the classiﬁcation error for each digit to get the 10-vector of errors. Then, we ﬁnd the average error and the variance of the error vector to show how the error is distributed over all tasks. We compare our method with ℓ1 /ℓ∞ reguralizer method and LASSO. Again, in all methods, parameters are chosen via cross-validation. For our method we separate out the B and S matrices that our method ﬁnds, so as to illustrate how many features it identiﬁes as “shared” and how many as “non-shared”. For the other methods we just report the straight row and support numbers, since they do not make such a separation. Acknowledgements We acknowledge support from NSF grant IIS-101842, and NSF CAREER program, Grant 0954059. 8 References [1] A. Asuncion and D.J. Newman. UCI Machine Learning Repository, http://www.ics.uci.edu/ mlearn/MLRepository.html. University of California, School of Information and Computer Science, Irvine, CA, 2007. [2] F. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179–1225, 2008. [3] R. Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 24(4):118–121, 2007. [4] R. Caruana. Multitask learning. Machine Learning, 28:41–75, 1997. [5] C.Zhang and J.Huang. Model selection consistency of the lasso selection in high-dimensional linear regression. Annals of Statistics, 36:1567–1594, 2008. [6] X. He and P. Niyogi. Locality preserving projections. In NIPS, 2003. [7] K. Lounici, A. B. Tsybakov, M. Pontil, and S. A. van de Geer. Taking advantage of sparsity in multi-task learning. In 22nd Conference On Learning Theory (COLT), 2009. [8] S. Negahban and M. J. Wainwright. Joint support recovery under high-dimensional scaling: Beneﬁts and perils of ℓ1,∞ -regularization. In Advances in Neural Information Processing Systems (NIPS), 2008. [9] S. Negahban and M. J. Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. In ICML, 2010. [10] G. Obozinski, M. J. Wainwright, and M. I. Jordan. Support union recovery in high-dimensional multivariate regression. Annals of Statistics, 2010. [11] P. Ravikumar, H. Liu, J. Lafferty, and L. Wasserman. Sparse additive models. Journal of the Royal Statistical Society, Series B. [12] P. Ravikumar, M. J. Wainwright, and J. Lafferty. High-dimensional ising model selection using ℓ1 -regularized logistic regression. Annals of Statistics, 2009. [13] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. In Allerton Conference, Allerton House, Illinois, 2007. [14] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58(1):267–288, 1996. [15] J. A. Tropp, A. C. Gilbert, and M. J. Strauss. Algorithms for simultaneous sparse approximation. Signal Processing, Special issue on “Sparse approximations in signal and image processing”, 86:572–602, 2006. [16] B. Turlach, W.N. Venables, and S.J. Wright. Simultaneous variable selection. Techno- metrics, 27:349–363, 2005. [17] M. van Breukelen, R.P.W. Duin, D.M.J. Tax, and J.E. den Hartog. Handwritten digit recognition by combined classiﬁers. Kybernetika, 34(4):381–386, 1998. [18] M. J. Wainwright. Sharp thresholds for noisy and high-dimensional recovery of sparsity using ℓ1 -constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 55: 2183–2202, 2009. 9

4 0.093194373 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

Author: Jean Morales, Charles A. Micchelli, Massimiliano Pontil

Abstract: We study the problem of learning a sparse linear regression vector under additional conditions on the structure of its sparsity pattern. We present a family of convex penalty functions, which encode this prior knowledge by means of a set of constraints on the absolute values of the regression coefﬁcients. This family subsumes the ℓ1 norm and is ﬂexible enough to include different models of sparsity patterns, which are of practical and theoretical importance. We establish some important properties of these functions and discuss some examples where they can be computed explicitly. Moreover, we present a convergent optimization algorithm for solving regularized least squares with these penalty functions. Numerical simulations highlight the beneﬁt of structured sparsity and the advantage offered by our approach over the Lasso and other related methods.

5 0.084411882 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

Author: Hongbo Zhou, Qiang Cheng

Abstract: Regularization technique has become a principled tool for statistics and machine learning research and practice. However, in most situations, these regularization terms are not well interpreted, especially on how they are related to the loss function and data. In this paper, we propose a robust minimax framework to interpret the relationship between data and regularization terms for a large class of loss functions. We show that various regularization terms are essentially corresponding to different distortions to the original data matrix. This minimax framework includes ridge regression, lasso, elastic net, fused lasso, group lasso, local coordinate coding, multiple kernel learning, etc., as special cases. Within this minimax framework, we further give mathematically exact deﬁnition for a novel representation called sparse grouping representation (SGR), and prove a set of sufﬁcient conditions for generating such group level sparsity. Under these sufﬁcient conditions, a large set of consistent regularization terms can be designed. This SGR is essentially different from group lasso in the way of using class or group information, and it outperforms group lasso when there appears group label noise. We also provide some generalization bounds in a classiﬁcation setting. 1

6 0.066751152 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

7 0.066211641 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

8 0.059948247 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

9 0.058352452 148 nips-2010-Learning Networks of Stochastic Differential Equations

10 0.057664469 231 nips-2010-Robust PCA via Outlier Pursuit

11 0.05379438 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

12 0.053687632 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

13 0.053604309 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

14 0.049525335 217 nips-2010-Probabilistic Multi-Task Feature Selection

15 0.049001519 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

16 0.046529327 166 nips-2010-Minimum Average Cost Clustering

17 0.043690722 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

18 0.042262241 243 nips-2010-Smoothness, Low Noise and Fast Rates

19 0.041061662 73 nips-2010-Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization

20 0.040771481 254 nips-2010-Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.12), (1, 0.024), (2, 0.064), (3, 0.067), (4, 0.055), (5, -0.078), (6, -0.023), (7, 0.084), (8, -0.081), (9, -0.033), (10, 0.033), (11, 0.085), (12, -0.08), (13, 0.054), (14, 0.025), (15, -0.046), (16, 0.013), (17, 0.07), (18, 0.022), (19, 0.012), (20, -0.003), (21, 0.027), (22, 0.028), (23, 0.1), (24, 0.02), (25, -0.07), (26, -0.013), (27, 0.029), (28, -0.007), (29, -0.042), (30, -0.026), (31, -0.03), (32, -0.099), (33, 0.015), (34, 0.084), (35, 0.017), (36, 0.08), (37, 0.053), (38, 0.058), (39, 0.014), (40, -0.02), (41, 0.027), (42, -0.073), (43, 0.037), (44, 0.021), (45, -0.065), (46, -0.02), (47, 0.087), (48, 0.065), (49, 0.076)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.91702259 172 nips-2010-Multi-Stage Dantzig Selector

Author: Ji Liu, Peter Wonka, Jieping Ye

2 0.77207553 5 nips-2010-A Dirty Model for Multi-task Learning

Author: Ali Jalali, Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar

3 0.70080864 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

Author: Seunghak Lee, Jun Zhu, Eric P. Xing

Abstract: To understand the relationship between genomic variations among population and complex diseases, it is essential to detect eQTLs which are associated with phenotypic effects. However, detecting eQTLs remains a challenge due to complex underlying mechanisms and the very large number of genetic loci involved compared to the number of samples. Thus, to address the problem, it is desirable to take advantage of the structure of the data and prior information about genomic locations such as conservation scores and transcription factor binding sites. In this paper, we propose a novel regularized regression approach for detecting eQTLs which takes into account related traits simultaneously while incorporating many regulatory features. We ﬁrst present a Bayesian network for a multi-task learning problem that includes priors on SNPs, making it possible to estimate the signiﬁcance of each covariate adaptively. Then we ﬁnd the maximum a posteriori (MAP) estimation of regression coefﬁcients and estimate weights of covariates jointly. This optimization procedure is efﬁcient since it can be achieved by using a projected gradient descent and a coordinate descent procedure iteratively. Experimental results on simulated and real yeast datasets conﬁrm that our model outperforms previous methods for ﬁnding eQTLs.

4 0.68848383 265 nips-2010-The LASSO risk: asymptotic results and real world examples

Author: Mohsen Bayati, José Pereira, Andrea Montanari

5 0.67511994 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

Author: Jean Morales, Charles A. Micchelli, Massimiliano Pontil

6 0.64085782 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

7 0.63301361 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

8 0.53982925 148 nips-2010-Learning Networks of Stochastic Differential Equations

9 0.53553027 45 nips-2010-CUR from a Sparse Optimization Viewpoint

10 0.48548293 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

11 0.46099818 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

12 0.43176472 154 nips-2010-Learning sparse dynamic linear systems using stable spline kernels and exponential hyperpriors

13 0.40951395 289 nips-2010-b-Bit Minwise Hashing for Estimating Three-Way Similarities

14 0.40470231 41 nips-2010-Block Variable Selection in Multivariate Regression and High-dimensional Causal Inference

15 0.40437487 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

16 0.39869857 217 nips-2010-Probabilistic Multi-Task Feature Selection

17 0.38789758 108 nips-2010-Graph-Valued Regression

18 0.37878942 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

19 0.37672204 178 nips-2010-Multivariate Dyadic Regression Trees for Sparse Learning Problems

20 0.36746603 231 nips-2010-Robust PCA via Outlier Pursuit

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.012), (13, 0.042), (17, 0.024), (27, 0.06), (30, 0.057), (35, 0.052), (39, 0.259), (45, 0.165), (50, 0.042), (52, 0.061), (60, 0.031), (77, 0.049), (90, 0.032)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.75257111 130 nips-2010-Interval Estimation for Reinforcement-Learning Algorithms in Continuous-State Domains

Author: Martha White, Adam White

Abstract: The reinforcement learning community has explored many approaches to obtaining value estimates and models to guide decision making; these approaches, however, do not usually provide a measure of conﬁdence in the estimate. Accurate estimates of an agent’s conﬁdence are useful for many applications, such as biasing exploration and automatically adjusting parameters to reduce dependence on parameter-tuning. Computing conﬁdence intervals on reinforcement learning value estimates, however, is challenging because data generated by the agentenvironment interaction rarely satisﬁes traditional assumptions. Samples of valueestimates are dependent, likely non-normally distributed and often limited, particularly in early learning when conﬁdence estimates are pivotal. In this work, we investigate how to compute robust conﬁdences for value estimates in continuous Markov decision processes. We illustrate how to use bootstrapping to compute conﬁdence intervals online under a changing policy (previously not possible) and prove validity under a few reasonable assumptions. We demonstrate the applicability of our conﬁdence estimation algorithms with experiments on exploration, parameter estimation and tracking. 1

same-paper 2 0.74999946 172 nips-2010-Multi-Stage Dantzig Selector

Author: Ji Liu, Peter Wonka, Jieping Ye

3 0.74350011 105 nips-2010-Getting lost in space: Large sample analysis of the resistance distance

Author: Ulrike V. Luxburg, Agnes Radl, Matthias Hein

Abstract: The commute distance between two vertices in a graph is the expected time it takes a random walk to travel from the ﬁrst to the second vertex and back. We study the behavior of the commute distance as the size of the underlying graph increases. We prove that the commute distance converges to an expression that does not take into account the structure of the graph at all and that is completely meaningless as a distance function on the graph. Consequently, the use of the raw commute distance for machine learning purposes is strongly discouraged for large graphs and in high dimensions. As an alternative we introduce the ampliﬁed commute distance that corrects for the undesired large sample effects. 1

4 0.73679394 182 nips-2010-New Adaptive Algorithms for Online Classification

Author: Francesco Orabona, Koby Crammer

Abstract: We propose a general framework to online learning for classiﬁcation problems with time-varying potential functions in the adversarial setting. This framework allows to design and prove relative mistake bounds for any generic loss function. The mistake bounds can be specialized for the hinge loss, allowing to recover and improve the bounds of known online classiﬁcation algorithms. By optimizing the general bound we derive a new online classiﬁcation algorithm, called NAROW, that hybridly uses adaptive- and ﬁxed- second order information. We analyze the properties of the algorithm and illustrate its performance using synthetic dataset. 1

5 0.71983135 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

Author: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari

Abstract: We develop a theory of online learning by deﬁning several complexity measures. Among them are analogues of Rademacher complexity, covering numbers and fatshattering dimension from statistical learning theory. Relationship among these complexity measures, their connection to online learning, and tools for bounding them are provided. We apply these results to various learning problems. We provide a complete characterization of online learnability in the supervised setting. 1

6 0.62751764 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

7 0.62602419 117 nips-2010-Identifying graph-structured activation patterns in networks

8 0.62081349 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

9 0.62067837 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

10 0.62050647 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing

11 0.61627603 179 nips-2010-Natural Policy Gradient Methods with Parameter-based Exploration for Control Tasks

12 0.61547023 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

13 0.61492562 265 nips-2010-The LASSO risk: asymptotic results and real world examples

14 0.61482507 200 nips-2010-Over-complete representations on recurrent neural networks can support persistent percepts

15 0.61465853 51 nips-2010-Construction of Dependent Dirichlet Processes based on Poisson Processes

16 0.61392307 5 nips-2010-A Dirty Model for Multi-task Learning

17 0.61268789 148 nips-2010-Learning Networks of Stochastic Differential Equations

18 0.60920399 155 nips-2010-Learning the context of a category

19 0.60836625 18 nips-2010-A novel family of non-parametric cumulative based divergences for point processes

20 0.60832828 258 nips-2010-Structured sparsity-inducing norms through submodular functions