# Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oracles

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 11 references that are in the map.
- First posted on arXiv 15 May 2024.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Automatic LQR Tuning Based on Gaussian Process Global Optimization](https://mlsanity.com/paper/1605.01950/) (2016)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)

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

- [Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2505.02281/) (2025)
- [Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles](https://mlsanity.com/paper/2510.15257/) (2025)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability](https://mlsanity.com/paper/2604.25372/) (2026)

## Abstract (arXiv)

The application of a zeroth-order scheme for minimising Polyak-Lojasewicz (PL) functions is considered. The framework is based on exploiting a random oracle to estimate the function gradient. The convergence of the algorithm to a global minimum in the unconstrained case and to a neighbourhood of the global minimum in the constrained case along with their corresponding complexity bounds are presented. The theoretical results are demonstrated via numerical examples.