nips nips2009 nips2009-67 knowledge-graph by maker-knowledge-mining

67 nips-2009-Directed Regression

Source: pdf

Author: Yi-hao Kao, Benjamin V. Roy, Xiang Yan

Abstract: When used to guide decisions, linear regression analysis typically involves estimation of regression coefﬁcients via ordinary least squares and their subsequent use to make decisions. When there are multiple response variables and features do not perfectly capture their relationships, it is beneﬁcial to account for the decision objective when computing regression coefﬁcients. Empirical optimization does so but sacriﬁces performance when features are well-chosen or training data are insufﬁcient. We propose directed regression, an efﬁcient algorithm that combines merits of ordinary least squares and empirical optimization. We demonstrate through a computational study that directed regression can generate signiﬁcant performance gains over either alternative. We also develop a theory that motivates the algorithm. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract When used to guide decisions, linear regression analysis typically involves estimation of regression coefﬁcients via ordinary least squares and their subsequent use to make decisions. [sent-4, score-0.36]

2 When there are multiple response variables and features do not perfectly capture their relationships, it is beneﬁcial to account for the decision objective when computing regression coefﬁcients. [sent-5, score-0.392]

3 Empirical optimization does so but sacriﬁces performance when features are well-chosen or training data are insufﬁcient. [sent-6, score-0.091]

4 We propose directed regression, an efﬁcient algorithm that combines merits of ordinary least squares and empirical optimization. [sent-7, score-0.172]

5 We demonstrate through a computational study that directed regression can generate signiﬁcant performance gains over either alternative. [sent-8, score-0.215]

6 1 Introduction When used to guide decision-making, linear regression analysis typically treats estimation of regression coefﬁcients separately from their use to make decisions. [sent-10, score-0.28]

7 In particular, estimation is carried out via ordinary least squares (OLS) without consideration of the decision objective. [sent-11, score-0.155]

8 The regression coefﬁcients are then used to optimize decisions. [sent-12, score-0.12]

9 When there are multiple response variables and features do not perfectly capture their relationships, it is beneﬁcial to account for the decision objective when computing regression coefﬁcients. [sent-13, score-0.392]

10 Imperfections in feature selection are common since it is difﬁcult to identify the right features and the number of features is typically restricted in order to avoid over-ﬁtting. [sent-14, score-0.144]

11 Empirical optimization (EO) is an alternative to OLS which selects coefﬁcients that minimize empirical loss in the training data. [sent-15, score-0.15]

12 Though it accounts for the decision objective when computing regression coefﬁcients, EO sacriﬁces performance when features are well-chosen or training data is insufﬁcient. [sent-16, score-0.318]

13 In this paper, we propose a new algorithm – directed regression (DR) – which is a hybrid between OLS and EO. [sent-17, score-0.19]

14 DR selects coefﬁcients that are a convex combination of those that would be selected by OLS and those by EO. [sent-18, score-0.094]

15 We study DR for the case of decision problems with quadratic objective functions. [sent-20, score-0.147]

16 The algorithm takes as input a training set of data pairs, each consisting of feature vectors and response variables, together with a quadratic loss function that depends on decision variables and response variables. [sent-21, score-0.482]

17 Each future decision depends on newly sampled feature vectors and is made prior to observing response variables with the goal of minimizing expected loss. [sent-23, score-0.316]

18 These results are for synthetic problems with regression models that include subsets of relevant 1 features. [sent-25, score-0.12]

19 In some cases, OLS and EO deliver comparable performance while DR reduces expected loss by about 20%. [sent-26, score-0.115]

20 This theory is based on a model in which selected features do not perfectly capture relationships among response variables. [sent-29, score-0.221]

21 We prove that, for this model, the optimal vector of coefﬁcients is a convex combination of those that would be generated by OLS and EO. [sent-30, score-0.084]

22 Each nth (n) (n) data pair is comprised of feature vectors x1 , . [sent-32, score-0.075]

23 , xK ∈ M and a vector y (n) ∈ M of response variables. [sent-35, score-0.104]

24 We would like to compute regression coefﬁcients r ∈ K so that given a data pair (x, y), the linear combination k rk xk of feature vectors estimates the expectation of y conditioned on x. [sent-36, score-0.481]

25 We consider a setting where the regression model is used to guide future decisions. [sent-38, score-0.182]

26 In particular, after computing regression coefﬁcients, each time we observe feature vectors x1 , . [sent-39, score-0.195]

27 , xK we will have to select a decision u ∈ L before observing the response vector y. [sent-42, score-0.215]

28 The choice incurs a loss (u, y) = u G1 u + u G2 y, where the matrices G1 ∈ L×L and G2 ∈ L×M are known, and the former is positive deﬁnite and symmetric. [sent-43, score-0.113]

29 We aim to minimize expected loss, assuming that the conditional expectation of y given K x is k=1 rk xk . [sent-44, score-0.267]

30 As such, given x and r, we select a decision K ur (x) = argmin u, u rk xk k=1 1 = − G−1 G2 2 1 K rk xk . [sent-45, score-0.967]

31 k=1 The question is how best to compute the regression coefﬁcients r for this purpose. [sent-46, score-0.12]

32 An average revenue of ym is received per customer of class m that the campaign reaches. [sent-50, score-0.144]

33 These factors may be correlated across customers classes; for example, they could capture customer preferences as they relate to ad content or how current economic conditions affect customers. [sent-55, score-0.103]

34 For each mth class, the cost of reaching the um th customer increases with um because ads are ﬁrst targeted at customers that can be reached at lower cost. [sent-56, score-0.189]

35 It is natural to predict the response vector y using a linear combination k rk xk of factors with the regression coefﬁcients rk computed based on past observations O = {(x(1) , y (1) ), · · · , (x(N ) , y (N ) )}. [sent-59, score-0.6]

36 This gives rise to a loss function that is quadratic in u and y: M (γm u2 − um ym ). [sent-61, score-0.229]

37 m (u, y) = m=1 One might ask why not construct M separate linear regression models, one for each response variable, each with a separate set of K coefﬁcients. [sent-62, score-0.202]

38 Models of the sort we consider, where regression coefﬁcients are shared across multiple response variables, are sometimes referred to as general linear models and have seen a wide range of applications [7, 8]. [sent-64, score-0.202]

39 It is well-known that the quality of results is highly sensitive to the choice of features, even more so than for models involving a single response variable [7]. [sent-65, score-0.082]

40 2 3 Algorithms Ordinary least squares (OLS) is a conventional approach to computing regression coefﬁcients. [sent-66, score-0.151]

41 This would produce a coefﬁcient vector N r OLS K = argmin r∈ K y (n) − n=1 2 (n) rk xk . [sent-67, score-0.455]

42 (1) k=1 Note that OLS does not take the decision objective into account when computing regression coefﬁcients. [sent-68, score-0.227]

43 This approach minimizes empirical loss on the training data: N rEO = argmin r∈ K (ur (x(n) ), y (n) ). [sent-70, score-0.342]

44 (2) n=1 Note that EO does not explicitly aim to estimate the conditional expectation of the response vector. [sent-71, score-0.082]

45 Instead it focusses on decision loss that would be incurred with the training data. [sent-72, score-0.229]

46 Both rOLS and rEO can be computed efﬁciently by minimizing convex quadratic functions. [sent-73, score-0.077]

47 In this paper, we propose an alternative algorithm – directed regression (DR) – which produces a convex combination rDR = (1 − λ)rOLS + λrEO of coefﬁcients computed by OLS and EO. [sent-75, score-0.252]

