Nyström Method

Latest papers

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

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
Oct 22, 2026Caixing Wang, Yue WangGeneralization Bounds Spectral Methods
School of Statistics and Data Science, Southeast University, Nanjing, 210000, Jiangsu, China · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China, Hefei, 230000, Anhui, China
Revisited Support Vector Machines: A Unified Joint Optimization Framework with Nyström Approximation for Scalable Adaptive Learning
Oct 11, 2026Nassou Gongon Benjamin, Noulapeu Ngaffo, Patrick Njionou SadjangNyström Method Support Vector Machines
Laboratory of Data Science and Artificial Intelligence (LSDIA), National Higher Polytechnic School of Douala (ENSPD), University of Douala, Cameroon · Department of Computer Sciences, National Higher Polytechnic School of Douala (ENSPD), University of Douala, Cameroon · Department of Basic Scientific Education, National Higher Polytechnic School of Douala (ENSPD), University of Douala, Cameroon
BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
Oct 9, 2026Giordano Vitale, Giacomo Meanti, Marco Rando +2Nyström Method Kernel Ridge Regression
MaLGa Center, DIBRIS, Universit`a degli Studi di Genova, Genoa, Italy · Universit´e Cˆote d’Azur, INRIA, CNRS, LJAD, Nice, France · Dipartimento di Matematica e Applicazioni, Universit`a degli Studi Milano–Bicocca, Italy +2
Clean: Second-order LLM Training at Linear Memory Cost via Nystr{ö}m Sketching
Oct 3, 2026Beheshteh T. Rakhshan, Sahar Rajabi, Maziar Sargordi +3Nyström Method Optimizer State Compression
Mila & DIRO, Université de Montréal · Critical ML, University of Waterloo · Independent Researcher +2
Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method
Aug 7, 2026Quanling Zhao, Anthony Hitchcock Thomas, Ari Brin +2Nyström Method Hyperdimensional Computing
Department of Computer Science and Engineering, UC San Diego
Convergence Analysis of Nyström Subsampling in Covariate Shift Adaptation for Misspecified case
Jun 20, 2026Hanna Myleiko, Sergei Solodky, Vasyl SemenovUnsupervised Domain Adaptation Domain Adaptation
Institute of Mathematics NAS of Ukraine, 3 Tereschenkivska st., Kyiv, Ukraine. · Institute of Mathematics NAS of Ukraine, 3 Tereschenkivska st., Kyiv, Ukraine · University of Giessen, Department of Mathematics, Giessen, Germany. +1
Spectral Anatomy of Quantum Gaussian Process Kernels
May 29, 2026Jian Xu, Chao Li, Guang Lin +4Nyström Method Quantum Machine Learning
1RIKEN iTHEMS · 2RIKEN AIP · 3South China University of Technology +1
Nyström Kernel Stein Discrepancy Tests
May 24, 2026Florian Kalinke, Zoltán Szabó, Bharath K. SriperumbudurGoodness-of-Fit Testing Nyström Method
Chair of Information Systems Karlsruhe Institute of Technology Am Fasanengarten 5, 76131 Karlsruhe, Germany · Department of Statistics London School of Economics Houghton Street, London, WC2A 2AE, UK · Department of Statistics The Pennsylvania State UniversityMay University Park, PA 16802, USA
FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling
May 12, 2026Hongmin LiUnsupervised Learning Nyström Method
School of Life Science and Technology, Institute of Science Tokyo · 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan 2Department of Computational Biology and Medical Sciences Graduate School of Frontier Sciences, The University of Tokyo
Nearly Optimal Algorithms for Adversarial Kernelized Bandits
May 11, 2026Shogo IwazakiMulti-Armed Bandits Nyström Method
LY Corporation, Tokyo, Japan
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
May 10, 2026Shabarish Chenakkod, Michał DerezińskiLow-Rank Matrix Decomposition Nyström Method
University of Michigan, Ann Arbor, MI 48105.
Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
Apr 24, 2026Daniele Calandriello, Alessandro Lazaric, Michal ValkoKernel Ridge Regression Kernel Regression
SequeL team, INRIA Lille - Nord Europe, France
LaplacianFormer:Rethinking Linear Attention with Laplacian Kernel
Apr 22, 2026Zhe Feng, Sen Lian, Changwei Wang +5Nyström Method Efficient ViTs
1MAIS,Institute of Automation, Chinese Academy of Sciences · usr 3China Electronics Data Corporation · 5The Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center, Qilu University of Technology +4
Analysis of Nystrom method with sequential ridge leverage scores
Apr 22, 2026Daniele Calandriello, Alessandro Lazaric, Michal ValkoKernel Ridge Regression Kernel Regression
SequeL team INRIA Lille - Nord Europe
Subspace Kernel Learning on Tensor Sequences
Mar 20, 2026Lei Wang, Xi Ding, Yongsheng Gao +1Nyström Method Kernel Methods
Griffith University · Data61 CSIRO · University of New South Wales
From Shallow Bayesian Neural Networks to Gaussian Processes: General Convergence, Identifiability and Scalable Inference
Feb 26, 2026Gracielle Antunes de Araújo, Flávio B. GonçalvesNyström Method Bayesian Neural Networks
Universidade do Estado de Minas Gerais (UEMG), FaEnge – Faculdade de Engenharia. · Universidade Federal de Minas Gerais (UFMG), ICEx – Instituto de Ciências Exatas.

Oct 22, 2026J/K move · Enter open · S save

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

Caixing Wang, Yue Wang

School of Statistics and Data Science, Southeast University, Nanjing, 210000, Jiangsu, China · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China, Hefei, 230000, Anhui, China

Generalization Bounds Spectral Methods Randomized Sketching Nyström Method

Open paper AskPDF arXiv

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e.,

s> α_0-1/β

, where

s,β

, and

α_0

denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when

α_0=1/β

, the optimality holds for all

s\in (0,2τ]

with

τ

and

γ

denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.