## GRADIENT-FREE OPTIMIZATION VIA INTEGRATION

Christophe Andrieu , Nicolas Chopin , Ettore Fincato , Mathieu Gerber 1 2 1

## 1 1 University of Bristol 2 ENSAE, Institut Polytechnique de Paris

Abstract . In this paper we propose a novel, general purpose, algorithm to optimize functions l : R d → R not assumed to be convex or differentiable or even continuous. The main idea is to sequentially fit a sequence of parametric probability densities, possessing a concentration property, to l using a Bayesian update followed by a reprojection back onto the chosen parametric sequence. Remarkably, with the sequence chosen to be from the exponential family, reprojection essentially boils down to the computation of expectations. Our algorithm therefore lends itself to Monte Carlo approximation, ranging from plain to Sequential Monte Carlo (SMC) methods. The algorithm is therefore particularly simple to implement and we illustrate performance on a challenging Machine Learning classification problem. Our methodology naturally extends to the scenario where only noisy measurements of l are available and retains ease of implementation and performance. At a theoretical level we establish, in a fairly general scenario, that our framework can be viewed as implicitly implementing a time inhomogeneous gradient descent algorithm on a sequence of smoothed approximations of l . This opens the door to establishing convergence of the algorithm and provide theoretical guarantees. Along the way, we establish new results for inhomogeneous gradient descent algorithms of independent interest.

Keywords : Gradient-Free Optimisation, Sequential Monte Carlo, Bayesian Updating, Variational methods, Smoothing.

## Contents

| 1. Introduction                                                          |   3 |
|--------------------------------------------------------------------------|-----|
| 2. Experiments                                                           |   7 |
| 3. Results on gradient descent with smooth approximations                |   9 |
| 3.1. Lower-semi continuity . . . . . . . . . . . . . . . . . . . . . . . |  10 |
| 3.2. Epi-convergence and convergence in minimisation . . . . . . . .     |  11 |
| 3.3. Stability and convergence of time-inhomogeneous gradient descent    |  14 |
| 4. Convergence of Alg. 1: deterministic scenario                         |  16 |
| 4.1. Epi-convergence of Laplace functionals . . . . . . . . . . . . . .  |  16 |
| 4.2. Descent lemma for Laplace functionals . . . . . . . . . . . . . .   |  19 |
| 4.3. Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . .  |  20 |
| 5. Discussion                                                            |  22 |
| A. Notation                                                              |  25 |
| B. Exponential family background                                         |  25 |
| B.1. Natural exponential families . . . . . . . . . . . . . . . . . . .  |  25 |
| B.2. Exponential dispersion models . . . . . . . . . . . . . . . . . .   |  27 |
| B.3. EDM example: Wishart distribution . . . . . . . . . . . . . . .     |  27 |
| B.4. EDM example: Beta distribution . . . . . . . . . . . . . . . . .    |  28 |
| C. More details on lower semi-continuity and epi-convergence             |  29 |
| C.1. Lower semi-continuity . . . . . . . . . . . . . . . . . . . . . . . |  29 |
| C.2. Epi-graphical closure . . . . . . . . . . . . . . . . . . . . . . . |  30 |
| C.3. Epi-convergence . . . . . . . . . . . . . . . . . . . . . . . . . . |  30 |
| D. Laplace Principle                                                     |  33 |
| E. Additional results from numerical experiments: impact of rescaling    |  34 |

All notation can be found in Appendix A.

## 1. Introduction

̸

Let l : X := R d → R be a lower-semicontinuous, potentially non-differentiable function such that inf x ∈ R d l ( x ) &gt; -∞ and hence arg min x ∈ K l ( x ) = ∅ for any compact set K ⊂ X . This manuscript is concerned with gradient free algorithms to minimize functions within this class, both in the scenario where l can be evaluated pointwise or only unbiased and independent noisy measurements are available, formalised as l ( x ) := E ( ℓ x, U ( )) for U ∈ U drawn from a distribution independent of x ∈ R d , where ℓ : R d × U → R can be evaluated pointwise.

Noiseless scenario In the scenario where l ( ) · can be evaluated pointwise, the main idea of the class of algorithms we propose can be easily understood with the following particular example. Let ϕ d be the density of the standard normal distribution N (0 , I d ) and define π θ,γ ( x ) := γ -d/ 2 ϕ d ( γ -1 / 2 ( x -θ ) ) for θ ∈ Θ = R d , γ &gt; 0 . Then, for a sequence { γ n ≥ 0 , n ∈ N } such that γ n ↓ 0 define sequentially the families of distributions { π , n n ∈ N } and { ˜ π , n n ∈ N } as in Alg. 1.

## Algorithm 1 Deterministic Gradient-Free Ideal Algorithm

↦

## Input:

x → l ( x ) ▷ objective function θ 0 , { γ , k k ≥ 0 } ▷ initial value and stepsizes π 0 ( x ) = π θ 0 ,γ 0 ( x ) ▷ initial distribution while n ≥ 0 do ˜ π n +1 ( x ) ∝ exp( - l ( x )) π n ( x ) ▷ generalised bayesian rule θ n +1 ∈ argmin θ ∈ Θ KL(˜ π n +1 , π θ,γ n ) ▷ project with Kullback-Leibler divergence Set π n +1 = π θ n +1 ,γ n +1 ▷ distribution shrinking end while Output: sequence of distributions ˜ π n and parameters θ n .

An iteration of Alg. 1 therefore consists of the application of Bayes' rule, where l ( ) · plays the role of a negative loglikelihood and π n that of the prior distribution, followed by a 'projection' onto the normal family π θ,γ n , using the KullbackLeibler divergence as a criterion. In a standard statistical context, repeated application of Bayes' rule, in the scenario involving random data, is known to lead to a concentration phenomenon around particular maximum points or the posteriors, under general conditions Kleijn and van der Vaart (2012); a similar phenomenon occurs in the present setup and is illustrated in Fig. 1.

Remark 1.1. In practice, one may approximate Alg. 1 by replacing ˜ π n with a cloud of N ∈ N weighted random samples { X ,i i n ∈ J N K } propagated along the iterations;see Section 2 for details. The rest of the paper (Section 3 onwards) focuses on ideal algorithms, corresponding to the scenario N →∞ . We see the study of such ideal algorithms as a prerequisite to the study of their implementable versions, seen as perturbations of the ideal algorithms.

Figure 1: Illustration of the algorithm in the Gaussian case. The initial Gaussian density (light red, n = 0 ) is multiplied with exp( - · l ( )) , where l ( x ) = x 2 (blue in the background). The product is not shown but fitted with another Gaussian using the KL divergence and assigned a smaller variance. The multiplication operation gives more weight to the points close to the maximum of exp( - · l ( )) -that is, close to the minimum of l ( ) · . As a result the Gaussians (red to black) are attracted to regions of low values of l ( ) · . Together with shrinking of the covariance results this in concentration minimum of l ( ) · . Note that differentiability of l ( ) · is not used here.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-f3146100-8164-4c99-a76e-b754af0e27af.jpg)

The update considered here differs from standard Bayesian updating in that it involves a reprojection step, therefore necessitating a new approach to establishing ability of the algorithm to find minima of l ( ) · . This reprojection step is motivated by practical considerations. Indeed it circumvents the need to propagate the sequence of distributions obtained by repeated use of Bayes' update and greatly facilitates implementation. It turns out that this reprojection step also facilitates theoretical analysis. Indeed the crucial observation allowing us to prove convergence of Alg. 1, in the sense that π n concentrates on local minima of l ( ) · , is that it implicitly implements a steepest descent algorithm tracking the minima of a sequence of differentiable approximations { h n : R d → R , n ≥ 1 } of l ( ) · . When such approximations converge to l ( ) · , validity of the procedure should ensue.

More precisely, the reprojection step can be shown to correspond to so-called moment matching, a fact extensively used in variational inference Wainwright and Jordan (2008). Taking into account that in the present setup θ n +1 is the first order moment of π n +1 , or mean, moment matching takes the form

$$\theta _ { n + 1 } = \int x \tilde { \pi } _ { n + 1 } ( x ) d x = \theta _ { n } + \frac { \int ( x - \theta _ { n } ) \exp \left ( - l ( x ) \right ) \phi ( \frac { x - \theta _ { n } } { \sqrt { \gamma _ { n } } } ) d x } { \int \exp \left ( - l ( x ) \right ) \phi ( \frac { x - \theta _ { n } } { \sqrt { \gamma _ { n } } } ) d x } \,. \text{$(1)$} \\ \text{valuation of these expectations which in practice requires a Monte Carlo approximation with weighted samples.}$$

It is the evaluation of these expectations which in practice requires a Monte Carlo approximation with weighted samples. For ( θ, γ ) ∈ Θ × R + let

$$h _ { \gamma } ( \theta ) \coloneqq - \log \left ( \int \exp \left ( - l ( x ) \right ) \phi \left ( \frac { x - \theta } { \sqrt { \gamma } } \right ) \mathrm d x \right ) \,,$$

and for n ∈ N and θ ∈ Θ let h n ( θ ) := h γ n ( θ . ) Then one can write (1) in the familiar form

$$\theta _ { n + 1 } = \theta _ { n } - \gamma _ { n } \nabla h _ { n } ( \theta _ { n } ) \,,$$

and recognize a time inhomogeneous steepest-descent algorithm tracking the sequence of stationary points of the sequence of functions { h , n n ∈ N } , again smoothed versions of l ( ) · . It should be remarkable that while this interpretation provides us with an additional rational for Alg. 1 and a route to establishing its convergence for a large class of non-differentiable functions l ( ) · (the subject of Section 3), implementation does not require differentiation but instead integration.

The arguments we provide in Sections 3 and 4 lead to the following convergence result on the inhomogeneous gradient descent in (2). We again remark that, due to the equivalence, this in fact represents a convergence result for Alg. 1 where at every iteration one reprojects on the Gaussian family by minimisation of the Kullback-Leibler divergence.

Theorem 1.1. Let l : R d → R be lower-bounded, strongly lower-semicontinuous and assume there exists C l ∈ (0 , ∞ ) such that | l ( θ ′ ) -l ( θ ) | ≤ C l + C l ∥ θ -θ ′ ∥ 2 for all θ, θ ′ ∈ R d . Let { γ n , n ∈ N } be a sequence with γ n = n -β for all n ≥ 1 , for some β ∈ (0 , 1) . Let { θ n , n ∈ N } be the output of recursion (2), corresponding to Alg. 1. Then, there exists a subsequence { θ n k , k ∈ N } of { θ n , n ∈ N } such that lim k →∞ ∥∇ h n k ( θ n k ) ∥ = 0 .

↦

We see that the most stringent assumptions on l ( ) · is simply that its 'jumps' are bounded and that its variations are at most quadratic for large increments of θ . This condition is always satisfied for l ( ) · bounded. When combined with the characterisation of local minima (Theorem 3.2) in our framework, Theorem 1.1 constitutes a tool to identify local minima candidates. In particular, as will shall see, this theorem implies that if the sequence { θ n , n ∈ N } defined in Alg. 1 converges to some θ then θ is a candidate for a local minima of l ( ) · . Theorem 1.1 therefore provides a convergence result for Alg. 1 under mild assumptions on l ( ) · , but it also leads to a number of consequences and stronger results, when more is known on the objective function. For instance, when x → l ( x ) is convex, the functions θ → h n ( θ ) are also convex for n ∈ N : in this case, one can easily show that Alg. 1 converges to the minimiser of l ( ) · .

↦

Beyond standard mollifiers Readers interested in implementation and algorithm performance may jump to Section 3 on a first reading. The notion of mollifiers is precisely defined in Def. 4.1. An important point is that the above examples relying on π θ,γ being a normal distribution of known covariance matrix is a particular case of a more general class of algorithms we introduce and study in this manuscript. Consider now the scenario where π θ,γ in Alg. 1 belongs to the regular exponential dispersion models (EDM) family of distributions Jorgensen (1987, 1997); for the reader's convenience we provide standard background implicitly used below in Appendix B.1. Such models are of the form

$$\pi _ { \theta, \gamma } ( x ) = \eta ( \gamma, x ) \exp \left \{ \gamma ^ { - 1 } \left [ \langle \theta, T ( x ) \rangle - A ( \theta ) \right ] \right \} \,,$$

where T : X → T and θ ∈ Θ . The normal distribution used earlier is a particular instance of this family and other examples include the Gamma distribution or the Wishart distribution among others. The motivation behind EDMs in the present context is that, provided θ → A θ ( ) is twice differentiable

$$\mu ( \theta ) \coloneqq \mathbb { E } _ { \pi _ { \theta, \gamma } } \left ( T ( X ) \right ) = \nabla _ { \theta } A ( \theta ) \\ \text{var} _ { \pi _ { \theta, \gamma } } \left ( T ( X ) \right ) = \gamma \nabla _ { \theta } ^ { 2 } A ( \theta ) \,.$$

↦

An interesting point is that such a search of a suitable θ is achieved with Alg. 1, without any modification and the gradient descent justification still holds. Notice first that the Bayes' update

This is interesting for the following reason: for any θ ∈ Θ , letting γ ↓ 0 ensures that the distribution of T X ( ) under π θ,γ concentrates on µ θ ( ) . In the most common scenario where T x ( ) = x (or a component of T x ( ) is x ), which is the case of the normal example we started with, this means that whenever θ → µ θ ( ) spans X then we can aim to adjust θ to ensure µ θ ( ) ∈ arg min x ∈ X l ( x ) . In the more general scenario, we may have l ( x ) = ˇ l ◦ T x ( ) for some ˇ : l T → R ; this is illustrated in Subsection B.4 in the scenario where one wants π θ,γ to be a Beta distribution.

$$\tilde { \pi } _ { \theta, \gamma } ( x ) = \tilde { \eta } ( \gamma, x ) \exp \left \{ \gamma ^ { - 1 } \left [ \langle \theta, T ( x ) \rangle - \tilde { A } ( \theta ) \right ] \right \} \,,$$

