Random Feature Methods

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 19

Oct 6, 2026stat.ML

Quadratic Weak-to-Strong Generalization in Random Feature Networks via Random Matrix Theory

Weak-to-strong generalization is the phenomenon where a strong student model trained with labels produced by a weak teacher model is able to generalize better than the teacher. In this paper, we study this phenomenon in two-layer random feature networks where the model strength is determined by its width. Using tools from random matrix theory, we derive deterministic equivalents for the population errors of an optimally trained teacher and a student trained with gradient flow. For ReLU activation and a pure spherical harmonic target, we obtain sharp asymptotics under a Gaussian universality assumption, showing a quadratic improvement: the student error scales as the square of the teacher error. These results attain the general lower bound of Medvedev at al (2025). We also analyze how the student behaves under more general stopping times and targets supported on multiple harmonic degrees, characterizing the regimes in which weak-to-strong generalization occurs and identifying the transition between quadratic, non-quadratic, and no improvement.

Deborah Oliveira, Elliot Paquette

McGill University Mila – Quebec AI Institute

Weak-to-Strong Generalization Random Feature Methods Neural Network Training Dynamics

Sep 17, 2026stat.ML

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

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.

Zhenlin Yao, Wei Xiong

School of Statistics University of International Business and Economics Beijing, China

Principal Component Analysis Random Feature Methods Dimensionality Reduction

Sep 14, 2026math.NA

Physics Informed Random Feature Neural Networks for Solving PDEs

Machine learning-based partial differential equations (PDEs) solvers have attracted significant attention in recent years. Most progress in this area has been driven by deep neural networks such as physics-informed neural networks (PINNs) and kernel method (such as physics-informed Gaussian Processes). We introduce a physics-informed random feature method for countering part of the spectral bias which PINN-based solvers are facing for a certain class of PDEs. Random feature method was originally proposed to approximate large-scale kernel machines and can be viewed as a specialized randomized neural network. Compared to other state-of-the-art PINN-based solvers which require a large number of collocation points, our proposed method reduces the computational complexity. In this paper, we develop a rigorous approximation error analysis and derive high-probability error bounds on the

H^1

norm. We provide extensive numerical tests for verifying our theoretical guarantees on error decay rates, as well as several comparison tests to showcase our claimed capability for combating spectral bias in these deep learning based methods.

Chi-An Chen, Chunyang Liao, Ming Zhong

Department of Applied Mathematics, Mathematics, Illinois Institute of Technology, Chicago, IL, 60616 · Department of Mathematical Sciences, University of Arkansas, Fayetteville, AR, 72701 · Department of Mathematics, University of Houston, Houston, TX, 77204

PDE Solving Random Feature Methods Neural Network Approximation Theory Physics-Informed ML

Sep 9, 2026quant-ph

A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features

Quantum-inspired classical algorithms have dequantized several quantum machine learning routines by replacing quantum linear-algebra subroutines with classical counterparts. However, the sampler based on quantum singular value transformation (QSVT) for learning with optimized random features is not covered by existing dequantization frameworks, because the matrix to be inverted is not itself available through sampling access. In this work, we develop a classical algorithm to address this type of quantum-advantage candidate. Our method samples heavy indices, reduces the transformation to a small principal block, and outputs a sparse classical representation with operator-norm guarantees. Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and polynomially related runtime. These results show that the factorization underlying a quantum block encoding can itself provide sufficient classical structure even when sampling-and-query access to the composite matrix is unavailable.

Natsuto Isogai, Mio Murao, Hayata Yamasaki

Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan · Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan

Quantum-Inspired ML Random Feature Methods

Sep 3, 2026math.NA

Spectral Convergence of Random Feature Method in Multiple Dimensions

We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes. The analysis establishes general high-probability approximation estimates in the interpolation scale generated by a kernel integral operator. On a single event determined only by the sampled features, one random space approximates every target in a prescribed source ball; moreover, for each target, a single coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. For both regularity-adapted frequency distributions and uniform distributions on growing frequency windows, the resulting rates range from super-exponential to algebraic, depending on the regularity of the target. Second, we establish abstract error estimates for strong- and weak-form RFM discretizations, thereby converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems. Finally, for random feature matrices (RFMtxs), we prove super-exponential singular-value decay with Fourier features and exponential decay with

