"Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes."

"Here we show, with a common, general, and simpler analysis, that weight sharing in fact achieves much more than what it was designed for. We use it to simultaneously prove new shifting regret bounds for online convex optimization on the simplex in terms of the total variation distance as well as new bounds for the related setting of adaptive regret. Finally, we exhibit the first logarithmic shifting bounds for exp-concave loss functions on the simplex."

ITCS 2011 best paper

"We show that these two properties are fundamentally at odds with each other: a sparse algorithm cannot be stable and vice versa."

Cute! "In this paper, we generalise the famous algorithm for swapping the contents of two variables without using a buffer. We introduce a novel combinatorial framework for procedural programming languages, where programs are only allowed to update one variable at a time. We first consider programs which do not have any additional memory. We prove that any function of all the variables can be computed this way in a number of updates which grows linearly with the number of variables. Similarly, any linear function can be computed using a linear number of linear instructions. We then derive the exact number of instructions required to compute any manipulation of variables. Second, we show that allowing programs to use additional memory is also incorporated in our framework. We quantify the gains obtained by using additional memory. This leads to shorter programs and allows to use only binary instructions, which is not sufficient in general when no memory is used."

"Given a subset K of the unit Euclidean sphere, we estimate the minimal number m = m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,y in K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m = O(w(K)^2) where w(K) is the Gaussian mean width of K."

"We introduce two new concepts designed for the study of empirical processes. First, we introduce a new Orlicz norm which we call the Bernstein-Orlicz norm. This new norm interpolates sub-Gaussian and sub-exponential tail behavior. In particular, we show how this norm can be used to simplify the derivation of deviation inequalities for suprema of collections of random variables. Secondly, we introduce chaining and generic chaining along a tree. These simplify the well-known concepts of chaining and generic chaining. The supremum of the empirical process is then studied as a special case. We show that chaining along a tree can be done using entropy with bracketing. Finally, we establish a deviation inequality for the empirical process for the unbounded case."

Slightly tighter analysis of Moitra & O'Donnell. More importantly: bounds higher moments.

"We present a variant of Azuma's concentration inequality for martingales, in which the standard boundedness requirement is replaced by the milder requirement of a subgaussian tail."

To attain O(1/T) convergence for non-smooth problems, SGD just needs a little tweak: an averaging window.

To deduce anticoncentration properties about X, use their "inner thickening" algorithm to produce Y, and deduce anticoncentration properties about that instead.

Online equivalent to sparsity oracle inequalities.

Lots of typos right now.

"Most online algorithms used in machine learning today are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, which combines "random playout" and randomized rounding of loss subgradients. As an application of our approach, we provide the first computationally efficient online algorithm for collaborative filtering with norm-constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning."

Finally!

Variational regret bounds.

"We derive exponential tail inequalities for sums of random matrices with no dependence on the explicit matrix dimensions. These are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the dimension is large or infinite. Some applications to principal component analysis and approximate matrix multiplication are given to illustrate the utility of the new bounds. "

Much shorter proof based on interplay between concentration and anticoncentration.

"We analyze and evaluate an online gradient descent algorithm with adaptive per-coordinate adjustment of learning rates. Our algorithm can be thought of as an online version of batch gradient descent with a diagonal preconditioner. This approach leads to regret bounds that are stronger than those of standard online gradient descent for general online convex optimization problems."

"In an incoherent dictionary, most signals that admit a sparse representation admit a unique sparse representation. In other words, there is no way to express the signal without using strictly more atoms. This work demonstrates that sparse signals typically enjoy a higher privilege: each nonoptimal representation of the signal requires far more atoms than the sparsest representation—unless it contains many of the same atoms as the sparsest representation."

"We derive an upper bound for the mean of the supremum of the empirical process indexed by a class of functions that are known to have variance bounded by a small constant $\delta$. The bound is expressed in the uniform entropy integral of the class at $\delta$."

"In this paper we develop an alternative approach to lower bounding the upper tail probability [P(supt∈T Z(t) > u)]. The ingredients are an initial conditioning step, followed by a comparison (in the sense of the method of comparison) with a “model” Gaussian process that can be explicitly analysed. The resulting bounds are clean and can be non-trivial for moderately sized u, which is very important in our two applications."

"The important work in this area is by Carbery and Wright, who gave a tight bound for anti-concentration of polynomials in normal variables. However, the proof of their result is quite complex. We give a weaker anti-concentration result which has an elementary proof, based on some convexity arguments, simple analysis and induction on the degree. Moreover, our proof technique is robust and extends to other distributions."

Workshop paper.

"The concentration of empirical measures is studied for dependent data, whose joint distribution satisfies Poincaré-type or logarithmic Sobolev inequalities. The general concentration results are then applied to spectral empirical distribution functions associated with high-dimensional random matrices."

