PaperlayerView exact revision on arXiv

Source-linked AI summary

Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization

Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, Lisa Amini

arXiv:1805.10367v2cs.LGstat.ML

TL;DR

ZO optimization needs lower-variance methods for nonconvex problems, but ZO gradient estimates violate the unbiasedness assumption underlying SVRG. The paper develops and analyzes ZO-SVRG and two accelerated variants, showing improved iteration rates while exposing a mini-batch-dependent error and balancing convergence against function-query complexity.

  • Problem

    Existing ZO algorithms often have high gradient-estimate variance and are mainly designed for convex settings, while SVRG's unbiased-gradient assumption does not hold in the ZO case.

  • Method

    The paper proposes ZO-SVRG, integrating SVRG with ZO gradient estimators, plus two accelerated variants using reduced-variance estimators.

  • Results

    The accelerated variants achieve a convergence rate toward O(d/T), while experiments show the approaches balance iteration complexity and function-query complexity.

  • Takeaways & Limitations

    Variance reduction can improve nonconvex ZO optimization, but estimator choice and mini-batch size determine the trade-off between convergence speed and function-query cost.

  • Takeaways & Limitations

    ZO-SVRG with random gradient estimation can incur an O(1/b) error, and small mini-batches may leave convergence only to a neighborhood of a stationary point.

Abstract

from arXiv · show

As application demands for zeroth-order (gradient-free) optimization accelerate, the need for variance reduced and faster converging approaches is also intensifying. This paper addresses these challenges by presenting: a) a comprehensive theoretical analysis of variance reduced zeroth-order (ZO) optimization, b) a novel variance reduced ZO algorithm, called ZO-SVRG, and c) an experimental evaluation of our approach in the context of two compelling applications, black-box chemical material classification and generation of adversarial examples from black-box deep neural network models. Our theoretical analysis uncovers an essential difficulty in the analysis of ZO-SVRG: the unbiased assumption on gradient estimates no longer holds. We prove that compared to its first-order counterpart, ZO-SVRG with a two-point random gradient estimator could suffer an additional error of order $O(1/b)$, where $b$ is the mini-batch size. To mitigate this error, we propose two accelerated versions of ZO-SVRG utilizing variance reduced gradient estimators, which achieve the best rate known for ZO stochastic optimization (in terms of iterations). Our extensive experimental results show that our approaches outperform other state-of-the-art ZO algorithms, and strike a balance between the convergence rate and the function query complexity.

1 Introduction

ZO methods face high gradient-estimate variance and limited nonconvex applicability, motivating variance-reduced methods. The paper introduces ZO-SVRG and accelerated variants, analyzes their convergence, and evaluates their iteration–query trade-off.

  • ZO algorithms often have high gradient-estimate variance and are mainly designed for convex settings.
  • SVRG motivates variance reduction for ZO optimization, but its unbiased-gradient assumption does not hold for ZO estimators.
  • ZO-SVRG combines SVRG with ZO gradient estimators for nonconvex stochastic optimization.
  • O(1/T) convergence is accompanied by an additional correction term of order 1/b, where b is the mini-batch size.
  • Two accelerated ZO-SVRG variants use reduced-variance gradient estimators to approach O(d/T), the best known iteration bound for ZO stochastic optimization.
  • Experiments cover black-box chemical material classification and universal adversarial perturbation generation while examining iteration and function-query complexity.

2 Related work

Prior ZO work largely emphasizes convex optimization, while nonconvex methods remain comparatively under-studied. Existing nonconvex approaches include gradient, stochastic, distributed, asynchronous coordinate, and variance-reduced coordinate methods.

  • Two-point ZO methods are prominent, but most prior work is restricted to convex problems.
  • Convex ZO methods typically match first-order iteration complexity up to a small-degree polynomial in the problem dimension d.
  • Nonconvex ZO optimization uses stationarity to measure convergence and has been comparatively under-studied.
  • ZO-GD addresses deterministic nonconvex programming, while ZO-SGD provides a stochastic counterpart.
  • Distributed and asynchronous coordinate methods extend nonconvex ZO optimization to multi-agent and parallel settings.
  • ZO-SVRC improves coordinate-descent convergence, motivating a more general ZO-SVRG framework with different gradient estimators.

3 Preliminaries

