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

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

Source: pdf

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.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu 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. [sent-4, score-0.138]

2 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. [sent-6, score-0.474]

3 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. [sent-7, score-0.45]

4 Experimental results on simulated and real yeast datasets conﬁrm that our model outperforms previous methods for ﬁnding eQTLs. [sent-11, score-0.125]

5 1 Introduction One of the fundamental problems in computational biology is to understand associations between genomic variations and phenotypic effects. [sent-12, score-0.166]

6 The most common genetic variations are single nucleotide polymorphisms (SNPs), and many association studies have been conducted to ﬁnd SNPs that cause phenotypic variations such as diseases or gene-expression traits [1]. [sent-13, score-0.561]

7 However, association mapping of causal QTLs or eQTLs remains challenging as the variation of complex traits is a result of contributions of many genomic variations. [sent-14, score-0.547]

8 Second, we need techniques to take advantage of prior biological knowledge to improve the performance of detecting eQTLs. [sent-17, score-0.13]

9 To address the ﬁrst problem, Lasso is a widely used technique for high-dimensional association mapping problems, which can yield a sparse and easily interpretable solution via an ℓ1 regularization [2]. [sent-18, score-0.146]

10 If we have multiple related traits it would be beneﬁcial to estimate eQTLs jointly since we can share information among related traits. [sent-20, score-0.345]

11 1 shows some prior knowledge on SNPs in a genome including transcription factor binding sites (TFBS), 5’ UTR and exon, which play important roles for the regulation of genes. [sent-22, score-0.371]

12 Intuitively, if SNPs are located on these regions, they are more likely to be true eQTLs compared to those on regions without such annotations since they are related to genes or gene regulations. [sent-24, score-0.193]

13 Thus, it would be desirable to penalize regression coefﬁcients less corresponding 1 SNPs Chromosome Transcription factor binding site Exon 5’ UTR Annotation Figure 1: Examples of prior knowledge on SNPs including transcription factor binding sites, 5’ UTR and exon. [sent-25, score-0.483]

14 Here association SNPs are denoted by red arrows (best viewed in color), showing that SNPs on regions with regulatory features are more likely to be associated with traits. [sent-27, score-0.22]

15 This paper presents a novel regularized regression approach, called adaptive multi-task Lasso, to effectively incorporate both the relatedness among multiple gene-expression traits and useful prior knowledge for challenging eQTL detection. [sent-30, score-0.622]

16 Although some methods have been developed for either adaptive or multi-task learning, to the best of our knowledge, adaptive multi-task Lasso is the ﬁrst method that can consider prior information on SNPs and multi-task learning simultaneously in one single framework. [sent-31, score-0.283]

17 For example, Lirnet uses prior knowledge on SNPs such as conservation scores, non-synonymous coding and UTR regions for a better search of association mappings [3]. [sent-32, score-0.311]

18 However, Lirnet considers the average effects of SNPs on gene modules by assuming that association SNPs are shared in a module. [sent-33, score-0.226]

19 This approach is different from multi-task learning where association SNPs are found for each trait while considering group effects over multiple traits. [sent-34, score-0.295]

20 To ﬁnd genetic markers that affect correlated traits jointly, the graph-guided fused Lasso [4] was proposed to consider networks over multiple traits within an association analysis. [sent-35, score-0.852]

21 However, graph-guided fused Lasso does not incorporate prior knowledge of genomic locations. [sent-36, score-0.18]

22 Unlike other methods, we deﬁne the adaptive multi-task Lasso as ﬁnding a MAP estimate of a Bayesian network, which provides an elegant Bayesian interpretation of our approach; the resultant optimization problem is efﬁciently solved with an alternating minimization procedure. [sent-37, score-0.159]

23 Finally, we present empirical results on both simulated and real yeast eQTL datasets, which demonstrates the advantages of adaptive multi-task Lasso over many other competitors. [sent-38, score-0.245]

