Stochastic two points method for deep model gradient free optimization

We greatly appreciate your constructive comments. Please see our responses below;

$*Weakness 1 and question 1,*$

We justified our algorithm in Section 3.4, Especially, our work provides the first theoretical guarantee of zeroth-order optimization for deterministic (L0, L1)-smooth nonconvex optimization. Please refer to the first point of our official comments. Our theoretical results serve as the source of inspiration for our algorithm development, and the resultant algorithm, informed by these findings, is anticipated to better capture the dynamics of optimizing deep models compared to previous algorithms based on L-smoothness assumptions. Empirically, the improvements in our algorithm manifest in significant convergence enhancements, achieving the same loss values with nearly half the training costs.

$*For the weakness 2,*$

The GA method in our experiment can be seen as the method in the referenced paper [1]. As far as our understanding goes, [1] is the first work to provide theoretical guarantees of the zeroth-order method for deterministic and stochastic nonsmooth nonconvex optimization under the (δ,ϵ)-Goldstein stationary optimality condition [2]. Notably, [1] gives the positive result that the zeroth-order method can be used in solving nonsmooth nonconvex optimization but doesn't propose a practical algorithm for performance improvement. The algorithm used in [1], SGFM, is akin to basic zeroth-order optimization algorithms such as those in earlier works [3].

$*Question 2 and Question 5,*$

There is no doubt that first-order methods are more commonly used in deep model problems. However, comparing first-order methods directly with zeroth-order optimization algorithms may not be suitable. Please refer to the second point of our official comments.

$*Question 3,*$

Options 1 ~ 4 represent the foundational algorithms for our theoretical guarantee analysis. Take option 1 and option 2 as an example to illustrate the differences, which assume the L-smoothness and require the knowledge of $L$ for option 2, however, the property of the function $L$ is unknown in practice. So, if we choose Option 2 due to its theoretical improvement over Option 1 to optimize our objectives, then we need to tune the learning rate to find the best practical learning rate. The situation is similar to the situation of commonly used SGD, which also suggests knowledge of $L$ and learning rate scheduler $1/\sqrt{k}$ but we basically need to tune the learning rate for each task accordingly and commonly choose the learning rate scheduler as cosine decay. So it is true that the theoretical results, while not always directly applicable to real-world conditions, inform practical algorithm development. Notably, such as Option 4 and our proposed AS2P, theatrical findings in Option 4 are expected to improve practical performance by incorporating them into our algorithm developments.

$*Question 4,*$

We highly appreciate your attention to ensuring a fair comparison of our experiment design. Due to space limitations, detailed experiment setup information is provided in Appendix D.1, as referenced in Section 4. Our effort to maintain fairness includes grid searches for hyperparameters (learning rate α and smoothing parameter ρ) for all baselines. Regarding f(x)-f*(x), for the smooth and non-convex optimization problems, the standard optimality condition is typically ϵ-first-order stationary point ( ||∇f(x)|| ≤ ϵ) given it is intractable to find global minima f*(x). We believe our improvements stem from deriving the algorithm under the relaxed smoothness assumption, which more closely captures deep model problems.

Thank you for pointing out the typo (Figure 3a); it has been corrected. Your attention to detail is invaluable.

[1] Lin T, Zheng Z, Jordan M. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems. 2022 Dec 6;35:26160-75.

[2] Zhang, Jingzhao, et al. "Complexity of finding stationary points of nonconvex nonsmooth functions." International Conference on Machine Learning. PMLR, 2020.

[3] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527–566, 2017.

$*Weakness 1 and question 1,*$

We appreciate your acknowledgment of our theoretical guarantee of zeroth-order optimization for deterministic (L0, L1)-smooth nonconvex optimization. Please refer to the first point of our official comments. Some existing works do provide empirical evidence to show the previous L-smoothness is often not satisfied in practical machine-learning problems [1, 2]. Notably, our work aligns with this trend and emphasizes the precision of (L0, L1)-smoothness in characterizing objective function landscapes, especially in training deep neural networks.