The paper formulates nonconvex finite-sum optimization under smoothness and bounded stochastic-gradient variance assumptions. It reviews two-point random, averaged random, and coordinate-wise gradient estimators, including their bias, variance, and query-cost trade-offs.

  • The nonconvex finite-sum formulation covers machine-learning problems from generalized linear models to neural networks.
  • A1 assumes each cost function has L-Lipschitz continuous gradients.
  • A2 bounds stochastic-gradient variance by σ^2 and is milder than assuming bounded gradients.
  • ZO gradient estimation: The two-point random gradient estimator uses random directions and a smoothing parameter µ, but is biased relative to the true gradient.
  • ZO gradient estimation: Averaging multiple random-direction samples forms an average random gradient estimator.
  • ZO gradient estimation: CoordGradEst estimates every partial derivative with fixed basis directions, requiring d times more queries but improving iteration complexity.

4 ZO stochastic variance reduced gradient (ZO-SVRG)

ZO-SVRG adapts SVRG to zeroth-order gradient estimators for nonconvex optimization, but their bias invalidates SVRG’s usual unbiasedness assumption. The resulting convergence analysis identifies additional errors tied to smoothing, epoch settings, and mini-batch size.

  • Convergence analysis: ZO-SVRG has an O(1/T)-type convergence rate but also incurs smoothing and variance-related error terms absent from first-order SVRG.The terms identified are Lµ^2/(Tγ̄) and Sχ_m/(Tγ̄), with χ_m depending on algorithmic and problem parameters.
  • SVRG foundation: SVRG uses a reference full gradient at an auxiliary point to construct a modified stochastic gradient estimate.The mini-batch variant samples batches of size b and updates iterates across epochs.
  • ZO-SVRG construction: ZO-SVRG replaces SVRG’s first-order gradients with zeroth-order estimates for batch, mini-batch, and blended gradients.The estimates can use RandGradEst, Avg-RandGradEst, or CoordGradEst.
  • ZO-SVRG construction: The ZO-SVRG analysis must account for biased gradient estimates because the unbiasedness assumption used by SVRG does not hold in the ZO setting.This difference makes the apparently minor substitution analytically essential.
  • Convergence analysis: O(dσ^2/b) is an additional error in the bound for b < n, induced by the second-order moment of RandGradEst.The parameter δ_n also depends on sampling: it is 1 for i.i.d. sampling with replacement and for without-replacement batches with b < n, but 0 when b = n without replacement.
  • Convergence analysis: The mini-batch-dependent error disappears only when each mini-batch contains all n samples, reducing ZO-SVRG to ZO-GD.For b < n or i.i.d. sampling, δ_n = 1 and the additional O(δ_n/b) error remains.

5 Acceleration of ZO-SVRG

The paper accelerates ZO-SVRG by analyzing lower-variance gradient estimators. Averaging random directions reduces an error term, while coordinate-wise estimation eliminates it at the cost of more function queries.

  • Gradient-estimator variance: Random-direction estimators introduce additional squared-error terms, decreasing as the number of direction samples q increases.RandGradEst and Avg-RandGradEst incur additional errors within factors O(d) and O((q + d)/q) of ∥∇f(x)∥2, respectively.
  • Gradient-estimator variance: The shared estimator error is bounded by O(µ2L2d2), which becomes O(d/T) when µ is chosen as specified in the analysis.This error is common to the gradient estimators considered.
  • Avg-RandGradEst: Avg-RandGradEst reduces the ZO-SVRG error O(δn/b) by averaging q random direction samples.The convergence-rate improvement becomes limited when q ≥ d.
  • CoordGradEst: CoordGradEst eliminates the O(1/b) and O(1/(b min{d, q})) errors appearing in the other convergence bounds.This improvement follows from its lower variance, but it requires d times more function queries than RandGradEst.
  • Query-complexity trade-offs: Given T iterations, ZO-SVRG requires nS + bT gradient evaluations, while its averaged and coordinate variants require O(q(nS + bT)) and O(d(nS + bT)) queries.ZO-SVRG-Coord has the best convergence rate but high query complexity; ZO-SVRG and ZO-SVRG-Ave offer better trade-offs.

6 Applications and experiments

The experiments evaluate ZO-SVRG and its variants on black-box chemical material classification and universal adversarial perturbation generation. Results examine convergence, testing error, and the trade-off between iteration and function-query complexity.

  • Black-box binary classification: The chemical-material task classifies 1,000 crystalline materials using 145 features and DFT-simulator labels for conductor or insulator.
  • Black-box binary classification: Figure 2 compares ZO-SVRG, ZO-SVRG-Coord, and ZO-SVRG-Ave with ZO-SGD and ZO-SVRC using epochs and function queries.
  • Black-box binary classification: Increasing the mini-batch size reduces ZO-SVRG’s convergence error, while b ≤10 can lead to convergence near a critical point.
  • Black-box binary classification: ZO-SVRG with b = 40, ZO-SVRG-Coord, and ZO-SVRG-Ave converge faster in iterations than ZO-SGD and ZO-SVRC.
  • Generation of adversarial examples from black-box DNNs: The adversarial-example experiment uses a black-box MNIST DNN with 99.4% natural-example test accuracy and compares ZO-SGD against ZO-SVRG-Ave.
  • Generation of adversarial examples from black-box DNNs: To reach attack loss 7, ZO-SVRG-Ave requires roughly 30×, 77×, or 380× more function evaluations than ZO-SGD for q = 10, 20, or 30.

