General Stability Analysis for Zeroth-Order Optimization Algorithms

Q1: It would be better if the author emphasized the new technique and idea used in this paper compared with the existing work by Nikolakakis et al. (2022).

A1: Thanks for your valuable comments. There exist key differences between (Nikolakakis et al. 2022) and our work, which are summarized as below:

1. Objective function: ZO-SGD with 2-point gradient estimator Vs. general ZO optimization. Nikolakakis et al. (2022) merely considered the generalization bound of ZO-SGD with 2-point gradient estimator. In this paper, we established a unified generalization analysis framework for ZO-GD, ZO-SGD as well as ZO-SVRG algorithms with 1-point / 2-point / coordinate-wise gradient estimators, which cover the mainstream estimators in existing zeroth-order algorithms.

2. Conditions: Gaussian distribution and non-convex condition Vs. general distribution and convex conditions. Nikolakakis et al. (2022) just considered the $u_k\sim\mathcal{N}\left(0, I_d\right)$ and non-convex loss function. In this paper, we derive the generalization bounds for more distributions (e.g.,uniform $u_k\sim \mathcal{U}\left(\sqrt{d+2} \mathbb{B}^d\right)$, $u_k\sim \mathcal{U}\big(\sqrt{d} \mathbb{S}^{d-1}\big)$ see Appendix E) and wider convexity conditions (strongly convex see Theorem 3,6,9 and Appendix G, H, I, convex see Theorem 3,6,9 and Appendix G,H, I and non-convex Theorem 1-9).

3. Filling the gap on the generalization bounds of ZO-SVRG. ZO-SVRG is a stage-wise algorithm with multiplication and summation from previous stages, which is totally different from ZO-SGD. To the best of our knowledge, this paper is the first endeavor to investigate the ZO-SVRG's generalization behavior. Meanwhile, our derived estimations of ZO-SGD $\Big({O}\big(T^{\frac{\beta C}{\beta C + 1}}/n\big)\Big)$ are tighter than the related results $\Big({O}\big(T/n\big)\Big)$ in Nikolakakis et al. 2022.

We have polished the comparisons with the related works and highlighted our contributions (see Appendix J).

Q2: In Figure 1(b), why did the generalization bound of ZO-SVRG decrease at the beginning?

A2: As shown in Figure 1(b), ZO-SVRG still lies in the fitting stage at the beginning. The training loss, testing loss as well as their difference are all declining due to random initialization.

To enrich the empirical evaluations, we have incorporated new results in the revision in Section 5 Numerical Experiments and Appendix B. Particularly, we have compared the generalization gaps of several estimators for zeroth-order algorithms (see Figure 2). Extended experiments verify our theoretical findings on generalization bounds.

Q1: Could your results be extended to the case where the objective function is not smooth? Are there any generalization bounds for this setting, even for first order algorithms?

A1: Thanks for your constructive comments. Indeed, there exist several works on non-smooth settings for first-order optimization, see e.g., [Ref1][Ref2]. However, these researches are limited to the convex or weakly convex settings. Moreover, the absence of smooth condition posed challenges on bounding the approximation error induced by zeroth-order optimization. Our analysis framework established here can not be extended to the non-smooth setting directly.
We are striving to address this issue in the future work.

We also added the related discussions in the revised paper, see new Remark 3 at Appendix J.

[Ref1] Bassily R, Feldman V, Guzmán C, et al. Stability of stochastic gradient descent on nonsmooth convex losses, NeurIPS, 2020.

[Ref2]Lei Y. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems, ICML, 2023.

Q1: Theoretical contributions, especially those stemming from the primary theoretical lemmas (Lemma 3 and 4), are incremental compared to prior works such as (Hardt et al., 2016) [2] and (Nikolakakis et al., 2022) [1].

A1: Thanks for your constructive comments. The zeroth-order optimization often is considered as an approximation of the first-order optimization. Naturally, it enjoys some similar strategy for error analysis. However, compared to prior works (e.g., Hardt et al., 2016 [Ref1], Nikolakakis et al., 2022 [Ref2]), there are key differences stated as below:

1. Unified generalization analysis framework for zeroth-order optimization. The existing analysis techniques (Hardt et al., 2016 [Ref1], Nikolakakis et al., 2022[Ref2]) mainly focus on ZO-SGD, and can not be applied to the other zeroth-order optimization approach (e.g., ZO-SVRG) directly. And our proof framework can encompass the generalization analysis of ZO-GD, ZO-SGD, and ZO-SVRG algorithms under various convexity conditions.

2. First stability analysis for zeroth-order SVRG algorithm. In contrast to SGD and GD algorithms, SVRG is a stagewise algorithm with new expansion factors among each stage and its stability-based generalization is unexplored for both first-order and zeroth-order settings. The update strategy of SVRG makes the existing theoretical techniques in [Ref1] and [Ref2] are not applicable directly. Here, we fill this theoretical gap by establishing stability-based error bounds for zeroth-order SVRG, where analysis technique are developed by the fine-grained error decomposition and estimations.

3. Diverse estimations for zeroth-order approximation. Nikolakakis et al. 2022 [Ref2] only considered the two-point estimator under Gaussian distribution. In contrast, this paper investigates one-point, two-point, and coordinate-wise estimators under different distributions and two difference forms. Theoretical results demonstrate that the smaller approximation error of these estimators are, the better generalization performance they get. The coordinate-wise estimators usually enjoy smaller approximation error. In addition, compared to first-order algorithms, coordinate-wise estimators can achieve similar generalization results under different convexity conditions. In particular, we have empirically verified that the zeroth-order algorithms with coordinate-wise estimator usually own the smallest generalization bounds compared with those using other estimators.

