Abstract: The problem of solving weighted logistic regression in the scalable machine learning setting is as follows: given n data points and an objective classification function F, the goal is to find a subset of m << n data points along with a corresponding set of weights for which minimizing F on those points would yield a near minimizer over the entire dataset. Most works on logistic regression study coresets as a data reduction method, but these require at least two passes over the data which add into the space overhead and update time. The advantage of using data oblivious sketching algorithms over coresets to solve this problem is that these methods require only one pass over the data stream and the sketches can be updated in the most flexible dynamic setting, referred to as the turnstile model. In my talk I will present the results of the paper "Oblivious Sketching for Logistic Regression" by Munteanu, Omlor, Woodruff (2021) in which the authors propose a sketch that reduces the size of a d-dimensional dataset of n points to poly(md log(n)) points yielding an O(log n) approximation to the original problem, where m is a parameter that captures the complexity of compressing the data.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.