A Direction Adaptation Evolution Strategy for Noisy Derivative-Free Optimization

arXiv:2607.10416 · math.OC · Submitted 2026-07-11 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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.

The resulting complexity orders are consistent with those reported in related optimization frameworks

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

Where the paper says it

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.

Springer, Berlin, Heidelberg (2017) [2] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to derivative-free optimization. p. 1
Where the paper says it

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.

In: MPS-SIAM Series on Optimization (2009) [3] Larson, J. p. 0
Where the paper says it

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.

, Menickelly, M., Wild, S.M.: Derivative-free optimization methods. p. 0
Where the paper says it

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.

Acta Numerica 28, 287–404 (2019) [4] Berahas, A.S., Byrd, R.H., Nocedal, J.: Derivative-free optimization of noisy functions via quasi-newton methods. p. 0
Where the paper says it

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.

SIAM Journal on Optimization 29(2), 965–993 (2019) [5] Brilli, A. p. 0
Where the paper says it

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.

, Kimiaei, M. p. 0
Where the paper says it

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.

, Liuzzi, G., Lucidi, S.: Worst case complexity bounds for linesearch-type derivative-free algorithms. p. 3
Where the paper says it

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.

Journal of Optimization Theory and Applications 203(1), 419–454 (2024) [6] Giovannelli, T. p. 0
Where the paper says it

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.

, Liuzzi, G., Lucidi, S., Rinaldi, F.: Derivative-free methods for mixed-integer nonsmooth constrained optimization. p. 0
Where the paper says it

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.

Computational Optimization and Applications 82(2), 293–327 (2022) [7] Kimiaei, M. p. 0
Where the paper says it

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.

: An improved randomized algorithm with noise level tuning for largescale noisy unconstrained dfo problems. p. 1
Where the paper says it

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.

Numerical Algorithms (2025) [8] Kimiaei, M. p. 0
Where the paper says it

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.

, Neumaier, A.: Efficient unconstrained black box optimization. p. 1
Where the paper says it

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.

Mathematical Programming Computation 14(2), 365–414 (2024) [9] Kimiaei, M. p. 0
Where the paper says it

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.

, Neumaier, A., Faramarzi, P.: New subspace method for unconstrained derivative-free optimization. p. 0
Where the paper says it

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.

ACM Transactions on Mathematical Software 49(4), 1–28 (2023) [10] Lucidi, S., Sciandrone, M.: A derivative-free algorithm for bound constrained optimization. p. 0
Where the paper says it

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.

Computational Optimization and Applications 21(2), 119–142 (2002) [11] De Santis, A. p. 4
Where the paper says it

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.

, Liuzzi, G., Lucidi, S.: A linesearch-based derivative-free method for noisy black-box problems. p. 0
Where the paper says it

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.

preprint arXiv:2508. p. 0
Where the paper says it

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.

00495 (2025) [12] Bandeira, A.S., Scheinberg, K., Vicente, L.N.: Convergence of trust-region methods based on probabilistic models. p. 1
Where the paper says it

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].

SIAM Journal on Optimization 24(3), 1238–1264 (2014) [13] Gratton, S. p. 0
Where the paper says it

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.

, Toint, P.L., Tröltzsch, A.: An active-set trust-region method for derivative-free nonlinear bound-constrained optimization. p. 0
Where the paper says it

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.

Optimization Methods and Software 26(4–5), 873–894 (2011) [14] Powell, M. p. 0
Where the paper says it

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.

J.: UOBYQA: unconstrained optimization by quadratic approximation. p. 1
Where the paper says it

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.

Mathematical Programming 92(3), 555–582 (2002) [15] Liuzzi, G., Lucidi, S., Rinaldi, F., Vicente, L.N.: Trust-region methods for the derivative-free optimization of nonsmooth black-box functions. p. 1
Where the paper says it

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].

SIAM Journal on Optimization 29(4), 3012–3035 (2019) [16] Dzahini, K. p. 0
Where the paper says it

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.

J., Rinaldi, F., Royer, C.W., Zeffiro, D.: Direct-search methods in the year 2025: Theoretical guarantees and algorithmic paradigms. p. 1
Where the paper says it

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].

EURO Journal on Computational Optimization 13, 100110 (2025) [17] Gratton, S. p. 4
Where the paper says it

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.

, Royer, C.W., Vicente, L.N., Zhang, Z.: Direct search based on probabilistic descent. p. 1
Where the paper says it

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].

p. 1
Where the paper says it

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].

SIAM Journal on Optimization 25(3), 1515–1541 (2015) [18] Higham, N. p. 0
Where the paper says it

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.

J.: Optimization by direct search in matrix computations. p. 1
Where the paper says it

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].

