Title: Quantum algorithms for the pathwise Lasso
Speaker: Dr. Tushar Vaidya
Date and time: 03 March 2025 (Monday), 11:30 a.m. – 12:30 p.m.
Venue: IEOR Seminar Room
Abstract: We propose a quantum algorithm for high-dimensional linear regression with an ℓ₁-penalty that builds on the classical LARS (Least Angle Regression) method. Our approach computes the entire regularisation path as the penalty changes, but it runs quadratically faster per iteration under certain conditions. By using Dürr and Høyer's quantum minimum-finding routine, we obtain a quadratic speedup in the number of features. We further enhance our method with an approximate quantum minimum-finding technique, achieving quadratic improvements in both the number of features and the number of observations. Additionally, we establish lower bounds and develop dequantized versions of these algorithms, which could be valuable for practitioners working with large-scale high-dimensional data sets. Quantum technicalities will be kept to a minimum to appeal to a wider mathematical audience.
Bio: Dr. Tushar Vaidya is a research fellow in quantum computing at Nanyang Technological University, Singapore. With a solid background in quantitative finance—having worked as a trader and quantitative strategist in fixed income derivatives—he brings practical industry insights to his academic pursuits. His current research encompasses algebraic AI and quantum algorithms for tackling fundamental problems in machine learning. His work includes using algebraic geometry to solve puzzles and employing probability theory to address new challenges in social networks of traders. The thrust of his work lies in the development of mathematical techniques drawn from both algebra and analysis.