ProbFedZO: Probabilistic Step Size Adaptation for Federated Zeroth-Order Optimization

Zeroth-order optimization allows clients with forward-only access to participate in federated learning while uploading only a few scalars. However, it does not determine how far to move along the estimated direction. Fixed schedules cannot adapt to the current round, whereas line search tests each candidate through additional client communication. We propose two algorithms that select the step size on the server without further client contact. Both collect one shared batch of probe evaluations and fit a polynomial surrogate of the global objective. Under full participation, SurrFedZO applies an Armijo test to the surrogate and takes the largest passing step. Under partial participation, ProbFedZO corrects the test for the uncertainty caused by client sampling and certifies a step only when its predicted decrease exceeds that uncertainty. We bound the error of the surrogate by the probe radius and show that accepted steps decrease the global objective, deterministically for SurrFedZO and with a prescribed probability for ProbFedZO. On federated logistic regression and LoRA fine-tuning, both algorithms achieve competitive or improved risk at matched communication budgets, including settings where fixed and diminishing schedules stall.