# Capacity dependent analysis for functional online learning algorithms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 25 Sep 2022.

## Builds on (most cited first, 5 of 5)

- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [Fast and Strong Convergence of Online Learning Algorithms](https://mlsanity.com/paper/1710.03600/) (2017)
- [Generalization Properties of Doubly Stochastic Learning Algorithms](https://mlsanity.com/paper/1707.00577/) (2017)

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

- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Adaptive learning of density ratios in RKHS](https://mlsanity.com/paper/2307.16164/) (2023)
- [Optimality of Robust Online Learning](https://mlsanity.com/paper/2304.10060/) (2023)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2407.07670/) (2024)
- [Spectral Algorithms under Covariate Shift](https://mlsanity.com/paper/2504.12625/) (2025)
- [Online Regularized Learning Algorithm for Functional Data](https://mlsanity.com/paper/2211.13549/) (2022)
- [Distributed Gradient Descent for Functional Learning](https://mlsanity.com/paper/2305.07408/) (2023)
- [On regularized polynomial functional regression](https://mlsanity.com/paper/2311.03036/) (2023)
- [A Kernel-based Stochastic Approximation Framework for Nonlinear Operator Learning](https://mlsanity.com/paper/2509.11070/) (2025)

## Abstract (arXiv)

This article provides convergence analysis of online stochastic gradient descent algorithms for functional linear models. Adopting the characterizations of the slope function regularity, the kernel space capacity, and the capacity of the sampling process covariance operator, significant improvement on the convergence rates is achieved. Both prediction problems and estimation problems are studied, where we show that capacity assumption can alleviate the saturation of the convergence rate as the regularity of the target function increases. We show that with properly selected kernel, capacity assumptions can fully compensate for the regularity assumptions for prediction problems (but not for estimation problems). This demonstrates the significant difference between the prediction problems and the estimation problems in functional data analysis.