Although the standard formulations of prediction problems involve
fully-observed and noiseless data drawn in an i.i.d. manner, many applications
involve noisy and/or missing data, possibly involving dependence as well. We
study these issues in the context of high-dimensional sparse linear regression,
and propose novel estimators for the cases of noisy, missing, and/or dependent
data.

We consider the hypothesis testing problem of detecting a shift between the
means of two multivariate normal distributions in the high-dimensional setting,
allowing for the data dimension p to exceed the sample size n. Specifically, we
propose a new test statistic for the two-sample test of means that integrates a
random projection with the classical Hotelling T^2 statistic.

We analyze convergence rates of stochastic optimization procedures for
non-smooth convex optimization problems. By combining randomized smoothing
techniques with accelerated gradient methods, we obtain optimal variance-based
convergence rates of stochastic optimization procedures, both in expectation
and with high probability, To the best of our knowledge, these are the first
variance-based rates for non-smooth optimization.

High-dimensional statistical inference deals with models in which the the
number of parameters $p$ is comparable to or larger than the sample size $n$.
Since it is usually impossible to obtain consistent procedures unless $p/n
\rightarrow 0$, a line of recent work has studied models with various types of
low-dimensional structure (e.g., sparse vectors; block-structured matrices;
low-rank matrices; Markov assumptions).

We consider the matrix completion problem under a form of row/column weighted
entrywise sampling, including the case of uniform entrywise sampling as a
special case. We analyze the associated random observation operator, and prove
that with high probability, it satisfies a form of restricted strong convexity
with respect to weighted Frobenius norm. Using this property, we obtain as
corollaries a number of error bounds on matrix completion in the weighted
Frobenius norm under noisy sampling and for both exact and near low-rank
matrices.

Sparse additive models are families of $d$-variate functions that have the
additive decomposition \mbox{$f^* = \sum_{j \in S} f^*_j$,} where $S$ is a
unknown subset of cardinality $s \ll d$. We consider the case where each
component function $f^*_j$ lies in a reproducing kernel Hilbert space, and
analyze a simple kernel-based convex program for estimating the unknown
function $f^*$. Working within a high-dimensional framework that allows both
the dimension $d$ and sparsity $s$ to scale, we derive convergence rates in the
$L^2(\mathbb{P})$ and $L^2(\mathbb{P}_n)$ norms.

Consider the standard linear regression model $\y = \Xmat \betastar + w$,
where $\y \in \real^\numobs$ is an observation vector, $\Xmat \in
\real^{\numobs \times \pdim}$ is a design matrix, $\betastar \in \real^\pdim$
is the unknown regression vector, and $w \sim \mathcal{N}(0, \sigma^2 I)$ is
additive Gaussian noise. This paper studies the minimax rates of convergence
for estimation of $\betastar$ for $\ell_\rpar$-losses and in the
$\ell_2$-prediction loss, assuming that $\betastar$ belongs to an
$\ell_{\qpar}$-ball $\Ballq(\myrad)$ for some $\qpar \in [0,1]$.

Principal component analysis (PCA) is a classical method for dimensionality
reduction based on extracting the dominant eigenvectors of the sample
covariance matrix. However, PCA is well known to behave poorly in the ``large
$p$, small $n$'' setting, in which the problem dimension $p$ is comparable to
or larger than the sample size $n$. This paper studies PCA in this
high-dimensional regime, but under the additional assumption that the maximal
eigenvector is sparse, say, with at most $k$ nonzero components.