PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Optimization Using a Trust-Region Method and Random Models

Ruobing Chen, Matt Menickelly, Katya Scheinberg

arXiv:1504.04231v2math.OC

TL;DR

The paper addresses unconstrained stochastic optimization when objective models and function estimates are noisy and may be biased. It proposes a trust-region method using random models and probabilistically accurate estimates, and proves almost-sure convergence to first-order stationary points under fixed-probability accuracy conditions. The paper also discusses model construction under unbiased and biased noise, while leaving convergence rates for future work.

  • Problem

    The paper addresses optimization of smooth, lower-bounded stochastic objectives whose function values are noisy, in settings where existing analyses commonly assume unbiased noise or stronger accuracy conditions.

  • Method

    The paper proposes a trust-region framework that uses random local models and noisy function estimates, requiring sufficient accuracy with fixed high probability but no distributional assumptions beyond those conditions.

  • Results

    The method converges almost surely to first-order stationary points under its probabilistic accuracy conditions.

  • Takeaways & Limitations

    The framework accommodates biased noise and does not require increasing accuracy probabilities, making it applicable beyond the unbiased-noise settings emphasized by many existing methods.

  • Takeaways & Limitations

    The paper does not provide convergence rates, and its analysis may impose η2 ≥ Θ(L), potentially forcing small step sizes; practical implementations avoid η2.

Abstract

from arXiv · show

In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function $f(x)$, obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with sufficiently high, but fixed, probability. Beyond these conditions, no assumptions are made on how these models and estimates are generated. Under these general conditions we show an almost sure global convergence of the method to a first order stationary point. In the second part of the paper, we present examples of generating sufficiently accurate random models under biased or unbiased noise assumptions. Lastly, we present some computational results showing the benefits of the proposed method compared to existing approaches that are based on sample averaging or stochastic gradients.

1 Introduction

The paper develops a trust-region framework for unconstrained stochastic optimization with random models and noisy function estimates, requiring only sufficiently high fixed-probability accuracy. It extends beyond common unbiased-noise and increasing-accuracy assumptions to support biased noise and nonconvex problems.

  • Motivation: The paper targets smooth, lower-bounded objectives whose values are available only through noise, extending derivative-free optimization ideas to stochastic nonlinear optimization.Traditional derivative-free methods were primarily developed for deterministic functions, while related stochastic analyses often assume unbiased noise.
  • Framework: The proposed trust-region method builds random local models and noisy estimates at the current and candidate iterates to assess progress.Models must satisfy a first-order accuracy requirement, while function estimates must be sufficiently accurate with sufficiently high probability.
  • Framework: Convergence requires sufficiently accurate models and estimates with probabilities above fixed constants, without assuming distributions for the random quantities or increasing accuracy probabilities.This permits inaccurate values to have arbitrary magnitude, including nonconstant bias in function-value noise.
  • Scope: The framework applies to derivative-free and derivative-based optimization and is designed for stochastic nonlinear, not necessarily convex, functions.The paper emphasizes that it does not require a unique minimizer or a priori convergence of the iterate sequence in nonconvex settings.
  • Analysis and model generation: The analysis models the algorithm as a stochastic process using martingale theory and proves convergence to first-order stationary points with probability one.The paper also discusses generating accurate models under unbiased and biased noise, including sample averaging for unbiased noise.
  • Comparison with related work: Compared with sample averaging and stochastic-gradient approaches, the framework allows dynamically adjusted sampling and fixed-probability accuracy under biased noise.Related methods commonly use unbiased estimates, monotonically increasing sampling, increasing accuracy probabilities, or stronger convergence assumptions.

2 Trust Region Method

The method uses a trust-region algorithm with random objective models and noisy function estimates to choose steps, assess progress, and update the radius. It distinguishes successful iterations by estimated progress while recognizing that inaccurate estimates can make accepted steps increase the true objective.

  • Trust-region iteration: At each iteration, a random model approximates f within the current trust region, and its approximate minimization produces a trial step.The model and estimates are generated from stochastic observations; quadratic models are used for presentation and commonality.
  • Trust-region iteration: The algorithm estimates function values at the current and trial points, compares the achieved reduction with the model reduction, and accepts the trial point when reduction is sufficient.Otherwise, the current iterate is retained and the trust-region radius is adjusted according to the iteration outcome.
  • Step computation: The trial step must satisfy a fraction of Cauchy decrease condition to ensure sufficient reduction in the model.The condition is imposed with a constant κfcd ∈ (0, 1].
  • Success assessment: A successful iteration satisfies ρk ≥ η1 and ∥gk∥ ≥ η2δk, but inaccurate function estimates can make the true objective increase.The framework therefore distinguishes true successful iterations from false successful iterations, which may produce arbitrarily small or negative true reduction.
  • Success assessment: The framework generalizes random-model trust-region analysis by requiring sufficiently accurate estimates because exact function values are unavailable.Its model randomness arises from noisy objective observations rather than only from the model-construction process considered in earlier work.

3 Probabilistic Models and Estimates

