source/tex/sections/intro.tex

% !TEX root = ../main.tex

\section{Introduction}
\label{sec:intro}
Online Convex Optimization (OCO) is a powerful and fundamental framework for modeling the interaction between a learner and the environment over time \citep{hazan2016introduction,orabona2019modern}. 
In round $t\in[T]$, the learner selects $\x_t \in \X \subseteq \R^d$, while the environment simultaneously chooses a convex function $f_t:\X\to \R$.
Then the learner suffers $f_t(\x_t)$ and receives gradient feedback about the online function, aiming to optimize the \mbox{game-theoretical} performance measure known as regret~\citep{cesa2006prediction}, which is defined as
\begin{equation*}
    \Reg_T^{\text{(OCO)}} \define \sumT f_t(\x_t) - \min_{\x\in\X} \sumT f_t(\x).
\end{equation*}
For OCO, the minimax optimal regret results are $\O(\sqrt{T})$ for convex and $\O(\log T)$ for strongly convex functions \citep{hazan2016introduction}. 
Beyond the worst-case minimax optimality, literature considers enhancing the adaptivity of the learner by adapting the regret to the problem-dependent hardness. 
Among various problem-dependent quantities, \emph{gradient variation}~\citep{chiang2012online, yang2014regret} has garnered much interest in recent years \citep{qiu2023gradient,tsai2023datadependent,zhao2024adaptivity,tarzanagh2024online,xie2024gradient}, due to its profound connections to bridging adversarial/stochastic optimization~\citep{Sarah2022between,chen2024optimistic}, enabling fast rates in games~\citep{rakhlin2013optimization,syrgkanis2015fast}, and facilitating acceleration in smooth offline optimization~\citep{cutkosky2019anytime,zhao2025gradient}, etc. 
Specifically, gradient variation measures the cumulative variation of gradients across consecutive functions:
\begin{equation}
    \label{eq:VT}
    V_T \define \sumTT \sup_{\x \in \X} \|\nabla f_t(\x) - \nabla f_{t-1}(\x)\|^2_2.
\end{equation} 
By adapting to the gradient variation, the aforementioned minimax regret guarantees can be improved to $\O(\sqrt{V_T})$ for convex and $\O(\log V_T)$ for strongly convex functions. 

