Source-linked AI summary
A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization
Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, Katya Scheinberg
TL;DR
The paper asks how derivative-free methods can approximate unavailable gradients of bounded noisy functions accurately enough for optimization. It derives error and sampling conditions for finite differences, interpolation, and randomized smoothing methods, then evaluates them theoretically and numerically. The main result is that smoothing can operate with fewer samples but generally needs substantially more samples to match interpolation accuracy, while the required convergence condition is achievable deterministically or with high probability depending on the method.
Problem
The paper addresses the lack of theoretical comparisons connecting gradient-estimate accuracy for noisy derivative-free methods with downstream optimization performance.
Method
The paper derives gradient-error and sampling-radius bounds for finite differences, linear interpolation, Gaussian smoothing, and sphere smoothing under bounded noise, and tests the estimates numerically with line-search DFO.
Results
Smoothing methods can use N≪n samples, but generally produce less accurate estimates than interpolation and may require significantly more samples to achieve comparable accuracy.
Takeaways & Limitations
The convergence norm condition needed by line-search methods is achievable either deterministically or with sufficiently high probability, depending on the gradient approximation method.
Takeaways & Limitations
The analysis assumes a known uniform noise bound and Lipschitz-continuous true gradients, and randomized smoothing guarantees depend on probability parameters such as δ.
Abstract
from arXiv · showhide
In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing and smoothing on a sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we use the results in [Berahas et al., 2019] and show how each method can satisfy the sufficient conditions, possibly only with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm.
1 Introduction
The paper compares derivative-free gradient approximations for bounded noisy functions, focusing on their accuracy, sampling requirements, and use in optimization. It establishes conditions under which deterministic and randomized methods support convergence, finding that smoothing methods generally require more samples for interpolation-level accuracy.
- Problem setting: The analysis targets f(x)=φ(x)+ϵ(x), where φ has an unavailable Lipschitz-continuous gradient and the noise is uniformly bounded by a known ϵ_f.The noise may be deterministic, stochastic, or adversarial; the analysis uses the worst-case bound.
- Methods: The study compares finite differences, linear interpolation, Gaussian smoothing, and sphere smoothing by sample count, directions, radius, and gradient-construction procedure.All methods use function values near the current point to construct a gradient estimate.
- Theory: The paper derives gradient-error bounds and sampling-radius choices that ensure sufficiently accurate estimates for fixed-step, adaptive-step, stochastic, or line-search methods.Finite-difference and interpolation bounds support deterministic convergence arguments, while randomized bounds support high-probability guarantees.
- Results: Smoothing methods can use N≪n samples, but their estimates generally have lower accuracy than interpolation estimates and may therefore yield slower optimization convergence.To obtain interpolation-comparable accuracy, smoothing methods can require significantly more samples; simulations support this theoretical comparison.
- Theory: The norm condition can be achieved deterministically for some methods or with probability 1−δ for smoothing methods, enabling line-search convergence analyses.The condition requires the estimated gradient to be sufficiently close to the true gradient and therefore to provide a descent direction.
- Results: For smoothing methods, the necessary sample count scales linearly with n, whereas accurate lower bounds are harder to derive and their δ dependence may be pessimistic.The Gaussian-smoothing lower-bound dependence on δ is identified as potentially arising from Chebyshev’s inequality, while sphere smoothing has better δ dependence but still linear n scaling.
2 Gradient Approximations and Sampling
The paper derives accuracy and sampling conditions for finite-difference, interpolation, Gaussian-smoothing, and sphere-smoothing gradient approximations. Deterministic methods and randomized smoothing methods have linear dimension dependence, but smoothing bounds can require larger constants or probability-dependent sample sizes.
- All methods are analyzed through conditions ensuring the gradient approximation satisfies the sufficient convergence bound (1.3).The analysis covers sampling sets, approximation construction, sample counts, and sampling radii.
- Gaussian smoothing: Gaussian-smoothed gradient estimates have variance bounds and achieve relative accuracy with probability 1 − δ when N and σ satisfy derived conditions.The results include both upper-bound conditions and probability-dependent guarantees.
- Gaussian smoothing: Gaussian smoothing requires sample counts larger than the fixed n evaluations used by finite differences and interpolation, with a strong dependence on δ.The paper notes that the δ dependence may be pessimistic because it comes from Chebyshev’s inequality.
- Gaussian smoothing: N > (1−2δ)⁄θ^2 (n + 1) is necessary for Gaussian smoothing to guarantee the target relative-error probability, establishing linear scaling in n.Numerical experiments further indicate that practical requirements can be closer to the upper bound than the theoretical lower bound suggests.
- Smoothing on a sphere: Sphere smoothing improves the dependence of the sample count on δ through Bernstein’s inequality, while retaining linear dependence on n.The paper derives high-probability approximation bounds for both sphere-smoothed estimators considered.
- Summary of results: Across methods, large-dimensional sample-count bounds have the same order in n, but deterministic methods can have substantially smaller constants than smoothing methods.The sampling-radius bounds are described as comparable across deterministic and smoothing approaches.
3 Numerical Results
Numerical experiments evaluate gradient-approximation accuracy across noise levels, sampling radii, dimensions, sample counts, and benchmark optimization tasks. The results broadly support the theory: deterministic methods often provide more accurate estimates, while noise makes sampling-radius selection important and randomized directions can help optimization escape local extrema.
- 3.1 Gradient Approximation Accuracy: Experiments compare finite differences, linear interpolation, Gaussian smoothing, and sphere smoothing using relative gradient-approximation error.The synthetic tests vary dimension, Lipschitz constants, sampling radius, sample count, and noise.
- 3.1 Gradient Approximation Accuracy: log10 θ < log10 1/2 ≈ −0.301 is the convergence-relevant accuracy threshold for gradient estimates.This corresponds to θ < 1/2 with sufficiently high probability.
- 3.1 Gradient Approximation Accuracy: In noise-free tests, reducing the sampling radius improves deterministic and interpolation approximations, while randomized methods show little radius dependence.The randomized approximations are significantly worse than deterministic methods in this regime.
- 3.1 Gradient Approximation Accuracy: In noisy tests, smaller sampling radii do not necessarily improve accuracy because the error bound contains terms that decrease and increase with σ.The experiments use noise levels ϵf ∈ {0, 10−4, 10−2} and show that σ must be selected carefully.
- 3.1 Gradient Approximation Accuracy: More than 4n samples are needed for smoothing methods to reliably achieve θ < 1/2, while FFD, CFD, and LI generally have smaller relative errors.This finding is reported for the noise-free Schittkowski experiments over 5330 points.
- 3.2 Performance of Line Search DFO Algorithm with Different Gradient Approximations: On line-search DFO benchmarks, interpolation outperforms GSG, and line search improves performance over manually tuned step sizes.Random orthonormal interpolation directions can also help avoid local maxima compared with deterministic finite differences.
4 Final Remarks
The paper concludes that several derivative-free gradient approximations can provide comparable estimates under reasonable bounded-noise assumptions, with sample and radius conditions supporting favorable convergence.
- 4 Final Remarks: Finite differences, linear interpolation, Gaussian smoothing, and sphere smoothing can provide comparable gradient estimates under reasonable assumptions.The analysis uses function values with bounded noise.
- 4 Final Remarks: The paper derives sample-count and sampling-radius bounds supporting favorable convergence for line-search and fixed-step descent methods.The bounds are developed for the considered derivative-free gradient-approximation techniques.
A.2 Derivation of (2.11)
The derivation applies the intermediate value theorem to represent perturbed function differences using intermediate points within the sampling radius.
- A.2 Derivation of (2.11): The intermediate value theorem introduces ξ1 and ξ2 between 0 and σ to express the relevant function differences.The derivation requires 0 ≤ ξ1 ≤ σ and 0 ≤ ξ2 ≤ σ.
A.3 Derivation of (2.18)
The derivation evaluates Gaussian directional moments and assembles them into matrix identities used in the approximation analysis.
- A.3 Derivation of (2.18): For Gaussian u, the matrix expectation involving (a⊺u)^2uu⊺ is evaluated componentwise and rewritten in matrix form.The diagonal calculation yields the identity a⊺aI + 2aa⊺.
- A.3 Derivation of (2.18): Oddness under the even Gaussian density makes the relevant expectation vanish for the stated odd integrand.The argument uses symmetry of the standard Gaussian distribution.
- A.3 Derivation of (2.18): Even-order Gaussian radial moments are expressed through moments of a chi-distributed variable.The derivation relates the quantity to the (k+2)nd chi moment and Q_k/2 for even k.
A.5 Derivation of (2.29)
The derivation evaluates a sum of products of four vectors by grouping terms according to index-equality patterns and simplifying the resulting inner-product expressions.
- The quantity is represented as a sum of N terms, each formed from the product of four vectors.
- Q is defined as the product of inner products formed from two pairs among four vectors in R^n.
- Terms with distinct indices are independent, so the calculation only requires cases defined by repeated-index conditions.
- One case has i = j ≠ k = l and occurs when N > 1; two other pairings, i = k ≠ j = l and i = l ≠ j = k, are treated as equivalent.
- After evaluating the grouped cases, the expression simplifies to N(N − 1)(n^2 + 4n + 7)(a⊺a)^2 + N(3n^2 + 20n + 37)(a⊺a)^2.
A.6 Derivation of (2.35)
The derivation uses the intermediate value theorem to represent the relevant function-value differences through intermediate points within the sampling interval.
- The function-value difference is expressed using points with 0 ≤ ξ1 ≤ σ and 0 ≤ ξ2 ≤ σ, obtained by the intermediate value theorem.
A.8 Derivation of (2.39)
The derivation uses the radial-direction decomposition of an iid Gaussian vector to establish independence between its norm and normalized direction, then applies this to homogeneous polynomials.
- An iid Gaussian vector v is decomposed as v = ∥v∥u, where its norm and normalized direction u are independent.
- This independence implies a corresponding property for any homogeneous polynomial in the entries of u.
- The vanishing second equality in (2.39) follows by the same argument used for the second equality in (2.18).
B Additional Details: RL Experiments
The RL experiments optimize policy-network parameters through black-box rewards, using low-displacement-rank feedforward policies and specified sampling, optimization, line-search, and orthogonalization settings.
- The black-box function maps policy parameters to the total reward obtained by applying the policy in an environment.
- Policies use fully connected feedforward networks with two hidden layers of 41 tanh neurons, with connection matrices encoded by low-displacement-rank neural networks.
- All experiments use σ = 0.1; non-line-search runs use Adam with α = 0.01, while line-search runs update α using the Armijo condition with c1 = 0.2 and τ = 0.3.
- Orthogonal samples are constructed by Gram-Schmidt orthogonalization of random Gaussian matrices, while structured alternatives such as random Hadamard matrices are noted as possible biased substitutes.
- Each environment-method combination is evaluated in k = 3 experiments using different random seeds.