# Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 27 references that are in the map.
- First posted on arXiv 26 Jul 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility](https://mlsanity.com/paper/1605.01418/) (2016)
- [A Model-Based Method for Minimizing CVaR and Beyond](https://mlsanity.com/paper/2305.17498/) (2023)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)

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

- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Stochastic Gradient Descent with Preconditioned Polyak Step-size](https://mlsanity.com/paper/2310.02093/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Taking the Road Less Scheduled with Adaptive Polyak Steps](https://mlsanity.com/paper/2511.07767/) (2025)
- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler](https://mlsanity.com/paper/2606.01827/) (2026)

## Abstract (arXiv)

Here we develop variants of SGD (stochastic gradient descent) with an adaptive step size that make use of the sampled loss values. In particular, we focus on solving a finite sum-of-terms problem, also known as empirical risk minimization. We first detail an idealized adaptive method called textttSPS_+ that makes use of the sampled loss values and assumes knowledge of the sampled loss at optimality. This textttSPS_+ is a minor modification of the SPS (Stochastic Polyak Stepsize) method, where the step size is enforced to be positive. We then show that textttSPS_+ achieves the best known rates of convergence for SGD in the Lipschitz non-smooth. We then move onto to develop textttFUVAL, a variant of textttSPS_+ where the loss values at optimality are gradually learned, as opposed to being given. We give three viewpoints of textttFUVAL, as a projection based method, as a variant of the prox-linear method, and then as a particular online SGD method. We then present a convergence analysis of textttFUVAL and experimental results. The shortcomings of our work is that the convergence analysis of textttFUVAL shows no advantage over SGD. Another shortcomming is that currently only the full batch version of textttFUVAL shows a minor advantages of GD (Gradient Descent) in terms of sensitivity to the step size. The stochastic version shows no clear advantage over SGD. We conjecture that large mini-batches are required to make textttFUVAL competitive. Currently the new textttFUVAL method studied in this paper does not offer any clear theoretical or practical advantage. We have chosen to make this draft available online nonetheless because of some of the analysis techniques we use, such as the non-smooth analysis of textttSPS_+, and also to show an apparently interesting approach that currently does not work.