Artificial Intelligence & Machine Learning Seminar
16:00 - 17:00
Dr Gregely Neu
Lectures, talks and seminars
Computer Science and Electronic Engineering, School of
Dr Dimitri Ognibene firstname.lastname@example.org
On 26 April we have a special talk from Dr Gergely Neu from the Pompeu Fabra University, Barcelona, about his new formal results on the PCA methods.
Gergely is a very creative and productive Machine Learning theoretician and is one of the few European recipients of the last Google Faculty Research Award. He has produced several interesting results on different areas of Machine Learning, such as Inverse reinforcement learning and the exploration-exploitation dilemma.
We consider a partial-feedback variant of the well-studied online PCA problem where a learner attempts to predict a sequence of d-dimensional vectors in terms of a quadratic loss, while only having limited feedback about the environment's choices. We focus on a natural notion of bandit feedback where the learner only observes the loss associated with its own prediction. Based on the classical observation that this decision-making problem can be lifted to the space of density matrices, we propose an algorithm that is shown to achieve a regret of O(d3/2√T) after T rounds in the worst case. We also prove data-dependent bounds that improve on the basic result when the loss matrices of the environment have bounded rank or the loss of the best action is bounded. One version of our algorithm runs in O(d) time per trial which massively improves over every previously known online PCA method. We complement these results by a lower bound of Ω(d√T).