# Fully Implicit Online Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2018.

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

- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Implicit Parameter-free Online Learning with Truncated Linear Models](https://mlsanity.com/paper/2203.10327/) (2022)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [Online Saddle Point Problem and Online Convex-Concave Optimization](https://mlsanity.com/paper/2312.06957/) (2023)

## Abstract (arXiv)

Regularized online learning is widely used in machine learning applications. In online learning, performing exact minimization (i.e., implicit update) is known to be beneficial to the numerical stability and structure of solution. In this paper we study a class of regularized online algorithms without linearizing the loss function or the regularizer, which we call fully implicit online learning (FIOL). We show that for arbitrary Bregman divergence, FIOL has the O(√T) regret for general convex setting and O(log T) regret for strongly convex setting, and the regret has an one-step improvement effect because it avoids the approximation error of linearization. Then we propose efficient algorithms to solve the subproblem of FIOL. We show that even if the solution of the subproblem has no closed form, it can be solved with complexity comparable to the linearized online algoritms. Experiments validate the proposed approaches.