Randomized Sketching

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 133% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 35

Oct 6, 2026cs.NE

A Connectome Test of the Fly Hashing Algorithm

Dasgupta, Stevens and Navlakha (2017) showed that the Drosophila olfactory circuit, modelled as a random sparse projection followed by winner-take-all, is a locality-sensitive hash that beats classical LSH. The projection was random because the wiring was unknown. We test it against four electron-microscopy connectomes (MaleCNS, hemibrain, FlyWire, BANC; four animals, seven hemispheres). First, the 2017 pattern holds in a reimplementation of its protocol on SIFT, MNIST and odour mixtures (GloVe is near chance at short codes for every method): the fly hash beats k Gaussian projections at short hash lengths (3.1x in AP@200 on MNIST at k = 4). Second, against the tested real-valued Gaussian baseline that advantage is per active cell, not per operation: Gaussian projections given the same projection arithmetic retrieve better on every dataset and input dimension tested. Third, across four connectomes the measured pairing of glomeruli gives no consistent retrieval advantage over degree-preserving rewiring: retrieval is slightly lower (median -1.6%), and the small odour deficits depend on how missing odour responses are treated. Separately, equalising glomerular fan-out at fixed connection count improves retrieval in the model in every hemisphere, while equalising inputs per cell lowers it on average. Yet the fan-out profile is similar across the four sampled animals (median between-animal Spearman rho = 0.86), structural synapse counts do not offset it, and its relation to odour tuning is weak. In the model that uneven allocation costs retrieval. For practice: measured wiring gives no consistent retrieval advantage over degree-preserving random wiring, so a fly hash needs no connectome data, and its advantage is per active unit, which may suit hardware where active units rather than arithmetic are the binding cost, a hypothesis we do not test.

Sebastian Senge

Independent Researcher

Dimensionality Reduction Randomized Sketching Brain Network Analysis

Sep 29, 2026cs.LG

The Advantages of Fresh Sketching for Ridge Regression

Over the past 25 years, sketching and sampling have become widely used tools for accelerating large-scale regression. In iterative randomized solvers, a basic design choice is whether to

\textit{reuse}

the same sketch or draw

\textit{fresh}

randomness at every step. For (under-constrained) iterative ridge regression with column sampling, whether fresh sketches offer provable advantages has remained open:

\textit{We show that they do.}

Fresh sketching lets us analyze error only along the current residual solution, rather than uniformly over the entire Gram matrix. This directional view yields sharper convergence guarantees for leverage score and ridge leverage score sampling and, more importantly, leads to residual-aware sampling rules. By minimizing the variance of the relevant sketched matrix-vector product, we derive an oracle distribution and practical approximations to the oracle distribution, including a mixture sampling distribution with (somewhat weaker) convergence guarantees. Experiments on synthetic and real data, including ridge probes on Qwen2.5 representations, support our theory, showing substantially faster convergence.

Linkai Ma, Qilin Li, Petros Drineas

Purdue University · University of Wisconsin-Madison

Importance Sampling Randomized Sketching Adaptive Sampling Ridge Regression

Sep 28, 2026cs.LG

Single-Layer MeMo as a Randomized Hamming-Kernel Classifier

MeMo (Zanzotto et al., 2025) is a recent language-model architecture that stores associations between token contexts and next tokens in a correlation matrix memory. In this work, we study its single-layer form and show that its ideal retrieval rule is a multiclass classifier based on the positional Hamming kernel. The MeMo architecture represents both the sequence features and the output labels with Gaussian random codes. Its score is therefore a doubly randomized sketch of the ideal classifier. Under independent input and output codebooks, we bound the errors introduced by context sketching and output decoding, characterize their dependence on model and data parameters, and give a margin-based guarantee for recovering the ideal prediction. Controlled simulations support the trends predicted by the analysis. On a restricted WikiText-2 next-token task, we compare single-layer MeMo with classical baselines and show that it can offer a useful trade-off among predictive accuracy, memory, and throughput, particularly on a GPU, where its matrix operations can be parallelized.

Alessandro Straziota

Department of Enterprise Engineering University of Rome “Tor Vergata” Rome, Italy

Memory-Augmented Language Models Next-Token Prediction Randomized Sketching Classification Kernel Methods

Sep 23, 2026cs.LG

Efficient Linear Bandits via Cluster-Aware Sketching

We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension

d

of the feature vectors leads to growing computational costs of

O(d^2)

