Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
Translation in progress — untranslated text is omitted.
ZO-SVRG is a variance-reduced zeroth-order optimization algorithm for nonconvex optimization. The analysis finds that the zeroth-order gradient estimate no longer satisfies the unbiasedness assumption, and the two-point stochastic gradient estimator may introduce an additional O(1/b) error (b is the mini-batch size); two accelerated versions achieve the best known iteration rate for zeroth-order stochastic optimization. Experiments cover black-box chemical material classification and black-box deep neural network adversarial example generation, outperforming other state-of-the-art zeroth-order algorithms and balancing convergence speed and function query complexity.
- Zeroth-order (gradient-free) optimization is increasingly important in scenarios where only function values can be queried (such as black-box adversarial attacks and black-box materials classification), but existing ZO algorithms have high variance and slow convergence, and mostly target convex problems; the first-order variance reduction method SVRG relies on the unbiased gradient assumption and cannot be directly transferred to the ZO setting.
- The authors propose ZO-SVRG, combining SVRG's gradient mixing with a two-point stochastic gradient estimator, and provide a non-convex convergence analysis; for the O(1/b) additional error that appears in the analysis, they propose two accelerated variants, ZO-SVRG-Ave and ZO-SVRG-Coord, using Avg-RandGradEst and CoordGradEst.
- Theoretically, ZO-SVRG achieves O(d/T + δn/b), and the two variants improve it to O(d/T + δn/(b min{d,q})) and O(d/T), respectively. Experimentally, in materials classification, ZO-SVRG (b=40) has a test error of 11.18%, lower than ZO-SGD's 12.56%; in the black-box MNIST attack, ZO-SVRG-Ave (q=30) has an ℓ2 distortion of 3.67, lower than ZO-SGD's 5.22.
- The authors point out that the tightness of the error bound O(d/T + δn/b) has not been proven; they only conjecture that the dependence on T and b may be optimal; CoordGradEst-type methods require d times as many function queries, and performance degrades when the query budget is fixed. The experiments cover only two applications and one MNIST target model; the attack experiment uses only n=10 images and does not report the number of repetitions.
Related papers
- On the Limitation of Local Intrinsic Dimensionality for Characterizing the Subspaces of Adversarial ExamplesAnalysis / interpretabilityarXiv
Show 3 more papers
- The Space of Transferable Adversarial ExamplesAnalysis / interpretabilityarXiv