Stochastic and Noisy Oracles in Smooth Continuous Optimization
Organizations: Department of Industrial and Operations Engineering, University of Michigan. · School of Mathematics, Nanjing University. · School of Industrial and Systems Engineering, Georgia Institute of Technology.
Abstract
We review models of inexact computational oracles in smooth continuous optimization and their implications for the convergence, computational complexity, and attainable accuracy of optimization algorithms. We adopt a framework in which zeroth-,first-, and second-order oracles are characterized by quantitative error bounds and may accept additional control parameters that influence both their accuracy and computational cost. We introduce deterministic and stochastic oracle models and illustrate their properties through a variety of examples, including finite-difference approximations, stochastic gradients, and randomized derivative estimators. Particular attention is given to the distinction between absolute and relative errors, bias and variance, and stochastic function evaluations with independent or coupled randomness. A central theme of the review is the use of common analytical tools to recover and compare convergence and complexity guarantees under different oracle models. For deterministic and stochastic first-order methods, we show how a general descent inequality leads to complexity bounds under various assumptions on the objective function and all proposed oracle models. In the stochastic setting, we develop bounds on expected stopping times and the accuracy that can be guaranteed under different oracle conditions. We also examine the total computational complexity of algorithms relying on specific oracle constructions and briefly review models of inexact second- order information and their use in optimization algorithms.
Figures & tables
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Description |
|---|---|
| Dimension of the decision variable. | |
| [1pt/2pt] | Decision variable. |
| [1pt/2pt] | Iterate at iteration . |
| [1pt/2pt] | Iteration counter. |
| [1pt/2pt] | True objective function. |
| [1pt/2pt] | Gradient of the true objective function. |
| Symbol | Description |
|---|---|
| Lipschitz constant of the function of . | |
| [1pt/2pt] | Lipschitz constant of the gradient of . |
| [1pt/2pt] | Lipschitz constant of the Hessian of . |
| [1pt/2pt] | Strong convexity or Polyak–Łojasiewicz (PL) parameter, according to context. |
| [1pt/2pt] | Diameter of the relevant level set. |
| [1pt/2pt] | Constant appearing in the Kurdyka–Łojasiewicz (KL) condition. |
| Symbol | Description |
|---|---|
| Inexact zeroth-order approximation of the objective function . | |
| [1pt/2pt] | Inexact first-order approximation of the gradient . |
| [1pt/2pt] | Inexact matrix-valued second-order approximation of the Hessian . |
| [1pt/2pt] | Inexact approximation of the Hessian-vector product . |
| [1pt/2pt] | Oracle control parameter, or collection of control parameters, governing oracle accuracy and computational cost. |
| [1pt/2pt] | Error measure used to quantify the discrepancy between two matrix-valued second-order quantities. |
| Symbol | Description |
|---|---|
| Additive error bound associated with the deterministic zeroth-order oracle. | |
| [1pt/2pt] | Additive error bound associated with the deterministic first-order oracle. |
| [1pt/2pt] | Multiplicative error parameter associated with the deterministic first-order oracle. |
| [1pt/2pt] | Modified multiplicative first-order error parameter, defined by . |
| [1pt/2pt] | Accuracy parameter for the deterministic matrix-valued second-order oracle under the error measure . |
| [1pt/2pt] | Accuracy parameter for the deterministic Hessian-vector product oracle, controlling the approximation error relative to . |
| Symbol | Description |
|---|---|
| Squared bias bound associated with a stochastic zeroth-order oracle. | |
| [1pt/2pt] | Variance bound associated with the single-point stochastic zeroth-order oracle. |
| [1pt/2pt] | Centered stochastic zeroth-order error, defined by . |
| [1pt/2pt] | Additive parameter controlling the mean-square variation of stochastic zeroth-order errors between multiple query points. |
| [1pt/2pt] | Gradient-dependent parameter controlling the mean-square variation of stochastic zeroth-order errors between multiple query points. |
| [1pt/2pt] | Additive component of the mean-square error or squared bias bound associated with a stochastic first-order oracle. |
| Symbol | Description |
|---|---|
| Desired accuracy aimed by the algorithm. | |
| [1pt/2pt] (or ) | Step-size parameter. |
| [1pt/2pt] | Maximum allowable step size. |
| [1pt/2pt] | Finite-difference interval. |
| [1pt/2pt] | Trust-region radius at iteration . |
| [1pt/2pt] | Line-search sufficient-decrease parameter. |
| Symbol | Description |
|---|---|
| Subspace dimension, with . | |
| [1pt/2pt] | Matrix with orthonormal columns defining an -dimensional subspace. |
| [1pt/2pt] | Set of cardinality corresponding to the components of with largest absolute values. |
| [1pt/2pt] | Subset of on which a regularity condition is imposed, when used in this context. |
| [1pt/2pt] | Finite set of points queried by a multi-point oracle or finite-difference construction. |
| [1pt/2pt] | Condition number of a matrix . |
| First-Order Oracle Example | Inputs ( ) | Absolute Error ( ) | Relative Error ( ) |
| Forward Finite Differences (FFD) | Finite difference interval | ||
| Central Finite Differences (CFD) | Finite difference interval | ||
| Block-Coordinate | Subspace dimension | ||
| Orthogonal Projected Gradient | Orthonormal matrix | , | |
| Block-Coordinate and FFD | Finite difference interval Subspace dimension | ||
| Orthogonal Projected Gradient and FFD | Finite difference interval Orthonormal matrix | , |
| Oracle/Parameter | Assumption 4.4 (orthonormal) | Assumption 4.5 (independent) | |
| Oracle S-0.1 | |||
| Oracle S-0.2 | |||
| Oracle/Parameter | Assumption 4.4 (orthonormal) | Assumption 4.5 (independent) | |
| Oracle S-0.1 | |||
| Oracle S-0.2 | |||
| Oracle/Parameter | Assumption 4.4 (orthonormal) | |
| Oracle S-0.1 | ||
| Oracle S-0.2 | ||
| Oracle/Parameter | Assumption 4.4 (orthonormal) | |
| Oracle S-0.1 | ||
| Oracle S-0.2 | ||
| Setting | Assumptions | Convergence Neighborhood | iteration Complexity | |
| Minibatch stochastic gradient descent for ERM (Sec 4.4.1 ) | , ( 4.17 ), and minibatch size | |||
| KL | ||||
| PL | ||||
| Minibatch stochastic gradient descent for least squares (Sec 4.4.2 ) | , ( 4.7 ), and minibatch size | |||
| KL | ||||
| PL | ||||
| Setting | Assumptions | Convergence Neighborhood | iteration Complexity | |
| Minibatch gradient descent in ERM (Sec 4.4.1 ) | ( 4.17 ) and | |||
| KL | ||||
| PL | ||||
| Minibatch stochastic gradient descent for least squares (Sec 4.4.2 ) | ( 4.7 ) and | |||
| KL | ||||
| PL | ||||
| Setting | Assumptions | Convergence Neighborhood | iteration Complexity | |
| Randomized forward finite difference methods with Oracle S-0.1 (Sec 4.4.9 ) | ||||
| KL | ||||
| PL | ||||
| Randomized forward finite difference methods with Oracle S-0.2 (Sec 4.4.9 ) | ||||
| KL | ||||
| PL | ||||
Stochastic Optimization Convergence
Stochastic optimization convergence studies how noisy, sampled, or delayed updates approach solutions and how fast they do so.
See all 228 papers