# On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 16 Apr 2022.

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

- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [A Generic Acceleration Framework for Stochastic Composite Optimization](https://mlsanity.com/paper/1906.01164/) (2019)
- [Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2011.02522/) (2020)
- [An acceleration of decentralized SGD under general assumptions with low stochastic noise](https://mlsanity.com/paper/2011.07585/) (2020)
- [Catalyst Acceleration for Gradient-Based Non-Convex Optimization](https://mlsanity.com/paper/1703.10993/) (2017)

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

- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

We study the acceleration of the Local Polynomial Interpolation-based Gradient Descent method (LPI-GD) recently proposed for the approximate solution of empirical risk minimization problems (ERM). We focus on loss functions that are strongly convex and smooth with condition number σ. We additionally assume the loss function is η-H"older continuous with respect to the data. The oracle complexity of LPI-GD is tildeOleft(σ md log(1/varepsilon)right) for a desired accuracy varepsilon, where d is the dimension of the parameter space, and m is the cardinality of an approximation grid. The factor md can be shown to scale as O((1/varepsilon)d/2η). LPI-GD has been shown to have better oracle complexity than gradient descent (GD) and stochastic gradient descent (SGD) for certain parameter regimes. We propose two accelerated methods for the ERM problem based on LPI-GD and show an oracle complexity of tildeOleft(√σ md log(1/varepsilon)right). Moreover, we provide the first empirical study on local polynomial interpolation-based gradient methods and corroborate that LPI-GD has better performance than GD and SGD in some scenarios, and the proposed methods achieve acceleration.