ZO-F2: Low-variance Fisher preconditioner via bilinear estimation for zeroth-order optimization

We propose a novel zeroth-order (ZO) optimization method, ZO-F2, where Fisher information matrix (FIM)-based preconditioners are estimated in a low-variance manner via bilinear forms. Using FIM rather than Hessian allows for a larger number of estimator samples by pairwise combinations of perturbations. We further propose a numerically stable whitening-based update rule for full-matrix preconditioners, even when the FIM estimate is ill-conditioned. We provide theoretical analyses on the variance, the whitening residual, and convergence under standard and reasonable assumptions. Experimental results on black-box training of diverse models from scratch support our proposals and demonstrate the superiority of ZO-F2 over existing methods in terms of accuracy and computational efficiency.