Thesis Defense - Lichen Zhang
· Building 32, 32-G575 · Cambridge
Other
Speaker: Lichen Zhang Title: Provably Efficient Algorithms for Classical and Modern Machine Learning Abstract: Modern machine learning relies largely on efficient heuristics without provable guarantees, while provable algorithms are often slow or depend on unrealistic assumptions. In this thesis, we design algorithms for machine learning problems that are both efficient and provably correct, using tools from randomized linear algebra, continuous optimization, differential privacy and quantum computing. We start with two classical problems: support vector machines and matrix completion. We train linear support vector machines to high accuracy in time nearly linear in the number of data points, where previous high-accuracy methods took superlinear time. For matrix completion, the problem behind recommender systems, we show that alternating minimization, the method used in practice, still converges when each step is solved only approximately, so it runs in nearly the time it takes to verify an answer. We then turn to modern settings. Learning algorithms often query randomized data structures, such as nearest neighbor indexes, with queries that depend on earlier answers. Using differential privacy, we make such data structures robust to these adaptive queries with far fewer independent copies than before. Finally, we give a quantum algorithm that builds coresets, which are small weighted summaries of large data sets, while querying only a sublinear number of points, and we show that this number of queries is essentially optimal for generic sensitivity sampling. Zoom Link: https://mit.zoom.us/j/8587512838
Tickets & details
Plans change. We refresh listings once a day, so check with the venue or organizer before you go, especially for anything outdoors. More in the FAQ.