Convergence of zeroth-order proximal point algorithms in the high-temperature regime
Emanuele Naldi, Hippolyte Labarrière, Cesare Molinari, Silvia Villa · 2026
Read Convergence of zeroth-order proximal point algorithms in the high-temperature regime by Emanuele Naldi, Hippolyte Labarrière, Cesare Molinari, Silvia Villa (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11929.txt.
Introduction
Emanuele Naldi and three colleagues analyze zeroth-order proximal point methods at fixed temperature above zero, the regime where sampling-based guesses stay usable. Earlier theory leaned on fading temperature, where Monte Carlo guesses suffer severe variance. They show the method equals an exact proximal point method on a helper smoothed goal. It settles with little assumed, and the smoothed problem links back to the first goal with clear bounds.
Catalog record
| CREATOR | Emanuele Naldi, Hippolyte Labarrière, Cesare Molinari, Silvia Villa |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 6337 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence of zeroth-order proximal point algorithms in the high-temperature regime
Emanuele Naldi, Hippolyte Labarrière, Cesare Molinari, Silvia Villa
Abstract
Efficient methods for non-convex black-box optimization largely rely on sampling. In this context, the Zeroth-Order Proximal Operator (ZOPO) and the corresponding Zeroth-Order Proximal Point Algorithm (ZOPPA) have attracted significant interest, as they combine the advantage of requiring only objective evaluations with the powerful theoretical framework of proximal point algorithms. ZOPO depends on a temperature parameter which, when going to zero, reduces ZOPO to the exact proximal operator. By exploiting this property, the vanishing-temperature regime has been leveraged in several works to obtain theoretical guarantees via inexact proximal methods. However, this regime is computationally unsustainable when sampling is used to estimate ZOPO, since the corresponding Monte Carlo estimators suffer from severe variance issues. We therefore propose a comprehensive analysis of ZOPO for any fixed positive temperature, and prove convergence of ZOPPA under minimal assumptions on the objective function. We do so by demonstrating that ZOPPA can be interpreted as an exact proximal point method applied to an auxiliary smoothed objective, rather than an inexact method on the original function. Importantly, we further derive explicit guarantees connecting this smoothed problem back to the original objective and establish convergence results for the sampled method (S-ZOPPA) at a fixed temperature.
1
Introduction
We consider the problem of minimizing a function through pointwise evaluations only. More precisely, given an objective
f:\mathbb{R}^{d}\to\mathbb{R}
, we seek to solve
\min_{x\in\mathbb{R}^{d}}f(x),
(P)
in a setting where derivatives of
f
are unavailable, or too costly to compute. Such problems are commonly referred to as zeroth-order, derivative-free, or black-box optimization problems
Spall
;
Conn2009
;
Larson2019
. They arise whenever the objective is specified implicitly through a simulation or a complex computational pipeline, so that optimization must proceed from function values alone
Salimans2017EvolutionSA
;
Mania18
;
pmlr-v80-choromanski18a
;
flaxman2005online
.
In machine learning, black-box optimization arises for instance in adversarial attacks
chen2017zoo
and to overcome the extreme memory requirements of standard backpropagation during LLMs fine tuning
zhang2024revisiting
.
A common strategy in zeroth-order optimization is to use function evaluations to recover, either explicitly or implicitly, local first-order information
Spall
;
Conn2009
. Finite-difference and random-direction methods
Conn2009
;
nest
follow this principle by constructing gradient surrogates and then embedding them in variants of gradient descent. This viewpoint has led to a rich class of algorithms and convergence guarantees. However, gradient descent is only one of the basic mechanisms underlying first-order optimization
BeckBook
. Another central object for first order optimization is the proximal operator, which provides stable implicit updates and plays a fundamental role in optimization, variational analysis, and splitting methods
combettes2005signal
. The question whether it is possible to design zeroth order analogues of proximal algorithms has been recently answered in
osher2023hamilton
(see also
crandall1984
), where the Zeroth-Order Proximal Operator (ZOPO) has been introduced. Given parameters
\lambda>0
and
\delta>0
, ZOPO is
defined by
\operatorname{zprox}^{\delta}_{\lambda,f}(x)=\frac{\mathbb{E}_{y\sim\mathcal{N}(x,\lambda\delta I)}\left[y\exp(-f(y)/\delta)\right]}{\mathbb{E}_{y\sim\mathcal{N}(x,\lambda\delta I)}\left[\exp(-f(y)/\delta)\right]}.
(1)
This operator replaces the variational minimization defining the classical proximal map by a
Gibbs-weighted average of zeroth-order queries around the current point. Points with lower objective
value receive exponentially larger weight, yielding an implicit descent mechanism that uses only
function evaluations. The ideal zeroth-order proximal point method, which we call ZOPPA
osher2023hamilton
(also introduced as Consensus Hopping (CH) in
Fornasier2024
), iterates
x^{k+1}=\operatorname{zprox}^{\delta}_{\lambda,f}(x^{k}).
(2)
Although this update is conceptually simple, the expectations in (
1
) are
typically intractable. We therefore consider its Monte Carlo approximation, the Stochastic
Zeroth-Order Proximal Point Algorithm (S-ZOPPA):
x^{k+1}=\frac{\sum_{i=1}^{N}y_{i}\exp(-f(y_{i})/\delta)}{\sum_{i=1}^{N}\exp(-f(y_{i})/\delta)},\qquad y_{i}\sim\mathcal{N}(x^{k},\lambda\delta I).
(3)
Thus, ZOPPA is the population-level proximal iteration, while S-ZOPPA is its practical sampled implementation. This distinction allows us to separate the deterministic properties of the zeroth-order proximal map from the statistical error introduced by Monte Carlo sampling.
The high-temperature regime.
The main contribution of this work is to focus on the behavior of ZOPPA and S-ZOPPA when the temperature parameter
\delta
is bounded away from
0
. This perspective distinguishes this paper from the increasing number of works
osher2023hamilton
;
zhang2024inexact
;
di2026operator
;
Fornasier2026
that build on the vanishing-temperature regime and the inexact proximal operator viewpoint and is particularly motivated by sampling issues. Indeed, S-ZOPPA is built around a Monte Carlo estimation of ZOPO (
1
) which has the property of tending to the exact value of the proximal operator when
\delta\to 0
(see the orange curve on Figure
(c)). However, estimating it turns back to approximating
\int\exp(-f(y)/\delta)\exp(-\|x-y\|^{2}/2\lambda\delta)dy
which is increasingly hard as
\delta
goes to
0
(see (a) and (b) in Figure
). This ultimately leads to extremely inaccurate approximations when
\delta
is small, for Monte Carlo estimation with a fixed number of samples, as shown by the blue curve in Figure
(c). This illustrates that, already in this simple example, the most reliable sampling regime is not the vanishing-temperature limit, but an intermediate range of positive temperatures where ZOPO remains close to the proximal point while its Monte Carlo approximation is still stable.
(a) Large
\delta
-2
0
2
4
0
0.5
1
y
(b) Small