# Unregularized Online Learning Algorithms with General Loss Functions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2015.

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

- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning](https://mlsanity.com/paper/2412.01773/) (2024)
- [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)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (2022)
- [Differentially Private Stochastic Gradient Descent with Low-Noise](https://mlsanity.com/paper/2209.04188/) (2022)
- [Three rates of convergence or separation via U-statistics in a dependent framework](https://mlsanity.com/paper/2106.12796/) (2021)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)

## Abstract (arXiv)

In this paper, we consider unregularized online learning algorithms in a Reproducing Kernel Hilbert Spaces (RKHS). Firstly, we derive explicit convergence rates of the unregularized online learning algorithms for classification associated with a general gamma-activating loss (see Definition 1 in the paper). Our results extend and refine the results in Ying and Pontil (2008) for the least-square loss and the recent result in Bach and Moulines (2011) for the loss function with a Lipschitz-continuous gradient. Moreover, we establish a very general condition on the step sizes which guarantees the convergence of the last iterate of such algorithms. Secondly, we establish, for the first time, the convergence of the unregularized pairwise learning algorithm with a general loss function and derive explicit rates under the assumption of polynomially decaying step sizes. Concrete examples are used to illustrate our main results. The main techniques are tools from convex analysis, refined inequalities of Gaussian averages, and an induction approach.