at each round of update. Traditional sketching-based methods such as SOFUL reduce computation via fixed-size matrix sketching, yet run the risk of incurring vacuous linear regret when the spectral tail of the data is heavy and the sketch size is inadequately selected. To guarantee regret convergence and effectively reduce computational costs, we introduce a clustering mechanism and propose the Cluster Sketch Linear Bandit (CS-LB) algorithm. Our method preserves the full covariance information in each cluster to guarantee robust sublinear regret without spectral-tail vulnerabilities, performs cluster switching by assigning a sentinel for each cluster, and reduces per-round update computation to

O(l^2d)

via a tunable sketch size

l<d

. Experiments on synthetic datasets demonstrate that our method consistently maintains a favorable trade-off between efficiency and regret.

Hantao Yang, Hong Xie, Defu Lian

University of Science and Technology of China

Multi-Armed Bandits Randomized Sketching Contextual Bandits

Sep 16, 2026cs.LG

Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices

Spectral co-clustering is a useful tool for discovering latent structure in word-document matrices, but its reliance on singular value decomposition (SVD) can make standard formulations expensive on high-dimensional data. This paper presents two randomized approximations for normalized spectral co-clustering of bipartite text data when the numbers of document and word clusters may differ. The first method uses randomized SVD through random projection, while the second combines partial SVD with element-wise random sampling. Across real-world and synthetic datasets, both methods reduce runtime relative to the full-SVD baseline, but their behavior depends on matrix sparsity. The random projection method is the more reliable approximation across the tested settings, whereas the sampling-based method is most useful on denser matrices and provides limited benefit on already sparse text data. These results show that randomized approximations for spectral co-clustering should be selected according to the underlying structure of the data.

Fateme Mazdarani, Carlos Toxtli

School of Computing Clemson University Clemson, SC, USA

Clustering Randomized Sketching Spectral Clustering Singular Value Decomposition

Sep 16, 2026cs.LG

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

We consider the problem of estimating the trace of an implicit matrix

\mathbf{A} \in \mathbb{R}^{d^p\times d^p}

that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% \cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$ , and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$ , satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$ , and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$ . Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in

\mathbb{R}^{d^p}

is constructed as the Kronecker product of

p

random vectors in

\mathbb{R}^d

, requiring

O(mpd)

random bits for

m

query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with

p

. In this work, we address this limitation by proposing a sketching-based estimator that requires

O\!\big(p (d + m)\log m\big)

random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with

p

.

Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma

Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502284, Telangana, India.

Randomized Sketching

Sep 14, 2026stat.ML

Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.

Xinchen Du, Elizaveta Rebrova, Micha\l Dereziński +1

School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Operations Research and Financial Engineering, Princeton University · Computer Science and Engineering, University of Michigan

Stochastic Approximation Second-Order Optimization Randomized Sketching

Sep 7, 2026cs.NE

Photonic reservoir computing with dimensionally compressed readout

This work addresses a hardware constraint in reservoir computing: the limited size of the readout layer imposed by systems with a physical readout. We investigate a strategy to accommodate this constraint based on random projection, which compresses high-dimensional reservoir states into a lower-dimensional subspace while preserving key properties of the source space and information- processing capabilities. To evaluate this approach, we compare a small, standalone time delay reservoir against a larger configuration whose output is projected down to match the same restricted readout dimension. Using task-independent metrics, we demonstrate that the distribution of information-processing capacities may differ between the two configurations, even at identical readout sizes. Furthermore, we perform a comprehensive hyperparameter scan to assess how both systems behave under varying physical regimes. Finally, we benchmark this approach on the standard NARMA10 task, showing that the random projection framework can yield superior performance compared to a standalone constrained reservoir, within specific compression range. These results provide a scalable pathway to bypass physical readout bottlenecks in hardware-based reservoir computing.

Gerald Kobi, Mohab Abdalla, Miguel C. Soriano +1

Université de Lorraine, CentraleSupélec, LMOPS, F-57000 Metz, France · Instituto de Física Interdisciplinar y Sistemas Complejos (IFISC), CSIC–UIB, Campus UIB, E-07122 Palma de Mallorca, Spain

Reservoir Computing Randomized Sketching Dimensionality Reduction Photonic Computing

Sep 2, 2026cs.LG

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of

n

points to

m=O(\varepsilon^{-2}\log n)

dimensions preserves pairwise squared distances within relative error

\varepsilon

with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature

f(D)

of a squared distance

D

from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data (

Σ=σ^2 I_d

), we diagonalize this operator in closed form. For fixed

k

with

m,d-m\to\infty

, its

k

th singular value satisfies

\ell_k\approx(m/ d)^{k/2}

. This yields three sharp consequences. A rank-

m

sketch retains at most an

m/d

fraction of the variance of any feature of one squared distance. If

