PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of trust-region methods based on probabilistic models

Afonso S. Bandeira, Katya Scheinberg, Luis Nunes Vicente

arXiv:1304.2808v1math.OCmath.PR

TL;DR

Randomized models are used to optimize deterministic functions, with derivative-free optimization providing a motivation for sampling-based local models. The paper analyzes a trust-region method requiring sufficiently accurate first-order models at least half the time, and reports almost-sure first-order convergence plus a second-order stationary subsequence under its stated conditions.

  • Problem

    Model-based derivative-free optimization can require complex sample-set maintenance to balance model quality, sample counts, and computational expense.

    Source: §1.1 · p. 2

  • Method

    The paper analyzes a trust-region method using random models whose sufficient first-order accuracy occurs with probability at least 1/2, possibly conditional on prior history.

    Source: §1.2 · p. 3, §3.1 · p. 7

  • Results

    The method’s gradient converges to zero almost surely, and with probabilistically fully quadratic models a subsequence reaches second-order stationarity almost surely.

    Source: §1.2 · p. 3, §5.3 · p. 19

  • Takeaways & Limitations

    The trust-region framework can use random models that may be inaccurate, provided sufficiently accurate models are more likely than not under the stated conditions.

    Source: §1.2 · p. 3

    For random sample sets that may be dependent, the paper leaves for future work determining when the submartingale property holds or can be relaxed while preserving convergence results.

    Source: §6.2 · p. 27

Abstract

from arXiv · show

In this paper we consider the use of probabilistic or random models within a classical trust-region framework for optimization of deterministic smooth general nonlinear functions. Our method and setting differs from many stochastic optimization approaches in two principal ways. Firstly, we assume that the value of the function itself can be computed without noise, in other words, that the function is deterministic. Secondly, we use random models of higher quality than those produced by usual stochastic gradient methods. In particular, a first order model based on random approximation of the gradient is required to provide sufficient quality of approximation with probability greater than or equal to 1/2. This is in contrast with stochastic gradient approaches, where the model is assumed to be "correct" only in expectation. As a result of this particular setting, we are able to prove convergence, with probability one, of a trust-region method which is almost identical to the classical method. Hence we show that a standard optimization framework can be used in cases when models are random and may or may not provide good approximations, as long as "good" models are more likely than "bad" models. Our results are based on the use of properties of martingales. Our motivation comes from using random sample sets and interpolation models in derivative-free optimization. However, our framework is general and can be applied with any source of uncertainty in the model. We discuss various applications for our methods in the paper.

1 Introduction

The paper studies randomized models for deterministic optimization, motivated by model-based derivative-free optimization and the trade-offs in constructing local models. It embeds these models in a trust-region method and analyzes convergence when model accuracy is probabilistic.

1.1 Motivation

  • Random sample sets may offer higher-quality models with fewer points and less complex maintenance, motivating randomized models for derivative-free optimization.The framework is not limited to derivative-free optimization and can also use models built from derivative information when sufficiently accurate with some probability.Source: §1.1 · pp. 2–3

1.2 Trust-region framework

  • The method uses a classical trust-region framework with random models: steps are accepted or rejected based on objective decrease, and the radius is adjusted accordingly.The paper states that this method drives the trust-region radius to zero.Source: §1.2 · p. 3
  • First-order model accuracy with probability at least 1/2 yields almost-sure convergence of the objective gradient to zero; second-order accuracy gives a stationary subsequence, with stronger assumptions needed for lim-type convergence.The analysis uses submartingale-like properties of events that models are accurate or inaccurate, conditional on the prior history.Source: §1.2 · p. 3

1.3 Notation

  • The introduction previews first- and second-order model definitions, convergence analyses, and examples of random models satisfying the required conditions.The paper lists commonly used constants for bounds on model errors, derivatives, and related quantities.Source: §1.3 · pp. 3–4

2 Methods of derivative-free optimization

Derivative-free optimization methods use function samples because derivatives are unavailable, with approaches ranging from directional search to model-based trust regions. The paper’s illustration contrasts directional methods with quadratic trust-region models and motivates random sampling for model construction.