In summary, this paper provides a unified framework for generalization analysis of zeroth-order optimization and fills the theoretical gap on the stability-based generalization for SVRG algorithm. Based on your important comments, we have added the above illustrations in (Section 1: Introduction and Appendix J ) to highlight our work clearly.

[Ref1] M. Hardt et al., Train faster, generalize better: Stability of stochastic gradient descent, International conference on machine learning (ICML), 2016.

[Ref2] K. Nikolakakis et al., Black-box generalization: Stability of zeroth-order learning. Advances in Neural Information Processing Systems (NeurIPS), 2022.

Q2: The paper could benefit from more extensive numerical experiments and a more detailed implementation section.

A2: Thanks for your constructive comments. In the revised version, we have conducted more numerical experiments to verify the theoretical results, where the implementation details are also provided (see Section 5.1 Experimental Setups).

Firstly, in Section 5.2, we compare the generalization errors of different ZO algorithms associated with the same gradient estimators. Experimental results in Figure 1 show that ZO-SGD can achieve the competitive generalization performance compared with ZO-GD and ZO-SVRG.

Secondly, we compare the generalization errors of same ZO algorithms with different gradient estimators in Section 5.3 and Appendix B. Experimental results in Figure 2 demonstrate that ZO algorithms with coordinate-wise gradient estimator usually have the lowest generalization error.

Q3: What is the zeroth-order estimator used in the experiments?

A3: In the experiments, we employ the coordinate-wise estimator as the zeroth-order estimator. Implementing code can be found in the Supplementary Material, lines 45-59 of the algs.py file.

Q1: Only one question is that for the ZO-SGD, ZO-GD and ZO-SVRG with one-point and two-point gradient estimation, the authors only presented the results for the non-convex setting. Is there any theoretical results for the general convex and strongly convex settings? Like the results for the coordinate-wise gradient estimation. If the authors could add these theoretical results, it could make the theoretical contributions much more complete.

A1: Thanks for your constructive comments.convex and strongly convex conditions. Following your valuable suggestions, we have added the corresponding generalization bounds under convex and strongly convex conditions. For details, please refer to Appendix (F.1, F.2, G.1, G.2, H.2). We expect that the additional results can make our analysis more complete and improve its readability. Explicitly, the generalization bounds for ZO-SGD are $O(T/n^{1-\frac{c}{d^2 L C \sqrt{n}}})$ and $O(T/n^{1-\frac{c}{d^2 L C \sqrt{n}}})$ under one-point strongly convex condition and one-point convex conditions respectively. Meanwhile, generalization bounds for ZO-SGD are $O(T/n)$ under two-point strongly convex condition and $O(T/n)$ under two-point convex condition. For ZO-GD, we present the generalization bounds $O(T^{C}/n)$ under one-point strongly convex condition, $O(T^{C}/n)$ under one-point convex condition, $O(T^{\beta C}/n)$ under two-point strongly convex condition, and $O(T^{\beta C}/n)$ under two-point convex condition. Similarly, ZO-SVRG exhibits generalization bounds $O(S^{3 C}/n)$ under one-point strongly convex condition, $O(S^{3 C}/n)$ under one-point convex condition, $O(S^{3 \beta C}/n)$ under two-point strongly convex condition, and $O(S^{3\beta C}/n)$ under two-point convex condition. Indeed, there are some preliminary discussions in Remark 1 in the original version.

In essential, the convexity property has impact on the expansion coefficient $\eta$ involving in the generalization bounds of first-order optimization methods (see Appendix (Lemma 6)) . It is easy to deduce that $\eta_t=1-\frac{\alpha_t\beta\gamma}{\beta+\gamma}$ (strong convex), $\eta = 1$ (convex), and $\eta_t = 1 + \alpha_t\beta$ (non-convex). However, for the zeroth-order case, there often is additional increment induced by the procedures of one-point or two-point estimation (Ref1). We can verify $\eta^{\prime}_t=1+\alpha_t\left(\frac{L}{\mu}\mathbb{E}\|u\|+\beta\mathbb{E}\left[\|u\|^2\right]\right)$ (one-point convex condition), $\eta^{\prime}_t=1+\alpha_t\mu\beta\mathbb{E}\left[\|u\|^2\right]$ (two-point convex condition), $\eta^{\prime}_t=1-\frac{\alpha_t\beta\gamma}{\beta+\gamma}+\alpha_t\left(\frac{L}{\mu}\mathbb{E}\|u\|+\beta\mathbb{E}\left[\|u\|^2\right]\right)$ (one-point strongly convex condition), and $\eta^{\prime}=1-\frac{\alpha_t\beta\gamma}{\beta+\gamma}+\alpha_t\mu\beta\mathbb{E}\left[\|u\|^2\right]$ (two-point strongly convex condition).

Due to the additional increments (e.g., $\eta^{\prime}$ may exceed $1$), multiplication process. the additional results for the general convex and strongly convex settings are analogous to the existing error bounds under non-convex conditions (e.g., Theorems 1,2,4,5,7,8).

[Ref1] K. Nikolakakis et al., Black-box generalization: Stability of zeroth-order learning. Advances in Neural Information Processing Systems (NeurIPS), 2022.