Learning faster from easy data II

It is well known that most of the common clustering objectives are NP-hard to optimize. In practice, however, clustering is being routinely carried out. One approach for providing theoretical understanding of this seeming discrepancy is to come up with notions of clusterability that distinguish realistically interesting input data from worst-case data sets. The hope is that there will be clustering algorithms that are provably efficient on such “clusterable” instances. This paper addresses the thesis that the computational hardness of clustering tasks goes away for inputs that one really cares about. In other words, that “Clustering is difficult only when it does not matter” (the CDNM thesis for short).

I would like to use the format of a workshop presentation to deviate from the conference paper style of focusing on cutting edge results. Instead, I wish to present a a critical bird’s eye overview of the results published on this issue so far and to call attention to the gap between available and desirable results on this issue. I start by discussing which requirements should be met in order to provide formal support to the the CDNM thesis. I then examine existing results in view of these requirements and list the most significant unsolved research challenges in that direction.

Tysbakov noise condition characterizes the level of noise in labels in a classification setting, leading to faster rates for both passive and active learning when the noise is low. However, the noise level is typically unknown and it is desirable to design adaptive algorithms that are robust to high noise setting while leading to faster rates in low noise settings. In passive learning, this is straightforward and can be achieved by model selection. However, model selection for active learning is an open problem. In this talk, I will present a noise-robust margin-based active learning algorithm that can find homogeneous multi-dimensional linear separators while adapting to unknown level of noise and achieves optimal statistical rate up to polylogarithmic factors. The ideas have close connections and implications for adaptive convex optimization where one can achieve adaptivity to the degree of convexity.

There is a chasm between theory and practice in machine learning. Theoretically derived algorithms are often empirically outperformed by heuristic ones engineered for the specific problem. The reason for this chasm is that theoretically derived algorithms are pessimistic and are tailored from a worst case analysis. There has of course been a plethora of work on adaptive learning algorithms that obtain the best of both worlds, the robustness against worst case instances and the good performances obtained by tailor made algorithms facing easy data. However often these analysis are case by case and problem specific. In this work we attempt to develop a unifying theory for adaptive online learning which in a sense is a first step to developing a VC or PAC style theory for adaptive online learning. We propose a general framework for studying adaptive regret bounds in the online learning framework, including model selection bounds and data-dependent bounds. Given a data- or model-dependent bound we ask, "Does there exist some algorithm achieving this bound?" We show that modifications to recently introduced sequential complexity measures can be used to answer this question by providing sufficient conditions under which adaptive rates can be achieved. In particular each adaptive rate induces a set of so-called offset complexity measures, and obtaining small upper bounds on these quantities is sufficient to demonstrate achievability. A cornerstone of our analysis technique is the use of one-sided tail inequalities to bound suprema of offset random processes.

Our framework recovers and improves a wide variety of adaptive bounds including quantile bounds, second-order data-dependent bounds, and small loss bounds. In addition we derive a new type of adaptive bound for online linear optimization based on the spectral norm, as well as a new online PAC-Bayes theorem that holds for countably infinite sets.

Optimal convergence rates in i.i.d. learning problems are determined by model complexity and a parameter indicating the inherent 'easiness' of the problem. As recently shown [1], for bounded and subgaussian losses this easiness is determined by a 'central' condition which generalizes both

1. the Bernstein condition of e.g. Bartlett and Mendelson (2006), itself a generalization of the Tsybakov margin condition to general losses and situations where the Bayes predictor is not in the class
2. stochastic mixability, itself a generalization of the stochastic-exp-concavity condition of Juditsky-Rigollet-Tsybakov (2008) for fast rates in on-line learning

Moving from stochastic to online adversarial, here we introduce a condition that expresses for an individual data sequence how 'easy' it is. We develop the individual-sequence central-condition with parameter \(\alpha\) between \(0\) and \(1/2\). Under this condition, the Hedge algorithm with \(K\) predictors and learning rate decreasing as \(T^{-\alpha}\) achieves a regret of order \((\log K)^{1-\alpha} T^\alpha\), nicely interpolating between the worst-case \(\sqrt{ (\log K) T }\) regret and the 'easy' \((\log K)\) regret that can be achieved if losses are i.i.d. While to use Hedge, one needs to know \(\alpha\) in advance, the recent Squint algorithm [2] automatically adapts to the right \(\alpha\).

(joint work with Wouter Koolen and Tom Sterkenburg)

We initiate the study of boosting in the online setting, where the task is to convert a "weak" online learner into a "strong" online learner. The notions of weak and strong online learners directly generalize the corresponding notions from standard batch boosting. In this talk we focus on the classification setting, for which we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority, and we prove that it is essentially optimal in terms of the number of weak learners and the sample complexity needed to achieve a specified accuracy. The second algorithm is adaptive (in the sense that it obtains improved performance for "easy data") and parameter-free, albeit not optimal.

In recent years, the literature on data-dependent performance bounds for full-information online learning underwent a rapid growth and by now, we have an almost complete understanding of what guarantees are achievable and what are not. However, the picture in partial-information (and, in particular, bandit) problems is much more scattered: only a handful of adaptive bounds existing for full-information settings have equivalents in the bandit case. The most surprising gap in the literature is the lack of "first-order" regret bounds for bandits, which is the most basic improvement in full-information settings, achievable by nearly all known full-information learning algorithms. In this talk, I review some existing results concerning adaptive bounds and describe a new efficient algorithm that achieves a first order bound for a general class of bandit problems.

In the second half of the talk, I describe some of the main obstacles for proving adaptive performance bounds for bandit problems. In particular, I show how the most powerful tools for proving adaptive bounds for the full information case break down in the bandit case, suggesting that the possibilities for learning faster from easy data may be much more limited in partial-information settings than in full-information problems.