is of a form similar to π θ,γ with ˜( η γ, x ) = exp ( -l ( x ) ) η γ, x ( ) and ˜ ( A θ ) = A θ ( ) + γ log π θ,γ ( exp( - · l ( ) ) . The moment matching condition, which again corresponds to the projection, therefore consists here of finding θ n +1 ∈ Θ such that µ n +1 := µ θ ( n +1 ) = E ˜ π n +1 ( T X ( ) ) = ∇ θ ˜ ( A θ n ) , that is

$$\mu _ { n + 1 } = \nabla _ { \theta } A ( \theta _ { n } ) + \gamma _ { n } \nabla _ { \theta } \log \pi _ { \theta _ { n }, \gamma _ { n } } \left ( \exp ( - l ( \cdot ) \right ),$$

which can be equivalently formulated as a recursion for { µ , n n ∈ N } or { θ n , n ∈ N }

$$\mu _ { n + 1 } = \mu _ { n } + \gamma _ { n } \nabla _ { \theta } \log \int \exp \left ( - l ( x ) \right ) \pi _ { ( \nabla A ) ^ { - 1 } ( \mu _ { n } ), \gamma _ { n } } \left ( \mathrm d x \right ),$$

with ( ∇ θ A ) -1 ( ) · the inverse mapping of ∇ θ A , or

$$\nabla _ { \theta } A ( \theta _ { n + 1 } ) = \nabla _ { \theta } A ( \theta _ { n } ) + \gamma _ { n } \nabla _ { \theta } \log \int \exp \left ( \, - l ( x ) \right ) \pi _ { ( \nabla A ) ^ { - 1 } ( \mu _ { n } ), \gamma _ { n } } \left ( \mathrm d x \right ),$$

that is

$$\theta _ { n + 1 } = \left ( \nabla _ { \theta } A \right ) ^ { - 1 } \left ( \nabla _ { \theta } A ( \theta _ { n } ) + \gamma _ { n } \nabla _ { \theta } \log \int \exp \left ( - \, l ( x ) \right ) \pi _ { \theta _ { n }, \gamma _ { n } } ( \mathrm d x ) \right ) \,.$$

One recognises a mirror descent recursion. In the standardized normal scenario ∇ θ A is the identity function and one recovers recursion (1). When the normal distribution involves a fixed, invertible, covariance matrix Σ 0 we see that the gradient is preconditioned by Σ -1 0 therefore allowing adaptation to the geometry of the problem and improve performance.

The use of the symbol θ instead of x earlier should now be clear, since their nature is very different in the general scenario, but confounded in the normal scenario where the mean is the sole parameter used. A natural question is what form condition concentration of the instrumental distribution π θ,γ should take, since now π θ,γ is not a standard approximation of the unity operator. For our purpose it is sufficient that for any x ∗ ∈ arg min x ∈ X l ( x ) there exists θ ∗ ∈ Θ such that

$$\lim _ { \gamma \downarrow 0 } \int \exp \left ( - \, l ( x ) \right ) \pi _ { \theta ^ { * }, \gamma } ( x ) \mathrm d x = \exp \left ( - \, l ( x ^ { * } ) \right ),$$

which formalizes the intuition behind the algorithm. In the simple scenario where T x ( ) = x , for any θ ∈ Θ the distribution π θ,γ concentrates on a specific point x θ ( ) ∈ X as γ ↓ 0 . If in addition for any x ∗ ∈ arg min x ∈ X l ( x ) there exists θ ∗ ∈ Θ such that π θ ∗ ,γ concentrates on x ∗ as γ ↓ 0 , then our algorithm will exploit this property and estimate θ ∗ . The Beta and Wishart examples are discussed in Subsections B.4-B.3.

Note the difference with a simulated annealing algorithm, where concentration on minima of l ( ) · is achieved in a different way, although it is possible to introduce this as an additional parameter by replacing exp ( -l ( x ) ) above with exp ( -λl x ( ) ) for λ &gt; 0 ; see Section 2 where we discuss strategies for learning λ and improve performance. Finally we point out that, in the present scenario, exp ( -l ( x ) ) appearing in the expression for h γ can be replaced with other non-negative decreasing transformations, but we do not pursue this here.

The scenario where noisy measurements are available proceeds similarly. In the stochastic scenario the algorithm proceeds as in Alg. 1 and the sequence { θ n , n ≥ } 1 is now the output of a time inhomogeneous stochastic gradient algorithm

$$\theta _ { n + 1 } = \theta _ { n } - \gamma _ { n } \nabla _ { \theta } \left \{ - \log \int e ^ { - \ell ( x, U _ { n + 1 } ) } \phi \left ( \frac { x - \theta _ { n } } { \sqrt { \gamma _ { n } } } \right ) \mathrm d x \right \}, \ U _ { n }, \ n \geq 1 \stackrel { i i d } { \sim } P \,,$$

here presented in the Gaussian scenario. Full details are provided in Alg. 2.

## Algorithm 2 Stochastic gradient free algorithm

↦

## Input:

( x, u ) → ℓ x, u ( )

▷ objective function

θ 0 , { γ , k k ≥ 0 }

▷ initial value and stepsizes

$$\pi _ { 0 } ( x ) = \pi _ { \theta _ { 0 }, \gamma _ { 0 } } ( x )$$

▷ initial distribution

while n ≥ 0 do

Sample U n +1 ∼ P

▷ generate noise

˜ π n +1 ( x ) ∝ exp( - ℓ x, U ( n +1 )) π n ( x )

▷ generalised bayesian rule

θ n +1 ∈ argmin θ ∈ Θ KL(˜ π n +1 , π θ,γ n )

▷ project with Kullback-Leibler divergence

Set π n +1 = π θ n +1 ,γ n +1

▷ distribution shrinking

## end while

Output: sequence of distributions ˜ π n and parameters θ n .

Validity in the noisy scenario hinges on the same ideas as in the deterministic scenario. Using properties of approximations to the identity for any θ ∈ Θ

$$\mathbb { E } \left \{ - \log \int e ^ { - \ell ( x, U ) } \phi \left ( \frac { x - \theta } { \sqrt { \gamma } } \right ) \mathrm d x \right \} \stackrel { \gamma \downarrow 0 } { \rightarrow } \mathbb { E } \left \{ - \log \int e ^ { - \ell ( x, U ) } \delta _ { \theta } ( \mathrm d x ) \right \}$$

$$= \mathbb { E } \left \{ \ell ( \theta, U ) \right \} = l ( \theta ) \,,$$

In the general scenario our algorithm will aim to exploit the property that for θ ∈ Θ

$$\mathbb { E } \left \{ - \log \int e ^ { - \ell ( x, U ) } \pi _ { \theta, \gamma } ( x ) d x \right \} \stackrel { \gamma \downarrow 0 } { \to } \mathbb { E } \left \{ - \log \int e ^ { - \ell ( x, U ) } \delta _ { x ( \theta ) } ( d x ) \right \} = \mathbb { E } \left \{ \ell ( x ( \theta ), U ) \right \} \,,$$

and again a time inhomogeneous stochastic gradient will be used to find θ ∗ such that x θ ( ∗ ) ∈ argmin x ∈ X l ( x ) . While we have completed theory for the noiseless setup, we are currently working on establishing convergence of the noisy algorithm.

## 2. Experiments

In this section we provide implementational details and evaluate our methodology on a statistical problem arising in machine learning.

Implementation Alg. 1 and Alg. 2 rely on theoretical distributions π n and ˜ π n which may be intractable. We approximate π n with N ∈ N randomised quasi-Monte Carlo (RQMC, see e.g. Lemieux, 2009) samples { X i i n ∈ J N K } , while we approximate ˜ π n with weighted samples { ( X ,w i n i n ) i ∈ J N K } where w i n = exp {-l ( X i n ) } , since ˜ π n ( x ) ∝ π n ( x ) exp {-l ( x ) } . We observe that these algorithms tend to work well even for quite low values of N ; we set N = 128 throughout. We define the output of Alg. 1 at iteration n to be arg min i l ( X i n ) , i.e. the particle with the smallest observed value for l ( x ) ) while we define the output of Alg. 2 to be simply the current mean. In the former scenario Theorem ?? justifies our strategy. The exponential family we consider is the family of Gaussian distributions N ( µ, γI d ) .

Since minimising l is equivalent to minimising l λ := λ × l for any scalar λ &gt; 0 , one may consider different strategies to scale l automatically to improve speed of convergence. We found the following approaches to work well in practice: set the scale λ so that the variance of the log-weights equals one, either for the first k iterations, or for all iterations. The results reported below correspond to the latter strategy, while we report results for the former in Appendix E for completeness. We note that, currently, the theoretical framework developed in Section 3 corresponds to the algorithms used in Appendix E and do not yet cover the algorithms used below.

AUC scoring and classification We illustrate our methodology on a staple machine learning scoring and classification task. Here, given training data { ( Z , Y i i ) ∈ R d ×{-1 1 , } : i = 1 , . . . , n data } , assumed to arise from a probability distribution P , one wishes to construct a score function s : R d →{-1 1 , } , such that for two independent realisations ( Z, Y ) and ( Z , Y ′ ′ ) the theoretical quantity

$$\mathbb { P } \left ( \left [ s ( Z ) - s ( Z ^ { \prime } ) \right ] ( Y - Y ^ { \prime } ) < 0 \right )$$

is as small as possible. This quantity is often called the area under curve (AUC) risk function; one of the motivations for this criterion is that it is less sensitive to class imbalance than other more standard classification criteria.

Assuming further a particular parametric form for s z ( ) , e.g. s z ( ) = s x ( z ) = x ⊤ z for x ∈ R d , Clémençon et al. (2008) proposed to estimate x through empirical risk minimisation, i.e.

$$\hat { x } = \arg \min _ { x \in \mathbb { R } ^ { d } } l ( x ) \,,$$

where l ( x ) is the following U-statistic:

$$l ( x ) = \frac { 1 } { n _ { \text{data} } ( n _ { \text{data} } - 1 ) } \sum _ { i, j = 1 } ^ { n _ { \text{data} } } \mathbf 1 \left \{ \left [ s _ { x } ( Z _ { i } ) - s _ { x } ( Z _ { j } ) \right ] ( Y _ { i } - Y _ { j } ) < 0 \right \}.$$

This function is challenging to minimise directly, for three reasons: (a) it is piecewise constant and therefore discontinuous; (b) it is invariant by affine transformations for the linear model, i.e. l ( λx ) = l ( x ) for any scalar λ ; and (c) it is expensive to compute when n data is large, because of its O ( n 2 data ) complexity. As a result, several alternative approaches have been proposed to perform AUC scoring; e.g. one may replace it with a convex approximation (Clémençon et al., 2008, Sect. 7) or use a PAC-Bayesian approach as in Ridgway et al. (2014).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-1a809e7d-7695-4ada-9bb4-1af07115f26d.jpg)

iteration

n

Figure 2: Pima dataset. Left: running mean as a function of iteration n for the exact (blue) and batch (red) algorithms ( 10 runs). Center: box-plot of the estimated minimum AUC for the three algorithms considered. (The plot is zoomed in for better readability.) Right: min/max of l across iterations n (different lines correspond to different runs) for the exact algorithm.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-cbadde4d-e611-4085-ab4c-b92db49305b1.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-0f621f68-8cc2-48ef-89a9-f9bba5e4110c.jpg)

Regarding point (c), one may replace (3) with the following unbiased estimate, based on the mini-batch approach, popular in machine learning. Assuming without loss of generality that Y i = 1 for i = 1 , . . . , n + , Y i = -1 , for i = n + +1 , . . . , n data , where n + = ∑ i 1 { Y i = 1 } and n -is defined similarly, take

$$\widehat { l } ( x ) \coloneqq \frac { 2 } { n _ { \text{data} } ( n _ { \text{data} } - 1 ) } \times \frac { n _ { + } n _ { - } } { n _ { \text{batch} } } \sum _ { k = 1 } ^ { n _ { \text{batch} } } 1 \left \{ s _ { x } ( Z _ { I _ { k } } ) < s _ { x } ( Z _ { J _ { k } } ) \right \}$$

where ( I k , J k ) are n batch independent draws from the uniform distribution over { 1 , . . . , n + }×{ n + +1 , . . . , n data } . Naturally, this (noisy) criterion is much faster to compute than (3) whenever n batch ≪ n + n -.

In Fig. 2, left panel, we report the running estimates, normalised to take point (b) above into account, for both our exact and batch algorithms, for the Pima Indian dataset. As expected, the batch variant leads to noisier estimates and the estimates arising from the exact algorithm convergence very quickly for this dataset.

We showcase how our approach may be used to implement AUC scoring, by using either our deterministic algorithm with objective function (3) (from now on, referred as the 'exact' method), or our stochastic algorithm relying on evaluations of the mini-batch objective (4) (the 'batch' method). We consider several classical datasets from the UCI machine learning repository and we pre-process the data so that each predictor is normalised, i.e. the empirical mean is set to zero and the variance is set to one. We compare our two algorithms to a strategy often used in practice which relies on the NelderMead, or simplex, algorithm with random start. This approach is considered naive in that Nelder-Mead does not require differentiability for implementation, but is a requirement for correctness. As in the introduction, we set π θ,γ to be a N ( θ, γ I p ) and choose γ n = 1 (1 + / n ) 0 4 . . We run the three algorithms 10 times, and we set n batch = 500 in the batch algorithm.

In Fig. 2, centre panel, we compare the variability (over 10 runs) of the output of the three algorithms considered. One can see that both the exact and batch variants of our algorithm provide much lower empirical risk than the naive approach based on Nelder-Mead. Finally, the right panel reports the smallest and largest values of l ( X i n ) at iteration n for the exact algorithm.

We repeat this experiment for the Sonar dataset, which is more challenging since p = 60 . Results are displayed in Fig. 3. Here we do not report the output of the Nelder-Mead algorithm, as they were found to be off, with a median over 10 runs of 0.25, which is more than an order of magnitude higher than the output of the other two algorithms. We notice that a larger number of iterations is required to achieve convergence in this case, and both algorithms were run for 4000 iterations. Note however that in this case 20 iterations of the batch algorithm requires the same number of data accesses as a single iteration of the exact algorithm (i.e. n + n -/n batch ≈ 20 ), so the batch algorithm remains a cheap and therefore appealing approach for AUC minimisation, in the present scenario.

Extensions We finish this section with some remarks concerning more general implementations. The algorithm described in this section is a particular instance of sequential Monte Carlo (SMC) samplers Del Moral et al. (2006), where the aim is to

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-74bd7a14-72ed-4515-ab73-48888aefd372.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-be637b53-bffe-4bc1-9ee8-1b339a468fde.jpg)

AUC

Figure 3: Same plots as Figure 2 for the Sonar dataset. For the left plot, only the last 5 components are shown. For the center plot, Nelder-Mead is excluded because results are far off. For the right plot, the first 300 iterations are not plotted to improve readibility.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-f68ee51b-703a-413b-ab4b-383c9d337079.jpg)

sample from a sequence of probability distributions sequentially in time. Here we took advantage of the fact that sampling from π θ,γ is routine and in fact used an SMC adaptive strategy to adapt λ . In more complex scenarios this may not be possible and instead one may choose to propagate samples with a more general mutation kernel, typically resulting in a perturbation of samples from previous generation, which is then corrected with an importance weight. Another advantage is that good particles can be recycled from one generation to the next and not resampled anew. Further extensions could involve the inclusion of persistency of movement in a particular direction i.e. take advantage of regularity of variations of l ( ) · e.g. 'in the tails', in the same way gradient information allows fast algorithms.

## 3. Results on gradient descent with smooth approximations

In this section we review essential notions and tools required to address the minimisation of a function f : R d → R , assumed lower-bounded, not necessarily differentiable, but for which there exists a sequence of differentiable approximations { f n : R d → R , f n ∈ C 1 ( R d ) , n ∈ N } , convergent to f in a sense to be made precise below. In this scenario it is natural to suggest the non-homogeneous gradient descent algorithm

$$\theta _ { n + 1 } = \theta _ { n } - \gamma _ { n } \nabla f _ { n } ( \theta _ { n } ) \,,$$

where { γ n ∈ R + , n ∈ N } with γ n ↓ 0 , in the hope that tracking the sequence points in { argmin f n , n ∈ N } will lead us to minima of f . This is however a subtle matter. To start with, non-differentiable functions such as in Fig. 4a do not have a minimum as it is not lower-semicontinuous, a weak property ensuring the existence of minima. A more substantial issue is that even when perfect minimisation of f n for all n ∈ N is possible, the intuitive set-limit (properly defined in Def. C.4) lim n { argmin f n } = argmin f may not hold. This is illustrated in Figure 4b with a counterexample illustrating that even uniform convergence of { f n , n ∈ N } to f is not sufficient to ensure lim n { argmin f n } = argmin f . An important point in the present paper is that using smoothed approximations for minimisation may not work in certain contrived scenarios.

̸

↦

Example 3.1. With the notation from Section 1, for d = 2 consider the function l ( x ) := min { 1 , | x 1 |} 1 { x 1 = x 2 } + 1 { x 1 = x 2 } . This function is such that Leb { x ∈ R 2 : l ( x ) &lt; 1 } = 0 and as a consequence for any θ ∈ Θ and γ &gt; 0 , h γ ( θ ) = 1 , that is the smoothed functions θ → h γ ( θ ) 'cannot see the minimum' at zero. In general a requirement therefore seems to be that for any x ∗ ∈ arg min x ∈ X l ( x )

$$\lim _ { \gamma \downarrow 0 } \gamma ^ { - d / 2 } \int \exp \left ( - \, l ( x ) \right ) \phi \left ( \frac { x - x ^ { * } } { \sqrt { \gamma } } \right ) \text{d} x = \exp \left ( - \, l ( x ^ { * } ) \right ).$$

In the toy countexample the left hand side is equal to exp( -1) while the right hand side is equal to 1 . The condition precludes the existence of sets A ∋ x ∗ such that for some c &gt; 0 for all x ∈ A we have l ( x ) ≥ l ( x ∗ )+ c and ´ A π x ,γ ∗ ( x )d x → γ ↓ 0 1 .

Epi-convergence of { f n : R d → R , n ∈ N } to f is a suitable and flexible form of convergence ensuring that smoothing techniques combined with exact optimisation achieve their goal. Ensuring this property is a natural prerequisite to the

justification of the recursion (5) to optimise f . However it must be noted that convergence in this framework differs from what is usually understood as convergence; weaker forms of the set limit lim n { argmin f n } = argmin f can be obtained, depending on the strength of the assumptions. The following result, due to (Ermoliev et al., 1995, Theorem 4.7), exemplifies what one may hope to be able to deduce. Assume that { f n : R d → R , f n ∈ C 1 ( R d ) , n ∈ N } epi-converges (properly defined in Def. 3.4) to f , then

$$\theta _ { \infty } \in \mathbb { R } ^ { d } \text{ local minimum of } f \, \Rightarrow \, \exists \, \{ \theta _ { n }, \, n \in \mathbb { N } \} \text{ s.t. } \theta _ { n } \to \theta _ { \infty } \text{ and } \| \nabla f _ { n } ( \theta _ { n } ) \| \to 0 \,.$$

The practical implication of this result is that if a sequence { θ n ∈ R d , n ∈ N } admits a subsequence { θ n k ∈ R d , k ∈ N } convergent to some θ ∞ ∈ R d and such that lim k ||∇ f n k ( θ n k ) || = 0 , then θ ∞ is a valid candidate as a local minimum of f , and accumulations points not satisfying the latter condition must be rejected. Theorem 3.2 in this manuscript presents an adaptation to our setting of Ermoliev et al. (1995) result.

Figure 4: Left: example of a function with empty argmin . Right: A sequence of functions { f n , n ∈ N } (red-toblack color palette) that epi-converges to the function f . The picture is inspired by (Rockafellar and Wets, 1998, Figure 7.7). It is clear that here argmin f n ⊂ argmin f .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-03d4e10f-c457-473a-90a3-661b5e08c039.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-c6d31ae0-fb02-4588-9796-20a4d10c6577.jpg)

## 3.1. Lower-semi continuity

The notion of lim inf for functions f : R d → R , frequently used in the manuscript, is defined as follows.

Definition 3.1. Let f : R d → R . For θ 0 ∈ R d ,

$$\liminf _ { \theta \to \theta _ { 0 } } f ( \theta ) \coloneqq \sup _ { \epsilon > 0 } \left ( \inf \left \{ f ( \theta ) ; \text{ } \theta \in \mathbb { B } ( \theta _ { 0 }, \epsilon ) \right \} \right )$$

where B ( θ , ϵ 0 ) denotes a closed metric ball with center θ 0 and radius ϵ &gt; 0 .

Definition 3.2 (Lower semicontinuity) . (Rockafellar and Wets, 1998, Def. 1.5) A function f : R d → R is said to be

- 1. lower-semicontinous ( lsc ) at θ 0 ∈ R d if

$$\nu \liminf _ { \theta \to \theta _ { 0 } } f ( \theta ) \geq f ( \theta _ { 0 } )$$

- 2. lower-semicontinous if the above holds for any θ 0 ∈ R d .

Remark 3.1. For θ 0 ∈ R d and ϵ &gt; 0 , inf { f ( θ ); θ ∈ B ( θ , ϵ 0 ) } ≤ f ( θ 0 ) , therefore, lim inf θ → θ 0 f ( θ ) ≤ f ( θ 0 ) ; hence condition (8) is equivalent to lim inf θ → θ 0 f ( θ ) = f ( θ 0 ) .

By definition, any lower-semicontinuous, lower-bounded function has a minimum on R d .

Definition 3.3 (Strong lower semicontinuity) . A function f : R d → R is said to be

