{"success":1,"msg":"","color":"rgb(28, 35, 49)","title":"Streaming k-PCA and concentration for random matrix products<\/b>","description":"webinar","title2":"","start":"2021-03-25 17:00","end":"2021-03-25 18:00","responsable":"Giacomo Zanella <\/i><\/a>","speaker":"Jonathan Niles-Weed (New York University)","id":"32","type":"webinar","timezone":"Europe\/Rome","activity":"Zoom information:\r\nJoin the webinar here: https:\/\/zoom.us\/j\/93067920710\r\nMeeting ID: 930 6792 0710\r\nPasscode: 488949","abstract":"We analyze a non-convex stochastic descent algorithm for streaming PCA due to Erkki Oja (1982). Despite its simplicity, this algorithm has resisted optimal analysis outside of the rank-one case. We show that given access to a sequence of i.i.d. d x d symmetric matrices, Oja's algorithm obtains an accurate approximation to the subspace of the top k eigenvalues of their expectation using a number of samples scaling polylogarithmically in d. This matches the performance of an optimal offline algorithm for the same problem.\r\n\r\nOur analysis is based on new concentration results for products of random matrices, which allow us to obtain strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution. The argument relies on the optimal uniform smoothness properties of the Schatten trace class obtained by Ball, Carlen, and Lieb.\r\n\r\nReference: \r\nBased on joint work with Huang, Tropp, and Ward."}