$*Weakness 2,*$

The works cited ([R1, R2]) differ significantly from ours in scope. Their experiments typically involve small problem dimensions, such as d = 32*32 for black-box attacks on CIFAR10 and a MLP with d = 2189 for non-differentiable metric optimization. In contrast, our experiments optimize ResNet (d = 11.7M) and even LLM (d = 13B). Implementing the baseline method Algorithm 1 in [R2] for our large-scale problems would be impractical, we have some comparisons below. (Note for simplification we use the baseline Algorithm 1 in [R2] instead of the proposed method in [R2] since they have similar performance.)

Under ResNet18, CIFAR10, batch size 1024, and same lab hardware,

AS2P completing 500 epoch training requires ~1h.

Algorithm 1 in [R2] taking one step of parameter updating requires ~ 195h (Finishing 1 epochs training, then ~476 days)

A quick answer to this large difference is that our method uses two time function queries to approximate the gradient while algorithm 1 in [R2] uses dimension d time function queries to approximate the gradient. However, the effectiveness of approximating gradients with two-symmetric perturbations is an ongoing research topic [3,4].

$*Weakness 3 and 4,*$

Comparing first-order methods directly with zeroth-order optimization algorithms may not be suitable. Please refer to the second point of our official comments. Additionally, we adopted the hardware budget for different methods from [3] to demonstrate the effectiveness of applying the zeroth-order method in LLM training, for instance, a A100 can fully fine-tune the largest OPT model with 2.7B parameters, FT-prefix up to 6.7B, and zeroth-order one can go up to fine-tune 30B model (Table 4 in [3], adopted in Section 4 of our work).

$*Question 2,*$

Apologies for any confusion. We introduced Definition 3.2 and Definition 3.3 at the beginning, not implying that both are satisfied simultaneously. Specifically, assumption 1 (Definition 3.2), is a popular one for deep model convergence analysis, and Theorem 3.1 satisfies assumption 1 only. Assumption 2 (Definition 3.3) is an emerging research topic, and Theorem 3.2 satisfies assumption 2 only. Those two assumptions lead to two distinct algorithms, mainly distinguished by the linear and non-linear correlations between step size α and |γ|. Those relationships inspire our practical algorithm developments.

$*Question 3,*$

We appreciate your careful examination in terms of our experiments and propose an important and concerning question for most readers we believe. To address concerns about practical query complexity, we designed Figure 1a and Figure 2a specifically to illustrate performance under the same number of queries (or training cost ratio, as mentioned in the figures). Additionally, we added the figures demonstrating the convergence w.r.t. number of queries during optimization as Figure 9 and Figure 10 in Appendix D.2. (See the uploaded revised PDF).

We greatly appreciate your constructive comments and are open to addressing any further concerns or questions you may have.

[1] Faw, Matthew, et al. "Beyond uniform smoothness: A stopped analysis of adaptive sgd." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

[2] Zhang, Bohang, et al. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.

[3] Malladi, Sadhika, et al. "Fine-Tuning Language Models with Just Forward Passes." arXiv preprint arXiv:2305.17333 (2023).

[4] Yue, Pengyun, et al. "Zeroth-order Optimization with Weak Dimension Dependency." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

Thank you for taking the time to read and review our paper. We sincerely appreciate your keen interest in the technical aspects of our work. Please see our responses below;

Weakness 1,

I believe there might be a misunderstanding regarding how stochastic optimization algorithms achieve optimality conditions. Taking results in two recent works as examples, such as Theorem 5 in [1] (zeroth-order optimization) and Theorem 2 in [2] (stochastic first-order optimization, mini-batch), the optimality conditions are achieved in expectation or with certain probabilities. It is well-established that having progress at each step for stochastic optimization algorithms is neither guaranteed nor necessary. Progressive monotonicity during optimization for stochastic optimization algorithms is rarely a focus, as seen in the golden baseline [3] referencing the GA method in our work. Therefore, the perceived "overestimation" is not a bottleneck for our algorithm. In comparison with the STP algorithm, we eliminate the non-updating component of STP, effectively saving one forward pass in a batch data forward pass. The practical performance of our proposed method surpasses standard methods with a 2× speed-up in training across most conducted tasks. Additionally, please refer to the first point of our official comments.