- 1. strongly lower-semicontinous ( slsc ) at θ ∈ R d if it is lower semicontinous at θ ∈ R d and there exists a sequence { θ n , n ∈ N } , θ n → θ such that f ( θ n ) → f ( θ ) .
- 2. strongly lower-semicontinuous if the above holds for any θ ∈ R d .

In words, strong lower-semicontinuity is lower-semicontinuity excluding discontinuities at isolated points. Remark that we do not make any assumption on smoothness of the function; the class of strongly lower-semicontinuous functions includes indicator functions of closed sets, step functions, ceiling functions; but also not-everywhere differentiable continuous and discontinuous (if there are not isolated discontinuity points) functions.

Example 3.2. The step function f : R → R defined by

$$f ( \theta ) = \begin{cases} 1, \ \theta > 0 \\ 0, \ \theta \leq 0 \end{cases} \.$$

is strongly lower-semicontinuous. The following function is lower-semicontinuous everywhere but at θ = 0 ,

$$f ( \theta ) = \begin{cases} 1, \ \theta \geq 0 \\ 0, \ \theta < 0 \end{cases} \.$$

Intuitively, we can note that the part of the space above the graph of this function, commonly called epigraph of f , is not a closed set, which in fact precludes lower-semicontinuity: see Appendix C.1 for more results on lower-semicontinuity and epigraphs.

Example 3.3. Consider a function f : R d → R . The epigraphical closure of f , denoted cl e ,

$$\text{cl} _ { e } \, f ( \theta ) \coloneqq \liminf _ { \theta ^ { \prime } \to \theta } f ( \theta ^ { \prime } ) \,, \, \theta \in \mathbb { R } ^ { d }$$

is lower-semicontinuous, with cl e f ( θ ) ≤ f ( θ ) . More details can be found in (Rockafellar and Wets, 1998, Chapter 1, Section D).

Example 3.4 (Probability functions) . Let P be a distribution on U and let U ∼ P random variable, and let g : R ×U → R be a two-variable function such that the objective

$$f ( \theta ) = - \int _ { \mathcal { U } } \mathbf 1 \left \{ g ( \theta, u ) < 0 \right \} P ( \mathrm d u )$$

has a minimum on R . As the function 1 {·} is discontinuous, f will in general not be everywhere differentiable (and hence non-smooth). For example, if g θ, u ( ) = θ + u and P is chosen to be the uniform Unif [0 , 1] , we have

$$L ( \theta ) = \begin{cases} | \theta | - 1, | \theta | \leq 1 \\ 0, & | \theta | > 1 \end{cases} \.$$

which is nonsmooth at θ ∈ { 0 1 , , - } 1 . This type of objective functions is for instance considered in Norkin (1993).

## 3.2. Epi-convergence and convergence in minimisation

As discussed in the introduction of this section, epi-convergence is the right notion of convergence for { f n : R d → R , n ∈ N } to f to formulate and establish convergence of the type of recursion (5). We therefore start with some definitions - a more classical abstract definition in terms of epigraphs convergence is provided in Appendix C.3.

Definition 3.4 (Epi-convergence) . A sequence of functions { f n : R d → R , n ∈ N } epi-converges to a function f : R d → R if for each θ ∈ R d

- 1. lim inf n f n ( θ n ) ≥ f ( θ ) for any sequence θ n → θ
- 2. lim n f n ( θ n ) = f ( θ ) for some sequence θ n → θ .

Thus, we say that f is the epi-limit of { f n , n ∈ N } .

We can immediately note that if a function f : R d → R is the epi-limit of some sequence { f n , n ∈ N } , then f is necessarily lower-semicontinuous.

Example 3.5. The three examples below aim to illustrate how epi-convergence differs from standard functional limits. Consider { f n : R → R , n ∈ N } where,

- 1. f n ( θ ) := -e -nθ 2 , then the sequence epi-converges to

̸

$$f ( \theta ) \, \coloneqq \, \begin{cases} - 1, & \theta = 0 \\ 0, & \theta \neq 0 \,. \end{cases}$$

In fact, it converges pointwise to the same limit. However, epi-convergence generally differs from e.g. pointwise convergence, as the following example shows.

- 2. f n ( θ ) = e -nθ 2 , then the sequence epi-converges to f ≡ 0 , as in particular lim n f n ( n -α ) = 0 for α ∈ (0 1 , / 2) ; we see here how epi-convergence differs from e.g. pointwise convergence since lim f n (0) = 1 here,
- 3. f n ( θ ) = ( -1) n e -nθ 2 , then fhe sequence fails to epi-converge as for θ = 0 and any sequence { θ n , n ∈ N } such that θ n → 0 we have lim n ( -1) n f n ( θ n ) = 1 , and therefore lim n f n ( θ n ) does not exist.

Epi-convergence is concerned with the set convergence of epigraphs, that is, of the part of the space above the graph of the functions; again full details are provided Appendix C for more details, but not required to understand the nature of our convergence results.

The following Theorem highlights two main consequences of epi-convergence, describing what type of results one can expect about convergence of minima and infima. Below, we say that a function g : R d → R is eventually level-bounded if for each a ∈ R d the sequence of level-sets { lev ≤ a f n , n ∈ N } is eventually bounded. For instance, a sequence of eventually lower-bounded functions is eventually level-bounded.

## Theorem 3.1 (Rockafellar and Wets (1998), Theorem 7.33) . Let

- 1. f : R d → R be a lower-bounded, lower-semicontinuous function,
- 2. { f n : R d → R , n ∈ N } be a sequence of lower-semicontinuous functions such that
- a) { f n , n ∈ N } epi-converges to f ,
- b) { f n , n ∈ N } is eventually level-bounded.

## Then,

- 1. inf θ ∈ R d f n ( θ ) → inf θ ∈ R d f ( θ ) ,
- 2. Limsup n argmin f n ⊂ argmin f .

In (Rockafellar and Wets, 1998, Chapter 5) it is remarked that looking for the inclusion Limsup n argmin f n ⊂ argmin f should be preferred over the stronger result lim n { argmin f n } = argmin f . Figure 4b provides an example of a sequence of functions that epi-converge (in fact, they converge uniformly) to a function f , and where it is not true that every point of argmin f is in the limit of argmin f n . Note that, however, any θ ∈ argmin f in the figure can be expressed as a limit of points θ n that are ϵ n -optimal for f n in the sense of equation (36), for ϵ n ↓ 0 .

We begin with two Lemmata that allow us to prove the key result of this section. The following Lemma describes a key differentiability property of the convolution of two functions, one of which is of class C 1 ( R d ) .

We now turn to results characterising local minima θ ∗ of f as accumulation points of sequences { θ n ∈ R d , n ∈ N } in the situation where an epi-convergent and differentiable approximating sequence { f n : R d → R , n ∈ N } exists. In particular the existence of θ n → θ ∗ is established, for which lim n ∥∇ f n ( θ n ) ∥ = 0 . As a consequence for any algorithm producing a sequence { θ n ∈ R d , n ∈ N } from which a convergent sequence θ n k → θ ∗ ∈ R d can be extracted, then if lim n k ∥∇ f n k ( θ n k ) ∥ ̸ = 0 we reject θ ∗ as a local minimum.

↦

$$\nabla \int f ( u ) g ( \theta - u ) \mathrm d u = \int f ( u ) \nabla g ( \theta - u ) \mathrm d u, \ \theta \in \mathbb { R } ^ { d }.$$

Lemma 3.1 (Rockafellar and Wets (1998), Theorem 9.67) . Let f, g : R d → R be locally integrable and assume that g ∈ C 1 ( R d ) . Then the function θ → ´ f ( u g θ ) ( -u )d u belongs to C 1 ( R d ) with

The lemma below describes an important property of convergent sequences that attain ϵ -optimal points of epi-convergent functions.

Lemma 3.2 (Attouch (1984), Theorem 1.10) . Let D ⊆ R d and

- 1. { f n : R d → R , n ∈ N } be epi-convergent to f : R d → R for all θ ∈ D
- 2. { θ n ∈ R d , n ∈ N } be such that θ n → θ ∗ ∈ D and for { ϵ n ∈ R + , n ∈ N } with ϵ n ↓ 0

$$f _ { n } ( \theta _ { n } ) \leq \inf _ { \theta \in D } f _ { n } ( \theta ) + \epsilon _ { n }, \ n \in \mathbb { N } \,.$$

Then, θ ∗ ∈ argmin θ ∈ D f .

Finally, the following justifies an optimisation procedure for finding local minima of l by tracking minimisers of differentiable functions { h , n n ∈ N } that epi-converge to l . The proof of the result is a generalisation of the proof of (Ermoliev et al., 1995, Theorem 4.7). While in the latter paper the result is stated for a strongly lower-semicontinuous f and auxiliary mollifiers with bounded support (implying epi-convergence in their setting), we noted that it is enough for f to be lowersemicontinuous and for the auxiliary mollifiers to be Gaussian if epi-convergence is put as an assumption of the theorem. This extends its validity and widens the class of methods whose convergence can be proven in terms of the Theorem below.

## Theorem 3.2. Let,

- 1. f : R d → R be locally integrable, lower bounded and lower-semicontinuous,
- 2. { f n : R d → R , n ∈ N } be a sequence of differentiable functions epi-convergent to f .

Then for any θ ∗ ∈ loc -argmin f there exists { θ k ∈ R d , k ∈ N } such that θ k → θ ∗ and lim k ||∇ f k ( θ k ) || = 0 .

Proof. Let θ ∗ be a local minimiser of f , define ϕ θ ( ) := f ( θ ) + || θ -θ ∗ || 2 and let V be a sufficiently small compact set such that θ ∗ ∈ V and argmin θ ∈ V ϕ θ ( ) = { θ ∗ } -that is, θ ∗ is the unique global minimiser of ϕ on V . The uniqueness of the minimiser on V , ensured by the auxiliary function ϕ , excludes potential issues arising from working with a locally flat function, and more generally guarantees that a (sub-) sequence converging to θ ∗ as per Lemma 3.2 exists, as we are going to illustrate. Consider the sequence of mollifiers { ψ n : R d → R + , n ∈ N } with

$$\psi _ { n } ( z ) \coloneqq ( 2 \pi \gamma _ { n } ) ^ { - d / 2 } \exp \left \{ - \frac { | | z | | ^ { 2 } } { 2 \gamma _ { n } } \right \}$$

and { γ n ∈ R + , n ∈ N } such that γ n ↓ 0 . From (Ermoliev et al., 1995, Remark 3.14) we have ψ n ∈ C 1 ( R d ) , ´ ψ n ( z )d z = 1 , n ∈ N , and for every δ &gt; 0 ,

$$\lim _ { n } \int _ { \{ | | z | | > \delta \} } \psi _ { n } ( z ) d z = 0, \text{ and } \lim _ { n } \int _ { | | z | | > \delta } | | z + \theta - \theta _ { * } | | ^ { 2 } \psi _ { n } ( z ) d z = 0$$

uniformly in θ ∈ R d . Let β n ( θ, θ ∗ ) := ´ || z + θ -θ ∗ || 2 ψ n ( z )d z , n ∈ N , θ ∈ V , and define the auxiliary functions

$$\phi _ { n } ( \theta ) \coloneqq f _ { n } ( \theta ) + \beta _ { n } ( \theta, \theta _ { * } ), \ n \in \mathbb { N }, \ \theta \in V.$$

## Note that

- · the functions { β , n n ∈ N } are of class C 1 ( R d ) by Lemma 3.1,

↦

- · For the above mollifiers, { β , n n ∈ N } epi-converge to θ →|| θ -θ ∗ || 2 on V due to (Ermoliev et al., 1995, Theorem 3.7 and Remark 3.14) - in fact, they converge uniformly,
- · By assumption, { f n , n ∈ N } is a sequence of differentiable functions that epi-converge to f ; therefore, { ϕ , n n ∈ N } is a sequence of well-defined differentiable (hence continuous) functions on V that epi-converge to ϕ on V .

Let { ¯ θ n ∈ V, n ∈ N } be a sequence of minimisers of { ϕ , n n ∈ N } , which exists since for any n ∈ N , ϕ n is continuous and V a compact set. From the compactness of V there exists a convergent subsequence { θ n ∈ V, n ∈ N } of { ¯ θ n ∈ V, n ∈ N } . By Lemma 3.2, it holds that θ n → θ ∗ . We now turn to the second statement. For each n ∈ N ,

$$0 = \nabla \phi _ { n } ( \theta _ { n } ) = \nabla f _ { n } ( \theta _ { n } ) + \nabla \beta _ { n } ( \theta _ { n }, \theta _ { * } ).$$

and in the limit,

$$\lim _ { n } \nabla f _ { n } ( \theta _ { n } ) = - \lim _ { n } \nabla \beta _ { n } ( \theta _ { n }, \theta _ { * } ) = 0.$$

which proves the statement.

In order to show the last equality, by continuity of the function θ →|| || θ 2 one can use Lemma 3.1 and write, for every k ,

↦

$$\text{aliy, by continuity of the function } \theta \mapsto | | \theta | | ^ { \ } one can use Lemma \\ \nabla \beta _ { k } ( \theta _ { k }, \theta _ { * } ) & = \nabla \int | | z + \theta _ { k } - \theta _ { * } | | ^ { 2 } \psi _ { k } ( z ) d z \\ & \text{Lemma } 3. 1 \int \nabla | | z + \theta _ { k } - \theta _ { * } | | ^ { 2 } \psi _ { k } ( z ) d z \\ & = \int 2 ( z + \theta _ { k } - \theta _ { * } ) \psi _ { k } ( z ) d z \\ & = 2 \left \{ \int z \psi _ { k } ( z ) d z + \theta _ { k } - \theta _ { * } \right \}. \\ \text{$\text{assumption} \, \int z \psi _ { k } ( z ) d z = 0$ for every $k \in \mathbb{N}$: moreover, $\theta_{k} \to \theta_{k}$}.$$

We can now note that, by assumption, ´ zψ k ( z )d z = 0 for every k ∈ N ; moreover, θ k → θ ∗ . Therefore, the last equality in (10) holds.

## 3.3. Stability and convergence of time-inhomogeneous gradient descent

↦

The following result establishes convergence of time inhomogeneous gradient algorithms to local minima of l ( ) · . This generalizes results such as Gupal and Norkin (1977), not requiring confinement of the sequence { θ n , n ∈ N } for example. The result is specialised to exploit the fact that for any n ∈ N the map θ →∥∇ f n ( θ ) ∥ is uniformly bounded in θ ∈ Θ .

Theorem 3.3. For differentiable functions { f n : R d → R , n ∈ N } and { γ n ∈ R + , n ∈ N } consider the recursion defined for some θ 0 ∈ R d and for n ≥ 0

$$\theta _ { n + 1 } = \theta _ { n } - \gamma _ { n } \nabla f _ { n } ( \theta _ { n } ) \,.$$

(11)

Let α ∈ [0 , 2] and { L n ∈ R + , n ∈ N } and { δ n ∈ [0 , ∞ ) , n ∈ N } be such that

$$\lim _ { n \to \infty } \sup _ { n } \gamma _ { n } L _ { n } < 1, \ \lim _ { n \to \infty } ( \delta _ { n } / \gamma _ { n } ) = \lim _ { n \to \infty } ( \delta _ { n } / \gamma _ { n + 1 } ) = 0, \ \sum _ { n = 1 } ^ { \infty } \gamma _ { n } = \infty.$$

Assume that the following conditions hold:

- 1. inf ( n,θ ) ∈ × N R d f n ( θ ) &gt; -∞ .
- 2. for all θ, θ ′ ∈ R d and n ∈ N ,

$$\L ^ { \cdot } _ { \quad f _ { n } ( \theta ^ { \prime } ) } \leq f _ { n } ( \theta ) + \langle \nabla f _ { n } ( \theta ), \theta ^ { \prime } - \theta \rangle + L _ { n } \| \theta ^ { \prime } - \theta \| ^ { 2 }.$$

- 3. for all θ ∈ R d and n ∈ N ,

$$f _ { n + 1 } ( \theta ) - f _ { n } ( \theta ) \leq \delta _ { n } \left [ 1 + \| \nabla f _ { n + 1 } ( \theta ) \| ^ { \alpha } \right ].$$

- 4. either of the following conditions holds (with the convention 0 · ∞ = 0 ):
- a) Condition 3 holds with α = 0 .

b)

c)

$$\lim _ { n \to \infty } \frac { \delta _ { n } \sup _ { \theta \in \mathbb { R } ^ { d } } \| f _ { n + 1 } ( \theta ) \| ^ { \alpha / 2 } } { \gamma _ { n + 1 } ^ { \alpha / 2 } \sum _ { m = 1 } ^ { n } \gamma _ { m } } = 0$$

$$\lim _ { n \to \infty } \frac { \delta _ { n } \sup _ { \theta \in \mathbb { R } ^ { d } } \| \nabla f _ { n + 1 } ( \theta ) \| ^ { \alpha } } { \sum _ { m = 1 } ^ { n } \gamma _ { m } } = 0$$

d) there exists a constant β ∈ (0 1] , and a sequence { ˜ L n ∈ (0 , ∞ ): n ≥ 1 } such that, for all θ, θ ′ ∈ R d and n ∈ N , | f n ( θ ) -f n ( θ ′ ) | ≤ ˜ L n ∥ θ -θ ′ ∥ β and such that

$$\lim _ { n \to \infty } \frac { \delta _ { n } \tilde { L } _ { n + 1 } ^ { \frac { \alpha } { 2 - \beta } } } { \gamma _ { n + 1 } ^ { \alpha ( 1 - \beta ) / ( 2 - \beta ) } \sum _ { m = 1 } ^ { n } \gamma _ { m } } = 0.$$

Then, there exists a subsequence { θ n k , k ∈ N } of { θ n , n ≥ } 1 such that lim k →∞ ∥∇ f n k ( θ n k ) ∥ = 0 .

Proof. Under 2 and using (11), for all n ≥ 1 we have