\tanh

features, together with corresponding condition-number lower bounds. The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.

Pingbing Ming, Hao Yu

PDE Solving Random Feature Methods Neural Network Approximation Theory

Aug 7, 2026cs.LG

Uncertainty-Aware Ensemble Deep Randomized Neural Networks for Classification

The current state-of-the-art (SOTA) deep randomized neural networks, such as deep Random Vector Functional Link (dRVFL) and ensemble deep RVFL (edRVFL), treat all training samples uniformly, which limits their robustness and effectiveness when applied to real-world datasets containing noise and outliers. Furthermore, the propagation of contaminated features across hidden layers negatively influences the decision-making capability of these models. To overcome these limitations, we propose intuitionistic fuzzy dRVFL (IF-dRVFL) and intuitionistic fuzzy edRVFL (IF-edRVFL) frameworks that enhance model robustness. The proposed models unify intuitionistic fuzzy theory to exploit sample neighborhood information in the kernel space by jointly considering membership and non-membership degrees for each sample. Membership degrees are computed based on the distance of samples from their respective class centroids, while non-membership degrees quantify sample heterogeneity within local neighborhoods. These measures are employed to assign adaptive weights to training samples, enabling effective discrimination among clean, noisy, and outlier data points. Extensive experiments conducted on UCI and KEEL benchmark datasets, with and without the presence of Gaussian noise, demonstrate the superiority of the proposed IF-dRVFL and IF-edRVFL models over existing SOTA fuzzy and non-fuzzy approaches. The source code is available at https://github.com/mtanveer1/IF-edRVFL.

M. Sajid, A. Quadir, A. Rahaman +2

Indian Institute of Technology Indore, Simrol, Indore, India · Qatar University, Qatar

Ensemble Learning Neural Network Robustness Random Feature Methods Fuzzy Logic Learning with Noisy Labels

Aug 4, 2026cs.LG

Random features for Grassmannian kernel approximation with bounded rank-one projections

We propose a family of random feature maps for scalable kernel machines on low-dimensional subspaces, ie on the Grassmannian manifold. Such representations are useful when data classes or clusters are well described by the span of a few samples. Classical Grassmannian kernels, including the projection and Binet-Cauchy kernels, require full Gram matrices, which leads to prohibitive computational and memory costs for large high-dimensional subspace datasets. We address this limitation using random features based on rank-one projections of subspace projection matrices followed by bounded non-linear transforms, either periodic or binary, to control the resulting distributions. We show that inner products in the random feature space approximate well-defined rotation-invariant Grassmannian kernels that depend only on the principal angles between subspaces. When the number of features is sufficiently large relative to the intrinsic subspace dimension, the approximation holds uniformly over all fixed-dimensional subspaces with high probability. For periodic transforms, the approximated kernel has a closed-form expression with tunable behaviour between inverse Binet-Cauchy and Gaussian-type regimes. Binary transforms yield compact one-bit subspace features, although no closed-form kernel is known. Structured rank-one projections based on randomised fast Fourier transforms further reduce computation without sacrificing practical accuracy. Experiments on synthetic data and ETH-80 classification tasks show that these features accurately preserve Grassmannian geometry while reducing computation, memory, and storage. Rank-one embeddings therefore provide a practical and scalable alternative to classical Grassmannian kernels.

Rémi Delogne, Laurent Jacques

INMA/ICTEAM, UCLouvain, Belgium

Geometric Representation Learning Random Feature Methods Kernel Methods

Jul 26, 2026cs.LG

A Coulomb Particle Model for Learning Kernel Attention in Transformers

Randomized features provide a scalable approximation to kernel machines, but their performance depends strongly on the choice of feature distribution. We propose a particle-based method that learns this distribution by optimizing kernel-target alignment while regularizing particles with a Riesz/Coulomb repulsive potential. The resulting Hamiltonian yields diverse, task-adaptive random features and admits a mean-field description through a McKean--Vlasov equation. We instantiate the method in linearized Transformer attention by learning positive random-feature maps in a first alignment phase, then freezing the kernel and training the remaining network parameters with cross-entropy. Experiments on synthetic classification and sentence-level benchmarks show that learned kernelized attention can improve accuracy, calibration, and robustness for several feature maps while preserving linear-attention inference complexity.