Weakness 2,

The mentioned distance $||x_{k} - x_{0}||$ is meaningful in convex problems and usually appears in the corresponding convergence analysis. To the best of our knowledge, there is no theoretical evidence to show the effectiveness of the distance in smooth non-convex problems.

Weakness 3,

3.1 As outlined in Section 4, it is important to note that 'GA is principally equivalent to MeZO as presented in Malladi et al. (2023), which reduces memory consumption with an implementation trick by performing twice forward passes sequentially instead of in parallel.' Hence, the GA method in our experiment aligns exactly with the MeZO method.

3.3 Comparing first-order methods directly with zeroth-order optimization algorithms may not be suitable. Please refer to the second point of our official comments.

3.2, 3.4, and 3.5 We have started working on the corresponding changes such as the additional table version result (Table 5 and Table 6 in Appendix D.2) and evaluation loss regarding the cifar datasets (Figure 1 in Appendix D.2). Please see the uploaded revised PDF. If you have any further concerns, we would like to address them as well. And, the code will be released upon acceptance.

[1] Lucchi, Aurelien, Antonio Orvieto, and Adamos Solomou. "On the second-order convergence properties of random search methods." Advances in Neural Information Processing Systems 34 (2021): 25633-25645.

[2] Wang, Bohan, et al. "Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

[3] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527–566, 2017.

Thank you for the constructive comments. The following addresses the weaknesses and questions.

We have worked on the corresponding changes, such as the additional table version result to “zoom in” the graphics (See Table 5 and Table 6 of Appendix D.2 in the revised PDF). If you have any further concerns, we would like to address them as well.

$*Weakness 1 and Question 1*$

The first-order methods and zeroth-order optimization algorithms have different use scenarios and may not be directly comparable. Please refer to the second point of our official comments below. $*Performance comparison with first-order method*$ Firstly, we conduct a simple experiment with the first-order method (Adam) under ResNet18 and CIFAR10, similar to Figure 1b.

Adam decreases the training loss from ~2.3 to ~0.0 in $**10**$ epochs.

AS2P decreases the training loss from ~2.3 to ~1.6 in $**500**$ epochs.

However, this huge gap is not evidence of negating zeroth-order optimization since zeroth-order optimization algorithms have distinct applications, especially in optimizing non-differentiable objectives and scenarios with constrained hardware budgets. In the context of LLM applications, our method aligns with this trend, exemplified by [1], showcasing up to 12× memory reduction compared to first-order methods. Our experiments, following the LLM training settings in [1], demonstrate nearly a 2× speed-up over baseline methods under the same hardware constraints, reinforcing the efficacy of zeroth-order optimization for fully fine-tuning LLMs within inference hardware budgets.

$*Weakness 2, Question 2, and Question 3,*$

We appreciate the suggestions regarding our experiment setup. The experiments in our original submission have encompassed a range of common deep models and datasets, including ResNet & CIFAR, and LLMs, which involve popular ResNet structure and attention structure. Across various settings and tasks, our proposed method consistently outperforms other baselines by a substantial margin.

Following your suggestion, we conducted additional experiments with VGG (architectures without skip connections), and the results show that the proposed algorithm consistently outperforms baselines by a large margin and requires 0.5$\times$ number of queries to reach specific loss values, which is summarized in Figure 8 of Appendix D.2 (See uploaded revised PDF). Though we do not have enough time to test ImageNet in this period, we believe our experiments covered common conditions and provided robust evidence of the method's advantages.

$*Question 4,*$

In our experiments, all mentioned methods consume the same amount of memory, ensuring consistency in comparison.

[1] Malladi, Sadhika, et al. "Fine-Tuning Language Models with Just Forward Passes." NeurIPS 2023.