Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis

DOI10.48550/ARXIV.1705.07194arXiv1705.07194OpenAlexW2617985792MaRDI QIDQ97534FDOQ97534

Summer Atkins, Gudmundur Einarsson, Brendan Ames, Line Clemmensen, Gudmundur Einarsson, Line Clemmensen, Summer Atkins, Brendan P. W. Ames

Publication date: 19 May 2017

Published in: Advances in Data Analysis and Classification. ADAC (Search for Journal in Brave)

Abstract: Linear discriminant analysis (LDA) is a classical method for dimensionality reduction, where discriminant vectors are sought to project data to a lower dimensional space for optimal separability of classes. Several recent papers have outlined strategies for exploiting sparsity for using LDA with high-dimensional data. However, many lack scalable methods for solution of the underlying optimization problems. We propose three new numerical optimization schemes for solving the sparse optimal scoring formulation of LDA based on block coordinate descent, the proximal gradient method, and the alternating direction method of multipliers. We show that the per-iteration cost of these methods scales linearly in the dimension of the data provided restricted regularization terms are employed, and cubically in the dimension of the data in the worst case. Furthermore, we establish that if our block coordinate descent framework generates convergent subsequences of iterates, then these subsequences converge to the stationary points of the sparse optimal scoring problem. We demonstrate the effectiveness of our new methods with empirical results for classification of Gaussian data and data sets drawn from benchmarking repositories, including time-series and multispectral X-ray data, and provide Matlab and R implementations of our optimization schemes.

Full work available at URL: https://arxiv.org/abs/1705.07194

zbMATH Keywords

alternating direction method of multipliersoptimal scoringproximal gradient methodsparse discriminant analysis

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Generalized linear models (logistic models) (62J12) Nonconvex programming, global optimization (90C26)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Penalized Classification using Fisher’s Linear Discriminant
• The elements of statistical learning. Data mining, inference, and prediction
• Multiclass Sparse Discriminant Analysis
• Least angle regression. (With discussion)
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Regularization and Variable Selection Via the Elastic Net
• Title not available (Why is that?)
• High-dimensional classification using features annealed independence rules
• Spatial variation. 2nd ed
• Smooth minimization of non-smooth functions
• Class prediction by nearest shrunken centroids, with applications to DNA microarrays.
• Penalized discriminant analysis
• Adaptive restart for accelerated gradient schemes
• On the global and linear convergence of the generalized alternating direction method of multipliers
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• A direct approach to sparse discriminant analysis in ultra-high dimensions
• A Direct Estimation Approach to Sparse Linear Discriminant Analysis
• Title not available (Why is that?)
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Gradient methods for minimizing composite functions
• Fast alternating linearization methods for minimizing the sum of two convex functions
• Flexible Discriminant Analysis by Optimal Scoring
• First-Order Methods in Optimization
• Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sparse linear discriminant analysis by thresholding for high dimensional data
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis

Cited In (4)

• Prediction and estimation consistency of sparse multi-class penalized optimal scoring
• Robust and sparse multigroup classification by the optimal scoring approach
• accSDA
• Title not available (Why is that?)

   Recommendations

• Sparse sufficient dimension reduction using optimal scoring 👍 👎
• Sparse discriminant analysis based on estimation of posterior probabilities 👍 👎
• Projection algorithms for nonconvex minimization with application to sparse principal component analysis 👍 👎
• Proximal methods for hierarchical sparse coding 👍 👎
• Sparse semiparametric discriminant analysis 👍 👎
• A direct approach to sparse discriminant analysis in ultra-high dimensions 👍 👎
• Sparse optimal discriminant clustering 👍 👎
• Asymptotic Optimality of Sparse Linear Discriminant Analysis with Arbitrary Number of Classes 👍 👎
• A convex optimization approach to high-dimensional sparse quadratic discriminant analysis 👍 👎

This page was built for publication: Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q97534)