text:
\section*{\centering #1}}

\def\foot#1#2{{\baselineskip=9pt\sevenrm\footnote{$^{#1}$}{#2}}}
\def\noindent\hangindent=1.5truecm\hangafter=1{\noindent\hangindent=1.5truecm\hangafter=1}
\def\bigskip{\bigskip}
\def\centerline{\centerline}
\def\medskip{\medskip}
\def\noindent{\noindent}
\def\vfill\eject{\vfill\eject}
\def\vfill\eject\end{\vfill\eject\end}

\def\alpha{\alpha}
\def{\rm A}{{\rm A}}
\def\allowbreak{\allowbreak}
\def{\rm B}{{\rm B}}
\def{\bar X}{{\bar X}}
\def{\bar Y}{{\bar Y}}
\def{\cal I}{{\cal I}}
\def{\cal L}{{\cal L}}
\def{\cal J}{{\cal J}}
\def{\cal M}{{\cal M}}
\def{\cal S}{{\cal S}}
\def{\cal T}{{\cal T}}
\def\delta{\delta}
\def\epsilon{\epsilon}
\def\gamma{\gamma}
\def^{1/2}{^{1/2}}
\def{\hat g}{{\hat g}}
\def{\hat\ga}{{\hat\gamma}}
\def{\hat\jmath}{{\hat\jmath}}
\def{\widehat\Sigma}{{\widehat\Sigma}}
\def{\rm I\!R}{{\rm I\!R}}
\def^{-1/2}{^{-1/2}}
\def^{-1}{^{-1}}
\def\,|\,{\,|\,}
\def\to{\to}
\def\ra\infty{\to\infty}
\def\sigma{\sigma}
\def\Sigma{\Sigma}
\def\sum_i\,{\sum_i\,}
\def\sum_{i=1}^n\,{\sum_{i=1}^n\,}
\def^{{\rm T}}{^{{\rm T}}}
\def{\textstyle{1\over2}}{{\textstyle{1\over2}}}
\def^0{^0}

\def\displaystyle{\displaystyle}

\setlength{\captionmargin}{1cm}

\pdfminorversion=4

\begin{document}

\begin{center}
{\LARGE\bf An Algorithm for Nonlinear, Nonparametric Model Choice and Prediction}

~\\~\\ {\large Fr\'ed\'eric FERRATY\footnote{\noindent Fr\'ed\'eric Ferraty is Professor, Toulouse Mathematics Insitute, University of Toulouse, 31062 Toulouse, France (E-mail: frederic.ferraty@math.univ-toulouse.fr). Peter Hall is Professor, Department of Mathematics and Statistics, University of Melbourne, Parkville 3010, Australia (E-mail: halpstat@ms.unimelb.edu.au)}, and Peter HALL}

\end{center}
~\\
\hspace*{1cm}\begin{minipage}[c]{0.85\textwidth}
We introduce an algorithm which, in the context of nonlinear regression on vector-valued explanatory variables, chooses those combinations of vector components that provide best prediction. The algorithm devotes particular attention to components that might be of relatively little predictive value by themselves, and so might be ignored by more conventional methodology for model choice, but which, in combination with other difficult-to-find components, can be particularly beneficial for prediction. Additionally the algorithm avoids choosing vector components that become redundant once appropriate combinations of other, more relevant components are selected.  It is suitable for very high dimensional problems, where it keeps computational labour in check by using a novel sequential argument, and also for more conventional prediction problems, where dimension is relatively low. We explore properties of the algorithm using both theoretical and numerical arguments.
\end{minipage}
~\\
\hspace*{1cm}\begin{minipage}[c]{0.85\textwidth}  ~\\ {\bf Key Words:}
Feature and variable selection; combinations of variables; nonparametric regression; sequential algorithm
\end{minipage}

\section{INTRODUCTION}

\noindent For more than 30 years statisticians have sought to identify the relevant vector components in relatively high-dimensional prediction problems.  Today, in the case of data from fields such as genomics, astronomy and consumer preference modeling, the challenges are greater than in the past, with the ratio of dimension to sample size often being higher than every before.  In the present paper we suggest a new, highly adaptive algorithm that can be used to build predictive models in both contemporary and classical settings.  Our approach is designed specifically for cases where the response is a nonlinear function of the predictors, and where we wish to be economical in our choice of variables.

Particularly in cases where dimension is greater than sample size, a great deal of attention has been devoted in the last 15 years to model choice in the framework of linear models. In this setting, Tibshirani's (1996) lasso was the starting point for the development of many techniques: coordinate descent methods (Fu, 1998, Friedman {\em et al.}, 2007), smoothly clipped absolute deviation (Fan and Li, 2001), least angle regression (Efron {\em et al.}, 2004), elastic net (Zou and Hastie, 2005), adaptative lasso (Zou, 2006), Dantzig selector (Cand\`es and Tao, 2007), relaxed lasso (Meinshausen, 2007), group lasso (Yuan and Lin, 2008), multi-step adaptative lasso (B\"uhlmann and Meier, 2008). Overviews of this work have been provided by Hastie {\em et al.}~(2009), Fan and Lv (2010) and B\"ulhmann and van de Geer (2011).

These variable selection tools have been applied successfully to various high-dimensional datasets, but their effectiveness can be hindered by the assumption of a linear relationship between response and covariates. One problem is that the high-dimensional setting makes it difficult to validate the existence of the linear relationship. Moreover, it is common to encounter nonlinear structure even in standard, relatively low-dimensional multivariate regression models, and there is no a priori reason why such structure should not occur in high-dimensional cases.

However, it can be very challenging to investigate nonlinear relationships when there are many variables.  There exists a literature on additive modeling, which often is treated as an extension of the lasso by combining the group lasso with basis expansion of each one-dimensional additive component.  See, for example, the work of Meier {\em et al.}~(2009), Ravikumar {\em et al.}~(2009) and Huang {\em et al.}~(2010).

Ferraty {\em et al.}~(2010) endeavoured to go beyond these techniques by developing methodology that captures interactions, using a stepwise forward search algorithm founded on minimizing a cross-validation criterion.  However, although this approach enjoys good performance in many cases, it fails in a worrying number of cases, where small submodels are not detected.

The new algorithm suggested in this paper is based on enlarging the class of possible combinations of covariates retained at each step, while keeping the run time within reasonable bounds.  This is an important issue from a pratical viewpoint. Our methodology is given in Section~2, where our approach to building and selecting submodels is discussed first in overview and then described in detail.  The technique is illustrated in Section~3 by application to a real genomics dataset, and in Section~4 in a simulation study.  Theoretical issues are treated in Section~5.
\bigskip

\section{METHODOLOGY}

\subsection{Measuring mean squared variation.}

Given independent and identically distributed data pairs $(X_i,Y_i)$ for $i\in{\cal S}=\{1,\ldots,n\}$, where $X_i=(X_{i1},\ldots,X_{ip})$ is a $p$-vector and $Y_i$ is a scalar, we wish to choose a small number of vector components, or variables or features, of $X_i$ on which to regress $Y_i$, with the aim of predicting a future $Y$ for a given~$x=(x_1,\ldots,x_p)$.

Our methodology is built around an algorithm, discussed in Section~2.2 and defined concisely in Section~2.3, for determining the extent to which a given subsequence,  $X_{ij_1},\ldots,X_{ij_\ell}$ say, of the components of $X_i$ successfully predict~$Y_i$.  Each step of the algorithm involves using our favorite nonparametric function estimator, for example a local linear approach or a spline, to construct a predictor ${\hat\ga}_{j_1,\dots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})$ of $Y$ from the dataset $\{(X_{ij_1},\ldots, X_{ij_\ell},Y_i);~i\in{\cal S}\}$, where $(x_{j_1},\ldots,x_{j_\ell})$ is a subvector of $x$.  Then compute the standard cross-validation criterion
$$
S(j_1,\ldots,j_\ell)=\sum_{i=1}^n \: \{Y_i-{\hat\ga}_{j_1,\ldots,j_\ell}^{-i}(X_{ij_1},\ldots,X_{ij_\ell})\}^2\,
w_\ell(X_{ij_1},\ldots,X_{ij_\ell})\,,\eqno(2.1)
$$
which measures the success of ${\hat\ga}_{j_1,\ldots,j_\ell}^{-i}(X_{ij_1},\ldots,X_{ij_\ell})$ in predicting~$Y_i$ where ${\hat\ga}_{j_1,\ldots,j_\ell}^{-i}$ is the leave-one-out estimator derived from ${\cal S}\mbox{\textbackslash}\{i\}$.  The function $w_\ell$ in (2.1) is taken to be nonnegative.

In order to simplify notation, let ${\cal J}=\{j_1,\ldots,j_\ell\}$ be a subset of  $\{1,\ldots,p\}$ so that, for any $p$-dimensional vector $u=(u_1,\ldots,u_p)$ of $\mathbb{R}^p$, $u^{\cal J}$ stands for the subvector $(u_{j_1},\ldots,u_{j_\ell})$.   Then, (2.1) may be written in an equivalent way as
$$
S({\cal J})=\sum_{i\in{\cal T}} \: \{Y_i-{\hat\ga}_{{\cal J}}^{-i}(X_i^{{\cal J}})\}^2\,
w_{|{\cal J}|}(X_i^{{\cal J}})\,,\eqno(2.2)
$$
where $|{\cal J}|$ is the size of ${\cal J}$.

If ${\cal J}_1,\ldots,{\cal J}_k$ are distinct subsets of indices then the permutation of ${\cal J}_1,\ldots,{\cal J}_k$ that is used in each of the steps in Section~2.3, for different values of $k$, is that which places the values of $S({\cal J}_1),\ldots,S({\cal J}_k)$ in increasing order.  In the subsequent step of the algorithm we merge ${\cal J}_1,\ldots,{\cal J}_k$ in a pairwise manner, creating new subsets of indices ${\cal J}_1\cup{\cal J}_2$, $\ldots$, ${\cal J}_1\cup{\cal J}_k$, $\ldots$, ${\cal J}_{k-1}\cup{\cal J}_k$ that are rearranged again to rank the corresponding predictive values; and we repeat this process until we obtain a subset ${\cal J}$ with a sufficiently small value of~$S({\cal J})$.

\subsection{Overview of algorithm.}

The first step of the algorithm involves searching over all single subsets $\{1\},\ldots,\{p\}$, the next over all combinations $\{j,j'\}$, the third over all  combinations of the previous ones (i.e.\ $\{j_1, j_1'\}\cup\{j_2, j_2'\}$), and so on. Normally this would be prohibitively expensive from a computational viewpoint.  Indeed, in many problems doing even the $O(p^2)$ search over pairs of indices would be out of the question.  However, we use the following ``trick'' to reduce labour.  Having searched over single subsets and ranked the variables there, we look only at the top $\sqrt{p}$ variables when constructing the sets $\{j,j'\}$ over which we search in the next step.  There are only $O(\sqrt{p}^{2})=O(p)$ subsets of indices constructed in this way, and so the search over sets $\{j, j'\}$ is not much more onerous than it was in the case of the single subsets.

In Section~2.3 we note that $O(p)$ may not, in general, be a good description of the upper bound to the capability of our computational resources.  Instead we take $O(q)$ to be that bound, where $q$ might be larger than $p$ if our resources are relatively extensive, or less than $p$ if the inherent multiplier of a power of $n$, which for simplicity we omitted from the arguments above, is problematic.  In this case our algorithm ``sniffs out'' the trace of potentially significant variables among the first $\sqrt{q}$ variables when building bivariate predictors, and subsequently also when constructing predictors of higher order.  For now, however, we assume that $q=p$.

It should be stressed that the steps in our algorithm rely on the variables that are ``useful'' for prediction making themselves known, to at least some extent, when we are experimenting with prediction based on a single variable.  Experimentation is described in Step~1 in Section~2.3.  Variables that are useful for building higher-order predictors do not have to be present in the top few of the $p$ variables, but some of them should be apparent with sufficient strength to lie among the top $\sqrt{p}$ variables.  It is difficult to see how this constraint can be removed without using a relatively a crude, model-based approached to variable selection.  The advantage of our alternative approach is that, if a variable shows itself to be just slightly useful for prediction in isolation, in particular if it lies among the top $\sqrt{p}$ variables, then we have an opportunity to detect its importance even if its main contributions are felt only when it operates in conjunction with
 one or more other variables.  In contrast, conventional approaches to feature selection, based on linear models, can completely overlook variables that have a major impact only through interaction with one or more other variables.

\subsection{Details of algorithm.}

\noindent{\sl Step~1: Prediction based on a single variable.}~Consider the $p$ singletons ${\cal J}_1=\{1\},\ldots,{\cal J}_p=\{p\}$, and compute the permutation ${\hat\jmath}_1(1),\allowbreak\ldots,{\hat\jmath}_1(p)$ of the indices $1,\ldots,p$ that represents the ranking $S\{{\cal J}^1(1)\}\leq\ldots\leq S\{{\cal J}^1(p)\}$, with ${\cal J}^1(k)={\cal J}_{{\hat\jmath}_1(k)}$ for $1\leq k\leq p$ and where $S$ is defined as at~(2.1).  If ${\hat\jmath}_1(k_1)<{\hat\jmath}_1(k_2)$ then $X_{i{\hat\jmath}_1(k_1)}$ better explains $Y_i$, in a particular sense, than does $X_{i{\hat\jmath}_1(k_2)}$.  In this sense, a regression of $Y$ on the ${\hat\jmath}_1(1)$th component of $X$ produces the ``best'' predictor based on a single variable.

\noindent{\sl Step~2: Prediction based on two variables.} Assume that our computing resources are limited to $O(q)$ calculations, multiplied by a low power of $n$, and put $p_1=\sqrt{q}$. From the top $p_1$ subsets ${\cal J}^1(1),\ldots,{\cal J}^1(p_1)$, build the set of all $p_2^*={\textstyle{1\over2}}\,p_1\,(p_1-1)=O(q)$ pairs ${\cal J}_1={\cal J}^1(1)\cup{\cal J}^1(2),\ldots,{\cal J}_{p_1-1}={\cal J}^1(1)\cup{\cal J}^1(p_1),{\cal J}_{p_1}={\cal J}^1(2)\cup{\cal J}^1(3),\ldots,{\cal J}_{p_2^*}={\cal J}^1(p_1-1)\cup{\cal J}^1(p_1)$. Then, compute the permutation ${\hat\jmath}_2(1),\allowbreak\ldots,{\hat\jmath}_2(p_2^*)$ of the indices $1,\ldots,p_2^*$ that places the values $S({\cal J}_{{\hat\jmath}_2(k)})$, for $1\leq k\leq p_2^*$, in increasing order, and retain for the next step only the $p_2=p_1=\sqrt{q}$ top subsets ${\cal J}^2(1)={\cal J}_{{\hat\jmath}_2(1)},\ldots,{\cal J}^2(p_2)={\cal J}_{{\hat\jmath}_2(p_2)}$.  A regression of $Y$ on $X^{{\cal J}^2(1)}$ provides the ``best'' predictor based on just two variables.

\noindent{\sl Steps~3,4,$\ldots$: Prediction based on $\ell\geq 3$ variables.} In step 1, or respectively step 2, the procedure builds only singletons, or respectively pairs. However, in step $\ell\geq 3$ the algorithm may generate subsets ${\cal J}$ of indices such that $\ell\leq|{\cal J}|\leq 2^{\ell-1}$. For instance, if we consider the sets ${\cal J}^2(1)=\{j_1,j_2\},~{\cal J}^2(2)=\{j_1,j_3\},~{\cal J}^2(3)=\{j_2,j_4\},~\ldots$, the third step of our algorithm will build a new family of subsets containing ${\cal J}^2(1)\cup{\cal J}^2(2)=\{j_1,j_2,j_3\},{\cal J}^2(1)\cup{\cal J}^2(3)=\{j_1,j_2,j_4\},\ldots,{\cal J}^2(2)\cup{\cal J}^2(3)=\{j_1,j_2,j_3,j_4\},\ldots$, which produces subsets of size 3 or 4.  Assume we have constructed, in the previous step, an ordered sequence of subsets ${\cal J}^{\ell-1}(1),\ldots,{\cal J}^{\ell-1}(p_{\ell-1})$ where all indices of each subset are listed in increasing numerical order and the subsets are ordered so that the corresponding values of $S\{{\cal J}^{\ell-1}(j)\}$ are increasing. The new family of subsets

 ${\cal J}_1={\cal J}^{\ell-1}(1)\cup{\cal J}^{\ell-1}(2),\ldots,{\cal J}_{p_{\ell-1}-1}={\cal J}^{\ell-1}(1)\cup{\cal J}^{\ell-1}(p_{\ell-1}),~{\cal J}_{p_{\ell-1}}={\cal J}^{\ell-1}(2)\cup{\cal J}^{\ell-1}(3),\ldots$ is filtered in order to retain only $p_\ell^*$ distinct subsets where $p_\ell^*\leq {\textstyle{1\over2}}\,p_{\ell-1}\,(p_{\ell-1}-1)$, and the indices in each subset form a strictly increasing sequence. Then, the permutation ${\hat\jmath}_\ell(1),\ldots,{\hat\jmath}_\ell(p_\ell^*)$ of $1,\ldots,p_\ell^*$ is carried out so that $S({\cal J}_{{\hat\jmath}_\ell(1)})\leq\ldots\leq S({\cal J}_{{\hat\jmath}_\ell(p_\ell^*)})$, and we retain for the next step only the $p_\ell=\min(p_1,p_\ell^*)$ top subsets ${\cal J}^\ell(1)={\cal J}_{{\hat\jmath}_\ell(1)},\ldots,{\cal J}^\ell(p_\ell)={\cal J}_{{\hat\jmath}_\ell(p_\ell)}$.

The algorithm can be terminated when a predetermined percentage of the mean squared variation among the $Y_i$s is explained by the regressions, or when the difference between two successive measures of that variation falls below a given level, or there is a marked ``kink'' in a graph of the minimum value of $S\{{\cal J}^\ell(1)\}$ against~$\ell$.  The second of these three rules can be interpreted as stopping as soon as, for some $\ell\geq1$,
$$
\frac{S\{{\cal J}^\ell(1)\}-S\{{\cal J}^{\ell+1}(1)\}}{S\{{\cal J}^\ell(1)\}}\leq t\,,\eqno(2.3)
$$
where $t=t(n)$ is a user-choosable threshold expressing a necessary minimum gain in going to the next step.  The estimator ${\hat g}$ is then computed in a standard way, using the ``favorite nonparametric function estimator'' referred to in Section~2.1, from the data pairs $(X_i^{{\cal J}^\ell(1)},Y_i)$ for $1\leq i\leq n$, where $X_i^{{\cal J}^\ell(1)}=(X_{ij})_{j\in{\cal J}^\ell(1)}$.  The ``kink'' approach is commonly used to determine a stopping point for clustering algorithms, where the value of $S$ at (2.1) is replaced by a measure of the tightness of a cluster.

 From now on, this nonparametric variable selection method will be referred to as NOVAS.

\subsection{Practical issues.}

Our method is computationally intensive; launching it with a very large dataset may be time consuming. One way to speed up computation is to parallelize the algorithm. Indeed, as soon as a computer is equipped with a multicore processor, which is the case for most current computers, parallelization allows us to process independent tasks simultaneously. The running time is then divided by the number of independent tasks that the multicore processor is able to manage. The programming language R (R Development Core Team, 2011) offers packages that make such a parallelization easy; see for instance the R package ``doSNOW'' of Revolution Analytic (2011). In addition, since R is freeware and used intensively by academic researchers, this programming language is one of the most popular in the statistical community. For these reasons we decided to use the R programming language to implement our variable selection method. All results presented with respect to the real dataset application (see Section \ref{sec:genomicsdata}) were obtained using a laptop with a 4-core, 2 GHz processor with 4 Go RAM. To give an idea about the run time, the R routine NOVAS is repeated for an artificial dataset containing $p=$100, 500, 1,000, 5,000, 10,000 and 50,000 covariates in such a way that $\ell=4$ steps are run systematically for each $p$ with $n=100$ and default threshold parameter $t=0.05$. Seven parallel jobs are launched (which is the more efficient number of parallel jobs for the used laptop); the corresponding run times (in seconds) are displayed in Figure \ref{fig1}; for instance, NOVAS lasts 691s when $p=10000$. It is worth noting an almost perfect linear relationship between the log number of variables, i.e.\ values of $p$, and the corresponding log run time.
\begin{figure}[h]
\begin{center}
\includegraphics[height=6cm, width=8cm]{RunTimeVSLogNbofVar.eps}
\caption{Linear fits based six points, depicted by the solid line, and only the first two points, indicated by the dashed line.}
\label{fig1}
\end{center}
\end{figure}
As suggested there, considering only $p=100$ and $p=500$ is enough to gain a good approximation to the run time for much higher dimensional cases. The simulation study, which requires massive computations, was granted access to a supercomputer resource (see the acknowledgements).

The nonparametric regression estimator ${\hat\ga}_{{\cal J}}$,  introduced in (2.1), is the usual local linear one (see e.g.\ Fan and Gijbels, 1996). In order to speed up the computations, the covariates are standardized and for each subset ${\cal J}$, we chose a common bandwidth among given a set of bandwidths to minimize the cross-validation criterion $S({\cal J})$ defined at (2.2) with $w_{|{\cal J}|}\equiv 1$.

\section{GENOMICS DATASET}\label{sec:genomicsdata}

This dataset was discussed by Bushel {\em et al.} (2007).  It is also addressed in the R package mixOmics, which is designed to explore and integrate omics data and was developed by Dejean {\em et al.}~(2011). The dataset treats liver toxicity and contains the expression levels of 3116 genes, or covariates, and nine clinical measurements, or scalar responses, for 64 rats. The original dataset included supplementary clinical responses, but these were not used since only three distinct values were available.

Our aim was to select, for each scalar response, the genes leading to the best predictor in terms of the cross-validation criterion at~(2.1). Table \ref{tab1} details stages of NOVAS when the aim is to predict the level of urea nitrogen. As pointed out earlier, the final model may involve variables not necessarily identified as the most predictive ones in the previous stages.
\begin{table}[h]
\caption{\label{tab1}The table gives, at each stage, the best predictive subset of variable number(s) and corresponding leave-one-out cross-validation criterion.}
\centering
\begin{tabular}{crc}
Stage number & Selected genes numbers & cv\\~\\ \hline
1 & 1165 & 6.83\\ \hline
2 & 1866\ 2050 & 5.22\\ \hline
3 & 1000\ 1167\ 1837\ 1957 & 3.76\\ \hline
4 & 1000\ 1167\ 1837\ 1899\ 1957 & 3.27\\ \hline
\end{tabular}
\end{table}
Table \ref{tab2} gives, for each clinical measurement, the gene numbers, i.e.\ the subset $\widehat{{\cal J}}$, selected by NOVAS, together with values of the corresponding cross-validation criterion, i.e.\ $S(\widehat{{\cal J}})$,
\begin{table}[h]
\caption{\label{tab2}NOVAS selected models for each clinical measurement.}
\centering
\begin{tabular}{c m{8cm}}
Clinical measurement & Selected genes numbers \\~\\ \hline
BUN & 1000\ 1167\ 1837\ 1899\ 1957 \\ \hline
TP & 1159\ 1970\ 2020\ 2173\ 2923\  2927\ 2971 \\ \hline
ALB & 1038\ 1165\ 1992\ 2020\ 2105\ 2669\ 2867\ 2921 \\ \hline
ALT & 1846\ 1871\ 1883\ 1909\ 1910\ 1911\ 1915\ 1921\ 2042 \\ \hline
SDH & 764\ 1145\ 1624\ 1866\ 1940\ 1992\ 1996\ 2894 \\ \hline
AST & 977\ 1116\ 1161\ 1335\ 1826\ 1891\ 1909\ 1961\ 2197\ 2201 \\ \hline
ALP & 1064\ 1484\ 1817\ 1823\ 2007\ 2385\ 2819 \\ \hline
TBA & 1891\ 1913\ 1916\ 1917\ 1954\ 2200\ 2205 \\ \hline
CHOL & 1836 1875 2044 \\ \hline
\end{tabular}
\end{table}
where the clinical response abbreviations were defined as follows: BUN, urea nitrogen;  TP, total protein; ALB, albumin; ALT, alanine aminotransferase; SDH, sorbitol dehydrogenase; AST, aspartate aminotransferase; ALP, alkaline phosphatase; TBA, total bile acids; and CHOL, cholesterol. Two clinical responses, BUN and CHOL, require three or five genes. Other clinical measurements, including AST, involve many more genes. Figure \ref{fig2} displays, for each clinical variable, the observed values plotted against the leave-one-out predictions. As can be seen, clinical responses are well explained by the selected genes.
\begin{figure}[h]
\centering
\makebox{\includegraphics[height=12cm,width=14cm]{Observations.vs.estimations.eps}}
\caption{\label{fig2}Observations (horizontal axis) plotted against leave-one-out predictions for each clinical measurement.}
\end{figure}

An important question arises: is the quality of the leave-one-out predictions high? To answer this question we propose comparing the leave-one-out cross-validation criterion, i.e.\ $S(\widehat{{\cal J}})$, obtained by NOVAS, with various alternative predictive methods:
\begin{itemize}
\item[$\bullet$] partial least squares regression, PLS, which is a non-selective iterative linear method and derives successive linear combinations, or loadings, of covariates maximizing its correlation with the response. It was originally developed by Wold (1966) for applications in economics and became a popular tool in the chemometrics community; see, for instance, Geladi and Kowalski (1986) or Martens and Naes (1989);
\item[$\bullet$] a sparse version of PLS, sPLS, including a lasso step leading to sparse loadings, developed by L\^e Cao {\em et al.} (2008), who experimented with this genomics dataset;
\item[$\bullet$] least angle regression, LAR, introduced by Efron {\em et al.} (2004), which is one of the most popular selective linear regression methods;
\item[$\bullet$] most predictive design points (MPDP), which is also an existing nonparametric alternative method and which we shall discuss in Section~4.5.
\end{itemize}
The PLS method requires the choice of only one parameter, the total number of loadings, whereas sPLS needs several variables, specifically the total number of loadings and the sparsity expressed as the number of zeros for each loading. The LAR procedure requires choice of the optimal fraction of non-zero values in the vector of parameters. For all these competing methods, the parameters were optimized so as to minimize the predictive leave-one-out criterion, and Table 3 gives the smallest leave-one-out cross-validation values obtained for each procedure.
\begin{table}
\caption{\label{tab3}Leave-one-out cross-validation values for each clinical measurement, or response, and each method.  Minimum values in each row are given in bold.}\centering
\begin{tabular}{cccccc}
\backslashbox{Responses}{Methods} & PLS & sPLS & LAR & MPDP & NOVAS \\ \hline
BUN  & 6.62 & 8.106 &  8.67 & {\bf 2.62} & 3.27\\ \hline
TP  & 0.104 & 0.115 & 0.117 & 0.072 & {\bf 0.045}\\ \hline
ALB  & 0.0351 & 0.0378 & 0.044 & 0.02 & {\bf 0.015}\\ \hline
ALT  & 1236163 & 1260917 & 1709814 & {\bf 46834} & 60621\\ \hline
SDH & 19736.38 & 23512.95 & 21314.9  & 2669.6 & {\bf 1404.7}\\ \hline
AST  & 5232362 & 6131264 & 92534432 & 2580580 & {\bf 318682}\\ \hline
ALP  & 3097.81 & 3194.96 & 3203.1 & 1225.4 & {\bf 1043.7}\\ \hline
TBA & 138.26 & 118.63 & 153.12 & 67.50 & {\bf 39.73}\\ \hline
CHOL & 76.91 & 72.87 & 94.96 & {\bf 26.77} & 40.68\\ \hline
\end{tabular}
\end{table}
It can be seen that NOVAS outperforms alternative linear methods, since it is able to take nonlinearities into account.

To enable predictive performances to be visualized, Figure \ref{fig3} compares, for each method, the results of leave-one-out estimation applied to a sample of four clinical measurements: TP, SDH, AST and CHOL. Clearly, the two nonparametric selective procedures, NOVAS and MPDP, have significantly greater predictive performance than the linear procedures, and NOVAS is much the stronger of the two.  For example, NOVAS leads to more accurate predictions in most cases, and enjoys spectacular performance when applied to predicting the clinical measurement AST.
\begin{figure}[h]
\centering
\makebox{\includegraphics[height=12cm, width=14cm]{Estimations.for.each.method.eps}}
\caption{\label{fig3}Four observed responses, TP, SDH, AST and CHOL, against leave-one-out estimations.}
\end{figure}

\section{ASSESSING PERFORMANCE}

\subsection{Simulated regression models.}

We consider five models, indexed by a superscript $m$ in square brackets and having the form
$$
Y_i \ =\ \gamma_{1,2,3}^{[m]} (X_{i1},X_{i2},X_{i3})\, +\, \varepsilon_i^{[m]},\ i=1,\ldots,n_m,
$$
where
$$
\begin{array}{ccl}
\gamma_{1,2,3}^{[1]}(X_{i1},X_{i2},X_{i3}) & = & X_{i1}^2+X_{i2}^2+X_{i3}^2\:, \\~\\
\gamma_{1,2,3}^{[2]}(X_{i1},X_{i2},X_{i3}) & = & \left|X_{i1}X_{i2}\right|+\left|X_{i1}X_{i3}\right| +\left|X_{i2}X_{i3}\right|,\\~\\
\gamma_{1,2,3}^{[3]}(X_{i1},X_{i2},X_{i3}) & = & \left|X_{i1}X_{i2}X_{i3}\right|, \\~\\
\gamma_{1,2,3}^{[4]}(X_{i1},X_{i2},X_{i3}) & = &\displaystyle \frac{\left|X_{i1}X_{i2}\right|+X_{i3}^2}{2+X_{i1}X_{i2}X_{i3}}\:,\\~\\
\gamma_{1,2,3}^{[5]}(X_{i1},X_{i2},X_{i3}) & = &\displaystyle \frac{\left|X_{i1}X_{i2}\right|+\left|X_{i1}X_{i3}\right|}{2+\left|X_{i2}X_{i3}\right|}\:.
\end{array}
$$
The vector components $X_{ij}$ are taken to be independent and identically distributed as uniform $[-1,1]$, and the errors $\varepsilon_i^{[m]}$ are independent and identically distributed as normal $N(0,\sigma_m^2)$, where $\sigma_m^2=0.05\,{\rm var}\{\gamma_{1,2,3}^{[m]}(X_{i1},X_{i2},X_{i3})\}$.
Different sample sizes will be considered in the simulation study to take into account the varying complexities and dimensionalities of these models.

\subsection{Influence of the sample size, $n$, and the number, $p$, of covariates.}\label{sec:influence-n-p}

Is our NOVAS procedure able to recognize the correct subset ${\cal J}=\{1,2,3\}$, even for large values of~$p$?  To answer this question our selected procedure was launched on each of the five models with four sample sizes $n=50,\,100,\,150,\,200$, three different sets of covariates of size $p=100,\,1000,\,10000$ and the threshold parameter $t$, defined at (2.3), set equal to 0.05 for all runs. We then consider $5\times4\times 3$ situations and the simulation scheme was repeated 100 times, producing 100 datasets for each situation. Table \ref{tab4} presents the results in order of sample size. One remarks that higher is the complexity of the model, larger has to be the sample size for recognizing it correctly. So, the role played by the  sample size $n$ corroborates what happens usually in statistics; higher is the dimensionality of the model, larger has to be the sample size for getting good estimation. For a too small sample size (i.e. $n=50$), NOVAS is not able to recognize models with a good frequency excepted Model 1 when $p=100$. In the opposite, when considering a large sample size (i.e. $n=200$), one gets good results for all models, even for large set of covariates. When focusing on the influence of the number $p$, its impact on the behaviour of NOVAS is clear: higher is the size of the set of covariates, lower is the frequency of selecting the correct model. However, as soon as one considers a sample size for each model large enough, the influence of $p$ is not so dramatic; for any $p=100,\,1000,\,10000$, one gets good and stable results for models 1 and 2 when $n=100$, model 3 when $n=150$, and models 4 and 5 when $n=200$.
\begin{table}[h]
\caption{\label{tab4}Number of times, out of 100, that NOVAS selected the correct model.}
\centering
\begin{tabular}{lll}
\begin{tabular}{c}
 \\
$p$  \\ \hline\hline
Model 1 \\ \hline
Model 2 \\ \hline
Model 3 \\ \hline
Model 4 \\ \hline
Model 5\\ \hline
\end{tabular}
&\begin{tabular}{ccc}
\multicolumn{3}{c}{$n=50$}\\
100 & 1000 & 10000 \\ \hline\hline
84 & 46 & 12 \\ \hline
49 & 25 & 1 \\ \hline
4 & 2 & 0 \\ \hline
18 & 6 & 0 \\ \hline
2 & 1 & 0\\ \hline
\end{tabular}
& \begin{tabular}{ccc}
 \multicolumn{3}{c}{$n=100$}\\
  100 & 1000 & 10000 \\ \hline\hline
  99 & 100 & 100 \\ \hline
  100 & 99 & 97 \\ \hline
  89 & 79 & 56 \\ \hline
  78 & 58 & 34 \\ \hline
  46 & 28 & 1\\ \hline
\end{tabular}
\\ ~\\
\begin{tabular}{c}
 \\
$p$  \\ \hline\hline
Model 1 \\ \hline
Model 2 \\ \hline
Model 3 \\ \hline
Model 4 \\ \hline
Model 5\\ \hline
\end{tabular}
&\begin{tabular}{cccc}
\multicolumn{3}{c}{$n=150$}\\
100 & 1000 & 10000 \\ \hline\hline
100 & 100 & 100 \\ \hline
100 & 100 & 100 \\ \hline
100 & 100 & 99 \\ \hline
97 & 91 & 74 \\ \hline
76 & 67 & 54\\ \hline
\end{tabular}
& \begin{tabular}{ccc}
\multicolumn{3}{c}{$n=200$}\\
 100 & 1000 & 10000 \\ \hline\hline
 100 & 100 & 100 \\ \hline
 100 & 100 & 100 \\ \hline
 100 & 100 & 100 \\ \hline
 100 & 98 & 95 \\ \hline
 97 & 90 & 76\\ \hline
\end{tabular}
\end{tabular}
\end{table}

\subsection{Influence of the threshold $t$.}

According to the previous section, considering different sample sizes allows to reduce the effect of the dimensionality of the simulated models on NOVAS (see Table \ref{tab5}). A high value of $t$ tends to stop the procedure too early, in which case NOVAS would retain too small a set of variables. A low value of $t$ results in the selected model incorporating too large a number of variables. However, as we shall show, NOVAS is not particularly sensitive to the value of $t$.
\begin{table}
\caption{\label{tab5}Number of times, out of 100, that NOVAS selected the correct model when $p=1000$.}
\centering
\begin{tabular}{cccccccccccc}
$t$ & 0.01 & 0.05 & 0.1 & 0.15 & 0.2 & 0.25 & 0.3 & 0.35 & 0.4 & 0.45 & 0.5 \\ \hline\hline
Model 1 ($n= 100$) &  100 & 100 & 100 & 100 &  100 & 98 & 95 & 72 & 46 & 12 & 8 \\ \hline
Model 2 ($n= 100$) &  99 & 100 & 99 & 100 &  98 & 87 & 69 & 41 & 25 & 5 & 1 \\ \hline
Model 3 ($n= 150$) &  100 & 100 & 99 & 99  & 94 & 88 & 61 & 44 & 9 & 1 & 0 \\ \hline
Model 4 ($n= 200$) &  98 & 98 & 99 & 94 & 69 & 38 & 12 & 6 & 1 & 0 & 0 \\ \hline
Model 5 ($n= 200$) &  92 & 90 & 87 & 89 & 84  & 75 & 45 & 17 & 2 & 1 & 0\\ \hline
\end{tabular}
\end{table}
As indicated in Table \ref{tab5}, there is a range of values for $t$, i.e.\ $t\leq0.2$, where NOVAS provides stable results. This encouraged us to use the default value $t=0.05$.

\subsection{Influence of noise-to-signal ratio.}

Noise-to-signal ratio is defined by ${\rm nsr}=\sigma_m^2/\mbox{var}\{\gamma_{1,2,3}^{[m]}\left(X_{i1},X_{i2},X_{i3}\right)\}$. Up to now, ${\rm nsr}=0.05$ has been used in our numerical experiments.  Table~\ref{tab6} summarises the influence of noise-to-signal ratio on the behaviour of NOVAS, and it can be seen that performance decreases by 10~to~54\% as noise-to-signal ratio increases by 100~to~700\%.
\begin{table}[h]
\caption{\label{tab6}Number of times, out of 100, that NOVAS selected the correct model when $p=1000$.}
\centering
\begin{tabular}{ccccc}
nsr & 0.05 & 0.1 & 0.2 & 0.4 \\ \hline\hline
Model 1 ($n=100$)  & 100 & 100 & 100 & 78 \\ \hline
Model 2 ($n=100$) & 100 & 98 & 91 & 58\\ \hline
Model 3 ($n=150$) & 100 & 100 & 96 & 84\\ \hline
Model 4 ($n=200$) & 98 & 96 & 99 & 89\\ \hline
Model 5 ($n=200$) & 90 & 96 & 75 & 41\\ \hline
\end{tabular}
\end{table}
Nevertheless, the performance of NOVAS remains stable with respect to noise-to-signal ratio;  when ${\rm nsr}=0.1$, the ability of NOVAS to recognise the true subset is very good for all models, when ${\rm nsr}=0.2$, NOVAS is still largely correct for models 1 to 4, and when ${\rm nsr}=0.4$ the results for models 1, 3 and 4 are reasonable. The performance of NOVAS, and of the competing methods that we shall discuss in the next section, degrades further for higher values of noise-to-signal ratio.

\subsection{Comparison with other methods.}

In this section, we compare NOVAS with the other competing methods introduced in Section~3: PLS, sPLS, LAR and MPDP which is a nonparametric selective technique  called ``most predictive design points,'' or MPDP proposed by Ferraty {\em et al.} (2010). Originally developed for functional data, the method remains valid in the more conventional high-dimensional setting of the present paper. The idea is to select, one by one, several variables among a large number of candidates in order to predict nonparametrically a scalar response. The first step of MPDP chooses the most predictive variable minimizing (2.1), and updates the subset of candidates by dropping it; the second step selects the most predictive variable among the new subset of candidates with respect to (2.1), and again updates the subset of candidates; and so on. This procedure is repeated until the relative gain in terms of the cross-validation criterion between two consecutive steps does not exceed some threshold; see (2.3). The nonparametric regression estimator suggested for MPDP is the local linear one. The fundamental difference with NOVAS comes at the second step; for any $\ell>1$, NOVAS may drop at step $\ell+1$ some covariates selected at step $\ell$ whereas it is not possible with the sequential feature of MPDP.

In order to achieve this comparison study, a family of regression models $$Y_i\,=\,\gamma_{1,2,3}^{\alpha} (X_{i1},X_{i2},X_{i3})\, +\, \varepsilon_i$$ indexed with a scalar $\alpha$ is simulated with
$$
\gamma_{1,2,3}^{\alpha} (X_{i1},X_{i2},X_{i3})\,=\,3\,+\,\alpha\,\left(X_{i1}+X_{i2}+X_{i3}\right)\,+\,(1-\alpha)\left(X_{i1}^2+X_{i2}^2+X_{i3}^2\right),
$$
where the $X_{ij}$'s and the $\varepsilon_i$'s are built according to the same scheme described in Section 4.1. We set the sample size $n=50$, the number of covariates $p=1000$, the noise-to-signal $snr=0.1$ and the threshold $t=0.05$. This family of models allow to consider pure nonlinear situation (i.e. $\alpha=0$) as well as pure linear setting (i.e. $\alpha=1$). We also take into account an intermediate semilinear models by setting $\alpha=0.35$; this value allows us to balance the variability due to the linear and nonlinear parts. Only variables 1, 2, and 3  are active. For each value of $\alpha$, 100 datasets are simulated. This particular simulation scheme tests severely the selective procedures since most of the time, they are not able to detect the exact set of active covariates (see  Table \ref{tab7}). LAR outperforms clearly both MPDP and NOVAS in the linear situation. However, in the pure nonlinear setting, the behavior of MPDP and NOVAS is much better than LAR (which was expected since LAR is not designed for nonlinear relationship) with a significant  advantage for NOVAS.
\begin{table}[h]
\caption{\label{tab7}Number of times, out of 100, that the correct model is selected.}
\centering
\begin{tabular}{cccc}
 & $\alpha=0$ (nonlinear) & $\alpha=0.35$ (semilinear) & $\alpha=1$ (linear)\\ \hline
LAR & 0 & 2 & 50 \\ \hline
MPDP & 28 & 23 & 0\\ \hline
NOVAS & 44 & 51 & 0\\ \hline
\end{tabular}
\end{table}
In fact, most of the time, extra covariates outside the active ones are selected. In order to better assess the selective performance of these methods, Table \ref{tab8} details how many times, out of 100, each active covariate are selected, and this for each value of $\alpha$. Of course, when tabulating all selected models, in addition of active variables 1, 2, and 3, a quite large number of extra covariates are retained three times at most (see column "others" in Table \ref{tab8}).
\begin{table}[h]
\caption{\label{tab8}Number of times, out of 100, that indicated covariates are  selected; the column "others" gives the maximum number of times that a same extra covariate is selected over the 100 runs.}
\centering
\begin{tabular}{llll}
\begin{tabular}{c}
 \\
Covariates \\ \hline\hline
LAR \\ \hline
MPDP \\ \hline
NOVAS \\ \hline
\end{tabular}
&\begin{tabular}{cccc}
\multicolumn{4}{c}{$\alpha=0$ (nonlinear)}\\
1 & 2 & 3 & others\\ \hline\hline
0 & 1 & 0 & 3\\ \hline
48 & 51 & 52 & 2\\ \hline
70 & 69 & 70 & 2\\ \hline
\end{tabular}
& \begin{tabular}{ccccc}
 \multicolumn{4}{c}{$\alpha=0.35$ (semilinear)}\\
  1 & 2 & 3 & others\\ \hline\hline
  38 & 46 & 39 & 3 \\ \hline
  69 & 74 & 72 & 2\\ \hline
  82 & 84 & 89 & 2\\ \hline
\end{tabular}
& \begin{tabular}{ccccc}
 \multicolumn{4}{c}{$\alpha=1$ (linear)}\\
  1 & 2 & 3 & others\\ \hline\hline
  100 & 100 & 100 & 2 \\ \hline
  79 & 76 & 77 & 4\\ \hline
  93 & 90 & 93 & 3\\ \hline
\end{tabular}
\end{tabular}
\end{table}
Firstly, when focusing on the number of times that active covariates are detected, LAR outperforms NOVAS and MPDP in the linear case whereas NOVAS and MPDP works better in the semilinear and nonlinear setting. Secondly, for each value of $\alpha$, NOVAS better recognizes the active covariates than MPDP does. Thirdly, even in the linear setting, the ability of selecting correctly the active covariates for NOVAS is still high.

Table~\ref{tab9} compares the predictive performance of NOVAS with all competing methods. To obtain these results the mean of the cross-validation estimator of average prediction error, defined at (2.1) and (2.2), was computed (over 100 simulated datasets for each value of $\alpha$).  It can be seen from the Table \ref{tab9} that PLS, sPLS and LAR perform similarly (although the predictive performance of PLS in the linear setting is of poor quality). Naturally, in the nonfavourable situation (i.e. nonlinear model), the linear methods fails; PLS, sPLS and LAR perform almost exactly the same as the simple leave-one-out empirical mean of the responses, where for any $i$, $Y_i$ is predicted naively by $(n-1)^{-1}\,\sum_{j\neq i}\,Y_j$.
\begin{table}[h]
\caption{\label{tab9}mean and variance, in parentheses, of cross-validation criterion, out of 100 simulated datasets.}
\centering
\begin{tabular}{llll}
 & $\alpha=0$ (nonlinear) & $\alpha=0.5$ (semilinear) & $\alpha=1$ (linear)\\ \hline
PLS & 0.30 (0.004) & 0.27 (0.004) & 1.07 (0.037)\\ \hline
sPLS & 0.38 (0.023) & 0.25 (0.007) & 0.18 (0.004)\\ \hline
LAR & 0.28 (0.004) & 0.23 (0.003) & 0.21 (0.006)\\ \hline
MPDP & 0.11 (0.001) & 0.07 (0.001) & 0.15 (0.043)\\ \hline
NOVAS & 0.10 (0.0005) & 0.06 (0.0002) & 0.11 (0.004)\\ \hline
\end{tabular}
\end{table}
When comparing NOVAS with MPDP, it seems that both methods have similar predictive behavior with an advantage for NOVAS which induces smaller variances in all cases.

But the superiority that NOVAS enjoys relative to MPDP include an ability to correctly identify the variables on which the regression actually depends with a shorter running time. Indeed, it is easy to see that, for achieving $k$ steps when dealing with a set of $p$ covariates, MPDP needs the estimation of $kp-0.5k(k-1)+1$ regression models whereas NOVAS involves only $kp/2$ ones (i.e. twice less). Here, for this comparative study, MPDP requires on average one step more than NOVAS which implies that the overall MPDP run time is at least two times longer than the NOVAS one. Another difference between MPDP and NOVAS appears in the situation when one has to deal with redundant variables that were correlated with non-redundant ones. To illustrate this aspect, we simulated datasets from model 4 with different sample sizes as in Section \ref{sec:influence-n-p} ($n=50,100,150,200$), noise-to-signal sets to 0.05, with a number of covariates equals to 1000. We replaced the 1000th explanatory variable by a combination of both the first two:  for $i=1,\ldots,n$, $X_{i\,1000}=X_{i\,1}^2|\,X_{i\, 2}|^{1/3}$. This 1000th variable contains redundant information which can mask the main role playing by variables 1 and 2 in the simulated regression model. Table \ref{tab10} details the selected variables, over 100 runs for each sample size.
{\small
\begin{table}[h]
\caption{\label{tab10}Number of times, out of 100, that the indicated subsets were selected; ${\cal J}_{no\,intruder}$ is $\{1,3,1000\}$ either $\{2,3,1000\}$ or $\{3,1000\}$ and ${\cal J}_{intruder}$ represents any subset containing intruder(s) (i.e. $j$ with $j\notin\{1,2,3, 1000\}$).}\centering
\begin{tabular}{ccccccccc}
 & \multicolumn{2}{c}{$\{1,2,3\}$} &  \multicolumn{2}{c}{$\{1,2,3,1000\}$} & \multicolumn{2}{c}{${\cal J}_{no\,intruder}$} & \multicolumn{2}{c}{${\cal J}_{intruder}$}\\ \hline
n & MPDP & NOVAS & MPDP & NOVAS & MPDP & NOVAS & MPDP & NOVAS\\ \hline
50 & 1 & 1 & 0 & 0 & 6 & 19 & 93 & 80\\ \hline
100 & 7  & 38  & 2  & 1  & 17  & 33  & 74  & 28\\ \hline
150 & 2  & 79  & 18  & 2  & 19  & 15  & 71  & 4\\ \hline
200 & 0  & 96  & 43  & 4  & 23  & 0  & 34  & 0\\ \hline
\end{tabular}
\end{table}
}
Note that the ability of MPDP to identify variables 1, 2, and 3, but most of the time combined with variable 1000, increases with $n$; for instance, $\{1,2,3,1000\}$ is selected 43 times, out of 100, when $n=200$. This artificially redundant 1000th covariate acts as a ``trap'' for MPDP, which looks for the most predictive variable at each step. Moreover, this mechanism leads systematically to selecting at the first step, variable 3, and at the second step, variables 1000, for the largest sample size. Consequently, MPDP selects rarely only variables 1, 2 and 3 in any case and never for $n$ large enough whereas the performance of NOVAS increases significantly with $n$.

Another weakness of MPDP is its propensity to retain, essentially arbitrarily, extra covariates which have no connection with the variables involved in the model; even if this trend behaves less important when $n$ increases, this still happened 34 times out of 100 for the largest sample size. The algorithm NOVAS is much less sensitive to this trap, because it allows us to select quite new models built from submodels which are not necessarily the most predictive.

\section{THEORETICAL PROPERTIES}

\noindent{\sl 5.1.  Main result.}
In Theorem~1, below, we show that, with probability converging to~1 as sample size increases, the algorithm in Section~2.3 correctly determines a small, fixed number of variables on which the function $g(\cdot)=E(Y_i\,|\, X_i=\cdot)$ depends, even if $p$ diverges to infinity much faster than~$n$.  Moreover, the estimator ${\hat g}$ based on these selected variables approximates $g$ with an error that, to first order, equals the error which would arise if we were told in advance the correct variables.  In this sense, ${\hat g}$ achieves oracle performance.

We take ${\hat\ga}_{j_1,\ldots,j_\ell}$, in (2.1), to be a conventional local linear estimator in a regression on $\ell$ variables,~i.e.
$$
{\hat\ga}_{j_1,\ldots,j_\ell}(x)={\bar Y}(x)+\{{\bar X}(x)-x\}^{{\rm T}}\,{\widehat\Sigma}(x)^{-1}\,T(x)\,,\eqno(5.1)
$$
where
$$
\begin{array}{l}
\displaystyle{\bar X}(x) = {\sum_i\, K\{(x-X_i)/h\}\,X_i\over\sum_i\, K\{(x-X_i)/h\}}\;,\quad
{\bar Y}(x)={\sum_i\, K\{(x-X_i)/h\}\,Y_i\over\sum_i\, K\{(x-X_i)/h\}}\;,\\
\:\displaystyle{\widehat\Sigma}(x) ={\sum_i\,\{X_i-{\bar X}(s)\}\,\{X_i-{\bar X}(s)\}^{{\rm T}}\,K\{(x-X_i)/h\}\,X_i\over\sum_i\, K\{(x-X_i)/h\}}\;,
\end{array}
$$
$K(u_1,\ldots,u_\ell)=K_1(u_1)\ldots K_1(u_\ell)$, $K_1$ is a univariate, uniformly bounded, compactly supported, symmetric probability density, and $h$ is a bandwidth.  For simplicity we use the same bandwidth for each component, although of course we could be more ambitious.

Our assumptions, (5.4), (5.5) and (5.6) are stated and discussed in Sections~5.2--5.4.  The theorem is proved in Appendix~A.

\bigskip

\noindent{\bf Theorem 1.} {\em If $(5.4)$, $(5.5)$ and $(5.6)$ hold then, with probability converging to~1 as $n\ra\infty$, the algorithm correctly concludes that $g(X_i)=E(Y_i\,|\, X_i)$ is a function of the first $r$ components of $X_i$ alone, and in particular the algorithm terminates at Step~$r$. }

\bigskip

It is straightforward to prove from the theorem that, if the assumptions there hold, then the regression estimator based on the components to which the algorithm leads has, to first order, the same asymptotic properties as an oracle procedure based on being told in advanced that $E(Y_i\,|\, X_i)$ is a function of the first $r$ components of $X_i$ alone.  In particular, the asymptotic bias and variance of estimators of $g$ that are founded on the conclusion of the algorithm are first-order equivalent to their counterparts for an oracle estimator.

\noindent{\sl 5.2.  Assumptions $(5.4)$ and $(5.5)$.}
These are the main conditions for the theorem.  To state (5.4), let $f$ denote the $p$-variate density of $X$, and, given $j_1,\ldots,j_\ell$, let $\phi_{j_1,\ldots,j_\ell}(x_1,\allowbreak\ldots,\allowbreak x_p)$ be the $p$-variate density proportional to $f(x_1,\ldots,x_p)\,w_\ell(x_{j_1},\allowbreak\ldots,x_{j_\ell})$, where $w_\ell$ is as in~(2.1).  Define $\psi_{j_1,\ldots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})$ to be the integral of $\phi_{j_1,\ldots,j_\ell}(x_1,\ldots,x_p)$ over $x_i$ for each $i\notin\{j_1,\ldots,j_\ell\}$, and let $\gamma_{j_1,\ldots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})$ be the value that $E\{g(X_i)\,|\, X_{ij_1}\allowbreak=x_{j_1},\ldots,X_{ij_\ell}=x_{j_\ell}\}$ would take if $X$ had density $\phi_{j_1,\ldots,j_\ell}$ rather than~$f$:
$$
\gamma_{j_1,\ldots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})
={\int g(x_1,\ldots,x_r)\,\phi_{j_1,\ldots,j_\ell}(x_1,\ldots,x_p)\,dx''\over
\psi_{j_1,\ldots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})}\;,\eqno(5.2)
$$
where $x''$ is the $(p-\ell)$-vector that remains after $x_{j_1},\ldots,x_{j_\ell}$ have been removed from $(x_1,\ldots,x_p)$.  Define