24 We have K related gene traits and Yik represents the gene expression level of k-th gene of i-th individual for k = 1, . [sent-46, score-0.576]

25 In our setting, we assume that the K traits are related to each other and we explore the relatedness in a multi-task learning framework. [sent-50, score-0.375]

26 To achieve the relatedness among tasks via grouping effects [5], we can use any clustering algorithms such as spectral clustering or hierarchical clustering. [sent-51, score-0.165]

27 In association mapping problems, these clusters can be viewed as clusters of genes which consist of regulatory networks or pathways [4]. [sent-52, score-0.287]

28 i Xij /N = 0 and Now, the open question is how we can devise an appropriate objective function over β that could effectively consider the desirable group effects over multiple traits and incorporate useful prior knowledge, as we have stated. [sent-59, score-0.536]

29 1 Lasso and Multi-task Lasso Lasso [2] is a technique for estimating the regression coefﬁcients β and has been widely used for association mapping problems. [sent-62, score-0.149]

30 Due to the singularity at the origin, the ℓ1 regularization (Lasso penalty) can yield a stable and sparse solution, which is desirable for association mapping problems because in most cases we have p ≫ N and there exists only a small number of eQTLs. [sent-67, score-0.179]

31 The proposed adaptive multi-task Lasso, as to be presented, is an extension of the multi-task Lasso to perform joint group-wise and within-group feature selection and incorporate the useful prior knowledge for effective association analysis. [sent-78, score-0.36]

32 2 Adaptive Multi-task Lasso Now, we formally introduce the adaptive multi-task Lasso. [sent-80, score-0.12]

33 For clarity, we ﬁrst deﬁne the sparse multi-task Lasso with ﬁxed scaling parameters, which will be a sub-problem of the adaptive multi-task Lasso, as we shall see. [sent-81, score-0.201]

34 Finally, as to be extended, unlike Lasso and multi-task Lasso which treat βj equally or with a ﬁxed scaling parameter, we can adaptively penalize each βj according to prior knowledge on covariates in such a way that SNPs having desirable features are less penalized (see Fig. [sent-91, score-0.252]

35 To incorporate the prior knowledge as we have stated, we propose to automatically learn the scaling parameters (θ, ρ) from data. [sent-93, score-0.149]

36 For example ftj can be a conservation score of j-th SNP or one if the SNP is located on TFBS, zero otherwise. [sent-97, score-0.259]

37 Similarly, to achieve a framework θ that enjoys an elegant Bayesian interpretation, we β Y deﬁne a Bayesian network and treat the adaptive ρ multi-task learning problem as ﬁnding its MAP f T ν estimate. [sent-105, score-0.159]

38 2 in order to compute the MAP estimate of β under adaptive scaling parameters, Figure 2: Graphical model representation of {θ, ρ}. [sent-107, score-0.173]

39 We deﬁne the conditional probability of β adaptive multi-task Lasso. [sent-108, score-0.12]

40 Remark 2 Our method also differs from the adaptive Lasso [7] , transfer learning with meta-priors [8] and the Bayesian Lasso [9]. [sent-121, score-0.12]

41 Thus we have group sparsity across tasks as well as sparsity in each group but they cannot induce group sparsity across different tasks. [sent-125, score-0.306]

42 Finally, the Bayesian Lasso [9] does not have the grouping effects in multiple traits and the priors used usually do not consider domain knowledge. [sent-126, score-0.406]

43 3 Optimization: an Alternating Minimization Approach Now, we solve the adaptive multi-task Lasso problem (6). [sent-127, score-0.12]

44 We can solve it using a coordinate descent procedure, which has been used to optimize the sparse group Lasso [14]. [sent-140, score-0.138]

45 Our problem is different from the sparse group Lasso in the sense that the sparse group Lasso includes group penalty over multiple covariates for a single trait, while adaptive multi-task Lasso considers group effects over multiple traits. [sent-141, score-0.52]

46 As summarized in Algorithm 1, the general optimization procedure is as follows: for each j, we check the group sparsity condition that βj = 0. [sent-143, score-0.133]

47 Note that gj = k βj βj 2 if βj = 0, otherwise gj 2 k k ≤ 1; and hk = sign(βj ) if βj = 0, otherwise hk ∈ [−1, 1]. [sent-150, score-0.388]

48 j j Then, we check the group sparsity that βj = 0. [sent-151, score-0.133]

49 (8), and we have, k k Xr βr = λ2 ρj gj +λ1 θj hk , and ||gj ||2 = j 2 T T Xj Y k −Xj r=j K 1 λ2 ρ 2 2 j k=1 k Xr βr − λ1 θj hk )2 . [sent-153, score-0.236]

