Journal article
Stochastic Canonical Correlation Analysis
Journal of machine learning research, Vol.20, 167
10/01/2019
Abstract
We study the sample complexity of canonical correlation analysis (CCA), i.e., the number of samples needed to estimate the population canonical correlation and directions up to arbitrarily small error. With mild assumptions on the data distribution, we show that in order to achieve epsilon-suboptimality in a properly defined measure of alignment between the estimated canonical directions and the population solution, we can solve the empirical objective exactly with N(epsilon, Delta, gamma) samples, where Delta is the singular value gap of the whitened cross-covariance matrix and 1/gamma is an upper bound of the condition number of auto-covariance matrices. Moreover, we can achieve the same learning accuracy by drawing the same level of samples and solving the empirical objective approximately with a stochastic optimization algorithm; this algorithm is based on the shift-and-invert power iterations and only needs to process the dataset for O (log 1/c) passes. Finally, we show that, given an estimate of the canonical correlation, the streaming version of the shift-and-invert power iterations achieves the same learning accuracy with the same level of sample complexity, by processing the data only once.
Details
- Title: Subtitle
- Stochastic Canonical Correlation Analysis
- Creators
- Chao Gao - University of ChicagoDan Garber - Technion – Israel Institute of TechnologyNathan Srebro - Toyota Technol Inst, Chicago, IL 60637 USAJialei Wang - University of ChicagoWeiran Wang - Toyota Technol Inst, Chicago, IL 60637 USA
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.20, 167
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 46
- Grant note
- 1546462 / NSF BIGDATA
- Language
- English
- Date published
- 10/01/2019
- Academic Unit
- Computer Science
- Record Identifier
- 9984696723902771
Metrics
1 Record Views