  The choice of the stepsize in first-order convex optimization is typically
based on the smoothness constant and plays a crucial role in the performance of
algorithms. Recently, there has been a resurgent interest in introducing
adaptive stepsizes that do not explicitly depend on smooth constant. In this
paper, we propose a novel adaptive stepsize rule based on function evaluations
(i.e., zero-order information) that enjoys provable convergence guarantees for
both accelerated and non-accelerated gradient descent. We further discuss the
similarities and differences between the proposed stepsize regimes and the
existing stepsize rules (including Polyak and Armijo). Numerically, we
benchmark the performance of our proposed algorithms with the state-of-the-art
literature in three different classes of smooth minimization (logistic
regression, quadratic programming, log-sum-exponential, and approximate
semidefinite programming), composite minimization ($\ell_1$ constrained and
regularized problems), and non-convex minimization (cubic problem).
