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 […]

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 […]