Masoud Badiei Khuzani, Sharath Honnaiah, Atiq Islam +2

eBay Inc., San Jose, CA, USA

Transformer Attention Efficient Attention Random Feature Methods Kernel Methods

Jul 22, 2026math.NA

A Structure-Adaptive Random Feature Method for High-Dimensional Elliptic PDEs

Random-feature methods reduce high-dimensional elliptic PDE collocation to linear coefficient problems, but full-dimensional trial spaces overlook lower-dimensional structure. We introduce the Hierarchical Analysis-of-Variance Random Feature Method (HA-RFM), which selects coordinate blocks using closed Sobol indices of the PDE residual, identifies oblique low-rank features from fitted-predictor gradients, and couples all retained features in one regularized least-squares solve. Under structural and stability hypotheses, we establish an

L^2

error bound that links solution and residual truncation to finite-width approximation and regularized finite-sample fitting, and we derive guarantees for width and structure recovery. The resulting width is polynomial in the dimension at fixed interaction order, with dimension-independent higher-order contributions under uniform structural control. Residual screening achieves exact recovery of the prescribed three-pair support, while fitted-predictor gradients recover oblique directions through dimension

50

. In random-ridge tests, less than

1\%

additional width reduces errors by factors of

14

-

39

over coordinate blocks and

34

-

100

over equal-width full-dimensional RFM. Semilinear computations extend HA-RFM through dimension

100

, while dense and distributed interactions delineate the coordinate families required for broader structure.

Jiale Linghu, Hao Dong, Yangshuai Wang

School of Mathematics and Statistics, Xidian University, Xi’an 710071, China. · Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, 119076, Singapore

PDE Solving Random Feature Methods Kernel Methods

Jun 9, 2026cs.LG

Accurate and Resource-Efficient Federated Continual Learning

Federated continual learning (FCL) must learn from distributed task streams under limited resources, such as communication, computation, memory, and label availability. Existing FCL methods often rely on repeated local optimization, replay, and full supervision. Analytic alternatives avoid iterative training and replay, but using high-dimensional random features to improve accuracy requires a second-order feature statistic, the Gram matrix, which has a quadratic communication cost in the random feature size

M

. We propose FedRAN, a resource-aware analytic FCL framework that replaces gradient-based updates with compact random feature statistics. Each client transmits a truncated-SVD summary of its Gram matrix, reducing the dominant second-order upload from quadratic to linear in

M

for fixed rank. The server performs a two-level QR-SVD subspace merge, spatially across clients and temporally across tasks, and solves a ridge classifier in closed form. FedRAN further supports label scarcity through prototype-based pseudo-labeling. Across CIFAR-100, ImageNet-R, and VTAB datasets, FedRAN improves average accuracy by up to 4.8 percentage points over the strongest baseline, uses 30.6-121.8

\times

less per-client communication than optimization-based FCL, and is 190.3

\times

faster on average than gradient-based baselines; with only 20% labels, pseudo-labeling improves average accuracy by up to 6.61 points. These results show that FedRAN enables accurate and resource-efficient FCL under communication, computation, and label constraints. The source code is available at https://github.com/JebacyrilArockiaraj/Fed-RAN-SSL.

Jebacyril Arockiaraj, Dhruv Parikh, Jayashree Adivarahan +2

University of Southern California · Los Angeles, USA · DEVCOM Army Research Office +1

Communication-Efficient Distributed Training Continual Learning Federated Continual Learning Random Feature Methods Federated Learning Data-Efficient Learning

Jun 8, 2026cs.LG

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

Bernstein--Schur kernels are products of a finite-feature kernel and a completely monotone shift-invariant kernel: nonstationary kernels falling between the shift-invariant and dot-product templates random features exploit, so neither Bochner sampling nor polynomial sketching applies to the full kernel directly. We give one random-feature construction for the whole class that randomizes both factors: it sketches the finite modulation and samples the radial factor's one-dimensional Bernstein--Widder scale before applying Gaussian random Fourier features, giving feature dimension

Dm

, free of the

O(d^2)

