A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization

Thank you for your thoughtful review. We highlight our technical contribution and new insights as follows:

1. To the best of our knowledge, the proposed POEM is the first parameter-free algorithm for zeroth-order stochastic optimization, which is also mentioned by all other reviewers.

2. Our method can achieve the near-optimal convergence with the smoothing parameter $\mu_t={\mathcal O}(\sqrt{d/t})$, which is larger than the counterparts in existing works such as $\mu_t={\mathcal O}(\sqrt{d/T})$ (Duchi et al., 2015) and $\mu_{2t}={\mathcal O}(1/(d^2t^2))$ (Shamir, 2017). This is a new observation which improves the numerical stability in the step of finite difference.

3. For the unbounded domain case, we establish the lower bound (Theorem 5.6) to show that achieving an ideal parameter-free stochastic zeroth-order algorithm is impossible, i.e., the algorithm cannot attain the near-optimal SZO complexity with only logarithmic dependence on problem parameters. Our lower bound construction considers the dependence on $d$ in the complexity (construct the $d$ dimensional function), which is more challenging than the lower bound for the first-order method that depends on the 1-dimensional function (Khaled & Jin, 2024).

Q1 The empirical evaluation is limited to a few datasets and could be extended to cover more diverse and large-scale scenarios.

A1 Thank you for your suggestion. We have addressed your comment by including the experiments on the higher-dimensional datasets "qsar" ($d=1,024$, $n=1,687$) from UCI machine learning repository and "gisette" ($d=6,000$, $n=5,000$) from LIBSVM repository. Please see link https://anonymous.4open.science/api/repo/a-5532/file/response-dAwi.pdf?v=78140e95 for the experimental results. We can observe that our POEM also performs better than baselines.

Q2 Can you elaborate on the challenges and potential modifications required to extend POEM to nonconvex optimization problems?

A2 Thank you for your question. It is still unclear how to extend POEM to nonconvex optimization problem. The convexity plays a crucial role in our theoretical analysis:

1. In Equation (8), we bound the function value gap by using Jensen’s inequality, which relies on the convexity of $f(\cdot)$.

2. In Equation (9) and the poof of Lemma C.3, we use the first-order condition in Lemma A.1 which requires the convexity of the smooth surrogate $f_\mu(\cdot)$, and the convexity of $f_\mu(\cdot)$ comes from the convexity of the objective $f$ (see Lemma 2.8).

For the nonconvex problem, it is possible to introduce the online-to-nonconvex conversion [1-3] into our framework to attain the nearly-tight upper bound. However, it seems not to be a direct extension. We believe this is a good future direction.

References

[1] Ashok Cutkosky, Harsh Mehta, Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. ICML 2023.

[2] Guy Kornowski, Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. JMLR 2024.

[3] Kwangjun Ahn, Gagik Magakyan, Ashok Cutkosky. General framework for online-to-nonconvex conversion: schedule-free SGD is also effective for nonconvex optimization. arXiv:2411.07061, 2024

Q3 What is the computational cost associated with computing the adaptive step size? The computation of the adaptive step size seems need a copy of initial parameters weight. How does this overhead compare with that of standard zeroth-order methods in large-scale applications and do you think there exists a memory-efficient way for the implementation?

A3 Thanks for your insightful question. Each iteration of POEM requires the computational cost of ${\mathcal O}(d)$ to access $||x_t-x_0||$ and $||g_t||$ to determine the step size.

Compared with standard zeroth-order methods, POEM needs to additionally maintain the initial point $x_0$, which requires storing additional $d$ floating point numbers in general. However, the domains of many real applications contain the origin. In such case, we can simply set $x_0=0$ to avoid the additional memory cost to store $x_0$.

Q4 Recent research has focused on fine-tuning large language models with zeroth-order optimization algorithms while sensitive to the selection of learning rate ([1], [2]). The proposed method seems to be a promising way for solving this problem. Do you think POEM is suitable for large-scale applications like training/fine-tuning large-scale models?

A4 Thanks for your constructive suggestions. This work focuses on convex optimization, while training/fine-tuning large-scale models typically corresponds to nonconvex optimization. As we mentioned in A2, our theory cannot be directly extended to the nonconvex case. Following your suggestion, we are currently attempting to adapt POEM to the fine-tuning of large-scale models. We have not yet determined whether POEM is suitable for this task.

Thank you for your positive feedback and appreciation of our work.

Q1 Figure 3 has not been mentioned in the main text. Add a description to it.

A1 We sincerely thank you for your careful review. We will modify the text in lines 436-438 of the left column to include a clear reference to Figure 3.

Q1 The main novelty—adapting at each iteration rather than fixing it in advance—introduces only minor modifications to the DoG analysis. While this is a useful refinement, it does not introduce a fundamentally new idea.

A1 Thank you for your thoughtful review. We highlight our novelty as follows:

