CS Paper Radar

Structure and Regularization of Fused Objectives in Kernel Discriminant Analysis for Small-Sample-Size Problems

Lingxiao Qu, Yan Pei

cs.LG ·submitted 2026-09-09 09:08 UTC · v2

Abstract

When the number of training samples is smaller than the dimension, discriminant analysis faces a singular within-class scatter matrix, and fused objectives that combine the total variance C, the between-class scatter S_b and the within-class scatter S_w are one way to handle it. Using the seven variants of Kernelized Linear Principal Component Discriminant Analysis (KLPCDA) as a platform, we derive the structure of such objectives in this small-sample-size (SSS) setting. The training projections split into a class-mean part and a within-class part, the two scatter operators satisfy WB = 0, and all between-class information lies in the null space of S_w. A single fusion coefficient therefore cannot change the solution, and the variants, KPCA, the regularized kernel Fisher discriminant and the null space methods lie on the boundary of one family with two parameters, the fusion ratio t and a ridge parameter mu. On six tasks from five application domains, the regularized members were more accurate than the best of the seven variants chosen on validation data on all six tasks, by 0.8 to 5.7 points, also under added noise, whereas the fusion ratio gave no gain, including in controlled experiments on dimension ratio, class imbalance and class separation. Selecting a variant per task could gain less than one point, while a fixed choice made on other tasks transferred to every held-out task. The analysis thus gives a principled default for SSS kernel discriminant analysis, with diagnostic quantities, the null space dimension and the class-size spectrum, that can be computed before training.

Comment
Revised version. Supplementary material merged into the main file

Closest papers

Nearest neighbours by meaning across the whole index.

A Functional SVD Framework for Regularized Multivariate Functional PCA with Dual Penalization

cs.LG stat.MLstat.ME ·2026-09-13 ·Yue Zhao, Hossein Haghbin, Rebecca Sanders, Mehdi Maadooliat
similarity 0.60
Abstract

This paper introduces a novel framework for Regularized Multivariate Functional Principal Component Analysis (ReMFPCA) via Functional Singular Value Decomposition (SVD). The proposed method extends existing MFPCA approaches by incorporating a generalized functional SVD within a Hilbert space framework, enabling simultaneous regularization of both functional principal components (PCs) and their associated PC scores. A key innovation of this framework is the inclusion of a sparsity penalty on the PC scores, which enhances interpretability by filtering out irrelevant subject-specific variations. This dual-penalization strategy represents a significant advancement beyond existing covariance-based eigen decomposition methods, which penalize only the functional PCs. Two power algorithm implementations, sequential and joint, are proposed, together with a cross-validation approach based on iterative regression for optimal smoothing parameter selection. Comprehensive simulation studies and real data applications demonstrate that the proposed framework substantially improves the extraction of informative and interpretable components, offering methodological and practical benefits for analyzing multivariate functional data across diverse domains.

0.34

Exact Degeneracy Under Balanced k-Shot Sampling:Consequences for Small-Sample Discriminant Analysis on LLM Embeddings

cs.LG ·2026-09-09 ·Lingxiao Qu
similarity 0.56
Abstract

Balanced k-shot sampling, drawing exactly k labeled examples per class, is the standard protocol in few-shot evaluation. We show that it induces an exact degeneracy in Kernelized Linear Principal Component Discriminant Analysis (KLPCDA), a family of seven supervised dimensionality reduction methods. The within-class operator becomes exactly a scaled orthogonal projector, so two variants have all signal eigenvalues equal and a third has a zero operator, and the truncated pseudo-inverse used to implement them removes exactly the subspace that contains all between-class information. We verify this to float64 precision on sentence embeddings and on residual-stream activations of a decoder-only model, and find that the accuracies of the truncated variants change with the number of BLAS threads, by up to 12 percentage points (57 for the variant with a zero operator). Replacing the truncation with a ridge selected within the support set, we evaluate few-shot text classification on frozen embeddings (d up to 4096) over four datasets, three embedding models, and three trained baselines. The regularized formulation outperforms the best original variant in 45 of 48 settings, but in general not a tuned linear probe or nearest centroid on bidirectional encoders. Its gains are largest on E5-Mistral, the only decoder-based embedding model, and come from regularized within-class whitening rather than from KLPCDA: shrinkage LDA outperforms both baselines in all 16 E5-Mistral settings, and pre-specified tests show that the effect depends on the embedding model rather than on its dimension. E5-Mistral's remaining gap is largely an estimation-efficiency effect: increasing k to 30-50 reduces the probe's gap to a bidirectional encoder by more than 80%. We give five guidelines limited to the conditions tested and release the code and per-seed results.

