- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies step-size adaptation in federated zeroth-order optimization. The server broadcasts shared probe points, and each client uploads only scalar changes of its local objective evaluated at these probes. The server fits a polynomial surrogate model from these scalar responses and selects both the update direction and the step size on the server side using an Armijo condition applied to the surrogate. Under full participation, SurrFedZO directly applies the Armijo test to the surrogate; under partial participation, ProbFedZO further incorporates a correction for client sampling uncertainty, certifying a step only when the predicted decrease exceeds the estimated uncertainty. The paper also provides bounds on surrogate model error, probabilistic descent guarantees under sampling uncertainty, and experiments on logistic regression and LoRA fine-tuning.
Critical strengths
1.Reusing the probe responses already collected to construct a surrogate and selecting the step size on the server is a sensible communication-efficient idea.
2.ProbFedZO propagates the client-sampling covariance to the surrogate gradient and Armijo residual, and certifies candidate steps using an uncertainty-corrected condition. This design is more suitable for the partial-participation setting than plain line search or fixed step sizes.
3.Experiments include two-dimensional nonconvex functions, federated logistic regression, and LoRA fine-tuning of OPT-125M and Qwen3-0.6B-base, together with several ablations, indicating substantial experimental effort.
Critical weaknesses
1.Key symbols such as , the kernel degree , and the candidate step-size grid are not adequately explained in the main text. The reason why the direction lies in rather than and its relation to the subspace need to be clarified. Too much content is deferred to Appendix Table 1, hurting the self-containedness of the main text.
2.Theorem 1 directly relies on an “Assumption 5” that is not stated in the main text. The smoothness assumptions in Lemma 1, the poisedness condition on the probes, etc., are also not fully presented. Readers cannot easily judge the applicability of the theorems without consulting the appendix.
3.The statement of Proposition 1 in the main text is phrased using the estimated covariance, but the appendix proof actually uses the population covariance for the uncertainty scale. The algorithm uses in place of ; whether the uniform probability bound remains valid after this substitution is not fully proved in the paper. In addition, the theory requires to obtain a positive probability guarantee, whereas the experiments use under the “uninflated plug-in rule.” The theoretical status of this choice needs to be clearly stated.
Questions for authors
1.Some minor questions: (1) why not ?; (2) why not in equstion 3?;
2.How is generated or updated? Is the direction in subspace coordinates, with the actual update being ? Please clarify at the first occurrence in the main text.
3.How is chosen in the experiments? The theory requires , but the experiments use . Is this choice heuristic or formally calibrated?
4.How is the candidate grid chosen?
5.How is the “matched communication budget” defined? How much communication is consumed by the fixed step size, diminishing step size, and distributed line search baselines? Are local evaluation counts and uploaded scalar counts unified into the same budget?
2 comments
Thanks for the authors' detailed response. It addresses my concern. I will increase my score.
Reply to Reviewer S7uc
We sincerely thank the reviewer for the close reading of both the main text and the proofs. Your comments on Proposition 1 in particular helped us state our guarantees more accurately.
W1, Q2. Notation and self-containedness. Thank you, we agree that too much was left to the appendix. The items you listed are now defined in the main text at first use, and your reading of V_t and d_t is correct:
W2. Assumptions behind Lemma 1 and Theorem 1. Thank you for pointing this out. Sec. 5 now opens with an "Assumptions" paragraph: (A1) exact responses, C^p smoothness with a Lipschitz p-th derivative, and a poised probe set; (A2) uniform client sampling; (A3) a lower bound on F and L-smoothness. Lemma 1 and Theorem 1 now cite (A1) directly.
W3, Q3. Estimated versus population covariance, and the choice of κ. We are grateful for this observation, which is correct: the statement of Prop. 1 was imprecise. It is now stated explicitly for the population covariance, and a new Remark 1 separates what is proved from what is heuristic:
So the experiments use a heuristic calibration (Cantelli's, for a single candidate fixed before sampling), and we now say so in the main text and list its certification as open. Because it is a heuristic, we measure its reliability directly: the fraction of certified steps that decrease the true objective rises from 0.77–0.89 at ρ = 0.1 to 0.86–0.98 at ρ = 0.9 across three datasets (Table 3).
Q1. Notation in Eq. (3). Thank you for catching this. Eq. (3) is written with S and m so that it serves both algorithms; under full participation S = {1, …, N} and m = N. This is now stated right after the equation.
Q4. Candidate grid. The grid is given in the table above. Every candidate is tested on the surrogate, so the grid costs only server arithmetic and no client evaluations.
Q5. Matched communication budget. Thank you for asking, as this was not defined clearly. The budget is a cap on the total bits uploaded by clients, at 32 bits per scalar; downlink is not counted because V_t and the probes come from a shared seed. Every method runs until it reaches the same total. Per round, constant and diminishing steps and our rules upload mK scalars, while the line search uploads mK + mJ (J ≤ 8) and so completes fewer rounds. Each uploaded scalar corresponds to one local evaluation (Sec. 6, App. E.11, Table 9).
We thank the reviewer again for the detailed and helpful feedback, and we would be glad to clarify any remaining point.