Past Events
Qualifying ExamScalable machine learning algorithms for multi-armed bandits and correlation clustering |
|
||
Tuesday, December 14, 2021, 03:00pm |
|||
Speaker: Chen Wang
Location : Via Zoom
Committee:
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.
Organization:
Rutgers University School of Arts and Sciences
Contact Prof. Sepehr Assadi