Editors’ Introduction
Sanjay Jain, Rémi Munos, Frank Stephan, and Thomas Zeugmann

The aim of the series of conferences on Algorithmic Learning Theory (ALT)
is to look at learning from algorithmic and mathematical perspective. Over timeseveral models of learning have been developed which study different aspectsof learning. In the following we describe in brief the invited talks and the contributed papers for ALT 2013 held in Singapore.
Invited Talks. Following the tradition of the co-located conferences ALT and
DS all invited lectures are shared by the two conferences. The invited speakers
are eminent researchers in their fields and present either their specific researcharea or lecture about a topic of broader interest.
This year’s joint invited speaker for ALT 2013 and DS 2013 is Nir Ailon,
who is an assistant professor at the Technion Department of Computer Sciencesince 2010. He received his Ph.D. from Princeton University in 2006. Then hejoined the Institute for Advanced Study in Princeton for a year as a postdoctoral member. Subsequently, he worked at Google Research for two years. His
research interests comprise high dimensional statistics, dimensionality reduction
techniques, learning theory, preference analysis, and ranking and clustering. His
research contributions have been recognized by a SIAM outstanding paper award
in 2012. The invited talk Learning and Optimizing with Preferences by Nir Ailon
deals with reasoning about preferences and choices as a fundamental source of
information. The social sciences have studied preferences and choices for centuries and with the advent of the internet, preference and ranking data became
ubiquitous. This abundance attracted many computer scientists to study suchdata in different contexts such as in information retrieval and filtering, rankaggregation, learning theory, among others. Ailon surveys fundamental results,
points to important problems, and exemplifies the challenges that arise in thiscontext. In particular, he points out that preferential information can be used
to optimize information systems.
The invited speaker for ALT 2013 is Eiji Takimoto, who is a professor at the
Department of Informatics at Kyushu University, Fukuoka, Japan. His major research interests are online decision making, computational learning theory, andcomplexity theory. The invited paper Efficient Algorithms for Combinatorial Online Prediction (co-authored by Kohei Hatano) deals with the following problem.
Let a concept class C be given which is typically finite but contains exponentially many concepts. Each concept of the class is encoded as an n-dimensional
non-negative real valued vector, where n is a natural number. Furthermore, aso-called loss space L is given which consists also of non-negative real valued vectors. The online linear optimization problem specified by a concept class C andthe loss space L can then be described as a repeated game between the player
and the adversary. For each trial t = 1, 2, . . . , T , the player chooses a concept

2

S. Jain et al.

ct ∈ C and the adversary returns a loss vector `t ∈ L. The player suffers a loss
ct · `t . The task is to minimize the expected regret. There are many interesting
problems that can be studied in this model such as spanning trees of a given
graph, truth assignments for a given CNF formula, and so on. The paper surveys
some recent results on universal and efficient implementations of low-regret algorithmic frameworks such as Follow the Regularized Leader (FTRL) and Follow
the Perturbed Leader (FPL).
Nader H. Bshouty is the ALT 2013 tutorial speaker. He is the Helen andMorris Mauerberger Chair in Sciences at the Technion Department of Computer
Science. His major research interest is computational learning theory. In his talkExact Learning from Membership Queries: Some Techniques, Results and New
Directions he focuses on the following general learning scenario. We are given a
black box that contains a function f : D → R from some class C of functions.
The source of information for the learner are membership queries, i.e., the learnerchooses in each time step an element d from the domain D of the function f ,and then the black box returns f (d) ∈ R in time T . The learning goal is then
to exactly learn the function f with a minimum number of queries and optimal
time complexity. Sometimes also a weaker learning goal is considered. That is,
the learner has to decide whether or not the function f is equivalent to a prespecified function g ∈ C. Such learning problems have been studied in different
areas and also under a variety of names such as interpolation, active learning,inference, guessing game, functional verification, and so on. Bshouty provides
an extensive survey of the results obtained and outlines new directions that areworth investigating.
Hannu Toivonen is the invited speaker for DS 2013. Since 2002, he is Professor of Computer Science at the University of Helsinki, Finland. Prior to thecurrent position, he worked at Nokia Research Center as principal scientist. His
research interests comprise data mining, computational method for data analysis, and applications of these areas in bioinformatics, genetics, ecology, andmobile communications. Currently, he and his research group focus their interest to computational creativity and this area is addressed in his talk Creative
Computers and Data Mining. A major goal in computational creativity is toenable computers to perform tasks that require creative skills such as thoseneeded in writing poetry or composing music. Clearly, a computational agent
then needs to know the field in which it operates. Toivonen and his researchgroup discovered that data mining has a great potential for achieving this goal.
He outlines how to make creative agents adaptive to various fields and genresby automatic discovery of relevant information from existing creative artifacts.
The talk gives several examples of how verbal creativity can benefit from data
mining of existing text corpora. Furthermore, he exemplifies that computational
creativity tools allow a whole new approach to data analysis. In this “Affective
Data Analysis,” the goal is to turn data into a subjective, esthetic experience byautomatic or semiautomatic creation of a novel artifact using the user’s data as
inspiration. This idea is illustrated with musicalization of sleep measurements
and chat discussions.