50 j T T (Xj Y k − Xj r=j According to subgradient conditions, we need to have a gj that satisﬁes the less than inequality gj 2 < 1; otherwise, βj will be non-zero. [sent-154, score-0.188]

51 Since gj is a function of hj , it sufﬁces to check whether 2 the minimal square ℓ2 -norm of gj is less than 1. [sent-155, score-0.264]

52 t hj , which gives the optimal hj as, 2 hk j =   ck j λ1 θj ck if | λ1j j | ≤ 1 θ k  sign( cj ) λ1 θj (9) otherwise T T k 2 where ck =Xj Y k − Xj j r=j Xr βr . [sent-158, score-0.19]

53 (8), we have, k Xr βr = λ1 θj hk , and hk = j j T T Xj Y k − Xj r=j 1 T T (Xj Y k − Xj λ 1 θj k Xr βr ). [sent-162, score-0.142]

54 4 Simulation Study To conﬁrm the behavior of our model, we run the adaptive multi-task Lasso and other methods on our simulated dataset (p=100, K=10). [sent-177, score-0.12]

55 We ﬁrst randomly select 100 SNPs from 114 yeast genotypes from the yeast eQTL dataset [16]. [sent-178, score-0.25]

56 Three sets of randomly selected four SNPs are associated with three trait clusters (1 − 3), (4 − 6), (7 − 10), respectively. [sent-181, score-0.122]

57 One SNP is associated with two clusters (1 − 3) and (4 − 6), and one causal SNP is for all traits (1 − 10). [sent-182, score-0.379]

58 For all association SNPs we set identical association strength from 0. [sent-183, score-0.269]

59 For visualization, we present normalized absolute values of regression coefﬁcients and darker colors imply stronger association with traits. [sent-207, score-0.149]

60 For each matrix, X-axis represents traits (1-10) and Y-axis represents SNPs (1-100). [sent-208, score-0.345]

61 3 shows the estimated β matrix by various methods including AML (adaptive multi-task Lasso), SML (sparse multi-task Lasso which is AML without adaptive weights), A+ℓ1 /ℓ2 (AML without Lasso penalty), Single SNP [17], Lasso and ℓ1 /ℓ∞ (multi-task learning with ℓ1 /ℓ∞ norm). [sent-211, score-0.12]

62 In this ﬁgure, X-axis represents traits (1-10) and Y-axis represents SNPs (1-100). [sent-212, score-0.345]

63 λ1 and λ2 for AML) were determined by holdout validation, and we set association strength to 0. [sent-215, score-0.178]

64 8 prior to run AML, SML, A+ℓ1 /ℓ2 and ℓ1 /ℓ∞ , and Single SNP and Lasso were analyzed for each trait separately. [sent-218, score-0.131]

65 It is not surprising since hierarchical clustering reproduced true trait clusters and true β could be detected without considering single SNP level sparsity in each group. [sent-221, score-0.232]

66 3, we could observe that adaptive weights improve the performance signiﬁcantly. [sent-227, score-0.16]

67 The results are based on 100 simulations for each association strength 0. [sent-234, score-0.151]

68 Also, discrete features are the most important since they discriminate true association SNPs with a high probability 0. [sent-241, score-0.146]

69 5 1 1 − Specificity Figure 5: ROC curves of various methods as association strength varies (a) 0. [sent-269, score-0.151]