size of the exact modulation feature. With the modulation kept exact (the

m\to\infty

limit), we prove unbiasedness, an exact variance, and a matrix-Bernstein operator-norm bound controlled by the top kernel and modulation eigenvalues and an intrinsic dimension rather than the crude

N\max_{ij}

route. Whitening this argument at the ridge makes the effective dimension

d_{\mathrm{eff}}(λ)

the \emph{exact} intrinsic dimension of the matrix variance, so

O((1+\|P\|_{\mathrm{op}}/λ)\log(d_{\mathrm{eff}}/δ))

radial draws preserve the kernel-ridge solution; tilting the draw by a closed-form whitened leverage improves this to the effective-dimension count

O((1+d_{\mathrm{eff}})\log(d_{\mathrm{eff}}/δ))

. Conditioning on the sketch carries every guarantee to the deployed doubly-randomized estimator up to one additive sketch term, and all hold for the whole class with the modulation Gram in place of the polynomial one. The flagship instance is the biased

yat

-kernel

k_{yat,b}(w,x)=(w^\top x+b)^2/(\|w-x\|^2+\varepsilon)

, whose family span contains the inverse-multiquadric kernel by finite differences in

b

.

Taha Bouhsine

Azetta AI

Fourier Feature Embeddings Kernel Ridge Regression Randomized Sketching Random Feature Methods Kernel Methods

Jun 3, 2026cs.LG

Generating Financial Time Series by Matching Random Convolutional Features

Generating realistic financial time series is challenging as training data is often limited to a single historical path. With such scarce data, overfitting is hard to avoid, especially under adversarial training where a trained discriminator can memorize the training samples. To mitigate this, recent approaches train generators to minimize the discrepancy between untrained feature representations of real and generated time series. In these works, the feature maps are based on path signatures, which can fail to capture relevant time series properties at tractable truncation depths. In this work, we instead train generators by matching random convolutional features of real and generated time series. Existing random convolutional feature maps, such as Rocket and Hydra, have been shown to provide informative representations of real-world time series, but cannot supervise generative models because they are non-differentiable. We introduce SOCK (SOft Competing Kernels), a fully differentiable random convolutional feature map, suited to train generative time series models. We show that generators trained by matching random SOCK features consistently outperform signature and diffusion baselines across a wide range of small-sample financial datasets. We further demonstrate SOCK's expressiveness on two-sample hypothesis testing and time series classification tasks, where SOCK matches or outperforms existing unsupervised feature maps.

Konrad J. Mueller, Nikita Zozoulenko, Ben Wood +2

Imperial College London · JPMorgan Chase & Co.‡

Time Series Generation Random Feature Methods Financial Time Series Time Series Representation Learning Finance

Jun 3, 2026cs.LG

HalfNet: Randomized Neural Networks with Learned Subspace Geometry

Many researchers investigated neural networks with some of their weights fixed to values randomly drawn from a given distribution, e.g.,

N(0, I)

. Our proposed HalfNet draws random weights from

N(0, Σ)

, where

Σ

, which defines the geometry of the distribution, has a low-rank factorization that we learn from data. Experiments on MNIST and CIFAR-10 demonstrate that HalfNet can match the performance of fully trained multilayer perceptrons while using substantially fewer parameters. Spectral analysis indicates that much of the predictive power of neural networks lies in the geometry of their weight space rather than in the precise values of individual parameters, and we observe that accuracy scales smoothly with rank. HalfNet is not a neural architecture trick for low-rank structure; it implements a data-dependent random embedding that can also be interpreted through supervised metric learning, or random-feature and kernel perspectives.

Ethem Alpaydin

Independent Researcher Istanbul, Turkey

Neural Representation Geometry Random Feature Methods Feedforward Neural Networks Neural Network Compression

May 25, 2026cs.LG

Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding

Conditionally positive definite (CPD) kernels are defined with respect to a function class

\mathcal{F}

. It is well known that such a kernel

K

is associated with its native space (defined analogously to an RKHS), which in turn gives rise to a learning method -- called conditional kernel ridge regression (conditional KRR) due to its analogy with KRR -- where the estimated regression function is penalized by the square of its native space norm. This method is of interest because it can be viewed as classical linear regression, with features specified by

\mathcal{F}