$$f _ { n } ( \theta _ { n + 1 } ) & \leq f _ { n } ( \theta _ { n } ) + \langle \nabla f _ { n } ( \theta _ { n } ), \theta _ { n + 1 } - \theta _ { n } \rangle + L _ { n } \| \theta _ { n + 1 } - \theta _ { n } \| ^ { 2 } \\ & = f _ { n } ( \theta _ { n } ) - \gamma _ { n } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { 2 } ( 1 - L _ { n } \gamma _ { n } )$$

Let n 1 ∈ N and ϵ 1 ∈ (0 , 1) be such that 1 -γ n L n ≥ ϵ 1 for all n ≥ n 1 . Then, for all n ≥ n 1 we have, using (12) and under 3,

$$f _ { n + 1 } ( \theta _ { n + 1 } ) & \leq f _ { n } ( \theta _ { n } ) - \gamma _ { n } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { 2 } ( 1 - L _ { n } \gamma _ { n } ) + f _ { n + 1 } ( \theta _ { n + 1 } ) - f _ { n } ( \theta _ { n + 1 } ) \\ & \leq f _ { n } ( \theta _ { n } ) - \gamma _ { n } \epsilon _ { 1 } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { 2 } + \delta _ { n } ( 1 + \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } ).$$

We now prove the result of the theorem by contradiction. To this aim, assume that there exists an ϵ 2 ∈ (0 , 1) and an n 2 ∈ N such that ∥∇ f n ( θ n ) ∥ ≥ ϵ 2 for all n ≥ n 2 .

Then, for all n ≥ n 3 := max { n , n 1 2 } we have, by (13) and letting ϵ 3 = ϵ 1 ϵ 2 -α 2

$$f _ { n + 1 } ( \theta _ { n + 1 } ) \leq f _ { n } ( \theta _ { n } ) - \epsilon _ { 3 } \gamma _ { n } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \alpha } + \delta _ { n } ( 1 + \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } ).$$

and thus, for all n ≥ n 3 , we have

$$s, & \text{for all $n\geq n_{3}$, we have} \\ & f _ { n + 1 } ( \theta _ { n + 1 } ) \leq f _ { n _ { 3 } } ( \theta _ { n _ { 3 } } ) - \epsilon _ { 3 } \sum _ { m = n _ { 3 } } ^ { n } \gamma _ { m } \| \nabla f _ { m } ( \theta _ { m } ) \| ^ { \alpha } \\ & \quad + \left ( \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } \| \nabla f _ { m + 1 } ( \theta _ { m + 1 } ) \| ^ { \alpha } \right ) + \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } \\ & \leq f _ { n _ { 3 } } ( \theta _ { n _ { 3 } } ) - \sum _ { m = n _ { 3 } + 1 } ^ { n } \| \nabla f _ { m } ( \theta _ { m } ) \| ^ { \alpha } \left ( \epsilon _ { 3 } \gamma _ { m } - \delta _ { m - 1 } \right ) \\ & \quad + \delta _ { n } \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } + \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } \,. \\ \text{:ceed further assume without loss of generality that $n_{3}$ is sufficiently large so that, for some $\epsilon_{4} \in (0,1), we have} ^ { n } \,.$$

To proceed further assume without loss of generality that n 3 is sufficiently large so that, for some ϵ 4 ∈ (0 1) , , we have ϵ 3 γ n -δ n -1 ≥ ϵ 4 γ n for all n ≥ n 3 . Then, using (14), for all n ≥ n 3 we have

$$\cdot \cdot \cdot \cdot \cdot & \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \\ f _ { n + 1 } ( \theta _ { n + 1 } ) & \leq f _ { n _ { 3 } } ( \theta _ { n _ { 3 } } ) - \epsilon _ { 4 } \epsilon _ { 2 } ^ { \alpha } \left ( \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } \right ) + \delta _ { n } \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } + \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } \\ & = f _ { n _ { 3 } } ( \theta _ { n _ { 3 } } ) - \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } \left ( \epsilon _ { 4 } \epsilon _ { 2 } ^ { \alpha } - \frac { \delta _ { n } \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } } { \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } } - \frac { \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } } { \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } } \right ) \\ \cdot \cdot & \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \end{cases}$$

where, under the assumptions of the theorem,

$$\lim _ { n \to \infty } \frac { \sum _ { m = n _ { 3 } } ^ { n } \delta _ { m } } { \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } } = 0, \quad \lim _ { n \to \infty } \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } = \infty.$$

Therefore, if

$$\lim _ { n \to \infty } \frac { \delta _ { n } \| \nabla f _ { n + 1 } ( \theta _ { n + 1 } ) \| ^ { \alpha } } { \sum _ { m = n _ { 3 } + 1 } ^ { n } \gamma _ { m } } = 0$$

then, by (15), we have lim n →∞ f n +1 ( θ n +1 ) = -∞ which contradicts 1. Hence, to complete the proof it remains to show that (16) holds under the assumption of the theorem.

Remark first that (16) trivially holds under 4a and under 4c. Next, remark that, by (12), for all n ≥ n 3 we have

$$f _ { n } ( \theta _ { n + 1 } ) \leq f _ { n } ( \theta _ { n } ) - \gamma _ { n } \epsilon _ { 1 } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { 2 } \Leftrightarrow \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \alpha } \leq \left ( \frac { f _ { n } ( \theta _ { n } ) - f _ { n } ( \theta _ { n + 1 } ) } { \gamma _ { n } \epsilon _ { 1 } } \right ) ^ { \frac { 3 } { 2 } }$$

from which we readily obtain that (16) holds under 4b.

Finally, by (17), for all n ≥ n 3 we have, under 4d and using (11),

$$\| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \alpha } & \leq \left ( \frac { \tilde { L } _ { n } \| \theta _ { n } - \theta _ { n + 1 } \| ^ { \beta } ) } { \gamma _ { n } \epsilon _ { 1 } } \right ) ^ { \frac { 2 } { 2 } } = \left ( \frac { \tilde { L } _ { n } \gamma _ { n } ^ { \beta } \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \beta } } { \gamma _ { n } \epsilon _ { 1 } } \right ) ^ { \frac { 2 } { 2 } } \\ & \Leftrightarrow \\ & \left \{ \left | \left | \epsilon _ { n } \varepsilon _ { n } \right \} \alpha ( 1 - \beta / 2 ) \right \} \left ( \left | \tilde { L } _ { n } \right \} ^ { \frac { 2 } { 2 } } \right.. \left | \left | \epsilon _ { n } \varepsilon _ { n } \right \} \alpha \right \} \left ( \left | \tilde { L } _ { n } \right \} ^ { \frac { \alpha } { 2 } - \beta }$$

$$\| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \alpha ( 1 - \beta / 2 ) } \leq \left ( \frac { \tilde { L } _ { n } } { \gamma _ { n } ^ { 1 - \beta } \epsilon _ { 1 } } \right ) ^ { \frac { \alpha } { 2 } } \Leftrightarrow \| \nabla f _ { n } ( \theta _ { n } ) \| ^ { \alpha } \leq \left ( \frac { \tilde { L } _ { n } } { \gamma _ { n } ^ { 1 - \beta } \epsilon _ { 1 } } \right ) ^ { \frac { \alpha } { 2 - \beta } }$$

and thus (16) follows. The proof of the theorem is complete.

## 4. Convergence of Alg. 1: deterministic scenario

In this section we show that the results of Subsections 3.2 and 3.3 apply to Alg. 1 in the scenario where π θ,γ is a Gaussian kernel as first introduced in the introduction, Section 1 - some of the intermediate results apply to approximations of the identity, but extension to the general EDM scenario is left for future work. Given an objective function l : R d → R , assumed lower bounded and strongly lower-semi-continuous, we essentially aim to establish epi-convergence to l ( ) · of the sequence of Laplace functionals { h n : R d → R , n ∈ N } , defined, for an approximating sequence of the unity distribution { ψ n : R d → R } , n ∈ N (see Def. 4.1), by

$$h _ { n } ( \theta ) = - \log \int e ^ { - l ( x ) } \psi _ { n } ( x - \theta ) \mathrm d x, \quad \theta \in \mathbb { R } ^ { d }.$$

From this one can apply Theorem C.4 and Theorem 3.2 to characterise local minima. In addition we establish the conditions required for Theorem 3.3 to apply to this scenario.

## 4.1. Epi-convergence of Laplace functionals

It is useful for later calculations to note that by a change of variable z = x -θ we can equivalently write

$$h _ { n } ( \theta ) = - \log \int e ^ { - l ( \theta + z ) } \psi _ { n } ( z ) \mathrm d z.$$

We begin with the definition of mollifiers.

Definition 4.1 (mollifiers) . Let

$$\left \{ \psi _ { n } \, \colon \mathbb { R } ^ { d } \to \mathbb { R } _ { + }, \ \psi _ { n } \in C ^ { 1 } ( \mathbb { R } ^ { d } ), \ \int \psi _ { n } ( z ) d z = 1, \ n \geq 0 \right \}$$

be a class of functions such that for every δ &gt; 0 ,

$$\lim _ { n } \int _ { | | z | | > \delta } \psi _ { n } ( z ) \mathrm d z = 0.$$

We call such ψ n mollifiers.

Example 4.1 (Gaussian mollifiers) . Take ψ n ( z ) = γ -d/ 2 n ϕ zγ ( -1 / 2 n ) with γ n ↓ 0 , n ∈ N , then { ψ , n n ∈ N } satisfy the definition of mollifiers.

The following theorem shows epi-convergence of Laplace functionals with mollifiers. The proof is inspired by ideas of (Ermoliev et al., 1995, Theorems 3.2, 3.7 and Corollary 3.3) but extend their scope.

Theorem 4.1. Let l : R d → R be a lower-bounded, strongly lower-semicontinuous function. Let { ψ n : R d → R + , n ∈ N } be mollifiers. Let h n ( θ ) = -log ´ e -l ( θ + ) z ψ n ( z )d z , θ ∈ R d , n = 1 2 , , . . . . Then, the sequence { h n : R d → R , n ∈ N } epi-converges to l .

Proof. Fix θ ∈ R d . We remark that by Proposition C.1, for a lower-bounded, integrable function f : R d → R , the epi-closure cl e f is a lower-semicontinuous function and the hypo-closure cl h f is an upper-semicontinuous function. Moreover, it holds cl e f ≤ f ≤ cl h f . Note also that if a function f ( ) · is lower-bounded and strongly lower-semicontinuous, then e -f ( ) · is upper-bounded and strongly upper-semicontinuous. We break the proof into three steps.

- · Define g := e -l and g n ( ) := · ´ e - · l ( + z ) ψ n ( z )d z . Let θ n → θ . As first step, we show that

$$\text{cl} _ { e } g ( \theta ) \leq \liminf _ { n } g _ { n } ( \theta _ { n } ) \leq \limsup _ { n } g _ { n } ( \theta _ { n } ) \leq \text{cl} _ { h } g ( \theta )$$

by only using that l is lower-bounded and that { ψ , n n ∈ N } is a sequence of mollifiers. Fix ϵ &gt; 0 .

- · By upper-semicontinuity of cl h e -l , there exists δ = ( ) δ ϵ &gt; 0 such that

$$\text{cl} _ { h } e ^ { - l ( \theta + z ) } \leq \text{cl} _ { h } e ^ { - l ( \theta ) } + \epsilon$$

for all z ∈ R d such that || z || ≤ δ .

- · For the above δ , by definition of the mollifiers { ψ , n n ∈ N } , we can choose n = n ϵ, δ ( ) large enough such that, for all n ≥ n ϵ, δ ( ) ,

$$\iota = \mu \nu \nu, \nu \nu, \\ 0 \leq \int _ { | | z | | > \frac { \delta } { 2 } } e ^ { - l ( \theta + z ) } \psi _ { n } ( z ) d z \leq \sup _ { u \in \mathbb { R } ^ { d } } e ^ { - l ( u ) } \int _ { | | z | | \geq \frac { \delta } { 2 } } \psi _ { n } ( z ) d z \leq \frac { \epsilon } { 2 }.$$

We first show the last inequality in equation (19). Let δ = δ ϵ ( ) as above. For all n ≥ n ϵ, δ ( ) large enough such that || θ n - || ≤ θ δ 2 , we have || θ n -θ + z || ≤ δ for any z such that || z || ≤ δ 2 . So we can write

$$\ e w e { \left | \theta _ { n } - \theta + z \right | } \right | \leq \delta \text{ for any } z \text{ such that } \left | \left | z \right | \right | \leq \frac { \delta } { 2 }. \text{ So we can write } \\ g _ { n } ( \theta _ { n } ) & = \int e ^ { - l ( \theta _ { n } + z ) } \psi _ { n } ( z ) d z \\ & = \int _ { \left | \right | z \right | \left | \leq \frac { \delta } { 2 } } e ^ { - l ( \theta _ { n } + z ) } \psi _ { n } ( z ) d z + \int _ { \left | \right | z \right | \right | > \frac { \delta } { 2 } } e ^ { - l ( \theta _ { n } + z ) } \psi _ { n } ( z ) d z \\ & \leq \int _ { \left | \right | z \right | \left | \leq \frac { \delta } { 2 } } \text{cl} _ { h } e ^ { - l ( \theta _ { n } + z ) } \psi _ { n } ( z ) d z + \frac { \epsilon } { 2 } \\ & = \int _ { \left | \right | z \right | \left | \leq \frac { \delta } { 2 } } \text{cl} _ { h } e ^ { - l ( \theta + \theta _ { n } - \theta + z ) } \psi _ { n } ( z ) d z + \frac { \epsilon } { 2 } \\ & \leq ( \text{cl} _ { h } e ^ { - l ( \theta ) } + \epsilon ) \int _ { \left | \right | z \right | \left | \leq \frac { \delta } { 2 } } \psi _ { n } ( z ) d z + \frac { \epsilon } { 2 } \\ \text{ge enough we have }$$

Hence, for n large enough we have

$$g _ { n } ( \theta _ { n } ) \leq \text{cl} _ { h } e ^ { - l ( \theta ) } + \epsilon + \frac { \epsilon } { 2 }$$