7 Conclusion

The conclusion presents ZO-SVRG as a nonconvex zeroth-order method with improved convergence analysis and accelerated variants. It also highlights the correction-term challenge and the trade-off between iteration and function-query complexity.

  • ZO-SVRG improves the ZO-SGD convergence rate from O(1/T) to O(1/T) while incurring an additional correction term of order O(1/b).
  • The correction term results from combining two-point random gradient estimators with SVRG.
  • Two accelerated ZO-SVRG variants use improved, reduced-variance gradient estimators to address this correction term.
  • The paper identifies a trade-off between iteration complexity and function-query complexity, with theoretical and experimental evidence supporting the approaches against state-of-the-art algorithms.

A.1 Zeroth-order (ZO) gradient estimators

The appendix characterizes the zeroth-order gradient estimators used in the analysis, including random-direction, averaged random-direction, and coordinate-wise constructions. It states their smoothing, moment, and variance-related properties under the paper’s assumptions.

  • Avg-RandGradEst averages independent random-vector estimates and has its own stated estimator properties and second-moment bound.
  • RandGradEst estimates a smoothed gradient using a random direction drawn uniformly from the unit Euclidean sphere.
  • The analysis establishes smoothness and moment properties for the smoothed function and the RandGradEst estimate.
  • CoordGradEst smooths each coordinate over a uniform interval and estimates partial derivatives using standard basis vectors.

A.2 Control variates

The control-variate analysis explains SVRG gradient blending as variance reduction that preserves the raw estimator’s expectation. It relates the variance reduction to the correlation between the raw estimate and the control variate.

  • SVRG gradient blending subtracts a control-variate correction from a raw gradient estimate while preserving its expectation.
  • The variance-minimizing coefficient is expressed using covariance traces of the raw estimate and control variate.
  • The blended estimate has lower variance when the control variate is positively correlated with the raw gradient estimate.

A.3 Proof of Proposition 1

The proposition proof analyzes a uniformly sampled mini-batch, distinguishes sampling with and without replacement, and bounds the relevant estimator term using a smoothing function.

  • The mini-batch I is sampled uniformly, with replacement, in Algorithm 2.
  • δn distinguishes sampling schemes: it equals 1 with replacement and I(b < n) without replacement.
  • The proof introduces the smoothing function fi,µ to bound the first term on the right-hand side.
  • The resulting inequalities are obtained by substitution and the stated lemmas and assumptions, completing the proof.

A.4 Proof of Theorem 1

The proof establishes the theorem through smoothness bounds, Lyapunov-function recursions, parameter conditions, and telescoping arguments. It also records the experimental settings and application data used elsewhere in the paper.

  • Proof setup: The analysis begins from L-smoothness and bounds involving random mini-batches and zeroth-order gradient-estimate directions.Expectations are taken over all random variables, with independence assumptions for mini-batches and random directions.
  • Lyapunov recursion: A Lyapunov function with positive coefficients is introduced for fµ, then repeatedly substituted into recursive inequalities.The proof simplifies these inequalities using bounds on inner products, gradient terms, and the coefficients c_k.
  • Convergence bound: Telescoping sums convert the recursive inequalities into an averaged-iterate bound using γ̄ = min_k γ_k and a uniformly random output iterate.The argument concludes with a theorem-level substitution after establishing γ̄ ≥ ηα_0, where α_0 is independent of T, d, and b.
  • Parameter conditions: The parameter analysis imposes conditions such as b ≥ 18 and ρ ≤ 1/518 to ensure valid coefficient and stepsize bounds.The proof tracks dominant terms in big-O notation while ignoring constants independent of the displayed problem parameters.
  • Experimental context: The experiments use m = 50, b = 10, q = 10, initial iterate x̃_0 = 0, and η = O(1/d); the materials dataset contains N = 1000 samples with d = 145 attributes.The dataset labels materials as conductors or insulators using DFT calculations, while the adversarial-image section compares ZO-SGD and ZO-SVRG examples.
Loading 1805.10367v2…