source/tex/main.tex

\documentclass{article}

\usepackage[square]{natbib}

\usepackage{microtype}
\usepackage{graphicx}
\usepackage{booktabs} 
\usepackage{xspace}
\usepackage{colortbl}
\usepackage[preprint]{icml2026}
\usepackage{amsmath}
\input{command.tex}

\newcommand{\UniGrad}{\textnormal{\textsf{\mbox{UniGrad}}}\xspace}
\newcommand{\UniGradpp}{\textnormal{\textsf{\mbox{UniGrad++}}}\xspace}

\makeatletter
\newcommand{\toccontents}{\@starttoc{toc}}
\newcommand{\Expand}{\texttt{Expand}\xspace}
\newcommand{\Bottomcoef}{\kappa}
\def \mlprod {\textsf{Adapt-ML-Prod}\xspace}
\def \omlprod {\textsf{Optimistic-Adapt-ML-Prod}\xspace}
\def \ith {{i\text{-th}}\xspace}
\def \jth {{j\text{-th}}\xspace}
\def \OGD {\textnormal{\textsf{OGD}}\xspace}
\def \OOGD {\textnormal{\textsf{OOGD}}\xspace}
\newcounter{romancounter}


\def \sumab {\sum_{t=a}^b}
\def \sumtau {\sum_{t=1}^\tau}
\def \summab {\sum_{t=a+1}^b}
\setlength{\parindent}{0pt}
\def \scvx {\textnormal{sc}}
\def \exp {\textnormal{exp}}
\def \cvx {\textnormal{cvx}}
\def \lin {\textnormal{lin}}

\def \Vs {V_\star}
\def \Vb {\bar{V}}
\def \hexp {h^{\textnormal{exp}}}
\def \hsc {h^{\textnormal{sc}}}
\def \hc {h^{\cvx}}
\def \hl {h^{\lin}}

\def \meta {\textsc{Meta-Reg}}
\def \base {\textsc{Base-Reg}}

\def \TODO {\textcolor{myred}{TODO}}
\begin{document}

\twocolumn[
    \icmltitle{Improved Dimension Dependence for\\ Bandit Convex Optimization with Gradient Variations}

    \icmlsetsymbol{equal}{*}

    \begin{icmlauthorlist}
        \icmlauthor{Hang Yu}{keylab,AI}
        \icmlauthor{Yu-Hu Yan}{keylab,AI}
        \icmlauthor{Peng Zhao}{keylab,AI}
    \end{icmlauthorlist}

    \icmlaffiliation{keylab}{National Key Laboratory for Novel Software Technology, Nanjing University, China}
    \icmlaffiliation{AI}{School of Artificial Intelligence, Nanjing University, China}

    \icmlcorrespondingauthor{Peng Zhao}{zhaop@lamda.nju.edu.cn}

    \icmlkeywords{}

    \vskip 0.3in
]
\printAffiliationsAndNotice{}

\begin{abstract}
    Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory, optimization, etc.
    It has been studied extensively in the full-information setting, but is underexplored with bandit feedback.
    In this work, we focus on gradient variation in Bandit Convex Optimization (BCO) with \mbox{two-point} feedback.  
    By proposing a refined analysis on the \mbox{\emph{non-consecutive}} gradient variation, a fundamental quantity in gradient variation with bandits, we improve the dimension dependence for both convex and strongly convex functions compared with the best known results~\citep{chiang2013beating}.
    Our improved analysis for the \mbox{non-consecutive} gradient variation also implies other favorable \mbox{problem-dependent} guarantees, such as \mbox{gradient-variance} and \mbox{small-loss} regrets.
    Beyond the \mbox{two-point} setup, we demonstrate the versatility of our technique by achieving the \emph{first} \mbox{gradient-variation} bound for one-point bandit linear optimization over \mbox{hyper-rectangular} domains.
    Finally, we validate the effectiveness of our results in more challenging tasks such as dynamic/universal regret minimization and bandit games, establishing the \emph{first} gradient-variation dynamic and universal regret bounds for two-point BCO and fast convergence rates in bandit games.
\end{abstract}

\input{sections/intro.tex}
\input{sections/Preliminary.tex}
\input{sections/Base.tex}
\input{sections/one-point.tex}
\input{sections/extension.tex}
\input{sections/Conclusion.tex}
\newpage
% \section*{Impact Statement}
% This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

\bibliography{online}
\bibliographystyle{icml2026}

\newpage
\onecolumn
\appendix
\input{Appendices/Properties-of-estimator.tex}
\input{Appendices/Proof-of-Methods.tex}
\input{Appendices/Proof-of-1-point.tex}
\input{Appendices/Proof-of-Extensions.tex}
\input{Appendices/technical.tex}

\end{document}