source/tex/sections/Base.tex

% !TEX root = ../main.tex

\section{Our Method}
\label{sec:two-point}
In this section, we improve the analysis of \emph{non-consecutive} structure defined in \pref{eq:non-consecutive}.  
For the sake of emphasis, we refer to $\Vb_T$~\eqref{eq:non-consecutive} as the non-consecutive gradient variation in the remainder of the paper.
In \pref{sec:cvx-base}, we present an improved analysis of $\E[\Vb_t]$, which enables us to establish enhanced regret bounds for general convex functions. 
In \pref{sec:scvx-base}, we provide a tight characterization of the maximal term within the expected non-consecutive gradient variation, i.e., \smash{$\max_{t\in[T]}\E[\|\g_t-\tgb_{t}\|^2]$}. This refinement, coupled with a stabilized step-size schedule, yields an improved regret bound in the strongly convex setting. 
Finally, in \pref{subsec:F_T and W_T}, we show that the non-consecutive gradient variation naturally yields other problem-dependent regret such as gradient-variance and small-loss guarantees.


\subsection{Improvement on Convex Case}
\label{sec:cvx-base}
In this part, we focus on bandit gradient-variation regret for convex functions and improve upon the result of \citet{chiang2013beating} by a factor of nearly $\sqrt{d}$, thereby closing the regret gap between the convex and linear settings.

We first restate the decomposition of the non-consecutive gradient variation $\Vb_T$~\eqref{eq:non-consecutive} in \citet{chiang2013beating}:
\begin{align}
 \Vb_T\lesssim{}& d^2\sumT (\nabla_{i_t} f_t(\w_t)-\nabla_{i_t} f_{\alpha_t}(\w_{\alpha_t}))^2\notag\\
 \le{}& 2d^2\sumT (\nabla_{i_t} f_t(\w_t)-\nabla_{i_t} f_{\alpha_t}(\w_t))^2\notag\\
 &+ 2d^2\sumT (\nabla_{i_t} f_{\alpha_t}(\w_{t})-\nabla_{i_t} f_{\alpha_t}(\w_{\alpha_t}))^2,\label{eq:VT_decom}
\end{align}
where the first inequality stems from the fact that $v_t$ closely approximates $\nabla_{i_t} f_t(\w_t)$ for all $t \in [T]$ when $\delta$ is sufficiently small and the second inequality holds by inserting an intermediate term of $\nabla_{i_t} f_{\alpha_t}(\w_t)$.

\begin{algorithm}[t]
\caption{Algorithm by \citet{chiang2013beating}}
\label{alg:chiang}
\begin{algorithmic}[1]
\Require Step sizes $\{\eta_t\}_{t=1}^T$.
\State Let $\x_1 = \hat{\x}_1 = \mathbf{0}$ and $\tgb_1 = \mathbf{0}$. Set exploration parameter $\delta=\frac{1}{2d^2 L TR}$ and shrinkage parameter $\xi=\frac{\delta}{R}$.
\For{$t =1,2,\ldots,T$}
    \State Choose $i_t$ uniformly from $[d]$.
    \State Submit two query points $\x_t = \w_t + \delta \eb_{i_t}, \x_t^\prime = \w_t - \delta \eb_{i_t}$, and observe $f_t(\x_t)$ and $f_t(\x_t^\prime)$.
    \State Compute the gradient estimator $\g_t$ and the optimism $\tgb_{t+1}$ as in \pref{eq:chiangestimator}
    \State Update the iterate as follows:
    \begin{align*}
        \hat{\w}_{t+1} = {} & \Pi_{(1 - \xi)\mathcal{X}}\mbr{\hat{\w}_{t} - \eta_t \g_t},\\
        \w_{t+1} = {} & \Pi_{(1 - \xi)\mathcal{X}}\mbr{\hat{\w}_{t+1} - \eta_{t+1} \tgb_{t+1}}
    \end{align*}
