A Direction Adaptation Evolution Strategy for Noisy Derivative-Free Optimization
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "A Direction Adaptation Evolution Strategy for Noisy Derivative-Free Optimization".
Title and authors: Ada: Morteza Kimiaei and Mahsa Yousefi introduce this "Direction Adaptation Evolution Strategy for Noisy Derivative-Free Optimization," which is designed specifically to bridge the gap between population-based search methods and having solid complexity analysis.
Emmy: They are proposing a fix to the standard MAES structure, essentially saying we can keep the overall population idea but we don't need that complicated adaptive matrix stuff anymore.
The paper's summary: Ada: The core mechanism they detail is replacing that adaptive matrix adaptation with a structured direction generation process that relies on symmetric sampling of directions and sorting noisy function values.
Emmy: That’s key because it gets rid of all the computational overhead from building and multiplying matrices at every step, which is what makes standard MAES methods so slow in practice.
The paper's improvements: Ada: They focus on several specific enhancements, starting with the mutation phase where they use symmetric sampling of both positive and negative directions to make sure the exploration isn't just biased toward one direction.
Emmy: And then in the recombination phase, they take those reordered directions and partition them into three groups based on how noisy their function values are, which lets them construct a new triangular search direction.
Conclusion: Ada: So to wrap up, the main point of "A Direction Adaptation Evolution Strategy for Noisy Derivative-Free Optimization" is that by using symmetric sampling for mutation and that specific three-group recombination for direction generation, they manage to get a high probability angle condition with the true gradient.
Emmy: Kolya, what does that probabilistic angle condition actually guarantee us about how well this method finds the minimum?
Kolya: Well, it means that on a high probability event, the geometric factor related to that triangular recombination direction stays uniformly bounded over all iterations. This gives us convergence guarantees for both convex and strongly convex objective functions under bounded noise.
Ada: That’s important because it provides explicit complexity orders for nonconvex and strongly convex settings derived at the noise-limited accuracy level.
Emmy: And numerically, they compared this DAES method against something called MADFO, and they found that DAES is more efficient when you have a small budget of evaluations.
Kolya: That makes sense; MADFO seems to be more robust when you have substantially larger budgets. The paper shows a favorable trade-off between evaluation efficiency and ultimate robustness for DAES on the six hundred fifty-five prince test problems from the BARON collection <ref:2607.10416#pg2>.
Ada: So, while it’s simpler to implement than some other methods, it still maintains strong performance benefits compared to MADFO on those test cases.
Emmy: It sounds like they managed to simplify the adaptation part while still keeping the necessary structure for theoretical tractability under noise.
Morteza Kimiaei, Mahsa Yousefi
Faculty of Mathematics, University of Vienna · Department of Industrial Engineering, University of Florence
math.OC
Submitted: 2026-07-11
Updated: 2026-11-15
Comments: 40 pages; 5 figures
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 77/100
The gist: In this paper, we develop a direction adaptation evolution strategy (DAES)—a new MAES-type method—for noisy derivative-free optimization…
Key concepts
- DAES
- A new MAES-type method for noisy derivative-free optimization. It fixes the adaptation matrix to the identity and uses a structured mechanism—symmetric sampling, sorting–selection, and three-group recombination—to generate search directions. This allows for practical performance while enabling complexity analysis under noise.
- Symmetric Sampling
- During the mutation phase, candidate solutions are generated by sampling pairs of random directions (a direction and its negative). This technique promotes balanced exploration across all possible search directions, helping to mitigate directional bias that can occur when only one-sided sampling is used in standard methods.
- Triangular Search Direction
- The recombination phase partitions reordered directions into three groups based on noisy function values. These groups define three recombination points whose geometry constructs a new triangular direction. This geometric construction guides the search toward promising regions by leveraging the ranked information from the noisy evaluations.
Terminology
Summary
In this paper, we develop a direction adaptation evolution strategy (DAES)—a new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous complexity analysis The structure yields a population-based MAES-type algorithm that retains competitive practical behavior while being amenable to nonasymptotic analysis under noisy evaluations
Pruning redundant reasoning tokens
The paper introduces DAES, a new MAES-type method for noisy derivative-free optimization by fixing the adaptation matrix to the identity and replacing matrix adaptation with a structured direction generation mechanism based on symmetric sampling, joint sorting–selection of noisy function values, three-group recombination, and a new triangular search direction Unlike standard MAES, DAES fixes the matrix to the identity and enables exploration over all mutation directions This redesign replaces adaptive matrix updates with a structured population-based direction mechanism that retains practical effectiveness while being amenable to rigorous complexity analysis under noisy evaluations The authors establish high-probability complexity bounds for nonconvex, convex, and strongly convex objective functions and derive corresponding guarantees at the noise-limited accuracy level.
How the training signal is built
The DAES algorithm proceeds iteratively through three distinct enhanced phases: mutation, sorting–selection, and recombination In the mutation phase, candidate solutions are generated by sampling symmetric pairs of random directions (a direction and its negative), thereby promoting balanced exploration and mitigating the directional bias associated with one-sided sampling The mutation directions are obtained directly from these sampled vectors without any covariance shaping, avoiding the computational overhead associated with matrix-based adaptations in DAES.
Where the gains come from
The recombination phase constructs a robust direction by partitioning the reordered directions into three groups based on noisy function values and constructing three recombination points whose geometry defines a new triangular direction The final search direction is obtained by applying a fixed-norm scaling to the unscaled triangular vector, ensuring that the geometric construction in (18) and magnitude control in (21) are separated.
Complexity analysis and comparison
The paper establishes high-probability complexity bounds for noisy DFO, providing the first such results for a noisy MAES-type method with this direction-adaptation structure The complexity bounds are derived under assumptions including bounded evaluation noise (AN) and a noise-calibrated range for step-sizes (AB). Numerical experiments compare DAES with MADFO, showing that DAES achieves the strongest overall behavior among its variants, while MADFO is more robust for substantially larger budgets. p. 3 We compare the full version of DAES, incorporating symmetric sampling, grouped
sorting–selection, triangular recombination, and extrapolation, with MADFO [27], an
advanced MAES-type derivative-free solver, on 655 prince test problems from the
BARON collection [31] with dimensions ranging from 2 to 100. The results show that
DAES achieves the strongest overall behavior among its variants, with triangular recombination and extrapolation contributing most to efficiency and robustness, and is more
efficient than MADFO over small and moderate budgets, whereas MADFO is ultimately
more robust for substantially larger budgets.Where the paper says it
Probabilistic guarantees and bounds
The randomized analysis introduces two failure mechanisms: sampling failure and sorting–selection failure The global good event GT, which combines both successes, has a probability of at least 1 − (γ0 + γsel) On this event, the geometric factor associated with the triangular recombination direction is uniformly bounded over the relevant iterations. This leads to high-probability convergence guarantees for objective accuracy and gradient norm bounds under both convex and strongly convex settings. p. 0 This structure yields a population-based MAES-type algorithm that retains competitive practical behavior while being amenable to nonasymptotic analysis under
noisy evaluations. We establish high-probability complexity bounds for nonconvex, convex, and strongly convex objective functions and derive corresponding
guarantees at the noise-limited accuracy level.Where the paper says it
Numerical results
The numerical experiments on the 655 prince test problems from the BARON collection compare DAES with the advanced MAES-type solver MADFO and show a favorable trade-off between evaluation efficiency and ultimate robustness The performance profile shows that the full DAES consistently outperforms both ablation variants, indicating improved efficiency when triangular recombination and extrapolation are used together Compared with MADFO, DAES is more efficient on problems solved with small budgets, whereas MADFO is more robust under larger budgets. The comparison suggests that DAES achieves the intended trade-off between simplicity and theoretical tractability
Conclusion
DAES proposes a simplified MAES for noisy derivative-free optimization that fixes the adaptation matrix to the identity and uses all sampled mutation directions The main algorithmic contribution of DAES lies in its mutation, sorting–selection, and recombination mechanisms The authors develop a high-probability complexity analysis under bounded noise, showing that the triangular recombination direction satisfies a probabilistic angle condition with the true gradient The numerical experiments on prince problems from the BARON collection support the proposed design. The ablation study shows that the best performance is obtained when triangular recombination and extrapolation are used together, while removing either component degrades performance Compared with MADFO, DAES is more efficient on problems solved with small budgets, whereas MADFO is more robust under larger budgets The comparison suggests that DAES achieves the intended trade-off between simplicity and theoretical tractability
References
[1] Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. p. 0 A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. We establish high-probability complexity bounds for nonconvex, convex, and strongly convex objective functions and derive corresponding
guarantees at the noise-limited accuracy level. To the best of our knowledge, these
results provide the first high-probability complexity guarantees for a noisy MAEStype derivative-free method with this direction-adaptation structure. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. Building on these results and standard tools from nonconvex, convex, and
strongly convex optimization, we derive total-iteration and function-evaluation complexity bounds at the noise-limited accuracy level, with explicit dependence on the
noise level ω and the sampling budget λ. We compare the full version of DAES, incorporating symmetric sampling, grouped
sorting–selection, triangular recombination, and extrapolation, with MADFO [27], an
advanced MAES-type derivative-free solver, on 655 prince test problems from the
BARON collection [31] with dimensions ranging from 2 to 100. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This means
that the mutation directions are directly derived from the sampled (distribution)
directions without any covariance shaping. Obviously, this avoids the computational
overhead associated with matrix-based adaptations in DAES. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. To the best of our knowledge, these
results provide the first high-probability complexity guarantees for a noisy MAEStype derivative-free method with this direction-adaptation structure. Finally,
1
arXiv:2607. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. For advanced DFO methods that combine DS or LS
with model-based techniques or with MAES, we refer the reader to [26–29]. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. This
setting is commonly referred to as the noisy DFO problem; see, e. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This
setting is commonly referred to as the noisy DFO problem; see, e. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. This means
that the mutation directions are directly derived from the sampled (distribution)
directions without any covariance shaping. Obviously, this avoids the computational
overhead associated with matrix-based adaptations in DAES. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. For advanced DFO methods that combine DS or LS
with model-based techniques or with MAES, we refer the reader to [26–29]. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. For advanced DFO methods that combine DS or LS
with model-based techniques or with MAES, we refer the reader to [26–29]. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This
setting is commonly referred to as the noisy DFO problem; see, e. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation
matrix to the identity and replaces matrix adaptation with a structured directiongeneration mechanism based on symmetric sampling, joint sorting–selection of
noisy function values, three-group recombination, and a new triangular search
direction. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This
setting is commonly referred to as the noisy DFO problem; see, e. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This
setting is commonly referred to as the noisy DFO problem; see, e. 1 Related work
To solve the noisy DFO problem (1), numerous deterministic and randomized methods have been proposed, including line search (LS) solvers [3–11], trust-region (TR)
methods [3, 12–15], direct search (DS) methods [3, 16–22], and matrix adaptation evolution strategies (MAES) [23–27]. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation
matrix to the identity and replaces matrix adaptation with a structured directiongeneration mechanism based on symmetric sampling, joint sorting–selection of
noisy function values, three-group recombination, and a new triangular search
direction. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation
matrix to the identity and replaces matrix adaptation with a structured directiongeneration mechanism based on symmetric sampling, joint sorting–selection of
noisy function values, three-group recombination, and a new triangular search
direction. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation
matrix to the identity and replaces matrix adaptation with a structured directiongeneration mechanism based on symmetric sampling, joint sorting–selection of
noisy function values, three-group recombination, and a new triangular search
direction. Building on these results and standard tools from nonconvex, convex, and
strongly convex optimization, we derive total-iteration and function-evaluation complexity bounds at the noise-limited accuracy level, with explicit dependence on the
noise level ω and the sampling budget λ. We compare the full version of DAES, incorporating symmetric sampling, grouped
sorting–selection, triangular recombination, and extrapolation, with MADFO [27], an
advanced MAES-type derivative-free solver, on 655 prince test problems from the
BARON collection [31] with dimensions ranging from 2 to 100. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. This means
that the mutation directions are directly derived from the sampled (distribution)
directions without any covariance shaping. Obviously, this avoids the computational
overhead associated with matrix-based adaptations in DAES. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. This means
that the mutation directions are directly derived from the sampled (distribution)
directions without any covariance shaping. Obviously, this avoids the computational
overhead associated with matrix-based adaptations in DAES. yousefi@unifi. it;
Abstract
In this paper, we develop a direction adaptation evolution strategy (DAES)—a
new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous
complexity analysis. To the best of our knowledge, these
results provide the first high-probability complexity guarantees for a noisy MAEStype derivative-free method with this direction-adaptation structure. Finally,
1
arXiv:2607. This structure yields a population-based MAES-type algorithm that retains competitive practical behavior while being amenable to nonasymptotic analysis under
noisy evaluations. We establish high-probability complexity bounds for nonconvex, convex, and strongly convex objective functions and derive corresponding
guarantees at the noise-limited accuracy level. numerical experiments on the 655 prince test problems from the BARON collection
compare DAES with the advanced MAES-type solver MADFO and show a favorable
trade-off between evaluation efficiency and ultimate robustness. Keywords: Noisy Derivative-Free Optimization, Evolution Strategy, Randomized
Optimization, Direction Adaptation, Complexity Results, Heuristic Optimization
1 Introduction
We consider the unconstrained derivative-free optimization (DFO) problem
min
x∈Rn
f(x), (1)
where the objective function f : R
n → R is smooth but not directly accessible. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. In addition to the enhancements introduced in DAES, we provide a complexity analysis. To the best of our knowledge, these are the first high-probability complexity results for
a noisy MAES-type method covering nonconvex, convex, and strongly convex objectives
and attaining the corresponding complexity orders reported for related optimization
frameworks in [7, 8, 17, 30]. Specifically, candidates are sampled along paired positive and negative directions, their inexact function values are jointly ranked, and the reordered
directions are partitioned into three groups to construct three recombination
points whose geometry defines the triangular direction. A signed sufficientdecrease search and extrapolation mechanism is then applied along this direction. By controlling the associated per-iteration failure probabilities, we establish
that the required directional and descent properties hold uniformly with high probability. Building on these results and standard tools from nonconvex, convex, and
strongly convex optimization, we derive total-iteration and function-evaluation complexity bounds at the noise-limited accuracy level, with explicit dependence on the
noise level ω and the sampling budget λ. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. A Direction Adaptation Evaluation Strategy for
Noisy Derivative-Free Optimization
Morteza Kimiaei 1 and Mahsa Yousefi 2
1Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz
1, Vienna, A-1090, Austria. 2Department of Industrial Engineering, University of Florence, Viale
G. Thus, Z
ℓ
± contains the raw symmetric Gaussian samples used in the scaling stepsize adaptation, whereas Dℓ
contains the normalized symmetric mutation directions
used to generate mutation points and in the subsequent sorting–selection and
recombination phases. Empirical results also confirm that symmetric sampling improves stability and search
performance compared to asymmetric directions.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve search direction generation by fixing it to a structured mechanism based on symmetric sampling, joint sorting-selection of noisy function values, three-group recombination, and a new triangular search direction to reconcile population-based search with rigorous complexity analysis.
-
Enhance the system's robustness in noisy regimes by employing symmetric sampling of paired positive and negative directions during mutation, which is shown to promote balanced exploration and mitigate directional bias compared to standard asymmetric sampling.
-
Implement a structured recombination phase that constructs three recombination points whose geometry defines a triangular direction, which is designed to guide the search toward promising regions based on the ranked groups of noisy function values.
-
Integrate an extrapolation step inspired by derivative-free line search methods along the generated triangular direction to achieve sufficient decrease, allowing for high-probability convergence guarantees under bounded evaluation noise.
-
Achieve high-probability complexity bounds for nonconvex, convex, and strongly convex objective functions by deriving bounds at the noise-limited accuracy level based on the probabilistic angle condition satisfied by the triangular recombination directions.
-
Enable more efficient practical performance by using a fixed population size of lambda = max(6, 4 + floor(3 log(n))), which is calibrated to be close to that used by MADFO for most tested dimensions, while introducing no additional explicit dependence on dimension n in the population calibration.
-
Increase computational efficiency by fixing the adaptation matrix to the identity and removing adaptive matrix updates, avoiding the computational overhead associated with matrix-based adaptations in standard MAES.
-
Develop a high-probability gradient norm bound of O(sqrt(L omega) c bar), where c bar is derived from the probabilistic angle condition, providing explicit guarantees for nonconvex and strongly convex problems under bounded noise.
-
Establish convergence accuracy bounds, such as f(x l star) - f = O(sqrt(L omega) c bar), for both convex and strong convexity cases with high probability by utilizing the properties of the noise-limited stationarity guarantee.
Abstract
In noisy derivative-free optimization (DFO), methods based on the matrix adaptation evolution strategy (MAES) often mistakenly identify points with spuriously good function values, undermining selection and leading to unreliable search directions. To address this, we develop a novel direction adaptation evolution strategy (DAES) that targets the algorithmic phases prone to noise propagation, combining selected-population search with complexity analysis. Fixing the transformation matrix to the identity, DAES employs a structured direction-generation mechanism consisting of symmetric sampling, joint sorting--selection of noisy values, partitioning of all sampled directions into three ranked groups, and construction of a heuristic search direction. Along this direction, a noisy derivative-free sufficient descent condition with extrapolation is applied. Using a probabilistic angle condition preserved through our proposed framework, we obtain, to the best of our knowledge, the first high-probability evaluation-complexity bounds for a noisy MAES-type method across nonconvex, convex, and strongly convex objectives, under bounded noise. Finally, experiments on 230 BARON BCP problems across eight noise levels compare DAES with five DFO solvers, notably MADFO, showing greater robustness at intermediate-to-small budgets.
Sources
- A linesearch-based derivative-free method for noisy black-box problems
- The CMA Evolution Strategy: A Tutorial
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise