Zeroth-order (ZO) optimization has become a popular technique for solving
machine learning (ML) problems when first-order (FO) information is difficult
or impossible to obtain. However, the scalability of ZO optimization remains an
open problem: Its use has primarily been limited to relatively small-scale ML
problems, such as sample-wise adversarial attack generation. To our best
knowledge, no prior work has demonstrated the effectiveness of ZO optimization
in training deep neural networks (DNNs) without a significant decrease in
performance. To overcome this roadblock, we develop DeepZero, a principled ZO
deep learning (DL) framework that can scale ZO optimization to DNN training
from scratch through three primary innovations. First, we demonstrate the
advantages of coordinate-wise gradient estimation (CGE) over randomized
vector-wise gradient estimation in training accuracy and computational
efficiency. Second, we propose a sparsity-induced ZO training protocol that
extends the model pruning methodology using only finite differences to explore
and exploit the sparse DL prior in CGE. Third, we develop the methods of
feature reuse and forward parallelization to advance the practical
implementations of ZO training. Our extensive experiments show that DeepZero
achieves state-of-the-art (SOTA) accuracy on ResNet-20 trained on CIFAR-10,
approaching FO training performance for the first time. Furthermore, we show
the practical utility of DeepZero in applications of certified adversarial
defense and DL-based partial differential equation error correction, achieving
10-20% improvement over SOTA. We believe our results will inspire future
research on scalable ZO optimization and contribute to advancing DL with black
box.

DeepZero 是一个基于 Zeroth-order optimization 的深度学习框架，通过三个主要创新使得 ZO 优化可用于深度神经网络的训练，同时实现了与一阶优化相当的性能，其优点包括坐标梯度估计（CGE）在训练准确性和计算效率上的优势，以及利用模型剪枝方法扩展稀疏 DL 先验信息的 ZO 训练协议，并通过特征重用和前向并行化方法提高 ZO 训练的实际实施。