0.40

Outliers and the Hard-Margin Linear SVM in High-Dimension, Low-Sample-Size Settings

cs.LG stat.ML ·2026-11-10 ·Yugo Nakayama
similarity 0.56
Abstract

We study how outliers affect the hard-margin linear support vector machine when the dimension grows while the sample sizes remain fixed. For one-sided contamination, the centered Gram matrix converges to a constant inlier block plus an outlier-diagonal component, and the limiting dual problem has a closed-form solution. All outliers act through one effective distance. This representation yields explicit thresholds for loss of inlier support, margin shrinkage. intercept displacement, and asymptotic misclassification. We then treat contamination in both classes. The limiting intercept is the multiplier of the class-balance constraint, and the two classes pull it in opposite directions. Consequently, at most one class can collapse or be asymptotically misclassified, whereas symmetric contamination leaves the limiting discriminant function unchanged even though the margin shrinks. Seven numerical experiments verify the dual allocation, phase transitions, and discriminant limits.

0.19

Infinity-Wasserstein Distributionally Robust Principal Component Analysis: Exact Reformulation, Finite-Sample Guarantee, and Efficient Algorithm

cs.LG math.OCmath.STstat.ME+1 ·2026-11-18 ·Zhouxing Luo, Lei Wang, Xin Liu
similarity 0.56
Abstract

Principal component analysis (PCA) is a fundamental and ubiquitous technique for dimension reduction and representation learning, yet its empirical formulation remains vulnerable to distributional uncertainty. While distributionally robust optimization (DRO) offers a natural remedy, existing order-2 Wasserstein models of PCA either preserve the nominal PCA subspace or lack an exact reformulation. This paper demonstrates how the infinity-Wasserstein distance can reconcile these two desirable properties. For the resulting DRO model of PCA, we derive an exact finite-dimensional reformulation and explicitly identify a worst-case distribution attaining the inner maximum. Crucially, the reformulated objective retains samplewise residual information beyond the empirical covariance matrix, revealing a mechanism through which distributional robustness can reshape the learned principal subspace. Under the mild assumption that the true distribution has a finite fourth moment, we further establish a uniform finite-sample performance guarantee for the proposed model. An iteratively reweighted majorization-minimization algorithm is also developed to solve the resulting nonconvex and nonsmooth optimization problem, with a rigorous analysis of its convergence properties. Numerical experiments substantiate the computational efficiency of the proposed algorithm and the practical effectiveness of the infinity-Wasserstein model in downstream applications.

0.20

Kernel Singular Value Decomposition with Extension to Multiple Data Sources

cs.LG ·2026-10-02 ·Xinjie Zeng, Qinghua Tao, Johan Suykens
theory similarity 0.55
Abstract

Kernel Singular Value Decomposition (KSVD) learns a pair of singular vectors w.r.t. an asymmetric kernel matrix, which can be induced by two data sources, e.g., the queries and keys in self-attention or the rows and columns of a given matrix. In this work, we extend KSVD to multiple data sources, namely eKSVD, which conducts joint nonlinear feature learning upon asymmetric kernels. In the primal formulation, the projections associated with each data source are jointly learned to capture maximal information, while incorporating pair-wise couplings. With the Lagrangian and its Karush-Kuhn-Tucker (KKT) conditions, the optimization in the dual leads to a generalization of the shifted eigenvalue problem in Lanczos decomposition theorem of KSVD. Further, a covariance-based framework is derived together with using neural networks (NNs) for explicit feature mappings, complementary to the kernel-based interpretation and optimization. Numerical experiments verify the effectiveness of our eKSVD compared to methods based on Mercer kernels for tackling multiple data sources, and our innovation of deploying NNs demonstrates great flexibility for kernel methods.