\begin{table*}[!t]
    \centering
    \caption{\small{Comparison of problem-dependent regret bounds for two-point BCO. Here, we consider the \emph{non-degenerative} setup for clarity, where we assume $V_T, W_T, F_T \ge \Omega(d)$. $V_T, W_T$, and $F_T$ denote the gradient variation~\eqref{eq:VT}, gradient variance~\eqref{eq:WT}, and small loss~\eqref{eq:FT}, respectively. The \smash{$\Ot(\cdot)$} notation omits logarithmic factors in the dimension $d$ and the time horizon $T$. We use `\textemdash' to denote results that match but do not improve upon state-of-the-art bounds.}}
    \renewcommand{\arraystretch}{1.2}
    \resizebox{0.8\linewidth}{!}{
    \begin{tabular}{r|cccc}
    \hline

    \hline
    & \textbf{Linear} & \textbf{Convex} & \textbf{$\lambda$-Strongly Convex} \\
    \hline
    \cellcolor{gray!10}\rule{0pt}{5mm}\textbf{\citet{chiang2013beating}} & \cellcolor{gray!10}$\O\big(d^{\frac{3}{2}}\sqrt{V_T}\big)$ & \cellcolor{gray!10} $\Ot\big(d^2\sqrt{V_T}\big)$ &\cellcolor{gray!10} $\O\big(\frac{d^2}{\lambda}\log V_T\big)$\\[1mm]
    \hline \hline
    \rule{0pt}{5mm} \textbf{Ours} [Gradient Variation $V_T$] & \textemdash & $\Ot\big(d^{\frac{3}{2}}\sqrt{V_T}\big)$ [\pref{thm:cvx-base}] & $\O\big(\frac{d}{\lambda}\log V_T\big)$ [\pref{thm:scvx-base}]  \\[1mm]
    \hline
    \rule{0pt}{5mm} \textbf{Ours} [Gradient Variance $W_T$] & $\O\big(\sqrt{dW_T}\big)$ [\pref{thm:WT}] & $\O\big(d\sqrt{W_T}\big)$ [\pref{thm:WT}] & $\O\big(\frac{d}{\lambda}\log W_T\big)$ [\pref{thm:WT}]  \\[1mm]
    \hline
    \cline{2-4}
    \rule{0pt}{5mm} \textbf{Ours} [Small Loss $F_T$] & $\O\big(\sqrt{dF_T}\big)$ [\pref{thm:FT}] & $\O\big(\sqrt{dF_T}\big)$ [\pref{thm:FT}] & $\O\big(\frac{d}{\lambda}\log F_T\big)$ [\pref{thm:FT}]  \\[1mm]
    \hline

    \hline
    \end{tabular}
    }
    \label{table:mainresults}
\end{table*}

While gradient-variation regret has been studied extensively in the full-information setting, it is still underexplored in Bandit Convex Optimization (BCO), where the learner only has access to the function values. Based on the number of function values queried, BCO can be classified into \mbox{one-point}, \mbox{two-point}, and \mbox{multi-point} settings. 
In the \mbox{one-point} setup, achieving gradient-variation regret (specialized as squared path-length regret in multi-armed bandits) remains open~\citep{wei2018more}. 
By contrast, when it comes to the \emph{two-point} setup, the \mbox{gradient-variation} regret bounds can be made possible~\citep{chiang2013beating}. 
Specifically, two-point BCO allows the learner to query two points $\x_t, \x_t^\prime \in \X$ at round $t \in [T]$, and observe the function values $f_t(\x_t)$ and $f_t(\x_t^\prime)$. 
\citet{chiang2013beating} initiated the study of gradient variation in two-point BCO and provided the first \smash{$\O(\sqrt{d^3 V_T})$}, \smash{$\Ot(d^2 \sqrt{V_T})$}, and \smash{$\O(\frac{d^2}{\lambda}\log (dV_T))$} for linear, convex, and $\lambda$-strongly convex functions, where $d$ is the dimension and $\Ot(\cdot)$ omits the logarithmic factors in $T$ and $d$.
While their results enjoy the optimal dependence on $V_T$, they incur a large dimension dependence,
as the $\Omega(\sqrt{dT})$ convexity lower bound~\citep{duchi2015optimal} indicates that a tighter dimension dependence is possible.

Mitigating the dimension dependence is a fundamental challenge in BCO~\citep{agarwal2010optimal,fokkema2024online} and zeroth-order stochastic optimization~\citep{duchi2015optimal,nesterov2017random,wang2018stochastic}, and there has been a lot of progress on this front. 
The difficulty stems from the inherent information bottleneck in bandit feedback, where reconstructing a $d$-dimensional gradient from scalar function values necessitates a sampling complexity that scales unfavorably with dimension $d$~\citep{lattimore2025banditconvexoptimisation}.

In bandit gradient-variation online learning, reducing the dimension dependence poses additional challenges.
To see this, we provide an intuition.
In OCO, where the learner has access to the full gradient information in \emph{all} directions, e.g., $\nabla f_t$ and $\nabla f_{t-1}$, the gradient-variation regret is straightforward to achieve by using the well-known optimistic online learning technique~\citep{chiang2012online}.
However, with bandit feedback, the learner can sample \emph{only one} direction at each round. 
For example, at the $t$-th round, the learner samples a random direction $i_t \in [d]$, constructs a gradient estimator, and obtains an estimation of $\nabla_{i_t} f_t$, where $\nabla_{i} f$ denotes the gradient of $f$ in the $i$-th direction. 
Therefore, it is hard to analyze $\nabla_{i_t} f_t - \nabla_{i_{t-1}} f_{t-1}$ directly because the two directions between consecutive rounds are very likely to be different. 
To this end, in bandit optimization, an essential quantity is a \emph{non-consecutive} version of the gradient variation~\citep{chiang2013beating, wei2018more}, which conceptually depends on the following term:
\begin{equation}
    \sumT (\nabla_{i_t} f_t - \nabla_{i_t} f_{\alpha_t})^2,
\end{equation}
where $\alpha_t$ is the largest integer such that $0 \leq \alpha_t < t$ and $i_{\alpha_t} = i_t$. 
Since the learner can only sample one direction at each round, the non-consecutive sampling gap, i.e., $t-\alpha_t$, will inevitably scale with the dimension $d$, leading to an additional dimension dependence compared with regret bounds in the full information setting.

In this work, we tighten the dimension dependence of the gradient-variation regret bounds in two-point BCO by unraveling the inherent correlation structure in the \emph{non-consecutive gradient variation}. 
By carefully decoupling these dependencies, we achieve \smash{$\Ot(d^{\frac{3}{2}}\sqrt{V_T})$} for convex functions and \smash{$\O(\frac{d}{\lambda}\log V_T)$} for $\lambda$-strongly convex functions, thereby improving the best known results by factors of nearly \smash{$\sqrt{d}$} and $d$, respectively.

Our analysis for \mbox{non-consecutive} gradient-variation also implies regret scaling with other favorable \mbox{problem-dependent} quantities, such as gradient variance $W_T$ and small loss $F_T$, thereby offering multiple perspectives to depict the \mbox{problem-dependent} hardness. 
Among the implied results, in particular, we achieve \smash{$\O\sbr{\sqrt{d F_T}+d}$} for convex functions and \smash{$\O\sbr{\sqrt{d W_T}+d}$} for linear functions, which are both optimal up to an \emph{additive} $\O(d)$ term. \pref{table:mainresults} summarizes our complete results. 

Beyond the two-point setup, we generalize our techniques to one-point Bandit Linear Optimization (BLO). 
Briefly, we introduce a novel gradient estimator with an associated algorithm and establish the \emph{first} gradient-variation regret bound for one-point BLO, in a special case where the domain is a hyper-rectangle, highlighting the versatility of our approach.

Finally, we showcase the effectiveness of our methods in more challenging environments: \textit{(i)} \mbox{\emph{dynamic regret}}~\citep{zhang2018adaptive}, where the learner competes against time-varying comparators; \textit{(ii)} \mbox{\emph{universal regret}}~\citep{van2016metagrad}, where the learner has no prior knowledge of the curvature but aims at achieving matching guarantees with curvature-aware methods; \textit{(iii)} \mbox{\emph{bandit game}}~\citep{rakhlin2013optimization}, where two learners play against each other with bandit feedback.
To conclude, we establish the \emph{first} gradient-variation dynamic and universal regret for two-point BCO and fast convergence rates for bandit games.


\textbf{Contributions.}~~
Our contributions are summarized below:
\begin{itemize}[left=2pt, itemsep=-2pt, topsep=-1pt]
    \item For two-point BCO with gradient variations, we obtain $\Ot(d^{\frac{3}{2}}\sqrt{V_T})$ and $\O(\frac{d}{\lambda}\log V_T)$ for convex and $\lambda$-strongly convex functions, thereby improving the previously best known results by factors of almost $\sqrt{d}$ and $d$, respectively. 
    \item We achieve the \emph{first} gradient-variance and small-loss regret for two-point BCO, among which, \smash{$\O(\sqrt{d F_T}+d)$} and \smash{$\O(\sqrt{d W_T}+d)$} for convex and linear functions, respectively, are \emph{the first} \mbox{problem-dependent} guarantees that can recover the minimax optimal $\O(\sqrt{dT})$ regret.
    \item We derive the \emph{first} gradient-variation regret bound in the one-point BLO setting over hyper-rectangular domains.    
    \item We establish the \emph{first} gradient-variation dynamic and universal regret bounds in two-point BCO and fast rates for bandit games over hyper-rectangular domains.
\end{itemize}

\textbf{Organization.}~~
The rest of the paper is organized as follows: 
In \pref{sec:preliminary}, we introduce the preliminaries.
In \pref{sec:two-point}, we present our main results for two-point BCO. 
In \pref{sec:1point}, we extend our methods to one-point BLO. 
In \pref{sec:extension}, we generalize our methods to more challenging environments, including dynamic regret, universal regret, and games. 
Finally, in \pref{sec:conclusion}, we conclude the paper. 
Due to page limits, all proofs are deferred to appendices.