Direct Search Based on Probabilistic Descent in Reduced Spaces
From MaRDI portal
Abstract: In this paper, we study a generic direct-search algorithm in which the polling directions are defined using random subspaces. Complexity guarantees for such an approach are derived thanks to probabilistic properties related to both the subspaces and the directions used within these subspaces. Our analysis crucially extends previous deterministic and probabilistic arguments by relaxing the need for directions to be deterministically bounded in norm. As a result, our approach encompasses a wide range of new optimal polling strategies that can be characterized using our subspace and direction properties. By leveraging results on random subspace embeddings and sketching matrices, we show that better complexity bounds are obtained for randomized instances of our framework. A numerical investigation confirms the benefit of randomization, particularly when done in subspaces, when solving problems of moderately large dimension.
Recommendations
- Expected decrease for derivative-free algorithms using random subspaces
- Direct search based on probabilistic descent
- Direct search based on probabilistic feasible descent for bound and linearly constrained problems
- \(Q\)-fully quadratic modeling and its application in a random subspace derivative-free method
- Lower bounds for randomized direct search with isotropic sampling
Cites work
- A deterministic algorithm to compute the cosine measure of a finite positive spanning set
- A stochastic line search method with expected complexity analysis
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Benchmarking optimization software with performance profiles.
- Complexity and global rates of trust-region methods based on probabilistic models
- Concentration inequalities. A nonasymptotic theory of independence
- Convergence of trust-region methods based on probabilistic models
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Derivative-free and blackbox optimization
- Derivative-free optimization methods
- Direct search based on probabilistic descent
- Direct search based on probabilistic feasible descent for bound and linearly constrained problems
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- scientific article; zbMATH DE number 2002582 (Why is no real title available?)
- Improving the flexibility and robustness of model-based derivative-free optimization solvers
- Introduction to Derivative-Free Optimization
- On the optimal order of worst case complexity of direct search
- On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization
- Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
- Random gradient-free minimization of convex functions
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Smallest singular value of a random rectangular matrix
- Sparser Johnson-Lindenstrauss transforms
- Stochastic three points method for unconstrained smooth minimization
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- Worst case complexity of direct search
- Zeroth-order optimization with orthogonal random directions
Cited in
(12)- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- Expected decrease for derivative-free algorithms using random subspaces
- \(Q\)-fully quadratic modeling and its application in a random subspace derivative-free method
- Stochastic zeroth order descent with structured directions
- A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization
- Direct-search methods in the year 2025: theoretical guarantees and algorithmic paradigms
- Fully adaptive zeroth-order method for minimizing functions with compressible gradients
- Convergence towards a local minimum by direct search methods with a covering step
- A class of sparse Johnson-Lindenstrauss transforms and analysis of their extreme singular values
- Zeroth-order random subspace algorithm for non-smooth convex optimization
- Quasi-Newton method with subspace gradients
- A partitioned optimization framework for structure-aware problems
This page was built for publication: Direct Search Based on Probabilistic Descent in Reduced Spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071887)