m\to\infty

and

m/d\to0

, the expected Kendall correlation is

\frac{2}π\sqrt{m/d}(1+o(1))

; for fixed

q

, nearest- neighbor agreement tends to

1/q

. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when

\log n\ll m\ll d

. After removing scale, Haar-averaged retained covariance-shape information is

(m/d)^2

. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

Piyush Sao

Computer Science and Mathematics Division, Oak Ridge National Laboratory, Oak Ridge, Tennessee 37830, USA

Randomized Sketching

Aug 27, 2026cs.LG

Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares

We classify when ordinary fixed-size volume sampling followed by unweighted least squares attains its sharp coefficient-covariance ceiling on a fixed design. For a real whitened design without coloops and a fixed positive-loss residual, the contact space is unchanged at every strict-interior sample size. Its possible nonzero values form a finite orthogonal family: each maximal parallel class of normalized Naimark-complement rows determines a deletion nullspace of dimension one less than the class size. A single residual attains an entire query precisely when the query range lies in one class space. The proof starts from two-sided Loewner comparison of every normalized covariance deficit with an explicit leave-one-out operator, using supported omission moments and reverse deletion. Residual augmentation provides resolvent and second-moment upper bounds, while complement geometry yields query-specific margins, angular concentration, local alignment, and a multi-output energy obstruction. Exact families give closed-form margins and covariances, exhibit support-boundary jumps, and approach the ceiling despite a uniformly positive geometric margin. Finally, the same moment identities give upper and lower bounds on expected fixed-query squared-loss excess. The subset draw is the only randomness; all support and endpoint restrictions are explicit.

Kihun Rhee, Hanjoon Byun, Junpyo Seo

Randomized Sketching Linear Regression Statistical Learning Theory

Aug 11, 2026cs.DS

Improving TensorSketch Using Complex Random Variables

\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels

\vec{x}^{\otimes p} \in \R^{d^p}

. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost

O(pDd)

, where

D

denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$ . However, the variance of both estimators grows exponentially with the polynomial degree $p$ , scaling as $3^{p}/D$ . Recent work by\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to

2^{p}/D

for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost

O(pDd)

and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~~\citep{pham2013fast} that achieves the same variance bound as~~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1

Department of Computer Science and Engineering, IIT Hyderabad, India · Department of Mathematics and Statistics, Bucknell University, USA

Randomized Sketching Kernel Methods Variance Reduction

Jul 23, 2026cs.DB

MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery

Join discovery is a core task in dataset search, enabling users to find columns that can be joined with a given query column. Early approaches focused on equi-joins, but data lakes and open-data repositories often contain columns whose values refer to the same entity but use different syntactic representations. To address this challenge, recent approaches discover semantically joinable columns but face a fundamental trade-off: methods that perform value-level comparisons accurately identify joinable columns but scale poorly to columns with high cardinality; column-level methods that encode an entire column into a single embedding are efficient but do not capture the fine-grained value alignment that determines whether a join is possible. We present MosaicJoin, a value-level semantic join discovery method that balances this trade-off. MosaicJoin achieves scalability through a novel sketching strategy that approximates the joinability of a column pair without having to compare all values. At query time, MosaicJoin scores each candidate sketch using a joinability score at a cost bounded by the sketch size, making retrieval efficient even for high-cardinality columns. A query subsampling operator further reduces online search time with provable accuracy guarantees, enabling robust retrieval for large query columns. Extensive experiments show that MosaicJoin outperforms previously published methods across all benchmarks while running up to 66 times faster than other value-level methods. MosaicJoin requires no training or fine-tuning, and it scales robustly to query columns containing up to 57K values and data lake columns containing up to 1M values.

Grace Fan, Eden Wu, Majid Daliri +1

New York University

Randomized Sketching Information Retrieval

Jul 8, 2026cs.LG

Distributed Sketching on Data Partitions for OLS Regression

This paper studies distributed sketching for ordinary least squares (OLS) regression, an approach that distributes small sketches of a large data set over multiple machines to separately construct OLS estimators and average them. Unlike prior studies that consider sketching on the whole data set, we consider sketching on partitioned subsets to further reduce computational cost. Under the fixed design setting, we characterize the exact excess loss of the averaged OLS estimator. Results show that this loss is comparable to the established loss for sketching on the whole data set when the divergence among subset covariances is small.

Luyuan Yang, Brayden Garner, Shayan Shafaei +1

a School of Computer Science, University of Oklahoma, U.S.

Randomized Sketching Linear Regression

Jul 8, 2026cs.NE

Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis

