Timezone: »
Poster
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
Huaian Diao · Rajesh Jayaram · Zhao Song · Wen Sun · David Woodruff
Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #53
We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Formally, given $A_i \in \R^{n_i \times d_i}$ for $i=1,2,\dots,q$ where $n_i \gg d_i$ for each $i$, and $b \in \R^{n_1 n_2 \cdots n_q}$, let $\mathcal{A} = A_i \otimes A_2 \otimes \cdots \otimes A_q$. Then for $p \in [1,2]$, the goal is to find $x \in \R^{d_1 \cdots d_q}$ that approximately minimizes $\|\mathcal{A}x - b\|_p$. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker product $\mathcal{A} \in \R^{n_1 \cdots n_q \times d_1 \cdots d_q}$. Specifically, for $p=2$ they achieve a running time of $O(\sum_{i=1}^q \texttt{nnz}(A_i) + \texttt{nnz}(b))$, where $ \texttt{nnz}(A_i)$ is the number of non-zero entries in $A_i$. Note that $\texttt{nnz}(b)$ can be as large as $\Theta(n_1 \cdots n_q)$. For $p=1,$ $q=2$ and $n_1 = n_2$, they achieve a worse bound of $O(n_1^{3/2} \text{poly}(d_1d_2) + \texttt{nnz}(b))$. In this work, we provide significantly faster algorithms. For $p=2$, our running time is $O(\sum_{i=1}^q \texttt{nnz}(A_i) )$, which has no dependence on $\texttt{nnz}(b)$. For $p<2$, our running time is $O(\sum_{i=1}^q \texttt{nnz}(A_i) + \texttt{nnz}(b))$, which matches the prior best running time for $p=2$. We also consider the related all-pairs regression problem, where given $A \in \R^{n \times d}, b \in \R^n$, we want to solve $\min_{x \in \R^d} \|\bar{A}x - \bar{b}\|_p$, where $\bar{A} \in \R^{n^2 \times d}, \bar{b} \in \R^{n^2}$ consist of all pairwise differences of the rows of $A,b$. We give an $O(\texttt{nnz}(A))$ time algorithm for $p \in[1,2]$, improving the $\Omega(n^2)$ time required to form $\bar{A}$. Finally, we initiate the study of Kronecker product low rank and and low-trank approximation. For input $\mathcal{A}$ as above, we give $O(\sum_{i=1}^q \texttt{nnz}(A_i))$ time algorithms, which is much faster than computing $\mathcal{A}$.
Author Information
Huaian Diao (Northeast Normal University)
Rajesh Jayaram (Carnegie Mellon University)
Zhao Song (UT-Austin)
Wen Sun (Microsoft Research NYC)
David Woodruff (Carnegie Mellon University)
More from the Same Authors
-
2023 Poster: Lower Bounds on Adaptive Sensing for Matrix Recovery »
Praneeth Kacham · David Woodruff -
2023 Poster: Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming »
Gregory Dexter · Petros Drineas · David Woodruff · Taisuke Yasuda -
2023 Poster: InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding »
Junda Wu · Tong Yu · Rui Wang · Zhao Song · Ruiyi Zhang · Handong Zhao · Chaochao Lu · Shuai Li · Ricardo Henao -
2023 Poster: Computing Approximate $\ell_p$ Sensitivities »
Swati Padmanabhan · David Woodruff · Richard Zhang -
2023 Poster: Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing »
Josh Alman · 杰昊 梁 · Zhao Song · Ruizhe Zhang · Danyang Zhuo -
2023 Poster: Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings »
Sudhanshu Chanpuriya · Ryan Rossi · Anup Rao · Tung Mai · Nedim Lipka · Zhao Song · Cameron Musco -
2023 Poster: H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models »
Zhenyu Zhang · Ying Sheng · Tianyi Zhou · Tianlong Chen · Lianmin Zheng · Ruisi Cai · Zhao Song · Yuandong Tian · Christopher Ré · Clark Barrett · Zhangyang Wang · Beidi Chen -
2023 Poster: Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products »
Tamas Sarlos · Xingyou Song · David Woodruff · Richard Zhang -
2023 Poster: Fast Attention Requires Bounded Entries »
Josh Alman · Zhao Song -
2023 Poster: On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds »
David Woodruff · Fred Zhang · Samson Zhou -
2023 Poster: Near-Optimal $k$-Clustering in the Sliding Window Model »
David Woodruff · Peilin Zhong · Samson Zhou -
2022 Spotlight: Optimal Query Complexities for Dynamic Trace Estimation »
David Woodruff · Fred Zhang · Richard Zhang -
2022 Poster: Optimal Query Complexities for Dynamic Trace Estimation »
David Woodruff · Fred Zhang · Richard Zhang -
2021 Poster: Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures »
Zhaozhuo Xu · Zhao Song · Anshumali Shrivastava -
2020 Poster: Learning the Linear Quadratic Regulator from Nonlinear Observations »
Zakaria Mhammedi · Dylan Foster · Max Simchowitz · Dipendra Misra · Wen Sun · Akshay Krishnamurthy · Alexander Rakhlin · John Langford -
2020 Poster: Constrained episodic reinforcement learning in concave-convex and knapsack settings »
Kianté Brantley · Miro Dudik · Thodoris Lykouris · Sobhan Miryoosefi · Max Simchowitz · Aleksandrs Slivkins · Wen Sun -
2019 Poster: Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels »
Michela Meister · Tamas Sarlos · David Woodruff -
2019 Poster: Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss »
Zhao Song · David Woodruff · Peilin Zhong -
2019 Poster: Provable Non-linear Inductive Matrix Completion »
Kai Zhong · Zhao Song · Prateek Jain · Inderjit Dhillon -
2019 Poster: Policy Poisoning in Batch Reinforcement Learning and Control »
Yuzhe Ma · Xuezhou Zhang · Wen Sun · Jerry Zhu -
2019 Poster: Efficient and Thrifty Voting by Any Means Necessary »
Debmalya Mandal · Ariel Procaccia · Nisarg Shah · David Woodruff -
2019 Poster: Regularized Weighted Low Rank Approximation »
Frank Ban · David Woodruff · Richard Zhang -
2019 Oral: Efficient and Thrifty Voting by Any Means Necessary »
Debmalya Mandal · Ariel Procaccia · Nisarg Shah · David Woodruff -
2019 Poster: Total Least Squares Regression in Input Sparsity Time »
Huaian Diao · Zhao Song · David Woodruff · Xin Yang -
2019 Poster: Towards a Zero-One Law for Column Subset Selection »
Zhao Song · David Woodruff · Peilin Zhong -
2018 Poster: Robust Subspace Approximation in a Stream »
Roie Levin · Anish Prasad Sevekari · David Woodruff -
2018 Spotlight: Robust Subspace Approximation in a Stream »
Roie Levin · Anish Prasad Sevekari · David Woodruff -
2018 Poster: On Coresets for Logistic Regression »
Alexander Munteanu · Chris Schwiegelshohn · Christian Sohler · David Woodruff -
2018 Spotlight: On Coresets for Logistic Regression »
Alexander Munteanu · Chris Schwiegelshohn · Christian Sohler · David Woodruff -
2018 Poster: Sublinear Time Low-Rank Approximation of Distance Matrices »
Ainesh Bakshi · David Woodruff -
2018 Spotlight: Sublinear Time Low-Rank Approximation of Distance Matrices »
Ainesh Bakshi · David Woodruff