Fetching the paper…
Reading the bibliography…
We settle the complexity of dynamic least-squares regression (LSR), where rows and labels $(\mathbf{A}^{(t)}, \mathbf{b}^{(t)})$ can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an $\epsilon$-approximate solution to $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)} \mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$.
Some theorems in least squares
R. L. Plackett · 1950
Earlier work this paper cites.
Methods of conjugate gradients for solving linear systems
Magnus R Hestenes, Eduard Stiefel, et al · 1952
Earlier work this paper cites.
A new approach to linear filtering and prediction problems
Rudolph Emil Kalman · 1960
Earlier work this paper cites.
Contributions to the Theory of Linear Least Maximum Approximation /
Charles Lawrence Lawson · 1961
Earlier work this paper cites.
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
On tail probabilities for martingales
David A Freedman · 1975
Earlier work this paper cites.
Theory and application of digital signal processing
Lawrence R Rabiner and Bernard Gold · 1975
Earlier work this paper cites.
Multivariate analysis
Nick Martin and Hermine Maes · 1979
Earlier work this paper cites.
Gauss and the Invention of Least Squares
Stephen M. Stigler · 1981
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Estimation, control, and the discrete kalman filter (donald e. calin)
Charles K. Chui · 1990
Earlier work this paper cites.
Rounding errors in algebraic processes
James Hardy Wilkinson · 1994
Earlier work this paper cites.
Support-vector networks
Corinna Cortes and Vladimir Vapnik · 1995
Earlier work this paper cites.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction
Trevor Hastie, Jerome H. Friedman, and Robert Tibshirani · 2001
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Approximate nearest neighbors and the fast johnson-lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth L Clarkson and David P Woodruff · 2009
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
User-friendly tail bounds for matrix martingales
Joel A Tropp · 2011
Earlier work this paper cites.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Earlier work this paper cites.
How robust are linear sketches to adaptive inputs?
Moritz Hardt and David P Woodruff · 2013
Earlier work this paper cites.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Madry · 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.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Cited alongside, same era.
Path finding methods for linear programming: Solving linear programs in O ~ ( rank ) \widetilde{O}(\sqrt{\mathrm{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.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Cited alongside, same era.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak · 2019
Later among the works it cites.
Algorithms and hardness for linear algebra on geometric graphs
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song · 2020
Later among the works it cites.
Near optimal linear algebra in the online and sliding window models
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P Woodruff, and Samson Zhou · 2020
Later among the works it cites.
Solving tall dense linear programs in nearly linear time
van den Jan Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song · 2020
Later among the works it cites.
Online row sampling
Michael B Cohen, Cameron Musco, and Jakub Pachocki · 2020
Later among the works it cites.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak · 2015
Cited alongside, same era.
On the hardness of partially dynamic graph problems and connections to diameter
Søren Dahlgaard · 2016
Cited alongside, same era.
Faster kernel ridge regression using sketching and preconditioning
Haim Avron, Kenneth L Clarkson, and David P Woodruff · 2017
Cited alongside, same era.
On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt · 2017
Cited alongside, same era.
Answering conjunctive queries under updates
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt · 2017
Cited alongside, same era.
Hashing-based-estimators for kernel density in high dimensions
Moses Charikar and Paris Siminelakis · 2017
Cited alongside, same era.
Low-rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2017
Cited alongside, same era.
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Stoc 2021 workshop: Robust streaming, sketching, and sampling, 2021
Omri Ben-Eliezer, Rajesh Jayaram, and Uri Stemmer · 2021
Later among the works it cites.
Adversarial robustness of streaming algorithms through importance sampling
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou · 2021
Later among the works it cites.
Minimum cost flows, mdps, and ℓ 1 \ell_{1} -regression in nearly linear time for dense instances
van den Jan Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2021
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B Cohen, Yin Tat Lee, and Zhao Song · 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.
Algorithms and hardness for multidimensional range updates and queries
Joshua Lau and Angus Ritossa · 2021
Later among the works it cites.
A very sketchy talk (invited talk)
David Woodruff · 2021
Later among the works it cites.
Worst-case to average-case reductions via additive combinatorics
Vahid R Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar · 2022
Closest in time.
A framework for adversarially robust streaming algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev · 2022
Closest in time.
On the robustness of countsketch to adaptive inputs
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer · 2022
Closest in time.
Memory bounds for continual learning
Xi Chen, Christos Papadimitriou, and Binghui Peng · 2022
Closest in time.
Adversarially robust streaming algorithms via differential privacy
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer · 2022
Closest in time.
Hardness self-amplification from feasible hard-core sets
Shuichi Hirahara and Nobutaka Shimizu · 2022
Closest in time.
Tight dynamic problem lower bounds from generalized bmm and omv
Ce Jin and Yinzhan Xu · 2022
Closest in time.
Tight bounds for adversarially robust streams and sliding windows via difference estimators
David P Woodruff and Samson Zhou · 2022
Closest in time.
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.