On the Almost Sure Convergence of the Stochastic Three Points Algorithm

Authors: Taha EL BAKKALI EL KADI, Omar Saadi
Primary area: optimization
Keywords: Derivative-free optimization, Zeroth Order optimization, Almost sure convergence, Stochastic Three Points Algorithm.

Abstract:
The stochastic three points (STP) algorithm is a derivative-free optimization technique designed for unconstrained optimization problems in $\mathbb{R}^d$. In this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation.
For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at a rate of $o(1/{T^{\frac{1}{2}-\epsilon}})$ for any $\epsilon\in (0,\frac{1}{2})$, where $T$ is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence in expectation of the final gradient iterate towards zero.
For the class of smooth convex functions, we establish that $f(\theta^T)$ converges to $\inf_{\theta \in \mathbb{R}^d} f(\theta)$ almost surely at a rate of $o(1/{T^{1-\epsilon}})$ for any $\epsilon\in (0,1)$, and in expectation at a rate of $O(\frac{d}{T})$ where $d$ is the dimension of the space.
Finally, for the class of smooth functions that are strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, $f(\theta^T)$ converges to $\inf_{\theta \in \mathbb{R}^d} f(\theta)$ in expectation at a rate of $O((1-\frac{\mu}{2\pi dL})^T)$, and almost surely at a rate of $o((1-s\frac{\mu}{2\pi dL})^T)$ for any $s\in (0,1)$,  where $\mu$ and $L$
are  the strong convexity and smoothness parameters of the function.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730206775325

thread_type:
official_review

<thread_object>
creator: reviewer_tfkj

<content>
summary:
Convergence analysis of the stochastic three points (STP) algorithm is studied. The rates for different classes of functions are shown. A almost sure convergence rate arbitrarily close to $O(1/\sqrt{T})$ is shown for smooth functions.
And almost sure convergence rate arbitrarily close to $o(1/T)$ and in expectation a rate of $O(d/T)$ is shown for smooth convex functions. For the class of strong convex functions, a rate of $O((1-\mu/dL)^T)$ in expectation and a rate arbitrarily close to $o((1-\mu/dL)^T)$ for almost sure convergence is shown.

strengths:
Paper is well-written. Convergence rates of the STP algorithm for smooth, smooth convex and smooth strongly convex functions are shown.

weaknesses:
The results are incremental. How does the convergence rate of STP compare with other methods both in expectation and almost sure. For example with RGF or GLD which is compared in the experiments ? This could be discussed or given as a table. What about the optimal convergence rate in each case ?  A brief discussion about the advantages of STP algorithm in the introduction would be helpful.

questions:
1. Please add a table comparing the convergence rates (both in expectation and almost sure) of STP, RGF, and GLD for each function class studied. Also please discuss how STP's rates compare to known optimal rates for each case. This is important as it would provide valuable context for the significance of the STP results.

2. Please add a paragraph or two in the introduction highlighting the key advantages of STP over other zeroth-order methods, such as its linear dependence on dimension compared to quadratic dependence for deterministic direct search methods. This would help readers better understand the importance of studying STP's convergence properties.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730434799142

thread_type:
official_review

<thread_object>
creator: reviewer_dtak

<content>
summary:
This paper establishes the almost sure (and last iterate) convergence of the stochastic three-point algorithm for zeroth-order optimization. The paper considers smooth nonconvex, convex, and strongly convex settings and gets the results under three different settings, respectively. Numerical experiments demonstrate the performance of the proposed method.

strengths:
The paper is well-written, with technical results clearly presented and explained. Also, different settings are considered in the paper.

weaknesses:
My major concern is the technical novelty of the paper.

1. Insufficient technical contribution.

   Although the paper considers multiple settings and gets almost-sure convergence results, the techniques seem to be a combination of [1] and other papers that establish almost-sure convergence of SGD in different settings. Especially the results in section 3 and 4 look less surprising, since most of them are obtained by verifying some conditions and invoking an existing almost-sure convergence result from the SGD literature. 

2. Presentation issues.

   The paper contains many technical results, either proven in this paper or cited from other papers. However, there is not sufficient explanation after each main result. This may make the results less accessible to the readers.

Overall I think this is a solid work, and I would like the authors to further clarify the technical contributions in this paper.