70 (a,b) Results on clustered data, where correct groups of gene traits are found using hierarchical clustering (cutoff = 0. [sent-274, score-0.488]

71 5, we generated ROC curves for association strength of 0. [sent-279, score-0.151]

72 Using hierarchical clustering we could correctly ﬁnd three clusters of gene traits at cutoff 0. [sent-285, score-0.555]

73 As association strength increased, the performance of multi-task learning methods improved quickly while methods based on a single trait such as Lasso and Single SNP showed gradual increase of performance. [sent-292, score-0.239]

74 5 Yeast eQTL dataset We analyze the yeast eQTL dataset [16] that contains expression levels of 5,637 genes and 2,956 SNPs. [sent-300, score-0.176]

75 The genotype data include genetic variants of 114 yeast strains that are progenies of the standard laboratory strain (BY) and a wild strain (RM). [sent-301, score-0.223]

76 For prior biological knowledge on SNPs used for adaptive multi-task Lasso, we downloaded 12 features from Saccharomyces Genome Database (http://www. [sent-304, score-0.254]

77 For a discrete feature, we set its value as ftj = s(2) if the feature is found on the j-th SNP, ftj = s(1) otherwise. [sent-307, score-0.174]

78 6 represents ω learned from the yeast eQTL dataset (ν is almost identical to ω). [sent-311, score-0.125]

79 The features are ncRNA (f1 ), noncoding exon (f2 ), snRNA (f3 ), tRNA (f4 ), intron (f5 ), binding site (f6 ), 5’ UTR intron (f7 ), LTR retrotransposon (f8 ), ARS (f9 ), snoRNA (f10 ), transposable element gene (f11 ) and conservation score (f12 ). [sent-312, score-0.646]

80 Five discrete features turn out to be important including ncRNA, snRNA, binding site, 5’ UTR intron and snoRNA as well as one f f f f f f f f f f f f 1 2 3 4 5 6 7 8 9 10 11 12 continuous feature, i. [sent-313, score-0.226]

81 For example, ncRNA, Figure 6: Learned weights of ω on the yeast snRNA and snoRNA are potentially important for gene eQTL dataset. [sent-317, score-0.242]

82 Also, conservation score would be signiﬁcant since mutation in conserved region is more likely to result in phenotypic effects. [sent-319, score-0.208]

83 5 β ncRNA snRNA binding sites five prime UTR intron conservation scores 3 2. [sent-331, score-0.395]

84 5 0 0 10 20 30 40 50 60 70 80 90 100 110 120 SNPs Figure 7: Plot of 121 SNPs on chromosome 1 and 2 vs the number of genes affected by the SNPs from the yeast eQTL analysis (blue bar). [sent-334, score-0.222]

85 For the four discrete priors (ncRNA, snRNA, binding site, 5’ UTR intron) we set the value to 1 if annotated, 0 otherwise. [sent-336, score-0.152]

86 Binding sites and regions with no associated traits are denoted by long green and short blue arrows. [sent-337, score-0.388]

87 We see that association mapping results were affected by both priors and data. [sent-340, score-0.148]

88 For example, genomic region indicated by blue arrow shows weak association with traits, where conservation score is low and no other annotations exist. [sent-341, score-0.39]

89 Also we can see that three SNPs located on binding sites affect a larger number of gene traits (see green arrows). [sent-342, score-0.618]

90 As an example of biological analysis, we investigate these three association SNPs. [sent-343, score-0.154]

91 The three SNPs are located on telomeres (chr1:483, chr1:229090, chr2:9425 (chromosome:coordinate)), and these genomic locations are in cis to Abf1p (autonomously replicating sequence binding factor-1) binding sites. [sent-344, score-0.39]

92 In biology, it is known that Abf1p acts as a global transcriptional regulator in yeast [19]. [sent-345, score-0.16]

93 Thus, the genomic regions in telomeres would be good candidates for novel putative eQTL hotspots that regulate the expression levels of many genes. [sent-346, score-0.18]

94 6 Conclusions In this paper, we proposed a novel regularized regression model, referred to as adaptive multi-task Lasso, which takes into account multiple traits simultaneously while weights of different covariates are learned adaptively from prior knowledge and data. [sent-349, score-0.674]

95 In our experiments on the yeast eQTL dataset, we could identify putative three eQTL hotspots with biological supports where SNPs are associated with a large number of genes. [sent-351, score-0.226]

96 A genome-wide association study identiﬁes novel risk loci for type 2 diabetes. [sent-366, score-0.145]

97 Statistical estimation of correlated genome associations to a quantitative trait network. [sent-391, score-0.144]

98 A note on the group Lasso and a sparse group Lasso. [sent-457, score-0.144]

99 The landscape of genetic complexity across 5,700 gene expression traits in yeast. [sent-473, score-0.466]

100 Genome-wide analysis of ARS (autonomously replicating sequence) binding factor 1 (Abf1p)-mediated transcriptional regulation in Saccharomyces cerevisiae. [sent-505, score-0.196]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('snps', 0.563), ('traits', 0.345), ('lasso', 0.336), ('eqtl', 0.229), ('snp', 0.215), ('aml', 0.188), ('yeast', 0.125), ('conservation', 0.123), ('utr', 0.122), ('binding', 0.122), ('adaptive', 0.12), ('association', 0.118), ('eqtls', 0.107), ('gj', 0.094), ('sml', 0.092), ('trait', 0.088), ('genomic', 0.084), ('gene', 0.077), ('intron', 0.076), ('ncrna', 0.076), ('snrna', 0.076), ('ftj', 0.074), ('hk', 0.071), ('transcription', 0.069), ('tfbs', 0.061), ('group', 0.058), ('phenotypic', 0.054), ('specificity', 0.054), ('scaling', 0.053), ('genes', 0.051), ('xr', 0.05), ('regulatory', 0.05), ('xj', 0.046), ('chromosome', 0.046), ('exon', 0.046), ('snorna', 0.046), ('hj', 0.045), ('sparsity', 0.044), ('genetic', 0.044), ('prior', 0.043), ('sites', 0.043), ('covariates', 0.043), ('genetics', 0.042), ('hotspots', 0.04), ('weights', 0.04), ('elegant', 0.039), ('regulation', 0.039), ('penalty', 0.038), ('clustering', 0.038), ('saccharomyces', 0.037), ('site', 0.036), ('xij', 0.036), ('biological', 0.036), ('transcriptional', 0.035), ('annotations', 0.034), ('clusters', 0.034), ('bayesian', 0.034), ('strength', 0.033), ('desirable', 0.033), ('cutoff', 0.033), ('lee', 0.032), ('five', 0.031), ('located', 0.031), ('check', 0.031), ('effects', 0.031), ('score', 0.031), ('xing', 0.031), ('regression', 0.031), ('brem', 0.031), ('lirnet', 0.031), ('noncoding', 0.031), ('telomeres', 0.031), ('yvert', 0.031), ('relatedness', 0.03), ('priors', 0.03), ('cients', 0.03), ('otherwise', 0.029), ('sensitivity', 0.028), ('associations', 0.028), ('genome', 0.028), ('hierarchical', 0.028), ('sparse', 0.028), ('features', 0.028), ('descent', 0.027), ('ars', 0.027), ('holdout', 0.027), ('loci', 0.027), ('strain', 0.027), ('knowledge', 0.027), ('feature', 0.026), ('incorporate', 0.026), ('rp', 0.026), ('adaptively', 0.025), ('coordinate', 0.025), ('autonomously', 0.025), ('putative', 0.025), ('coef', 0.025), ('arrows', 0.024), ('detecting', 0.024), ('map', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

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

2 0.17861256 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

3 0.14497085 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.

4 0.12808579 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

5 0.11894866 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.

6 0.11395862 247 nips-2010-Sparse Instrumental Variables (SPIV) for Genome-Wide Studies

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

8 0.10411944 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

9 0.10106235 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

10 0.070022829 224 nips-2010-Regularized estimation of image statistics by Score Matching

11 0.067922577 217 nips-2010-Probabilistic Multi-Task Feature Selection

12 0.066751152 172 nips-2010-Multi-Stage Dantzig Selector

13 0.063925996 55 nips-2010-Cross Species Expression Analysis using a Dirichlet Process Mixture Model with Latent Matchings

14 0.058112796 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

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

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

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

18 0.05207742 147 nips-2010-Learning Multiple Tasks with a Sparse Matrix-Normal Penalty

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

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

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.142), (1, 0.047), (2, 0.044), (3, 0.076), (4, 0.026), (5, -0.15), (6, -0.005), (7, 0.12), (8, -0.12), (9, -0.068), (10, -0.013), (11, 0.173), (12, -0.109), (13, 0.016), (14, 0.09), (15, -0.046), (16, -0.059), (17, 0.098), (18, 0.029), (19, -0.082), (20, -0.035), (21, 0.033), (22, 0.071), (23, 0.122), (24, -0.054), (25, 0.033), (26, -0.052), (27, -0.043), (28, -0.006), (29, -0.045), (30, 0.002), (31, -0.029), (32, 0.08), (33, -0.011), (34, 0.041), (35, 0.013), (36, 0.078), (37, 0.046), (38, 0.129), (39, -0.031), (40, -0.06), (41, 0.035), (42, -0.029), (43, 0.012), (44, 0.049), (45, 0.015), (46, -0.04), (47, 0.077), (48, 0.064), (49, -0.079)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95157784 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

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

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

Author: Hongbo Zhou, Qiang Cheng

3 0.77182603 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

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

4 0.74827009 5 nips-2010-A Dirty Model for Multi-task Learning

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

5 0.64657056 172 nips-2010-Multi-Stage Dantzig Selector

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

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

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

8 0.57187462 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

9 0.5320493 265 nips-2010-The LASSO risk: asymptotic results and real world examples

10 0.46539897 247 nips-2010-Sparse Instrumental Variables (SPIV) for Genome-Wide Studies

11 0.46203798 41 nips-2010-Block Variable Selection in Multivariate Regression and High-dimensional Causal Inference

12 0.45015711 45 nips-2010-CUR from a Sparse Optimization Viewpoint

13 0.42561275 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

14 0.40647554 148 nips-2010-Learning Networks of Stochastic Differential Equations

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

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

17 0.38794085 217 nips-2010-Probabilistic Multi-Task Feature Selection

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

19 0.36786887 147 nips-2010-Learning Multiple Tasks with a Sparse Matrix-Normal Penalty

20 0.36180988 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.037), (17, 0.038), (27, 0.05), (30, 0.059), (35, 0.08), (45, 0.144), (50, 0.044), (52, 0.031), (54, 0.295), (60, 0.016), (71, 0.039), (77, 0.05), (78, 0.011), (90, 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.72677284 111 nips-2010-Hallucinations in Charles Bonnet Syndrome Induced by Homeostasis: a Deep Boltzmann Machine Model

Author: Peggy Series, David P. Reichert, Amos J. Storkey

Abstract: The Charles Bonnet Syndrome (CBS) is characterized by complex vivid visual hallucinations in people with, primarily, eye diseases and no other neurological pathology. We present a Deep Boltzmann Machine model of CBS, exploring two core hypotheses: First, that the visual cortex learns a generative or predictive model of sensory input, thus explaining its capability to generate internal imagery. And second, that homeostatic mechanisms stabilize neuronal activity levels, leading to hallucinations being formed when input is lacking. We reproduce a variety of qualitative ﬁndings in CBS. We also introduce a modiﬁcation to the DBM that allows us to model a possible role of acetylcholine in CBS as mediating the balance of feed-forward and feed-back processing. Our model might provide new insights into CBS and also demonstrates that generative frameworks are promising as hypothetical models of cortical learning and perception. 1

same-paper 2 0.7089051 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

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

3 0.65659779 289 nips-2010-b-Bit Minwise Hashing for Estimating Three-Way Similarities

Author: Ping Li, Arnd Konig, Wenhao Gui

Abstract: Computing1 two-way and multi-way set similarities is a fundamental problem. This study focuses on estimating 3-way resemblance (Jaccard similarity) using b-bit minwise hashing. While traditional minwise hashing methods store each hashed value using 64 bits, b-bit minwise hashing only stores the lowest b bits (where b ≥ 2 for 3-way). The extension to 3-way similarity from the prior work on 2-way similarity is technically non-trivial. We develop the precise estimator which is accurate and very complicated; and we recommend a much simpliﬁed estimator suitable for sparse data. Our analysis shows that b-bit minwise hashing can normally achieve a 10 to 25-fold improvement in the storage space required for a given estimator accuracy of the 3-way resemblance. 1

4 0.53567362 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

Author: Pierre Garrigues, Bruno A. Olshausen

Abstract: We propose a class of sparse coding models that utilizes a Laplacian Scale Mixture (LSM) prior to model dependencies among coefﬁcients. Each coefﬁcient is modeled as a Laplacian distribution with a variable scale parameter, with a Gamma distribution prior over the scale parameter. We show that, due to the conjugacy of the Gamma prior, it is possible to derive efﬁcient inference procedures for both the coefﬁcients and the scale parameter. When the scale parameters of a group of coefﬁcients are combined into a single variable, it is possible to describe the dependencies that occur due to common amplitude ﬂuctuations among coefﬁcients, which have been shown to constitute a large fraction of the redundancy in natural images [1]. We show that, as a consequence of this group sparse coding, the resulting inference of the coefﬁcients follows a divisive normalization rule, and that this may be efﬁciently implemented in a network architecture similar to that which has been proposed to occur in primary visual cortex. We also demonstrate improvements in image coding and compressive sensing recovery using the LSM model. 1

5 0.53134912 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

Author: Jun Liu, Jieping Ye

Abstract: We consider the tree structured group Lasso where the structure over the features can be represented as a tree with leaf nodes as features and internal nodes as clusters of the features. The structured regularization with a pre-deﬁned tree structure is based on a group-Lasso penalty, where one group is deﬁned for each node in the tree. Such a regularization can help uncover the structured sparsity, which is desirable for applications with some meaningful tree structures on the features. However, the tree structured group Lasso is challenging to solve due to the complex regularization. In this paper, we develop an efﬁcient algorithm for the tree structured group Lasso. One of the key steps in the proposed algorithm is to solve the Moreau-Yosida regularization associated with the grouped tree structure. The main technical contributions of this paper include (1) we show that the associated Moreau-Yosida regularization admits an analytical solution, and (2) we develop an efﬁcient algorithm for determining the effective interval for the regularization parameter. Our experimental results on the AR and JAFFE face data sets demonstrate the efﬁciency and effectiveness of the proposed algorithm.

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

7 0.53064263 97 nips-2010-Functional Geometry Alignment and Localization of Brain Areas

8 0.52764356 59 nips-2010-Deep Coding Network

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

10 0.52447546 117 nips-2010-Identifying graph-structured activation patterns in networks

11 0.52445441 200 nips-2010-Over-complete representations on recurrent neural networks can support persistent percepts

12 0.52017987 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

13 0.51862955 149 nips-2010-Learning To Count Objects in Images

14 0.51394302 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing

15 0.51339883 217 nips-2010-Probabilistic Multi-Task Feature Selection

16 0.51299143 203 nips-2010-Parametric Bandits: The Generalized Linear Case

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

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

19 0.51251197 265 nips-2010-The LASSO risk: asymptotic results and real world examples

20 0.51158959 247 nips-2010-Sparse Instrumental Variables (SPIV) for Genome-Wide Studies