\begin{tabular}{cr}
\begin{minipage}{5in}
\begin{eqnarray*}
\qquad u_\ell(j_1,\ldots,j_\ell)
&=&\int\{g(x_1,\ldots,x_r)-\gamma_{j_1,\ldots,j_\ell}(x_{j_1},\ldots,x_{j_\ell})\}^2\\
& & \qquad\qquad\qquad\quad\,\times\;
\phi_{j_1,\ldots,j_\ell}(x_1,\ldots,x_p)\,dx_1\ldots dx_p\,,\qquad\;\;(5.3)\\
u_0&=&E\{g(X)-Eg(X)\}^2\,.
\end{eqnarray*}
\end{minipage}
\end{tabular}

We assume that, for a subset ${\cal S}_\ell$ of ${\rm I\!R}^\ell$ that we take to be a finite union of nondegenerate compact spheres,\\

\begin{tabular}{cc}
\begin{minipage}{5in} (a)~Among all $\ell$-vectors $(j_1,\ldots,j_\ell)$ satisfying $1\leq j_1<\ldots<j_\ell\leq p$ and $1\leq\ell\leq r$, the choice $(1,\ldots,r)$ uniquely minimises $u_\ell(j_1,\ldots,j_\ell)$, in the sense that the minimum over all choices exceeds $u_r(1,\ldots,r)$ by at least a fixed constant~$B_3>0$, uniformly in~$n$; (b)~for some $\eta>0$, and for $1\leq\ell\leq r$, the number of distinct $\ell$-vectors $j_1,\ldots,j_\ell$, with $1\leq j_1<\ldots<j_\ell\leq p$, for which $u_\ell(j_1,\ldots,j_\ell)>n^{\eta-\{4/(\ell+4)\}}$, is of strictly smaller order than $\sqrt{q}$, and, for $1\leq\ell\leq r$, this includes all $\ell$-vectors of distinct integers chosen from $1,\ldots,r$; (c)~for each $\ell=1,2,\ldots,r+1$ there exists a constant $C_\ell>1$ such that, for all distinct $j_1,\ldots,j_\ell\in\{1,\ldots,p\}$, the joint density of $f_{j_1,\ldots,j_\ell}$ is bounded below $C_\ell$ and above $C_\ell^{-1}$ on ${\cal S}_\ell$.
\end{minipage} &  (5.4)
\end{tabular}
~\\