The paper models both trust-region approximations and function-value estimates as random quantities whose conditional accuracy is sufficient with fixed high probability. These probabilistic accuracy requirements support the convergence analysis without prescribing how sampling or estimation must be performed.

  • Random quantities and accuracy: Random models, iterates, steps, trust-region radii, and function estimates form a stochastic process driven by samples of the stochastic objective.The paper denotes random models and their realizations separately, reflecting randomness throughout the algorithm.
  • Accuracy assumptions: The paper uses a standard fully-linear model definition under Lipschitz continuity of ∇f and extends it to probabilistic model sequences.Procedures for constructing such models and estimates under different noise models are deferred to Section 5.
  • Random models: Probabilistically fully-linear models are fully linear with sufficiently high conditional probability and may be arbitrarily inaccurate otherwise.This differs from assumptions based on expected values and variances of stochastic optimization models.
  • Random estimates: Function-value estimates must be sufficiently accurate to determine whether a trial step is successful, unlike analyses that assume exact values at the current and trial points.The estimate accuracy is defined relative to the trust-region radius and is required probabilistically with respect to the evolving stochastic process.
  • Accuracy assumptions: The convergence analysis assumes fixed κ-fully-linear model accuracy and sufficiently small ϵF-accurate estimates, each achieved with sufficiently high probability conditioned on the past.Both accuracy requirements scale proportionally to δk^2, while the estimate condition is tighter because of an upper bound on ϵF.

4 Convergence Analysis

The convergence analysis establishes almost-sure first-order convergence under probabilistic accuracy requirements for random models and function estimates, together with regularity assumptions on the objective. It proceeds through decrease guarantees, trust-region-radius convergence, and liminf- and lim-type gradient results.

  • Assumptions: The analysis assumes f is bounded below and that f and its gradient are Lipschitz continuous in the region considered by algorithm realizations.The region may depend on algorithmic behavior because noisy estimates can permit iterates to increase the true objective.
  • Decrease guarantees: If a fully linear model, accurate estimates, and a sufficiently small trust-region radius satisfy the stated conditions, the trial step is guaranteed to produce a successful iteration.The successful iteration follows from sufficient model and estimate accuracy together with a radius condition relative to the model gradient.
  • Decrease guarantees: Accepted trial steps guarantee a lower bound on improvement in the true objective function.The bound applies on successful iterations, where the model-gradient and acceptance-ratio conditions hold.
  • Assumptions: Random models must be sufficiently accurate with high probability, while function estimates must be sufficiently accurate with high probability.The model requirement is probabilistic full linearity, and the estimate requirement is probabilistic accuracy with fixed parameters.
  • Global convergence: The trust-region radius converges to zero with probability 1 under the theorem’s assumptions and suitable choices of accuracy probabilities.A corollary specifies additional conditions on the model and estimate failure probabilities.
  • Global convergence: The algorithm first yields a liminf-type result, then establishes that the gradient norm converges to zero almost surely.The latter result accounts for the possibility that noisy function values increase along the iterates.

5 Constructing models and estimates in different stochastic settings.

The paper constructs probabilistically accurate models and function estimates under unbiased noise, biased noise, and stochastic computation failures. These constructions support the framework’s assumptions, while hidden constraints remain outside its theory and convergence rates are left unresolved.

  • Simple stochastic noise: Under unbiased noise, sample averaging can construct sufficiently accurate function estimates, with sample size chosen through variance bounds and Chebyshev’s inequality.The construction targets κ-fully linear models and β-probabilistically εF-accurate estimates in a trust region.
  • Simple stochastic noise: With function-only observations on a well-poised interpolation set, the resulting model is κ-fully linear with probability at least α = (α′)^(n+1).Each sampled function value must satisfy the required accuracy event for the interpolation model.
  • Simple stochastic noise: With noisy gradients available, a linear expansion using averaged function and gradient values becomes a κ-fully linear model with probability at least α = (α′)^2.The model uses the averaged function value and averaged gradient at the trust-region center.
  • Function computation failures: For biased noise, optimizing the noisy expectation generally differs from optimizing f(x), so Monte Carlo sampling alone is not a correct approach.The discrepancy persists when the failure probability depends on x and the inaccurate-output expectation is not constant.
  • Function computation failures: When computation failures occur with probability bounded by σ, exact evaluations yield fully linear models with probability at least (1 − σ)^|Y|.The same setting supports accurate estimates when the relevant evaluations are correct.
  • Scope and limitations: The theory excludes hidden constraints, where function computation can fail continually at specific points, and it does not provide convergence rates.The authors leave whether the algorithm achieves an optimal sampling rate as an open question.

6 Computational Experiments

