English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the context of unconstraint numerical optimization, this paperinvestigates the global linear convergence of a simple probabilisticderivative-free optimization algorithm (DFO). The algorithm samples a candidatesolution from a standard multivariate normal distribution scaled by a step-sizeand centered in the current solution. This solution is accepted if it has abetter objective function value than the current one. Crucial to the algorithmis the adaptation of the step-size that is done in order to maintain a certainprobability of success. The algorithm, already proposed in the 60's, is ageneralization of the well-known Rechenberg's $(1+1)$ Evolution Strategy (ES)with one-fifth success rule which was also proposed by Devroye under the namecompound random search or by Schumer and Steiglitz under the name step-sizeadaptive random search. In addition to be derivative-free, the algorithm isfunction-value-free: it exploits the objective function only throughcomparisons. It belongs to the class of comparison-based step-size adaptiverandomized search (CB-SARS). For the convergence analysis, we follow themethodology developed in a companion paper for investigating linear convergenceof CB-SARS: by exploiting invariance properties of the algorithm, we turn thestudy of global linear convergence on scaling-invariant functions into thestudy of the stability of an underlying normalized Markov chain (MC). We henceprove global linear convergence by studying the stability (irreducibility,recurrence, positivity, geometric ergodicity) of the normalized MC associatedto the $(1+1)$-ES. More precisely, we prove that starting from any initialsolution and any step-size, linear convergence with probability one and inexpectation occurs. Our proof holds on unimodal functions that are thecomposite of strictly increasing functions by positively homogeneous functionswith degree $\alpha$ (assumed also to be continuously differentiable). Thisfunction class includes composite of norm functions but also non-quasi convexfunctions. Because of the composition by a strictly increasing function, itincludes non continuous functions. We find that a sufficient condition forglobal linear convergence is the step-size increase on linear functions, acondition typically satisfied for standard parameter choices. While introducedmore than 40 years ago, we provide here the first proof of global linearconvergence for the $(1+1)$-ES with generalized one-fifth success rule and thefirst proof of linear convergence for a CB-SARS on such a class of functionsthat includes non-quasi convex and non-continuous functions. Our proof alsoholds on functions where linear convergence of some CB-SARS was previouslyproven, namely convex-quadratic functions (including the well-know spherefunction).

Linear Convergence on Positively Homogeneous Functions of a Comparison  Based Step-Size Adaptive Randomized Search: the (1+1) ES with Generalized  One-fifth Success Rule