Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients

1. Some comparisons with existing works are not fair.

$(a)$ The assumption that each $f_i$ is sampled from a Gaussian process and one has observations to $f_i+\mathcal{N}(0, \sigma^2)$ might be standard in some Bayesian optimization literature, but is not common in federated optimization. All existing algorithms that the paper compares do not make this assumption. Such an assumption is not verified in the real-world experiments this paper provides as well. The paper should review and compare existing works on federated Bayesian optimization that employ the same assumption. Moreover, under which condition does the average of functions sampled from the Gaussian process to be strongly-convex and convex?

$(b)$ The algorithm needs to invert a matrix that can be as large as $RT\times RT$ to compute $\nabla\mu$, which is much more computationally heavy than existing methods. The numerical results are only plotted against the number of rounds, which could be not fair as different algorithms have different operations in one single round.

$(c)$ The algorithm needs to communicate a vector of size at least $1/\epsilon^2$ at each round while existing zeroth-order methods only need to communicate two scalars, one for finite difference, the other one for the random seed to generate the random vector, when $Q=1$. As per Theorem 2, the total communication cost can be $MR=1/\epsilon^5$ when $F$ is convex. Does existing works have a worse communication cost $QR$ compared to that?

2. Some concerns regarding the theoretical results.

$(a)$ Is $\epsilon$ in Theorem 2 the same as the $\epsilon$ in Theorem 1? The $\epsilon$ convergence error is never defined in the paper. Does it mean $F-F^*$ for the convex case and $\Vert\nabla F\Vert^2$ for the nonconvex case?

$(b)$ Why is there only dependence in the dimension $d$ for the convex setting and no dependence in $d$ for the strongly-convex and nonconvex setting?

$(c)$ What does "$\rho<1$ likely to be satisfied" means? Does it hold with a high probability or require additional conditions? Will this affect the results in Theorem 2? Is this the reason why Theorem 2 only holds with constant probability?

$(d)$ The setting of $\gamma$ requires knowledge of $G$. How to estimate $G$ to run Algorithm 2?

3. Minor: It is not formal to start sentences with any conjunction like "so"; Why is it required in Algorithm 2 that "send $x_r$ first and then $w_r$"? Does the order matter? "urther" at the end of line 15 on page 7 should be "further"?

1. The problem formulated in Eq (1) is weird. Traditional federated learning optimizes the parameters $x$ in the domain of $\mathbb{R}^d$, and (Fang et al., 2022) optimizes this one as well. However, this paper optimizes the parameters in the domain of $[0, 1]^d$ and assumes $|f_i(x)| \leq 1$. The authors should explain why they formulate the problem different from the existing works.
2. Followed by the first point, the work should make use of proximal methods to restrain the parameter updates. However, the proposed algorithm allows the parameters $x$ updated in the domain of $\mathbb{R}^d$. This conflicts with the problem formulated in Eq. (1).
3. Theorem 2 targets to achieve $\epsilon$-convergence error. When $\epsilon$ approaches 0, $M$ will be very large, which will increase the communication costs, although the total communication rounds diminish.
4. The experiments study a 5/7-client federated learning, which is too small. I suggest the authors enlarge the scale, e.g., the number of clients should be 50/100.

• Computation Efficiency: I am not convinced that using historical information is the right alternative to additional queries when it comes to computation efficiency in a FL setting. Firstly given that the algorithm runs for $R$ rounds, client $i$ would need to store $x\_{r,t}^{(i)}$ for all $r \in [R], t \in [T]$ leading to a storage cost of $O(RTd)$ bits which can quickly become unsustainable, especially when $d$ is in the millions. Secondly, there is the cost of inverting the kernel matrix at every iteration. I would encourage authors to add a figure showing the total computation time/FLOPS used in FZooS vs FedZO for their experiments.

• Partial Client Participation: The authors do not account for partial client participation (which is common in FL settings) either in their analysis or experiments. In my understanding, partial client participation would exacerbate the error in the gradient approximation in FZooS. Firstly, each client would have fewer stored iterates since it participates less. Secondly, the distance between the stored iterates would also increase.

• Dependence on bounded heterogeneity assumption: I haven't gone through the proof carefully, but I don't see why the authors need a bounded heterogeneity assumption if they are applying gradient correction. For instance, Theorem 3 in SCAFFOLD does not need any bounded heterogeneity assumption. In fact, the entire motivation for gradient correction is to remove the dependence on $G$. Therefore, seeing a dependence on $G$ in Theorem 2 even after gradient correction seems a bit strange to me.

• Advantage of adaptive gradient correction: The advantage of the adaptive gradient correction needs more theoretical justification. In Section 5.2 it would be good to add the rates of convergence when standard gradient correction is used, as in the case of SCAFFOLD. Also, I would like to see more discussion on the benefit of using $\gamma_{r,t-1} = 1$ vs the choice of $\gamma_{r,t-1}$ proposed in Corollary 1.

• Linear Speedup and dependence on $d$ in Theorem 2: We do not see an effect of linear speedup in Theorem 2, i.e., $R$ does not reduce as $N$ increases. Also, why does the convex case have a dependence on $d$ but not the strongly convex and non-convex case? Additionally, can the dependence of $M$ on $d^2$ in the convex case be improved? Dependence on $d^2$ makes the communication cost similar to a second order method.