1. Our method can achieve the near-optimal convergence with the smoothing parameter $\mu_t=\mathcal{O}(\sqrt{d/t})$, which is larger than the counterparts in existing works such as $\mu\_t=\mathcal{O}(\sqrt{d/T})$(Shamir, 2017) and $\mu\_{2t}=\mathcal{O}(1/(d^2t^2))$ (Duchi et al., 2015). This is a new observation which improves the numerical stability.

2. For the unbounded domain case, we establish the lower bound (Theorem 5.6) to show that achieving an ideal parameter-free stochastic zeroth-order algorithm is impossible, i.e., the algorithm cannot attain the near-optimal SZO complexity with only logarithmic dependence on problem parameters. Our lower bound construction considers the dependence on $d$ in the complexity (construct the $d$ dimensional function), which is more challenging than the lower bound for the first-order method that depends on the 1-dimensional function (Khaled & Jin, 2024).

Q2 The algorithm is truly parameter-free only when the domain is bounded and the complexity bound depends on the domain's diameter.

A2 Thank you for your suggestion. We will clarify the claim of "parameter-free" in revision. For the unbounded problems, we provide the lower bound to show that it is impossible to achieve the near-optimal and parameter-free algorithm. Please see the second point in the last response.

Q3 There is a mistake in the formula $\mu_t$ for Algorithm 1, which makes the final bound in Proposition 4.7 not scale-invariant. The correct formula is likely $\mu\_t=\bar{r}\_t\sqrt{\frac{d}{t+1}}$.

A4 Thank you for your careful review. You're right that the smoothing parameter should be $\mu_t = \bar{r}\_t \sqrt{\frac{d}{t+1}}$. The result of Lemma 4.5 should be modified to

$$\sum_{k=0}^{t-1}2L \bar{r}\_k \mu\_k\leq 4L \bar{r}\_{t-1}^2\sqrt{dt},$$

where the exponent of $\bar{r}\_{t-1}$ changes from $1$ to $2$. Thus, Proposition 4.7 should be stated as:

$$f(\bar{x}\_t)-f(x^*)\leq\frac{16\theta\_{t,\delta}(\bar{r}\_t+s\_0)\big(\sqrt{G\_{t-1}}+Ld+L\sqrt{dt}\big)}{\sum_{k=0}^{t-1} \bar{r}\_k/ \bar{r}\_t},$$

which is scale-invariant. Based on above modification, the main result (Theorem 4.9) still holds. We also update our implementation and empirical results are very similar to previous ones. Please see the link https://anonymous.4open.science/api/repo/a-5532/file/response-ZPYR.pdf?v=abeb97c6.

Q4 Assumption 2.6 is missing "for all $x,y\in\mathbb{R}^d$".

A4 Thank you for your careful review. We will involve the description for these variables in revision.

Q5 Line 163: The claim that "this is more challenging" is somewhat misleading. In principle, $\mu_t$ can be arbitrarily small, even zero, in which case finite differences reduce to a directional derivative. While choosing a very small may degrade numerical stability in practice, this is a separate issue unrelated to theoretical complexity bounds.

A5 Thank you for your valuable suggestion. In revision, we will clarify that the choice of $\mu_t$ is important to the numerical stability, rather than the theoretical complexity bounds.

Q6 Lemma A.4: The reference to Shamir (2017, Lemma 9) seems incorrect.

A6 Thank you for your careful review. The result of Lemma A.4 appears at the beginning of the proof of Shamir (2017, Lemma 9), which can be found at the bottom of page 6 (not the final result of Lemma 9). We will clarify this point in revision.

Q7 Typos: "differed" (line 169), "soothing" (line 267).

A7 We appreciate your careful review. We will correct the typos in revision.

Q8 The paper assumes that the original objective is Lipschitz. What if it is Lipschitz-smooth? Can the proposed method still be applied, and what would its convergence rate be?

A8 Thank you for your insightful question.

For the bounded setting, our proposed method remains applicable. We assume that $F(\cdot;\xi)$ is $M$-smooth, i.e., $\Vert \nabla F(x)-\nabla F(y)\Vert \leq M\Vert x-y\Vert$ for all $x,y \in \mathcal{X}$. Let $x^*\in \mathcal{X}$ be the solution. It follows that $\Vert \nabla F(x)\Vert\leq\Vert\nabla F(x^*)\Vert+\Vert\nabla F(x)-\nabla F(x^*)\Vert\leq\Vert\nabla F(x^*)\Vert+M\Vert x-x^*\Vert\leq\Vert\nabla F(x^*)\Vert+MD_\mathcal{X}$ for all $x\in \mathcal{X}$. Thus, the function $F(\cdot;\xi)$ is $(\Vert\nabla F(x^*)\Vert+M D_\mathcal{X})$-Lipchitz on the domain $\mathcal{X}$. Hence, we can directly apply Theorem 4.9 to achieve the convergence rate.

For the unbounded setting, the additional assumption such as bounded variance for the stochastic gradient (Ghadimi & Lan, 2013) is typically required. It seems that our analysis cannot be directly applied to this case.