Scalable subspace methods for derivative-free nonlinear least-squares optimization
From MaRDI portal
Publication:6038650
DOI10.1007/S10107-022-01836-1arXiv2102.12016OpenAlexW3133264924MaRDI QIDQ6038650FDOQ6038650
Authors: Coralia Cartis, Lindon Roberts 
Publication date: 2 May 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We introduce a general framework for large-scale model-based derivative-free optimization based on iterative minimization within random subspaces. We present a probabilistic worst-case complexity analysis for our method, where in particular we prove high-probability bounds on the number of iterations before a given optimality is achieved. This framework is specialized to nonlinear least-squares problems, with a model-based framework based on the Gauss-Newton method. This method achieves scalability by constructing local linear interpolation models to approximate the Jacobian, and computes new steps at each iteration in a subspace with user-determined dimension. We then describe a practical implementation of this framework, which we call DFBGN. We outline efficient techniques for selecting the interpolation points and search subspace, yielding an implementation that has a low per-iteration linear algebra cost (linear in the problem dimension) while also achieving fast objective decrease as measured by evaluations. Extensive numerical results demonstrate that DFBGN has improved scalability, yielding strong performance on large-scale nonlinear least-squares problems.
Full work available at URL: https://arxiv.org/abs/2102.12016
Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Derivative-free methods and methods using generalized derivatives (90C56)
Cites Work
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Bayesian optimization in a billion dimensions via random embeddings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Benchmarking optimization software with performance profiles.
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Title not available (Why is that?)
- Randomized Algorithms for Matrices and Data
- Trust Region Methods
- Connected components in random graphs with given expected degree sequences
- Random gradient-free minimization of convex functions
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Introduction to Derivative-Free Optimization
- Direct search based on probabilistic descent
- Worst case complexity of direct search
- Coordinate descent algorithms
- Benchmarking Derivative-Free Optimization Algorithms
- Stochastic optimization using a trust-region method and random models
- Convergence of trust-region methods based on probabilistic models
- A derivative-free algorithm for least-squares minimization
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
- Detection and Remediation of Stagnation in the Nelder--Mead Algorithm Using a Sufficient Decrease Condition
- Geometry of interpolation sets in derivative free optimization
- On trust region methods for unconstrained minimization without derivatives
- Least Frobenius norm updating of quadratic models that satisfy interpolation conditions
- Optimizing partially separable functions without derivatives
- Sparser Johnson-Lindenstrauss transforms
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- Sketching as a tool for numerical linear algebra
- Derivative-free optimization methods
- A Derivative-Free Method for Structured Optimization Problems
- Advances and Trends in Optimization with Engineering Applications
- Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Sub-sampled Newton methods
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- An investigation of Newton-sketch and subsampled Newton methods
- Block stochastic gradient iteration for convex and nonconvex optimization
- Stochastic three points method for unconstrained smooth minimization
- Inexact derivative-free optimization for bilevel learning
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- A derivative-free Gauss-Newton method
- Improving the flexibility and robustness of model-based derivative-free optimization solvers
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Error bounds for overdetermined and underdetermined generalized centred simplex gradients
- Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization
- Direct search based on probabilistic feasible descent for bound and linearly constrained problems
- Complexity and global rates of trust-region methods based on probabilistic models
- Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings
- Two decades of blackbox optimization applications
- A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
- Optimization by moving ridge functions: derivative-free optimization for computationally intensive functions
Cited In (13)
- Adaptive state-dependent diffusion for derivative-free optimization
- Global optimization using random embeddings
- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- On the global complexity of a derivative-free Levenberg-Marquardt algorithm via orthogonal spherical smoothing
- The substitution secant/finite difference method for large scale sparse unconstrained optimization
- Expected decrease for derivative-free algorithms using random subspaces
- Direct Search Based on Probabilistic Descent in Reduced Spaces
- \(Q\)-fully quadratic modeling and its application in a random subspace derivative-free method
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Quadratic regularization methods with finite-difference gradient approximations
- Stochastic zeroth order descent with structured directions
- Large-scale unconstrained optimization using separable cubic modeling and matrix-free subspace minimization
- A Subspace Decomposition Principle for Scaled Gradient Projection Methods: Local Theory
This page was built for publication: Scalable subspace methods for derivative-free nonlinear least-squares optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038650)
