source/tex/sections/Preliminary.tex

% !TEX root = ../main.tex

\section{Preliminary}
\label{sec:preliminary}
In this section, we introduce the  notations, assumptions, and a brief review of the progress of \citet{chiang2013beating}.

\subsection{Notations and Assumptions}
\label{subsec:notations}
\textbf{Notations.}~~  For any $N \in \mathbb{N}$, we define $[N]$ as $\{1, \ldots, N\}$. We represent the $i$-th out of $d$ dimensions of the bold vector $\v$ (or $\boldsymbol{v}$) using the corresponding regular font $v_i$, i.e., $\v$ (or $\boldsymbol{v}$) $= (v_1, \dots, v_d)^\top$. We use $\nabla_i f$ to denote the partial derivative of $f$ w.r.t. the $i$-th coordinate.  
We use $\|\cdot\|$ for $\|\cdot\|_2$ by default.
We write $a \lesssim b$, or $a = \O(b)$, if there exists a constant $C < \infty$ such that $a \le Cb$. We use $\O(\cdot)$ to highlight the dependencies on $d, T$, and \mbox{problem-dependent} quantities, while $\Ot(\cdot)$ omits logarithmic factors in $d$ and $T$. Throughout the paper, we treat the $\log\log T$ factor as a constant and omit it following~\citet{luo2015achieving}.

\begin{Assumption}[Boundedness]
    \label{ass:boundedness}
    The feasible domain $\X\in \R^d$ is compact, convex, and satisfies $r\B\subseteq \X\subseteq R\B$, where $\B=\{\x\in \R^d \given \|\x\|\le 1\}$ is a unit ball.
\end{Assumption}
\begin{Assumption}[Lipschitzness]
    \label{ass:Lipschitzness}
    For any $\x,\x^\prime\in\X$ and all $t\in[T]$, $|f_t(\x)-f_t(\x^\prime)|\le G \|\x-\x^\prime\|$.
\end{Assumption}
\begin{Assumption}[Smoothness]
    \label{ass:Smoothness} 
    For any $\x,\x^\prime\in \X$ and all $t\in[T]$, $\|\nabla f_t(\x)-\nabla f_t(\x^\prime)\|\le L \|\x-\x^\prime\|$.
\end{Assumption}
Assumptions~\ref{ass:boundedness} and \ref{ass:Lipschitzness} are standard for BCO \citep{flaxman2004online,agarwal2010optimal}. 
\pref{ass:Smoothness} is essential for establishing gradient-variation regret~\citep{chiang2012online}.

\subsection{A Review of \texorpdfstring{\citet{chiang2013beating}}{Chiang et al. (2013)}}
\label{subsec:chiang}
For full-information feedback, a standard technique for gradient-variation regret is Optimistic Online Gradient Descent (\OOGD) \citep{chiang2012online}. At round $t$, the learner leverages an optimism $M_{t}$, which serves as a predictive hint of the upcoming gradient $\nabla f_{t}(\x_{t})$. Established on this optimism, \OOGD proceeds with the following updates:
\begin{equation*}
    \x_t = \Pi_{\X} \mbr{\xh_{t}-\eta_{t} M_{t}},\ \xh_{t+1} = \Pi_{\X} \mbr{\xh_t-\eta_t \nabla f_{t}(\x_{t})}
\end{equation*}
where  $\eta_t > 0$ is a time-varying step size, \smash{$\xh_t$} and \smash{$\xh_{t+1}$} are internal decisions, and $\Pi_{\X}[\x] \define \argmin_{\y \in \X} \|\x - \y\|$ is the Euclidean projection onto the feasible domain $\X$. 
The resulting regret depends on the cumulative prediction error \smash{$\sum_{t=1}^T \|\nabla f_t(\x_t) - M_t\|^2$}, which characterizes the accuracy of the prediction $M_t$. 
A straightforward instantiation of $M_t$ is to set it as the preceding gradient $\nabla f_{t-1}(\x_{t-1})$. 
Such a predictive choice is sufficient to attain the optimal gradient-variation regret~\citep{chiang2012online}.