Editors’ Introduction

3

Online Learning. In online learning, a problem (or a component of it) has tobe solved online. At time t, some instance of a problem (or part thereof) is given
to the learner, and it outputs a solution (or part thereof). The online algorithm
suffers a regret based on how badly it performs compared to the best offline
algorithm, which knows the whole input. In some cases, the offline algorithms
might be required to have some properties, such as being deterministic, whereas
the online algorithm might be probabilistic.
One of the uses of online prediction is in stock market, where one may want topredict as well as any other strategy. The paper Universal Algorithm for Tradingin Stock Market Based on the Method of Calibration by Vyugin considers such aproblem. Suppose S1 , S2 , . . ., are prices of a stock over time. Assume via scalingthat each Si is in the range [0, 1]. Suppose a trader trades in each interval, andgains (looses) based on the change in price. Furthermore, the paper assumesa side information zi ∈ [0, 1], a signal, is given to the trader. Consider any
stationary trading strategy, D, which is a continuous function of zi , that is,
the trader buys/sells D(zi ) units of share at time i. Then Vyugin constructs−1
a randomizing algorithm M such that, lim inf n→∞ n1 (KnM − kDk+ KnD ) ≥ 0,MD
almost surely, where Kn and Kn are the gain made by M and D respectively−1
after n time steps, and kDk+ is a normalizing factor used (as D may buy/sellmore than one units, though M is restricted to buy/sell 1 unit in each timestep).
Online prediction of combinatorial concepts such as set cover, permutations,
MAX-SAT etc arise in real life situations such as in routing and ranking. Suppose C ⊆ Rn is a finite set of combinatorial concepts. Consider the following
protocol for online prediction: in each trial t, the player predicts ct ∈ C, theadversary returns loss vector `t , and the player has a loss of ct · `t . The aim of
the player is to minimize
the loss compared to the best possible c ∈ C that is,
P
P
c
·
`
.
c
·
`
−
min
t Fujita, Hatano and Takimoto in the paper Combinac∈Ctt t t
torial Online Prediction via
P a variant in which one miniPMetarounding consider
mizes the α regret, that is t ct · `t − α minc∈C t c · `t . This is based on the factthat for many combinatorial problems, α-approximation algorithms are known,
which are allowed to be used as oracles by the online algorithm. Earlier, Kalai and
Vempala had proposed a Follow the Perturbed Leader (FPL) √algorithm, whichworks for α = 1. This algorithm has a regret bounded by O( T ) and runs intime O(n) per√trial. Taking into account α-approximations, this algorithm hasa regret O(αT T ), which is√high. Kakade, Kalai and Ligett proposed anotherstrategy which achieves O(α T ) regret with running time of O(poly(n)T ). The
paper by Fujita, Hatano and Takimoto considers a stronger assumption on an
approximation algorithm: for any ` ∈ [0, 1]n as input, the approximation algorithm outputs a c ∈ C such that c · ` ≤ α minx∈P x · `, where P is a convex
superset of C and linear optimization over P can be done in time polynomial
in n. This is based on the fact that several combinatorial problems have corresponding linear programming approximations. Under this assumption, Fujita,√
Hatano and Takimoto give a strategy whose regret is bounded by O((α + ε) T )and has running time polynomial in n and 1/ε for any ε > 0. The main idea

4

S. Jain et al.

used is the concept of metarounding by boosting. Metarounding was originallyproposed by Carr and Vempala for a different purpose. The authors show as examples that the method works for online set cover, MAX-SAT, and some othercombinatorial problems.
In their paper On Competitive Recommendations Uitto and Wattenhofer consider the problem of recommending an item to a user. Suppose M is an unknownn × m binary matrix. The goal of the algorithm is to determine at least one 1
entry in each row, using a minimum number of queries, where it is assumed thateach row contains at least one 1. The entries can be considered as preferencesof n users (customers) on m items (say books): M (i, j) = 1 can be considered ascustomer i liking book j. The goal of the algorithm is to find a suitable book foreach customer. To determine a suitable book for customer i, the algorithm canquery an entry of the matrix. The protocol of the algorithm works in rounds,
where each round has three steps, (where U is the set of unsatisfied customers,
initially the set of all the customers): (1) receive a customer u ∈ U chosen uniformly at random, (2) recommend book b to u, and (3) if M (u, b) = 1, then thealgorithm can remove u from U . One measures the number of rounds needed(equivalently the number of recommendations made in the step (2) above). The
cost can thus vary from n to m · n. Comparing an on-line algorithm against an
off-line algorithm which knows all the entries of the matrix is not much useful,as the off-line algorithm can then solve the problem using n queries. Thus, Uitto
and Wattenhofer consider the competitiveness against a quasi-off-line algorithm
which only knows the probability distribution D over possible preference vectors and n, the number of customers. The preference vectors for these customers
are chosen independently at random from D. The authors consider the caseof m = O(n), as if m is very large, many √of columns might have 0 for every
customer. Uitto and Wattenhofer give a O( n log2 n) competitive on-line
algo√rithm for the problem. The authors also show a lower bound of Ω( n) for theabove problem, and thus their algorithm is within a poly-log factor of optimalcompetitive ratio.
The paper On-line PCA with Optimal Regrets by Nie, Kotlowski and Warmuth considers the online version of the Principal Component Analysis (PCA)
problem. In PCA, an n-dimensional datum is given as input, and the output is a projection of it in k-dimensions, where k is much smaller than n. In
their paper, the following model is considered. In each trial t = 1, 2, . . . , T
the algorithm first chooses a projection matrix Pt of rank k. Then it is given
the next point xt of dimension n. The algorithm suffers a compression loss
2
kxt − Pt xt k2 = tr((I − Pt )xt xTt . The goal is to obtain an on-line algorithm
whose cumulative loss is not far from the loss of the best possible projection
matrix P which is chosen after having seen all the data. There are two maintypes of algorithms which have been used for on-line learning. The Gradient
Descent (GD) family of algorithms and Exponentiated Gradient (EG) family ofalgorithms. For PCA, the authors show that EG achieves the same regret boundas GD despite the sparseness of instance matrices (for which usually EG algo-Editors’ Introduction

5

rithms do not do well). They also show that for both algorithms, regret bounds
are within a constant factor of a lower bound for any PCA algorithm.
Inductive Inference and Grammatical Inference. The learning modelstudied in inductive inference of formal languages from positive data may bedescribed as follows. A learner receives, one element at a time, all the elementsof a target language L from a class of languages L. Over time, each element of thetarget language is presented at least once (in arbitrary order) to the learner andno non-elements of the language L are presented to the learner. As the learnerreceives its data, it conjectures a sequence of hypotheses. These hypotheses areinterpreted as grammars in some system which contains grammars for all the
languages in L. If the sequence of grammars converges to a grammar for L, then
one can say that the learner has learned the language L. The learner learns L if
it learns each language in L. This is basically the model of explanatory learning
first considered by Gold, and later by various authors. Over time various modifications to the above model have been considered. A variation of the model of
explanatory learning, first studied by Osherson, Stob and Weinstein, is partial
learning, where the learner outputs exactly one index infinitely often, and thisindex is for the input language. In the traditional explanatory learning model,
various researchers have considered constraints on the learner such as (i) consistency (first introduced by Bārzdiņš), where each conjecture of the learner is
expected to be consistent with the data seen by the time the conjecture is made,i.e., the conjectured language must contain the data seen so far, (ii) conservativeness (first studied by Angluin), where the learner changes its hypothesis to adifferent one only if the presented data are inconsistent with its hypothesis, and(iii) confidence, where the sequence of hypotheses of the learner converges to ahypothesis, whether correct or wrong, even when the data presented to it is fora language outside the class being learned.
In the paper Partial Learning of Recursively Enumerable Languages, Gao,
Stephan and Zilles study the corresponding notions for partial learning. They
give a complete picture of relationships between these criteria. Furthermore, theauthors also give interesting characterizations of some of the inference criteria
studied. In particular they show that a class is consistently partially learnable
iff it is a subclass of a uniformly recursive family of languages.
One of the main problems considered in inductive inference is comparison
between different learning criteria. That is, given two learning criteria I and J,
is every class of languages (functions) learnable under criterion I also learnable
under criterion J? There are two main reasons for a class not to be learnable
under a criterion: topological reasons, when the class is not learnable under thecriterion even if one allows the learners to be non-computable; and computational
reasons, where the class is not learnable for computable learners, but would
become learnable if the computability constraints are removed from the learner.
The paper Topological Separations in Inductive Inference by Case and Kötzing
formalizes when two learning criteria separate topologically in learning power.
This allows one to study more closely the relative powers of the two criteria. For
example, if one considers the model T xtExa , where in the explanatory learning

6

S. Jain et al.

model described above one allows the final conjecture to have upto a errors,then one can show that T xtExa+1 and T xtExa separate topologically. However,
if one considers vacillatory learning, that is the number of different grammars
output by the learner during the learning process is finite, and after some time,
all the grammar output by the learner are correct, then it can be shown thatvacillatory learning separates from explanatory learning, but not topologically.
Case and Kötzing show for variety of pairs of learning criteria from the literaturethat they separate topologically, whereas some pairs of criteria are shown not toseparate topologically.
The class of all recursively enumerable languages or even that of all contextfree languages or of all regular languages is not learnable under various modelsof learning, such as explanatory learning. Thus it is interesting to consider special subclasses of context-free languages which are learnable, particularly if they
can be learned efficiently. In the literature there have been several results showing interesting subclasses of context free languages to be learnable under the
explanatory learning model and/or other learning models. Some examples include explanatory learning of substitutable context free languages and learningof c-deterministic and congruential context free languages from a minimally adequate teacher. However, these results are often impractical, as one may neverknow when the learner has converged to the correct grammar in explanatory
learning and a minimally adequate teacher is often not available. Probabilistic learning is often considered more practical. However, the positive results forlearning such classes in Valiant’s PAC learning model are rather limited. Clark
has shown that a class of unambiguous non-terminally separated languages is
PAC learnable from partially distribution-free positive data. Luque and Lopez
later generalized this result. The paper PAC Learning of Some Subclasses ofContext-Free Grammars with Basic Distributional Properties by Shibata andYoshinaka expands Clark’s result to other subclasses of context free grammars
that are known to be exactly learnable based on distributional learning techniques. Shibata and Yoshinaka translate some of the existing distributional exact
learning algorithms into PAC-type ones where a learner gets positive examples
drawn from a distribution determined by a probabilistic context free grammar.
Under some assumptions, Shibata and Yoshinaka show how membership queries
used in exact learners can be simulated by observed positive examples.
A goal of a scientist is to acquire knowledge about the surrounding and to predict the future. The Solomonoff induction method solves the prediction problem
by using algorithmic information theory to obtain a universal prior and Bayes
theorem to perform induction. This method is able to predict in any stochastically computable environment. However, the method itself is uncomputable.
Solomonoff induction has been extended to the reinforcement learning framework by Hutter. However, optimal reinforcement learning is different from an
optimal scientist as it is rewarded extrinsically by the environment rather thanintrinsically by the information gain. A knowledge seeking scientist tries to maximize the information gain. Storck, Hochreiter, and Schmidhuber used various
information gain criteria in a frequentist setting to explore non-deterministic

Editors’ Introduction

7

Markov environments, where information gain is considered as rewards. Orseau
had earlier presented two universal knowledge seeking agents, called SquareKSA and Shannon-KSA for deterministic computable environments. In the paper Universal Knowledge-Seeking Agents for Stochastic Environments, Orseau,
Lattimore, and Hutter consider countable stochastic environments, and define
a new universal knowledge-seeking agent based on Kullback-Leibler divergence.
The resulting universal agent, if it exists, has several nice properties. The newagent is resistant to noise and behaves as expected in variety of toy examples.
Teaching and Learning from Queries. Suppose X = {x1 , x2 , . . . , xn } tobe an instance space and assume that C and H are subsets of the powerset of
X. Then C and H are said to be a concept class and a hypothesis class, respectively. A labeled sample S ⊆ X × {0, 1} is C realizable if there exists a
C ∈ C such that, for all (x, `) ∈ S, C(x) = `. A sample compression scheme,
for a given class C, consists of a compression function f and a reconstruction
function g, with the property that, for any labeled sample S, the conditions
f (S) ⊆ S and g(f (S))(x) = ` are satisfied for all (x, `) ∈ S. An open question iswhether for any class C, there exists a sample compression scheme of size linear(or even equal) to the VC-dimension of C. A teaching set for a concept C ∈ C
is a sample S such that C is the only concept in C which is consistent with S.
A teaching plan for the (ordered) class C = {C1 , C2 , . . . , Cm } is a sequence ofsamples ((C1 , S1 ), (C2 , S2 ), . . . , (Cm , Sm )) such that St is a teaching set for Ct
with respect to the class {Ct , Ct+1 , . . . , Cm }. The order of the teaching plan is
the maximum over the cardinality of the Si ’s. The recursive teaching dimension (RTD) of C is the minimum order over all teaching plans for C. The paper
Order Compression Schemes by Darnstädt, Doliwa, Simon, and Zilles considers a sample compression scheme called order compression scheme. In this, forthe hypothesis class H = {H1 , H2 , . . . , Hm }, f (S) is the smallest subset of S
that is a teaching set for Ht with respect to {Ht , Ht+1 , . . . , Hm }, where t is thelargest number such that Ht is consistent with S. Furthermore, g(f (S)) = Hr ,for the largest number r such that Hr is consistent with f (S). The authors showthat such a scheme is indeed a compression scheme. Let OCN(C, H) denote thecardinality of the largest compressed sample in the order compression scheme
defined above, and OCN(C) denote the minimal OCN(C, H) over all H ⊇ C.
Then the authors show that OCN(C) ≥ RTD(C), and OCN(C) ≥ VCD(C). Furthermore, for many natural classes, such as those which are intersection-closed
or maximum or Dudley classes, the authors show that OCN(C) =VCD(C). Thus,
order compression schemes give a reasonable way to try to address the sample
compression conjecture.
In the paper Learning a Bounded-Degree Tree using Separator Queries, Jagadish and Sen investigate the following problem. Consider an undirected tree T
with bounded degree. Suppose the learner knows the nodes in the tree (numbered 1 to n), but does not know the edges of the tree. The learner has to find thetree T using the following type of queries called separator queries: Does node x
lie in the path from node a to node b? Jagadish and Sen show that there existsan O(n1.5 d log n) time algorithm for the above problem, where d is the bound8

S. Jain et al.

on the degree of the tree, and n is the number of nodes of the tree. They also
give an O(nd2 log2 n) randomized algorithm and show a lower bound of Ω(nd)for the problem.
Bandit Theory. In multi-armed bandit problems, the standard stochastic setting considers an agent or learner facing a finite number of distributions (alsocalled arms), that can be sampled one at a time. Each sample gives a reward,
and the goal is to maximize the reward after T trials. As the learner/agent’s
decision is made based on random data from an unknown distribution, there
is often a tradeoff between exploration (drawing more arms) and exploitation(drawing the current best arm). For the analysis, the learner is often compared
to a fixed strategy which constantly pulls the arm with highest mean reward. The
expected regret is then the difference between the learner’s cumulative reward
and the cumulative reward of the fixed strategy as described above.
The paper Faster Hoeffding Racing: Bernstein Races via Jackknife Estimatesby Loh and Nowozin considers a variation of the bandit problem where the goal
is not to minimize the expected regret but to identify an almost optimal arm
with high confidence using as few resources as possible. That is, the aim is todetermine how many samples to use before concluding that with probability atleast 1 − δ, the selected arm is within a factor 1 − ε of optimal. Often racing
algorithms are used, where confidence intervals are constructed. As the aim is toget a (near) optimal arm, one eliminates arms with low value after few samples,
and then races the best candidates against one another. Hoeffding race derives
its name from Hoeffding’s inequality, which is used to construct the confidence
intervals. Loh and Nowozin use tighter variants based on empirical Bernsteininequalities as well as jackknife estimates for constructing confidence intervals.
They show that this gives better bounds for U-statistics and discrete entropy
estimators.
The usual situation in bandit problems is for the learner to maximize its
expected return (or minimize the expected regret). However this may not besuitable for every problem. For example, in medical treatment, one may wantto avoid endangering the patient. So one wants to avoid high variation in the
rewards. In particular, one may prefer an arm with smaller mean, but narrower
left-tail compared to an arm with larger mean, but fat left-tail. Maillard’s paper
Robust Risk-averse Stochastic Multi-Armed Bandits addresses such a situation.
This paper defines a notion of risk-averseness based on the best risk-aversenessof the arms, and then gives an algorithm, called RA-UCB, which has O(log T )bounds on the regret and O(log T ) bounds on the risk-averse regret, with respect
to the best risk-averse arm, where T is the number of trials.
The paper An Efficient Algorithm for Learning with Semi-Bandit Feedback
by Neu and Bartók considers a semi-bandit setting, where one can pull several
arms together and see the loss/reward for each of the arms pulled. Only certain
combinations of arms are allowed to be pulled together. An example where this
could be useful is displaying m advertisements out of a possible n advertisements when a user visits a web-page. The authors propose an algorithm combining the Follow-the-Perturbed-Leader (FPL) prediction method with a newEditors’ Introduction

9

loss estimation procedure which they call Geometric Resampling (GR). This
new algorithm can be efficiently implemented whenever efficient offline combinatorial optimization√ is possible. The authors show the expected regret, after T
rounds, to be O(m dT log d), where the elements of the decision set is describedusing d-dimensional binary vectors with at most m non-zero entries. This also
improves the√ best known regret bounds for FPL in the full information settingto O(m3/2 T log d).
Statistical Learning Theory. Many real world datasets have a high dimension. The time-complexity of many existing algorithms dealing with a large
amount of data often depends super-polynomially on the dimension. This iscalled the curse of dimensionality in machine learning. Often, the dimension of
the data-sets can be reduced as the actual data lie in a low dimensional manifold. Several dimension reduction techniques have been developed. Dasgupta
and Freund have analyzed the technique presented by Freund et al. to learn the
structure of a manifold that has low dimension d, but the actual data lie in RD ,where D is much larger than d. This involved a construction of a data structure
called random projection tree. Choromanska, Choromanski, Jagannathan, andMonteleoni, in the paper Differentially-Private Learning of Low Dimensional
Manifolds, extend this technique for the case of differential private learning.
Differential privacy is a model of privacy for database access. The aim in thissetting is to make sure that the addition/removal of a single data item in the
database does not cause significant impact on the output produced for a query.
The problems of high-dimensionality are compounded in differentially-private
learning as it needs more data. The authors extend the random projection tree
technique by constructing a differentially-private data structure that depends
exponentially only on the doubling dimension d of the data rather than the
extrinsic dimension D.
In traditional learning theory often the assumption is made that the data
are independent and identically distributed (IID). However, this may not always
hold in the real world. When training data come form a Markov chain withcertain mixing properties, a common algorithm that has been analyzed is theempirical risk minimization (ERM) algorithm, which tries to find the hypothesis
which minimizes the empirical loss. Generalization bounds of ERM have been
proved for strongly mixing data, uniformly ergodic data, and V-geometricallyergodic data. The paper Generalization and Robustness of Batched Weighted
Average Algorithm with V-geometrically Ergodic Markov Data by Cuong, Ho,and Dinh, considers another learning algorithm called the batched weighted average (BWA) algorithm. This algorithm places weights on each of the hypotheses
during training. During testing a prediction is made based on the weighted average prediction of the hypotheses. The advantage of such a method is that itsuffers less from overfitting. Cuong, Ho, and Dinh give a PAC-style bound on the
training sample size for the expected loss to converge to optimal loss with highprobability when the training data are V-geometrically ergodic. The authors also
show robustness of BWA in the presence of a small amount of noise.

10

S. Jain et al.

Most of the dimension reduction techniques require that the date lie on alow dimension subspace, and do not work when the sample is close to a lowdimensional subspace. The paper Adaptive Metric Dimensionality Reduction by
Gottlieb, Kontorovich and Krauthgamer addresses this issue when the data areclose to a low-dimensional subspace. The authors show that the linear classifier
generalizes well for such data regardless of the ambient dimension. This resultis shown for the Euclidean space and then generalized to metric spaces.
The paper Dimension-Adaptive Bounds on Compressive FLD Classification
by Kabán and Durrant continues the work on how to address the curse of dimensionality by using the intrinsic dimension rather than the ambient dimension.
This paper analyzes the Compressive Fisher Linear Discriminant (CFLD) classifier and shows that, under certain conditions, the estimated error of the CFLD
depends on the intrinsic dimension of the data rather than the ambient dimension. The authors also show that if the data is noisy, then dependence on theambient dimension cannot be totally avoided.
Bayesian/Stochastic Learning. In the paper Bayesian Methods for LowRank Matrix Estimation: Short Survey and Theoretical Study, Alquier studies
low-rank matrix learning. Despite empirical performance of Bayesian procedures
being at least as good as the performance based on penalized empirical risk minimization methods, there have not been many theoretical guarantees on Bayesian
procedures. In his paper, Alquier gives a theoretical result on the Bayesian estimator in the context of reduced rank regression. For some appropriate choiceof the parameters, the rate of convergence is the same as that for penalized
methods, up to log terms.
The sequence prediction problem is to predict xt , having already observed
x1 , x2 , . . . , xt−1 . The sequence is assumed to be sampled from an unknown measure µ contained in a countable model class M. At time t, having observed
x1 , x2 , . . . , xt−1 , the predictor outputs a distribution ρt over the next symbol xt .
A predictor can be considered good if, ρt − µt → 0. Bayesian prediction methods are often considered, where one assigns a non-zero prior probability to eachmeasure in M. Let ξ denote the probability distribution obtained for a universal
Bayesian
predictor. Strong bounds are known on the expected cumulative erPror t dist(ξt , µt ) with respect to the Kullback-Leibler divergence and Hellinger
distance. The paper Concentration and Confidence for Discrete Bayesian Sequence Predictors by Lattimore, Hutter and Sunehag shows a high-probability
bound on this cumulative error: with respect to the Kullback-Leibler divergence,the cumulative error is bounded by e · (ln 6δ )(ln 2δ + ln w1µ ), with µ-probability atleast 1 − δ, where µ is the underlying probability distribution. The authors also
show that this bound is close to optimal. Furthermore, the authors show that
the Kullback-Leibler divergence dist(ξt , µt ) can be bounded without knowing µ(but knowing a bound on prior probability for µ), with high confidence.
Convex optimization is the task of approximately minimizing a convex function over a convex set, given oracle access to unbiased estimates of the function
and its gradient at any point, thereby using as few queries as possible. The problem of active threshold learning can be described as follows. Suppose we have

Editors’ Introduction

11

an interval [0, R]. A point x ∈ [0, R] has label + and − with probability η(x)and 1 − η(x), respectively. Assume that there exists a unique point t such that
η(t) = 1/2, and η(t) > 1/2 on one side of t and η(t) < 1/2 on the other side of t.
Then the task is to estimate t by sequentially querying T points and observing thelabels from the distribution. Recently some connections have been establishedbetween convex optimization and active learning. In the paper Algorithmic Connections Between Active Learning and Stochastic Convex Optimization, Ramdas
and Singh continue to exploit these connections. Inspired by a recent optimization algorithm that was adaptive to unknown uniform convexity parameters, theauthors present a new active learning algorithm for one-dimensional thresholds
that is adaptive to unknown noise parameters. Furthermore, the authors showthat noisy gradient signs suffice for minimization of uniformly convex functions
by showing that a random coordinate descent algorithm with an active learning
line-search subroutine achieves minimax convergence rates.
Unsupervised/Semi-Supervised Learning. In many learning situations, thefeedback for the learning algorithm is scarce or absent. In the paper, Unsupervised Model-Free Representation Learning, Ryabko considers a situation in which
all or a large part of relevant information is in the time-series dependence of theprocess. Such a situation happens for example in speech or hand-written text
or sensor data interacting with the environment. Assume that there is a stationary sequence X0 , X1 , . . . , Xn , . . ., where Xi belongs to a large continuousand high dimensional space X . The aim is to look for a compact representationf (X0 ), f (X1 ), . . ., where f (Xi ) belongs to a small space Y. In an ideal situation,
there exists a function f as above such that, given f (Xi ), Xi is independent ofrest of the sample X0 , X1 , . . . , Xi−1 , Xi+1 , . . .. Thus all the time-series dependence of the sequence is available in f (X0 ), f (X1 ), . . ., and given this sequence,
the Xi are conditionally independent. In this ideal situation, it can be shownthat f maximizes I∞ = h(f (X0 )) − h∞ (f (X)), where h(f (X0 )) gives the Shannon entropy of the first element and h∞ is the entropy rate of the stationary
time series f (X0 ), f (X1 ), . . .. In a non-ideal situation one may define the function f which maximizes I∞ as the one which preserves the most of the timeseries dependence. In the paper, Ryabko shows that under certain conditions
it is possible to estimate I∞ uniformly over a set F of functions from X to Y.
This can even be done without estimating the distribution of the original timeseries (Xi )i∈N . In particular, if the sequence (Xi )i∈N forms a Markov process,then in the ideal situation, it can be shown that (f (Xi ))i∈N is also Markov andthat I∞ (f ) = h(f (X0 )) − h(f (X1 )|f (X0 )). Rybko also extends the results to thecase when the learner is allowed to take some actions (which may affect the next
observations).
Clustering has become one of the fundamental problems in machine learning
due to the presence of large datasets. Spectral clustering is one of the existing
techniques for clustering. A problem for scaling up this method is the cost ofbuilding an affinity matrix between pairs of data points, which becomes computationally prohibitive for large data sets. There have been several attempts
to address the problem, however, most of these works did not provide perfor-

12

S. Jain et al.

mance guarantees. The paper Fast Spectral Clustering via the Nyström Method
by Choromanska, Jebara, Kim, Mohan, and Monteleoni, gives a computationallyefficient modification of the spectral clustering algorithm. The authors combine
the spectral clustering idea with the Nyström approximation method. For thisthey only need to sample a small random set of columns of the affinity matrix, which leads to a complexity that is linear in the number of data points.
The authors also provide performance guarantees for their algorithm, which arecomparable to spectral clustering with the original graph Laplacian.
Often, the distribution from which data are sampled may change over time.
Suppose we have a sample
x := X1 , X2 , . . . , Xbnθ1 c , Xbnθ1 c+1 , . . . , Xbnθ2 c , Xbnθ2 c+1 , . . . , Xbnθκ c+1 , Xnformed by the concatenation of κ + 1 non-overlapping segments, where θ1 ,
θ2 , . . . , θκ ∈ (0, 1) are parameters. Each segment is generated by some unknown stochastic process distribution. The aim is then to determine the change
points bnθ1 c, bnθ2 c, . . . , bnθκ c. In the paper, Nonparametric Multiple Change
Point Estimation in Highly Dependent Time Series, Khaleghi and Ryabko consider such a problem. They consider a highly dependent time series, where eachsegment is generated by an unknown stationary ergodic process distribution.
The joint distribution over the samples can be otherwise arbitrary. The authors
construct an asymptotically consistent algorithm that estimates the parametersθ1 , θ2 , . . . , θκ , where the estimates becomes arbitrary close to the actual one as ngoes to infinity.