48 The term directed is chosen to indicate that DR is inﬂuenced by the decision objective though, unlike EO, it does not simply minimize empirical loss. [sent-76, score-0.199]

49 The parameter λ ∈ [0, 1] is computed via cross-validation, with an objective of minimizing average loss on validation data. [sent-77, score-0.121]

50 Average loss is a convex quadratic function of λ, and therefore can be easily minimized over λ ∈ [0, 1]. [sent-78, score-0.166]

51 DR is designed to generate decisions that are more robust to imperfections in feature selection than OLS. [sent-79, score-0.143]

52 Our focus on making good decisions despite modeling inaccuracies also complements recent work that studies how models deployed in practice can generate effective decisions despite their failure to pass basic statistical tests [4]. [sent-81, score-0.103]

53 To generate a data set, we ﬁrst sample parameters of a generative model as follows: 1. [sent-83, score-0.105]

54 For each k = 1, 2, · · · , K, let xk = Ck φ(n) . [sent-101, score-0.131]

55 Note that, though response variables depend on P feature vectors, only K ≤ P are used in the regression model. [sent-107, score-0.242]

56 Given generative model parameters and a coefﬁcient vector r ∈ K , it is easy to evaluate the expected loss (r) = Ex,y [ (ur (x), y)]. [sent-108, score-0.19]

57 (b) Excess losses delivered by OLS, EO, and DR, using different numbers K of the 60 features. [sent-110, score-0.141]

58 We will assess each algorithm in terms of the excess loss (r) − ∗ delivered by the coefﬁcient vector r that the algorithm computes. [sent-112, score-0.359]

59 Excess loss is nonnegative, and this allows us to make comparisons in percentage terms. [sent-113, score-0.089]

60 For each N ∈ {10, 15, 20, 30, 50}, we ran 100 trials, each with an independently sampled generative model and training data set. [sent-116, score-0.092]

61 In each trial, each algorithm computes a coefﬁcient vector given the training data and loss function. [sent-117, score-0.15]

62 Note that the excess loss incurred by DR is never larger than that of OLS or EO. [sent-120, score-0.291]

63 Further, when N = 20, the excess loss of OLS and EO are both around 20% larger than that of DR. [sent-121, score-0.265]

64 Note that when K = 55, DR delivers excess loss around 20% less than EO and OLS. [sent-126, score-0.265]

65 When K = P = 60, there are no missing features and OLS matches the performance of DR. [sent-127, score-0.166]

66 As the number of feature vectors K grows, λ diminishes, indicating that DR is weighted more heavily toward OLS. [sent-130, score-0.099]

67 5 Theoretical Analysis In this section, we formulate a generative model for the training data and future observations. [sent-131, score-0.114]

68 1 Model In this section, we describe a generative model that samples the training data set, as well as “missing features,” and a representative future observation. [sent-135, score-0.114]

69 We then formulate an optimization problem where the objective is to minimize expected loss on the future observation conditioned on the training data and missing features. [sent-136, score-0.342]

70 It may seem strange to condition on missing features since in practice they are unavailable when computing regression coefﬁcients. [sent-137, score-0.286]

71 2 20 30 N 40 0 45 50 50 55 60 K (a) (b) Figure 2: (a) The average values of selected λ, for different numbers N of training samples. [sent-146, score-0.091]

72 coefﬁcients are convex combinations of rOLS and rEO , each of which can be computed without observing missing features. [sent-148, score-0.215]

73 Since directed regression searches over these convex combinations, it should approximate what would be generated by a hypothetical algorithm that observes missing features. [sent-149, score-0.37]

74 Speciﬁcally, the N training data samples depend on information vectors φ(1) , . [sent-151, score-0.074]

75 A linear function mapping an information vector to a feature vector can be represented by a matrix in M ×Q , and to describe our generative model, it is useful to deﬁne an inner product for such matrices. [sent-155, score-0.158]

76 First, there are the number of samples N , the number of response variables M , and the number of feature vectors K. [sent-158, score-0.157]

77 Finally, there are standard deviations σr , σ , and σw , of observed feature coefﬁcients, missing feature coefﬁcients, and noise, respectively. [sent-160, score-0.194]

78 2 from N (0, σw IM ), and let x(n) = C1 φ(n) ··· CK φ(n) , (3) ˜ z (n) = D1 φ(n) ··· ˜ DJ φ(n) , (4) K y (n) = (n) J ∗ rk xk + j=1 k=1 5 (n) ⊥∗ rj zj + w(n) . [sent-193, score-0.313]

79 First, since Ck , Dj = 0, missing features are uncorrelated with observed features. [sent-202, score-0.166]

80 If this were not the case, observed features would provide information about missing features. [sent-203, score-0.166]

81 , DJ are orthonormal, the distribution of missing features is invariant to rotations in the J-dimensional subspace from which they are drawn. [sent-207, score-0.166]

82 We deﬁne an augmented training set O = {(x(1) , z (1) , y (1) ), · · · , (x(N ) , z (N ) , y (N ) )} and consider selecting regression coefﬁcients r ∈ K that solve ˆ min E[ (ur (˜), y )|O]. [sent-209, score-0.159]

83 The following theorem ˆ ˆ ˆ establishes that these extremes are delivered by OLS and EO. [sent-218, score-0.157]

84 For all N , M , K, µQ , σw , and O, N K r0 = argmin ˆ r∈ K y (n) n=1 − 2 (n) rk xk k=1 and N (ur (x(n) ), y (n) ). [sent-220, score-0.433]

85 r∞ = argmin ˆ r∈ K n=1 Note that σ represents the degree of bias in a regression model that assumes there are no missing features. [sent-221, score-0.454]

86 Hence, the above theorem indicates that OLS is optimal when there is no bias while EO is optimal as the bias becomes asymptotically large. [sent-222, score-0.111]

87 It is also worth noting that the coefﬁcient vectors r0 and r∞ can be computed without observing the missing features, though r is deﬁned by ˆ ˆ ˆ an expectation that is conditioned on their realizations. [sent-223, score-0.205]

88 Our next theorem establishes that the coefﬁcient vector r is always a convex combination of r0 and ˆ ˆ r∞ . [sent-225, score-0.137]

89 This suggests that directed regression, which optimizes λ via cross-validation to generate ˆ a coefﬁcient vector rDR = (1 − λ)rOLS + λrEO , should approximate r well without observing the ˆ missing features or requiring knowledge of Q, σ , or σw . [sent-229, score-0.319]

90 Then the optimal coefﬁcient vector would be rO = argmin E[ (ur (˜), y )|O, r∗ , r⊥∗ ]. [sent-232, score-0.214]

91 In particular, as the number of training samples N increases, variance diminishes and λ approaches 1, placing increasing weight on EO. [sent-236, score-0.092]

92 On the other hand, as the number of observed features K increases, model bias decreases and λ approaches 0, placing increasing weight on OLS. [sent-237, score-0.101]

93 In particular, machine learning algorithms should factor decision objectives into the learning process. [sent-240, score-0.075]

94 In particular, rather than selecting a few features and facing the consequences of model bias, one might select an enormous set of features and apply a method like the lasso [10] to identify a small subset. [sent-243, score-0.135]

95 RL algorithms learn from experience to predict a sum of future rewards as a function of a state, typically by ﬁtting a linear combination of features of the state. [sent-253, score-0.099]

96 The problem we addressed in this paper can be viewed as a single-period version of RL, in the sense that each decision incurs an immediate cost but bears no further consequences. [sent-255, score-0.099]

