Lindon Roberts

Model Construction for Convex-Constrained Derivative-Free Optimization

  • Lindon Roberts
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We develop a new approximation theory for linear and quadratic interpolation models, suitable for use in convex-constrained derivative-free optimization (DFO). Most existing model-based DFO methods for constrained problems assume the ability to construct sufficiently accurate approximations via interpolation, but the standard notions of accuracy (designed for unconstrained problems) may not be achievable by only sampling … Read more

    Expected decrease for derivative-free algorithms using random subspaces

  • Lindon Roberts
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags ,

    Derivative-free algorithms seek the minimum of a given function based only on function values queried at appropriate points. Although these methods are widely used in practice, their performance is known to worsen as the problem dimension increases. Recent advances in developing randomized derivative-free techniques have tackled this issue by working in low-dimensional subspaces that are … Read more

    Analyzing Inexact Hypergradients for Bilevel Learning

  • Matthias J. Ehrhardt
  • Lindon Roberts
    • Categories Nonlinear Optimization, Optimization in Data Science Tags , ,

    Estimating hyperparameters has been a long-standing problem in machine learning. We consider the case where the task at hand is modeled as the solution to an optimization problem. Here the exact gradient with respect to the hyperparameters cannot be feasibly computed and approximate strategies are required. We introduce a unified framework for computing hypergradients that … Read more

    A Simplified Convergence Theory for Byzantine Resilient Stochastic Gradient Descent

  • Lindon Roberts
    • Categories Optimization in Data Science, Stochastic Programming Tags , ,

    In distributed learning, a central server trains a model according to updates provided by nodes holding local data samples. In the presence of one or more malicious servers sending incorrect information (a Byzantine adversary), standard algorithms for model training such as stochastic gradient descent (SGD) fail to converge. In this paper, we present a simplified … Read more

    Direct search based on probabilistic descent in reduced spaces

  • Lindon Roberts
  • ClĂ©ment W. Royer
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Derivative-free algorithms seek the minimum value of a given objective function without using any derivative information. The performance of these methods often worsen as the dimension increases, a phenomenon predicted by their worst-case complexity guarantees. Nevertheless, recent algorithmic proposals have shown that incorporating randomization into otherwise deterministic frameworks could alleviate this effect for direct-search methods. … Read more

    Model-Based Derivative-Free Methods for Convex-Constrained Optimization

  • Matthew Hough
  • Lindon Roberts
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We present a model-based derivative-free method for optimization subject to general convex constraints, which we assume are unrelaxable and accessed only through a projection operator that is cheap to evaluate. We prove global convergence and a worst-case complexity of $O(\epsilon^{-2})$ iterations and objective evaluations for nonconvex functions, matching results for the unconstrained case. We introduce … Read more

    Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization

  • Coralia Cartis
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , ,

    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 … Read more

    Inexact Derivative-Free Optimization for Bilevel Learning

  • Matthias J. Ehrhardt
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , , ,

    Variational regularization techniques are dominant in the field of mathematical imaging. A drawback of these techniques is that they are dependent on a number of parameters which have to be set by the user. A by now common strategy to resolve this issue is to learn these parameters from data. While mathematically appealing this strategy … Read more

    Escaping local minima with derivative-free methods: a numerical investigation

  • Coralia Cartis
  • Lindon Roberts
  • Oliver Sheridan-Methven
    • Categories Nonlinear Optimization Tags , ,

    We apply a state-of-the-art, local derivative-free solver, Py-BOBYQA, to global optimization problems, and propose an algorithmic improvement that is beneficial in this context. Our numerical findings are illustrated on a commonly-used test set of global optimization problems and associated noisy variants, and on hyperparameter tuning for a machine learning test set. As Py-BOBYQA is a … Read more

    Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers

  • Coralia Cartis
  • Jan Fiala
  • Benjamin Marteau
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , , , , ,

    We present DFO-LS, a software package for derivative-free optimization (DFO) for nonlinear Least-Squares (LS) problems, with optional bound constraints. Inspired by the Gauss-Newton method, DFO-LS constructs simplified linear regression models for the residuals. DFO-LS allows flexible initialization for expensive problems, whereby it can begin making progress from as few as two objective evaluations. Numerical results … Read more