Scalable Derivative-Free Optimization for Nonlinear Least-Squares Problems

• URL: http://arxiv.org/abs/2007.13243v2
• Date: Sat, 1 Aug 2020 12:53:38 GMT
• Title: Scalable Derivative-Free Optimization for Nonlinear Least-Squares Problems
• Authors: Coralia Cartis and Tyler Ferguson and Lindon Roberts
• Abstract summary: Derivative-free - or zeroth-order - optimization (DFO) has gained recent attention for its ability to solve problems in a variety of application areas. We develop a novel model-based DFO method for solving nonlinear-squares problems.
• Score: 0.6445605125467572
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Mixed geometry information regularization for image multiplicative denoising [12.43943610396014]
  This paper focuses on solving the multiplicative gamma denoising problem via a variation model. To overcome these issues, in this paper we propose a mixed information model, incorporating area geometry term and curvature term as prior knowledge.
  arXiv  Detail & Related papers  (2024-12-21T02:24:42Z)
• On improving generalization in a class of learning problems with the method of small parameters for weakly-controlled optimal gradient systems [0.0]
  We consider a variational problem for a weakly-controlled gradient system, whose control input enters into the system dynamics as a coefficient to a nonlinear term. Using the perturbation theory, we provide results that will allow us to solve a sequence of optimization problems. We also provide an estimate for the rate of convergence for such approximate optimal solutions.
  arXiv  Detail & Related papers  (2024-12-11T20:50:29Z)
• Scalable Higher-Order Tensor Product Spline Models [0.0]
  We propose a new approach using a factorization method to derive a highly scalable higher-order tensor product spline model. Our method allows for the incorporation of all (higher-order) interactions of non-linear feature effects while having computational costs proportional to a model without interactions.
  arXiv  Detail & Related papers  (2024-02-02T01:18:48Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Deep Equilibrium Optical Flow Estimation [80.80992684796566]
  Recent state-of-the-art (SOTA) optical flow models use finite-step recurrent update operations to emulate traditional algorithms. These RNNs impose large computation and memory overheads, and are not directly trained to model such stable estimation. We propose deep equilibrium (DEQ) flow estimators, an approach that directly solves for the flow as the infinite-level fixed point of an implicit layer.
  arXiv  Detail & Related papers  (2022-04-18T17:53:44Z)
• Data-Driven Minimax Optimization with Expectation Constraints [9.373649142701803]
  We propose a class of efficient primal-dual algorithms to tackle the minimax expectation-constrained problem. We show that our algorithms converge at the optimal rate of $mathcalO(frac1sqrtN)$.
  arXiv  Detail & Related papers  (2022-02-16T05:23:27Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Progressive Batching for Efficient Non-linear Least Squares [31.082253632197023]
  Most improvements of the basic Gauss-Newton tackle convergence guarantees or leverage the sparsity of the underlying problem structure for computational speedup. Our work borrows ideas from both machine learning and statistics, and we present an approach for non-linear least-squares that guarantees convergence while at the same time significantly reduces the required amount of computation.
  arXiv  Detail & Related papers  (2020-10-21T13:00:04Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.