Scalable Derivative-Free Optimization for Nonlinear Least-Squares Problems
This work addresses scalability issues in derivative-free optimization for nonlinear least-squares problems, which is incremental but offers practical benefits for applications with high-dimensional data.
The paper tackles the problem of solving nonlinear least-squares problems using derivative-free optimization by introducing a novel method that uses sketching for dimensionality reduction, resulting in dramatically improved runtime performance compared to existing software.
Derivative-free - or zeroth-order - optimization (DFO) has gained recent attention for its ability to solve problems in a variety of application areas, including machine learning, particularly involving objectives which are stochastic and/or expensive to compute. In this work, we develop a novel model-based DFO method for solving nonlinear least-squares problems. We improve on state-of-the-art DFO by performing dimensionality reduction in the observational space using sketching methods, avoiding the construction of a full local model. Our approach has a per-iteration computational cost which is linear in problem dimension in a big data regime, and numerical evidence demonstrates that, compared to existing software, it has dramatically improved runtime performance on overdetermined least-squares problems.