Classical space-filling designs often fail to provide reliable statistical results for Exploratory Landscape Analysis (ELA) when only limited evaluation budgets are available, as commonly occurs in high-dimensional problems or other resource-constrained settings, resulting in noisy and unstable landscape descriptors. To address this challenge, we propose an alternative sampling strategy for ELA based on random linear embeddings. Rather than sampling uniformly in the full decision space, we allocate the budget to randomly oriented low-dimensional subspaces and investigate whether this improves the robustness of the resulting landscape descriptors. We compare full-space and embedding-based sampling strategies across several classical ELA feature sets on the noiseless Black-Box Optimization Benchmarking (BBOB) test suite from the COmparing Continuous Optimizers (COCO) environment, in a 20-dimensional setting. Our results suggest that random linear embeddings constitute a promising alternative for budget-constrained ELA, although their effectiveness remains dependent on the feature class and the underlying problem.

Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck +1

Leiden Institute of Advanced Computer Science (LIACS), Leiden University, The Netherlands · RWTH Aachen University, Germany

Black-Box Optimization Randomized Sketching

Jul 8, 2026math.ST

Any-Dimensional Learning by Sampling

Many machine learning models are defined for inputs of different sizes, such as point clouds containing different numbers of points, sequences of tokens of different lengths, and graphs on different numbers of nodes. Such models are trained on finitely many examples of necessarily limited sizes. How well do these models generalize from inputs of small size to larger inputs of size not seen during training? Furthermore, evaluating such models on large inputs is often expensive. How can we sketch large inputs to obtain smaller ones on which the model takes similar values? At the heart of both questions is the need to compare inputs of different sizes and to approximate large inputs by small ones. We present a unified approach to address these questions by using random sampling maps to compare inputs of different sizes. The sampling maps we consider are generalizations of sampling with replacement, random binning, and species sampling. We characterize the application domains in which each type of sampling is appropriate in terms of the symmetries and relations between problem instances of different sizes in the domain. Our framework yields explicit generalization and sketching rates for function classes continuous with respect to a chosen notion of sampling, encompassing large families of functions defined on sequences, graphs, and tensors of different sizes. Specific examples include moment polynomials on measures, homomorphism densities and numbers of graphs, permutation-invariant transformers, and graph neural networks.

Eitan Levin, Venkat Chandrasekaran

Department of Statistics University of Chicago Chicago, IL 60637 · Department of Computing and Mathematical Sciences Department of Electrical Engineering California Institute of Technology Pasadena, CA 91125

Randomized Sketching Generalization Bounds

Jun 19, 2026cs.LG

Fast-TurboQuant: A Multiplier-Free Online Vector Quantization Approach

As large language models scale, memory bandwidth for key-value caches and retrieval-augmented generation systems becomes a critical bottleneck. While 1-bit quantization addresses this constraint, recent TurboQuant relies on dense random rotation matrices to condition the vector distribution before quantization. This projection demands millions of floating-point multiplications per embedding, making it difficult to deploy on constrained edge silicon. We introduce Fast-TurboQuant, a multiplier-free projection architecture that replaces the dense matrix with a structured fast Johnson-Lindenstrauss transform. By applying a Rademacher phase inversion followed by a fast Walsh-Hadamard transform (FWHT), the method leverages sub-Gaussian concentration to satisfy the prerequisites of scalar Lloyd-Max quantization without Gaussian projections. This substitution reduces the arithmetic complexity to only additions, eliminating hardware multipliers. Evaluation on DBpedia OpenAI-3 Large embeddings demonstrates a 19.7 times algorithmic speedup under sequential execution. Furthermore, the dimension expansion due to the FWHT zero-padding reduces the mean squared error and improves Recall@10.

Pedro M. R. Pereira, Felipe A. P. de Figueiredo, Rausley A. A. de Souza

National Institute of Telecommunications (Inatel), Santa Rita do Sapucaí, MG 37536-001, Brazil

LLM Quantization Rotation-Based Quantization Vector Quantization Randomized Sketching Embedding Compression

Jun 14, 2026stat.ML

Stochastic trace estimation with tensor train random vectors

Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products. However, in tensor-structured settings, unstructured Gaussian or Rademacher test vectors may be prohibitively expensive to store and compute with, while cheaper rank-one tensor-product vectors can require sample complexities that grow exponentially with the tensor order. This work studies Gaussian random tensor train vectors as a structured alternative for stochastic trace estimation. We show that, with a suitable choice of the tensor train rank, random tensor train vectors recover dimension-independent guarantees for the Girard--Hutchinson estimator. In particular, a median-of-means variant with tensor train rank