97 ˆ The ﬁrst part of the theorem then follows because (7) (8) N r0 = X † Y = argmin Y − Xr ˆ 2 r r K y (n) − = argmin n=1 2 (n) rk xk . [sent-269, score-0.655]

98 Note that N N (ur (x(n) ), y (n) ) = argmin argmin r r n=1 ur (x(n) ) G1 ur (x(n) ) + ur (x(n) ) G2 y (n) n=1 N h(n) y (n) = (A A)−1 H Y, = argmin r A Ar − 2r r where h (n) = n=1 G2 G−1 G2 x(n) 1 and H =   hk =  h(1) ··· h(N ) G2 G−1 G2 Ck φ(1) 1  . [sent-271, score-1.255]

99 −1 (N ) G2 G1 G2 Ck φ ˜ ˜ is in span{col X, col Z} because G2 G−1 G2 Ck ∈ M ×Q = span{C1 , · · · , CK , D1 , · · · , DJ }. [sent-275, score-0.079]

100 1 † † Since the residual Y = Y − XX Y − ZZ Y upon projecting Y onto span {col X, col Z} is orthogonal to the subspace, we have hk Y = 0, ∀ k and hence H Y = 0. [sent-276, score-0.134]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ols', 0.47), ('eo', 0.374), ('dr', 0.366), ('ur', 0.218), ('coef', 0.208), ('argmin', 0.192), ('rols', 0.18), ('reo', 0.177), ('excess', 0.176), ('cients', 0.158), ('ck', 0.137), ('xk', 0.131), ('regression', 0.12), ('missing', 0.114), ('rk', 0.11), ('dj', 0.106), ('loss', 0.089), ('response', 0.082), ('col', 0.079), ('decision', 0.075), ('delivered', 0.072), ('stanford', 0.07), ('directed', 0.07), ('bz', 0.068), ('um', 0.054), ('zz', 0.054), ('generative', 0.053), ('features', 0.052), ('ga', 0.05), ('losses', 0.049), ('ordinary', 0.049), ('campaign', 0.045), ('cp', 0.041), ('customers', 0.041), ('rj', 0.041), ('feature', 0.04), ('quadratic', 0.04), ('guide', 0.04), ('customer', 0.04), ('imperfections', 0.039), ('rdr', 0.039), ('training', 0.039), ('decisions', 0.039), ('convex', 0.037), ('observing', 0.036), ('xx', 0.036), ('gb', 0.036), ('vectors', 0.035), ('rl', 0.034), ('revenue', 0.034), ('extremes', 0.032), ('diminishes', 0.032), ('objective', 0.032), ('selected', 0.032), ('perfectly', 0.031), ('squares', 0.031), ('zj', 0.031), ('enormous', 0.031), ('ro', 0.031), ('span', 0.03), ('theorem', 0.03), ('hypothetical', 0.029), ('bias', 0.028), ('combinations', 0.028), ('sample', 0.027), ('im', 0.026), ('incurred', 0.026), ('sacri', 0.026), ('expected', 0.026), ('insuf', 0.026), ('asymptotically', 0.025), ('generate', 0.025), ('combination', 0.025), ('entry', 0.025), ('hk', 0.025), ('ym', 0.025), ('incurs', 0.024), ('relationships', 0.024), ('heavily', 0.024), ('motivate', 0.023), ('motivates', 0.023), ('establishes', 0.023), ('future', 0.022), ('orthonormal', 0.022), ('uenced', 0.022), ('empirical', 0.022), ('trials', 0.022), ('helpful', 0.022), ('ad', 0.022), ('vector', 0.022), ('grows', 0.021), ('ces', 0.021), ('placing', 0.021), ('rise', 0.021), ('inner', 0.021), ('generalizations', 0.02), ('univariate', 0.02), ('conditioned', 0.02), ('reinforcement', 0.02), ('numbers', 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 67 nips-2009-Directed Regression

Author: Yi-hao Kao, Benjamin V. Roy, Xiang Yan

2 0.20696828 104 nips-2009-Group Sparse Coding

Author: Samy Bengio, Fernando Pereira, Yoram Singer, Dennis Strelow

Abstract: Bag-of-words document representations are often used in text, image and video processing. While it is relatively easy to determine a suitable word dictionary for text documents, there is no simple mapping from raw images or videos to dictionary terms. The classical approach builds a dictionary using vector quantization over a large set of useful visual descriptors extracted from a training set, and uses a nearest-neighbor algorithm to count the number of occurrences of each dictionary word in documents to be encoded. More robust approaches have been proposed recently that represent each visual descriptor as a sparse weighted combination of dictionary words. While favoring a sparse representation at the level of visual descriptors, those methods however do not ensure that images have sparse representation. In this work, we use mixed-norm regularization to achieve sparsity at the image level as well as a small overall dictionary. This approach can also be used to encourage using the same dictionary words for all the images in a class, providing a discriminative signal in the construction of image representations. Experimental results on a benchmark image classiﬁcation dataset show that when compact image or dictionary representations are needed for computational efﬁciency, the proposed approach yields better mean average precision in classiﬁcation. 1

3 0.11185057 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

Author: Shuheng Zhou

