We consider solving the $\ell_1$-regularized least-squares ($\ell_1$-LS)
problem in the context of sparse recovery, for applications such as compressed
sensing. The standard proximal gradient method, also known as iterative
soft-thresholding when applied to this problem, has low computational cost per
iteration but a rather slow convergence rate. Nevertheless, when the solution
is sparse, it often exhibits fast linear convergence in the final stage.

We prove an effective upper bound on the number of effective sections of a
nef hermitian line bundle over an arithmetic surface. It is an effective
version of the arithmetic Hilbert--Samuel formula. As a consequence, we obtain
effective lower bounds on the Faltings height and on the self-intersection of
the canonical bundle in terms of the number of singular points on fibers of the
arithmetic surface.

We apply the concept of structured sparsity to improve boosted decision trees
with general loss functions. The existing approach to this problem is
Friedman's gradient boosting procedure using a regression tree base learner.
Although this method has led to many successful industrial applications, it
suffers from several theoretical and practical drawbacks. By employing the idea
of structured greedy search, we are able to design a regularized greedy forest
procedure to address these issues.

Concave regularization methods provide natural procedures for sparse
recovery. However, they are difficult to analyze in the high dimensional
setting. Only recently a few sparse recovery results have been established for
some specific local solutions obtained via specialized numerical procedures.
Still, the fundamental relationship between these solutions such as whether
they are identical or their relationship to the global minimizer of the
underlying nonconvex formulation is unknown.

We address the problem of learning in an online setting where the learner
repeatedly observes features, selects among a set of actions, and receives
reward for the action taken. We provide the first efficient algorithm with an
optimal regret. Our algorithm uses a cost sensitive classification learner as
an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number
of classification rules among which the oracle might choose. This is
exponentially faster than all previous algorithms that achieve optimal regret
in this setting.

Suppose a given observation matrix can be decomposed as the sum of a low-rank
matrix and a sparse matrix (outliers), and the goal is to recover these
individual components from the observed sum. Such additive decompositions have
applications in a variety of numerical problems including system
identification, latent variable graphical modeling, and principal components
analysis. We study conditions under which recovering such a decomposition is
possible via a combination of $\ell_1$ norm and trace norm minimization.