Finally we impose basic conditions on the univariate kernel $K_1$, bandwidth~$h$ and weight function $w_\ell$ in (2.1), and on the manner in which the algorithm is terminated.  Recall that ${\cal S}_\ell$ was introduced prior to~(5.4).\\

\begin{tabular}{cc}
\begin{minipage}{5in}(a)~$K_1$ is a symmetric, compactly supported, H\"older continuous probability density; (b)~the bandwidth $h=h(n)$, when used to construct the $\ell$-variate regression estimator ${\hat\ga}_{j_1,\ldots,j_\ell}$ at (5.1), equals a constant multiple of~$n^{-1/(\ell+4)}$; (c)~the support of the weight function $w_\ell$ equals ${\cal S}_\ell$, and $w_\ell$ is bounded and twice differentiable there; (d)~we terminate the algorithm using the rule at (2.3), where $t=t(n)$ satisfies $n^{\eta+\{\ell/(\ell+4)\}}\leq t\leq B_5\,n$, $0<B_5<B_3$, $B_3$ is as in (5.4)(a) and $\eta$ is as in (5.4)(b).
\end{minipage} & \mbox{(5.5)}
\end{tabular}
~\\

\noindent{\sl 5.3.  Discussion of assumptions (5.4) and (5.5).}
An example where (5.4)(a) fails, and our algorithm consequently has difficulty, arises when $g(x)=x_1\ldots x_r$, the first $r$ components of $X$ are independent of one another and distributed symmetrically about zero, $w_\ell(t_1,\ldots,t_\ell)=v(t_1)\ldots v(t_\ell)$ where the nonnegative function $v$ is symmetric, and ${\cal S}_\ell$ is a sphere centered at the origin.  Then the fitted function $\gamma_{j_1,\ldots,j_\ell}$, whenever $1\leq j_1<\ldots<j_\ell\leq r$ and $1\leq\ell\leq r-1$, equals~0, and so approximating $g$ by its expected value, conditional on one or more of the first $r-1$ variables, is ineffective.  In particular, no one variable has a visible advantage over any other, and so there is no clear opportunity for choosing the correct variables.  However, this difficulty evaporates if we take the functions $w_1,\ldots,w_r$ to be sufficiently asymmetric.  This example points to the potential influence of $w_\ell$ in (2.1); for example, it can be used to counteract the  negative effects that symmetry
has on the algorithm.

