2026-07-17T15:43:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17153 2024-03-06T10:59:06Z ddc:004 open_access

Adaptive Sketches for Robust Regression with Importance Sampling Mahabadi, Sepideh Woodruff, David P. Zhou, Samson Streaming algorithms stochastic optimization importance sampling We introduce data structures for solving robust regression through stochastic gradient descent (SGD) by sampling gradients with probability proportional to their norm, i.e., importance sampling. Although SGD is widely used for large scale machine learning, it is well-known for possibly experiencing slow convergence rates due to the high variance from uniform sampling. On the other hand, importance sampling can significantly decrease the variance but is usually difficult to implement because computing the sampling probabilities requires additional passes over the data, in which case standard gradient descent (GD) could be used instead. In this paper, we introduce an algorithm that approximately samples T gradients of dimension d from nearly the optimal importance sampling distribution for a robust regression problem over n rows. Thus our algorithm effectively runs T steps of SGD with importance sampling while using sublinear space and just making a single pass over the data. Our techniques also extend to performing importance sampling for second-order optimization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sepideh Mahabadi and David P. Woodruff and Samson Zhou 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.31 urn:nbn:de:0030-drops-171531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.31 eng https://creativecommons.org/licenses/by/4.0/legalcode