| Abstract: |
| We study a randomized zeroth-order algorithm that uses only differences of function values and integrates mirror descent for stochastic optimization. In convex problems, we present a new convergence analysis under $\gamma$-H\"older gradient continuity ($0\lt \gamma\leq1$) without boundedness assumptions, showing that the last iterate achieves rates of
\[
\mathcal{O}\left(T^{-\frac{1}{2}}(\log T)^2\right),
\]
matching optimal rates up to a logarithmic factor. In strongly convex settings, we analyze convergence in Bregman distance, establishing necessary and sufficient conditions for stochastic problems and linear rates for deterministic ones. For nonconvex problems, we derive convergence using the Bregman Forward-Backward envelope, a stronger stationary measure. Under the proximal Polyak-{\L}ojasiewicz condition, we obtain fast convergence rates. |
|