# Fast and Strong Convergence of Online Learning Algorithms

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2017.

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

- [Capacity dependent analysis for functional online learning algorithms](https://mlsanity.com/paper/2209.12198/) (2022)
- [Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay](https://mlsanity.com/paper/2602.06797/) (2026)
- [Optimality of Robust Online Learning](https://mlsanity.com/paper/2304.10060/) (2023)
- [Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2407.07670/) (2024)
- [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)
- [Convergence analysis of online algorithms for vector-valued kernel regression](https://mlsanity.com/paper/2309.07779/) (2023)

## Abstract (arXiv)

In this paper, we study the online learning algorithm without explicit regularization terms. This algorithm is essentially a stochastic gradient descent scheme in a reproducing kernel Hilbert space (RKHS). The polynomially decaying step size in each iteration can play a role of regularization to ensure the generalization ability of online learning algorithm. We develop a novel capacity dependent analysis on the performance of the last iterate of online learning algorithm. The contribution of this paper is two-fold. First, our nice analysis can lead to the convergence rate in the standard mean square distance which is the best so far. Second, we establish, for the first time, the strong convergence of the last iterate with polynomially decaying step sizes in the RKHS norm. We demonstrate that the theoretical analysis established in this paper fully exploits the fine structure of the underlying RKHS, and thus can lead to sharp error estimates of online learning algorithm.