Past Events

Qualifying Exam

Scalable machine learning algorithms for multi-armed bandits and correlation clustering


Download as iCal file

Tuesday, December 14, 2021, 03:00pm


Speaker: Chen Wang

Location : Via Zoom


Prof. Sepehr Assadi

Prof. Jie Gao

Prof. Peng Zhang

Prof. Mubbasir Kapadia

Event Type: Qualifying Exam

Abstract: Massive datasets appear frequently in modern machine learning applications. The situation poses a pressing challenge to design provably efficient large-scale learning algorithms. One of the most promising directions to tackle this challenge is to explore sublinear algorithms for machine learning, i.e. the algorithms that can work with resources substantially smaller than the size of the input they operate on. In this talk, I will discuss sublinear machine learning algorithms for two well-known problems, namely multi-armed bandits (MABs) and correlation clustering. For the multi-armed bandits problem, I will discuss the space efficiency for best-arm identification under the streaming model. The optimal sample complexity to identify the best arm has been known for almost two decades. However, not much was known about the space complexity of the algorithms. To study the space complexity, we introduced the streaming multi-armed bandits model. We proved that, perhaps surprisingly, there exists an algorithm that achieves the asymptotically optimal sample complexity and only uses a space of a single arm. More recently, we extended the results by showing several lower bounds that characterize the necessary assumptions for instance-sensitive sample complexity in streaming MABs. For the correlation clustering problem, I will discuss recent results on sublinear time and space algorithms. This, in particular, includes algorithms that can solve the problem quadratically faster than even reading the input -- assuming standard query access to the data -- or with quadratically smaller space than needed to store the input using a single-pass stream over the data.


Rutgers University School of Arts and Sciences

Contact  Prof. Sepehr Assadi