$$\lim _ { n } \sup _ { g _ { n } } g _ { n } ($$

$$( 2 1 )$$

so for any ϵ &gt; 0

Therefore, by taking ϵ → 0 , we obtain

$$\lim _ { n } \sup _ { g _ { n } } g _ { n } ($$

The middle inequality in (19) is obvious, while the first can be proven in a very similar way, using positivity from equation (20) and the fact that, for n large-enough, ´ || z ||≤ δ 2 ψ n ( z )d z ≥ 1 -ϵ 2 .

- · The next step is to show that g n hypo-converges to g . Here we use strong lower-semicontinuity of l .
- · As g = e -l is upper-semicontinuous, it holds that g = cl h g by Proposition C.1. Hence, by equation (21), for any θ ∈ R d and any sequence { θ n , n ∈ N } with θ n → θ , we have

$$\lim _ { n } \sup _ { n } g _ { n } ( \theta _$$

- · It remains to show that for any θ ∈ R d , lim n g n ( θ n ) = g θ ( ) for at least one sequence such that θ n → θ . Here we use Lemma 4.2.
- · We finally show that { h , n n ∈ N } epi-converges to l , based on the above results, continuity and monotonicity of log , and on the fact that, by definition, if { f n : R d → R , n ∈ N } is a sequence of functions that hypo-converge to f : R d → R , then {-f n , n ∈ N } epi-converge to -f . In detail: by continuity and monotonicity of log( ) · and by hypo-convergence of g n to g , we can first show that { log( g n ) , n ∈ N } hypo-converges to log( g ) = -l . Indeed, the following chain of inequalities holds for any sequence { θ n , n ∈ N } with θ n → θ :

$$\begin{array} {$$

Hence the first condition for hypo-convergence of { log( g n ) , n ∈ N } to log( g ) = -l holds. For the second condition, we just use hypo-convergence of { g n , n ∈ N } to g and continuity of log . Note that the above chain of inequalities would hold for any non-decreasing continuous transformation. Finally, as h n = -log( g n ) , we conclude that { h , n n ∈ N } epi-converge to l .

↦

↦

Compared to the results by Ermoliev, we can work with mollifiers with unbounded support with one less assumption: Ermoliev requires that for any δ &gt; 0 lim n ´ {|| z || &gt;δ } | l ( θ + ) z | ψ n ( z )d z = 0 uniformly in θ ∈ R d , to control the tail behaviour. Here we can avoid an assumption of this kind as the mollifiers weight the function x → e -l ( x ) , which is upper-bounded when x → l ( x ) is lower-bounded.

When the objective is continuous, we obtain stronger convergence results.

Lemma 4.1. Under the conditions of Theorem 4.1, if l is also continuous, then the sequence { h , n n ∈ N } converges continuously to l , that is, lim n h n ( θ n ) = l ( θ ) for any sequence { θ n , n ∈ N } such that θ n → θ , for any θ ∈ R d . This also implies that the sequence converges uniformly to l on compact subsets of R d .

Proof. For a continuous function f : R d → R , cl e f = cl h f = f by Proposition C.1. Hence the statement about continuous convergence follows by the same steps that lead to equation (19) in Theorem 4.1, combined with continuity of log( ) · . The statement about uniform convergence on compact sets follows by (Rockafellar and Wets, 1998, Theorem 7.14).

Lemma 4.2. Let l : R d → R be a lower-bounded, strongly lower-semicontinuous function. Let

$$\left \{ \psi _ { n } \, \colon \mathbb { R } ^ { d } \rightarrow \mathbb { R } _ { + }, \, \int \psi _ { n } ( z ) \mathrm d z = 1, \ n \in \mathbb { N } \right \}$$

be a sequence of functions such that, for any δ &gt; 0 , lim n ´ || z ||≥ δ ψ n ( z )d z = 0 . Let g θ ( ) := e -l ( θ ) and g n ( θ ) := ´ e -l ( θ + ) z ψ n ( z )d z , θ ∈ R d , n = 1 2 , , . . . . Then, for any θ ∈ R d , there is at least one sequence { θ n , n ∈ N } such that

$$\lim _ { n } g _ { n } ( \theta _ { n } ) = g ( \theta ).$$

Proof. The proof is given in (Ermoliev et al., 1995, Theorem 3.7). Let ¯ := g -g and ¯ g n := -g n . We already now that ¯ g is strongly lower-semicontinuous and that lim inf n ¯ ( g n θ n ) ≥ ¯( g θ ) for all sequences { θ n , n ∈ N } such that θ n → θ .

We show lim n ¯ ( g n θ n ) = ¯( g θ ) for at least one sequence θ n → θ . Here we use strong lower-semicontinuity and proceed as follows. By strong lower-semicontinuity of ¯ g , there exists a sequence θ k → θ such that lim k ¯( g θ k ) = ¯( g θ ) , with ¯ g continuous at θ k . Lemma 4.1 states that under (local) continuity we have that, for all k ≥ 0 ,

$$\lim _ { n } \bar { g } _ { n } ( \theta _ { k } ) = \bar { g } ( \theta _ { k } )$$

Now note that set S := { ¯( g θ k ); k ∈ N } is such that S ∈ Liminf n S n , S n := { ¯ ( g n θ k ); k ∈ N } where we recall that S ∈ Liminf n S n consists of all limit points of sequences { α , n n ∈ N } with α n ∈ S n . By definition, Liminf n S n is closed and, moreover, ¯( g θ ) ∈ cl ( S ) , where cl ( ) · denotes the closure of a set. This means that there exists a sequence { α , n n ∈ N } s.t. lim n α n = ¯( ) g θ with α n ∈ S n . Then let θ n be such that ¯ ( g n θ n ) = α n , n = 1 2 , , . . . to obtain the result. Since ¯ = g -g and ¯ g n = -g n , n = 1 2 , , . . . , the result translates to { g n , n ∈ N } and g .

## 4.2. Descent lemma for Laplace functionals

We show that a crucial convexity property from the theory of exponential families allows us to derive a Descent Lemma for Laplace functionals. The Descent Lemma is derived in the general case in terms of the Bregman divergence, along the lines of Bolte et al. (2018). The result for the Gaussian algorithm is then recovered as a simple by-product.

Definition 4.2 (Bregman divergence) . Let u : R d → R be a differentiable function. The Bregman divergence D u : R d × R d → R associated with u is defined as

$$D _ { u } ( x, y ) = u ( x ) - u ( y ) - \langle \nabla u ( y ), x - y \rangle, \ x, y \in \mathbb { R } ^ { d }.$$

Properties. For any x, y ∈ R d ,

- 1. For any pair of differentiable functions u , u 1 2 : R d → R ,

$$D _ { \alpha u _ { 1 } + \beta u _ { 2 } } ( x, y ) = \alpha D _ { u _ { 1 } } ( x, y ) + \beta D _ { u _ { 2 } } ( x, y ).$$

- 2. For any differentiable, convex function u : R d → R , we also have that

$$D _ { u } ( x, y ) \geq 0$$

$$w i t h \, { \mathrm D } _ { u } ( x, y ) = 0 \ i f f \, x = y.$$

We can now state the general Descent Lemma.

Theorem 4.2 (Descent Lemma) . Consider a function l : R d → R and for γ &gt; 0 , θ ∈ R d consider an exponential model (see Appendix B.2)

$$\pi _ { \theta, \gamma } ( x ) \coloneqq \eta ( \gamma, x ) \exp \left \{ \gamma ^ { - 1 } \left [ \langle \theta, T ( x ) \rangle - A ( \theta ) \right ] \right \}$$

with sufficient statistic T : R d → R d and log-partition function A : R d → R . Let

$$h _ { \gamma } ( \theta ) \coloneqq - \log \int \exp ( - l ( x ) ) \pi _ { \theta, \gamma } ( x ) \mathrm d x, \ \theta \in \mathbb { R } ^ { d }$$

and assume ´ exp( -l ( x )) π θ,γ ( x )d x &lt; ∞ for any θ ∈ R d . Then, for any θ, θ ′ ∈ R d , it holds that

$$h _ { \gamma } ( \theta ^ { \prime } ) \leq h _ { \gamma } ( \theta ) + \langle \nabla h _ { \gamma } ( \theta ), \theta ^ { \prime } - \theta \rangle + \frac { 1 } { \gamma } \mathrm D _ { A } ( \theta ^ { \prime }, \theta ),$$

Proof. Let x, θ ∈ R d and γ &gt; 0 . Consider the exponential model from the assumption

$$\pi _ { \theta, \gamma } ( x ) = \eta ( \gamma, x ) \exp \left \{ \frac { 1 } { \gamma } \left [ \langle \theta, T ( x ) \rangle - A ( \theta ) \right ] \right \}$$

and let

$$\tilde { \pi } _ { \theta, \gamma } ( x ) \in \exp \left ( - l ( x ) \right ) \pi _ { \theta, \gamma } ( x ).$$

Note that

$$\tilde { \pi } _ { \theta, \gamma } ( x ) = \exp \left ( - l ( x ) \right ) \eta ( \gamma, x ) \exp \left \{ \frac { 1 } { \gamma } \left [ \langle \theta, T ( x ) \rangle - A ( \theta ) \right ] + h _ { \gamma } ( \theta ) \right \}$$

that is, the distribution ˜ π θ,γ still belongs to the regular (in the sense of Definition B.2) exponential family, with log-partition function given by

$$\tilde { A } ( \theta ) = A ( \theta ) - \gamma h _ { \gamma } ( \theta ).$$

↦

↦

$$D _ { \tilde { A } } ( \theta ^ { \prime }, \theta ) & \geq 0.$$

The Bregman divergence D ˜ A is well-defined as both θ → A θ ( ) and θ → h γ ( θ ) are differentiable functions. By (Wainwright and Jordan, 2008, Proposition 3.1), ˜ ( A θ ) is convex. From the properties of the Bregman divergence, we note that the convexity of ˜ A implies that for all θ, θ ′ ∈ R d

By the linearity property, we have

$$0 \leq D _ { \tilde { A } } ( \theta ^ { \prime }, \theta ) = D _ { A - \gamma h _ { \gamma } } ( \theta ^ { \prime }, \theta ) = D _ { A } ( \theta ^ { \prime }, \theta ) - \gamma D _ { h _ { \gamma } } ( \theta ^ { \prime }, \theta )$$

and using the definition of the Bregman Divergence, one obtains

$$\gamma \left \{ h _ { \gamma } ( \theta ^ { \prime } ) - h _ { \gamma } ( \theta ) - \langle \nabla h _ { \gamma } ( \theta ), \theta ^ { \prime } - \theta \rangle \right \} \leq \mathrm D _ { A } ( \theta ^ { \prime }, \theta ).$$

That is,

$$h _ { \gamma } ( \theta ^ { \prime } ) \leq h _ { \gamma } ( \theta ) + \langle \nabla h _ { \gamma } ( \theta ), \theta ^ { \prime } - \theta \rangle + \frac { 1 } { \gamma } \mathrm D _ { A } ( \theta ^ { \prime }, \theta ),$$

which concludes the proof.

In the Gaussian case, as a corollary, we recover a standard Descent Lemma in terms of the Euclidean distance.

Corollary 4.1. Consider a function l : R d → R . For γ &gt; 0 , let h γ ( θ ) := -log ´ exp( -l ( x )) ϕ ( x -θ √ γ ) d x , θ ∈ R d and assume ´ exp( -l ( x )) ϕ ( x -θ √ γ ) d x &lt; ∞ for any θ ∈ R d . Then, for any θ, θ ′ ∈ R d , it holds that

$$h _ { \gamma } ( \theta ^ { \prime } ) \leq h _ { \gamma } ( \theta ) + \langle \nabla h _ { \gamma } ( \theta ), \theta ^ { \prime } - \theta \rangle + \frac { 1 } { 2 \gamma } | | \theta ^ { \prime } - \theta | | ^ { 2 }.$$

Proof. This follows directly from Theorem 4.2 by noting that, for π θ,γ ( ) · := γ -d/ 2 ϕ ( ·-θ √ γ ) , one has A θ ( ) = || θ || 2 2 and D ( A θ, θ ′ ) = 1 2 || θ ′ - || θ 2 , for any θ, θ ′ ∈ R d .

## 4.3. Proof of Theorem 1.1

We note here that the Laplace functionals satisfy the conditions of Theorem 3.3 when the mollifiers are Gaussian; specifically, assumption 2 follows by Corollary 4.1 and assumption 3 by Lemma 4.3, which we prove below. This, combined with epi-convergence of Laplace functionals (Theorem 4.1) and our characterisation of local minima under epi-convergence (Theorem 3.2), proves Theorem 1.1.

In the proof below we specifically denote the univariate Gaussian density by ϕ z ( ) := (2 π ) -1 / 2 e -z 2 / 2 , x ∈ R , hence ψ z ( ) := ∏ d i =1 γ -1 / 2 ϕ z / ( i √ γ ) , z = ( z , . . . , z 1 d ) ∈ R d , is a multivariate Gaussian with covariance γ I d , γ &gt; 0 , and zero mean. This notation is consistent with the mollifiers' framework presented in subsection 4.1.

Lemma 4.3. Let { γ n , n ∈ N } be a sequence on (0 , ∞ ) such that lim n →∞ γ n = 0 and such that γ n +1 ≤ γ n for all n ≥ 1 , and for all n ∈ N let ψ n ( z ) = ∏ d i =1 γ -1 / 2 n ϕ z / ( i √ γ n ) . Assume that there exists a constant C l ∈ (0 , ∞ ) such that | l ( θ ′ ) -l ( θ ) | ≤ C l + C l ∥ θ -θ ′ ∥ 2 for all θ, θ ′ ∈ R d and let

$$\delta _ { n } = \left ( ( \gamma _ { n } / \gamma _ { n + 1 } ) ^ { d / 2 } - 1 \right ) ( \gamma _ { n } + 1 ) + ( \gamma _ { n } - \gamma _ { n + 1 } ) + \gamma _ { n } ^ { 2 }, \ \forall n \geq 1.$$

Then, there exists a constant ¯ C ∈ (0 , ∞ ) and an n ′ ∈ N such that

$$\sup _ { \theta \in \mathbb { R } ^ { d } } \left ( h _ { n + 1 } ( \theta ) - h _ { n } ( \theta ) \right ) \leq \bar { C } \delta _ { n }, \ \forall n \geq n ^ { \prime }.$$

Remark 4.1. If γ n = n -β for all n ≥ 1 and some β ∈ (0 1) , . Then, ∑ n ≥ 1 γ n = ∞ and, since we have ( γ n /γ n +1 ) d/ 2 -1 ≈ n -1 and γ n -γ n +1 = n - -β 1 , it follows that δ n = O ( γ n ) and thus δ n /γ n → 0 .

Proof. Let n ≥ 1 and θ ∈ R d . If g n ( θ ) ≤ g n +1 ( θ ) we have h n +1 ( θ ) -h n ( θ ) ≤ 0 and thus below we assume that g n +1 ( θ ) ≤ g n ( θ ) . Then, using the fact that for any real numbers 0 &lt; x &lt; y we have log( y ) -log( x ) ≤ ( y -x /x ) , it follows that

$$h _ { n + 1 } ( \theta ) - h _ { n } ( \theta ) \leq \frac { g _ { n } ( \theta ) - g _ { n + 1 } ( \theta ) } { g _ { n + 1 } ( \theta ) }.$$

To proceed further let c n = ( γ n /γ n +1 ) d/ 2 ≥ 1 and note that

$$0 \leq \frac { \psi _ { n + 1 } ( x - \theta ) } { \psi _ { n } ( x - \theta ) } \leq c _ { n }, \ \forall x \in \mathbb { R } ^ { d }.$$

In addition, let n ′ ∈ N be such that γ m ≤ 1 (4 / C l ) for all m ≥ n ′ , with C l as in the statement of the lemma. Then, assuming that n ≥ n ′ , we have

$$\text{In addition, let $n^{\prime}\in N$ be such that $\gamma_{m}\leq 1/(4C_{i})$ for all $m\geq n^{\prime},$ with $C_{i}$ as in the statement of the lemma.  Then,} \\ \text{assuming that $n\geq n^{\prime},$ we have} \\ g _ { n } ( \theta ) - g _ { n + 1 } ( \theta ) & = \int e ^ { - l ( x ) } \Big ( \psi _ { n } ( x - \theta ) - \psi _ { n + 1 } ( x - \theta ) ) d x \\ & = e ^ { - l ( \theta ) } \int e ^ { - ( l ( x ) - l ( \theta ) ) } \Big ( \psi _ { n } ( x - \theta ) - \psi _ { n + 1 } ( x - \theta ) ) d x \\ & = e ^ { - l ( \theta ) } \int e ^ { - ( l ( x ) - l ( \theta ) ) } \Big ( c _ { n } - \psi _ { n + 1 } ( x - \theta ) } \Big ) \psi _ { n } ( x - \theta ) d x \\ & \leq e ^ { - l ( \theta ) } \int e ^ { - ( l ( x ) - l ( \theta ) ) } \Big ( c _ { n } - \psi _ { n + 1 } ( x - \theta ) } \Big ) \psi _ { n } ( x - \theta ) d x \\ & \leq e ^ { - l ( \theta ) + C _ { l } } \int e ^ { C _ { l } | | x - \theta | | ^ { 2 } } \Big ( c _ { n } - \psi _ { n + 1 } ( x - \theta ) } \Big ) \psi _ { n } ( x - \theta ) d x \\ & = e ^ { - l ( \theta ) + C _ { l } } \Big ( c _ { n } \int e ^ { C _ { l } | | x - \theta | | ^ { 2 } } \psi _ { n } ( x - \theta ) d x - \int e ^ { C _ { l } | | x - \theta | | ^ { 2 } } \psi _ { n + 1 } ( x - \theta ) d x \Big ) \\ & = e ^ { - l ( \theta ) + C _ { l } } \Big ( c _ { n } ( 1 - 2 C _ { l } \gamma _ { n } ) ^ { - d / 2 } - ( 1 - 2 C _ { l } \gamma _ { n + 1 } ) ^ { - d / 2 } \Big ). \\ \text{Using Taylor's theorem, there exists a constant $C^{<} \, <} \infty$ such that} \\.. \quad - - - - - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cdots - \cd$$

Using Taylor's theorem, there exists a constant C &lt; ∞ such that

$$\text{using any non-unused, one can use a common } \cup \times \infty \, \text{and} \, \quad \\ c _ { n } ( 1 - 2 C _ { l } \gamma _ { n } ) ^ { - d / 2 } - ( 1 - 2 C _ { l } \gamma _ { n + 1 } ) ^ { - d / 2 } & \leq c _ { n } ( 1 + d C _ { l } \gamma _ { n } + C \gamma _ { n } ^ { 2 } ) - ( 1 + d C _ { l } \gamma _ { n + 1 } - C \gamma _ { n + 1 } ^ { 2 } ) \\ & = ( c _ { n } - 1 ) ( d C _ { l } \gamma _ { n } + 1 ) + d C _ { l } ( \gamma _ { n } - \gamma _ { n + 1 } ) + C ( \gamma _ { n } ^ { 2 } + \gamma _ { n + 1 } ^ { 2 } ) \\ & \leq \max \{ 1, d C _ { l }, 2 C \} \left ( ( c _ { n } - 1 ) ( \gamma _ { n } + 1 ) + ( \gamma _ { n } - \gamma _ { n + 1 } ) + \gamma _ { n } ^ { 2 } \right ) \\ & = \max \{ 1, d C _ { l }, 2 C \} \delta _ { n } \\ \dots \, \cdots \, \cdots \, \cdots \, \quad \, \sim \, \cdots \, \quad \, \sim \, \cdots \, \quad \, \cdots \, \quad \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cd: \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdclots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \cdots \, \quad \, \end{$$

which, together with (26)-(27) and letting C ′ = e C l max 1 { , dC , l 2 C } , shows that

$$h _ { n + 1 } ( \theta ) - h _ { n } ( \theta ) \leq \delta _ { n } \frac { C ^ { \prime } e ^ { - l ( \theta ) } } { g _ { n + 1 } ( \theta ) }.$$

On the other hand,

$$r \, \text{hand}, & & g _ { n + 1 } ( \theta ) = \int \exp ( - l ( \theta + \gamma _ { n + 1 } ^ { \frac { 1 } { 2 } } z ) ) \prod _ { i = 1 } ^ { d } \phi ( z _ { i } ) d z \\ & = e ^ { - l ( \theta ) } \int \exp \left ( - \left ( l ( \theta + \gamma _ { n + 1 } ^ { \frac { 1 } { 2 } } z ) - l ( \theta ) \right ) \right ) \prod _ { i = 1 } ^ { d } \phi ( z _ { i } ) d z \\ & \geq e ^ { - l ( \theta ) - C _ { i } } \int \exp ( - C _ { l } \gamma _ { n + 1 } z ^ { 2 } ) \prod _ { i = 1 } ^ { d } \phi ( z _ { i } ) d z \\ & = e ^ { - l ( \theta ) } \left ( e ^ { - C _ { l } } ( 1 + 2 C _ { l } \gamma _ { n + 1 } ) ^ { - 1 / 2 } \right ) \\ & \geq e ^ { - l ( \theta ) } e ^ { - C _ { l } } ( 1 + 2 C _ { l } \gamma _ { 1 } ) ^ { - 1 / 2 }$$

where the last inequality uses the fact that the sequence { γ n , n ∈ N } is assumed to be non-increasing. By combining (28) and (29), we obtain

$$h _ { n + 1 } ( \theta ) - h _ { n } ( \theta ) \leq \bar { C } \delta _ { n }, \ \bar { C } = C ^ { \prime } e ^ { C _ { l } } \left ( e ^ { - C _ { l } } ( 1 + 2 C _ { l } \gamma _ { 1 } ) ^ { 1 / 2 } \right )$$

and the proof of the lemma is complete.

## 5. Discussion

We briefly discuss links to the literature and possible extensions we are currently exploring or have not explored yet.

Convergence in the noisy case We are currently developing theory for the noisy version of the algorithm Alg. 2, aiming to obtain almost sure convergence results using stochastic gradient techniques. Epi-convergence of the Laplace functionals follows along similar lines to those of the deterministic while convergence can easily be framed in terms of stable trajectories; establishing stability remains the challenge we are working on.

Links to other optimisation schemes Algorithm 1 is reminiscent of the cross-entropy (CE) method (Rubinstein and Kroese, 2004), which also relies on exponential families and Kullback-Leibler minimisation. In the Gaussian case however, CE would require estimating both the mean and the covariance matrix of the current Gaussian approximation; while in our case we impose the covariance matrix to evolve according to a pre-determined schedule. This point seems crucial in our theoretical derivations. On the other hand, to the best of our knowledge, convergence of the CE method for a general class of objective functions has not been established; see e.g. for some numerical evidence it may not converge in some reinforcement learning scenarios Szita and Lörincz (2006).

For completeness, we discuss here a variation on our algorithm which can be shown to be equivalent to an time inhomogeneous proximal minimisation recursion. A natural modification of our algorithm consists of inverting the order of the distributions in the minimisation step of the KL divergence; see Alg. 3.

In independent recent work, Osher et al. (2023) and Tibshirani et al. (2024), a recursion similar to ours is proposed, albeit with fixed stepsizes. Perspective of their work is however significantly different from ours, which leads to a number of differences. While our algorithm was motivated by Bayes' rule and the potential use of general SMC sampler schemes, techniques the present authors are very familiar with, the recursion in Osher et al. (2023); Tibshirani et al. (2024) is obtained by considering a Gaussian transformation to a Hamilton Jacobi system of partial differential equations representing the Moreau envelope of a proximal minimisation problem, and therefore relates to infinitesimal convolutions. The statistical filiation of our work naturally leads to considering general EDM kernels, therefore extending the scope of the approach to more general scenarios, which together with known facts on KL divergence for exponential families lead to our crucial interpretation of the algorithm as a time inhomogeneous gradient descent algorithm, both in the deterministic and stochastic scenarios.

## Algorithm 3 Proximal version

## Input:

↦

x → l ( x ) ▷ objective function θ 0 , { γ , k k ≥ 0 } ▷ initial value and stepsizes π 0 ( x ) = π θ 0 ,γ 0 ( x ) ▷ initial distribution while n ≥ 0 do ˜ π n +1 ( x ) ∝ exp( -l ( x )) π n ( x ) ▷ generalised bayesian rule θ n +1 ∈ argmin θ ∈ Θ KL( π θ,γ n , π ˜ n +1 ) ▷ minimisation of Kullback-Leibler divergence Set π n +1 = π θ n +1 ,γ n +1 ▷ distribution shrinking end while Output: sequence of distributions ˜ π n and parameters θ n .

Link to proximal minimisation can be obtained by application of Lemma D.1 which establishes that Alg. 3 generates a sequence { θ n ∈ R d , n ∈ N } such that

$$\theta _ { n + 1 } = \underset { \theta } { \arg \min } \left \{ F _ { \gamma _ { n } } ( \theta ) + \text{KL} ( \pi _ { \theta, \gamma _ { n } }, \pi _ { \theta _ { n }, \gamma _ { n } } ) \right \}, \ n \in \mathbb { N },$$

↦

where F γ ( θ ) := ´ l ( x π ) θ,γ ( x )d x , θ ∈ R d , γ &gt; 0 . We see that the algorithm aims to adjust π θ,γ to decrease θ → F γ ( θ ) subject to a proximal penalty, which is reminiscent of proximal Expectation-Maximization (EM) algorithms. When π θ,γ is a Gaussian, KL( π θ,γ n , π θ n ,γ n ) = (2 γ n ) -1 || θ -θ n || 2 , and interpretation in terms of an inhomogeneous (vanilla) proximal minimisation algorithm should be clear. Note that, however, in the general case of exponential families we have that for any n ∈ N , KL( π θ,γ n , π θ n ,γ n ) is the Bregman divergence D ( A θ n , θ ) (see Lemma B.1), convex in the first variable but not necessarily in the second. Hence Alg. 3 above cannot always be interpreted as a proximal algorithm. Despite its theoretical attractiveness we have not pursued this proximal approach here since its implementation seems to require another minimisation procedure, in contrast with our approach.

In the very last stages of preparing this manuscript Sam Power has pointed out the reference Spokoiny (2023) where an update similar to our update with Gaussian kernel is suggested. However this is where similarities seem to end as the motivation appears slightly different and the analysis of the properties of the algorithm significantly different, in particular requiring differentiability of l ( ) · and using concentration properties. In contrast we identify an underlying inhomogeneous gradient algorithm, which leads to convergence results in a more general setup. However understanding to what extent the results of the type developed Spokoiny (2023); Nesterov and Spokoiny (2017) could be extended to a more general scenario would be of interest.

Choice of transformation in the Bayesian update A natural extension of Alg.1 consists of considering more general transformation of the objective function involved in the Bayesian update other than the exponential. In general a nonnegative, decreasing function g ( ) · such that log ´ | ( g ◦ l )( x ) | π θ,γ ( x )d x &lt; ∞ for any θ ∈ R d and γ &gt; 0 could be used. The implementation technique remains unchanged, and so does the interpretation as an inhomogeneous mirror descent on smooth approximations of l ( ) · . More specifically with

$$\pi _ { \theta, \gamma } ( x ) = \eta ( \gamma, x ) \exp \left \{ \frac { 1 } { \gamma } \left [ \langle \theta, T ( X ) \rangle - A ( \theta ) \right ] \right \} \,,$$

↦

where T : R d → R d , an exponential model with log-partition function θ → A θ ( ) , θ ∈ R d the Bayes update yields

$$\tilde { \pi } _ { \theta, \gamma } ( x ) = g ( l ( x ) ) \eta ( \gamma, x ) \exp \left \{ \frac { 1 } { \gamma } \left [ \langle \theta, T ( X ) \rangle - A ( \theta ) \right ] - \log \pi _ { \theta, \gamma } ( g ( l ) ) \right \}$$

## Algorithm 4 Deterministic Gradient-Free Ideal Algorithm with general transformation

## Input:

↦

```
Input:
    x \mapsto l ( x )                                                                                                                                                                                                        
    \theta _ { 0 }, \{ \gamma, k \geq 0 \}                                                                                                                                                                                                        \
    \pi _ { 0 } ( x ) = \pi _ { 0 } \nolimits ( x )                                                                                                                                                                                                     \
  \emph { \nolimits initial distribution} } \\ \emph { while } n \geq 0 do } \\ \tilde { \pi _ { n + 1 } ( x ) \in g ( l ( x ) ) \pi _ { n } ( x ) } \\ \tilde { \theta _ { n + 1 } \in \argmin _ { 0 } \geq 0 } K L ( \tilde { \pi _ { n + 1 }, \pi _ { \gamma _ { n } } } ) \, \rightarrow \text{project with Kullback-Leibler divergence} \\ \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph  \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph
 \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph. \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph	 \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph | \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph } \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph - \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph{ \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph. \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph'\emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph [ \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph- \emph { \emph { \emph { \emph { \emph { \emph { \emph
 \emph { \emph { \emph
 \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph
 \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph
 \emph { \emph { \emph { \emph { \emph { \emph { \emph { \emph
 \emph { \emph { \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \emph. \end} } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }
```

Output: sequence of distributions ˜ π n and parameters θ n .

which still belongs to the exponential family and has cumulant function

$$\tilde { A } ( \theta ) = A ( \theta ) + \gamma \log \pi _ { \theta, \gamma } ( g ( l ) ), \ \theta \in \mathbb { R } ^ { d }.$$

By essentially repeating the same reasoning as for Alg. 1 one finds that the algorithm is equivalent to the recursion

$$\mu _ { n + 1 } = \mu _ { n } + \gamma _ { n } \nabla _ { \theta } \log \pi _ { \theta _ { n }, \gamma _ { n } } ( g ( l ) )$$

(30)

where µ n := ´ T x π ( ) θ n ,γ n ( x )d x . Equivalently, in terms of natural parameter

$$\nabla A ( \theta _ { n + 1 } ) = \nabla A ( \theta _ { n } ) + \gamma _ { n } \nabla _ { \theta } \log \pi _ { \theta _ { n }, \gamma _ { n } } ( g ( l ) ).$$

If the family is also minimal, then ∇ A is invertible with ( ∇ A ) -1 = ∇ A ∗ , its dual gradient (Appendix B.1), and

$$\theta _ { n + 1 } & = \nabla A ^ { * } ( \nabla A ( \theta _ { n } ) + \gamma _ { n } \nabla _ { \theta } \log \pi _ { \theta _ { n }, \gamma _ { n } } ( g ( l ) ) ). & ( 3 2 )$$

We leave investigation of the choice of g for future work.

## A. Notation

List of notation.

- · R d , d ≥ 1 denotes the real coordinate d -space, and B ( R d ) its Borel sigma-algebra.
- · R + denotes the set of positive real numbers including zero.
- · M 1 + ( R d ) is the set of probability measures on the space R d .
- · For ν, ρ ∈ M 1 + ( R d ) , we write ν ≪ ρ if ν is absolutely continuous with respect to ρ .
- · For a measure π ∈ M 1 + ( R d ) that is absolutely continuous with respect to the Lebesgue measure, we again denote by π its density. In formulae, we write π (d x ) = π x ( )d x .
- · Wesometimes adopt the linear functional notation for integrals with respect to measures, writing π f ( ) for ´ f ( x π ) (d x ) , for measurable functions f .
- · We denote expectation operator by E . When we need to specify the probability measure ν of integration, we sometimes write E ν f ( X ) for ν f ( ) .
- · For µ, ν ∈ M 1 + ( R d ) with absolutely continuous density (with respect to the Lebesgue measure), we denote the Kullback-Leibler divergence by KL( µ, ν ) := ´ µ x ( ) log µ x ( ) ν x ( ) d x .
- · Given a point θ ∈ R d and a sequence { θ n ∈ R d , n ∈ N } , we say that lim n →∞ θ n = θ if for every ϵ &gt; 0 there exists number n 0 = n 0 ( ϵ ) ∈ N such that, for every n ≥ n 0 , || θ n - || θ &lt; ϵ. We also write, with the same meaning, θ n → n θ or θ n → θ when there is no ambiguity. As a shortcut, we sometimes denote the limit operation lim n →∞ as lim n .
- · Similarly, we write lim inf n , lim sup n for lim inf n →∞ , lim sup n →∞ , respectively.
- · For a sequence { α n ∈ R + , n ∈ N } that decreases to zero, we write α n ↓ 0 .
- · The closure of a set A ⊂ R d is denoted by cl( A ) and corresponds to the intersection of all closed subsets of R d containing A .
- · For two sets C , C 1 2 of R d , we denote their elementwise (Minkowsky) sum by C 1 + C 2 := { x + ; y x ∈ C , y 1 ∈ C 2 }
- · Let ( R d ) N denote the space of sequences { θ n ∈ R d , n ∈ N } . Let { θ n } ∈ ( R d ) N . Given g : ( R d ) N → R , we write inf θ n → θ g ( { θ n } ) for inf { g ( { θ n } ); θ n ∈ R d , n ∈ N , θ n → θ } .
- · C 1 ( R d ) denotes the class of functions f : R d → R with continuous gradient. Gradient operators are denoted by ∇ , or ∇ θ when we need to specify that the variable of differentiation is θ
- · The d -dimensional standard normal density is denoted as ϕ z ( ) := 1 (2 π ) d/ 2 e -|| z || 2 2 , z ∈ R d .
- · Given two functions f, g : R d → R , we write f ≥ g if f ( θ ) ≥ g θ ( ) ∀ θ ∈ R d .
- · The Dirac Delta measure on zero is denoted as δ 0 (d x ) .
- · For two vectors θ, θ ′ ∈ R d , we denote their Euclidean inner product by ⟨ θ, θ ′ ⟩ .
- · The notation

## argmin f

stands for argmin u ∈ R d f ( u ) and denotes the set of global minima of a function f : R d → R .

- · The set of local minima of a function f is denoted by

loc -argmin f.

## B. Exponential family background

## B.1. Natural exponential families

For x, θ ∈ R d , T : R d → R d and a baseline measure υ on R d , we consider a (natural) exponential family to be a distribution of the form

$$\pi _ { \theta } ( \mathrm d x ) = \exp \left \{ \langle x, T ( x ) \rangle - A ( \theta ) \right \} \upsilon ( \mathrm d x ) \,,$$

where the cumulant function for T X ( ) is

$$A ( \theta ) = \log \int \exp \left ( \langle \theta, T ( x ) \rangle \right ) \upsilon ( \mathrm d x ) \,.$$

Here the canonical parameter θ of interest belongs to the set

$$\Theta \coloneqq \left \{ \theta \in \mathbb { R } ^ { d } \colon \ A ( \theta ) < \infty \right \}.$$

Definition B.1. Given an exponential family distribution with sufficient statistic T : R d → R d , we say that the model is minimal if the elements of T are linearly independent, that is, if there is no nonzero vector a ∈ R d s.t. ∑ d i =1 a T i i ( x ) is equal to a constant υ -almost everywhere. This implies that there is a unique natural parameter vector θ associated with each distribution.

↦

Definition B.2. An exponential family with log-partition function θ → A θ ( ) is said to be regular when the domain Θ is an open set.

Examples of minimal and regular exponential families include Bernoulli, Gaussian, Exponential, Poisson, and Beta distributions.

Proposition B.1. (Wainwright and Jordan, 2008, Proposition 3.1). The log-partition function

$$A ( \theta ) \coloneqq \log \int \exp \langle \theta, T ( x ) \rangle \upsilon ( \mathrm d x ), \ \theta \in \mathbb { R } ^ { d }$$

associated with any regular exponential family with sufficient statistic T : R d → R d has the following properties

- 1. It has derivatives of all orders on its domain Θ , furthermore,

$$\nabla A ( \theta ) & = \mathbb { E } _ { \pi _ { \theta } } T ( X ) \\ \nabla ^ { 2 } A ( \theta ) & = \text{var} _ { \pi _ { \theta } } ( T ( X ) )$$

↦

2. θ → A θ ( ) is a convex function on Θ , and strictly convex if the representation is minimal.

The convexity argument comes from the fact that the full Hessian ∇ 2 A θ ( ) is the covariance matrix of the random vector T X ( ) , and so is positive semidefinite on the open set Θ , which ensures convexity.

We now report an important dual coupling property of exponential families. Let

$$\mathcal { M } \coloneqq \left \{ \mu \in \mathbb { R } ^ { d } ; \, \exists \, \theta \text{ s.t.} \, \mathbb { E } _ { \pi _ { \theta } } T ( X ) = \mu \right \}.$$

We have

Proposition B.2. (Wainwright and Jordan, 2008, Proposition 3.2) The gradient mapping ∇ A : Θ →M is one-to-one if and only if the exponential representation is minimal.

Theorem B.1. (Wainwright and Jordan, 2008, Theorem 3.3) In a minimal exponential family, the gradient map ∇ A is onto the interior of M , denoted by M o . Consequently, for each µ ∈ M o , there exists some θ = θ µ ( ) ∈ Θ such that E π θ T X ( ) = µ .

A result on conjugate duality is also available. Given a function A , the conjugate dual function to A , which we denote by A ∗ , is defined as

$$A ^ { * } ( \mu ) \coloneqq \sup _ { \theta \in \Omega } \left \{ \langle \mu, \theta \rangle - A ( \theta ) \right \}, \ \mu \in \mathbb { R } ^ { d }.$$

Proposition B.3. (Wainwright and Jordan, 2008, Proposition B.2) The dual function A ∗ of a log-partition function A of an exponential family is always convex and lower-semicontinuous. Moreover, in a minimal and regular exponential family:

$$1. \ A ^ { * } \ i s \ d i f f e r e n t i a b l e \ o n \ \mathcal { M } ^ { o }, \ a n d \ \nabla A ^ { * } ( \mu ) = ( \nabla A ) ^ { - 1 } ( \mu )$$

- 2. A ∗ is strictly convex and essentially smooth.

A convex function f is essentially smooth if it has a nonempty domain C = dom( f ) , it is dfferentiable throughout the interior C o , and lim k →∞ ∇ f ( x k ) = ∞ for any sequence { x , k k ∈ N } contained in C , and converging to a boundary point of C . Note that a convex function with domain R d is always essentially smooth, since its domain has no boundary.

As a consequence of the above results, one obtains the following relations for the KL and Bregman divergence in the case of exponential families.

Lemma B.1. (Nielsen and Nock, 2010, Section 4) Assume π θ 1 and π θ 2 belong the same minimal regular exponential family with log-partition function A and denote its dual function by A ∗ . Suppose θ 1 , θ 2 are their natural parameters, dually coupled with their mean parameters µ , µ 1 2 . We have

$$D _ { A } ( \theta _ { 2 }, \theta _ { 1 } ) = K L ( \pi _ { \theta _ { 1 } }, \pi _ { \theta _ { 2 } } ) = D _ { A ^ { * } } ( \mu _ { 2 }, \mu _ { 1 } ).$$

## B.2. Exponential dispersion models

Given a natural exponential family ( υ, T ) one can introduce an exponential dispersion model (EDM) as follows Jorgensen (1987). Consider values λ ∈ Λ ⊂ R + such that λ · A θ ( ) is the cumulant function of some probability distribution we denote υ λ . In this situation we define the EDM distribution generated by ( υ, T, λ ) as

$$\pi _ { \theta, \lambda } ^ { * } ( \mathrm d x ) = \exp \left ( \langle \theta, T ( x ) \rangle - \lambda A ( \theta ) \right ) \upsilon _ { \lambda } ( \mathrm d x ) \,.$$

When T x ( ) = x one can use the change of variable x ← x/λ , leading to the distribution

π

θ,λ

(d

x

) = exp

(

λ

[

⟨

θ, x

⟩ -

A θ

(

)]

)

υ

λ

(d x .

)

This family is of interest to us because for θ ∈ Θ all moments of this distribution exist and with λ = γ -1

$$\mu ( \theta ) = \mathbb { E } _ { \pi _ { \theta, \gamma } } ( X ) = \nabla _ { \theta } A ( \theta ) \\ v a r ( X ) = \gamma \nabla _ { \theta } ^ { 2 } A ( \theta )$$

̸

therefore implying concentration of π θ,γ on µ θ ( ) as γ ↓ 0 . When T = I d one can consider the distribution of T X /λ ( ) and go back to the scenario above i.e.

$$\tilde { \pi } _ { \theta, \lambda } ( A ; T ) = \int \mathbf 1 \{ T ( x ) / \lambda \in A \} \exp \left ( \langle \theta, T ( x ) \rangle - \lambda A ( \theta ) \right ) \upsilon _ { \lambda } ^ { * } ( \mathrm d x )$$

↦

Existence of all moments for any θ ∈ Θ the cumulant generating function t → κ γ ( ; t θ ) = log E ˇ π θ, γ ( exp( ⟨ t, T ( X ) ) ⟩ ) = ( A θ ( + γt ) -A θ ( ) ) /γ and one obtains all moments by differentiation

$$\mu ( \theta ) = \mathbb { E } _ { \pi _ { \theta, \gamma } } \left ( T ( X ) \right ) = \nabla _ { \theta } A ( \theta ) \\ \text{var} \left ( T ( X ) \right ) = \gamma \nabla _ { \theta } ^ { 2 } A ( \theta ) \,.$$

Example B.1. Here X = [0 1] , . For a Beta distribution the parameter is θ = ( α, β ) and T x ( ) = ( log( x , ) log(1 -x ) ) therefore the exponential distribution is such that the random variable T X ( ) concentrates on the point

$$\mu ( \theta ) = \left ( \mathbb { E } _ { \theta } \log ( X ), \mathbb { E } _ { \theta } \log ( 1 - X ) \right ).$$

Note that we have l ( x ) = l ◦ exp( T 1 ( x )) for this example.

## B.3. EDM example: Wishart distribution

We illustrate here the interest of our general framework, where standard kernel approximation of the identity can be replaced with elements of the EDM family. In this scenario the sufficient statistic is T Y ( ) = Y ∈ R p × p , the parameter θ is a p × p symmetric positive definite matrix Σ and R + ∋ ν &gt; p -1 is the number of degrees of freedom Bishop et al. (2018). The parameter ν can take a finite number of smaller values ν ≤ p -1 in the so-called Jorgensen set, but this is not required

here. The reference measure is the Lebesgue measure υ on R p p ( +1) 2 / which only takes into account the upper triangular part of Y , including its diagonal. The corresponding probability density is given by

↦

$$Y \mapsto \frac { \exp \left ( - \frac { 1 } { 2 } \text{Tr} \left ( \Sigma ^ { - 1 } Y \right ) \right ) | Y | ^ { \frac { \nu - p - 1 } { 2 } } } { 2 ^ { \frac { \nu p } { 2 } } | \Sigma | ^ { \nu / 2 } \Gamma _ { p } ( \nu / 2 ) } \,,$$

where | Y | and Σ are here the determinant and Γ p is the Gamma function. The cumulant function is here A θ ( ) = ν 2 log | Σ | . Performing a change of variable X = Y/ν then the probability density of X with respect to υ ν becomes

↦

$$X \mapsto \frac { \exp \left ( - \frac { 1 } { 2 } \nu \text{Tr} ( \Sigma ^ { - 1 } X ) \right ) \nu ^ { \frac { p ( \nu - p - 1 ) } { 2 } } | X | ^ { \frac { \nu - p - 1 } { 2 } } } { 2 ^ { \frac { \nu p } { 2 } } | \Sigma | ^ { \nu / 2 } \Gamma _ { p } ( \nu / 2 ) } = \frac { \exp \left ( - \frac { 1 } { 2 } \text{Tr} \left ( ( \nu ^ { - 1 } \Sigma ) ^ { - 1 } X \right ) \right ) | X | ^ { \frac { \nu - p - 1 } { 2 } } } { 2 ^ { \frac { \nu p } { 2 } } | \nu ^ { - 1 } \Sigma | ^ { \nu / 2 } \Gamma _ { p } ( \nu / 2 ) } \nu ^ { \frac { - p ( p + 1 ) } { 2 } }$$

After rescaling the Lebesgue measure on υ on R p p ( +1) 2 / gives rise to a Jacobian ν p p ( +1) 2 which cancels the last term. Finally since we have E ( Y ) = ν Σ and v ar Y ( i,j ) = ν (Σ 2 ij -Σ Σ ii jj ) we deduce E ( X ) = Σ and v ar X ( i,j ) = ν -1 (Σ 2 ij -Σ Σ ii jj ) and concentration on the mean occurs as ν →∞ .

## B.4. EDM example: Beta distribution

In our context the Beta distribution could be of interest in scenarios where l ( ) · is to be optimised on a finite interval, without any loss of generality on [0 , 1] . We first show why the Beta distribution requires particular treatment as it is not an EDM and convenient parametrisation leads to intractability. The Beta distribution belongs to the linear exponential family with θ = ( α, β ) ∈ R 2 + , T x ( ) = ( log( x , ) log(1 -x ) ) and µ θ ( ) = ( E θ log( X , ) E θ log(1 -X ) ) . The Beta distribution is not an EDM but one can write, with E ( X ) = µ and γ -1 = α + β &gt; 0

$$\ v a r ( X ) = \frac { \mu ( 1 - \mu ) } { 1 + \gamma ^ { - 1 } }$$

which for µ fixed vanishes as γ ↓ 0 , as desired. However the issue is that moment matching takes the form

$$\mathbb { E } [ \log X ] = \psi ( \alpha ) - \psi ( \alpha + \beta ),$$

$$\mathbb { E } [ \log ( 1 - X ) ] = \psi ( \beta ) - \psi ( \alpha + \beta ),$$

$$\beta &, \\ \beta &,$$

where ψ is the Digamma function. While the Digamma function is standard in software packages, inverting the equations above to recover θ would require an additional and specific numerical method.

One can circumvent this problem as follows. We know that if X 1 ∼ Gamma( α, 1) and X 2 ∼ Gamma( β, 1) are independent, then X / X 1 ( 1 + X 2 ) ∼ Beta( α, β ) . It is therefore natural to aim to minimise the instrumental function ˜ ( l x ) := l ( x / x 1 ( 1 + x 2 ) ) , noting however that to each element of argmin X l corresponds a line, which nevertheless does not invalidate our approach. The Gamma distributions belong to the natural exponential family with θ 1 = ( α, 1) , θ 2 = ( β, 1) and summary statistics T i ( x i ) = T i ( x ) = ( log( x i ) , x i ) . The probability density of X := ( X ,X 1 2 ) is therefore

$$\pi _ { \theta, \gamma } ( x ) = \eta ( x _ { 1 }, \gamma ) \exp \left ( \gamma ^ { - 1 } [ \langle \theta _ { 1 }, T _ { 1 } ( x _ { 1 } ) \rangle - A ( \theta _ { 1 } ) ] \right ) \eta ( x _ { 2 }, \gamma ) \exp \left ( \gamma ^ { - 1 } [ \langle \theta _ { 2 }, T _ { 2 } ( x _ { 2 } ) \rangle - A ( \theta _ { 2 } ) ] \right ),$$

with A θ ( 1 ) = log Γ( α ) an A θ ( 2 ) = log Γ( β ) . Moment matching here takes the form

$$\mathbb { E } ( \log X _ { 1 } ) = \partial \log \Gamma ( \alpha ) = \psi ( \alpha )$$

$$\mathbb { E } ( \log X _ { 2 } ) = \partial \log \Gamma ( \beta ) = \psi ( \beta )$$

as the second components of θ i and T i ( ) · do not play any role. Solving for ( α, β ) requires inverting the Digamma function ψ , which again is fairly standard in statistical packages e.g. R. For any fixed θ ∈ Θ the distribution X ∼ π θ,γ is therefore such that T X ( ) = ( T 1 ( X 1 ) , T 2 ( X 2 ) ) concentrates on its mean as γ ↓ 0 , which together with the fact that log( ) · is invertible means that x θ ( ) can be recovered. However ˜ ( l x ) = ˜ ( l λx ) for any λ &gt; 0 , implying that θ may not converge to a point, but to a set of points.

## C. More details on lower semi-continuity and epi-convergence

## C.1. Lower semi-continuity

The following sets are major ingredients for the formal treatment of lower-semicontinuity and epi-convergence.

Definition C.1. Let f : R d → R be a function. We denote

- 1. The epigraph set of f by

$$\text{epi} ( f ) \coloneqq \left \{ ( \theta, a ) \in \mathbb { R } ^ { d } \times \mathbb { R } ; \ f ( \theta ) \leq a \right \}.$$

- 2. The hypograph set of f by

$$\text{hypo} ( f ) \coloneqq \left \{ ( \theta, a ) \in \mathbb { R } ^ { d } \times \mathbb { R } ; \ f ( \theta ) \geq a \right \}.$$

- 3. The level sets of f by

$$\text{lev} _ { \leq \alpha } ( f ) \coloneqq \left \{ \theta \in \mathbb { R } ^ { d } ; \ f ( \theta ) \leq \alpha \right \}, \ \alpha \in \mathbb { R }.$$

The following theorem characterises lower-semicontinuity in terms of epigraphs and level-sets.

Theorem C.1. (Rockafellar and Wets, 1998, Theorem 1.6) For a function f : R d → R , the following statements are equivalent

- · f is lower-semicontinuous on R d
- · Its epigraph set epi( f ) is closed in R d × R
- · Level sets lev ≤ a are closed in R d , for each a ∈ R .

Example C.1. The step function f : R → R defined by

$$f ( \theta ) = \begin{cases} 1, \ \theta > 0 \\ 0, \ \theta \leq 0 \end{cases} \.$$

is strongly lower-semicontinuous. The following function is lower-semicontinuous everywhere but at θ = 0 ,

$$f ( \theta ) = \begin{cases} 1, \ \theta \geq 0 \\ 0, \ \theta < 0 \end{cases} \.$$

indeed, its epigraph does not contain all of its boundary points. See Figure 5 for a similar situation.

Example C.2. The epigraph of the function in Figure 5 does not contain all of its boundary points, and it is therefore not closed. It is clear that the issue is at θ = 0 : the part of the space { (0 , a ); 0 ≤ a ≤ } 1 is not included in the epigraph. In this case, in fact, the function is not lower-semicontinuous at θ 0 , and note that the set argmin f is not defined.

Figure 5: Example of a function that is not lower-semicontinuous at θ = 0 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-466a7b47-59cd-40ec-ac5c-4cb02259621d.jpg)

## C.2. Epi-graphical closure

The epi- (resp. hypo-) graphical closure defined below can be seen as the lower- (resp. upper-) semicontinuous regularisation of a lower-bounded function f . These quantities play a role in the proof of epi-convergence of Laplace functionals - see Theorem 4.1. The following can be found for instance in (Rockafellar and Wets, 1998, Chapter 1).

Definition C.2. Consider a function f : R d → R . We define the epigraphical closure of f as the function

↦

$$\theta \mapsto \text{cl} _ { \text{e} } \, f ( \theta ) \coloneqq \inf _ { \theta _ { k } \rightarrow \theta } \liminf _ { k } f ( \theta _ { k } )$$

and the hypographical closure f as

↦

$$\theta \mapsto \text{cl} _ { h } f ( \theta ) \coloneqq \sup _ { \theta _ { k } \to \theta } \lim \sup _ { k } f ( \theta _ { k } ).$$

Proposition C.1. Consider a function f : R d → R . Then,

- · cl e f is lower-semicontinuous with cl e f ( θ ) ≤ f ( θ )
- · cl h f is upper-semicontinuous and cl h f ( θ ) ≥ f ( θ ) .

## Moreover,

- · When f is lower-semicontinuous, f ( θ ) = cl e f ( θ )
- · When f is upper-semicontinuous, f ( θ ) = cl h f ( θ ) .

## Example C.3. Let

$$f ( \theta ) = \begin{cases} 1, & \theta \geq 0 \\ 0, & \theta < 0 \end{cases} \.$$

Note that the function f is not lower-semicontinuous. We have

$$\text{cl} _ { e } f ( \theta ) = \begin{cases} 1, & \theta > 0 \\ 0, & \theta \leq 0 \end{cases} \.$$

.

## C.3. Epi-convergence

We will need the notion of outer and inner limits of a sequence of sets, which should not be confused with the superior or inferior limits of a sequence of sets, as the latter do not assume a topological structure. We note the unfortunate traditional use of the same notation for both ideas in the literature, adopted here. This allows us to define (Painleveé-Kuratowski) convergence and hence epi-convergence and to formulate Theorem C.4, but also Propostion C.5 and Theorem C.3.

## Definition C.3. Let

$$\mathcal { N } _ { \infty } ^ { \ddagger } \coloneqq \{ N \subset \mathbb { N } ; \ N \ i n f i n i t e \}$$

be the set of all unbounded subsequences of N , and

$$\mathcal { N } _ { \infty } \coloneqq \{ N \subset \mathbb { N } ; \ \mathbb { N } \, \Sigma \, N \, \ f i n i t e \}$$

be the set of all subsequences of N containing all n beyond some ¯ n ∈ N .

Definition C.4 (Outer and Inner Limits) . Let { A n ⊂ R d , n ∈ N } be a sequence of sets. We define

1. its outer limit as

$$L i m s u p _ { n } A _ { n } \coloneqq \bigcap _ { N \in \mathcal { N } _ { \infty } } c l \bigcup _ { n \in N } A _ { n }$$

- 2. its inner limit as

$$\text{Liminf} _ { n } A _ { n } \coloneqq \bigcap _ { N \in \mathcal { N } _ { \infty } ^ { \delta } } \text{cl} \bigcup _ { n \in N } A _ { n },$$

3. when Limsup n A n = Liminf n A n =: A then { A ,n n ∈ N } is said to set-converge to A , denoted

$$\text{Lim} _ { n } A _ { n } = A, \ A _ { n } \rightarrow A.$$

Another definition is given by the following equivalent, more intuitive, representation of inner and outer limits.

Proposition C.2. (Rockafellar and Wets, 1998, Section 4.A). Let { A n ⊂ R d , n ∈ N } be a sequence of sets. We have

$$L i m s u p _ { n } A _ { n } = \left \{ z \in \mathbb { R } ^ { d } ; \ \forall \epsilon > 0 \ \exists N \in \mathcal { N } _ { \infty } ^ { \dagger }, \ \forall n \in N \colon z \in A _ { n } + \mathbb { B } ( \epsilon ) \right \}$$

$$\text{Liminf} _ { n } A _ { n } = \left \{ z \in \mathbb { R } ^ { d } ; \ \forall \epsilon > 0 \ \exists N \in \mathcal { N } _ { \infty }, \ \forall n \in N \colon z \in A _ { n } + \mathbb { B } ( \epsilon ) \right \}$$

where B ( ϵ ) denotes a closed metric ball of radius ϵ . Moreover, it also holds that

$$L \liminf _ { n } A _ { n } = \bigcap _ { \epsilon \geq 0 } \left \{ \bigcup _ { m \geq 1 } \bigcap _ { j \geq m } \left [ A _ { n } + \mathbb { B } ( \epsilon ) \right ] \right \}.$$

̸

In words, for a sequence of sets { A , n n ∈ N } with A n = ∅ , the set Liminf n A n is the set of all possible limit points of sequences { z n , n ∈ N } with z n ∈ A n for all n ∈ N ; the set Limsup n A n is the set of all possible cluster points of those sequences Rockafellar and Wets (1998). As N ∞ ⊂ N ♯ ∞ , it is clear that Liminf n A n ⊂ Limsup n A n . We note that the two sets are closed, and identified by the closures, in the following sense.

Proposition C.3. (Rockafellar and Wets, 1998, Prop. 4.4). For any sequence of sets { A , n n ∈ N } , both Limsup n A n and Liminf n A n are closed sets. Hence, whenever lim n A n exists, then it is closed. In fact, if for two sequences of sets { C , n n ∈ N } , { D , n n ∈ N } one has cl C n = cl D n , n ∈ N , then Liminf n C n = Liminf n D n and Limsup n C n = Limsup n D n .

Example C.4. (Rockafellar and Wets, 1998, Section 4.B)

- · Let C ⊂ R d with cl C = R d . Then, the constant sequence A n = C , n ∈ N set-converges to R d (and not to C ).
- · Let C 1 and C 2 be distinct closed sets, and define a sequence { A , n n ∈ N } such that A n = C 1 for n odd, and A n = C 2 for n even. This sequence does not converge in the sense of Def. 3.4: the inner limit equals C 1 ∩ C 2 , while the outer limit equals C 1 ∪ C 2 .

Epi-convergence is commonly defined in terms of convergence of epigraphs.

Definition C.5. Let { f n : R d → R , n ∈ N } . The lower epi-limit e -liminf n f n is the function having as its epigraph the Limsup of the sequence of epigraphs of { f n , n ∈ N }

$$\ e p i ( e - \liminf _ { n } f _ { n } ) = \text{Limsup} _ { n } \text{epi} ( f _ { n } )$$

The upper epi-limit e -limsup n f n of the sequence is defined as the function satisfying

$$\text{epi} ( e - \limsup _ { n } f _ { n } ) = \text{Liminf} _ { n } \text{epi} ( f _ { n } ).$$

When for any θ ∈ R d

$$( e - \liminf _ { n } f _ { n } ) ( \theta ) = ( e - \limsup _ { n } f _ { n } ) ( \theta ) \,,$$

this function is called the epi-limit of { f n , n ∈ N } . Thus,

$$f _ { n } \ e p i \text{-converse to } f \iff \ e p i ( f _ { n } ) \to \text{epi} ( f ).$$

The following provides an intuitive characterisation of epi-convergence.

Theorem C.2 (Characterisation of epi-limits) . (Rockafellar and Wets, 1998, Prop 7.2) Let { f n : R d → R , n ∈ N } be a sequence of functions and let θ ∈ R d . We have

- · (e -liminf n f n )( θ ) = min { a ∈ R ; ∃ θ n → θ with lim inf n f n ( θ n ) = a }
- · (e -limsup n f n )( θ ) = min { a ∈ R ; ∃ θ n → θ with lim sup n f n ( θ n ) = a }

Thus, { f n , n ∈ N } epi-converge to f if and only if for each θ ∈ R d

- · lim inf n f n ( θ n ) ≥ f ( θ ) for any θ n → θ
- · lim n f n ( θ n ) = f ( θ ) for some sequence θ n → θ .

We can similarly characterise hypo-convergence.

Proposition C.4. Let { f n : R d → R , n ∈ N } be a sequence of functions and let θ ∈ R d . We have

$$f _ { n } \ h y p o { - c o n v e r g e \ t o \ f } \iff \ h y p o { ( f _ { n } ) \to \ h y p o { ( f ) } }.$$

We can rephrase Example 3.5 in the main text in terms of convergence of epigraphs and hypographs.

Example C.5. We illustrate with three examples the definitions of inner and outer limit of a sequence of epigraphs and the fact that this type of convergence differs from traditional functional convergence e.g. pointwise. Consider the following examples of sequences { f n : R → R , n ∈ N } where

$$\cdot \ f _ { n } ( \theta ) = - e ^ { - n \theta ^ { 2 } } \ a n d \ c o n s i d e r \ t h e \ f u n c t i o n$$

$$f ( \theta ) \coloneqq \begin{cases} - 1, & \theta = 0 \\ 0, & o t h e r w i s e \end{cases} \.$$

.

of epigraph the closed set

$$\ e p i ( f ) = ( \mathbb { R } \times \mathbb { R } _ { + } ) \cup \{ ( 0, a ) ; \ a \geq - 1 \} \subset \ e p i ( f _ { n } ) \subset \mathbb { R } ^ { 2 }, \forall n \in \mathbb { N },$$

Noting that epi( f n +1 ) ⊂ epi( f n ) for any n ∈ N then for any N ∈ N ♯ ∞ we have

$$\bigcup _ { n \in N } \epsilon i ( f _ { n } ) = \epsilon i ( f _ { \min \{ N \} } ) = c l ( \epsilon i ( f _ { \min \{ N \} } ) ) \,.$$

Now N ♯ ∞ = ∪ n ∈ N { N ∈ N ♯ ∞ : min { N } = n } and similarly N ∞ = ∪ n ∈ N { N ∈ N ∞ : min { N } = n } . Therefore

$$\text{Liminf} _ { n } \text{epi} ( f _ { n } ) = \text{Limp} _ { n } \text{epi} ( f _ { n } ) = \bigcap _ { n \in \mathbb { N } } \text{epi} ( f _ { n } ) \,,$$

and, by contradiction,

$$( \theta, a ) \in \text{pi} ( f _ { n } ) \subset \mathbb { R } ^ { 2 }, \forall n \in \mathbb { N } \iff ( \theta, a ) \in \text{pi} ( f ) \,,$$

and we conclude

$$\bigcap _ { n \in \mathbb { N } } \text{epi} ( f _ { n } ) = \text{epi} ( f ) \,,$$

which is closed and independent of N ∈ N ♯ ∞ . Therefore, from Def. C.4 and noting that N ∞ ⊂ N ♯ ∞ , we have Liminf n epi( f n ) = Limsup n epi( f n ) = epi( f ) and { f n , n ∈ N } epi-converges to f .

- · Let f n ( θ ) = e -nθ 2 and consider the function g ≡ 0 , whose epigraph is given by the closed set epi( g ) = R × R + . It is clear that, for an arbitrary N ∈ N ♯ ∞ ,

$$\bigcup _ { n \in N } \ e p i ( f _ { n } ) = \left ( \mathbb { R } \times \mathbb { R } _ { + } \right ) \, \| \left ( \{ ( \theta, a ) ; \, a = 0 \} \cup \{ ( 0, a ) ; \, 0 \leq a < 1 \} \right ) \subset \text{epi} ( g )$$

and it should be clear that

$$\text{cl} \bigcup _ { n \in N } \text{epi} ( f _ { n } ) = \text{epi} ( g ) \,,$$

which is independent of N . There, as for the previous example, the intersections involved in Def. C.4 are trivial, establishing that Liminf n epi( f n ) = Limsup n epi( f n ) = epi( g ) ; hence, { f n , n ∈ N } epi-converges to g . The remarkable point here is that { f n , n ∈ N } does not converge pointwise to g , since f n (0) = 1 for all n ∈ N .

- · Let f n ( θ ) = ( -1) n e -nθ 2 . This sequence fails to epi-converge as the set-limit does not exist. Adapting the above the inner limit Liminf n epi( f n ) = epi( f ) does not coincide with the outer limit Limsup n epi( f n ) = epi( g ) .

We are now in a position to report set-limit results one may obtain under the assumption of epi-convergence.

Definition C.6 ( ϵ -optimality set) . The set of points that minimise a function f : R d → R within ϵ ≥ 0 is denoted by

$$\epsilon - \arg \min f \coloneqq \left \{ \theta \in \mathbb { R } ^ { d } ; \ f ( \theta ) \leq \inf _ { u \in \mathbb { R } ^ { d } } f ( u ) + \epsilon \right \}.$$

The following result is central in the theory of convergence for procedures involving sequential minimisation of functions.

Proposition C.5 (epigraphical nesting, Rockafellar and Wets (1998), Proposition 7.30) . Let { f n : R d → R , n ∈ N } be a sequence of functions and let f : R d → R .

$$1. \ I f e - \limsup _ { n } f _ { n } \leq f, \, t h e n$$

$$\lim _ { n } \sup _ { \theta } \inf _ { \theta } f _ { n } ( \theta ) \leq \inf f.$$

- 2. Let { ϵ n ∈ R + , n ∈ N } , ϵ n ↓ 0 , be such that for any { θ n ∈ ϵ n -argmin f n , n ∈ N } admitting a subsequence { θ n k ∈ R d , k ∈ N } convergent to θ ∈ R d , then it holds that f n k ( θ n k ) → k f ( θ ) and

$$L i m s u p _ { n } \left \{ \epsilon _ { n } - \arg \min f _ { n } \right \} \subset \arg \min f \,.$$

We can in fact obtain a stronger result when epi-convergence holds.

Theorem C.3 (Rockafellar and Wets (1998), Theorem 7.31) . Let { f n : R d → R } be a sequence of functions that epiconverge to f , with -∞ &lt; inf f ( u ) &lt; ∞ . Then

$$u \in \mathbb { R } ^ { d }$$

- 1. For any ϵ &gt; 0

$$L i m s u p _ { n } \left \{ \epsilon - \arg \min f _ { n } \right \} \subset \epsilon - \arg \min f \,,$$

- 2. For any sequence { ϵ n ∈ R + , n ∈ N } , ϵ n ↓ 0 , we have

$$L i m s u p _ { n } \left \{ \epsilon _ { n } - \arg \min f _ { n } \right \} \subset \arg \min f \,.$$

An even stronger result holds when the the functions are lower-semicontinuous. Below, we say that a function g : R d → R is eventually level-bounded if for each a ∈ R d the sequence of level-sets { lev ≤ a f n , n ∈ N } is eventually bounded. For instance, a sequence of eventually lower-bounded functions is eventually level-bounded. The following result is Theorem C.4 in the main text; we report it here for completeness.

Theorem C.4 (Rockafellar and Wets (1998), Theorem 7.33) . Let

- 1. f : R d → R be a lower-bounded, lower-semicontiuous function,
- 2. { f n : R d → R , n ∈ N } be a sequence of lower-semicontinuous functions such that
- a) { f n , n ∈ N } epi-converges to f ,
- b) { f n , n ∈ N } is eventually level-bounded.