, followed by the application of standard KRR to the residual (unexplained) component of the target variable. Methods of this type have recently attracted increasing attention. We study the statistical properties of this method by reducing its behavior to that of KRR with another fixed kernel, called the residual kernel. Our main theoretical result shows that such a reduction is indeed possible, at the cost of an additional term in the expected test risk, bounded by

\mathcal{O}(1/\sqrt{N})

, where

N

is the sample size and the hidden constant depends on the class

\mathcal{F}

and the input distribution. This reduction enables us to analyze conditional KRR in the case where

K

is positive definite and

\mathcal{F}

is given by the first

k

principal eigenfunctions in the Mercer decomposition of

K

. We also consider the setting where

\mathcal{F}

consists of

k

random features from a random feature representation of

K

. It turns out that these two settings are closely related. Both our theoretical analysis and experiments confirm that conditional KRR outperforms standard KRR in these cases whenever the

\mathcal{F}

-component of the regression function is more pronounced than the residual part.

Rustem Takhanov, Zhenisbek Assylbekov

Department of Mathematics, Nazarbayev University, Astana, Kazakhstan · Nazarbayev University Research Administration, Astana, Kazakhstan · Purdue University Fort Wayne, Indiana, USA.

Kernel Ridge Regression Kernel Regression Random Feature Methods Kernel Methods Statistical Learning Theory Ridge Regression

May 21, 2026cs.LG

Worse than Random: The Importance of a Baseline for Unsupervised Feature Selection

Many novel unsupervised feature selection methods are proposed each year, yet their empirical evaluation is limited to supervised and unsupervised evaluation metrics computed on selected datasets, along with comparisons to existing methods. However, in the absence of an established evaluation baseline, it is difficult to determine the value added to the existing literature by each of these methods, and how effective their underlying approaches are. We propose using random feature selection as a baseline for evaluating the unsupervised feature selection methods. We empirically show that many of the state-of-the-art methods in unsupervised feature selection are outperformed by random feature selection in both performance and efficiency. Accordingly, we emphasize on the strict requirement of considering random feature selection as a baseline in the development process of novel unsupervised feature selection methods to ensure a consistent improvement over random feature selection.

Muhammad Rajabinasab, Michael E. Houle, Oussama Chelly +1

University of Southern Denmark, Odense, Denmark · New Jersey Institute of Technology, Newark, NJ, United States · oratio Technologies, Tunis, Tunisia

Unsupervised Learning Random Feature Methods Feature Selection

May 14, 2026eess.SY

Randomized Atomic Feature Models for Physics-Informed Identification of Dynamic Systems

We present a physics-informed framework for system identification based on randomized stable atomic features. Impulse responses are represented as random superpositions of stable atoms, namely damped complex exponentials associated with poles sampled inside a prescribed disk. Identification is then cast as a convex regularized least-squares problem with optional linear, second-order-cone, and KYP constraints. The approach generalizes random Fourier and random Laplace features to the damped, nonstationary regime relevant to engineering systems while retaining modal interpretability and scalable finite-dimensional computation. The main analytic point is an operator-theoretic Disk-Bochner viewpoint: positive measures over stable poles generate positive-definite kernels with a radius-dependent shift defect, while a converse scalar disk moment representation for an arbitrary kernel is characterized by subnormality of the canonical shift. We prove this statement, establish an RKHS-to-l1 embedding, show that sampled poles induce a valid finite atomic gauge, discuss random-feature convergence, and state sparse-recovery guarantees conditionally on the restricted-eigenvalue properties of the realized disk-Vandermonde or input-output design matrix. We also connect the normalized transfer function problem to Nevanlinna-Pick interpolation and LFT set-membership. The framework directly encodes stability margins, modal localization, DC-gain bounds, monotonicity, passivity, relative degree, settling-time targets, and time/frequency-domain error bounds. Numerical comparisons illustrate how physically meaningful priors can compensate for poor excitation and improve constrained impulse-response recovery in an under-informative data setting.

Rajiv Singh, Mario Sznaier, Lennart Ljung

∗The MathWorks Inc., 1 Apple Hill Drive, Natick, MA 01760 USA · ∗∗ECE Dept., Northeastern University, Boston, MA 02115, USA · ∗∗∗Div. of Automatic Control, Linköping University, Sweden

