This work proposes a computationally efficient algorithm that achieves the optimal $O(1/\sqrt{T})$ convergence rate, matching the lower bound, and closes the existing gap in one dimension, providing the first sharp rate guarantee in this setting.
Abstract
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.
We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. We provide a complete characterization of every optimal fixed-step method. Moreover, we show every optimal fixed-step method can be derived from the constructive approach of~\cite{constructive_approach} and provide a polyhedral representation of the set of optimal methods through proof multipliers. From this characterization, we show that no anytime optimal fixed-step subgradient methods exist.
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are $(L,\kappa)$-H\"older smooth with respect to the $\ell_p$-norms, $p \geq 1$. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting $p>2$. For H\"older-smooth objectives, we close the complexity gap throughout the full $p$-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al.· 0 citations
A global iteration complexity bound is established for the smallest gradient norm among the first $k$ iterates for the smallest gradient norm among the first $k$ iterates when the initial sublevel set is bounded.
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in $\ell_1$-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions $L$-smooth relative to negative von Neumann entropy on the spectrahedron of $d \times d$ Hermitian positive-semidefinite matrices with unit trace.
Jacob M. Aguirre, Dmitrii M. Ostrovskii· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