The experiments evaluate STORM variants under unbiased, additive, multiplicative, and biased noise, including comparisons with sample-averaging trust-region methods and stochastic-gradient methods. Results report strong STORM performance, robustness to function-computation failures, and stable loss trajectories.

  • Simple stochastic noise: The experiments compare STORM variants with TR-SAA and TR-SAA-resample on 53 unconstrained sum-of-squares problems under noisy function evaluations.The test budget was 1000(n + 1) noisy evaluations, with results averaged over 10 runs per problem.
  • Simple stochastic noise: For the tested unbiased noise setting, computational results show that a constant number of samples is sufficient for convergence.The passage notes that this behavior is not established by theory because the rate at which f(x_k) decreases is unknown.
  • Simple stochastic noise: STORM-unbiased performs extremely well compared with TR-SAA in the reported performance profiles.The comparison uses multiplicative noise with τ = 10^-3.
  • Function computation failures: 100% of n = 10 instances were solved when (1 − σ) = .998, although the models were accurate on only roughly 27% of iterations.The required accuracy was f(x*) < 10^-5 within 10^4 function evaluations.
  • Stochastic-gradient comparison: STORM implementations produce fairly stable decreasing training-loss trajectories, while Adagrad’s true function values vary widely over the displayed horizon.The loss appears to generalize fairly well to holdout test data.

7 Appendix

The appendix gives a trust-region algorithm that builds quadratic models from averaged function estimates, computes a trial step, evaluates progress, and accepts or rejects the step using ratio and gradient conditions.

  • Algorithm: The algorithm initializes x0, the trust-region radius, control constants, and an interpolation set Y0 containing x0.The set size is bounded by pmax, with pmin ≥ n + 1.
  • Algorithm: The sample rate is updated as pk = max{pmin + k, 1/δ}.This links sampling effort to iteration count and the inverse trust-region scale.
  • Algorithm: A quadratic model is built to interpolate averaged function estimates at the interpolation points, and a trust-region step approximately minimizes that model.The model uses gradient and Hessian terms around xk.
  • Algorithm: New estimates at the current and trial points are used to calculate the actual-to-predicted progress ratio.The ratio compares estimated function decrease with model decrease.
  • Algorithm: The trial point is accepted when ρk ≥ η1 and ∥gk∥ ≥ η2δk; otherwise, the current iterate is retained.The interpolation set is then augmented and pruned if it exceeds pmax.

14 end

This appendix variant uses independently sampled regression sets and noisy function estimates to construct a quadratic regression model within a trust-region iteration.

  • STORM for unbiased noise: The algorithm initializes a trust region and selects an initial regression set Y0 of size pmin.The initialization requires pmin and the trust-region control constants.
  • STORM for unbiased noise: The sample rate is set to pk = max{pmin + k, 1/δ}, and a regression set is uniformly sampled inside the trust region.The regression set is refreshed during the iteration.
  • STORM for unbiased noise: New regression value estimates are computed for the sampled points before constructing the model.The model therefore uses freshly estimated noisy function information.
  • STORM for unbiased noise: A quadratic model regresses the noisy function estimates at the regression points, and the trial step approximately minimizes the model.The model is expressed using gradient and Hessian terms around xk.
  • STORM for unbiased noise: The algorithm computes new current and trial estimates, forms the model decrease ratio, and accepts the step only when the ratio and gradient conditions hold.Otherwise, it keeps xk and proceeds to the next iteration.

13 end

This appendix variant repeatedly recomputes interpolation values on a changing interpolation set, builds an interpolating quadratic model, and applies trust-region acceptance rules.

  • STORM for unbiased noise: The algorithm initializes x0, trust-region controls, and an interpolation set Y0 of size p0 within the initial trust region.The set-size bounds include p0 ≥ n + 1 and pmax = (n + 1)(n + 2)/2.
  • STORM for unbiased noise: New interpolation value estimates are computed for every point in Yk before model construction.The interpolation values are recomputed during each iteration.
  • STORM for unbiased noise: A quadratic model interpolates the newly estimated noisy values at the interpolation points, and a trial step approximately minimizes the model.The model is centered at xk and includes gradient and Hessian terms.
  • STORM for unbiased noise: The trial step is accepted only when ρk ≥ η1 and ∥gk∥ ≥ η2δk; the interpolation set is then augmented and pruned if necessary.The iteration counter is incremented after the update.

12 end

STORM initializes a trust-region problem, builds a stochastic quadratic model from sampled gradients and Hessians, estimates function values with new samples, and accepts or rejects trial steps using model agreement and gradient-size conditions.

  • Initialization: STORM initializes x0, a trust-region radius δ0, algorithmic constants, and iteration counter k.The initial radius lies in (0, δmax).
  • Sampling: At each iteration, the method chooses a sample rate pk and uniformly draws a sample Ik without replacement.The sample Ik is drawn from {1, . . . , N}.
  • Model building: Using Ik, STORM computes a stochastic gradient gk and stochastic Hessian Hk to define a quadratic model mk(s).The model includes a linear gradient term and a Hessian-based quadratic term.
  • Model building: The method approximately minimizes mk(s) to obtain a trial step sk within the trust-region procedure.The supplied algorithm passage identifies sk as the approximate model-minimization step.
  • Estimates calculation: New samples are drawn to compute function-value estimates used in assessing the trial step.The estimates concern function values at the current and trial points.
  • Acceptance and iteration: The trial step is accepted when ρk ≥ η1 and ∥gk∥ ≥ η2δk; otherwise, the iterate remains unchanged before k increments.Acceptance updates xk+1 to xk + sk, while rejection sets xk+1 to xk.
Loading 1504.04231v2…