Property (5.4)(a) implies that the choice $\ell=r$ and $j_k=k$ for $1\leq k\leq r$ uniquely minimises asymptotic mean square prediction error, but by itself (5.4)(a) does not ensure that the algorithm in Section~2.3 takes us to that particular combination of variables.  However, the latter property is guaranteed by (5.4)(b), which implies that, with high probability, the singletons $(j)$, for $1\leq j\leq r$; the doublets $(j_1,j_2)$, for $1\leq j_1<j_2\leq r$; and so on up to the $r$-tuple $(1,\ldots,r)$; are, with probability converging to~1, present among the vectors of indices treated in Steps~$1,2,\ldots,r$, respectively, in the algorithm.  Additionally, property (5.6)(d) in section~5.3, which tells us that $Y$ equals a function of the first $r$ components of $X$ alone, plus an independent error, implies that passing from these $r$ components to $r+1$ components produces, with probability converging to~1, at most a negligibly small decrease in prediction error.  In consequence, the rule (2.3) for terminating the algorithm will, with probability converging to~1, lead to a halt immediately after we have concluded, in Step~$r$, that the $r$-vector $(1,\ldots,r)$ is appropriate.  Assumption (5.5)(d), below, also helps in this regard.

More generally, the implication from (5.6)(d) and (5.4)(a) that the choice of variable indices $(j_1,\ldots,j_\ell)=(1,\ldots,r)$ uniquely minimises $u_\ell(j_1,\ldots,j_\ell)$ allows us to investigate an oracle property of conventional type; see the theorem below.  That is, there exists a unique choice of variables that leads to best prediction of~$Y$.  Without (5.6)(d) and (5.4)(a) there could exist many different choices that produced the same asymptotic minimum mean squared prediction error.  For example, without the uniqueness part of (5.4)(a) there could exist components of the $p$-vector $X$ that were simply copies of the first $r$ components but were positioned quite differently in that vector.  On the other hand, if we were not interested in establishing such a result then we could relax (5.4) and~(5.6).