Then,

- 1. inf θ ∈ R d f n ( θ ) → inf θ ∈ R d f ( θ ) ,
- 2. Limsup n argmin f n ⊂ argmin f .

## D. Laplace Principle

The Laplace Principle is a known result which provides a variational representation of integrals of the form -log ´ e -l ( x ) π x ( )d x , where π is a probability density and l is an integrable function.

Lemma D.1 (Laplace Principle) . Let ν, π be two probability measures with ν ≪ π . Let l : R d → R be a locally integrable function such that ´ e -l ( x ) π x ( )d x &lt; ∞ and set ˜ π ∝ e -l π to be a probability measure. It holds that

$$K L ( \nu, \tilde { \pi } ) = \int l ( x ) \nu ( x ) d x + K L ( \nu, \pi ) + \log \int e ^ { - l ( x ) } \pi ( x ) d x.$$

A well-known consequence is

$$\sim \mathfrak { w } \quad & \tilde { \pi } = \underset { \nu \in M _ { + } ^ { 1 } ( R ^ { d } ) } { \arg \min } \left \{ \int l ( x ) \nu ( x ) \mathrm d x + K L ( \nu, \pi ) \right \}.$$

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-06d9b673-e938-4712-943d-9947038b0645.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-45caeb92-ad46-4743-9878-d7f02cf3b357.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-ee472c40-f003-4ee8-bd41-3d7b3da1c3c4.jpg)

