Abstract:

 
The complexity of learning is measured mainly along two
axis: information and computation.

The information complexity  of learning is supported by
a rich theory that yields rather crisp sample-size and
convergence-rate guarantees.

The focus of this talk is the computational (or algorithmic)
complexity of learning. While playing a critical role in any
application, its theoretical understanding is far less
satisfactory.

I shall concentrate on the basic learning paradigm of
Empirical Risk Minimization (ERM). I shall describe some
pessimistic computational complexity hardness results.
I shall then briefly explain the solutions suggested by
the Support Vector Machines (SVM) paradigm, and show 
new results pointing to some inherent limitations of this
approach. Finally, I shall introduce a new measure of success
for ERM algorithms (and more generally, to combinatorial
optimization approximation problems) and describe an
algorithmic technique that is guaranteed to meet this success 
measure while obtaining computational efficiency.

The talk shall be presented in a survey'ish non-technical
style and  should not require background knowledge of the
field.

The talk is based on a series of papers written in
collaboration with Hans Ulrich simon, Nadav Eiron and  Phil
Long.