\EndFor
\end{algorithmic}
\end{algorithm}
Next, we analyze the non-consecutive structure, primarily focusing on the first term in the upper bound due to its strong connections with $V_T$.
Specifically, we have
\begin{align*}
    &\sumT (\nabla_{i_t} f_t(\w_t)-\nabla_{i_t} f_{\alpha_t}(\w_t))^2\\
    \le{}& \sumT (t-\alpha_t)\sum_{s=\alpha_t+1}^{t} (\nabla_{i_t} f_s(\w_t)-\nabla_{i_t} f_{s-1}(\w_{t}))^2\\
    \le{}& \sum_{t=1}^T \sum_{i=1}^{d} \rho_{t,i} (\nabla_i f_t(\w_t)-\nabla_i f_{t-1}(\w_{t}))^2,
\end{align*}
where the first step is by the Cauchy-Schwarz inequality, and the second step is obtained by reordering the summation. Here, $\rho_{t,i}$ is the non-consecutive sampling gap defined as \smash{$\rho_{t,i} \define \tau_2 - \tau_1$}, where \smash{$\tau_1 \define\max\{ 0\le\tau < t\given i_\tau = i\}$} and \smash{$\tau_2\define\min \{ t\le\tau\le T+1\given i_\tau = i\}$}. 
Intuitively, $\rho_{t,i}$ quantifies the duration between the most recent sampling of coordinate $i$ before $t$ and its next sampling at or after $t$.

In the linear setting, the gradient difference $\nabla_i f_t(\w_t)-\nabla_i f_{t-1}(\w_t)$ is deterministic and is independent of the non-consecutive gap $\rho_{t,i}$. Taking expectation gives:
\begin{align}
    &\E\mbr{\sum_{i=1}^{d}\rho_{t,i} (\nabla_i f_t(\w_t)-\nabla_i f_{t-1}(\w_{t}))^2}\label{eq:mid-cvx}\\
    ={}& \E[\rho_{t,i}] \sup_{\x\in\X} \|\nabla f_t(\x) - \nabla f_{t-1}(\x)\|^2,\notag
\end{align}
which holds by summing over $i\in[d]$ and the gradients of linear functions remain constant.
Following the analysis of Lemma 5 in \citet{chiang2013beating}, we have $\E[\rho_{t,i}] \le 2d$, which results in an $\O(d)$ dimension dependence.

However, for convex functions, this independence no longer holds, as both $\rho_{t,i}$ and the gradient difference share the randomness of $\{i_s\}_{s=1}^t$. This interdependence complicates the analysis and leads to a coarse upper bound.
\begin{equation*}
    \text{\pref{eq:mid-cvx}}\le \E\mbr{\sum_{i=1}^{d}\rho_{t,i}} \sup_{\x\in\X}\|\nabla f_t(\x)-\nabla f_{t-1}(\x)\|^2,
\end{equation*}
where the inequality is due to $w_i^2 \le \|\w\|^2$ for any vector $\w\in\R^d$. Since each $\E[\rho_{t,i}]$ is of order $\O(d)$, this analysis introduces an additional $d$ factor.

To address this challenge, we decouple the dependence between the sampling gap $\rho_{t,i}$ and the gradient difference by employing a uniform upper bound over all coordinates. Specifically, we have the following decomposition:
\begin{align*}
    \text{\pref{eq:mid-cvx}}\le{}& \E\mbr{\max_{i\in[d]}\rho_{t,i} \sum_{i=1}^d \sbr{\nabla_i f_{t}(\w_t)-\nabla_i f_{t-1}(\w_t)}}\\
    \le{}&\E\mbr{\max_{i\in[d]} \rho_{t,i}} \sup_{\x\in\X}\|\nabla f_t(\x)-\nabla f_{t-1}(\x)\|^2,
\end{align*} 
where the second inequality decouples the terms by taking the supremum. 
Crucially, while the expectation of a single interval $\rho_{t,i}$ is of order $\O(d)$, we prove that the expectation of their maximum across all coordinates is bounded by $\O(d \log d)$, thus incurring only an additional $\O(\log d)$ factor for convex functions. We provide a detailed analysis of the non-consecutive sampling gap $\rho_{t,i}$ in \pref{app:rho}.