iteration

n

Figure 6: AUC scoring example, Pima Indians dataset, objective function l is rescaled only at the first iteration. Left: Estimates of ̂ x across iterations (blue: exact algorithm, red: minibatch algorithm). Center: boxplots (across independent runs) of final output for both algorithms, compared with Nelder-Mead with random initialisation. Right: min/max values of l ( X i n ) at each iteration n (the different lines correspond to the different runs.)

Proof. By direct calculations, we have

$$\text{rect calculations, we have} \\ K L ( \nu, \bar { \pi } ) & = \int \nu ( x ) \log \left ( \frac { \nu ( x ) \pi ( e ^ { - l } ) } { e ^ { - l ( x ) } \pi ( x ) } \right ) d x = \\ & = \int \nu ( x ) \log \left ( \frac { \nu ( x ) } { e ^ { - l ( x ) } \pi ( x ) } \right ) d x + \log \pi ( e ^ { - l } ) \\ & = \int \nu ( x ) \left \{ \log ( \nu ( x ) ) - \log ( e ^ { - l ( x ) } ) - \log ( \pi ( x ) ) \right \} d x + \log \pi ( e ^ { - l } ) \\ & = \int \nu ( x ) \log \left ( \frac { \nu ( x ) } { \pi ( x ) } \right ) d x + \int \nu ( x ) l ( x ) d x + \log \pi ( e ^ { - l } ) \\ \text{to equation (37). This implies}$$

