Author

Alexandre B. Tsybakov

View on Semantic Scholar

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Jul 2026

Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension

Stochastic convex optimization is a classical problem with well-understood guarantees under first-order feedback. In contrast, for zero-order optimization with noisy function evaluations, a logarithmic gap has persisted between known upper bounds and the $\Omega(1/\sqrt{T})$ lower bound, even in the one-dimensional case. In this work, we study the problem of minimizing a convex function $f : [0,1] \to [0,1]$ using a zero-order oracle with subGaussian noise. We propose a computationally efficient algorithm that achieves the optimal $O(1/\sqrt{T})$ convergence rate, matching the lower bound. The result closes the existing gap in one dimension, providing the first sharp rate guarantee in this setting.

A. Carpentier, Chloé Rouyer, Alexandre B. Tsybakov et al. · 0 citations

Preprint Jul 2026

Gradient-free stochastic optimization of derivatives under strong convexity

We consider the problem of minimizing the $k$-th order partial derivative $f=\partial_j^k g$ of an unknown function $g$ along a fixed coordinate direction $j$, based on noisy queries of $g$. Assuming that $g$ has H\"older regularity ${\beta+k}$ for some $\beta\ge 2$, that $f$ is strongly convex on a compact convex set $\Theta\subset\mathbb{R}^d$ and that $g$ and $f$ satisfy mild boundedness and Lipschitz regularity conditions on $\Theta$, we propose a kernel-based estimator of $\nabla f$ and analyze the projected stochastic gradient algorithm driven by this estimator. We obtain a non-asymptotic upper bound on the optimization error of the order $d^{(2\beta+k-1)/(\beta+k)}\,N^{-(\beta-1)/(\beta+k)}$, where $N$ is the total number of queries. We also establish a minimax lower bound of the order $N^{-(\beta-1)/(\beta+k)}$ showing that this rate is optimal in $N$ over all sequential algorithms.

A. Akhavan, Sirine Louati, Alexandre B. Tsybakov · 0 citations