The aforementioned insight allows us to derive a refined analysis for the non-consecutive gradient variation $\Vb_T$, as formalized in \pref{lem:bandit-VT-correction-cvx}. The proof is in \pref{app:lem1}.
\begin{Lemma}
\label{lem:bandit-VT-correction-cvx}
Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness}, for convex functions,  \pref{alg:chiang} satisfies the following guarantee:
\begin{align*}
    \E\mbr{\Vb_T} \le{}&  8d^3 L^2 \log T \cdot \E\mbr{\sumT \|\w_t-\w_{t-1}\|^2} \\
    &+8d^3 V_T\log d + \O(1).
\end{align*} 
\end{Lemma}
By leveraging \pref{lem:bandit-VT-correction-cvx}, we achieve a tighter dimension dependence for convex functions in \pref{thm:cvx-base} below, with the proof deferred to \pref{app:cvx-base}.
\begin{Theorem}
    \label{thm:cvx-base}    
    Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness},  for convex functions, choosing $\eta_t=\frac{R}{\sqrt{1152d^3R^4L^2\log T+\bar{V}_{t-1}}}$, \pref{alg:chiang} satisfies the following guarantee:
    \begin{align*}
        \E[\Reg_T]\define{}& \E\mbr{\sum_{t=1}^T \frac{1}{2} \sbr{f_t(\x_{t})+f_t(\x_{t}^\prime)}-\min_{\x\in \X}\sum_{t=1}^{T}f(\x)}\\
        \le{}& \Ot \big(\sqrt{\min\{d^3 V_T, dT+d^3\}}\big),
    \end{align*}
    where $V_T$ and $\Vb_t$ are defined in \pref{eq:VT} and \pref{eq:VbT}.
\end{Theorem}
Up to logarithmic factors, \pref{thm:cvx-base} effectively closes the performance gap between the convex and linear settings. Furthermore, while the dimension factor in our gradient variation bound is larger than that in the minimax-optimal $\O(\sqrt{dT})$, our result performs better in \emph{benign} environments, e.g., when $V_T = o(T/d^2)$.
Meanwhile, our result offers an $\Ot(\sqrt{dT+d^3})$ worst-case safeguard, matching optimal regret up to an additive \smash{$\Ot(d^{3/2})$ term.}


\subsection{Improvement on Strongly Convex Case}
\label{sec:scvx-base}
In this part, we focus on bandit gradient-variation regret for strongly convex functions.
Our solution consists of two key components: a more stable step-size schedule and a tight characterization of the \emph{maximal expected variation}, $\max_{t\in[T]}\E[\|\g_t-\tgb_t\|^2]$.
To contextualize our improvements, we begin with a brief review of the problem-dependent learning rate by \citet{chiang2013beating}.

Specifically, \citet{chiang2013beating} chose a problem-dependent learning rate schedule as \smash{$\eta_t \approx \frac{1}{\lambda \Vb_{t-1}}$}, where $\Vb_{t-1}$ is defined in \pref{eq:VbT}.
This learning rate is not stable enough, as the randomness of the gradient estimator will perturb it when the function value varies dramatically, leading to a large regret.
Besides, the stochasticity in the step size makes the analysis challenging due to the correlation between the step size and the gradient estimator.

To tackle this issue, we adopt a more stable and deterministic learning rate schedule~\citep{chen2024optimistic}:
\begin{equation*}
    \eta_t=\frac{1}{\lambda t}.
\end{equation*}
Building upon this deterministic step size, we propose a tight analysis for the following maximal expected variation. 
Below, we establish \pref{lem:str_alpha}, with the proof in \pref{app:g_t}.
\begin{Lemma}
    \label{lem:str_alpha}
    Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness}, for convex functions, \pref{alg:chiang} satisfies that: for any $t\in[T]$, 
    \begin{equation*}
        \E\mbr{\left\|\g_t-\tgb_t\right\|^2}\le 4d G^2+\O\sbr{\frac{1}{d^2T^2}}.
    \end{equation*}
