# Optimality of Robust Online Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 58 references that are in the map.
- First posted on arXiv 20 Apr 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Unregularized Online Learning Algorithms with General Loss Functions](https://mlsanity.com/paper/1503.00623/) (2015)
- [Capacity dependent analysis for functional online learning algorithms](https://mlsanity.com/paper/2209.12198/) (2022)
- [Optimal Rates for Multi-pass Stochastic Gradient Methods](https://mlsanity.com/paper/1605.08882/) (2016)
- [Fast and Strong Convergence of Online Learning Algorithms](https://mlsanity.com/paper/1710.03600/) (2017)
- [A Framework of Learning Through Empirical Gain Maximization](https://mlsanity.com/paper/2009.14250/) (2020)
- [Learning with incremental iterative regularization](https://mlsanity.com/paper/1405.0042/) (2014)

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

- [Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay](https://mlsanity.com/paper/2602.06797/) (2026)
- [Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2407.07670/) (2024)
- [Theory of Decentralized Robust Kernel-Based Learning](https://mlsanity.com/paper/2506.05215/) (2025)
- [Stress-Aware Learning under KL Drift via Trust-Decayed Mirror Descent](https://mlsanity.com/paper/2510.15222/) (2025)
- [Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms](https://mlsanity.com/paper/2609.11712/) (2026)

## Abstract (arXiv)

In this paper, we study an online learning algorithm with a robust loss function Lσ for regression over a reproducing kernel Hilbert space (RKHS). The loss function Lσ involving a scaling parameter σ>0 can cover a wide range of commonly used robust losses. The proposed algorithm is then a robust alternative for online least squares regression aiming to estimate the conditional mean function. For properly chosen σ and step size, we show that the last iterate of this online algorithm can achieve optimal capacity independent convergence in the mean square distance. Moreover, if additional information on the underlying function space is known, we also establish optimal capacity dependent rates for strong convergence in RKHS. To the best of our knowledge, both of the two results are new to the existing literature of online learning.