2 Methods of derivative-free optimization

  • Directional methods use objective samples to explore directions, while model-based DFO builds interpolation or regression approximations from nearby sample points.DFO assumes explicit derivatives are unavailable; samples may explore directions or build models.Source: §2 · p. 4
  • Finite-basis directional methods can be slow on larger problems, while allowing infinitely many positive bases was proposed to improve practical performance.Directional methods may lack curvature information and rarely reuse sample points; dense generation on the unit sphere supports results for nonsmooth functions.Source: §2 · p. 4
  • DSR reaches f = 10−8 in 5,756 evaluations, while CS reaches f = 10−6 in 11,307 evaluations in the Figure 1 illustration.DSR uses a randomly generated orthogonal positive basis; CS is coordinate or compass search.Source: Figure 1 · p. 5, §2 · p. 5
  • Random directional approaches can find descent directions more successfully than coordinate search, while accurate models can improve efficiency; the paper therefore considers models built from random samples.Deterministic sample-set maintenance can be costly, and randomized models are presented as a possible alternative offering good approximations with high probability.Source: §2 · p. 5
  • TRQ reaches f = 10−14 in 62 evaluations, while RS reaches f = 10−8 in 3,724 evaluations in the Figure 2 illustration.TRQ is a basic model-based trust-region method with quadratic models; RS is random search with step size inversely proportional to iteration count.Source: §2 · p. 5, Figure 2 · p. 6

3 First order trust-region method based on probabilistic models

The first-order method places random models inside a trust-region framework and assumes that sufficiently accurate models occur with adequate probability, even when model quality depends on the algorithm’s history. Its update rules yield a radius-convergence property under the stated step and smoothness conditions.

3.1 The probabilistically fully linear models

  • Probabilistically fully linear models are sufficiently accurate with probability at least p, conditional on prior history, rather than requiring independence from that history.Fully linear accuracy is defined over the trust-region ball; the model sequence may depend on the algorithm’s past.Source: §3.1 · pp. 6–7

3.2 Algorithm and basic properties

  • The method approximately minimizes a model in the trust region and accepts a step when the reduction ratio and model-gradient condition pass thresholds; otherwise it rejects the step and shrinks the radius.The step is required to achieve a fraction of Cauchy decrease, and the model Hessians are uniformly bounded under an assumption the authors describe as nonrestrictive for fully linear models.Source: §3.1 · p. 7, §3.2 · p. 8
  • The first-order convergence analysis assumes a continuously differentiable objective with Lipschitz-continuous gradient on the specified region, and an objective bounded below on the initial level set.The stated trust-region radii are bounded above by the algorithm’s δmax.Source: §3.2 · p. 8
  • The trust-region radius converges to zero for every algorithm realization when each step achieves a fraction of Cauchy decrease.For successful steps with radius sufficiently small relative to the model-gradient norm, the method increases the radius; the proof uses objective decrease and a lower bound on the function.Source: §3.2 · pp. 8–9

4 Convergence of the first order trust-region method based on probabilistic models

Under probabilistically fully linear random models, the first-order trust-region analysis proves almost-sure convergence of gradient norms to zero. It uses martingale arguments and extends the results to modified trust-region radius rules.

4 Convergence of the first order trust-region method based on probabilistic models

  • The analysis uses a bounded-increment submartingale result: the process either converges to a finite limit or is unbounded above.The paper applies this result to the log of the trust-region radius, which behaves as a random walk with upward drift.Source: §4 · pp. 9–10

4.1 The liminf-type convergence

  • Theorem 4.2 establishes that the gradient norm has liminf zero almost surely under probabilistically fully linear models.The proof uses a submartingale argument to show that the norm cannot remain bounded away from zero.Source: §4.1 · pp. 10–11

4.2 The lim-type convergence

  • Almost surely, the gradient norm converges to zero when the model sequence is probabilistically fully linear.Theorem 4.3 establishes this lim-type result for iterates generated by Algorithm 3.1.Source: §4.2 · pp. 11–12

4.3 Modified trust-region schemes

  • The authors propose a less restrictive radius update and state that the convergence proofs adapt, including with separate decrease and increase thresholds.The proposed thresholds satisfy 0 < η0 < 1 for decrease and η1 > η0 for increase.Source: §4.3 · p. 14

5 Second order trust-region method based on probabilistic models

The second-order method uses probabilistically fully quadratic models in a trust-region algorithm and proves almost-sure convergence results for second-order stationarity. It establishes liminf convergence, but does not prove that the full sequence’s second-order stationarity measure converges to zero under the stated probabilistic conditions.