\end{Lemma}
By combining the deterministic step size and the tight analysis for the maximal expected variation, we achieve an improved regret guarantee in the strongly convex setting in \pref{thm:scvx-base}, with the proof deferred to \pref{app:scvx-base}.
\begin{Theorem}
    \label{thm:scvx-base}
    Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness}, for $\lambda$-strongly convex functions, choosing \smash{$\eta_t=\frac{1}{\lambda t}$}, \pref{alg:chiang} enjoys 
    \begin{equation*}
        \E[\Reg_T]\le \O\sbr{\frac{d}{\lambda}\log(dV_T)}.
    \end{equation*}
\end{Theorem}
Compared to \smash{$\O\big(\frac{d^2}{\lambda}\log(dV_T)\big)$} of {\citet[Theorem 16]{chiang2013beating}}, \pref{thm:scvx-base} tightens the dimensional dependence from $d^2$ to $d$. 
As a byproduct, our result also tightens the \emph{worst-case} bound for strongly convex functions, improving the \smash{$\O\big(\frac{d^2}{\lambda}\log T\big)$} of \citet{agarwal2010optimal} by a factor of $d$.
\begin{Corollary}
   \label{cor:scvx}
    With the same assumptions and step size as in \pref{thm:scvx-base}, \pref{alg:chiang} enjoys $\E[\Reg_T]\le \O(\frac{d}{\lambda}\log T)$.
\end{Corollary}
Notably, without smoothness, the same regret guarantee can be achieved by a simple algorithm coupled with a dedicated concentration-based analysis~\citep{shamir2017optimal}. 
We defer the formal details and analysis to the \pref{app:cor-scvx}.


\subsection{Implications to Small Loss and Gradient Variance}
\label{subsec:F_T and W_T}
In this part, we demonstrate that with careful analysis, the non-consecutive gradient variation naturally yields \mbox{gradient-variance} regret~\citep{hazan2009betterBCO,hazan2011betterBCO} and \mbox{small-loss} regret~\citep{srebro2010smoothness,orabona2012beyond}.

To start with, we present an additional smoothness assumption for small-loss bounds.
\begin{Assumption}[Appendix A of \citet{yan2024simple}]
    \label{ass:Smoothness++} 
   Under the condition of $\|\nabla f_t(\x)\| \leq G$ for any $\x \in \X$ and $t \in[T]$, all online functions are $L$-smooth: $\|\nabla f_t(\x)-\nabla f_t(\y)\| \leq L\|\x-\y\|$ for any $t \in[T]$ and \smash{$\x, \y \in \X^+$}, where $\X^{+} \triangleq\{\x+\b \mid \x \in \X, \b \in G / L \cdot \B\}$ is a superset of $\X$.
\end{Assumption}
Without loss of generality, we assume $L\ge 1$ in \pref{ass:Smoothness++}, since any $L^\prime$-smooth function with $L^\prime \le L$ is also $L$-smooth. Then, we define the gradient variance $W_T$ as
\begin{equation}
    \label{eq:WT}
  W_T \define \sup_{\{\x_1,\ldots,\x_T\} \in \X} \bbr{\sumT \|\nabla f_t(\x_t) - \mub_T\|^2},
\end{equation}
where \smash{$\mub_T \define \frac{1}{T} \sumT \nabla f_t(\x_t)$} is the gradient mean. 
And we define the small loss $F_T$ as
\begin{equation}
    \label{eq:FT}
    F_T \define \min_{\x \in \X} \sumT f_t(\x) - \sumT \min_{\x \in \X^+} f_t(\x).
\end{equation}
We clarify that the small-loss definition here generalizes the standard one defined over non-negative functions \citep{srebro2010smoothness}. 
Thus, it requires smoothness on a superset of the original domain $\X$, as shown in \pref{ass:Smoothness++}.

Due to space limitations, we only focus on how to obtain $F_T$ bounds from the non-consecutive gradient variation $\Vb_T$ here. 
Specifically, we decompose $\Vb_T$ as follows:
\begin{align}
    \label{eq:FT_decom}
    &\E[\Vb_T]\lesssim d^2\E\mbr{\sumT (\nabla_{i_t} f_t(\w_t)-\nabla_{i_t} f_{\alpha_t}(\w_{\alpha_t}))^2}\notag\\
    \le{}& 2d^2 \E\mbr{\sumT  \sbr{\nabla_{i_t} f_t(\w_t)^2+\nabla_{i_t} f_{\alpha_t}(\w_{\alpha_t})^2}}.
