Timezone: »

Adaptive Sketching for Fast and Convergent Canonical Polyadic Decomposition
Alex Gittens · Kareem Aggour · Bülent Yener

Wed Jul 15 12:00 PM -- 12:45 PM & Thu Jul 16 01:00 AM -- 01:45 AM (PDT) @ Virtual

This work considers the canonical polyadic decomposition (CPD) of tensors using proximally regularized sketched alternating least squares algorithms. First, it establishes a sublinear rate of convergence for proximally regularized sketched CPD algorithms under two natural conditions that are known to be satisfied by many popular forms of sketching. Second, it demonstrates that the iterative nature of CPD algorithms can be exploited algorithmically to choose more performant sketching rates. This is accomplished by introducing CPD-MWU, a proximally-regularized sketched alternating least squares algorithm that adaptively selects the sketching rate at each iteration. On both synthetic and real data we observe that for noisy tensors CPD-MWU produces decompositions of comparable accuracy to the standard CPD decomposition in less time, often half the time; for ill-conditioned tensors, given the same time budget, CPD-MWU produces decompositions with an order-of-magnitude lower relative error. For a representative real-world dataset CPD-MWU produces residual errors on average 20% lower than CPRAND-MIX and 44% lower than SPALS, two recent sketched CPD algorithms.

Author Information

Alex Gittens (Rensselaer Polytechnic Institute)

Alex Gittens's research focuses on using randomization to reduce the computational costs of extracting information from large datasets. His work lies at the intersection of randomized algorithms, numerical linear algebra, high-dimensional probability, and machine learning.

Kareem Aggour (GE Research)
Bülent Yener (Rensselaer Polytechnic Institute)

More from the Same Authors