Tensors in statistical learning and combinatorial optimization

Nikos Sidiropoulos
Louis T. Rader Professor
University of Virginia
DCC 318
Wed, March 22, 2023 at 4:00 PM

In this talk, I will review recent work on the use of low-rank tensor models in multivariate probability, density estimation, supervised learning, and combinatorial optimization. We have recently shown that it is possible to learn high-order but low-rank multivariate distributions from low-order marginals, and that every multivariate categorical distribution can be generated by a (so-called) "naive" Bayes model. As it turns out, many real-life datasets can be fitted using distributions of very low rank. We have also proposed viewing sampling and supervised learning / system identification problems through the lens of low-rank tensor completion, which affords parsimonious modeling and sample-efficient learning with identification guarantees.  Our most recent work explores the interplay between tensors and combinatorial optimization: it shows that every NP-complete problem can be cast as an instance of computing the minimum element of a tensor from its (two) rank-one factors. This exemplifies the modeling power of very low-rank tensors, and it also opens the door to a continuous multilinear problem relaxation whose empirical performance on the classic partition problem and other combinatorial optimization problems appears to be promising.

N. Sidiropoulos is the Louis T. Rader Professor of Electrical and Computer Engineering at the University of Virginia. He earned his Ph.D. in Electrical Engineering from the University of Maryland–College Park, in 1992. He has served on the faculty of the University of Minnesota, and the Technical University of Crete, Greece. His research interests are in signal processing, communications, optimization, tensor decomposition, and factor analysis, with applications in machine learning and communications. He received the NSF/CAREER award in 1998, the IEEE Signal Processing Society (SPS) Best Paper Award in 2001, 2007, 2011, and 2023, and his students received four IEEE SPS conference best paper awards. Sidiropoulos has authored a Google Classic Paper in Signal Processing (on multicast beamforming), and his tutorial on tensor decomposition is ranked #1 in Google Scholar metrics for IEEE Transactions in Signal Processing (TSP), and tops the charts of the most popular / most frequently accessed TSP papers in IEEExplore. He served as IEEE SPS Distinguished Lecturer (2008-2009), Vice President of IEEE SPS (2017-2019), and as chair of the IEEE Fellow evaluation committee of SPS (2020-2021). He received the 2010 IEEE Signal Processing Society Meritorious Service Award, and the 2013 Distinguished Alumni Award from the ECE Department of the University of Maryland. He is a Fellow of IEEE (2009) and a Fellow of EURASIP (2014). He received the EURASIP Technical Achievement Award in 2022, and the IEEE SPS Claude Shannon - Harry Nyquist Technical Achievement Award in 2023. More information at http://www.ece.virginia.edu/~nds5j/ and https://scholar.google.com/citations?user=ZOkfkFMAAAAJ&hl=en