By Berkeley/TTIC/Penn.

Followup to the "online learnability" paper.

"We define a data dependent permutation complexity for a hypothesis set H, which is similar to a Rademacher complexity or maximum discrepancy. The crucial difference is that it is based on permutation (dependent) sampling. We prove a uniform bound on the generalization error, as well as a concentration result which means that the permutation estimate can be efficiently estimated."

"We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the $\gamma$-adapted-dimension, which is a simple function of the spectrum of a distribution’s covariance matrix, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the $\gamma$-adapted-dimension of the source distribution. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. The bounds hold for a rich family of sub-Gaussian distributions."

How are these better/different from the "Bernoulli conjecture" chapter in _The Generic Chaining_?

"...we isolate and highlight two key properties of a regularized M-estimator—namely, a decomposability property for the regularizer, and a notion of restricted strong convexity that depends on the interaction between the regularizer and the loss function."

"We prove rates of convergence in the statistical sense for kernel-based least squares regression using a conjugate gradient algorithm, where regularization against overfitting is obtained by early stopping. This method is directly related to Kernel Partial Least Squares, a regression method that combines supervised dimensionality reduction with least squares projection. The rates depend on two key quantities: first, on the regularity of the target regression function and second, on the intrinsic dimensionality of the data mapped into the kernel space."

"We establish am excess risk bound of order $H \Rad_n^2 + \sqrt{H L^*}\Rad_n$ for ERM with an H-smooth loss function and a hypothesis class with Rademacher complexity $\Rad_n$, where $L^*$ is the best risk achievable by the hypothesis class. For typical hypothesis classes where $\Rad_n = \sqrt{R/n}$, this translates to a learning rate of order $RH/n$ in the separable ($L^*=0$) case and $RH/n + \sqrt{L^* RH/n}$ more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective."

"... for any sampling problem S, there exists a search problem R such that, if C is any "reasonable" complexity class, then R is in the search version of C if and only if S is in the sampling version."

"This paper provides noncommutative generalizations of the classical bounds associated with the names Azuma, Bennett, Bernstein, Chernoff, Freedman, Hoeffding, and McDiarmid. The matrix inequalities promise the same diversity of application, ease of use, and strength of conclusion that have made the scalar inequalities so valuable."

"We survey a few concentration inequalities for submodular and fractionally subadditive functions of independent random variables, implied by the entropy method for self-bounding functions. The power of these concentration bounds is that they are dimension-free, in particular implying standard deviation O(\sqrt{\E[f]}) rather than O(\sqrt{n}) which can be obtained for any 1-Lipschitz function of n variables."

Of the Hoeffding/Chernoff variety. Constructive in the sense that "if the sum of the given random variables is not concentrated around the expectation, then we can efficiently find (with high probability) a subset of the random variables that are statistically dependent."

Check if this is actually new.

"Provides the most complete analysis of the ways markets aggregate information [and] bridges the gap between the rational expectations and herding literatures."

A decent looking greedy criterion.

The adversarial strategies used by forecasters to manipulate tests are computationally intractable.

Bound the risk of your hypothesis without strong mixing, β-mixing, or iid requirements.

"Penalization procedures often suffer from their dependence on multiplying factors, whose optimal values are either unknown or hard to estimate from data. We propose a completely data-driven calibration algorithm for these parameters in the least-squares regression framework, without assuming a particular shape for the penalty. Our algorithm relies on the concept of minimal penalty, recently introduced by Birge and Massart (2007) in the context of penalized least squares for Gaussian homoscedastic regression. On the positive side, the minimal penalty can be evaluated from the data themselves, leading to a data-driven estimation of an optimal penalty which can be used in practice;
on the negative side, their approach heavily relies on the homoscedastic Gaussian nature of their stochastic framework."

Topics include: flattening lemma, isoperimetric inequalities, the martingale method, large deviations, Lipschitz functions...

"We study the label complexity of pool-based active learning in the PAC model with noise. Taking inspiration from extant literature on Exact learning with membership queries, we derive upper and lower bounds on the label complexity in terms of generalizations of extended teaching dimension. Among the contributions of this work is the first nontrivial general upper bound on label complexity in the presence of persistent classification noise."

"We study the rates of convergence in generalization error achievable by active learning under various types of label noise. Additionally, we study the more general problem of active learning with a nested hierarchy of hypothesis classes, and propose an algorithm whose error rate provably converges to the best achievable error among classifiers in the hierarchy at a rate adaptive to both the complexity of the optimal classifier and the noise conditions. In particular, we state sufficient conditions for these rates to be dramatically faster than those achievable by passive learning."

Like McDiarmid's inequality? Then you'll love Kontorovich & Ramanan.

Philosophical portions apparently disliked by CRS and Kevin Kelly.