\end{align}
The primary challenge lies in evaluating the expectation over \smash{$\nabla_{i_t} f_{\alpha_t}(\w_{\alpha_t})^2$}, which arises from the non-consecutive structure and the interdependence between $\alpha_t$ and $i_t$. 
A simplistic way to handle the coupling between $i_t$ and $\alpha_t$ is to coarsely upper-bound the $i_t$-th entry using \smash{$w_{i_t}^2 \le \|\w\|^2$}. While this eliminates the need to take expectation over $i_t$, it results in a loose $\O(d\sqrt{F_T})$ bound. To address this, we provide a refined analysis leveraging the law of total expectation to establish \pref{lem:FT}. The proof is in \pref{app:FT_lem}.
\begin{Lemma}
    \label{lem:FT}
Under Assumptions~\ref{ass:boundedness}, \ref{ass:Lipschitzness}, \ref{ass:Smoothness++},  for convex functions, \pref{alg:chiang} enjoys
\begin{equation}
    \label{eq:FTlem}
    \E[\Vb_T]\lesssim 16dL\E\mbr{\sumT f_t(\w_t)-\sumT \min_{\x\in\X^+}f_t(\x)}.
\end{equation}
\end{Lemma}
Note that the right-hand side of \pref{eq:FTlem} can be transformed to the small-loss $F_T$ using standard techniques~\citep{srebro2010smoothness,orabona2012beyond}.

The analysis for gradient variance follows an analogous approach and is thus omitted here for brevity.
To conclude, by leveraging a careful analysis of non-consecutivity, $\Vb_T$ also yields gradient-variance and small-loss bounds. We present the corresponding bounds for linear, convex, and strongly convex functions in \pref{thm:WT}-\ref{thm:FT}. The proofs are deferred to Appendices \ref{app:WT} and \ref{app:FT}.
\begin{Theorem}
    \label{thm:WT}
    Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness}, denote by $\Vb_t$ the \mbox{non-consecutive} gradient variation defined in \pref{eq:VbT}.
    \begin{itemize}[left=2pt, itemsep=-2pt, topsep=-3pt]
        \item \pref{alg:chiang} with step size \smash{$\eta_t=R/\sqrt{d^2+\bar{V}_{t-1}}$} enjoys $\O\sbr{\sqrt{dW_T}+d}$ for linear functions and $\O\sbr{d\sqrt{W_T+d}}$ for convex functions.
        \item \pref{alg:chiang} with step size $\eta_t=1/(\lambda t)$ enjoys $\O\sbr{\frac{d}{\lambda}\log(d W_T)}$ for $\lambda$-strongly convex functions.
    \end{itemize}
\end{Theorem}
\begin{Theorem}
    \label{thm:FT}
    Under Assumptions \ref{ass:boundedness}, \ref{ass:Lipschitzness}, \ref{ass:Smoothness++}, denote by $\Vb_t$ the non-consecutive gradient variation defined in \pref{eq:VbT}.
    \begin{itemize}[left=2pt, itemsep=-2pt, topsep=-3pt]
        \item \pref{alg:chiang} with step size \smash{$\eta_t=R/\sqrt{d^2+\bar{V}_{t-1}}$} enjoys $\O\sbr{\sqrt{dF_T}+d}$ for convex and linear functions.
        \item \pref{alg:chiang} with step size $\eta_t=1/(\lambda t)$ enjoys $\O\sbr{\frac{d}{\lambda}\log(d F_T)}$ for $\lambda$-strongly convex functions.
    \end{itemize}
\end{Theorem}
Up to an \emph{additive} $\O(d)$ term, our gradient-variance bound is optimal for linear functions, while our small-loss result achieves optimality for convex functions.
Notably, these two results recover the minimax optimal \smash{$\O(\sqrt{dT})$} regret when \smash{$T \ge d$}.
For strongly convex functions, the dimension dependencies of our problem-dependent bounds align with the best known results.