Assumption (5.4)(b) guarantees that, although the number of variables that can be used effectively to at least partially explain $Y$ may diverge with increasing $n$, the number is not so large that extraneous variables fatally confuse the algorithm given in Section~2.3, resulting in the algorithm not correctly identifying the variable indices $(j_1,\ldots,j_\ell)=(1,\ldots,r)$ that best predict a future value of~$Y$.

Condition (5.4)(c) asks merely that the features have the sorts of joint distributions that enable reasonable nonparametric estimation of conditional means such as $E\{g(X_i)\,|\, X_{ij_1},\allowbreak\ldots,X_{ij_\ell}\}$.  To appreciate the reason for the bandwidth choices made in (5.5)(b) we note that, when computing a point estimator ${\hat\ga}_{j_1,\dots,j_\ell}$ of $\gamma_{j_1,\dots,j_\ell}$, the bias is of order $h^2$ (since we assumed, in (5.4)(b) and (5.4)(e), that $f_{j_1,\dots,j_\ell}$ and $g$ have two bounded derivatives), and the error about the mean is of size $(nh^\ell)^{-1/2}$; here we used (5.4)(c).  Therefore the optimal bandwidth for point estimation of $\gamma_{j_1,\dots,j_\ell}$ is of size $n^{-1/(\ell+4)}$, and that is the size assumed in~(5.5)(b).  The resulting estimator of $u_\ell$, $n^{-1}\,S_\ell(j_1,\dots,j_\ell)$, is in error by $O_p\{(nh^\ell)^{-1/2}+h^2\}$.  Actually the term $(nh^\ell)^{-1/2}$ here can be replaced by a quantity of smaller order, and the overall accuracy improved by using a smaller bandwidth, but in practice it will often be the case that the bandwidth is chosen to optimise performance for estimating $\gamma_{j_1,\dots,j_\ell}$ rather than estimating $u_\ell$, and so it is appropriate to proceed as suggested above.

