# The Nystr"om method for convex loss functions

arXiv: https://arxiv.org/abs/2006.10016 · HTML: https://mlsanity.com/paper/2006.10016/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Error Scaling Laws for Kernel Classification under Source and Capacity Conditions](https://mlsanity.com/paper/2201.12655/) (2022)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (2021)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Kernel Density Machines](https://mlsanity.com/paper/2504.21419/) (2025)
- [Interpretable Self-Supervised Learning via Representer Landmarks and Nystr"om Approximation](https://mlsanity.com/paper/2509.24467/) (2025)
- [Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketches](https://mlsanity.com/paper/2110.09042/) (2021)
- [Snacks: a fast large-scale kernel SVM solver](https://mlsanity.com/paper/2304.07983/) (2023)
- [Error Propagation in Dynamic Programming: From Stochastic Control to American Option Pricing](https://mlsanity.com/paper/2509.20239/) (2025)

## Abstract (arXiv)

We investigate an extension of classical empirical risk minimization, where the hypothesis space consists of a random subspace within a given Hilbert space. Specifically, we examine the Nystr"om method where the subspaces are defined by a random subset of the data. This approach recovers Nystr"om approximations used in kernel methods as a specific case. Using random subspaces naturally leads to computational advantages, but a key question is whether it compromises the learning accuracy. Recently, the tradeoffs between statistics and computation have been explored for the square loss and self-concordant losses, such as the logistic loss. In this paper, we extend these analyses to general convex Lipschitz losses, which may lack smoothness, such as the hinge loss used in support vector machines. Our main results show the existence of various scenarios where computational gains can be achieved without sacrificing learning performance. When specialized to smooth loss functions, our analysis recovers most previous results. Moreover, it allows to consider classification problems and translate the surrogate risk bounds into classification error bounds. Indeed, this gives the opportunity to compare the effect of Nystr"om approximations when combined with different loss functions such as the hinge or the square loss.