Fetching the paper…
Reading the bibliography…
Given a matrix $A\in \mathbb{R}^{n\times d}$ and a vector $b\in \mathbb{R}^n$, we consider the regression problem with $\ell_\infty$ guarantees: finding a vector $x'\in \mathbb{R}^d$ such that $ \|x'-x^*\|_\infty \leq \frac{\epsilon}{\sqrt{d}}\cdot \|Ax^*-b\|_2\cdot \|A^\dagger\|$ where $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|_2$.
Über dyadische brüche
Aleksandr Khintchine · 1923
Earlier work this paper cites.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
A bound on tail probabilities for quadratic forms in independent random variables
David Lee Hanson and Farroll Tim Wright · 1971
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1996
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
Beatrice Laurent and Pascal Massart · 2000
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Earlier work this paper cites.
Improved analysis of the subsampled randomized hadamard transform
Joel A. Tropp · 2010
Earlier work this paper cites.
An Introduction to Heavy-Tailed and Subexponential Distributions
Sergey Foss, Dmitry Korshunov, and Stan Zachary · 2011
Earlier work this paper cites.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Earlier work this paper cites.
Faster ridge regression via the subsampled randomized hadamard transform
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar · 2013
Earlier work this paper cites.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Earlier work this paper cites.
Subspace embeddings for the polynomial kernel
Haim Avron, Huy Nguyen, and David Woodruff · 2014
Cited alongside, same era.
Path finding methods for linear programming: Solving linear programs in O ( r a n k ) {O}(\sqrt{rank}) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
David P Woodruff · 2014
Cited alongside, same era.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B Cohen · 2016
Cited alongside, same era.
Sublinear time orthogonal tensor decomposition
Zhao Song, David Woodruff, and Huan Zhang · 2016
Cited alongside, same era.
Fast regression with an ℓ ∞ \ell_{\infty} guarantee
Eric Price, Zhao Song, and David P Woodruff · 2017
Cited alongside, same era.
Training (overparametrized) neural networks in near-linear time
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein · 2021
Later among the works it cites.
A faster algorithm for solving general lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2021
Later among the works it cites.
Fast sketching of polynomial kernels of polynomial degree
Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang · 2021
Later among the works it cites.
Oblivious sketching-based central path method for solving linear programming problems
Zhao Song and Zheng Yu · 2021
Later among the works it cites.
Training multi-layer over-parametrized neural network in subquadratic time
Zhao Song, Lichen Zhang, and Ruizhe Zhang · 2021
Later among the works it cites.
Subquadratic kronecker regression with applications to tensor decomposition
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sketching for kronecker product regression and p-splines
Huaian Diao, Zhao Song, Wen Sun, and David Woodruff · 2018
Cited alongside, same era.
Optimal sketching for kronecker product regression and low rank approximation
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff · 2019
Cited alongside, same era.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Cited alongside, same era.
Relative error tensor low rank approximation
Zhao Song, David P Woodruff, and Peilin Zhong · 2019
Cited alongside, same era.
Oblivious sketching of high-degree polynomial kernels
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh · 2020
Cited alongside, same era.
Near input sparsity time kernel embeddings via adaptive sampling
David P Woodruff and Amir Zandieh · 2020
Cited alongside, same era.
Matthew Fahrbach, Thomas Fu, and Mehrdad Ghadiri · 2022
Later among the works it cites.
Dynamic tensor product regression
Aravind Reddy, Zhao Song, and Lichen Zhang · 2022
Later among the works it cites.
Accelerating frank-wolfe algorithm using low-dimensional and adaptive data structures
Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, and Lichen Zhang · 2022
Later among the works it cites.
Speeding up sparsification using inner product search data structures
Zhao Song, Zhaozhuo Xu, and Lichen Zhang · 2022
Later among the works it cites.
Leverage score sampling for tensor product matrices in input sparsity time
David Woodruff and Amir Zandieh · 2022
Later among the works it cites.
Optimal algorithms for linear algebra in the current matrix multiplication time
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, and Samson Zhou · 2023
Closest in time.
An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo · 2023
Closest in time.