`

Timezone: »

 
Poster
SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling
Dehua Cheng · Richard Peng · Yan Liu · Kimis Perros

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #126 #None

Tensor CANDECOMP/PARAFAC (CP) decomposition is a powerful but computationally challenging tool in modern data analytics. In this paper, we show ways of sampling intermediate steps of alternating minimization algorithms for computing low rank tensor CP decompositions, leading to the sparse alternating least squares (SPALS) method. Specifically, we sample the the Khatri-Rao product, which arises as an intermediate object during the iterations of alternating least squares. This product captures the interactions between different tensor modes, and form the main computational bottleneck for solving many tensor related tasks. By exploiting the spectral structures of the matrix Khatri-Rao product, we provide efficient access to its statistical leverage scores. When applied to the tensor CP decomposition, our method leads to the first algorithm that runs in sublinear time per-iteration and approximates the output of deterministic alternating least squares algorithms. Empirical evaluations of this approach show significantly speedups over existing randomized and deterministic routines for performing CP decomposition. On a tensor of the size 2.4m by 6.6m by 92k with over 2 billion nonzeros formed by Amazon product reviews, our routine converges in two minutes to the same error as deterministic ALS.

Author Information

Dehua Cheng (Univ. of Southern California)
Richard Peng (Georgia Tech)
Yan Liu (University of Southern California)
Kimis Perros (Georgia Institute of Technology)

More from the Same Authors

  • 2021 Poster: VigDet: Knowledge Informed Neural Temporal Point Process for Coordination Detection on Social Media »
    Yizhou Zhang · Karishma Sharma · Yan Liu
  • 2020 Poster: A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices »
    Jiezhong Qiu · Chi Wang · Ben Liao · Richard Peng · Jie Tang
  • 2020 Poster: Multi-agent Trajectory Prediction with Fuzzy Query Attention »
    Nitin Kamra · Hao Zhu · Dweep Kumarbhai Trivedi · Ming Zhang · Yan Liu
  • 2020 Poster: How does This Interaction Affect Me? Interpretable Attribution for Feature Interactions »
    Michael Tsang · Sirisha Rambhatla · Yan Liu
  • 2019 Workshop: Learning with Temporal Point Processes »
    Manuel Rodriguez · Le Song · Isabel Valera · Yan Liu · Abir De · Hongyuan Zha
  • 2019 Poster: Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression »
    Deeksha Adil · Richard Peng · Sushant Sachdeva
  • 2018 : Lunch »
    Hong Yu · Bhanu Pratap Singh Rawat · Arijit Ukil · Waheeda Saib · Jekaterina Novikova · John Hughes · Yuhui Zhang · Rahul V · Mi Jung Kim · Babak Taati · Hariharan Ravishankar · Harry Clifford · Hirofumi Kobayashi · Babak Taati · Keyang Xu · Yen-Chi Cheng · Timothy Cannings · Jayashree Kalpathy-Cramer · Jayashree Kalpathy-Cramer · Parinaz Sobhani · Kimis Perros · Wei-Hung Weng · Yordan Raykov · Lars Lorch · Mengqi Jin · Xue Teng · Michael Ferlaino · Marek Rei · Cédric Beaulac · Aman Verma · Sebastian Keller · Eddie Cunningham · Luc Evers · Victor Rodriguez · Vipul Satone · Dianbo Liu · Angeline Yasodhara · Geoff Tison · Ligin Solamen · Bryan He · Rahul Ladhania · Yipeng Shi · Nafiz Hamid · Pouria Mashouri · Woochan Hwang · Sejin Park · Xu Chen · Rachneet Kaur · Davis Blalock · Holly Wiberg · Parminder Bhatia · Kezi Yu · RUMENG LI · Jun Sakuma · Charles Ding · Aaron Babier · Yong Cai · Abhi Pratap · Luke O'Connor · Allen Nie · Martin Kang · Ian Covert · Xun Wang · Alan Luo · Serena Yeung · Willie Boag · Kazuki Tachikawa · Mary Saltz · Owen Lahav · Edward Lee · Eric Teasley · Michael Kamp · Nirmesh Patel · Vishwali Mhasawade · Maxim Samarin · Ryo Uchimido · Farzad Khalvati · Francisco Cruz · Laura Symul · Zaid Nabulsi · Mads Mihailescu · Rosalind Picard
  • 2018 Poster: Neural Interaction Transparency (NIT): Disentangling Learned Interactions for Improved Interpretability »
    Michael Tsang · Hanpeng Liu · Sanjay Purushotham · Pavankumar Murali · Yan Liu
  • 2017 : Posters 1 »
    J.P. Lewis · Housam Khalifa Bashier Babiker · Zhongang Qi · Laura Rieger · Ning Xie · Filip Dabek · KOUSHIK NAGASUBRAMANIAN · Bolei Zhou · Dieuwke Hupkes · CHUN-HAO CHANG · Pamela K Douglas · Enea Ceolini · Derek Doran · Yan Liu · Fuxin Li · Randy Goebel
  • 2017 : Coffee break and Poster Session I »
    Nishith Khandwala · Steve Gallant · Greg Way · Aniruddh Raghu · Li Shen · Aydan Gasimova · Alican Bozkurt · Willie Boag · Daniel Lopez-Martinez · Ulrich Bodenhofer · Samaneh Nasiri GhoshehBolagh · Michelle Guo · Christoph Kurz · Kirubin Pillay · Kimis Perros · George H Chen · Alexandre Yahi · Madhumita Sushil · Sanjay Purushotham · Elena Tutubalina · Tejpal Virdi · Marc-Andre Schulz · Samuel Weisenthal · Bharat Srikishan · Petar Veličković · Kartik Ahuja · Andrew Miller · Erin Craig · Disi Ji · Filip Dabek · Chloé Pou-Prom · Hejia Zhang · Janani Kalyanam · Wei-Hung Weng · Harish Bhat · Hugh Chen · Simon Kohl · Mingwu Gao · Tingting Zhu · Ming-Zher Poh · Iñigo Urteaga · Antoine Honoré · Alessandro De Palma · Maruan Al-Shedivat · Pranav Rajpurkar · Matthew McDermott · Vincent Chen · Yanan Sui · Yun-Geun Lee · Li-Fang Cheng · David Fang · Sibt Hussain · Cesare Furlanello · Zeev Waks · Hiba Chougrad · Hedvig Kjellstrom · Finale Doshi-Velez · Wolfgang Fruehwirt · Yanqing Zhang · Lily Hu · Junfang Chen · Sunho Park · Gatis Mikelsons · Jumana Dakka · Stephanie Hyland · yann chevaleyre · Hyunwoo Lee · Xavi Giro-i-Nieto · David Kale · Mike Hughes · Gabriel Erion · Rishab Mehra · William Zame · Stojan Trajanovski · Prithwish Chakraborty · Kelly Peterson · Muktabh Srivastava · Amy Jin · Helio Tejeda Lemus · Priyadip Ray · Tamas Madl · Joe Futoma · Enhao Gong · Syed Rameel Ahmad · Eric Lei · Ferdinand Legros
  • 2016 Workshop: Learning with Tensors: Why Now and How? »
    Anima Anandkumar · Rong Ge · Yan Liu · Maximilian Nickel · Rose Yu
  • 2016 Poster: Learning Influence Functions from Incomplete Observations »
    Xinran He · Ke Xu · David Kempe · Yan Liu
  • 2014 Poster: Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning »
    Mohammad Taha Bahadori · Rose Yu · Yan Liu
  • 2014 Spotlight: Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning »
    Mohammad Taha Bahadori · Rose Yu · Yan Liu