Timezone: »
We consider the problem of factorizing a structured 3-way tensor into its constituent Canonical Polyadic (CP) factors. This decomposition, which can be viewed as a generalization of singular value decomposition (SVD) for tensors, reveals how the tensor dimensions (features) interact with each other. However, since the factors are a priori unknown, the corresponding optimization problems are inherently non-convex. The existing guaranteed algorithms which handle this non-convexity incur an irreducible error (bias), and only apply to cases where all factors have the same structure. To this end, we develop a provable algorithm for online structured tensor factorization, wherein one of the factors obeys some incoherence conditions, and the others are sparse. Specifically we show that, under some relatively mild conditions on initialization, rank, and sparsity, our algorithm recovers the factors exactly (up to scaling and permutation) at a linear rate. Complementary to our theoretical results, our synthetic and real-world data evaluations showcase superior performance compared to related techniques.
Author Information
Sirisha Rambhatla (University of Southern California)
Xingguo Li (Princeton University)
Jarvis Haupt (University of Minnesota)
More from the Same Authors
-
2021 Affinity Workshop: WiML Workshop 4 »
Soomin Aga Lee · Meera Desai · Nezihe Merve Gürel · Boyi Li · Linh Tran · Akiko Eriguchi · Jieyu Zhao · Salomey Osei · Sirisha Rambhatla · Geeticka Chauhan · Nwamaka (Amaka) Okafor · Mariya Vasileva -
2021 Affinity Workshop: WiML Workshop 3 »
Soomin Aga Lee · Meera Desai · Nezihe Merve Gürel · Boyi Li · Linh Tran · Akiko Eriguchi · Jieyu Zhao · Salomey Osei · Sirisha Rambhatla · Geeticka Chauhan · Nwamaka (Amaka) Okafor · Mariya Vasileva -
2021 Affinity Workshop: WiML Workshop 2 »
Soomin Aga Lee · Meera Desai · Nezihe Merve Gürel · Boyi Li · Linh Tran · Akiko Eriguchi · Jieyu Zhao · Salomey Osei · Sirisha Rambhatla · Geeticka Chauhan · Nwamaka (Amaka) Okafor · Mariya Vasileva -
2021 Affinity Workshop: WiML Workshop 1 »
Soomin Aga Lee · Meera Desai · Nezihe Merve Gürel · Boyi Li · Linh Tran · Akiko Eriguchi · Jieyu Zhao · Salomey Osei · Sirisha Rambhatla · Geeticka Chauhan · Nwamaka (Amaka) Okafor · Mariya Vasileva -
2020 Poster: Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality »
Yi Zhang · Orestis Plevrakis · Simon Du · Xingguo Li · Zhao Song · Sanjeev Arora -
2020 Poster: How does This Interaction Affect Me? Interpretable Attribution for Feature Interactions »
Michael Tsang · Sirisha Rambhatla · Yan Liu -
2019 Poster: ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization »
Xiangyi Chen · Sijia Liu · Kaidi Xu · Xingguo Li · Xue Lin · Mingyi Hong · David Cox -
2017 Poster: Near Optimal Sketching of Low-Rank Tensor Regression »
Xingguo Li · Jarvis Haupt · David Woodruff -
2017 Poster: On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning »
Xingguo Li · Lin Yang · Jason Ge · Jarvis Haupt · Tong Zhang · Tuo Zhao