SIAM Journal on Matrix Analysis and Applications 14(2), 317–333 (1993) [19] Porcelli, M. p. 0
Where the paper says it

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.

, Toint, P.L.: Exploiting problem structure in derivative free optimization. p. 1
Where the paper says it

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.

ACM Transactions on Mathematical Software 48(1), 1–25 (2022) [20] Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. p. 0
Where the paper says it

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.

Journal of Global Optimization 14(4), 331–355 (1999) [21] Custódio, A. p. 0
Where the paper says it

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.

L., Madeira, J.F.A.: Glods: Global and local optimization using direct search. p. 1
Where the paper says it

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].

Journal of Global Optimization 62(1), 1–28 (2014) [22] Custódio, A. p. 0
Where the paper says it

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.

L., Madeira, J.F.A.: Multiglods: global and local multiobjective optimization using direct search. p. 1
Where the paper says it

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].

Journal of Global Optimization 72(2), 323–345 (2018) [23] Auger, A. p. 0
Where the paper says it

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.

, Hansen, N.: A restart CMA evolution strategy with increasing population size. p. 0
Where the paper says it

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.

In: Congress on Evolutionary Computation, vol. 2, pp. 1769–1776. IEEE, Edinburgh, UK (2005) [24] Beyer, H.-G.: Design principles for matrix adaptation evolution strategies. p. 0
Where the paper says it

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.

In: Genetic and Evolutionary Computation Conference Companion, vol. 2, pp. 682–700. ACM, Cancún Mexico (2020) [25] Beyer, H.-G., Sendhoff, B.: Simplify your covariance matrix adaptation evolution strategy. p. 0
Where the paper says it

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.

IEEE Transactions on Evolutionary Computation 21(5), 746–759 (2017) [26] Kimiaei, M. p. 0
Where the paper says it

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.

: GS1400/MATRS: MATRSv3.0. Zenodo (2024) [27] Kimiaei, M. p. 0
Where the paper says it

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.

, Neumaier, A.: Effective matrix adaptation strategy for noisy derivative-free optimization. p. 0
Where the paper says it

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.

Mathematical Programming Computation 16(3), 459–501 (2024) [28] Audet, C., Le Digabel, S., Montplaisir, V.R., Tribes, C.: Algorithm 1027: Nomad version 4: Nonlinear optimization with the mads algorithm. p. 3
Where the paper says it

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.

ACM Transactions on Mathematical Software 48(3), 1–22 (2022) [29] Ma, K., Rios, L.M., Zheng, H., Sahinidis, N.V., Rajagopalan, S.: Model-andsearch: a derivative-free local optimization algorithm. p. 0
Where the paper says it

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.

Computational Optimization and Applications 92(3), 889–921 (2025) [30] Bergou, E. p. 4
Where the paper says it

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.

H., Gorbunov, E., Richtárik, P.: Stochastic three points method for unconstrained smooth minimization. p. 1
Where the paper says it

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.

SIAM Journal on Optimization 30(4), 2726–2749 (2020) [31] Zhang, Y. p. 0
Where the paper says it

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.

, Sahinidis, N.V.: Solving continuous and discrete nonlinear programs with BARON. p. 1
Where the paper says it

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.

Computational Optimization and Applications 92(3), 1123–1161 (2024) [32] Hansen, N. p. 4
Where the paper says it

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.

: The CMA evolution strategy: A tutorial. p. 0
Where the paper says it

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.

preprint arXiv:1604. p. 0
Where the paper says it

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.

00772 (preprint) [33] C. Elster, A.N.: A grid algorithm for bound constrained optimization of noisy functions. p. 0
Where the paper says it

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.

IMA Journal of Numerical Analysis 15(4), 585–608 (1995) [34] Gratton, S. p. 1
Where the paper says it

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.

, Royer, C.W., Vicente, L.N., Zhang, Z.: Direct search based on probabilistic descent. SIAM Journal on Optimization 25(3), 1515–1541 (2015) [35] Nesterov, Y. p. 0
Where the paper says it

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.

: Introductory Lectures on Convex Optimization: A Basic Course. p. 2
Where the paper says it

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].

Applied Optimization, vol. p. 0
Where the paper says it

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.

87. Springer, Berlin, Heidelberg (2004) [36] Cartis, C., Gould, N.I.M., Toint, P.L.: Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. p. 3
Where the paper says it

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 λ.

Society for Industrial and Applied Mathematics, Philadelphia (2022) [37] Moré, J. p. 0
Where the paper says it

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.

J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. p. 0
Where the paper says it

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.

SIAM Journal on Optimization 20(1), 172–191 (2009) [38] Dolan, E. p. 0
Where the paper says it

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.

D., Moré, J.J.: Benchmarking optimization software with performance profiles. p. 5
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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

Related papers