r \geq d-1

achieves the same dependence on the accuracy

\varepsilon

and failure probability

δ

as the classical estimator based on unstructured Gaussian vectors. We further prove an oblivious subspace injection result for sketches formed from independent Gaussian random tensor train vectors: tensor train rank

r\geq d-1

and

\mathcal{O}(\varepsilon^{-2}(k+\log(1/δ)))

samples suffice for a

k

-dimensional target subspace. Finally, we investigate the use of such sketches within the Nyström++ framework. We show that the resulting estimator can achieve the desired

\mathcal{O}(\varepsilon^{-1})

sample complexity under an additional spectral-tail condition. These results provide clarififcation on both the potential and the limitations of random tensor train vectors in stochastic trace estimation.

Zvonimir Bujanović, Daniel Kressner, Hrvoje Olić

University of Zagreb, Faculty of Science, Department of Mathematics, Croatia. · Institute of Mathematics, EPFL, Switzerland.

Tensor Networks Randomized Sketching

Jun 9, 2026math.ST

Bidirectional Random Projections

This paper analyzes bidirectional random projections for ordinary least squares (OLS) regression under the fixed design setting. Let

(X,Y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n

be a sample and

R \in \mathbb{R}^{n_1 \times n}, W \in \mathbb{R}^{p \times p_1}

be two properly distributed random projections. We develop an expected excess loss bound for the OLS estimator built on

(WXR, WY)

. Compared to an established bound for OLS estimator built on

(XR, Y)

, the gap is approximately

O\left( p_1 + C \frac{1}{p_1} \right)

, where

C

scales with

n_1/n

and can be negative for small

n_1/n

. Its implications are confirmed by numerical results on real-world data.

Chao Lan, Luyuan Yang

a School of Computer Science, University of Oklahoma, U.S.

Randomized Sketching Linear Regression Generalization Bounds

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

May 28, 2026cs.LG

The Fast Mixing Mechanism for Differential Privacy

Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, such as the Hadamard matrix, can be applied efficiently and often yield solutions that approximate those of the original problem at much lower computational cost. In differential privacy (DP), Gaussian sketching has been used to solve DP linear regression, beginning with \citet{sheffet2017differentially, sheffet2019old} and later refined by \citet{lev2025gaussianmix, lev2026near}. However, although these methods achieve strong utility guarantees, they usually do not improve runtime over classical DP approaches. In this work, we introduce a new DP sketching mechanism based on fast transforms, which, in certain cases, matches the runtime of classical fast sketching methods. We prove state-of-the-art privacy guarantees for this mechanism and show that, in favorable regimes, they match those of the Gaussian sketch up to a constant factor. As an application, we combine this mechanism with recent sketch-based methods for DP linear regression to obtain a new algorithm with strong utility and improved runtime. We establish privacy and accuracy guarantees for this algorithm, yielding, to the best of our knowledge, the first fast method for DP ordinary least squares.

Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2

Massachusetts Institute of Technology · The Hebrew University of Jerusalem

Randomized Sketching Differential Privacy

May 19, 2026stat.ML

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size

n

from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems

\left( d \in \{2,3\} \right)

, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of

n

and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to

ε

-additive error in expectation with respect to the sampling; we allow

O(1)

computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under

α

-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate

W_2^2(P,Q)

within

ε

error in

ε^{-\max(2,\frac{d+1+o(1)}{1+α})}

time for

0 < α< 1

Hölder smooth distributions

P,Q

on

(0,1)^{d}

; an optimal

Θ(ε^{-2})

for

α> 1/2

when

d=2

and nearly optimal as

α\to 1

when

d = 3

.

Peter Matthew Jacobs, Jeff M. Phillips

Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

Randomized Sketching Approximation Algorithms Optimal Transport Wasserstein Distance

May 18, 2026cs.LG

RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search

Randomized linear algebra (RLA) algorithms are a modern class of numerical linear algebra techniques that play an essential role in scientific computing and machine learning, with broad and growing adoption. However, their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. In this paper, we present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode inductive bias specific to the RLA domain; (2) Monte Carlo Graph Search, which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch, and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability. Code is available at https://github.com/Tim-Xiong/RL4RLA.

Jinglong Xiong, Xiaotian Liu, Ruoxin Wang +4

Pratt School of Engineering, Duke University, Durham, NC, USA · Department of Computer Science, Dartmouth College, Hanover, NH, USA.

Reinforcement Learning Automated Algorithm Discovery Randomized Sketching

May 15, 2026stat.ML

MaxSketch: Robust Distinct Counting in Streams via Random Projections

Estimating the number of distinct elements in a data stream is well understood when repeated elements are identical. In modern settings, however, observations are high-dimensional and noisy, so repeated instances of the same object are only approximately similar -- for example, different images of the same individual may vary significantly at the pixel level. Classical sketches such as HyperLogLog rely on consistent hash values for identical elements and break down in this regime. Recent work on robust distinct counting in general metric spaces achieves

\widetildeΘ(\sqrt{n})

memory, which is tight in the worst case. We show that substantially improved memory guarantees are possible under geometric structure common in learned representations. We introduce MaxSketch, a simple max-linear sketch built from random Gaussian projections, and prove that it succeeds in estimating the number of distinct latent objects. Concretely, we show that under this assumption

m = \widetilde{O} (\log n / \varepsilon^2)

random projections (and hence

\widetilde{O} (\log n/\varepsilon^2)

memory) suffice to recover the true distinct count within a

(1+\varepsilon)

factor. Experiments on image streams confirm that MaxSketch accurately estimates distinct counts and generalizes beyond the training regime. Our results bridge classical streaming algorithms and modern representation learning, showing how geometric structure can fundamentally reduce the complexity of distinct counting.

Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

National and Kapodistrian University of Athens, Greece · Archimedes, Athena Research Center, Greece · The University of Texas at Austin, USA

Randomized Sketching Streaming Algorithms

May 13, 2026cs.LG

Provable Quantization with Randomized Hadamard Transform

Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require

Θ(d^2)

time. The randomized Hadamard transform

HD

reduces this cost to

O(d \log d)

, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies

HD

to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error

\bigl(π\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}

at

b

bits per coordinate, where the

o(1)

term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.

Ying Feng, Piotr Indyk, Michael Kapralov +2

Vector Quantization Randomized Sketching Low-Bit Quantization Neural Network Quantization

May 10, 2026math.NA

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.

Shabarish Chenakkod, Michał Dereziński

University of Michigan, Ann Arbor, MI 48105.

Low-Rank Matrix Decomposition Randomized Sketching Low-Rank Approximation Spectral Methods Singular Value Decomposition

May 7, 2026cs.LG

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is individually distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any

d

-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within

O(d^{-1/2})

of a standard Gaussian both in Kolmogorov distance and in

1

-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, we show that two RHTs may not be sufficient for Vector Quantization (VQ), which often requires weak correlation across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time

{O}(d)

check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.

Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher +2

UCL and Broadcom · Carnegie Mellon University · Harvard University +2

Rotation-Based Quantization Gradient Compression Vector Quantization Randomized Sketching

May 1, 2026math.OC

Randomized Subspace Nesterov Accelerated Gradient

Randomized-subspace methods reduce the cost of first-order optimization by using only low-dimensional projected-gradient information, a feature that is attractive in forward-mode automatic differentiation and communication-limited settings. While Nesterov acceleration is well understood for full-gradient and coordinate-based methods, obtaining accelerated methods for general subspace sketches that use only projected-gradient information and can improve over full-dimensional Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. The key technical ingredient is a three-sequence formulation tailored to matrix smoothness, which recovers the corresponding classical Nesterov methods in the full-dimensional case. The resulting theory establishes accelerated oracle-complexity guarantees and makes explicit how matrix smoothness and the sketch distribution enter the complexity. It also provides a unified basis for comparing sketch families and identifying when randomized-subspace acceleration improves over full-dimensional Nesterov acceleration in oracle complexity.

Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda

Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

Gradient Descent Randomized Sketching Accelerated Gradient Methods

Apr 25, 2026stat.ML

Inference of Online Newton Methods with Nesterov's Accelerated Sketching

Reliable decision-making with streaming data requires principled uncertainty quantification of online methods. While first-order methods enable efficient iterate updates, their inference procedures still require updating proper (covariance) matrices, incurring

O(d^2)

time and memory complexity, and are sensitive to ill-conditioning and noise heterogeneity of the problem. This costly inference task offers an opportunity for more robust second-order methods, which are, however, bottlenecked by solving Newton systems with

O(d^3)

complexity. In this paper, we address this gap by studying an online Newton method with Hessian averaging, where the Newton direction at each step is approximately computed using a sketch-and-project solver with Nesterov's acceleration, matching

O(d^2)

complexity of first-order methods. For the proposed method, we quantify its uncertainty arising from both random data and randomized computation. Under standard smoothness and moment conditions, we establish global almost-sure convergence, prove asymptotic normality of the last iterate with a limiting covariance characterized by a Lyapunov equation, and develop a fully online covariance estimator with non-asymptotic convergence guarantees. We also connect the resulting uncertainty quantification to that of exact and sketched Newton methods without Nesterov's acceleration. Extensive experiments on regression models demonstrate the superiority of the proposed method for online inference.

Haoxuan Wang, Xinchen Du, Sen Na

School of Industrial and Systems Engineering, Georgia Institute of Technology.

Stochastic Approximation Second-Order Optimization Randomized Sketching Covariance Estimation

Apr 22, 2026cs.LG

Analysis of Nystrom method with sequential ridge leverage scores

Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed matrix. The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation. While exact RLSs are as difficult to compute as a KRR solution, we may be able to approximate them well enough. In this paper, we study KRR problems in a sequential setting and introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates. INK-ESTIMATE maintains a small sketch of K_t, that at each step is used to compute an intermediate estimate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel matrix is sufficient. Second, the algorithm requires a fixed, small space budget to run dependent only on the effective dimension of the kernel matrix. Finally, our sketch provides strong approximation guarantees on the distance between the true kernel matrix and its approximation, and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.

Daniele Calandriello, Alessandro Lazaric, Michal Valko

SequeL team INRIA Lille - Nord Europe

Kernel Ridge Regression Kernel Regression Randomized Sketching Spectral Methods Ridge Regression Streaming Algorithms

Apr 14, 2026cs.LG

Does Dimensionality Reduction via Random Projections Preserve Landscape Features?

Exploratory Landscape Analysis (ELA) provides numerical features for characterizing black-box optimization problems. In high-dimensional settings, however, ELA suffers from sparsity effects, high estimator variance, and the prohibitive cost of computing several feature classes. Dimensionality reduction has therefore been proposed as a way to make ELA applicable in such settings, but it remains unclear whether features computed in reduced spaces still reflect intrinsic properties of the original landscape. In this work, we investigate the robustness of ELA features under dimensionality reduction via Random Gaussian Embeddings (RGEs). Starting from the same sampled points and objective values, we compute ELA features in projected spaces and compare them to those obtained in the original search space across multiple sample budgets and embedding dimensions. Our results show that linear random projections often alter the geometric and topological structure relevant to ELA, yielding feature values that are no longer representative of the original problem. While a small subset of features remains comparatively stable, most are highly sensitive to the embedding. Moreover, robustness under projection does not necessarily imply informativeness, as apparently robust features may still reflect projection-induced artifacts rather than intrinsic landscape characteristics.

Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck +1

Leiden Institute of Advanced Computer Science, Leiden University · Leiden, The Netherlands · RTWH Aachen University +1

Black-Box Optimization Randomized Sketching Dimensionality Reduction

Mar 15, 2026cs.LG

On the (Generative) Linear Sketching Problem

Sketch techniques have been extensively studied in recent years and are especially well-suited to data streaming scenarios, where the sketch summary is updated quickly and compactly. However, it is challenging to recover the current state from these summaries in a way that is accurate, fast, and real. In this paper, we seek a solution that reconciles this tension, aiming for near-perfect recovery with lightweight computational procedures. Focusing on linear sketching problems of the form

\boldsymbolΦf \rightarrow f

, our study proceeds in three stages. First, we dissect existing techniques and show the root cause of the sketching dilemma: an orthogonal information loss. Second, we examine how generative priors can be leveraged to bridge the information gap. Third, we propose FLORE, a novel generative sketching framework that embraces these analyses to achieve the best of all worlds. More importantly, FLORE can be trained without access to ground-truth data. Comprehensive evaluations demonstrate FLORE's ability to provide high-quality recovery, and support summary with low computing overhead, outperforming previous methods by up to 1000 times in error reduction and 100 times in processing speed compared to learning-based solutions.

Xinyu Yuan, Yan Qiao, Zonghui Wang +1

College of Computer Science and Technology, Zhejiang University, Hangzhou, China · School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China

Unsupervised Learning Randomized Sketching

Oct 27, 2025cs.LG

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation

Approximate Nearest Neighbor (ANN) search and Approximate Kernel Density Estimation (A-KDE) are fundamental problems at the core of modern machine learning, with broad applications in data analysis, information systems, and large-scale decision making. In massive and dynamic data streams, a central challenge is to design compact sketches that preserve essential structural properties of the data while enabling efficient queries. In this work, we develop new sketching algorithms that achieve sublinear space and query time guarantees for both ANN and A-KDE for a dynamic stream of data. For ANN in the streaming model, under natural assumptions, we design a sublinear sketch that requires only

\mathcal{O}(n^{(1-η)(1+ρ)})

memory by storing only a sublinear (

n^{-η}

) fraction of the total inputs, where

ρ

is a parameter of the LSH family, and

0<η<1

. Our method supports sublinear query time, batch queries, and extends to the more general Turnstile model. While earlier works have focused on Exact NN, this is the first result on ANN that achieves near-optimal trade-offs between memory size and approximation error. Next, for A-KDE in the Sliding-Window model, we propose a sketch of size

\mathcal{O}\left(LW \cdot \frac{1}{\sqrt{1+ε} - 1} \log^2 N\right)

, where

L

is the number of sketch rows,

W

is the LSH range,

N

is the window size, and

ε

is the approximation error. This, to the best of our knowledge, is the first theoretical sublinear sketch guarantee for A-KDE in the Sliding-Window model. We complement our theoretical results with experiments on various real-world datasets, which show that the proposed sketches are lightweight and achieve consistently low error in practice.

Ved Danait, Srijan Das, Sujoy Bhore

Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Computer Science & Engineering and Centre for Machine Intelligence & Data Science (CMINDS), Indian Institute of Technology Bombay, Mumbai, India.

Randomized Sketching Kernel Density Estimation Approximate Nearest Neighbor Search Streaming Algorithms

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

Oct 2, 2025cs.LG

Geometrically Principled Randomized Optimization for Efficient LLM Training

Low-rank gradient optimization for large language models is currently divided into two categories: structured methods that rigorously identify subspaces, and randomized approaches employed primarily for computational efficiency. In this work, we question the intuition behind why random projections are effective. We trace this phenomenon to the geometry of the gradient subspaces, which exhibits subspace optimization landscape has a nearly flat curvature, while a significant portion of gradient information lies outside the core subspace. Leveraging these insights, and drawing on randomized linear algebra, we theoretically establish that random low-rank projections preserve the geometry, and we introduce GrassWalk and GrassJump, algorithms that navigate the Grassmannian manifold via random walks and jumps. By coupling this randomized exploration with subspace-aware optimizer and recovering the lost gradient signals, we achieve state-of-the-art results on LLaMA-1B, LLaMA-7B, and Qwen-1.5B pretraining. Our findings reframe randomization not merely as a computational shortcut, but as a geometrically principled approach to high-dimensional optimizations.

Sahar Rajabi, Nayeema Nonta, Sirisha Rambhatla

CriticalML Lab, University of Waterloo

Language Model Pretraining Deep Learning Optimization Riemannian Optimization Randomized Sketching LLM Training

Date pendingcs.LG

When do cheap embeddings beat protein language models? A theoretically-grounded hashing sketch for biological sequence classification

\textbf{Motivation:} Pre-trained protein language models (PLMs) such as ESM-2 have become the default representation for biological sequence tasks, but they are computationally heavy and require GPUs both for embedding and for fine-tuning. Whether they are actually necessary for sequence \emph{classification}, as opposed to structure prediction, is rarely tested against strong, principled, lightweight alternatives. This question has direct practical stakes for large-scale genomic surveillance, where embedding millions of sequences on commodity hardware is a recurring bottleneck.\ \textbf{Results:} We introduce Murmur2Vec, an alignment-free, training-free embedding that aggregates

k

-mer counts into a small hash table via the deterministic MurmurHash function, and we cast it as a randomized sketch of the classical

k

-mer spectrum kernel. We provide a complete theoretical treatment: closed-form bias/variance of the inner product, an unbiased signed variant with a Johnson--Lindenstrauss-type concentration bound, an excess-risk bound for downstream linear classifiers that makes the bias--variance trade-off in the hash-table size explicit, and an implicit-regularization mechanism by which collisions damage frequent non-discriminative

k

-mers more than rare lineage-defining ones. Across four classification tasks, SARS-CoV-2 spike lineage (22 classes), HIV-1 Env subtype (8 classes), and two protein-family benchmarks (8 and 6 classes), Murmur2Vec matches a LoRA-fine-tuned 650M-parameter ESM-2 model on the two tasks for which LoRA fine-tuning was run to convergence (SARS-CoV-2 and HIV-1) and ties frozen ESM-2 on the two protein-family tasks, and it \emph{outperforms} the fine-tuned model on the hardest task (SARS-CoV-2 lineage:

0.854

vs.\

0.807

accuracy; macro-F1

0.684

vs.\

0.401

).

Sarwan Ali, Taslim Murad, Imdadullah Khan +1

Columbia University, NY, USA · Institute of Business Administration, Karachi, Pakistan · Lahore University of Management Sciences, Lahore, Pakistan +1

Protein Language Models Randomized Sketching Kernel Methods Protein Representation Learning Sequence Modeling