{"id":255615,"date":"2016-06-25T03:04:54","date_gmt":"2016-06-25T10:04:54","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&p=255615"},"modified":"2018-10-16T20:20:14","modified_gmt":"2018-10-17T03:20:14","slug":"streaming-pca-matching-matrix-bernstein-near-optimal-finite-sample-guarantees-ojas-algorithm","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/streaming-pca-matching-matrix-bernstein-near-optimal-finite-sample-guarantees-ojas-algorithm\/","title":{"rendered":"Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm"},"content":{"rendered":"

This work provides improved guarantees for streaming principle component analysis (PCA). Given A<\/span>1<\/span><\/span>,<\/span>\u2026<\/span>,<\/span>A<\/span>n<\/span><\/span>\u2208<\/span>R<\/span><\/span><\/span>d<\/span>\u00d7<\/span>d<\/span><\/span><\/span><\/span><\/span><\/span><\/span> sampled independently from distributions satisfying E<\/span><\/span><\/span>[<\/span>A<\/span>i<\/span><\/span>]<\/span>=<\/span>\u03a3<\/span><\/span><\/span><\/span> for \u03a3<\/span>\u2ab0<\/span>0<\/span><\/span><\/span><\/span><\/span><\/span>, this work provides an O<\/span>(<\/span>d<\/span>)<\/span><\/span><\/span><\/span>-space linear-time single-pass streaming algorithm for estimating the top eigenvector of \u03a3<\/span><\/span><\/span><\/span>. The algorithm nearly matches (and in certain cases improves upon) the accuracy obtained by the standard batch method that computes top eigenvector of the empirical covariance 1<\/span>n<\/span><\/span>\u2211<\/span>i<\/span>\u2208<\/span>[<\/span>n<\/span>]<\/span><\/span><\/span><\/span>A<\/span>i<\/span><\/span><\/span><\/span><\/span> as analyzed by the matrix Bernstein inequality. Moreover, to achieve constant accuracy, our algorithm improves upon the best previous known sample complexities of streaming algorithms by either a multiplicative factor of O<\/span>(<\/span>d<\/span>)<\/span><\/span><\/span><\/span> or 1<\/span>\/<\/span><\/span><\/span>g<\/span>a<\/span>p<\/span><\/span><\/span><\/span><\/span><\/span> where g<\/span>a<\/span>p<\/span><\/span><\/span><\/span><\/span><\/span> is the relative distance between the top two eigenvalues of \u03a3<\/span><\/span><\/span><\/span>.
\nThese results are achieved through a novel analysis of the classic Oja’s algorithm, one of the oldest and most popular algorithms for streaming PCA. In particular, this work shows that simply picking a random initial point w<\/span>0<\/span><\/span><\/span><\/span><\/span> and applying the update rule w<\/span>i<\/span>+<\/span>1<\/span><\/span><\/span><\/span>=<\/span>w<\/span>i<\/span><\/span>+<\/span>\u03b7<\/span>i<\/span><\/span>A<\/span>i<\/span><\/span>w<\/span>i<\/span><\/span><\/span><\/span><\/span> suffices to accurately estimate the top eigenvector, with a suitable choice of \u03b7<\/span>i<\/span><\/span><\/span><\/span><\/span>. We believe our result sheds light on how to efficiently perform streaming PCA both in theory and in practice and we hope that our analysis may serve as the basis for analyzing many variants and extensions of streaming PCA.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

This work provides improved guarantees for streaming principle component analysis (PCA). Given A1,\u2026,An\u2208Rd\u00d7d sampled independently from distributions satisfying E[Ai]=\u03a3 for \u03a3\u2ab00, this work provides an O(d)-space linear-time single-pass streaming algorithm for estimating the top eigenvector of \u03a3. The algorithm nearly matches (and in certain cases improves upon) the accuracy obtained by the standard batch method […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"Proceedings of The 29th Conference on Learning Theory (COLT)","msr_chapter":"","msr_edition":"Proceedings of The 29th Conference on Learning Theory (COLT)","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"Proceedings of The 29th Conference on Learning Theory (COLT)","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2016-06-25","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/arxiv.org\/abs\/1602.06929","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13556],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-255615","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-artificial-intelligence","msr-locale-en_us"],"msr_publishername":"","msr_edition":"Proceedings of The 29th Conference on Learning Theory (COLT)","msr_affiliation":"","msr_published_date":"2016-06-25","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"Proceedings of The 29th Conference on Learning Theory (COLT)","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"255636","msr_publicationurl":"http:\/\/arxiv.org\/abs\/1602.06929","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"JJKNS16_COLT","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/07\/JJKNS16_COLT.pdf","id":255636,"label_id":0},{"type":"url","title":"http:\/\/arxiv.org\/abs\/1602.06929","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/arxiv.org\/abs\/1602.06929"}],"msr-author-ordering":[{"type":"user_nicename","value":"prajain","user_id":33278,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=prajain"},{"type":"text","value":"Chi Jin","user_id":0,"rest_url":false},{"type":"text","value":"Sham Kakade","user_id":0,"rest_url":false},{"type":"text","value":"Praneeth Netrapalli","user_id":0,"rest_url":false},{"type":"text","value":"Aaron Sidford","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199562],"msr_event":[],"msr_group":[144924,144938,144940],"msr_project":[171330],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":171330,"post_title":"Provable Non-convex Optimization for Machine Learning Problems","post_name":"provable-non-convex-optimization-for-machine-learning-problems","post_type":"msr-project","post_date":"2014-04-04 06:19:02","post_modified":"2019-11-18 10:38:44","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/provable-non-convex-optimization-for-machine-learning-problems\/","post_excerpt":"We explore theoretical properties of simple non-convex optimization methods for problems that feature prominently in several important areas such as recommendation systems, compressive sensing, computer vision etc.","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171330"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/255615","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/255615\/revisions"}],"predecessor-version":[{"id":526899,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/255615\/revisions\/526899"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=255615"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=255615"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=255615"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=255615"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=255615"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=255615"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=255615"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=255615"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=255615"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=255615"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=255615"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=255615"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=255615"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}