For two-point BCO, where the learner only has access to function values instead of gradients, we define the corresponding cumulative prediction error as:
\begin{equation}
    \label{eq:VbT}
    \Vb_T \define \sum_{t=1}^T \|\g_t - \tgb_t\|^2,
\end{equation}
where $\g_t$ is the gradient estimator at round $t$ and $\tgb_t$ denotes the optimism constructed from historical information up to round $t-1$. 
A direct choice in bandits would be using the estimator $\g_t = c_t \u_t$ and assigning the optimism $\tgb_t$ as the preceding $\g_{t-1}$. 
Here, $\u_t$ denotes a random vector drawn from a specified distribution and $c_t$ is an estimation constant to ensure $\E[\g_t]\approx \nabla f_t(\x_t)$.
For example, in \mbox{two-point} BCO~\citep{agarwal2010optimal}, $\u_t$ is uniformly sampled from the unit sphere, and $c_t = \frac{d}{2\delta}(f_t(\x_t + \delta \u_t) - f_t(\x_t - \delta \u_t))$, where $\delta > 0$ is a small exploration parameter.
However, in this case, the gap $\|\g_t - \tgb_t\|$ becomes unmanageable, as the randomness of $\u_t$ and $\u_{t-1}$ causes severely misaligned consecutive estimators with high probability.

To bridge this gap, inspired by the gradient estimator in \citet{hazan2009betterBCO,hazan2011betterBCO}, \citet{chiang2013beating} introduced a novel gradient estimator and an optimism term to effectively solve the issue of direction misalignment.  
Specifically, at $t\in[T]$, the gradient estimator $\g_t$ and the optimism $\tgb_t$ are constructed as follows:
\begin{equation}
    \label{eq:chiangestimator}
    \begin{gathered}
        \g_t=d\left(v_t-\tilde{g}_{t, i_t}\right) \eb_{i_t}+\tilde{\g}_t,\\
        \tilde{\g}_{t+1}=\left(v_t-\tilde{g}_{t, i_t}\right) \eb_{i_t}+\tilde{\g}_t,
    \end{gathered}
\end{equation}
where $i_t$ is drawn uniformly from $[d]$, $\{\eb_1,\ldots,\eb_d\}$ is the standard basis of $\R^d$, and $v_t \define \frac{1}{2\delta} (f_t(\w_t + \delta \eb_{i_t}) - f_t(\w_t - \delta \eb_{i_t}))$ serves as an estimation of the directional derivative of $f_t$ at $\w_t$ along $\eb_{i_t}$. 
Here, $\mathbf{w}_t$ is the center around which the query points $\x_t$ and $\x_t^\prime$ are  sampled as $\x_t=\w_t+\delta\eb_{i_t}$ and $\x_t^\prime =\w_t-\delta\eb_{i_t}$, where $\delta > 0$ is a small exploration parameter. 
By concentrating the difference onto a single coordinate $\g_t - \tgb_t = d (v_t - \gt_{t, i_t}) \eb_{i_t}$, \pref{eq:chiangestimator} yields a manageable difference between $\g_t$ and $\tgb_t$, further leading to a controllable  $\Vb_T$. 
Leveraging this construction, the authors integrated the estimator and optimism in \pref{eq:chiangestimator} into \OOGD. We restate their method in \pref{alg:chiang}.

Despite the aforementioned innovative design, \citet{chiang2013beating} underestimated the non-consecutive nature of the gradient estimators. 
Specifically, by choosing the estimators from \eqref{eq:chiangestimator}, $\Vb_T$~\eqref{eq:VbT} exhibits the following structure:
\begin{equation}
    \label{eq:non-consecutive}
    \Vb_T = d^2\sum_{t=1}^T  (v_t-v_{\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$. 
Intuitively, the $(v_t-v_{\alpha_t})$ term measures the gap of two directional derivative estimates between two iterations where the sampled direction is the same, leading to a natural non-consecutive structure.
This term is essential for the dimension dependence of the regret bound.
In the next section, we will show the analysis of \citet{chiang2013beating} for the essential quantity $\Vb_T$, their limitations and our improved analysis for it.