Tata Institute of Fundamental Research
Fast Algorithms and Data Structures for Regression
STCS Seminar
Speaker:
Deeksha Adil (Institute for Theoretical Studies in ETH Zurich)
Organiser:
Jatin Batra
Date:
Monday, 9 Sep 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In this talk I will present state-of-the-art algorithms for $\ell_{\infty}$-norm regression. Our algorithms involve new techniques which combine acceleration algorithms with advanced data structures. In order to
do so, we propose a novel acceleration scheme for multiplicative weight update algorithms that exhibits stabiliy and robustness, which are required for the efficient implementations of the inverse maintenance data structures. Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.
Short Bio:
Deeksha Adil has been a Junior Fellow at the Institute for Theoretical Studies at ETH Zurich since January 2023. She focuses on designing fast algorithms with provable guarantees for problems in optimization, machine learning, and theoretical computer science. She completed a Ph.D. at the University of Toronto under the supervision of Sushant Sachdeva in August 2022 after which she was visiting the University of Michigan in the Fall of 2022. Prior to that, she earned a BS-MS in mathematics from the Indian Institute of Science Education and Research, Pune, in 2017.
| Speaker: | Deeksha Adil (Institute for Theoretical Studies in ETH Zurich) |
| Organiser: | Jatin Batra |
| Date: | Monday, 9 Sep 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In this talk I will present state-of-the-art algorithms for $\ell_{\infty}$-norm regression. Our algorithms involve new techniques which combine acceleration algorithms with advanced data structures. In order to
do so, we propose a novel acceleration scheme for multiplicative weight update algorithms that exhibits stabiliy and robustness, which are required for the efficient implementations of the inverse maintenance data structures. Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.
Short Bio:
Deeksha Adil has been a Junior Fellow at the Institute for Theoretical Studies at ETH Zurich since January 2023. She focuses on designing fast algorithms with provable guarantees for problems in optimization, machine learning, and theoretical computer science. She completed a Ph.D. at the University of Toronto under the supervision of Sushant Sachdeva in August 2022 after which she was visiting the University of Michigan in the Fall of 2022. Prior to that, she earned a BS-MS in mathematics from the Indian Institute of Science Education and Research, Pune, in 2017.