\noindent{\sl 5.4.  Assumption $(5.6)$.}
Condition (5.6) is standard, except perhaps for the assertion in (5.6)(d) that $g(x_1,\ldots,x_p)$ depends only on the first $r$ components $x_1,\ldots,x_r$.  However, since our algorithm is invariant under reorderings of vector components then this assumption is made without loss of generality.  It allows us to take $g$ to not depend on~$n$.\\

\begin{tabular}{cc}
\begin{minipage}{5in}
(a)~$p=p(n)$ is a function of $n$, diverging at a rate no faster than $n^{B_1}$, for some $B_1>0$, as $n$ increases; (b)~the data pairs $(X_i,Y_i)$, for $1\leq i\leq n$, are independent and identically distributed, with a common distribution that can depend on~$n$; (c)~for all choices of $j_1<\ldots<j_\ell$ from $1,\ldots,p$, each subvector $(X_{ij_1},\ldots,X_{ij_\ell})$ of $X_i$ has a well-defined probability density $f_{j_1,\ldots,j_\ell}$ (which may depend on $n$), and, for each fixed $\ell$, all second derivatives of $f_{j_1,\ldots,j_\ell}$ are bounded uniformly in distinct choices of $j_1,\ldots,j_\ell$ from $1,\ldots,p$; (d)~$Y_i=g(X_{i1},\ldots,X_{ir})+\sigma(X_i)\,\epsilon_i$, where the fixed function $g$ is uniformly bounded and has two uniformly bounded derivatives, the function $\sigma$ (which may depend on $n$) is uniformly bounded, and, conditional on $X_i$, the errors $\epsilon_i$ have a distribution depending on neither $X_i$ nor $n$, with zero mean and satisfying $E|\epsilon_i|^{
 B_2}<\infty$ for a sufficiently large constant $B_2>2$.
\end{minipage}
 & (5.6)
\end{tabular}

\bigskip\bs\medskip

\centerline{\bf APPENDIX~A: PROOF OF THEOREM}

\noindent To simplify notation we assume throughout that the function $\sigma$, in (5.6)(d), is identically~1.  Let ${\hat\ga}_{j_1,\ldots,j_\ell}$, $\gamma_{j_1,\ldots,j_\ell}$ and $u_\ell$ be as at (5.1), (5.2) and (5.3), respectively, define $S_\ell$ as at (2.1), and let the random variable $\epsilon$ have the common distribution of the errors $\epsilon_i$ in~(5.6)(d).  Take $\eta_1$ to satisfy $0<\eta_1<\eta$, where $\eta$ is as in (5.4)(b).  Then, in view of the assumption of uniform boundedness of second derivatives in (5.6)(c) and (5.6)(d), and the assumption about the support of the density $f_{j_1,\ldots,j_\ell}$ in~(5.4)(c),
$$
n^{-1}\,S_\ell(j_1,\ldots,j_\ell)=u_\ell(j_1,\ldots,j_\ell)+E\big(\epsilon^2\big)
+O_p\big(n^{\eta_1-\{4/(\ell+4)\}}\big)\,,\eqno({\rm A}.1)
$$
uniformly in $1\leq j_1,\ldots,j_\ell\leq p$ and $1\leq\ell\leq r+1$.  To prove ({\rm A}.1) we need the constant $B_2$ in (5.6)(d) to be chosen sufficiently large, depending on $B_1$ in (5.6)(a) and $\eta_1$ in~({\rm A}.1).  The proof uses Markov's inequality to bound the probability that $|n^{-1}\,S_\ell(j_1,\ldots,j_\ell)-\{u_\ell(j_1,\ldots,j_\ell)+E(\epsilon^2)\}|$ exceeds $n^{\eta_2-\{4/(\ell+4)\}}$, and observes that, since $p\leq n^{B_1}$ (see (5.6)(a)), then, for $1\leq\ell\leq r+1$, the number of vectors $(j_1,\ldots,j_\ell)$ being considered is no larger than $O(n^{(r+1)\,B_1}$).

In Step~1 of the algorithm we take $\ell=1$ and rank values of $S_1(j)$ in order of size.  It follows from (5.4)(b) and ({\rm A}.1) that, with probability converging to~1 as $n\ra\infty$, all the indices $j$ for which $u_1(j)\geq n^{\eta-(1/5)}$ are listed among the $\sqrt{q}$ indices for which $S_1(j)$ achieves its $\sqrt{q}$ highest values, and that this includes all the indices $1,\ldots,r$.  Similarly, in Step~2 of the algorithm we conclude with a list of ranked pairs of indices, containing all pairs chosen from among $1,\ldots,r$; and so on, until the $r$th step, when the list of selected $r$-vectors $(j_1,\ldots,j_r)$ includes $1,\ldots,r$.  It now follows from (5.4)(a) that, with probability converging to~1 as $n\ra\infty$, the algorithm will give $(1,\ldots,r)$ the highest rank in Step~$r$, and, from (5.4)(a) and ({\rm A}.1), that with probability converging to~1 as $n\ra\infty$ the inequality in (2.3) holds for the first time when $\ell=r$.  Therefore, with probability converging to~1 Step~$r$
  is the last step, and the $r$-tuple that is ranked most highly there, i.e.~$(1,\ldots,r)$, is the vector of component indices with which the algorithm concludes.

\bigskip

\centerline{\bf ACKNOWLEDGEMENT}

\noindent The simulation study of this work was granted access to the HPC resources of the scientific grouping CALMIP under the allocation 2013-P1309. This grouping aims to promote the use of the new technologies in scientific computations in the researcher community of Toulouse and the french province of Midi-Pyr\'en\'ees.

\bigskip

\centerline{\bf REFERENCES}

\noindent B\"uhlmann, P., van de Geer, S. (2011). {\em Statistics for High-Dimensional Data: Methods, Theory and Applications}. Springer.

\noindent B\"uhlmann, P., Meier, L. (2008). Discussion of ``One-step sparse estimates in nonconcave penalized likelihood models'' (authors H. Zou and R. Li). {\em Ann. Statist.}, {\bf 36}, 1534--1541.

\noindent Bushel, P., Wolfinger, R. D., Gibson, G. (2007). Simultaneous clustering of gene expression data with clinical chemistry and pathological evaluations reveals phenotypic prototypes. {\em BMC Systems Biology} {\bf 1}(15). doi:10.1186/1752-0509-1-15.

