“Efficient Algorithms and Computational Barriers in Reliable Machine Learning”
Speaker: Alkis Kalavasis
National Technical University of Athens
Abstract: In this talk, we will discuss the computational challenges arising in various problems in Reliable Machine Learning. Reliable ML aims at the design of computationally efficient algorithms that provide guarantees such as robustness to biased data, reproducibility and privacy. We firstly focus on the design of algorithms robust to biased and corrupted observations. We begin with the problem of learning from coarse data. The motivation behind this problem is that in many learning tasks one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the annotator. We formalize these settings from the viewpoint of computational learning theory and provide efficient algorithms and computational hardness results. We then continue with the task of learning noisy linear label rankings. Label ranking is the supervised task of learning a sorting function that maps feature vectors to rankings over a finite set of labels. We provide the first efficient algorithms for learning linear sorting functions in the presence of bounded noise (an extension of the Massart noise condition to label rankings) under Gaussian marginals. Next, we consider questions regarding responsibility aspects of ML systems. We study the important problem of reproducibility as an algorithmic property in decision-making settings. We introduce the notion of reproducible policies in the context of stochastic bandits, one of the canonical problems in interactive learning. A policy in the bandit environment is called reproducible if it pulls, with high probability, the exact same sequence of arms in two different and independent executions (under independent reward realizations and shared internal randomness). We show that not only do reproducible policies exist, but also they achieve almost the same optimal (non-reproducible) regret bounds in terms of the time horizon. In the end of the talk, we will shortly discuss some on-going work on the complexity of min-max optimization, a fundamental problem in the area of equilibrium computation in multi-agent environments.