Randomized Iterative Algorithms for Fisher Discriminant Analysis

Agniva Chowdhury, Jiasen Yang, Petros Drineas

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations

Abstract

Fisher discriminant analysis (FDA) is a widely used method for classification and dimensionality reduction. When the number of predictor variables greatly exceeds the number of observations, one of the alternatives for conventional FDA is regularized Fisher discriminant analysis (RFDA). In this paper, we present a simple, iterative, sketching-based algorithm for RFDA that comes with provable accuracy guarantees when compared to the conventional approach. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. We analyze the behavior of RFDA when leverage scores and ridge leverage scores are used to select predictor variables, and prove that accurate approximations can be achieved by a sample whose size depends on the effective degrees of freedom of the RFDA problem. Our results yield significant improvements over existing approaches and our empirical evaluations support our theoretical analyses.

Original languageEnglish
Pages (from-to)239-249
Number of pages11
JournalProceedings of Machine Learning Research
Volume115
StatePublished - 2019
Externally publishedYes
Event35th Uncertainty in Artificial Intelligence Conference, UAI 2019 - Tel Aviv, Israel
Duration: Jul 22 2019Jul 25 2019

Funding

Acknowledgements. We thank the anonymous reviewers for their helpful comments. AC and PD were supported by NSF grants IIS-1661760, IIS-1661756, CCF-1814041, and DMS-1760353. JY was supported by NSF grants IIS-1618690, IIS-1546488, and CCF-0939370.

FundersFunder number
National Science FoundationCCF-0939370, IIS-1546488, IIS-1661760, CCF-1814041, IIS-1618690, DMS-1760353, IIS-1661756

    Fingerprint

    Dive into the research topics of 'Randomized Iterative Algorithms for Fisher Discriminant Analysis'. Together they form a unique fingerprint.

    Cite this