Designed and built with care, filled with creative elements

Top

The complexity of algorithmic teaching, query learning, and sample compression

IHP Salle 314

Computational learning theory is concerned with the complexityof machine learning problems, for instance with the question ofhow many training examples are needed for a machine toidentify a concept in a given class of possible target concepts.   This presentation focuses on the combinatorial structureof concept classes that can be learned from a small number ofexamples. When learning from randomly chosen examples, theVC-dimension is known to provide bounds on the numberof examples needed for learning. However, for previously studiedmodels of algorithmic teaching (i.e., learning from helpfulexamples), no such combinatorial parameters are […]

Information-based complexity of black-box convex optimization: a new look via feedback information theory

IHP Salle 314

In this talk, I will revisit information complexity of black-box convex optimization, first studied in the seminal work of Nemirovski and Yudin, from the perspective of feedback information theory. These days, large-scale convex programming arises in a variety of applications, and it is important to refine our understanding of its fundamental limitations. The goal of black-box convex optimization is to minimize an unknown convex objective function from a given class over a compact, convex domain using an iterative scheme that generates approximate solutions by querying an oracle for local information […]