\noindent Cand\`es, E., Tao, T. (2007). The Dantzig selector: statistical estimation when $p$ is much larger than $n$. {\em Ann. Statist.}, {\bf 35}, 2313--2351.

\noindent Dejean, S., Gonzalez, I., Le Cao, K.-A., Monget, P., Coquery, J. (2011). mixOmics: Omics Data Integration Project. R package version 3.0.
  http://CRAN.R-project.org/ package=mixOmics.

\noindent Efron, B., Hastie, T., Johnstone, I., Tibshirani, R. (2004). Least angle regression. {\em Ann. Statist.}, {\bf 32}, 407--499.

\noindent Fan, J., Gijbels, I, (1996). {\em Local Polynomial Modeling and its Applications}. Chapman and Hall, London.

\noindent Fan, J., Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties. {\em J. Am. Statist. Ass.}, {\bf 96}, 1348--1360.

\noindent Fan, J., Lv, J. (2010). A selective overview of variable selection in high dimensional feature space (invited review article). {\em Statistica Sinica}, {\bf 20}, 101--148.

\noindent Ferraty, F., Vieu, P. (2002). The functional nonparametric model and application to spectrometric data. {\em Computational Statistics}, {\bf 17}, 545--564.

\noindent Ferraty, F., Hall, P., Vieu, P. (2010). Most-predictive design points for functional data predictors. {\em Biometrika}, {\bf 97}, 807--824.

\noindent Friedman, J., Hastie, T., H\"ofling, H. and Tibshirani, R. (2007). Pathwise coordinate optimization. {\em Ann. Appl. Statist.}, {\bf 1}, 302--332.

\noindent Fu, W. (1998). Penalized regressions: the Bridge versus the lasso. {\em Journal of  Computational and Graphical Statistics}, {\bf 7}, 397--416.

\noindent Geladi, P., Kowalski, B.R. (1986). Partial least squares regression: A Tutorial. {\em Analytica Chimica Acta}  {\bf 185}, 1--17.

\noindent Hastie, T., Tibshirani, R., Friedman, J. (2009). {\em The Elements of Statistical Learning: Data Mining, Inference, and Prediction} (2nd edition). Springer, New York.

\noindent Huang, J., Horowitz, J. L., Wei, F. (2010). Variable selection via nonparametric additive models. {\em Ann. Statist.}, {\bf 38}, 2282--2313.

\noindent L\^e Cao, K. A., Rossouw D., Robert-Grani\'e, C., Besse, P. (2008). A sparse PLS for variable selection when integrating Omics data. {\em Statist. Appl. Genet. Mol. Biol.} {\bf 7}, article 35.

\noindent Martens, H., Naes, T. (1989). {\em Multivariate calibration}. John Wiley \& Sons Ltd.

\noindent Meier, L., van de Geer, S., B\"uhlmann, P. (2009). High-dimensional additive modeling. {\em Ann. Statist.}, {\bf 37}, 3779--3821.

\noindent Meinshausen, N. (2007). Relaxed lasso. {\em Computational Statistics and Data Analysis}, {\bf 52}, 374--393.

\noindent R Development Core Team (2011). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0, URL http://www.R-project.org/.

\noindent Ravikumar, P., Lafferty, J., Liu, H., Wasserman, L. (2009). Sparse additive models. {\em J. R. Statist. Soc.} B, {\bf 71}, 1009--1030.

\noindent Revolution Analytics (2011). doSNOW: Foreach parallel adaptor for the snow package. R package version 1.0.5. (Available from http://CRAN.R-project.org/package =doSNOW.)

\noindent Tibshirani, R. (1996). Regression analysis and selection via the lasso. {\em J. R. Statist. Soc.} B, {\bf 58}, 267--288.

\noindent Wold, H. (1966). Estimation of principal components and related models by iterative least squares. In: Krishnaiah, P.R. (editors). {\em Multivariate Analysis}. Academic Press, N.Y., 391--420.

\noindent Yuan, M., Lin, Y. (2006). Model selection and estimation in regression with grouped variables. {\em J. R. Statist. Soc.} B, {\bf 68}, 49--67.

\noindent Zou, H. (2006). The adaptive lasso and its oracle properties. {\em J. Am. Statist. Ass.}, {\bf 101}, 1418--1429.

\noindent Zou, H., Hastie, T. (2005). Regularization and variable selection via the Elastic Net. {\em J. R. Statist. Soc.} B, {\bf 67}, 301--320.

\end{document}

redpajama_set_name: RedPajamaArXiv


I know more Wholesale NFL Jerseys Supply every day. posted 14 points , seven rebounds and three assists 32 minutes during Monday's 123 loss to the Cavaliers. Paxton Lynch appears to be a first round bust and Chad has not shown much either. He also managed to pull down seven rebounds . He also added 42 minutes penalties. But be careful. The inability of the running game to take advantage of the soft zone schemes is allowing defensive coaches to remain Cover 2 looks to take away big plays and misdirection calls that work better against coverages.
Four plays later, the Broncos scored a touchdown to restore and gain momentum. He was taken prisoner times for trying to leave Cuba; it's a very stressful thing. Meyer won national championships with 2006 and Wholesale River Plate Jerseys '08, but his teams also had more than two dozen players get into trouble with the law. The four RBI were his most a game all and matched a career high for the 25-year-old. Quins led 12 at half-time but collapsed after the restart as the visitors came away from the Stoop with two points. Whether it's delivering accurate throws on time or anticipating and defeating the blitz with quick-rhythm passes, quarterbacks must be able to function the midst of chaos.
NEXT Bucks: Host Oklahoma City on Tuesday. They enjoy you coming out and giving your best. , who turns 32 April, cheap jerseys suffered a -ending neck and spinal Cheap Jerseys For Sale injury early Cheap Jerseys Free Shipping October which end his career; either way, his time wholesale nfl jerseys Seattle is probably done. Even the players; they liked Cheap Jerseys Free Shipping him because they were the Circle of Trust. Yeah, they're pretty good.
"I kind of blacked out," a smiling Hagg said.
Utah missed covering the spread by one point despite outgaining Air Force, 440, and actually just scored the go-ahead touchdown with under one minute to play. We 't know what's going to happen to Panarin.
The 18-year old was drafted fourth overall the Cheap Jerseys For Sale latest NHL Entry Draft, and placed straight into the NHL. Cheap Jerseys Paypal But the glass-half-full view is a simple one: More new content, yay! A lot be written about Flacco's contract Cheap Jerseys Free Shipping this offseason, but the end result is preordained. Like Brees, he's coming off yet another stellar . Read more about MLB Weekend Preview. Weaknesses.
28, and he impressed management at training camp that he was on the opening-night roster for the 2015 .
After a sack, Wholesale NFL Jerseys Supply another defensive penalty for pass interference on third down made it first-and-goal on the 10.
Not too after, Smith found Cheap Jerseys Free Shipping himself heading to warmer weather Nashville. It's always been about winning. Fitzgerald is not the only current player to make this prestigious list. Brown, Cheap Memphis Grizzlies Jerseys 24, a former soccer player the USA program from Clinton, ., is late to the party. And the Warriors render all but the most transformative maneuvering moot. Staying strong and opening holes against Cheap Jerseys Paypal those guys assure scouts that he can be a longtime starter. The Red are incredibly old – two guys over 40, and six more over 35 – but whatever they are doing is working. Fast Sign up with Instant Access Click Here Free Play from Doc's Sports.


XMailer running 3.0, you will see the starting window of the program.
If you run XMailer first time on this computer, then you need to read and accept the agreement.
If the server is found a new version of the XMailer, you should press the button "Download the update" and run the new version.
To login - click "Next" and go to the window "The entrance to the XMailer".


text:
Q: C# - Binary Tree Issues To the best of my knowledge my program  should work, however, I'm having difficulties with the ref keyword. We aren't expected to use an Insert() method, yet. However, I'm having a hard time trying to use the traverse methods as every time I get an error, it's regarding the ref either an argument is missing or something else. I know I've probably messed up my Main method, but that's due to experimenting and trying to get it to work. I do have a NodeClass with Get and Setter methods, however, the issue is essentially the ref keyword. What am I missing? I've added string I get an error, I've tried to use buffer I get an error.
BinaryTree Class-
 class BinTree<T> where T : IComparable
    {
        private Node<T> root;

        public BinTree()  //creates an empty tree
        {
            root = null;
        }
        public BinTree(Node<T> node)  //creates a tree with node as the root
        {
            root = node;
        }

        public void InOrder(ref string buffer)
        {
            inOrder(root, ref buffer);
        }

        private void inOrder(Node<T> tree, ref string buffer)
        {
            if (tree != null)
            {
                inOrder(tree.Left, ref buffer);
                buffer += tree.Data.ToString() + ",";
                inOrder(tree.Right, ref buffer);
            }

        }

        public void Preorder(ref string buffer)
        {
            PreOrder(root, ref buffer);
        }

        public void PreOrder(Node<T> tree, ref string buffer)
        {
            if (tree != null)
            {
                buffer += tree.Data.ToString() + ",";
                PreOrder(tree.Left, ref buffer);
                PreOrder(tree.Right, ref buffer);
            }
        }

        public void postOrder( ref string buffer)
        {
            PostOrder(root, ref buffer);
        }

        public void PostOrder(Node<T> tree, ref string buffer)
        {
            if (tree != null)
            {

                PostOrder(tree.Left, ref buffer);
                PostOrder(tree.Right, ref buffer);
                buffer += tree.Data.ToString() + ",";
            }
        }
    }

Program Class-
   class Program
{
    static void Main(string[] args)
    {
        BinTree<int> tree = new BinTree<int>();

        Node<int> root = new Node<int>(6);
        root.Left = new Node<int>(15);
        root.Left.Right = new Node<int>(654);

        tree.InOrder(ref , root.Data);

        System.Console.WriteLine();
        Console.ReadLine();
    }
}

Could someone possibly help me? Thank you.
Apologises in advance if it's something obvious.

A: From the above common chain:

*

*You need to pass the root node into the binTree otherwise it will not be able to do anything in the inOrder methods. (BinTree<int> tree = new BinTree<int>();)

*You need a string to pass into the inOrder method call.  You can use StringBuilder to improve performance and remove reliance on ref
The fiddle contains a copy of the code with adjustments.

redpajama_set_name: RedPajamaStackExchange


text:
Compass - March 2017
What links investment companies with The Beatles?
Do you remember the Beatles releasing Sgt Pepper's Lonely Hearts Club Band? That takes you back to 1967 and since then three investment companies have raised their dividends every year consecutively for fifty years – City of London, Bankers and Alliance Trust. Turn to the next page to find out more about these and the other seventeen dividend hero investment companies which have increased their dividends for at least twenty years or longer.
Time is ticking as the end of the tax year approaches. ISAs are nearly 18 years old so in our article on page five, we've examined the best performing investment company ISAs over 18 years. It's interesting to see that the top performing investment company sector over the last 18 years is Sector Specialist: Biotechnology & Healthcare, up a whopping 1,313%.
Continuing with the end of the tax year theme, we've also looked at Venture Capital Trusts (VCTs) which provide finance and support to small and high risk companies. The Government offers generous tax breaks to compensate investors for the risks involved. To find out more about VCTs, what they invest in and the benefits to the economy please watch the video below where I talk to VCT managers Patrick Reeve, Managing Partner of Albion Ventures and David Hall, Managing Director of YFM Equity Partners.
Patrick Reeve, Managing Partner of Albion Ventures has also written an interesting article on the social value of VCTs. And finally, we reveal the top twenty VCTs and the dividends they have paid over the last ten years.
See you next month.
Annabel Brodie-Smith, Communications Director, AIC
Dividend heroes
The latest list published by the AIC
The Association of Investment Companies (AIC) has released the latest list of dividend heroes – those investment companies that have increased their dividends each year for 20 years or more. To celebrate the achievement of these dividend hero investment companies the AIC has created a new logo.
Three investment companies have reached the impressive milestone of 50 years of consecutive dividend increases. They are City of London Investment Trust, Bankers Investment Trust and Alliance Trust.
Job Curtis, manager, City of London Investment Trust said: "City of London's record of growing its dividend every year for 50 years has been achieved both by investing in good companies and also through the investment trust structure. In the good years for dividends, we add to our revenue reserves which we are then able to use in more difficult periods. Indeed, in 7 of the 25 years during my period as fund manager, we have dipped into revenue reserves to help grow the dividend.
"In our view, the dividend yield from UK equities remains attractive compared with the main alternatives and dividend growth has been augmented by the fall in the value of sterling over the last nine months."
Job Curtis, manager, City of London Investment Trust
"Global growth in dividends is expected to be in the 3-5% range, but for investors in the UK this may be higher if the pound continues to fall against overseas currencies."
– Alex Crooke, Bankers Investment Trust
Alex Crooke, manager, Bankers Investment Trust said: "Bankers has just passed the anniversary of the 50th consecutive year of increasing its annual dividend. The trust last held the dividend flat in the year 1966, following a bumper year of dividends received in 1965 when companies tried to avoid the introduction of capital gains tax for the first time. The record of growth before then goes back all the way to the Second World War.
Alex Crooke, manager, Bankers Investment Trust
"The key is to invest in companies that themselves focus on cash generation and distributing dividends throughout economic cycles. The current outlook for income is more muted than previous years, partly because dividends, after lagging the recovery of corporate earnings post the 2008 crash, have now caught up. Many companies in the US and Europe are now paying out a relatively high percentage of their earnings as dividends and therefore fund managers need to carefully focus on those industries where earnings are rising.
"Telecommunications looks a place to avoid as both intense competition and regulators are keeping prices low, while potentially investing in 5G and new services could be a drain on cash flow for many years ahead. Conversely the technology sector in the US looks well placed, particularly long established companies. There is good underlying earnings growth and also room to pay out a higher percentage of profits to shareholders. Overall global growth in dividends is expected to be in the 3-5% range, but for investors in the UK this may be higher if the pound continues to fall against overseas currencies."
An additional seven investment companies have already announced dividend increases for their 2016 year-end. With Foreign & Colonial Investment Trust reaching 46 years of consecutive dividend increases, Brunner Investment Trust reaching 45 years, JPMorgan Claverhouse Investment Trust 44 years, Witan Investment Trust 42 years, Scottish American Investment Trust 37 years and both Scottish Investment Trust and Temple Bar announcing their 33rd year of consecutive dividend increase. For a full list of dividend heroes, please see the table below.
Annabel Brodie-Smith, Communications Director, AIC said: "It's such an achievement to see three investment companies reach 50 years of consecutive dividend increases. In the current low interest rate environment, with inflation creeping up, the ability to 'smooth' dividends is a unique advantage of the investment company structure. Investment companies can store up to 15% of the income they receive each year and can use these reserves to boost dividends when times get tough in the future.
"To celebrate the success of these investment companies which have increased their dividends year in year out for over 20 years, the AIC has launched a dividend hero logo."
The social value of VCTs
By Patrick Reeve, Albion Ventures
Patrick Reeve, Managing Partner, Albion Ventures
In the empty aftermath of the First World War, the novelist John Buchan tried to find a sense of reason with the words, "the only way that we can hope to repay our debt to the Past, is by ensuring that the Future is in debt to us". There's something about this concept that seems particularly powerful for us in the West at the start of the twenty-first century, after seventy years of extraordinary prosperity, and at a time when the future seems particularly unclear.
This applies as much in my "day job" as anywhere, because your job as a venture capitalist is to watch where the world is changing, and to gauge whether that change is going to result in growth, and above all in value. In recent years, it's become clear to me that for value to be lasting rather than transitory, it needs to have a social resonance and to improve people's lives in a permanent rather than temporary way.
"Your job as a venture capitalist is to watch where the world is changing, and to gauge whether that change is going to result in growth, and above all in value"
– Patrick Reeve
This realisation has spread across the venture capital sector, and not least the £3.5 billion Venture Capital Trust (VCT) part of it. In fact, there is an increasing realisation amongst VCT managers that socially positive investment is good for investors, and a growing number of investee companies are at the forefront of developments in sectors such as the environment, healthcare and education. In all of these, the dynamics driving change have been huge, from the multiple pressures of climate change, the increased health demands of an aging population and the need, both technological and social, to better equip the young to a changing world.
In the environmental sector, VCTs have played a major role in smaller-scale renewable energy infrastructure, contributing to the 25% of UK power that is now derived from renewable sources. Less well known, are contributions towards agriscience, enabling more food to be produced for growing populations in a fast-changing environment. VCT investments in this area include Cawood Scientific, backed by the Northern VCTs, which is the UK's largest independent provider of analytical laboratory testing services for agricultural industries. It specialises in the analysis of animal feed, grain, soil, composts, anaerobic digestate and contaminated land, with the overall aim of driving land improvement and providing the product assurance that is vital for UK food quality.
"There is an increasing realisation amongst VCT managers that socially positive investment is good for investors"
There are a number of areas where VCTs support the education sector, both in the provision of technology and in the actual ownership and management of schools. On the technology side, Firefly Learning, backed by the ProVen VCTs, provides software to 500 schools in 32 countries, enabling 400,000 pupils to improve their educational engagement. Meanwhile, the Radnor House group, backed by us at Albion Ventures, established a new London day school in Twickenham, catering for 11-18 year olds, which now has over 400 pupils. The group also owns and operates a 300 pupil school in Sevenoaks, Kent.
VCTs' involvement in healthcare can be seen in a number of areas, from healthcare IT through to diagnostics. Network Locum, for instance, backed by the ProVen VCTs, helps match locum doctors with available shifts in NHS hospitals and GP practices. Antidote, meanwhile, backed by Octopus Titan VCT, has developed the world's largest machine readable clinical trial database, aimed at matching willing participants with local trials appropriate to their condition; saving lives by speeding up the clinical trial process.
In women's health, Create Health, backed by the Baronsmead VCTs, is a leading innovator in natural and mild IVF techniques and has recently opened two new clinics, in Central London and Birmingham, with two additional satellite clinics in Bristol and Hertfordshire. Dysis Medical, meanwhile, which is backed by us at the Albion VCTs, has developed a new system for screening cervical cancer; its products have now processed more than 80,000 examinations, enabling a significant number of tumours to be treated which would otherwise have been left undiagnosed.
"In an ever more cramped (and sometimes sharp-elbowed) world, any activity that is not socially positive, can only be short term"
In an ever more cramped (and sometimes sharp-elbowed) world, any activity that is not socially positive, can only be short term. And the potential for change is huge; as the great Groucho Marx once commented, "just think what God could have done – if only he'd had the money…"
18 years of ISAs
What was the best investment company sector?
We've all had those moments when we've wished we could turn back time, and Cher famously sang a song about it.
With ISAs now nearly 18 years old, the Association of Investment Companies (AIC) has published a list of the top performing investment company sectors over this period.
The top performing investment company sector over the last 18 years is Sector Specialist: Biotechnology & Healthcare, up a whopping 1,313% - clearly not a bad place to be over the long-term, to date at least. The Asia Pacific sectors and Global Emerging Markets also feature strongly, as do smaller companies across a range of regions.
"The top performing investment company sector over the last 18 years is Sector Specialist: Biotechnology & Healthcare, up 1,313%"
Annabel Brodie-Smith, Communications Director, Association of Investment Companies (AIC) said: "Everyone has different ideas about what constitutes 'long-term' – in fact our own investor confidence research this year found that 8% of active investors consider 3 to 5 years a 'long-term' investment horizon. Whereas we consider long-term investments to be at least five years and preferably longer.
"There's no doubt that 18 years is a long-term investment and it was Warren Buffet who said that 'successful investing takes time, discipline and patience.' It's clear that investors in some of the top performing investment company sectors have been rewarded for their patience over the long-term. In some sectors investors have needed bags of patience, as demonstrated by the volatility of the Global Emerging Markets sector in recent years, but their investment has paid off over the long term. Of course, there's no telling which sector will be topping the tables in the future so investors need to focus on a diversified portfolio for the long-term."
"There's no telling which sector will be topping the tables in the future so investors need to focus on a diversified portfolio for the long-term"
– Annabel Brodie-Smith, AIC
Asia Pacific and Global Emerging Markets also lead the pack
Hot on the heels of the Sector Specialist: Biotechnology & Healthcare is the eight companies strong Country Specialist: Asia Pacific sector, in second place over 18 years and up 1,280%. This is followed by the Global Emerging Markets sector, which is up 805%, but as the discrete performance data shows, this sector has had a more volatile time over the last 5 years. Also in the top 5 over the period is the Asia Pacific Excluding Japan sector, up 794%. This data demonstrates that despite some greater volatility over the last five years compared to the sector average, long-term patient investors have been rewarded.
Smaller companies have also produced some strong returns and feature heavily amongst the top performing investment company sectors, with European Smaller Companies in 5th place, up 625%, followed by North American Smaller Companies (556%) and UK Smaller Companies (520%). The Private Equity sector has also posted above average returns, up 507%, and the UK All Companies sector up 456%.
Top performing investment company sectors over 18 years - % share price total return
VCT income & growth over a decade
Top 20 performers paid average tax free dividend of 87 pence per share Top 20 VCTs up an average of 141%
Recent research from the Association of Investment Companies (AIC) has demonstrated continued strong appetite for VCTs. In the current low interest rate environment, not to mention the pension rule changes and reduction in the lifetime allowance, it is easy to see why demand is strong.
"The VCT sector as a whole is up 82% by share price total return over the last decade to 31 December 2016"
Earning their stripes
But figures published today by the AIC demonstrate that, more significantly, the VCT sector has now 'earned its stripes' as it has built up an impressive track record. The VCT sector as a whole is up 82% by share price total return over the last decade to 31 December 2016, with the added benefit of tax free dividends and capital gains.
At the same time, the sector has supported fledgling UK businesses and, in 2015 alone, last year's AIC survey showed VCTs provided £225m of funds to 115 SMEs. VCT backed businesses averaged an increase of 60 employees per company since VCT investment. Where investment had been present for over five years the average increase in jobs was 103 per company.
The top 20 performing VCTs on a share price total return basis over the last decade have paid out an average total tax free dividend of 87 pence per share.
Looking at share price total return, the top 20 VCTs are up an average of 141% over the last 10 years. Seventeen out of twenty of the top performing VCTs were in the VCT Generalist sector, with one VCT AIM Quoted, one VCT Specialist: Technology and one VCT Specialist: Environmental completing the twenty.
"The top performing VCT of the last decade, Northern Venture Trust, is up 226%"
The top performing VCT of the last decade, Northern Venture Trust, is up 226% over the last decade and Maven Income and Growth VCT is in second place, up 187% and the Income and Growth VCT (managed by Mobeus Equity Partners) was also up 187%. Next was British Smaller Companies VCT, up 185% over the decade.
Northern Venture Trust, the best performer, has paid out total tax free dividends of 98.50 pence per share over the period. Maven Income and Growth VCT, in second place, has paid out total tax free dividends of 60.10 pence per share over the decade and the third best performing, Income and Growth VCT (managed by Mobeus Equity Partners) paid out total tax free dividends of 99.75 pence per share. Next was British Smaller Companies VCT which paid out total tax free dividends of 83.25 pence per share over the decade. See table at end of release for a list of the top 20 performing VCTs, with dividend information.
Commenting on the data, Ben Yearsley, Co-Founder and Investment Director, Wealth Club, said: "Tax free dividends remain the most attractive feature of VCTs and the last decade has shown both excellent total dividends and more importantly consistency in those dividend payments. With the rule changes of 2015 now starting to be felt, in my view investors may have to get used to a slightly different picture going forwards. The emphasis on earlier stage, higher growth potential companies should lead to equal if not higher returns over long term.
"However whilst the last decade has been characterised by consistency I think the next decade will see the return profile being bumpier as dividends will have to be funded more from sales of businesses rather than maturing loan stock for example. Overall the VCT sector is in excellent shape, and I'm still a long-term investor with the best managers."
The AIC has collated views from a number of managers from the top 20 VCTs
Bill Nixon, Managing Partner at Maven, said: "There continues to be a healthy investor appetite for established private equity focused VCTs, which are now firmly positioned as a mainstream investment product. With persistent low interest rates for savers, and continued pressure on the scope for pension contributions, VCTs offer an attractive, tax-efficient alternative for investment and retirement planning. The VCT sector has consolidated in recent years into a number of highly capable management groups who have established a reliable and long-term track record of growth in shareholder returns, including an attractive level of tax free dividends. Investors in VCTs are also helping directly to create quality jobs and economic value and are supporting the development of some of the brightest emerging companies in the UK at an important time for British industry as we prepare to leave the EU.
"Notwithstanding the recent changes in the VCT rules, which have limited the types of company and transaction in which a VCT can invest, the sector is adapting to this new environment and we expect to see a significant pick up in investment activity in 2017. The VCT industry continues to offer a unique bridge between SME funding and retail investors, who can tax-efficiently gain access to an asset class and portfolio developed by a specialist manager, which ordinarily would not be available to them. And we should recognise and celebrate VCTs for what they are – the most important and reliable source of equity capital for small growing companies in the UK, and a product which has surpassed all expectations since it was first conceived in 1995"
David Hall, Managing Director, YFM Equity Partners, said: "The financial performance across a range of the trusts demonstrates that investing in the UK's small businesses delivers strong growth in those businesses from which investors directly benefit by way of dividend, but also through the positive economic impact of employment growth and increased tax take from those businesses.
"VCTs have been a vital part of scale up capital to Britain's smaller companies and this year will again be raising over £400 million and investment over the years topping £3 billion. Now VCTs have the key to the door, plenty of experience and considerable cash to invest they have emerged as a significant force in supporting the growth of UK businesses."
Mark Wignall, manager of the Mobeus VCTs, said: "It's pleasing that Mobeus feature strongly in the top 20. The Mobeus VCT objective has always been to build shareholder value and pay it out in tax free dividends; that's why each has Income & Growth in the name and each has done exactly what it says on the tin. And there continues to be no shortage of ambitious, young companies that need VCT backing to grow. Over the past 12 months, Mobeus has completed six exciting new investments in great companies that are expanding fast by innovating or disrupting markets and our pipeline of further investment opportunities is strong."
Tim Levett Chairman, NVM (Fund Manager, Northern VCTs) said: "The performance of the leading VCTs over the last ten years not only reflects on the depth of talent that has been built up in VCT teams but also the resilience of the UK SME sector. Post the Brexit referendum the economy has continued to grow and we are confident of seeing a strong flow of exciting companies to back."
Annabel Brodie-Smith Communications Director, Association of Investment Companies (AIC) said: "As the VCT sector has matured, so too have returns, with good long-term performance together with a strong tax-free income. It is telling that, during the financial crisis, 19 out of the top 20 performing VCTs were still able to pay a dividend. Recently the pension changes and the reduction in the lifetime allowance has boosted investor demand, with fund raising higher to the end of January 2017 than in the previous year.
"The performance figures do not take into account the tax benefits VCT investors receive, to offset some of the higher risk which comes with supporting small and growing UK companies at the coalface of the economy. These figures demonstrate that as well as being higher risk, VCTs can also be high reward however, the old adage 'don't let the tax tail wag the investment dog' is as true as ever. If you have any doubts about VCTs, it's well worth consulting an independent financial adviser."
For performance and dividend data of top 20 performing VCTs over ten years see next page
Top 20 performing VCTs of decade: % share price total return and dividends (share price pence)

redpajama_set_name: RedPajamaCommonCrawl


Chattanooga Engineers Club - New Website goes LIVE !!
New Website goes LIVE !!
We apologize to those who have stopped receiving the Engineers Club newsletter over the past year as we have struggled with a web site and mailing list change. This site represents a new start with professional support and enhanced capabilities.
Our vision is that Engineers Club Events calendar will become your go-to place to find engineering and technical events all over the region. We value your feedback (and patience!) as we work toward this end.