Abstract
Black-box optimization algorithms have been widely used in various machinelearning problems, including reinforcement learning and prompt fine-tuning.However, directly optimizing the training loss value, as commonly done inexisting black-box optimization methods, could lead to suboptimal model qualityand generalization performance. To address those problems in black-boxoptimization, we propose a novel Sharpness-Aware Black-box Optimization (SABO)algorithm, which applies a sharpness-aware minimization strategy to improve themodel generalization. Specifically, the proposed SABO method firstreparameterizes the objective function by its expectation over a Gaussiandistribution. Then it iteratively updates the parameterized distribution byapproximated stochastic gradients of the maximum objective value within a smallneighborhood around the current solution in the Gaussian distribution space.Theoretically, we prove the convergence rate and generalization bound of theproposed SABO algorithm. Empirically, extensive experiments on the black-boxprompt fine-tuning tasks demonstrate the effectiveness of the proposed SABOmethod in improving model generalization performance.