Source-linked AI summary
Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
Coralia Cartis, Katya Scheinberg
TL;DR
The paper asks how global convergence rates can be obtained when optimization models and derivative information are only probabilistically accurate. It develops a stochastic hitting-time framework for line-search and cubic-regularization methods, showing that probabilistic models preserve deterministic accuracy-order complexity while changing constants and supporting several function classes.
Problem
Deterministic model accuracy can be expensive or impossible to ensure at every iteration, while existing stochastic analyses often focus on expected error rather than expected steps to a target accuracy.
Method
The paper analyzes line-search and cubic-regularization algorithms through random models, conditional model-quality probabilities, and a stochastic process measuring progress toward optimality.
Results
The resulting bounds match deterministic counterparts in the order of accuracy ε, with model inaccuracy affecting a constant dependent on the probability of sufficient accuracy.
Takeaways & Limitations
The framework provides expected iteration complexity for probabilistic line-search and cubic-regularization methods across nonconvex, convex, and strongly convex settings.
Takeaways & Limitations
The paper leaves exact complexity comparisons based on total gradient samples and derivation of suitable probabilistic models for stochastic-gradient ARC settings to future work.
Abstract
from arXiv · showhide
We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. We particularize and improve these results in the convex and strongly convex case. We also analyze a probabilistic cubic regularization variant that allows approximate probabilistic second-order models and show improved complexity bounds compared to probabilistic first-order methods; again, as a function of the accuracy, the probabilistic cubic regularization bounds are of the same (optimal) order as for the deterministic case.
1 Introduction
The paper develops global convergence-rate analysis for optimization methods using random models that are sufficiently accurate only with probability. Its framework preserves deterministic-method structure while bounding expected iterations to reach a target accuracy.
- Motivation: Derivative and model requirements can be prohibitively expensive, unavailable, or impossible to satisfy at every iteration.This motivates replacing deterministic accuracy guarantees with probabilistic model-quality assumptions.
- Probabilistic models: The proposed methods allow model or derivative errors to be arbitrarily large on some iterations, provided accuracy holds with sufficiently high probability.The analysis assumes no zero-mean error or bounded variance and validates successful iterates using exact function evaluations.
- Methods: The analyzed algorithms closely follow deterministic line-search and cubic-regularization methods without iterate averaging or other major changes.The framework covers nonconvex, convex, and strongly convex line search, plus probabilistic cubic regularization.
- Complexity measure: Expected iteration complexity is bounded until a desired accuracy is reached, rather than bounding expected error after a fixed number of iterations.The stopping time N_ε is treated as a hitting time of a stochastic progress process.
- Stochastic analysis: The stochastic framework uses random models that remain sufficiently good with conditional probability at least p despite dependence on the iteration history.Step-size evolution and successful or unsuccessful iterations are analyzed through an associated stochastic process.
- Results: Under p > 1/2, the hitting time N_ε has a bound in expectation, and the framework can also yield exponentially decaying tail probabilities.The framework is intended to apply beyond the specific algorithms analyzed in the paper.
3 The line-search algorithm
This section introduces a probabilistic line-search algorithm within the paper’s generic framework for analyzing random-model optimization methods.
- The algorithm is presented as a simple probabilistic line-search method to which the generic stochastic-process analysis is applied.
- Choose γ ∈ (0, 1), θ ∈ (0, 1), and αmax > 0, then initialize x0 and α0 < αmax.
1. Compute a model and a step
The method computes a random model, uses it to generate a direction, and sets the step as a scaled negative direction.
- A random model m_k is computed.
- The model generates a direction g_k.
- The step is set as s_k = −α_k g_k.
3. Successful step
The line-search analysis treats model accuracy as probabilistic: true iterations are sufficiently accurate with probability p>1/2, and sufficiently small steps make true iterations successful. Expected complexity retains deterministic accuracy dependence, with p-dependent overhead.
- Line-search model: For the linear model mk(x) = f(xk) + (x − xk)^Tgk, the random direction gk determines each line-search step.The method uses a simple first-order model and updates the stepsize after successful or unsuccessful iterations.
- Probabilistic accuracy: p > 1/2 is required for probabilistically sufficiently accurate random models and directions.True iterations are defined through the model-accuracy indicators and their submartingale-like condition.
- Successful steps: A true iteration is successful whenever the stepsize satisfies the derived threshold condition under the Lipschitz-gradient assumption.The proof uses the global Lipschitz continuity of ∇f to establish sufficient decrease on true iterations.
- Nonconvex complexity: The nonconvex expected iteration bound has accuracy dependence of order 1/ε^2, matching deterministic smooth line-search methods.The dependence on p is finite for p>1/2, recovers deterministic complexity at p=1, and diverges as p approaches 1/2.
- Convexity effects: In convex and strongly convex settings, the expected bounds retain deterministic accuracy dependence; the strongly convex dependence is logarithmic in 1/ε.The probability parameter contributes the same type of overhead as in the nonconvex case.
4 Probabilistic second-order models and cubic regularization methods
The probabilistic ARC framework extends randomized modeling to approximate second-order information. It forms a cubic-regularized model, approximately minimizes it, and preserves the deterministic optimal convergence order in expectation with a probability-dependent term.
- Probabilistic ARC: Probabilistic ARC uses random approximate gradients and Hessians whose model is sufficiently accurate with probability at least p.The method targets general, not necessarily convex, objectives.
- Complexity: The expected probabilistic cubic-regularization rate has the same order as the deterministic optimal rate, augmented by a term depending on model-accuracy probability.This improves the complexity order compared with probabilistic first-order methods.
- Cubic model: The cubic model is approximately minimized in a trial step sk using a gradient gk, matrix bk, and regularization parameter σk.The step is required to satisfy the model stationarity and curvature conditions in (29).
- Step computation: The step conditions can be met by minimizing the model globally over a subspace, or even along the line αsk.A relative termination condition supports approximate model minimization.
1. Compute a model
The first ARC step is to compute approximate first- and second-order information and use it to form the cubic model.
- Model construction: Compute an approximate gradient gk and Hessian bk, then form the model (28).
2. Compute the trial step sk
After forming the cubic model, ARC computes a trial step that satisfies the prescribed approximate-minimization conditions.
- Trial step: Compute the trial step sk so that conditions (29) and (30) are satisfied.
3. Check sufficient decrease
The method checks whether random-model steps achieve sufficient decrease, then uses successful iterations to establish progress and an expected complexity bound. For probabilistic cubic regularization, the resulting dependence on accuracy is O(ε^-3/2), matching deterministic ARC.
- The algorithm classifies iterations as successful when the actual-to-predicted reduction ratio ρk meets threshold θ, otherwise retaining xk.
- True iterations use sufficiently accurate models with conditional probability at least p, even though model accuracy may depend on the history.
- For the cubic-regularization method, global Lipschitz continuity of the Hessian supports sufficient-decrease and gradient-norm bounds on true iterations.
- True, successful iterations provide progress, while sufficiently large σk guarantees success; these properties allow the generic stochastic-process analysis to apply.
- The expected iteration bound for reaching ∥∇f(Xk+1)∥≤ε has accuracy dependence O(ε^-3/2), the same order as deterministic ARC and optimal for nonconvex second-order optimization.
- The analysis also establishes almost-sure lim inf convergence of the gradient norm to zero for Algorithm 4.1.
5 Random models
The paper extends probabilistic-model analysis to stochastic gradients and derivative-free models by requiring model accuracy with sufficiently high conditional probability. These constructions support convergence-rate results while retaining explicit scope boundaries for sample-complexity analysis.
- For stochastic gradients, sufficiently large sample sets can make the gradient estimate probabilistically sufficiently accurate, extending the framework to nonconvex, convex, and strongly convex settings.
- The framework bounds iterations to target accuracy and supports lim inf-type almost-sure convergence, with exponentially decaying tails also obtainable.
- The exact comparison in total gradient samples remains future work because it requires a sample-size strategy and potentially improved analysis.
- Probabilistically fully-linear and fully-quadratic models differ from the paper’s models because their error scale Δk does not depend on the current random model Mk.
- Choosing the sampling radius proportional to the algorithmic step size can make fully-linear or fully-quadratic models sufficiently accurate for line search or ARC.
1. Compute a model
The method begins by constructing a probabilistically fully-linear model around the current iterate and using it to generate a search direction.
- At each iteration, the algorithm computes a probabilistically fully-linear model in B(xk, αkξk) and uses it to generate direction gk.
2. Check model accuracy
The algorithm tests whether the generated direction is sufficiently large before accepting a step, adapting ξk and model accuracy when necessary. For ARC, probabilistically fully-quadratic models yield the corresponding second-order accuracy conditions.
- If ∥gk∥ is below κΔξk, the algorithm rejects the step, keeps xk and αk unchanged, and reduces ξk by κΔ.
- If the direction passes the threshold, the algorithm takes sk=−αkgk and updates αk toward a larger step size when sufficient decrease holds.
- The maintained quantity ξk estimates the descent-direction norm, while δk=αkξk sets the radius used to construct fully-linear models.
- Once ξk is sufficiently small, the adaptive procedure reduces to the original line-search analysis; reaching that scale requires O(log(1/ε)) iterations.
- With probability at least p, each iteration either reduces ξk or uses a model that is sufficiently accurate.
- For ARC, sufficiently small δk makes probabilistically fully-quadratic models sufficiently accurate, and the second-order analysis uses the resulting bound on ∥∇f(xk+sk)∥.
- The required δk bound depends on problem constants that may be unknown beforehand, motivating an adaptive adjustment during the algorithm’s run.
1. Compute a model
The method constructs probabilistically fully-quadratic models and adapts the model region when the trial step is too short. Once the region parameter is sufficiently reduced, the method behaves like the preceding algorithm, with only an additional O(log(1/ǫ)) complexity term.
- Compute a model: Probabilistically fully-quadratic models are constructed in a ball whose radius is controlled by ξk/σk, and a trial step is computed from the model.The model uses approximate gradient and Hessian information, while the step must satisfy the prescribed conditions.
- Adapt the model region: If the trial step is too short, ξk is reduced while xk and σk remain unchanged, and a new model is generated in a smaller ball.The algorithm uses δk := ξk/σk as an underestimate of the step length.
- Reduction to the base algorithm: Once ξk falls below the required threshold, fully quadratic models ensure sufficiently accurate steps, and Algorithm 5.2 reduces to Algorithm 4.1.This reduction holds from the threshold-crossing iteration onward while the gradient norm remains at least ǫ.
- Complexity: O(log(1/ǫ)) is the additional complexity term accounting for the iterations needed to drive ξk below ξǫ.The remaining complexity is essentially that of Algorithm 4.1.