Abstract: Given n noisy samples with p dimensions, where n ≪ p, we show that the multistep thresholding procedure can accurately estimate a sparse vector β ∈ Rp in a linear model, under the restricted eigenvalue conditions (Bickel-Ritov-Tsybakov 09). Thus our conditions for model selection consistency are considerably weaker than what has been achieved in previous works. More importantly, this method allows very signiﬁcant values of s, which is the number of non-zero elements in the true parameter. For example, it works for cases where the ordinary Lasso would have failed. Finally, we show that if X obeys a uniform uncertainty principle and if the true parameter is sufﬁciently sparse, the Gauss-Dantzig selector (Cand` se Tao 07) achieves the ℓ2 loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle which would supply perfect information about which coordinates are non-zero and which are above the noise level, while selecting a sufﬁciently sparse model. 1

4 0.11134188 55 nips-2009-Compressed Least-Squares Regression

Author: Odalric Maillard, Rémi Munos

Abstract: We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M . From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting “Compressed Least Squares Re√ gression” (CLSR) in terms of N , K, and M . When we choose M = O( K), we √ show that CLSR has an estimation error of order O(log K/ K). 1 Problem setting We consider a regression problem where we observe data DK = ({xk , yk }k≤K ) (where xk ∈ X and yk ∈ R) are assumed to be independently and identically distributed (i.i.d.) from some distribution P , where xk ∼ PX and yk = f ∗ (xk ) + ηk (xk ), where f ∗ is the (unknown) target function, and ηk a centered independent noise of variance σ 2 (xk ). For a given class of functions F, and f ∈ F, we deﬁne the empirical (quadratic) error def LK (f ) = 1 K K [yk − f (xk )]2 , k=1 and the generalization (quadratic) error def L(f ) = E(X,Y )∼P [(Y − f (X))2 ]. Our goal is to return a regression function f ∈ F with lowest possible generalization error L(f ). Notations: In the sequel we will make use of the following notations about norms: for h : X → R, we write ||h||P for the L2 norm of h with respect to (w.r.t.) the measure P , ||h||PK for the L2 norm n 2 1/2 of h w.r.t. the empirical measure PK , and for u ∈ Rn , ||u|| denotes by default . i=1 ui The measurable function minimizing the generalization error is f ∗ , but it may be the case that f ∗ ∈ F. For any regression function f , we deﬁne the excess risk / L(f ) − L(f ∗ ) = ||f − f ∗ ||2 , P which decomposes as the sum of the estimation error L(f ) − inf f ∈F L(f ) and the approximation error inf f ∈F L(f ) − L(f ∗ ) = inf f ∈F ||f − f ∗ ||2 which measures the distance between f ∗ and the P function space F. 1 In this paper we consider a class of linear functions FN deﬁned as the span of a set of N functions def def N {ϕn }1≤n≤N called features. Thus: FN = {fα = n=1 αn ϕn , α ∈ RN }. When the number of data K is larger than the number of features N , the ordinary Least-Squares Regression (LSR) provides the LS solution fα which is the minimizer of the empirical risk LK (f ) b 1 in FN . Note that here LK (fα ) rewrites K ||Φα − Y ||K where Φ is the K × N matrix with elements (ϕn (xk ))1≤n≤N,1≤k≤K and Y the K-vector with components (yk )1≤k≤K . Usual results provide bound on the estimation error as a function of the capacity of the function space and the number of data. In the case of linear approximation, the capacity measures (such as covering numbers [23] or the pseudo-dimension [16]) depend on the number of features (for example the pseudo-dimension is at most N + 1). For example, let fα be a LS estimate (minimizer of LK b in FN ), then (a more precise statement will be stated later in Subsection 3) the expected estimation error is bounded as: N log K E L(fα ) − inf L(f ) ≤ cσ2 , (1) b f ∈FN K def where c is a universal constant, σ = supx∈X σ(x), and the expectation is taken with respect to P . Now, the excess risk is the sum of this estimation error and the approximation error inf f ∈FN ||f − f ∗ ||P of the class FN . Since the later usually decreases when the number of features N increases [13] (e.g. when N FN is dense in L2 (P )), we see the usual tradeoff between small estimation error (low N ) and small approximation error (large N ). In this paper we are interested in the setting when N is large so that the approximation error is small. Whenever N is larger than K we face the overﬁtting problem since there are more parameters than actual data (more variables than constraints), which is illustrated in the bound (1) which provides no information about the generalization ability of any LS estimate. In addition, there are many minimizers (in fact a vector space of same dimension as the null space of ΦT Φ) of the empirical risk. To overcome the problem, several approaches have been proposed in the literature: • LS solution with minimal norm: The solution is the minimizer of the empirical error with minimal (l1 or l2 )-norm: α = arg minΦα=Y ||α||1 or 2 , (or a robust solution arg min||Φα−Y ||2 ≤ε ||α||1 ). The choice of 2 -norm yields the ordinary LS solution. The choice of 1 -norm has been used for generating sparse solutions (e.g. the Basis Pursuit [10]), and assuming that the target function admits a sparse decomposition, the ﬁeld of Compressed Sensing [9, 21] provides sufﬁcient conditions for recovering the exact solution. However, such conditions (e.g. that Φ possesses a Restricted Isometric Property (RIP)) does not hold in general in this regression setting. On another aspect, solving these problems (both for l1 or l2 -norm) when N is large is numerically expensive. • Regularization. The solution is the minimizer of the empirical error plus a penalty term, for example f = arg min LK (f ) + λ||f ||p , for p = 1 or 2. p f ∈FN where λ is a parameter and usual choices for the norm are 2 (ridge-regression [20]) and 1 (LASSO [19]). A close alternative is the Dantzig selector [8, 5] which solves: α = arg min||α||1 ≤λ ||ΦT (Y − Φα)||∞ . The numerical complexity and generalization bounds of those methods depend on the sparsity of the target function decomposition in FN . Now if we possess a sequence of function classes (FN )N ≥1 with increasing capacity, we may perform structural risk minimization [22] by solving in each model the empirical risk penalized by a term that depends on the size of the model: fN = arg minf ∈FN ,N ≥1 LK (f ) + pen(N, K), where the penalty term measures the capacity of the function space. In this paper we follow another approach where instead of searching in the large space FN (where N > K) for a solution that minimizes the empirical error plus a penalty term, we simply search for the empirical error minimizer in a (randomly generated) lower dimensional subspace GM ⊂ FN (where M < K). Our contribution: We consider a set of M random linear combinations of the initial N features and perform our favorite LS regression algorithm (possibly regularized) using those “compressed 2 features”. This is equivalent to projecting the K points {ϕ(xk ) ∈ RN , k = 1..K} from the initial domain (of size N ) onto a random subspace of dimension M , and then performing the regression in the “compressed domain” (i.e. span of the compressed features). This is made possible because random projections approximately preserve inner products between vectors (by a variant of the Johnson-Lindenstrauss Lemma stated in Proposition 1. Our main result is a bound on the excess risk of a linear estimator built in the compressed domain in terms of the excess risk of the linear estimator built in the initial domain (Section 2). We further detail the case of ordinary Least-Squares Regression (Section 3) and discuss, in terms of M , N , K, the different tradeoffs concerning the excess risk (reduced estimation error in the compressed domain versus increased approximation error introduced by the random projection) and the numerical complexity (reduced complexity of solving the LSR in the compressed domain versus the additional load of performing the projection). √ As a consequence, we show that by choosing M = O( K) projections we deﬁne a Compressed Least-Squares Regression which uses O(N K 3/2 ) elementary operations to compute a regression √ function with estimation error (relatively to the initial function space FN ) of order log K/ K up to a multiplicative factor which depends on the best approximation of f ∗ in FN . This is competitive with the best methods, up to our knowledge. Related works: Using dimension reduction and random projections in various learning areas has received considerable interest over the past few years. In [7], the authors use a SVM algorithm in a compressed space for the purpose of classiﬁcation and show that their resulting algorithm has good generalization properties. In [25], the authors consider a notion of compressed linear regression. For data Y = Xβ + ε, where β is the target and ε a standard noise, they use compression of the set of data, thus considering AY = AXβ + Aε, where A has a Restricted Isometric Property. They provide an analysis of the LASSO estimator built from these compressed data, and discuss a property called sparsistency, i.e. the number of random projections needed to recover β (with high probability) when it is sparse. These works differ from our approach in the fact that we do not consider a compressed (input and/or output) data space but a compressed feature space instead. In [11], the authors discuss how compressed measurements may be useful to solve many detection, classiﬁcation and estimation problems without having to reconstruct the signal ever. Interestingly, they make no assumption about the signal being sparse, like in our work. In [6, 17], the authors show how to map a kernel k(x, y) = ϕ(x) · ϕ(y) into a low-dimensional space, while still approximately preserving the inner products. Thus they build a low-dimensional feature space speciﬁc for (translation invariant) kernels. 2 Linear regression in the compressed domain We remind that the initial set of features is {ϕn : X → def N FN = {fα = n=1 αn ϕn , α ∈ components (ϕn (x))n≤N . Let us R, 1 ≤ n ≤ N } and the initial domain R } is the span of those features. We write ϕ(x) the N -vector of N now deﬁne the random projection. Let A be a M × N matrix of i.i.d. elements drawn for some distribution ρ. Examples of distributions are: • Gaussian random variables N (0, 1/M ), √ • ± Bernoulli distributions, i.e. which takes values ±1/ M with equal probability 1/2, • Distribution taking values ± 3/M with probability 1/6 and 0 with probability 2/3. The following result (proof in the supplementary material) states the property that inner-product are approximately preserved through random projections (this is a simple consequence of the JohnsonLindenstrauss Lemma): Proposition 1 Let (uk )1≤k≤K and v be vectors of RN . Let A be a M × N matrix of i.i.d. elements drawn from one of the previously deﬁned distributions. For any ε > 0, δ > 0, for M ≥ ε2 1 ε3 log 4K , we have, with probability at least 1 − δ, for all k ≤ K, δ 4 − 6 |Auk · Av − uk · v| ≤ ε||uk || ||v||. 3 def We now introduce the set of M compressed features (ψm )1≤m≤M such that ψm (x) = N We also write ψ(x) the M -vector of components (ψm (x))m≤M . Thus n=1 Am,n ϕn (x). ψ(x) = Aϕ(x). We deﬁne the compressed domain GM = {gβ = m=1 βm ψm , β ∈ RM } the span of the compressed features (vector space of dimension at most M ). Note that each ψm ∈ FN , thus GM is a subspace of FN . def 2.1 M Approximation error We now compare the approximation error assessed in the compressed domain GM versus in the initial space FN . This applies to the linear algorithms mentioned in the introduction such as ordinary LS regression (analyzed in details in Section 3), but also its penalized versions, e.g. LASSO and ridge regression. Deﬁne α+ = arg minα∈RN L(fα ) − L(f ∗ ) the parameter of the best regression function in FN . Theorem 1 For any δ > 0, any M ≥ 15 log(8K/δ), let A be a random M × N matrix deﬁned like in Proposition 1, and GM be the compressed domain resulting from this choice of A. Then with probability at least 1 − δ, inf ||g−f ∗ ||2 ≤ P g∈GM 8 log(8K/δ) + 2 ||α || M E ||ϕ(X)||2 +2 sup ||ϕ(x)||2 x∈X log 4/δ + inf ||f −f ∗ ||2 . P f ∈FN 2K (2) This theorem shows the tradeoff in terms of estimation and approximation errors for an estimator g obtained in the compressed domain compared to an estimator f obtained in the initial domain: • Bounds on the estimation error of g in GM are usually smaller than that of f in FN when M < N (since the capacity of FN is larger than that of GM ). • Theorem 1 says that the approximation error assessed in GM increases by at most O( log(K/δ) )||α+ ||2 E||ϕ(X)||2 compared to that in FN . M def def Proof: Let us write f + = fα+ = arg minf ∈FN ||f − f ∗ ||P and g + = gAα+ . The approximation error assessed in the compressed domain GM is bounded as inf ||g − f ∗ ||2 P g∈GM ≤ ||g + − f ∗ ||2 = ||g + − f + ||2 + ||f + − f ∗ ||2 , P P P (3) since f + is the orthogonal projection of f ∗ on FN and g + belongs to FN . We now bound ||g + − def def f + ||2 using concentration inequalities. Deﬁne Z(x) = Aα+ · Aϕ(x) − α+ · ϕ(x). Deﬁne ε2 = P log(8K/δ) 8 M log(8K/δ). For M ≥ 15 log(8K/δ) we have ε < 3/4 thus M ≥ ε2 /4−ε3 /6 . Proposition 1 applies and says that on an event E of probability at least 1 − δ/2, we have for all k ≤ K, def |Z(xk )| ≤ ε||α+ || ||ϕ(xk )|| ≤ ε||α+ || sup ||ϕ(x)|| = C (4) x∈X On the event E, we have with probability at least 1 − δ , ||g + − f + ||2 P = ≤ ≤ EX∼PX |Z(X)|2 ≤ ε2 ||α+ ||2 ε2 ||α+ ||2 1 K 1 K K |Z(xk )|2 + C 2 k=1 K ||ϕ(xk )||2 + sup ||ϕ(x)||2 x∈X k=1 E ||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x∈X log(2/δ ) 2K log(2/δ ) 2K log(2/δ ) . 2K where we applied two times Chernoff-Hoeffding’s inequality. Combining with (3), unconditioning, and setting δ = δ/2 then with probability at least (1 − δ/2)(1 − δ ) ≥ 1 − δ we have (2). 4 2.2 Computational issues We now discuss the relative computational costs of a given algorithm applied either in the initial or in the compressed domain. Let us write Cx(DK , FN , P ) the complexity (e.g. number of elementary operations) of an algorithm A to compute the regression function f when provided with the data DK and function space FN . We plot in the table below, both for the initial and the compressed versions of the algorithm A, the order of complexity for (i) the cost for building the feature matrix, (ii) the cost for computing the estimator, (iii) the cost for making one prediction (i.e. computing f (x) for any x): Construction of the feature matrix Computing the regression function Making one prediction Initial domain NK Cx(DK , FN , P ) N Compressed domain N KM Cx(DK , GM , P ) NM Note that the values mentioned for the compressed domain are upper-bounds on the real complexity and do not take into account the possible sparsity of the projection matrix A (which would speed up matrix computations, see e.g. [2, 1]). 3 Compressed Least-Squares Regression We now analyze the speciﬁc case of Least-Squares Regression. 3.1 Excess risk of ordinary Least Squares regression In order to bound the estimation error, we follow the approach of [13] which truncates (up to the level ±L where L is a bound, assumed to be known, on ||f ∗ ||∞ ) the prediction of the LS regression function. The ordinary LS regression provides the regression function fα where b α= argmin α∈argminα ∈ RN ||α||. ||Y −Φα || Note that ΦΦT α = ΦT Y , hence α = Φ† Y ∈ RN where Φ† is the Penrose pseudo-inverse of Φ1 . def Then the truncated predictor is: fL (x) = TL [fα (x)], where b def TL (u) = u if |u| ≤ L, L sign(u) otherwise. Truncation after the computation of the parameter α ∈ RN , which is the solution of an unconstrained optimization problem, is easier than solving an optimization problem under the constraint that ||α|| is small (which is the approach followed in [23]) and allows for consistency results and prediction bounds. Indeed, the excess risk of fL is bounded as 1 + log K E(||f − f ∗ ||2 ) ≤ c max{σ2 , L2 } N + 8 inf ||f − f ∗ ||2 (5) P P f ∈FN K where a bound on c is 9216 (see [13]). We have a simpler bound when we consider the expectation EY conditionally on the input data: N EY (||f − f ∗ ||2 K ) ≤ σ2 + inf ||f − f ∗ ||2 K (6) P P K f ∈F Remark: Note that because we use the quadratic loss function, by following the analysis in [3], or by deriving tight bounds on the Rademacher complexity [14] and following Theorem 5.2 of Koltchinskii’s Saint Flour course, it is actually possible to state assumptions under which we can remove the log K term in (5). We will not further detail such bounds since our motivation here is not to provide the tightest possible bounds, but rather to show how the excess risk bound for LS regression in the initial domain extends to the compressed domain. 1 In the full rank case, Φ† = (ΦT Φ)−1 ΦT when K ≥ N and Φ† = ΦT (ΦΦT )−1 when K ≤ N 5 3.2 Compressed Least-Squares Regression (CLSR) CLSR is deﬁned as the ordinary LSR in the compressed domain. Let β = Ψ† Y ∈ RM , where Ψ is the K × M matrix with elements (ψm (xk ))1≤m≤M,1≤k≤K . The CLSR estimate is deﬁned as def gL (x) = TL [gβ (x)]. From Theorem 1, (5) and (6), we deduce the following excess risk bounds for b the CLSR estimate: √ ||α+ || E||ϕ(X)||2 K log(8K/δ) Corollary 1 For any δ > 0, set M = 8 max(σ,L) c (1+log K) . Then whenever M ≥ 15 log(8K/δ), with probability at least 1 − δ, the expected excess risk of the CLSR estimate is bounded as √ E(||gL − f ∗ ||2 ) ≤ 16 c max{σ, L}||α+ || E||ϕ(X)||2 P × 1+ supx ||ϕ(x)||2 E||ϕ(X)||2 (1 + log K) log(8K/δ) K log 4/δ + 8 inf ||f − f ∗ ||2 . P f ∈FN 2K (7) √ ||α+ || E||ϕ(X)||2 Now set M = 8K log(8K/δ). Assume N > K and that the features (ϕk )1≤k≤K σ are linearly independent. Then whenever M ≥ 15 log(8K/δ), with probability at least 1 − δ, the expected excess risk of the CLSR estimate conditionally on the input samples is upper bounded as 2 log(8K/δ) supx ||ϕ(x)||2 1+ K E||ϕ(X)||2 EY (||gL − f ∗ ||2 K ) ≤ 4σ||α+ || E||ϕ(X)||2 P log 4/δ . 2K Proof: Whenever M ≥ 15 log(8K/δ) we deduce from Theorem 1 and (5) that the excess risk of gL is bounded as E(||gL − f ∗ ||2 ) ≤ c max{σ2 , L2 } P +8 8 log(8K/δ) + 2 ||α || M 1 + log K M K E||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x log 4/δ + inf ||f − f ∗ ||2 . P f ∈FN 2K By optimizing on M , we deduce (7). Similarly, using (6) we deduce the following bound on EY (||gL − f ∗ ||2 K ): P σ2 8 M + log(8K/δ)||α+ ||2 K M E||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x log 4/δ + inf ||f − f ∗ ||2 K . P f ∈FN 2K By optimizing on M and noticing that inf f ∈FN ||f − f ∗ ||2 K = 0 whenever N > K and the features P (ϕk )1≤k≤K are linearly independent, we deduce the second result. Remark 1 Note that the second term in the parenthesis of (7) is negligible whenever K Thus we have the expected excess risk log K/δ + inf ||f − f ∗ ||2 . P f ∈FN K E(||gL − f ∗ ||2 ) = O ||α+ || E||ϕ(X)||2 √ P log 1/δ. (8) The choice of M in the previous corollary depends on ||α+ || and E||ϕ(X)|| which are a priori unknown (since f ∗ and PX are unknown). If we set M independently of ||α+ ||, then an additional multiplicative factor of ||α+ || appears in the bound, and if we replace E||ϕ(X)|| by its bound supx ||ϕ(x)|| (which is known) then this latter factor will appear instead of the former in the bound. Complexity of CLSR: The complexity of LSR for computing the regression function in the compressed domain only depends on M and K, and is (see e.g. [4]) Cx(DK , GM , P ) = O(M K 2 ) which √ is of order O(K 5/2 ) when we choose the optimized number of projections M = O( K). However the leading term when using CLSR is the cost for building the Ψ matrix: O(N K 3/2 ). 6 4 4.1 Discussion The factor ||α+ || E||ϕ(X)||2 In light of Corollary 1, the important factor which will determine whether the CLSR provides low generalization error or not is ||α+ || E||ϕ(X)||2 . This factor indicates that a good set of features (for CLSR) should be such that the norm of those features as well as the norm of the parameter α+ of the projection of f ∗ onto the span of those features should be small. A natural question is whether this product can be made small for appropriate choices of features. We now provide two speciﬁc cases for which this is actually the case: (1) when the features are rescaled orthonormal basis functions, and (2) when the features are speciﬁc wavelet functions. In both cases, we relate the bound to an assumption of regularity on the function f ∗ , and show that the dependency w.r.t. N decreases when the regularity increases, and may even vanish. Rescaled Orthonormal Features: Consider a set of orthonormal functions (ηi )i≥1 w.r.t a measure µ, i.e. ηi , ηj µ = δi,j . In addition we assume that the law of the input data is dominated by µ, i.e. PX ≤ Cµ where C is a constant. For instance, this is the case when the set X is compact, µ is the uniform measure and PX has bounded density. def We deﬁne the set of N features as: ϕi = ci ηi , where ci > 0, for i ∈ {1, . . . , N }. Then any f ∈ FN decomposes as f = 2 we have: ||α|| = ||α+ ||2 E||ϕ||2 ≤ C N bi 2 i=1 ( ci ) N bi 2 i=1 ( ci ) and N i=1 N bi i=1 ci ϕi , where N 2 2 i=1 ci X ηi (x)dPX (x) f, ηi ηi = E||ϕ|| = 2 def bi = f, ηi . Thus ≤ C N 2 i=1 ci . Thus N 2 i=1 ci . Now, linear approximation theory (Jackson-type theorems) tells us that assuming a function f ∗ ∈ L2 (µ) is smooth, it may be decomposed onto the span of the N ﬁrst (ηi )i∈{1,...,N } functions with decreasing coefﬁcients |bi | ≤ i−λ for some λ ≥ 0 that depends on the smoothness of f ∗ . For example the class of functions with bounded total variation may be decomposed with Fourier basis (in dimension 1) with coefﬁcients |bi | ≤ ||f ||V /(2πi). Thus here λ = 1. Other classes (such as Sobolev spaces) lead to larger values of λ related to the order of differentiability. √ N By choosing ci = i−λ/2 , we have ||α+ || E||ϕ||2 ≤ C i=1 i−λ . Thus if λ > 1, then this term is bounded by a constant that does not depend on N . If λ = 1 then it is bounded by O(log N ), and if 0 < λ < 1, then it is bounded by O(N 1−λ ). However any orthonormal basis, even rescaled, would not necessarily yield a small ||α+ || E||ϕ||2 term (this is all the more true when the dimension of X is large). The desired property that the coefﬁcients (α+ )i of the decomposition of f ∗ rapidly decrease to 0 indicates that hierarchical bases, such as wavelets, that would decompose the function at different scales, may be interesting. Wavelets: Consider an inﬁnite family of wavelets in [0, 1]: (ϕ0 ) = (ϕ0 ) (indexed by n ≥ 1 or n h,l equivalently by the scale h ≥ 0 and translation 0 ≤ l ≤ 2h − 1) where ϕ0 (x) = 2h/2 ϕ0 (2h x − l) h,l and ϕ0 is the mother wavelet. Then consider N = 2H features (ϕh,l )1≤h≤H deﬁned as the rescaled def wavelets ϕh,l = ch 2−h/2 ϕ0 , where ch > 0 are some coefﬁcients. Assume the mother wavelet h,l is C p (for p ≥ 1), has at least p vanishing moments, and that for all h ≥ 0, supx l ϕ0 (2h x − l)2 ≤ 1. Then the following result (proof in the supplementary material) provides a bound on supx∈X ||ϕ(x)||2 (thus on E||ϕ(X)||2 ) by a constant independent of N : Proposition 2 Assume that f ∗ is (L, γ)-Lipschitz (i.e. for all v ∈ X there exists a polynomial pv of degree γ such that for all u ∈ X , |f (u) − pv (u)| ≤ L|u − v|γ ) with 1/2 < γ ≤ p. Then setting γ 1 ch = 2h(1−2γ)/4 , we have ||α+ || supx ||ϕ(x)|| ≤ L 1−22 |ϕ0 |, which is independent of N . 1/2−γ 0 Notice that the Haar walevets has p = 1 vanishing moment but is not C 1 , thus the Proposition does not apply directly. However direct computations show that if f ∗ is L-Lipschitz (i.e. γ = 1) then L 0 αh,l ≤ L2−3h/2−2 , and thus ||α+ || supx ||ϕ(x)|| ≤ 4(1−2−1/2 ) with ch = 2−h/4 . 7 4.2 Comparison with other methods In the case when the factor ||α+ || E||ϕ(X)||2 does not depend on N (such as in the previous example), the bound (8) on the excess risk of CLSR states that the estimation error (assessed in √ √ terms of FN ) of CLSR is O(log K/ K). It is clear that whenever N > K (which is the case of interest here), this is better than the ordinary LSR in the initial domain, whose estimation error is O(N log K/K). It is difﬁcult to compare this result with LASSO (or the Dantzig selector that has similar properties [5]) for which an important aspect is to design sparse regression functions or to recover a solution assumed to be sparse. From [12, 15, 24] one deduces that under some assumptions, the estimation error of LASSO is of order S log N where S is the sparsity (number of non-zero coefﬁcients) of the K√ best regressor f + in FN . If S < K then LASSO is more interesting than CLSR in terms of excess risk. Otherwise CLSR may be an interesting alternative although this method does not make any assumption about the sparsity of f + and its goal is not to recover a possible sparse f + but only to make good predictions. However, in some sense our method ﬁnds a sparse solution in the fact that the regression function gL lies in a space GM of small dimension M N and can thus be expressed using only M coefﬁcients. Now in terms of numerical complexity, CLSR requires O(N K 3/2 ) operations to build the matrix and compute the regression function, whereas according to [18], the (heuristical) complexity of the LASSO algorithm is O(N K 2 ) in the best cases (assuming that the number of steps required for convergence is O(K), which is not proved theoretically). Thus CLSR seems to be a good and simple competitor to LASSO. 5 Conclusion We considered the case when the number of features N is larger than the number of data K. The result stated in Theorem 1 enables to analyze the excess risk of any linear regression algorithm (LS or its penalized versions) performed in the compressed domain GM versus in the initial space FN . In the compressed domain the estimation error is reduced but an additional (controlled) approximation error (when compared to the best regressor in FN ) comes into the picture. In the case of LS regression, when the term ||α+ || E||ϕ(X)||2 has a mild dependency on N , then by choosing a √ random subspace of dimension M = O( K), CLSR has an estimation error (assessed in terms of √ FN ) bounded by O(log K/ K) and has numerical complexity O(N K 3/2 ). In short, CLSR provides an alternative to usual penalization techniques where one ﬁrst selects a random subspace of lower dimension and then performs an empirical risk minimizer in this subspace. Further work needs to be done to provide additional settings (when the space X is of dimension > 1) for which the term ||α+ || E||ϕ(X)||2 is small. Acknowledgements: The authors wish to thank Laurent Jacques for numerous comments and Alessandro Lazaric and Mohammad Ghavamzadeh for exciting discussions. This work has been supported by French National Research Agency (ANR) through COSINUS program (project EXPLO-RA, ANR-08-COSI-004). References [1] Dimitris Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687, June 2003. [2] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast JohnsonLindenstrauss transform. In STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557–563, New York, NY, USA, 2006. ACM. [3] Jean-Yves Audibert and Olivier Catoni. Risk bounds in linear regression through pac-bayesian truncation. Technical Report HAL : hal-00360268, 2009. [4] David Bau III and Lloyd N. Trefethen. Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics, 1997. 8 [5] Peter J. Bickel, Ya’acov Ritov, and Alexandre B. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. To appear in Annals of Statistics, 2008. [6] Avrim Blum. Random projection, margins, kernels, and feature-selection. Subspace, Latent Structure and Feature Selection, pages 52–68, 2006. [7] Robert Calderbank, Sina Jafarpour, and Robert Schapire. Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain. Technical Report, 2009. [8] Emmanuel Candes and Terence Tao. The Dantzig selector: Statistical estimation when p is much larger than n. Annals of Statistics, 35:2313, 2007. [9] Emmanuel J. Candes and Justin K. Romberg. Signal recovery from random projections. volume 5674, pages 76–86. SPIE, 2005. [10] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientiﬁc Computing, 20:33–61, 1998. [11] Mark A. Davenport, Michael B. Wakin, and Richard G. Baraniuk. Detection and estimation with compressive measurements. Technical Report TREE 0610, Department of Electrical and Computer Engineering, Rice University, 2006. [12] E. Greenshtein and Y. Ritov. Persistency in high dimensional linear predictor-selection and the virtue of over-parametrization. Bernoulli, 10:971–988, 2004. [13] L. Gy¨ rﬁ, M. Kohler, A. Krzy˙ ak, and H. Walk. A distribution-free theory of nonparametric o z regression. Springer-Verlag, 2002. [14] Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Leon Bottou, editors, Neural Information Processing Systems, pages 793– 800. MIT Press, 2008. [15] Yuval Nardi and Alessandro Rinaldo. On the asymptotic properties of the group Lasso estimator for linear models. Electron. J. Statist., 2:605–633, 2008. [16] D. Pollard. Convergence of Stochastic Processes. Springer Verlag, New York, 1984. [17] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Neural Information Processing Systems, 2007. [18] Saharon Rosset and Ji Zhu. Piecewise linear regularized solution paths. Annals of Statistics, 35:1012, 2007. [19] Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society, Series B, 58:267–288, 1994. [20] A. N. Tikhonov. Solution of incorrectly formulated problems and the regularization method. Soviet Math Dokl 4, pages 1035–1038, 1963. [21] Yaakov Tsaig and David L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52:1289–1306, 2006. [22] Vladimir N. Vapnik. The nature of statistical learning theory. Springer-Verlag New York, Inc., New York, NY, USA, 1995. [23] Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002. [24] Tong Zhang. Some sharp performance bounds for least squares regression with L1 regularization. To appear in Annals of Statistics, 2009. [25] Shuheng Zhou, John D. Lafferty, and Larry A. Wasserman. Compressed regression. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Neural Information Processing Systems. MIT Press, 2007. 9

5 0.079982765 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

Author: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar

Abstract: High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n → 0, a line of recent work has studied models with various types of structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M -estimator) which combines a loss function (measuring how well the model ﬁts the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide a uniﬁed framework for establishing consistency and convergence rates for such regularized M estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identiﬁes two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M -estimators have fast convergence rates. 1

6 0.077940062 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

7 0.070574619 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors

8 0.066283204 138 nips-2009-Learning with Compressible Priors

9 0.060734108 226 nips-2009-Spatial Normalized Gamma Processes

10 0.058528714 62 nips-2009-Correlation Coefficients are Insufficient for Analyzing Spike Count Dependencies

11 0.057026144 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

12 0.053188633 147 nips-2009-Matrix Completion from Noisy Entries

13 0.052703917 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

14 0.052488603 195 nips-2009-Probabilistic Relational PCA

15 0.051562231 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

16 0.049064163 105 nips-2009-Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction

17 0.048899852 191 nips-2009-Positive Semidefinite Metric Learning with Boosting

18 0.048702255 180 nips-2009-On the Convergence of the Concave-Convex Procedure

19 0.048383709 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output

20 0.047599301 128 nips-2009-Learning Non-Linear Combinations of Kernels

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.156), (1, 0.053), (2, 0.009), (3, 0.043), (4, -0.01), (5, -0.036), (6, 0.032), (7, -0.083), (8, 0.111), (9, 0.075), (10, 0.021), (11, -0.013), (12, -0.041), (13, -0.008), (14, 0.028), (15, 0.093), (16, 0.037), (17, 0.023), (18, 0.03), (19, 0.017), (20, -0.017), (21, -0.006), (22, 0.001), (23, 0.088), (24, 0.057), (25, 0.108), (26, -0.004), (27, 0.051), (28, -0.005), (29, 0.105), (30, 0.194), (31, -0.05), (32, -0.066), (33, -0.131), (34, 0.024), (35, 0.058), (36, -0.025), (37, 0.016), (38, -0.079), (39, -0.05), (40, 0.002), (41, -0.05), (42, -0.143), (43, -0.048), (44, 0.062), (45, 0.042), (46, 0.125), (47, 0.153), (48, 0.084), (49, -0.164)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9169696 67 nips-2009-Directed Regression

Author: Yi-hao Kao, Benjamin V. Roy, Xiang Yan

2 0.57018977 104 nips-2009-Group Sparse Coding

Author: Samy Bengio, Fernando Pereira, Yoram Singer, Dennis Strelow

3 0.55967516 55 nips-2009-Compressed Least-Squares Regression

Author: Odalric Maillard, Rémi Munos

4 0.55239916 105 nips-2009-Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction

Author: Grzegorz Swirszcz, Naoki Abe, Aurelie C. Lozano

Abstract: We consider the problem of variable group selection for least squares regression, namely, that of selecting groups of variables for best regression performance, leveraging and adhering to a natural grouping structure within the explanatory variables. We show that this problem can be efﬁciently addressed by using a certain greedy style algorithm. More precisely, we propose the Group Orthogonal Matching Pursuit algorithm (Group-OMP), which extends the standard OMP procedure (also referred to as “forward greedy feature selection algorithm” for least squares regression) to perform stage-wise group variable selection. We prove that under certain conditions Group-OMP can identify the correct (groups of) variables. We also provide an upperbound on the l∞ norm of the difference between the estimated regression coefﬁcients and the true coefﬁcients. Experimental results on simulated and real world datasets indicate that Group-OMP compares favorably to Group Lasso, OMP and Lasso, both in terms of variable selection and prediction accuracy. 1

5 0.4292644 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

Author: Percy Liang, Guillaume Bouchard, Francis R. Bach, Michael I. Jordan

Abstract: Many types of regularization schemes have been employed in statistical learning, each motivated by some assumption about the problem domain. In this paper, we present a uniﬁed asymptotic analysis of smooth regularizers, which allows us to see how the validity of these assumptions impacts the success of a particular regularizer. In addition, our analysis motivates an algorithm for optimizing regularization parameters, which in turn can be analyzed within our framework. We apply our analysis to several examples, including hybrid generative-discriminative learning and multi-task learning. 1

6 0.42448926 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

7 0.41970453 138 nips-2009-Learning with Compressible Priors

8 0.41917944 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors

9 0.41680208 64 nips-2009-Data-driven calibration of linear estimators with minimal penalties

10 0.40736687 173 nips-2009-Nonparametric Greedy Algorithms for the Sparse Learning Problem

11 0.38665831 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

12 0.38026607 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

13 0.37069982 180 nips-2009-On the Convergence of the Concave-Convex Procedure

14 0.35309079 195 nips-2009-Probabilistic Relational PCA

15 0.34387243 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem

16 0.34055433 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints

17 0.33704042 76 nips-2009-Efficient Learning using Forward-Backward Splitting

18 0.33020574 91 nips-2009-Fast, smooth and adaptive regression in metric spaces

19 0.31356141 7 nips-2009-A Data-Driven Approach to Modeling Choice

20 0.30850345 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(24, 0.044), (25, 0.044), (35, 0.03), (36, 0.078), (39, 0.023), (58, 0.565), (61, 0.017), (66, 0.011), (71, 0.039), (81, 0.014), (86, 0.046)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.98329628 43 nips-2009-Bayesian estimation of orientation preference maps

Author: Sebastian Gerwinn, Leonard White, Matthias Kaschube, Matthias Bethge, Jakob H. Macke

Abstract: Imaging techniques such as optical imaging of intrinsic signals, 2-photon calcium imaging and voltage sensitive dye imaging can be used to measure the functional organization of visual cortex across different spatial and temporal scales. Here, we present Bayesian methods based on Gaussian processes for extracting topographic maps from functional imaging data. In particular, we focus on the estimation of orientation preference maps (OPMs) from intrinsic signal imaging data. We model the underlying map as a bivariate Gaussian process, with a prior covariance function that reﬂects known properties of OPMs, and a noise covariance adjusted to the data. The posterior mean can be interpreted as an optimally smoothed estimate of the map, and can be used for model based interpolations of the map from sparse measurements. By sampling from the posterior distribution, we can get error bars on statistical properties such as preferred orientations, pinwheel locations or pinwheel counts. Finally, the use of an explicit probabilistic model facilitates interpretation of parameters and quantitative model comparisons. We demonstrate our model both on simulated data and on intrinsic signaling data from ferret visual cortex. 1

2 0.97369295 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

Author: John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma

Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efﬁciently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the ﬁrst proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision. 1

3 0.95985335 257 nips-2009-White Functionals for Anomaly Detection in Dynamical Systems

Author: Marco Cuturi, Jean-philippe Vert, Alexandre D'aspremont

Abstract: We propose new methodologies to detect anomalies in discrete-time processes taking values in a probability space. These methods are based on the inference of functionals whose evaluations on successive states visited by the process are stationary and have low autocorrelations. Deviations from this behavior are used to ﬂag anomalies. The candidate functionals are estimated in a subspace of a reproducing kernel Hilbert space associated with the original probability space considered. We provide experimental results on simulated datasets which show that these techniques compare favorably with other algorithms.

same-paper 4 0.95701808 67 nips-2009-Directed Regression

Author: Yi-hao Kao, Benjamin V. Roy, Xiang Yan

5 0.94822705 223 nips-2009-Sparse Metric Learning via Smooth Optimization

Author: Yiming Ying, Kaizhu Huang, Colin Campbell

Abstract: In this paper we study the problem of learning a low-rank (sparse) distance matrix. We propose a novel metric learning model which can simultaneously conduct dimension reduction and learn a distance matrix. The sparse representation involves a mixed-norm regularization which is non-convex. We then show that it can be equivalently formulated as a convex saddle (min-max) problem. From this saddle representation, we develop an efﬁcient smooth optimization approach [17] for sparse metric learning, although the learning model is based on a nondifferentiable loss function. Finally, we run experiments to validate the effectiveness and efﬁciency of our sparse metric learning model on various datasets.

6 0.9370172 81 nips-2009-Ensemble Nystrom Method

7 0.76942378 147 nips-2009-Matrix Completion from Noisy Entries

8 0.7683537 36 nips-2009-Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing

9 0.74821085 177 nips-2009-On Learning Rotations

10 0.71641058 243 nips-2009-The Ordered Residual Kernel for Robust Motion Subspace Clustering

11 0.71543527 254 nips-2009-Variational Gaussian-process factor analysis for modeling spatio-temporal data

12 0.69447231 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

13 0.69189328 62 nips-2009-Correlation Coefficients are Insufficient for Analyzing Spike Count Dependencies

14 0.6892035 22 nips-2009-Accelerated Gradient Methods for Stochastic Optimization and Online Learning

15 0.68719077 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models

16 0.68670148 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

17 0.68332756 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

18 0.68149906 202 nips-2009-Regularized Distance Metric Learning:Theory and Algorithm

19 0.67769837 163 nips-2009-Neurometric function analysis of population codes

20 0.67738944 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints