On the Almost Sure Convergence of the Stochastic Three Points Algorithm
Zeroth Order Optimization;Almost sure convergence;Stochastic Three Points Algorithm.
Yes
No ethics review needed.
- 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.
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.
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.
- 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.
Yes
No ethics review needed.
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.
The paper is well-written, with technical results clearly presented and explained. Also, different settings are considered in the paper.
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.
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.
Yes
No ethics review needed.
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.
Paper is well-written. Convergence rates of the STP algorithm for smooth, smooth convex and smooth strongly convex functions are shown.
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.
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.
@inproceedings{
anonymous2024on,
title={On the Almost Sure Convergence of the Stochastic Three Points Algorithm},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=N8tJmhCw25},
note={under review}
}
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 arbitrarily close to $o(\frac{1}{\sqrt{T}})$, 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 arbitrarily close to $o(\frac{1}{T})$, 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}{dL})^T)$, and almost surely at a rate arbitrarily close to $o((1-\frac{\mu}{dL})^T)$,  where $\mu$ and $L$
are  the strong convexity and smoothness parameters of the function.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Zeroth Order Optimization Almost sure convergence Stochastic Three Points Algorithm.
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/a93f87d30dd13a5a146cdfca0268b4b22c43a86a.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/0579060665afc7fea307a53ee28106e208f41c91.zip
On the Almost Sure Convergence of the Stochastic Three Points Algorithm
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission