Deeksha Adil: Fast Algorithms for l_p-Regression and Other Problems

Regression in $\ell_p$-norms is a canonical problem in optimization, machine learning, and theoretical computer science. In this talk, I will describe our recent advances in developing fast, high-accuracy algorithms both in theory and practice. Our algorithms are based on a few novel techniques which I will go over briefly and are the fastest available both in theory and practice. Our algorithms for $\ell_p$-regression also imply fast algorithms for the p-norm flow problem and an $m^{1+o(1)}\epsilon^{-1}$ time algorithm for the maximum flow problem on unit capacity graphs, matching the best-known bounds for this problem.

I will further show how our techniques extend to obtain fast algorithms for a broader class, quasi-self-concordant functions which capture several important loss functions such as soft-max and logistic regression. As a result, we obtain the first unified width reduced multiplicative weights algorithm. Our rates match the ones obtained by explicit acceleration schemes for these problems thus suggesting a deeper connection between our techniques and standard acceleration schemes. I would finally end with some open directions.