One day in September 2014, in a hamlet in the French Pyrenean foothills, Jean-Claude, a landscape gardener in his late 50s, was surprised to see his neighbour at the gate. He hadn't spoken to the 86-year-old in nearly 15 years after a dispute over a climbing rose that Jean-Claude had wanted to prune. The old man lived in total seclusion, tending to his garden in the djellaba he always wore, writing by night, heeding no one. Now, the long-bearded seeker looked troubled. "Would you do me a favour?" he asked Jean-Claude. "Could you buy me a revolver?" Then, after watching the hermit – who was deaf and nearly blind – totter erratically about his garden, he telephoned the man's children. Even they hadn't spoken to their father in close to 25 years. When they arrived in the village of Lasserre, the recluse repeated his request for a revolver, so he could shoot himself. There was barely room to move in his dilapidated house. The corridors were lined with shelves heaving with flasks of mouldering liquids.

This paper studies the optimality of kernel methods in high-dimensional data clustering. Recent works have studied the large sample performance of kernel clustering in the high-dimensional regime, where Euclidean distance becomes less informative. However, it is unknown whether popular methods, such as kernel k-means, are optimal in this regime. We consider the problem of high-dimensional Gaussian clustering and show that, with the exponential kernel function, the sufficient conditions for partial recovery of clusters using the NP-hard kernel k-means objective matches the known information-theoretic limit up to a factor of $\sqrt{2}$ for large $k$. It also exactly matches the known upper bounds for the non-kernel setting. We also show that a semi-definite relaxation of the kernel k-means procedure matches up to constant factors, the spectral threshold, below which no polynomial-time algorithm is known to succeed. This is the first work that provides such optimality guarantees for the kernel k-means as well as its convex relaxation. Our proofs demonstrate the utility of the less known polynomial concentration results for random variables with exponentially decaying tails in a higher-order analysis of kernel methods.

In this paper we consider the cluster estimation problem under the Stochastic Block Model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. The error bound implies weak recovery in the sparse graph regime with bounded expected degrees, as well as exact recovery in the dense regime. An immediate corollary of our results yields error bounds under the Censored Block Model. Moreover, these error bounds are robust, continuing to hold under heterogeneous edge probabilities and a form of the so-called monotone attack. Significantly, this error rate is achieved by the SDP solution itself without any further pre- or post-processing, and improves upon existing polynomially-decaying error bounds proved using the Grothendieck\textquoteright s inequality. Our analysis has two key ingredients: (i) showing that the graph has a well-behaved spectrum, even in the sparse regime, after discounting an exponentially small number of edges, and (ii) an order-statistics argument that governs the final error rate. Both arguments highlight the implicit regularization effect of the SDP formulation.

Forward regression is a statistical model selection and estimation procedure which inductively selects covariates that add predictive power into a working statistical regression model. Once a model is selected, unknown regression parameters are estimated by least squares. This paper analyzes forward regression in high-dimensional sparse linear models. Probabilistic bounds for prediction error norm and number of selected covariates are proved. The analysis in this paper gives sharp rates and does not require beta-min or irrepresentability conditions.