Randomized Iterative Algorithms for Fisher Discriminant Analysis

Agniva Chowdhury, Jiasen Yang, Petros Drineas
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:239-249, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-chowdhury20a, title = {Randomized Iterative Algorithms for Fisher Discriminant Analysis}, author = {Chowdhury, Agniva and Yang, Jiasen and Drineas, Petros}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {239--249}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/chowdhury20a/chowdhury20a.pdf}, url = {https://proceedings.mlr.press/v115/chowdhury20a.html}, 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.} }
Endnote
%0 Conference Paper %T Randomized Iterative Algorithms for Fisher Discriminant Analysis %A Agniva Chowdhury %A Jiasen Yang %A Petros Drineas %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-chowdhury20a %I PMLR %P 239--249 %U https://proceedings.mlr.press/v115/chowdhury20a.html %V 115 %X 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.
APA
Chowdhury, A., Yang, J. & Drineas, P.. (2020). Randomized Iterative Algorithms for Fisher Discriminant Analysis. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:239-249 Available from https://proceedings.mlr.press/v115/chowdhury20a.html.

Related Material