Master’s candidate Niki Hasrati and Professor Shai Ben-David have received the best paper award at ALT 2023, the 34th International Conference on Algorithmic Learning Theory. This year, the annual meeting that explores the theoretical and algorithmic aspects of machine learning will take place in Singapore from February 20 to 23.
Their paper, “On Computable Online Learning,” studies online learning with computable learners. It analyzes that question under various requirements for successful learning. The paper gives a necessary and sufficient condition for optimal computable online learning and shows that the Littlestone dimension — a combinatorial parameter that characterizes online learnability without computability requirements — no longer applies when the learners are required to be computable.
L
to
R:
Niki
Hasrati
and
Shai
Ben-David
Niki
Hasrati
is
a
master’s
student
at
the
Cheriton
School
of
Computer
Science,
advised
by
Professor
Shai
Ben-David.
Her
research
interests
intersect
theoretical
computer
science
and
theoretical
machine
learning.
She
studies
online
learning,
private
learning,
combinatorial
characterizations
of
different
learning
models,
and
non-worst-case
analysis
of
computational
and
statistical
resources
required
for
learning.
Shai
Ben-David
is
a
University
Research
Chair
and
Professor
at
the
Cheriton
School
of
Computer
Science.
He
is
also
a
faculty
member
at
the
Vector
Institute
and
a
Canada
CIFAR
Artificial
Intelligence
Chair.
His
research
spans
a
wide
spectrum
of
topics
in
the
foundations
of
computer
science
and
its
applications,
with
a
particular
emphasis
on
statistical
and
computational
machine
learning.
The
common
thread
throughout
his
research
is
to
provide
mathematical
formulation
and
understanding
of
real-world
problems.
About this award-winning research
Two central setups for machine learning are batch learning, where the learner is given a set or batch of randomly generated training examples, and online learning, where the learner encounters examples one at a time and gets feedback on its performance on each example before being challenged with the next one.
A fundamental question in each of these setups is distinguishing between learnable and unlearnable tasks. Learnability in the batch setup is known to be characterized by the Vapnik–Chervonenkis dimension (see Vapnik and Chervonenkis, 1971) and learnability in the online setup is characterized by the Littlestone dimension (see Littlestone, 1988).
In both cases, however, learnability is defined in terms of the existence of a successful learning function — for example, a mapping of training examples to learned models. In their ALT 2020 paper, Agarwal, Ananthakrishnan, Lechner, Ben-David and Urner pointed out that in practical machine learning, one cares only about learners that can be realized by computer programs, what are known as computable learners. They showed that once one considers only such learners, the Vapnik–Chervonenkis dimension no longer characterizes learnability in the batch setup.
Niki and Shai’s 2023 award-winning paper addresses the question of computable learnability in the online learning setup. The paper analyzes various notions of success, or optimality, of an online learner when learners are required to be computable — that is, when they are executable by an algorithm. Their paper shows that, in fact, the well-known characterization of online learnability by the Littlestone dimension breaks down in the context of computable learning. The answer required the use of sophisticated recursion theoretic analysis, as well as careful examination of different tasks that an online learner may be faced with.
To learn more about the research that resulted in Niki and Shai receiving the best paper award at ALT 2023, please see Niki Hasrati, Shai Ben-David. On Computable Online Learning. 34th International Conference on Algorithmic Learning Theory (ALT), 2023.