which leads to equation (37). This implies

$$\underset { \nu \in M _ { + } ^ { 1 } ( \mathbb { R } ^ { d } ) } { \arg \min } \left \{ \int l ( x ) \nu ( x ) \mathrm d x + K L ( \nu, \pi ) \right \} = \underset { \nu \in M _ { + } ^ { 1 } ( \mathbb { R } ^ { d } ) } { \arg \min } K L \left ( \nu, \tilde { \pi } \right ) = \tilde { \pi }$$

as KL( ν, π ˜) = 0 if and only if ν = ˜ π . Hence relation (38) holds.

## E. Additional results from numerical experiments: impact of rescaling

In this section we provide additional simulations, supplementing those of Section 2. In Figure 6 we report results similar to those of Figure 2 for the Pima Indians dataset, except that, this time, the objective function l is rescaled at the first iteration only. One can see that the both the exact and stochastic algorithms converge in this scenario, albeit at a slower rate (see in particular the left panel and compare with the corresponding panel in Figure 2). On the other hand, the results for the noisy (mini-batch) version look more stable.

The same strategy of rescaling l at the first iteration only works poorly for the Sonar dataset (results not shown), as the estimate remains far off the solution after 4000 iterations. We managed to achieve reasonable performance by rescaling the objective function l in the first k = 400 iterations (10% of the total number of iterations), see Figure 7. Stopping adaptation at some point leads to an algorithm that corresponds more directly to our theoretical analysis, but in practice adapting at every iteration seems to always improve the results to a certain extent.

Figure 7: AUC scoring example, Sonar dataset, objective function is rescaled at each of the first k = 400 iterations. Same plots as in Figure 6.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-54a86892-cc63-4fe3-bbd6-72734aaafdeb.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-042faede-bac5-4721-9718-68d9baf53970.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00888v1-figure-7981da0c-135c-49ce-9d97-1b38a0fb06e7.jpg)

## References

Attouch, H. (1984). Variational Convergence for Functions and Operators . Applicable mathematics series. Pitman Advanced Pub. Program.

Bishop, A. N., Del Moral, P., Niclas, A., et al. (2018). An introduction to Wishart matrix moments. Foundations and Trends® in Machine Learning , 11(2):97-218.

Bolte, J., Sabach, S., Teboulle, M., and Vaisbourd, Y. (2018). First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization , 28(3):2131-2151.

Clémençon, S., Lugosi, G., and Vayatis, N. (2008). Ranking and Empirical Minimization of U-statistics. The Annals of Statistics , 36(2):844 - 874.

Del Moral, P., Doucet, A., and Jasra, A. (2006). Sequential Monte Carlo samplers. Journal of the Royal Statistical Society. Series B (Statistical Methodology) , 68(3):411-436.

Ermoliev, Y. M., Norkin, V. I., and Wets, R. J.-B. (1995). The minimization of semicontinuous functions: Mollifier subgradients. SIAM Journal on Control and Optimization , 33(1):149-167.

Gupal, A. and Norkin, V. (1977). Algorithm for the minimization of discontinuous functions. Cybernetics and Systems Analysis - CYBERN SYST ANAL-ENGL TR , 13:220-223.

Jorgensen, B. (1987). Exponential dispersion models. Journal of the Royal Statistical Society. Series B (Methodological) , 49(2):127-162.

Jorgensen, B. (1997). The Theory of Dispersion Models . Chapman &amp; Hall/CRC Monographs on Statistics &amp; Applied Probability. Taylor &amp; Francis.

Kleijn, B. and van der Vaart, A. (2012). The Bernstein-Von-Mises theorem under misspecification. Electronic Journal of Statistics , 6(none):354 - 381.

Lemieux, C. (2009). Monte Carlo and quasi-Monte Carlo sampling . Springer Series in Statistics. Springer, New York.

Nesterov, Y. and Spokoiny, V. (2017). Random gradient-free minimization of convex functions. Foundations of Computational Mathematics , 17(2):527-566.

Nielsen, F. and Nock, R. (2010). Entropies and cross-entropies of exponential families. pages 3621-3624.

Norkin, V. I. (1993). The analysis and optimization of probability functions. Iiasa working paper, IIASA, Laxenburg, Austria.

Osher, S., Heaton, H., and Fung, S. W. (2023). A Hamilton-Jacobi-based proximal operator.

Ridgway, J., Alquier, P., Chopin, N., and Liang, F. (2014). Pac-Bayesian AUC classification and scoring. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., and Weinberger, K., editors, Advances in Neural Information Processing Systems , volume 27. Curran Associates, Inc.

Rockafellar, R. and Wets, R. J.-B. (1998). Variational Analysis . Springer Verlag, Heidelberg, Berlin, New York.

Rubinstein, R. Y. and Kroese, D. P. (2004). The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation, and machine learning , volume 133. Springer.

Spokoiny, V. (2023). Dimension free nonasymptotic bounds on the accuracy of high-dimensional Laplace approximation. SIAM/ASA Journal on Uncertainty Quantification , 11(3):1044-1068.

Szita, I. and Lörincz, A. (2006). Learning Tetris using the noisy cross-entropy method. Neural computation , 18(12):29362941.

Tibshirani, R. J., Fung, S. W., Heaton, H., and Osher, S. (2024). Laplace meets Moreau: Smooth approximation to infimal convolutions using Laplace's method.

Wainwright, M. and Jordan, M. (2008). Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning , 1:1-305.
Christophe Andrieu Nicolas Chopin Ettore Fincato Mathieu Gerber
Gradient-free optimization via integration
In this paper we propose a novel, general purpose, algorithm to optimize
functions $l\colon \mathbb{R}^d \rightarrow \mathbb{R}$ not assumed to be
convex or differentiable or even continuous. The main idea is to sequentially
fit a sequence of parametric probability densities, possessing a concentration
property, to $l$ using a Bayesian update followed by a reprojection back onto
the chosen parametric sequence. Remarkably, with the sequence chosen to be from
the exponential family, reprojection essentially boils down to the computation
of expectations. Our algorithm therefore lends itself to Monte Carlo
approximation, ranging from plain to Sequential Monte Carlo (SMC) methods.
  The algorithm is therefore particularly simple to implement and we illustrate
performance on a challenging Machine Learning classification problem. Our
methodology naturally extends to the scenario where only noisy measurements of
$l$ are available and retains ease of implementation and performance. At a
theoretical level we establish, in a fairly general scenario, that our
framework can be viewed as implicitly implementing a time inhomogeneous
gradient descent algorithm on a sequence of smoothed approximations of $l$.
This opens the door to establishing convergence of the algorithm and provide
theoretical guarantees. Along the way, we establish new results for
inhomogeneous gradient descent algorithms of independent interest.