Research map / Optimization / Nonconvex and smooth optimization
On the Almost Sure Convergence of the Stochastic Three Points Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first almost sure convergence results (with rates) for the stochastic three points (STP) derivative-free algorithm on smooth nonconvex, smooth convex, and smooth strongly convex functions, plus in-expectation results and numerical comparisons with RGF and GLD.
Problem
Almost sure convergence and convergence rates of derivative-free stochastic three points (STP) optimization, which previously only had in-expectation guarantees.
Approach
Uses a Robbins-Siegmund-type / sum-of-step-sizes analysis of the STP iteration (with step sizes alpha_t = alpha/t^{1/2+eps} or alpha/t, and for strongly convex functions directional-derivative-approximating step sizes) to derive almost sure rates for best and last gradient iterates and function values, using only smoothness, lower bound and distributional assumptions on the search directions.
Key results
- For smooth functions, the best gradient iterate converges almost surely at rate o(1/T^{1/2-eps}) under step sizes alpha/t^{1/2+eps}.
- For smooth convex functions, f(theta^T)-f* is o(1/T^{1-eps}) almost surely for any eps in (2beta,1), and O(d/T) in expectation with step sizes alpha/t.
- For strongly convex functions, f(theta^T)-f* is O((1-mu/(2 pi d L))^T) in expectation and o((1-s mu/(2 pi d L))^T) almost surely for any s in (0,1), for the uniform-sphere distribution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use α_t = α/t^(1/2+ε), α > 0, for the best iterate | STP · Smooth functions | best-iterate gradient norm: o(1/T^{1/2-ε}) | Helped |
| Use step sizes with Σα_t² < ∞ and Σα_t = ∞ | STP · Smooth functions | final gradient norm | Helped |
| Use α_t = O(1/t^(1-β)), β ∈ (0, 1/2) | STP · Smooth convex functions | objective gap: o(1/T^{1-ε}), ∀ ε ∈ (2β,1) | Helped |
| Use α_t = α/t, α > R/μ_D | STP · Smooth convex functions | objective gap: O(d/T) | Helped |
| Use step sizes based on directional-derivative approximations | STP · Smooth strongly convex functions | objective gap: O((1-μ/(2πdL))^T); o((1-sμ/(2πdL))^T) | Helped |
| Use STP instead of RGF | STP · Smooth functions, d=500 | iterations and time to achieve a given accuracy | Helped |
| Use STP instead of GLD | STP · Smooth functions, d=500 | iterations and time to achieve a given accuracy | Helped |
Limitations
- Almost sure rates for the nonconvex case apply to the best iterate, with the last iterate only shown to converge without explicit rate.
- Strongly convex results require the step size to depend on the constant h and the distribution satisfying the mu_D condition, and the rate for the strongly convex case is only derived for the step size from directional derivative approximation.
- Numerical experiments are limited to a single synthetic quadratic problem in d=500.
Experimental setup
Benchmarks: synthetic quadratic objective (d=500)
Metrics: log10 gradient norm T^0.49 times best gradient norm elapsed time
Baselines: RGF (random gradient-free) GLD (Gradientless Descent)
Builds on: Stochastic Three Points (STP) Bergou et al. stochastic three points analysis Robbins-Siegmund lemma Gradientless Descent
Closest papers by meaning
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.88)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.88)
- Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization (AAAI 2024 · similarity 0.87)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.87)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.