DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence

We truly appreciate your insightful suggestions. We have provided a point-by-point reply to all your questions and hope we have successfully addressed all your concerns.

(Q1) In general the experimental designs and analysis are sound, which is partially discussed in Methods And Evaluation Criteria section. But dataset choice in hyper-parameter optimization lacks diversity since they are largely MNIST-related. And the treatment methods are limited, the paper only compares with 2 methods, FedZOO and FedRZO.

(R1) Thanks for your helpful suggestions. Addressing the trilevel zeroth order optimization problem in a distributed manner is significantly challenging, as even $*finding a feasible solution*$ in a linear trilevel optimization problem is NP-hard. This is the first work to explore solving trilevel zeroth-order optimization problems in a distributed manner while providing theoretical guarantees. We have conducted experiments on several more complex datasets, including CIFAR-10 and CIFAR-100 (using CNN models), as well as time series datasets such as MelbournePedestrian, Crop, and UWaveGestureLibraryAll from the UCR Archive [1], as suggested. Additionally, we have incorporated more state-of-the-art distributed single-level, bilevel, and trilevel optimization methods with zeroth-order estimators [2], including FedAvg+ZO [3], FEDNEST+ZO [4], ADBO+ZO [5], and AFTO+ZO [6], as baseline methods. The experimental results are presented in Table 3.1 below. Please note that combining distributed nested optimization methods with zeroth order estimators does not provide any theoretical guarantees; these methods are included only for comparative evaluation. As shown in Table 3.1, the proposed DTZO exhibits superior performance. This can be attributed to two key factors: (1) Compared to existing methods, the proposed DTZO is capable of effectively addressing higher-nested zeroth order optimization problems with non-asymptotic convergence guarantees. (2) The proposed nonlinear zeroth order cuts facilitate the development of a more refined cascaded polynomial relaxation.

Table 3.1 Experimental results on robust hyperparameter optimization.

Furthermore, we have conducted additional experiments to evaluate the proposed DTZO in three aspects:

• 1. Experimental results on another domain, i.e., continual learning, please see the results in (R1) to Reviewer 1qiE.
• 2. Ablation experiments, please refer to (R3) to Reviewer LX43 for details.
• 3. Experimental results when using larger LLMs, i.e., Qwen-2-7B and Llama-3.1-8B, please see (R2) to Reviewer LX43 for results.

(Q2) The paper has good novelty and solid theoretical foundations. But experimental study is limited as mentioned above. In general, it should be above borderline acceptance.

(R2) We appreciate your comments and support. Please refer to our modifications regarding the experimental study in (R1). We hope that our revisions have adequately addressed your concerns.

(Q3) In Assumption 4.4. there is a typo that word "Following" is mis-included in the cite hyperlink.

(R3) We sincerely appreciate your careful review and thank you for pointing it out. We have corrected it as suggested.

Reference

[1] The UCR Time Series Classification Archive, 2018

[2] A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications

[3] Communication-efficient learning of deep networks from decentralized data

[4] FEDNEST: Federated bilevel, minimax, and compositional optimization, ICML 2022

[5] Asynchronous Distributed Bilevel Optimization, ICLR 2023

[6] Provably Convergent Federated Trilevel Learning, AAAI 2024

We sincerely appreciate your insightful and valuable suggestions. We have provided a detailed point-by-point response to your questions below.

(Q1) A table that compares the latest progress with the related analysis.

(R1) This work is the first to explore solving the distributed TLL without relying on first-order information while providing theoretical guarantees. Per your suggestion, we have included a table comparing the non-asymptotic convergence results of the proposed DTZO with SOTA distributed nested optimization methods, under the assumption/setting where first-order information is either available (FO) or unavailable (ZO). Please note that ZO is more general and challenging than FO.

Table 2.1

(Q2) More models and datasets, i.e. LLAMA-7B.

(R2) Additional experiments are conducted on (1) more datasets and models in robust hyperparameter optimization, and (2) larger LLMs in black-box TLL. Specifically,

(1) Due to character limitations, please refer to (R1) to Reviewer urFe.

(2) Experiments are conducted using larger LLMs, i.e., Qwen-2-7B and LLAMA-3.1-8B, and the results are shown in Table 2.2.

Table 2.2

(Q3) Ablation experiments.

(R3) Ablation Study. To analyze DTZO’s performance improvements, we conduct an ablation study comparing DTZO against its variants: DTZO(-) and DBZO. DTZO(-) replaces the proposed nonlinear cuts in DTZO with linear cuts, while DBZO removes cascaded polynomial approximation, using only single-layer polynomial approximation. It is seen from Table 2.2 that DTZO outperforms all variants, demonstrating the benefits of cascaded polynomial approximation and nonlinear ZO cuts. In addition, we also compare DTZO with a variant of DTZO without removing inactive cuts. It is seen from Figure 3 in page 33 that removing inactive cuts greatly enhances DTZO’s efficiency, underscoring the importance of this step.

Table 2.3

(Q4) Core theoretical contribution.

(R4) Existing works focus on single-level and bilevel ZO, while tackling the trilevel ZO is under-explored and significantly more challenging (even finding a feasible solution in TLL is NP-hard). This work marks an initial step in solving TLL without first-order information. A key theoretical contribution is the first trilevel ZO framework and first non-asymptotic convergence guarantee (e.g., iteration and communication complexity) for trilevel ZO, aligning with DTZO’s superior performance in experiments, i.e., DTZO outperforms SOTA methods by handling higher-nested ZO with theoretical guarantees. Another key theoretical contribution is the construction of the first theoretically guaranteed ZO cuts in nested optimization, enabling cascaded polynomial relaxation without gradients. The proposed ZO cut is also the first nonlinear cut in nested optimization, offering better approximations for complex functions than linear cut. This advancement can also be observed in ablation study, where DTZO outperforms its variant without ZO cuts.

(Q5) More detailed records (communication bits, training time).

(R5) Compared to single-level and bilevel optimization, solving TLL inherently demands higher complexity. This is because 1) TLL has higher-nested structure, finding a feasible solution in TLL requires solving a bilevel optimization problem; 2) it involves more optimization variables than bilevel and single-level optimization. Per your suggestions, we provide a comparison of communication complexity and training time between DTZO and SOTA distributed TLL method. As shown in Table 2.4, DTZO achieves superior performance due to its non-asymptotic convergence guarantees and simplified optimization procedure.

Table 2.4

$^1$Because this method lacks non-asymptotic convergence guarantee.

We truly appreciate your insightful and valuable suggestions. We have provided a detailed response addressing each of the questions you raised.

(Q1) Experiments on another domain and ablation study.

(R1) This work is the first to investigate solving the distributed TLL problem without relying on first-order (FO) information while providing theoretical guarantees. The proposed DTZO exhibits high adaptability which can be applied to a broader range of TLL problems, please refer to (R5) for details. To address your concerns, we have incorporated additional experimental results on another domain, i.e., continual learning, along with ablation study, as detailed below.

• Continual Learning. In the experiment, the adversarial architecture-based continual learning task is considered, which can be formulated as a TLL problem.

$

\min&{\sum_j\sum_{(x,y)\in D_j ^B}\frac{{L([\theta_1,\theta_2],x,y)}}{|D_j^B|}}\\ s.t.&\theta_1=\mathop{\arg \min}\limits_{\theta_1'}\sum_j\sum_{(x,y)\in D_j^A}\frac{L(\theta_1',x,y, P_1)}{|D_j^A|}\\ &s.t.P_1=\mathop{\arg \max}\limits_{P_1'} \sum_j \sum_{(x,y) \in D_j^A}\frac{L(\theta _1',x,y,P_1')}{|D_j^A|}

$

The results are reported in Table 1.1. It is seen that the proposed DTZO outperforms SOTA methods because: 1) DTZO is capable of solving higher-nested zeroth order (ZO) problems; 2) the proposed nonlinear ZO cut has superior approximation performance.

• Ablation study. Due to character limitations, please refer to (R3) to Reviewer LX43.

Table 1.1

(Q2) Additional datasets and baseline methods.

(R2) Due to character limitations, please see (R1) to Reviewer urFe.

(Q3) Explanation to $T_1$.

(R3) In the proposed framework, $T_1<\infty$ is a constant that can be flexibly adjusted based on specific requirements. Specifically, if the distributed system has sufficient computational and communication resources, a relatively larger $T_1$ (but still finite) can be chosen to achieve a better cascaded polynomial relaxation. Conversely, if the resources are limited, a smaller $T_1$ can be set to reduce the iteration and communication complexity.

(Q4) No discussion of computational limitations. Dataset and benchmark size is limited.

(R4) Solving TLL is highly challenging, as even $*finding a feasible solution*$ for a linear TLL is NP-hard. The proposed DTZO is a distributed optimization method, making it well-suited for large-scale learning tasks due to the scalability of distributed algorithms. It decomposes large tasks into subproblems assigned to individual workers, enabling efficient problem-solving. Moreover, even in scenarios with limited computational resources, DTZO can effectively handle them due to its flexibility. By setting a smaller $T_1$, the communication and iteration complexities are reduced. Experimental results on more datasets and larger models are reported in (R2) to Reviewer LX43 and (R1) to Reviewer urFe.

(Q5) Trade-off between gradient-free vs. gradient-based method.

(R5) The proposed framework is highly adaptable, accommodating both fully gradient-unavailable TLL and cases with partial gradient access with minimal modifications. We further discuss and compare the trade-off below.

1. Gradients at 1-level are available. In this case, Eq. (16–18) can be replaced with gradient descent steps in DTZO, which introduce less noise per iteration and improve convergence rate ($O(1/\epsilon)$). However, Eq. (16–18) do not rely on gradients, making them more applicable to scenarios where gradients are unavailable. This represents a trade-off between convergence efficiency and applicability, which can be flexibly adjusted within DTZO.

2. Gradients at 2-level are available. In this case, the outer layer ZO cut can be replaced by FO cut: $\nabla\phi_{out}{(\\{{x_{2,j}^t}\\},\\{{x_{3,j}^t}\\},\\{z_i^t\\})^{\top}}[\\{x_{2,j}-x_{2,j}^t\\};\\{x_{3,j}-x_{3,j}^t\\};\\{z_i-z_i^t\\}]+\phi_{out}(\\{{x_{2,j}^t}\\},\\{{x_{3,j}^t}\\},\\{z_i^t\\})\le L/2(\sum_{i=2}^3\sum_j||x_{i,j}-x_{i,j}^t||^2+\sum_i||z_i-z_i^t||^2)+\varepsilon_{out}$. Since FO cut is generated based on gradients, it introduces less noise in generation process and can get a superior polynomial relaxation. In contrast, ZO cut exhibits broader applicability, as its generation does not rely on gradients. This represents a trade-off between polynomial relaxation and applicability, which can be effectively controlled in DTZO.

3. Gradients at 3-level are available. Similar to 2), there exists a trade-off between inner layer polynomial relaxation and applicability.

(Q6) Some ZO references are missing.

(R6) More discussion on ZO will be added as Appendix J.3. We are happy to include any references the reviewer may suggest.