source/tex/sections/Conclusion.tex

% !TEX root = ../main.tex

\section{Conclusion}
\label{sec:conclusion}
In this work, we investigate the gradient-variation regret in two-point BCO. 
By providing a refined analysis of the non-consecutive structure, we achieve $\Ot(d^{\frac{3}{2}}\sqrt{V_T})$ and $\O(\frac{d}{\lambda}\log V_T)$ for convex and $\lambda$-strongly convex functions, improving the best known results by factors of almost $\sqrt{d}$ and $d$, respectively. 
We also establish the first \mbox{gradient-variance} and \mbox{small-loss} bounds for two-point BCO, including the first problem-dependent guarantees that recover the minimax optimal $\O(\sqrt{dT})$ regret.
Furthermore, we extend our techniques to \mbox{one-point} BLO, achieving the first \mbox{gradient-variation} regret bound $\Ot(d^{\frac{7}{2}}\sqrt{V_T})$ for \mbox{hyper-rectangular} domains. 
We finally validate the effectiveness of our results in more challenging tasks such as dynamic/universal regret minimization and bandit games. 

Beyond the current applications, our results may find potential utility in facilitating acceleration for smooth zeroth-order optimization \citep{nesterov2017random}, and we leave this interesting direction for future exploration.