questions:
1. In the nonconvex case (Theorem 1), lower-boundedness (A2) is not assumed. But on line 624 in the appendix, the authors use the assumption that $f$ is bounded from below. 
2. A7 seems to be an artifact of analysis. Could you provide more intuitions behind it?
3. Results in section 4 require the initial point to lie in the sublevel set. Here the cost of finding such an initial point is not discussed. Could you elaborate more on this?

**Minor issues**

1. Line 139

   There seems to be an additional 2 in the complexity.

2. Line 146

   The Assump column does not match all the results in the paper (e.g., Theorem 7 in section 5 mentions "Assumption 1 and 4 to 7"). Also, assumption 7 does not appear in the table.

3. Line 146, 533

   Please put the caption of the table at the top.

4. Line 204

   The statement of the examples seems incorrect and inconsistent with [1]. The covariance matrix in [1] is $I_d / d$  instead of $I_d$.

   For any arbitrary => For any.

5. Line 318, 372

   $\ast$ and $^\star$ are inconsistent.

6. Line 890

   $m$ is undefined.

**References**

[1] Bergou, E. H., Gorbunov, E., & Richtarik, P. (2020). Stochastic three points method for unconstrained smooth minimization. *SIAM Journal on Optimization*, *30*(4), 2726-2749.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709359156

thread_type:
official_review

<thread_object>
creator: reviewer_3ujn

<content>
summary:
This paper analyzes almost-sure convergence for the derivative-free stochastic three points (STP) algorithm in (Bergou et al., 2020), where only the convergence in expectation was studied. The convergence in expectation does not guarantee convergence of individual instance of trajectories, which is why, for example, extensive research on almost-sure convergence has been conducted for SGD. This paper's study of STP, therefore, aligns with recent theoretical advancements in SGD. In particular, this paper provides the almost-sure convergence results for three standard classes of functions, as summarized in Table 1.

strengths:
This paper provides the first almost-sure convergence analysis of the STP method for three standard classes of functions, a non-trivial achievement. This analysis guarantees convergence of each trajectory instance, making it valuable both theoretically and practically.

weaknesses:
- Motivation: The focus on STP in this paper is not well motivated in the abstract and introduction, aside from mentiong its low per-iteration complexity. Is the STP widely used in practice? Given its simplicity and strong theoretical guarantees, I cannot see why this would not be considered by practitioners. I suggest that the authors further elaborate on the theoretical and practical importance of studying the STP.

- Comparison to other existing derivative-free methods: Although this paper focuses on the STP, it would have been helpful to include comparisons or discussions of the almost-sure convergence (rate) analyses for other existing derivative-free methods, if available. Without these, it is difficult to locate this work within the broader literature.

- Experiment: What is the purpose of this experiment? It seems quite orthogonal to the paper's theoretical contributions. It looks like it was added to appeal to practitioner reviewers, but I believe it may ultimately satisfy neither theory nor practitioner reviewers. I suggest revising the experiment section to better align with the paper's main contributions.

questions:
- Lines 111-112: Although it is straightforward, please explicitly state the consequence of the result.
- Line 124: $\theta$ denotes both the iterates and the step size parameter, and I suggest using other letter for the step size parameter.
- Remark 2: This seems redundant and I suggest removing it.
- Lemma 4: This does not seem necessary here, which is only used in the proof in the Appendix. I suggest moving it to Appendix.
- Remarks 7,8 and 10: They discuss the condition that Assumption 3 can be satisfied. I believe that they can be simply discussed right after Assumption 3, or can be more clearly and briefly stated in the remarks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732215494127

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank all the reviewers for their constructive feedback. Your comments and questions were invaluable in improving our paper. We have uploaded a revised version of our work taking into account your suggestions. Additionally, the supplementary material includes this updated version with all changes clearly highlighted in red.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies the almost sure convergence of a specific algorithm for zeroth-order optimization called the stochastic three points (STP) algorithm, in three main settings of smooth optimization: nonconvex, convex, and strongly convex. The main result are the rates of almost sure convergence for all three settings, significantly strengthening the previous results that were only applicable in expectation. On a technical level, the paper combines results for almost sure convergence of SGD and prior "in expectation" results for STP, which makes it somewhat limited. Nevertheless, the authors provided a more elegant analysis in the rebuttal and there was ultimately a consensus that the paper should be accepted.

A small comment: I found the statements like "at a rate arbitrarily close to <little oh of something>" confusing. Something is either "little oh" or "Big Oh." It is unclear what "arbitrarily close" to it even means. Please make sure to state the results more clearly in the abstract.