5.1 The probabilistically fully quadratic models

  • A sequence of random models is probabilistically (κeh, κeg, κef)-fully quadratic if its model events satisfy the submartingale-like condition with conditional probability p ≥ 1/2 given prior model history.Source: §5.1 · p. 15
  • Under the stated smoothness assumptions, fully quadratic models have bounded Hessians and approximate the second-order stationarity measure with error of order δk.The Hessian bound follows from boundedness of the function Hessian; the τ-measure error bound extends the model approximation analysis to second order.Source: §5.1 · pp. 15–16
  • When τk tends to zero, the gradient norm and the magnitude of negative Hessian curvature both tend to zero.The paper’s τ measure incorporates gradient and Hessian information to assess second-order stationarity.Source: §5.1 · pp. 16–17

5.2 Algorithm and liminf-type convergence

  • Algorithm 5.1 approximately minimizes each model for a fraction of optimal decrease and updates the trust-region radius according to the step’s performance.The stated step construction can compare the Cauchy step with an eigenstep when the model has negative curvature.Source: §5.1 · pp. 15–16, §5.2 · pp. 17–18
  • Almost surely, Algorithm 5.1 has lim inf τk = 0 when its models are probabilistically fully quadratic.The theorem establishes a subsequence approaching second-order stationarity.Source: §5.2 · pp. 18–19

5.3 The lim-type convergence

  • Almost surely, the iterates approach first-order stationary points, and a subsequence approaches a second-order stationary point.If the Hessian is strictly positive definite at every second-order stationary point, the paper states that all limit points are second-order stationary.Source: §5.3 · p. 19
  • The paper cannot establish full-sequence convergence of τk to zero under the probabilistic model conditions because trust-region growth is not guaranteed at every iteration.The authors say an added assumption that fully quadratic models become more likely in some cases yields a proof, but effectively leads to deterministic schemes.Source: §5.3 · pp. 20–21

6 Examples of probabilistically fully linear and fully quadratic models in DFO

The section describes polynomial interpolation and random sampling strategies for building probabilistically accurate models in derivative-free optimization. Its examples compare random and deterministic sample sets and discuss when sparse recovery, parallel evaluations, and reuse of samples may be useful.

6.1 Fully linear and fully quadratic polynomial interpolation models and Λ- poised sample sets

  • For Λ-poised sets near the current iterate, at least n+1 points support fully linear models, while (n+1)(n+2)/2 points support fully quadratic models, with constants O(pΛ).Estimating the interpolation matrix condition number may require O(n6) operations, limiting fully quadratic models to small-dimensional problems.Source: §6.1 · pp. 22–23
  • Incomplete quadratic models reduce sample and linear-algebra costs; minimizing the Hessian-coefficient L1 norm can recover fully quadratic models for sparse Hessians from fewer points.The section notes that the required sparse recovery sample-count condition is developed using compressed sensing and random matrix theory.Source: §6.1 · p. 23, §6.2 · p. 25

6.2 Random sample sets

  • Random sample sets can provide good models with sufficiently high probability without the worst-case behavior of deterministic sets chosen independently of the function's shape.Bounds for random interpolation matrices and their fixed-sample condition numbers are identified as future research.Source: §6.2 · pp. 23, 25
  • Random sample sets achieved 10−6 in 2,700 evaluations, compared with 10−4 in 8,500 evaluations for deterministic sets using MFN models.The random set used four points in a ball around the current iterate; the deterministic set used the iterate and coordinate steps.Source: §6.2 · pp. 23–24
  • Nonuniform recovery can use fewer samples than uniform recovery when only the specific model approximating the objective within a trust region must be recovered.The probability of a good model may be conditioned on the current iterate and trust-region radius, consistent with the framework's submartingale property rather than independence from the past.Source: §6.2 · pp. 25–26
  • On the 10-dimensional test, RSTR reached 4.0e-11 in 18 iterations versus 5.0e-8 for GSTR and 2.5e-5 for MFN, with 494 function evaluations; only RSTR recovered fully quadratic models.The authors note that RSTR's function evaluations can be obtained in parallel.Source: Figure 3 · p. 26, §6.2 · p. 26
  • In parallel evaluations, late function values may be omitted while the returned subset remains random; approximate sample-point values can also yield good models with high probability.The value evaluated at a potential new iterate is still assumed accurate; relaxing that condition is left for future study.Source: §6.2 · p. 27
  • Greedy sample sets that reuse points can make sparse models useful in practice, but the submartingale conditions and convergence guarantees for such dependent sets remain future work.The sparse recovery properties are unlikely to hold for these greedy sets.Source: §6.2 · p. 27
Loading 1304.2808v1…