Random Feature Methods System Identification Kernel Methods Physics-Informed ML

May 7, 2026stat.ML

Fourier Feature Methods for Nonlinear Causal Discovery: FFML Scoring, TRFF Scoring, and FFCI Testing in Mixed Data

Gaussian process (GP) marginal likelihood scores and kernel conditional independence tests are theoretically appealing for nonlinear causal discovery but computationally prohibitive at scale. We present three complementary RFF-based methods forming a practical toolkit for score-based, constraint-based, and hybrid causal discovery. The Fourier Feature Marginal Likelihood (FFML) score approximates the exact GP marginal likelihood by replacing the

n x n

kernel Gram matrix with a finite-dimensional feature representation, reducing cost to

O(nm^2 + m^3)

while retaining the probabilistic interpretation and automatic complexity penalty of the exact score. FFML extends to mixed (continuous and discrete) parent sets via a product-kernel construction, with a Kronecker path for small discrete parent sets and a Hadamard-product path otherwise. The Tetrad Random Fourier Feature (TRFF) score is a complementary BIC-style alternative using penalized Student-t regression with random Fourier features. TRFF offers robustness to heavy-tailed noise and faster runtime than FFML. Empirically, TRFF and FFML exhibit a complementary precision-recall profile: TRFF achieves higher precision while FFML achieves better recall and lower SHD overall. The Fourier Feature Conditional Independence (FFCI) test is a fast nonparametric CI test for mixed data, using ridge residualization in feature space and a Frobenius-norm cross-covariance statistic approximated as a weighted sum of chi-squared variables. Empirically, BOSS+FFML achieves the lowest SHD on nonlinear data, while BOSS+TRFF offers the highest precision. When run through PC-Max, FFCI and RCIT exhibit complementary precision-recall profiles: RCIT is more precise while FFCI achieves better recall and substantially lower SHD, at approximately twice the runtime.

Joseph D. Ramsey

Department of Philosophy Carnegie Mellon University Pittsburgh, PA 15213

Fourier Feature Embeddings Causal Discovery Random Feature Methods Causal Inference Conditional Independence Testing

Apr 17, 2026cs.LG

Green-ELM: Efficient Analytic Learning via High-Dimensional Random Projections

We present Green-ELM, a non-iterative neural architecture that replaces gradient-based optimization of the output layer with a closed-form analytic solution over a fixed, high-dimensional random feature representation. By projecting input manifolds into a high-dimensional, random feature space (

d \gg 784

), our results show that complex class boundaries can be effectively untangled without the computational overhead of backpropagation. Utilizing the Moore-Penrose pseudoinverse, LU and Cholesky decomposition to solve for the output layer in a single analytic step, Green-ELM achieves a classification accuracy of 98.10% on MNIST (

d=4000

) and 86.63% on Fashion-MNIST. Furthermore, we experiment with a pre-trained ``frozen-backbone'' based on ResNet-18 to extract high-quality features and show that these one-shot solvers are effective beyond simple datasets. Notably, our baseline CPU configuration on MNIST (

d=2000

) achieves 97.15% accuracy in 1.5s, representing a 11.6

\times

reduction in reported training time over an SGD baseline while maintaining comparable performance. We observe a near-logarithmic scaling behavior between dimensionality and accuracy, where the accuracy increases approximately logarithmically with hidden dimensionality over the tested range, suggesting that feature-space expansion contributes substantially to performance in these experiments. . This one-shot linear matrix solver approach offers a viable alternative for real-time Edge AI, where the traditional training phase is bypassed in favor of non-iterative manifold representation and readout. Finally, we propose an Empirical Scaling Hypothesis, a framework that models accuracy bounds as a function of high dimensionality and intrinsic dataset complexity.

Wladimir Silva

Department of Computer Engineering North Carolina State University

Neural Network Optimization Random Feature Methods Image Classification

Oct 9, 2025cs.LG

Computationally-efficient Graph Modeling with Refined Graph Random Features

We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.

Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish +1

Google DeepMind, New York, NY, USA · Columbia University, New York, NY, USA · Google Research, Mountain View, CA, USA +2

Graph Representation Learning Randomized Sketching Random Feature Methods