0.21

Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs

cs.LG stat.MLstat.CO ·2026-09-17 ·Zhenlin Yao, Wei Xiong
similarity 0.55
Abstract · 41 pages, 4 figures, 18 tables; includes core supplementary material

Accurate optimization of a supervised spectral objective need not produce an accurate population subspace or a better predictive representation. We investigate these distinctions for Online Kernel Supervised Principal Component Analysis (OKSPCA), which combines a centered cross-moment in finite random-feature coordinates with an Adam-style orthonormal basis update for an established objective. Fixed-map consistency, concentration and perturbation results describe the estimator and its exact subspace; same-target comparisons then assess the practical iterate separately. Across six predictive benchmarks, performance depends on the declared pipeline: replacing the tracker with the exact empirical target leaves the two regression deficits largely unchanged. Direct classification-rank models capture nearly all terminal objective energy on average, but a saved intermediate state exhibits substantial geometric deviation; a controlled sample-size study further separates empirical accuracy from population recovery. In distinct numerical-service workloads, exact on-request computation is faster in the tested classification settings, whereas Adam saves time relative to the tested full thin-SVD service for some dense wider-regression requests, alongside persistent geometric error. These diagnostics limit explanations based solely on terminal optimization accuracy and distinguish numerical cost from quality, rank coverage and freshness; they establish neither practical-tracker convergence nor predictive or deployment benefits from basis availability.

0.27

Compact and Infinite-Order Error Analysis for Null-Space SVD Estimation

cs.LG math.ST ·2026-08-31 ·Xin Li, Jonathan Cohen, Rami Puzis
theory similarity 0.54
Abstract · 31 pages

We study null-space estimation from a noisy matrix. For a simple left null space, we first derive an exact compact expression for the error of the smallest left singular vector. We then give an all-order series for the SVD vector and projector, followed by compact and consistently truncated series forms for the fixed-realization empirical risk and conditional population generalization risk. The recursion extends to a multiple-dimensional null space by following the complete invariant subspace. The convergence radius is not inferred from an error plot: it is computed independently from the nearest complex exceptional point that joins a retained eigenvalue branch to its complement. A reduced-nullity experiment shows that moving this spectral boundary can increase the radius, although the improvement is not monotone in the retained nullity. For individually ordered null directions under Gaussian training with \(τ\geq m\), we prove that the Wishart splitting matrix \(W\) gives a strict second-order empirical ranking. Gaussian averaging equalizes the leading generalization risks at both small and very large noise, while a column-swap theorem proves strict expected generalization ranking for an isotropic signal subspace. For unequal spikes, an exact population-overlap criterion and a simultaneous \(99\%\) Monte Carlo confidence certificate explain the observed intermediate ranking. A sixth-order risk correction improves the lower-crossover estimate in the reported experiment. This equal--ranked--equal phenomenon is a finite-sample diagnostic related to spectral mixing, but its tolerance crossings, the exceptional-point radius, and the asymptotic BBP threshold are three distinct quantities.

0.38

Efficient Estimation of High Information Projections using Nearest Neighbours

cs.LG stat.ML ·2026-08-26 ·David P. Hofmeyr
similarity 0.54
Abstract

An intuitive method for dimensionality reduction is proposed, which is highly effective for finding interesting projections of multivariate data. Following similar intuitive motivation to a number of existing techniques, the proposed method is based on enhancing the nearest neighbour relationships in the data. The proposed projection arises from the spectral decomposition of a matrix designed to encode the local covariance structure in the data, where the local covariance at a point is captured by pairs of its nearest neighbours. We show that under standard regularity conditions this matrix is a consistent estimator of the so-called ``Density Information Matrix'' (DIM); a non-parametric analogue of the Fisher Information Matrix. Spectral decompositions of DIMs have been shown to be connected with the important problems of Independent Components Analysis and, in the supervised context, Sufficient Dimension Reduction. However, existing estimators of the DIM are computationally expensive to compute and only target the DIM of a surrogate density, which is proportional to the square of the true underlying density. In addition, we go on to explore the practical utility of our method in aiding the downstream tasks of cluster analysis and outlier detection.

0.22