Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization

Abstract

In derivative-free optimization (DFO), one minimizes functions for which the gradient is unavailable or expensive to compute. In many applications, objective function values and gradients are noisy due to simulations or system randomness. A class of standard direct-search methods for DFO accept a trial point when it decreases the objective function by an amount proportional to the squared stepsize. However, when applied to complex landscapes, such a requirement may trap the algorithm in a neighborhood of sub-optimal solutions. We study a non-monotone direct-search alternative where the trial function value is compared with the largest objective function obtained through the M most recent distinct iterates. This max-M non-monotone condition permits temporary increases in the objective function and can help navigate narrow curved valleys; however, its theoretical analysis is significantly more challenging due to the lack of monotonic decrease. In this paper, we develop a comprehensive complexity theory for the max-M non-monotone direct-search in both deterministic and stochastic DFO problems. For deterministic objectives, we establish a worst-case iteration bound for a complete poll based on a positive spanning set and an expected iteration bound for a probabilistic-descent poll. We then analyze a stochastic variant using independent function estimates and show the expected iteration complexity under tail-bound assumptions of the stochastic errors. All three results have the standard complexity of 𝒪(ε⁻²), which matches the iteration complexity of monotone direct-search methods. Our theory is enabled by a new family of merit functions that correct the stored objective values by ordered multiples of the squared stepsize, together with a renewal-reward stopping-time argument for the probabilistic methods.

Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants
Zhuoyu Xiao, Uday V. Shanbhag, Yue Xie
arXiv29 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Deterministic and stochastic particle methods for the Fokker-Planck equation in S--formulation with application to point set registration
Klaas Willems, Angelo Iollo, Giovanni Russo +1
arXiv1 Oct 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
Tianzhu Liu, Michael J. O'Neill
arXiv27 Aug 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
Tao Hu, Rohan Ghuge
arXiv12 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
A note on the complexity of random subspace model-based methods for derivative-free optimization
Coralia Cartis, Lindon Roberts
arXiv18 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{ding2026nonmonotone,
  title = {{Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization}},
  author = {Anjie Ding and Trang H. Tran and Luis Nunes Vicente},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.11567},
  eprint = {2609.11567},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.11567},
}

RIS

TY  - UNPB
TI  - Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization
AU  - Anjie Ding
AU  - Trang H. Tran
AU  - Luis Nunes Vicente
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.11567
UR  - https://arxiv.org/abs/2609.11567
AB  - In derivative-free optimization (DFO), one minimizes functions for which the gradient is unavailable or expensive to compute. In many applications, objective function values and gradients are noisy due to simulations or system randomness. A class of standard direct-search methods for DFO accept a trial point when it decreases the objective function by an amount proportional to the squared stepsize. However, when applied to complex landscapes, such a requirement may trap the algorithm in a neighborhood of sub-optimal solutions. We study a non-monotone direct-search alternative where the trial function value is compared with the largest objective function obtained through the M most recent distinct iterates. This max-M non-monotone condition permits temporary increases in the objective function and can help navigate narrow curved valleys; however, its theoretical analysis is significantly more challenging due to the lack of monotonic decrease. In this paper, we develop a comprehensive complexity theory for the max-M non-monotone direct-search in both deterministic and stochastic DFO problems. For deterministic objectives, we establish a worst-case iteration bound for a complete poll based on a positive spanning set and an expected iteration bound for a probabilistic-descent poll. We then analyze a stochastic variant using independent function estimates and show the expected iteration complexity under tail-bound assumptions of the stochastic errors. All three results have the standard complexity of 𝒪(ε^−2), which matches the iteration complexity of monotone direct-search methods. Our theory is enabled by a new family of merit functions that correct the stored objective values by ordered multiples of the squared stepsize, together with a renewal-reward stopping-time argument for the probabilistic methods.
ER  -

Abstract

Related

Cite