\section{Introduction}
Online learning algorithms differ from conventional learning paradigms as they targeted at learning the model incrementally from data in a sequential manner given the knowledge (could be partial) of answers pertaining to previously made decisions. They have shown to be effective in handling large-scale and high-velocity streaming data and emerged to become popular in the big data era \cite{Hoi2018Online,Hoi2014LIBOL}. In recent years, a number of effective online learning algorithms have been investigated and applied in a variety of high-impact domains, ranging from game theory, information theory, to machine learning and data mining \cite{Ding2017Large,Shai2011Online,Wang2003Mining}. Most previously proposed online learning algorithms fall into the well-established framework of online convex optimization \cite{Gordon1999Regret,Zinkevich2003Online}.

In terms of the optimization algorithms, online learning algorithms can be broadly divided into the following categories: (i) first-order algorithms which aim to optimize the objective function using the first-order (sub) gradient such as the well-known OGD algorithm \cite{Zinkevich2003Online}; and (ii) second-order algorithms which aim to exploit second-order information to speed up the convergence rate of the optimization process, such as the ONS algorithm \cite{Hazan2007Logarithmic}. In online convex optimization, previous approaches are mainly based on the first-order optimization, i.e., optimization using the first-order derivative of the cost function. The regret bound achieved by these algorithms is often considered to be proportional to the polynomial of the number of rounds $T$. For example, \cite{Zinkevich2003Online} showed that with the simple OGD algorithm, we can achieve the regret bound of $\mathcal{O}(\sqrt{T})$. Later on, \cite{Hazan2007Logarithmic} introduced a new algorithm with ONS by exploiting the second-order derivative of the cost function, which can be regarded as an online analogy of the Newton-Raphson method~\cite{Ypma1995Historical} in the offline learning. Although the time complexity $\mathcal{O}(d^2)$ of ONS is higher than that of OGD $\mathcal{O}(d)$ ($d$ denotes the number of features) per iteration, it guarantees a logarithmic regret bound $\mathcal{O}(\log T)$ with a warm assumption of the cost function.

Additionally, according to the forms of feedback information of the prediction, existing online convex optimization algorithms can be broadly classified into two categories \cite{Abernethy2012Interior}: (i) online learning with full information feedback; and (ii) online learning with limited feedback (or bandit feedback) \cite{Dani2007The,Hazan2016An,Mcmahan2004Online,Neu2013An}. In the former scenario, full information feedback of the prediction is always revealed to the learner at the end of each round; while in the latter scenario, the learner only receives partial information feedback from the environment of the prediction. In many real-world applications, the full information feedback is often difficult to acquire while the cost of obtaining bandit feedback is often much lower. For example, in many e-commerce websites, users only provide positive feedback (e.g., clicks or purchasing behaviors) \cite{Suhara2013Robust,Zoghi2017Online} but do not necessarily disclose the full information feedback (e.g., fine-grained preferences). In this regard, online convex optimization with bandit feedback has motivated a surge of research interests in recent years. For example, \cite{Flaxman2005Online} extended the OGD algorithm to the bandit setting, where the learner only knows the value of the cost function at the current prediction point while the cost function value at other points remains opaque. In particular, it uses a simple approximation of the gradient of the cost function $f_{t}$ at the current point $\mat{x}_t$, and bounds the expected regret (against an oblivious adversary) as $\mathcal{O}(T^{5/6})$.

As second-order algorithms such as ONS often lead to lower regret bound than the first-order methods when full information feedback is available, one natural question to ask is whether the success can be shifted to the bandit feedback scenario. To answer this question, in this paper, we make the initial investigation of the ONS algorithm when only partial feedback is available. Our main contribution is the development of a novel second-order online convex optimization algorithm which can reduce the regret bound from $\mathcal{O}(T^{5/6})$~\cite{Flaxman2005Online} to $\mathcal{O}(T^{2/3})$. Furthermore, if the cost function $f_{t}$ is $L$-Lipschitz, we can further bound the regret as $\mathcal{O}(\sqrt T)$ which is often desired in practical usage.

The remainder of this paper is organized as follows. In Section 2, we summarize some symbols used throughout this paper and present the preliminaries of the bandit convex optimization problem. In Section 3,
we introduce the proposed Online Newton Step algorithm with Estimated Gradient in details. In Section 4, empirical evaluations on benchmark datasets are given to show the superiority of the proposed algorithm. In Section 5, we briefly review related work on bandit convex learning. The conclusion is presented in Section 6.

\section{Preliminaries}
In this section, we first present the notations and symbols used in the paper and then formally define the problem of bandit convex optimization.
\subsection{Notations and Symbols}
Table \ref{tab:symbols} lists the main notations and symbols used in this paper.
We use bold lowercase characters to denote vectors (e.g., \mat{a}), bold upper case characters to denote matrices (e.g., \mat{A}), and $\mat{A}^T$ to denote the transpose of \mat{A}. For a positive definite matrix \mat{A}, we use $\|\mat{x}\|_\mat{A} = \sqrt{\langle \mat{x},\mat{A}\mat{x}\rangle}$ to denote the Mahalanobis norm of vector \mat{x} with respect to \mat{A}.

$\nabla$ denotes the gradient operator. $\mat{u}\sim U_{\mathbb{B}}$ denotes a random variable that is distributed uniformly over $\mathbb{B}$.
Under the bandit feedback setting, we use $\mathbb{E}_{t-1}[\cdot]$ to denote the conditional expectation given the observations up to time $t-1$.
\begin{table}[htbp]
\centering
\caption{Descriptions of notations and symbols. \label{tab:symbols}}
\begin{tabular}{|c|c|}
\hline Notations &  Definitions  \\
\hline\hline
$\mathcal{P}$& convex feasible set\\
$\varPi_{\mathcal{P}}^{\mat{A}}[\mat{x}]$ & the generalized projection of $\mat{x}$ onto $\mathcal{P}$\\
$D$          & $D=\mathop{\max}_{\mat{x}, \mat{y}\in\mathcal{P}}\|\mat{x}-\mat{y}\|_{2}$ \\
$\mat{X}^t$  & $[\mat{x}^1;\mat{x}^2;\ldots;\mat{x}^t]$ \\
$f_t$        & loss function of the $t^{th}$ iteration\\
$\mathbb{B}$ & $\mathbb{B}=\{\mat{x}\in\mathbb{R}^{d}\mid \|\mat{x}\|\leq1\}$ \\
$\mathbb{S}$ & $\mathbb{S}=\{\mat{x}\in\mathbb{R}^{d}\mid \|\mat{x}\|=1\}$ \\
$r$          & $r\mathbb{B}\subseteq \mathcal{P}$\\
$F$          & upper bound of $|f_t|$ on $\mathcal{P}$\\
$\hat{f}$    & $\hat{f}(\mat{x})=\mathop{\mathbb{E}}_{\mat{u}\sim U_{\mathbb{B}}}[f(\mat{x}+\delta\mat{u})]$\\
$\delta$     & parameter of $\hat{f}(\mat{x})$\\
$\sigma$     & parameter of the $\sigma$-nice function\\
\hline
\end{tabular}
\end{table}

\subsection{Bandit Convex Optimization}
Bandit convex optimization (BCO) are often performed for a sequence of consecutive rounds. In particular at each round $t$, the online learner picks a data sample $\mat{x}_t$ from a convex set $\mathcal{P}$. After the data sample is picked and used to make the prediction, a convex cost function $f_t$ is revealed, then the online learner suffers from an instantaneous loss $f_t(\mat{x}_t)$. Under the online convex optimization framework, we assume that the sequence of loss functions $f_{1}, f_{2},\ldots, f_{T}: \mathcal{P}\rightarrow\mathbb{R}$ are fixed in advance.
And the goal of the online learner is to choose a sequence of predictions $\mat{x}_1,\mat{x}_2,\ldots, \mat{x}_T$ such that the regret defined as $\sum_{t=1}^{T}f_{t}(\mat{x}_{t}) - \mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{x})$ is minimized, where $\sum_{t=1}^{T}f_{t}(\mat{x}_{t})$ denotes the cumulative error across all $T$ rounds while $\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{x})$ denotes the cumulative error resulted from the optimal decisions in hindsight.
In the full information feedback setting, the learner has access to the gradient of the loss function at any point in the feasible set $\mathcal{P}$.
Conversely, in the BCO setting the given feedback is $f_t(\mat{x}_t)$, which is the value of the loss function at the point it chooses.

In this paper, we assume that origin is contained in the feasible set $\mathcal{P}$ with $D$ as diameter, so $r\mathbb{B} \subseteq \mathcal{P} \subseteq D\mathbb{B}$. Meanwhile, the loss functions $f_t$ are $\sigma$-nice function (see \cite{Hazan2016Graduated}) and bounded by $F$ (i.e. $|f_t|\leq F$).

\section{The Proposed Online Newton Step Algorithm with Estimated Gradient}
As mentioned previously, this paper focuses on the online learning problem with partial information feedback - the bandit setting. For example, in the multi-armed bandit problem (MAB) \cite{Salehi2017Stochastic,Tekin2010Online}: there are $d$ different arms, and on each round $t$ the learner chooses one of the arms which is denoted by a basic unit vector $\mat{x}_t$ (indicate which arm is pulled). Then the learner receives a cost of choosing this arm, $f_t(\mat{x}_t)=\langle \mat{y}_t,\mat{x}_t \rangle\in\{0,1\}$. The vector $\mat{y}_t\in\{0,1\}^d$ associates a cost for each arm, but the learner only has access to the cost of the arm she/he pulls.

In this setting, the functions change adversarially over time and we can only evaluate each function once and cannot access the gradient of $f_t$ directly for gradient descent. To tackle this issue, \cite{Flaxman2005Online} proposed to use one-point estimate of the gradient. Specifically, for a uniformly random unit vector $\mat{v}$, we have $\nabla f(\mat{x}) \approx \mathbb{E}_{\mat{v}\sim U_{\mathbb{S}}}[(f(\mat{x}+\delta\mat{v})-f(\mat{x}))\mat{v}]\frac{d}{\delta} = \mathbb{E}_{\mat{v}\sim U_{\mathbb{S}}}[f(\mat{x}+\delta\mat{v}))\mat{v}]\frac{d}{\delta}$\footnote{The equation holds for $\mathbb{E}_{\mat{v}\sim U_{\mathbb{S}}}[f(\mat{x})\mat{v}]=0.$}. Theoretically, the vector $\frac{d}{\delta}f(\mat{x}+\delta\mat{v})\mat{v}$ is an estimate of the gradient with low bias, and thus it is an approximation of the gradient. In fact, $\frac{d}{\delta}f(\mat{x}+\delta\mat{v})\mat{v}$ is an unbiased estimator of the gradient of a smoothed version of $f$, which can be mathematically formulated as $\hat{f}(\mat{x})=\mathop{\mathbb{E}}_{\mat{u}\sim U_{\mathbb{B}}}[f(\mat{x}+\delta\mat{u})].$
As shown by Flaxman \emph{et al.} \cite{Flaxman2005Online}, the advantage of $\hat{f}$ is that it is differentiable and we can estimate its gradient with a single call since $\mathop{\mathbb{E}}_{\mat{v}\sim U_{\mathbb{S}}}[\frac{d}{\delta}f(\mat{x}+\delta\mat{v})\mat{v}]=\nabla\hat{f}(\mat{x})$ (see LEMMA 2.1 in \cite{Flaxman2005Online} for details). One should note that under the assumption of $f$ is bounded ($|f|\leq F$) and $\sigma$-nice\footnote{Hazan et al. show that these functions are rich enough to capture non-convex structure that exists in natural data.} \cite{Hazan2016Graduated}, we can prove that $\hat{f}$ is $\alpha$-exp-concave function (when $\alpha \leq \frac{\sigma \delta^2}{d^2F^2}$) \cite{Hazan2007Logarithmic}, which is a key property in the proof of \textbf{Theorem 1}.

Based on the merit of the equation $\mathop{\mathbb{E}}_{\mat{v}\sim U_{\mathbb{S}}}[\frac{d}{\delta}f(\mat{x}+\delta\mat{v})\mat{v}]=\nabla\hat{f}(\mat{x})$, we extend the ONS to the setting of limited feedback and propose a novel second-order online learning method - Online Newton Step algorithm with Estimated Gradient algorithm (ONSEG). The proposed ONSEG algorithm is summarized as follows:

\begin{algorithm}
	\caption{Online Newton Step Algorithm with Estimated Gradient (ONSEG)}
	\LinesNumbered
	\KwIn{$d, F, D, \sigma, r, T$}
	{\bf Initialize}: $\delta, \gamma$ \\
 Set $\alpha = \frac{\sigma \delta^2}{d^2F^2}$, $\beta=\frac{1}{2}\min\left\lbrace \frac{\delta}{4dFD},\alpha\right\rbrace$, $\varepsilon=\frac{1}{\beta^{2}D^{2}}$, $\mat{A}_{0}=\varepsilon \mat{I}_{d}$\\
	Specify the starting point $\mat{y}_{1}=\mat{0}$\\
	\For{t=1:T}{
		Select the unit vector $\mat{v}_{t}$ uniformly at random\\
		$\mat{x}_{t}=\mat{y}_{t} + \delta\mat{v}_{t}$\\
		$\mat{g}_{t}=\frac{d}{\delta}f_{t}(\mat{x}_{t})\mat{v}_{t}$\\
		$\mat{A}_{t}=\mat{A}_{t-1}+\mat{g}_{t}\mat{g}_{t}^{T}$\\
		$\mat{y}_{t+1}=\varPi_{(1-\gamma)\mathcal{P}}^{\mat{A}_{t}}[\mat{y}_{t}-\frac{1}{\beta}\mat{A}_{t}^{-1}\mat{g}_{t}]$, where $\varPi_{(1-\gamma)\mathcal{P}}^{\mat{A}_{t}}$ is the projection in norm induced by $\mat{A}_{t}$, viz\\
		$\varPi_{(1-\gamma)\mathcal{P}}^{\mat{A}_{t}}[\mat{y}]\triangleq\mathop{\arg\min}_{\mat{x}\in(1-\gamma)\mathcal{P}} \|\mat{y}-\mat{x}\| _{\mat{A}_{t}}$
	}
\end{algorithm}

In the following, we give the regret analysis of the proposed \emph{Online Newton Step Algorithm with Estimated Gradient} (ONSEG).
\begin{comment}
\newtheorem{observation}{Observation}
\begin{observation}\label{ob sets}
	The optimum in $(1-\gamma)\mathcal{P}$ is near the optimum in $\mathcal{P}$:
	$$
	\mathop{\min}_{\mat{x}\in(1-\gamma)\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{x})\leq2\gamma FT+\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{x}).
	$$
\end{observation}
$\mat{Proof}$:
It is clear that:
$$\mathop{\min}_{\mat{x}\in(1-\gamma)\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{x})=	\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}((1-\gamma)\mat{x}).$$
Since $\mat{0}\in\mathcal{P}$ and $|f_{t}(\mat{x})|\leq F$ hold for all $\mat{x}\in\mathcal{P}$ and $t\in\{1,\cdots,T\}$, we have:
\begin{eqnarray*}
	\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}((1-\gamma)\mat{x})
	&\leq&\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}\gamma f_{t}(\mat{0})+(1-\gamma)f_{t}(\mat{x})\\
	&=&\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}\gamma (f_{t}(\mat{0})-f_{t}(\mat{x}))+f_{t}(\mat{x})\\
	&\leq&\mathop{\min}_{\mat{x}\in\mathcal{P}}\sum_{t=1}^{T}\gamma2F+f_{t}(\mat{x}).
\end{eqnarray*}

\begin{observation}\label{ob radius}
	For any point $\mat{x}\in(1-\gamma)\mathcal{P}$, the ball of radius $\gamma r$ centered at $\mat{x}$ is contained in $\mathcal{P}$.
\end{observation}
$\mat{Proof:}$
Since $r\mathbb{B}\subseteq\mathcal{P}$ and $\mathcal{P}$ is convex, we have
$
(1-\gamma)\mathcal{P}+\gamma r\mathbb{B}\subseteq(1-\gamma)\mathcal{P}+\gamma\mathcal{P}=\mathcal{P}.
$
The next observation establishes a bound on the maximum value the function value can reach in $(1-\gamma)\mathcal{P}$, which is an implicit Lipschitz condition.

\begin{observation}\label{ob L-Lipschitz}
	For any $\mat{y}\in (1-\gamma)\mathcal{P}$ and any $\mat{x} \in \mathcal{P}$, we have:
	$$|f_{t}(\mat{x})-f_{t}(\mat{y})|\leq\frac{2F}{\gamma r}\|\mat{x}-\mat{y}\|.$$
\end{observation}
$\mat{Proof}$:
Let $\mat{x}=\mat{y}+\Delta$. If $|\Delta|>\gamma r$, the observation follows directly from $|f_{t}|\leq F$. Otherwise, let $\mat{z}=\mat{y}+\gamma r\frac{\Delta}{|\Delta|}$, which is the point at distance $\gamma r$ from $\mat{y}$ in the direction $\Delta$. By the previous observation, we know $\mat{z}\in\mathcal{P}$. Also, $\mat{x}=\frac{|\Delta|}{\gamma r}\mat{z}+\left(1-\frac{|\Delta|}{\gamma r}\right)\mat{y}$, so we have:
\begin{eqnarray*}
	f_{t}(\mat{x})
	&\leq&\frac{|\Delta|}{\gamma r}f_{t}(\mat{z})+\left(1-\frac{|\Delta|}{\gamma r}\right)f_{t}(\mat{y})\\
	&=&f_{t}(\mat{y})+\frac{f_{t}(\mat{z})-f_{t}(\mat{y})}{\gamma r}|\Delta|\\
	&\leq&f_{t}(\mat{y})+\frac{2F}{\gamma r}|\Delta|.
\end{eqnarray*}
\end{comment}
\begin{theorem}\label{theorem without L}
Assume that for all t, function $f_{t}:\mathcal{P}\rightarrow \mathbb{R}$ is $\sigma$-nice function (see \cite{Hazan2016Graduated}).
For all $\mat{y}$ in $\mathcal{P}$,

	$|f_t(\mat{y})|\leq F$, with the notation of $\nabla_{t} \triangleq \nabla\hat{f}_{t}$,

	we have $\|\nabla_{t}\|\leq\frac{d}{\delta}F.$
	For $\delta=\sqrt[3]{\frac{25d^4D^2{\log}^2 Tr}{3T^2}}$, $\gamma = \sqrt[3]{\frac{15d^2D\log T}{rT}}$, and $\alpha=\frac{\sigma \delta^2}{d^2F^2}$ ONSEG gives the following guarantee on the expected regret bound:

			\begin{equation*}
			\mathbb{E}\left[\sum_{t=1}^Tf_t(\mat{x}_t)\right] - \min_{\mat{x}\in \mathcal{P}}\sum_{t=1}^{T}f_t(\mat{x}) \leq6FT^{\frac{2}{3}}\sqrt[3]{\frac{15d^{2}D
					\log T}{r}}+\frac{5d}{\alpha}\log T.
			\end{equation*}

\end{theorem}
$\mat{Proof}$:
For any $\mat{y}_t\in(1-\gamma)\mathcal{P}$, OBSERVATION 3.2 in \cite{Flaxman2005Online}
shows that with a proper setting of the parameters $\frac{\delta}{r}\leq \gamma<1$,
the picked points $\mat{x}_t=\mat{y}_t+\delta\mat{v}_t\in \mathcal{P}$. Suppose we run the ONS algorithm on the functions $\hat{f}_t$ (i.e., the smoothed function of $f_t$) on the feasible set $(1-\gamma)\mathcal{P}$. Let $\mat{g}_t=\frac{d}{\delta}f_t(\mat{y}_t+\delta\mat{v}_t)\mat{v}_t$, then
LEMMA 2.1 in \cite{Flaxman2005Online}
shows that $\mathbb{E}\left[\mat{g}_t|\mat{y}_t\right]=\nabla\hat{f}_t(\mat{y}_t)$. For convenience, we denote $\nabla\hat{f}_t(\mat{y}_t)$ as $\nabla_t$ in the following context.
We first show that the following formulation provides an upper bound of the expected regret:
\begin{equation*}
\mathbb{E}\left[\sum_{t=1}^T\hat{f}_t(\mat{y}_t)\right] - \min_{\mat{y}\in (1-\gamma)\mathcal{P}}\sum_{t=1}^{T}\hat{f}_t(\mat{y}) \leq\frac{10d^{2}FD\log T}{\delta}+\frac{5d}{\alpha}\log T.
\end{equation*}

Let $\mat{y}^{\star}\in\mathop{\arg \min}_{\mat{y}\in(1-\gamma)\mathcal{P}}\sum_{t=1}^{T}\hat{f}_{t}(\mat{y})$ denotes the best chosen with the benefit of hindsight. By
Lemma 3 \cite{Hazan2007Logarithmic}, we have:
\begin{eqnarray}\label{f-f_hat}
&&\hat{f}_{t}(\mat{y}_{t})-\hat{f}_{t}(\mat{y}^{\star})\leq R_{t}\\
&\overset{\triangle}{=}& \nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})-\frac{\beta}{2}(\mat{y}^{\star}-\mat{y}_{t})^{T}\nabla_{t}\nabla_{t}^{T}(\mat{y}^{\star}-\mat{y}_{t})\notag
\end{eqnarray}
for $\beta=\frac{1}{2}\min\left\lbrace \frac{\delta}{4dFD},\alpha\right\rbrace.$ For convenience, we can define $\mat{z}_{t+1}=\mat{y}_{t}-\frac{1}{\beta}\mat{A}_{t}^{-1}\nabla_{t}$ according to the update rule of $\mat{y}_{t+1}=\varPi_{(1-\gamma)\mathcal{P}}^{\mat{A}_{t}}[\mat{z}_{t+1}].$ In this way, by the definition of $\mat{z}_{t+1}$, we have:
\begin{equation}\label{y_t+1-x^star}
\mat{z}_{t+1}-\mat{y}^{\star}=\mat{y}_{t}-\mat{y}^{\star}-\frac{1}{\beta}\mat{A}_{t}^{-1}\nabla_{t},
\end{equation}
\vspace{-0.1in}
\begin{equation}\label{A_t(y_t+1-x^star)}
\mat{A}_{t}(\mat{z}_{t+1}-\mat{y}^{\star})=\mat{A}_{t}(\mat{y}_{t}-\mat{y}^{\star})-\frac{1}{\beta}\nabla_{t}.
\end{equation}
Multiplying the transpose of Eq.\eqref{y_t+1-x^star} by Eq.\eqref{A_t(y_t+1-x^star)} we get:
\begin{small}
\begin{equation}\label{(y_t+1-x^star)^TA_t(y_t+1-x^star)}
(\mat{z}_{t+1}-\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{z}_{t+1}-\mat{y}^{\star})=(\mat{y}_{t}-\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{y}_{t}-\mat{y}^{\star})\notag
-\frac{2}{\beta}\nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})+\frac{1}{\beta^{2}}\nabla_{t}^{T}\mat{A}_{t}^{-1}\nabla_{t}.
\end{equation}
\end{small}
\noindent Since $\mat{y}_{t+1}$ is the projection of $\mat{z}_{t+1}$ in the norm that can be induced by $\mat{A}_{t}$, we can obtain that (See Lemma 8 \cite{Hazan2007Logarithmic}):
$$
(\mat{z}_{t+1}-\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{z}_{t+1}-\mat{y}^{\star})\geq	(\mat{y}_{t+1}-\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{y}_{t+1}-\mat{y}^{\star}).
$$
This inequality justifies the reason of using the generalized projections rather than the standard projections. This fact together with Eq.\eqref{(y_t+1-x^star)^TA_t(y_t+1-x^star)} gives:
\begin{scriptsize}
\begin{eqnarray*}
\nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})\leq \frac{\beta}{2}(\mat{y}_{t}-
\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{y}_{t}-\mat{y}^{\star})+\frac{1}{2\beta}\nabla_{t}^{T}\mat{A}_{t}^{-1}\nabla_{t} -\frac{\beta}{2}(\mat{y}_{t+1}-\mat{y}^{\star})^{T}\mat{A}_{t}(\mat{y}_{t+1}
-\mat{y}^{\star}).
\end{eqnarray*}
\end{scriptsize}
Now, by summing up over $t$ from $1$ to $T$, it leads to the following inequality:
\begin{eqnarray*}
	\sum_{t=1}^{T}\nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})
&\leq&\frac{1}{2\beta}\sum_{t=1}^{T}\nabla_{t}^{T}\mat{A}_{t}^{-1}\nabla_{t}+
	\frac{\beta}{2}(\mat{y}_{1}-\mat{y}^{\star})^{T}\mat{A}_{1}(\mat{y}_{1}-\mat{y}^{\star})\\
	&&+\frac{\beta}{2}\sum_{t=2}^{T}(\mat{y}_{t}-\mat{y}^{\star})^{T}(\mat{A}_{t}-\mat{A}_{t-1})(\mat{y}_{t}-\mat{y}^{\star})\\
	&&-\frac{\beta}{2}(\mat{y}_{T+1}-\mat{y}^{\star})^{T}\mat{A}_{T}(\mat{y}_{T+1}-\mat{y}^{\star})\\ &\leq&\frac{1}{2\beta}\sum_{t=1}^{T}\nabla_{t}^{T}\mat{A}_{t}^{-1}\nabla_{t}+\frac{\beta}{2}\sum_{t=1}^{T}(\mat{y}_{t}-\mat{y}^{\star})^{T}
	\nabla_{t}\nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})\\
	&&+\frac{\beta}{2}(\mat{y}_{1}-\mat{y}^{\star})^{T}(\mat{A}_{1}-\nabla_{1}\nabla_{1}^{T})(\mat{y}_{1}-\mat{y}^{\star}).
\end{eqnarray*}
It should be noted that we use the fact that $\mat{A}_{t}-\mat{A}_{t-1}=\nabla_{t}\nabla_{t}^{T}.$ in the last inequality. By moving the term  $\frac{\beta}{2}\sum_{t=1}^{T}(\mat{y}_{t}-\mat{y}^{\star})^{T}\nabla_{t}\nabla_{t}^{T}(\mat{y}_{t}-\mat{y}^{\star})$ to the LHS, it leads to the expression for $\sum_{t=1}^{T}R_{t}.$

Using the facts that $\mat{A}_{1}-\nabla_{1}\nabla_{1}^{T}=\varepsilon\mat{I}_{d}$ and $\|\mat{y}_{1}-\mat{y}^{\star}\|^{2}\leq D^{2}$, and the choice of $\varepsilon=\frac{1}{\beta^{2}D^{2}}$ we get:
\begin{eqnarray*}
&&\sum_{t=1}^{T}(\hat{f}_{t}(\mat{y}_{t})-\hat{f}_{t}(\mat{y}^{\star}))\leq\sum_{t=1}^{T}R_{t}\\
&\leq&\frac{1}{2\beta}\sum_{t=1}^{T}\nabla_{t}^{T}\mat{A}_{t}^{-1}\nabla_{t}+\frac{\varepsilon}{2}R^{2}\beta\\

&\leq&\frac{1}{2\beta}\sum_{t=1}^{T}\|\nabla_{t}\|^2_{\mat{A}_{t}^{-1}}+\frac{1}{2\beta}.
\end{eqnarray*}
Taking expectation, and using the fact that $\mathbb{E}[\mat{g}_t]=\nabla_t$, we obtain:
\begin{equation}\label{eq exp-bound}
\mathbb{E}\left[\sum_{t=1}^{T}(\hat{f}_{t}(\mat{y}_{t})-\hat{f}_{t}(\mat{y}^{\star}))\right]
\leq\frac{1}{2\beta}\sum_{t=1}^{T}\|\mathbb{E}[\mat{g}_{t}]\|^2_{\mat{A}_{t}^{-1}}+\frac{1}{2\beta}.
\end{equation}
According to Lemma 11 in \cite{Hazan2007Logarithmic},
Eq.\eqref{eq exp-bound} can be bounded by $\frac{d}{2\beta}\log(\frac{d^{2}F^{2}T}{\delta^{2}\varepsilon}+1)$, via the setting of $\mat{V}_{t}=\mat{A}_{t}$, $\mat{u}_{t}=\nabla_{t}$, and $r=\frac{dF}{\delta}$. Now since $\varepsilon=\frac{1}{\beta^{2}D^{2}}$, and $\beta=\frac{1}{2}\min\left\lbrace \frac{\delta}{4dFD},\alpha\right\rbrace$, we have $\beta\leq\frac{\delta}{8dFD}$ and $\frac{1}{2\beta}\leq4\left(\frac{2dFD}{\delta}+\frac{1}{\alpha}\right)$. Then we get:
\begin{eqnarray*}
	&&\mathbb{E}\left[\sum_{t=1}^{T}\hat{f}_{t}(\mat{y}_{t})\right] -\mathop{\min}_{\mat{y}\in (1-\gamma)\mathcal{P}}\sum_{t=1}^{T}\hat{f}_{t}(\mat{y})\\
	&\leq& \frac{1}{2\beta}\left[ d\log(\frac{d^{2}F^{2}T}{\delta^{2}\varepsilon}+1)+1\right]  \\
	&\leq&4(\frac{2dFD}{\delta}+\frac{1}{\alpha})\left[ d\log T+1\right] \\
	&\leq&\frac{10d^{2}FD}{\delta}\log T+\frac{5d}{\alpha}\log T.
\end{eqnarray*}

Let $L=\frac{2F}{\gamma r}$ be as given in
OBSERVATION 3.3 \cite{Flaxman2005Online}.
For any $\mat{y}_t\in(1-\gamma)\mathcal{P}$, as $\hat{f}_t$ is the average of $\mat{y}_t$  within $\delta$,
OBSERVATION 3.3 in \cite{Flaxman2005Online}
shows that $|\hat{f}(\mat{y}_t)-f(\mat{x}_t)|\leq|\hat{f}(\mat{y}_t)-f(\mat{y}_t)|+|{f}(\mat{y}_t)-f(\mat{x}_t)|\leq 2\delta L$.
According to
OBSERVATION 3.1 in \cite{Flaxman2005Online},
we have $\min_{\mat{x}\in(1-\gamma)\mathcal{P}} f(\mat{x}) \leq 2\gamma F + \min_{\mat{x}\in\mathcal{P}} f(\mat{x})$. With these above observations, we can obtain the expectation regret upper bound of ONSEG as:
\begin{eqnarray}
& & \mathbb{E}\left[\sum_{t=1}^{T}f_{t}(\mat{y}_{t}+\delta \mat{v}_{t})\right] -\mathop{\min}_{\mat{y}\in \mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{y})\nonumber \\
&\leq& \mathbb{E}\left[ \sum_{t=1}^{T}f_{t}(\mat{y}_{t}+\delta \mat{v}_{t})\right] -\mathop{\min}_{\mat{y}\in (1-\gamma)\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mat{y})+2\gamma FT\nonumber\\
&\leq& \mathbb{E}\left[ \sum_{t=1}^{T}\hat{f}_{t}(\mat{y}_{t})\right] -\mathop{\min}_{\mat{y}\in (1-\gamma)\mathcal{P}}\sum_{t=1}^{T}\hat{f}_{t}(\mat{y})+3L\delta T+2\gamma FT\nonumber\\
&\leq& \frac{10d^{2}FD}{\delta}\log T+3L\delta T+2\gamma FT+\frac{5d}{\alpha}\log T.\label{general results}
\end{eqnarray}

By plugging in $L=\frac{2F}{\gamma r}$, we get the expression of the form $\frac{a}{\delta}+b\frac{\delta}{\gamma}+c\gamma$, where $a=10d^{2}FD\log T$, $b=\frac{6FT}{r}$ and $c=2FT$. Setting $\delta=\sqrt[3]{\frac{a^{2}}{bc}}$ and $\gamma=\sqrt[3]{\frac{ab}{c^{2}}}$ gives a value of $3\sqrt[3]{abc}$. This gives the stated expected regret bound.%

\begin{comment}
\begin{lemma}\label{lemma:2}
	For a function $ \hat{f}:(1-\gamma)\mathcal{P}\rightarrow \mathbb{R}$, where $\mathcal{P}$ has a diameter D, such that $\forall \mat{x}\in (1-\gamma)\mathcal{P}$, $\|\nabla \hat{f}(\mat{x})\|\leq \frac{dF}{\delta}$ and $\exp{(-\alpha\hat{f}(\mat{x}))}$ is concave, the following holds for $\beta\leq\frac{1}{2} \min\left\lbrace \frac{\delta}{4dFD},\alpha\right\rbrace  $:
	$
	\forall \mat{x},\mat{y}\in (1-\gamma)\mathcal{P}:\hat{f}(\mat{x})\geq\hat{f}(\mat{y})+\nabla\hat{f}(\mat{y})^{T}(\mat{x}-\mat{y})+\frac{\beta}{2}(\mat{x}-\mat{y})^{T}\nabla\hat{f}(\mat{y})\nabla\hat{f}(\mat{y})^{T}(\mat{x}-\mat{y}).
	$
\end{lemma}
$\mat{Proof:}$
Since $\exp{(-\alpha\hat{f}(\mat{x}))}$ is concave and $2\beta\leq\alpha$, the function $h(\mat{x})\overset{\triangle}{=}\exp{(-2\beta\hat{f}(\mat{x}))}$ is also concave. Then by the concavity of $h(\mat{x})$, we have:
$$
h(\mat{x})\leq h(\mat{y})+\nabla h(\mat{y})^{T}(\mat{x}-\mat{y}).
$$
Plugging in $\nabla h(\mat{y})=-2\beta \exp{(-2\beta\hat{f}(\mat{y}))}\nabla\hat{f}(\mat{y})$ gives:
$$
\hat{f}(\mat{x})\geq\hat{f}(\mat{y})-\frac{1}{2\beta}\log[1-2\beta\nabla\hat{f}(\mat{y})^{T}(\mat{x}-\mat{y})].
$$
Next, note that $|2\beta\nabla\hat{f}(\mat{y})^{T}(\mat{x}-\mat{y})|\leq2\beta dFD/\delta\leq\frac{1}{4}$ and that for $|z|\leq\frac{1}{4}$, $-\log(1-z)\geq z+\frac{1}{4}z^{2}.$ Applying the inequality for $z=2\beta\nabla\hat{f}(\mat{y})^{T}(\mat{x}-\mat{y})$ completes the proof of the lemma.

\begin{lemma}[Folklore]\label{folklore}
	Let $\mathcal{P}\subseteq\mathbb{R}^{d}$ be a convex set, $\mat{y}\in \mathbb{R}^{d}$ and $\mat{z}=\varPi_{\mathcal{P}}^{\mat{A}}[\mat{y}]$ be the generalized projection of $\mat{y}$ onto $\mathcal{P}$ according to the positive semidefinite matrix $\mat{A}\succeq 0.$ Then for any point $\mat{a}\in \mathcal{P}$ it holds that \cite{Hazan2007Logarithmic}:
	$$
	(\mat{y}-\mat{a})^{T}\mat{A}(\mat{y}-\mat{a})\geq	(\mat{z}-\mat{a})^{T}\mat{A}(\mat{z}-\mat{a}).
	$$
\end{lemma}

\begin{lemma}\label{matrix algebra}
	Let $\mat{u}_{t}\in\mathbb{R}^{d}$, for $t=1,\cdots,T$, be a sequence of vectors such that for some $r>0$, $\| \mat{u}_{t}\|\leq r$. Define $\mat{V}_{t}=\sum_{\tau=1}^{t}\mat{u}_{\tau}\mat{u}_{\tau}^{T}+\varepsilon \mat{I}_{d}$. Then we have:
	$$
	\sum_{t=1}^{T}\mat{u}_{t}^{T}\mat{V}_{t}^{-1}\mat{u}_{t}\leq d\log\left(\frac{r^{2}T}{\varepsilon}+1\right).
	$$
\end{lemma}
$\mat{Proof:}$
For real numbers $a>b>0$, the inequality $1+x\leq e^{x}$ implies that $\frac{1}{a}(a-b)\leq\log\frac{a}{b}$ (taking $x=\frac{b}{a}-1$). A similar fact holds for the positive definite matrices. Now, we define the inner product of two matrices $\mat{A},\mat{B}\in\mathbb{R}^{d\times d}$ as $\mat{A}\bullet\mat{B}=\sum_{i,j=1}^{d}\mat{A}_{ij}\mat{B}_{ij}$. Then, for matrices $\mat{A}\succeq\mat{B}\succ 0$, we have $\mat{A}^{-1}\bullet(\mat{A}-\mat{B})\leq\log\frac{|\mat{A}|}{|\mat{B}|}$, where $|\mat{A}|$ is the determinant of $\mat{A}$. Using the above facts, we have (for convenience, let $\mat{V}_{0}=\varepsilon \mat{I}_{d}$):
\begin{eqnarray*}
	&&\sum_{t=1}^{T}\mat{u}_{t}^{T}\mat{V}_{t}^{-1}\mat{u}_{t}
	=\sum_{t=1}^{T}\mat{V}_{t}^{-1}\bullet\mat{u}_{t}\mat{u}_{t}^{T}\\
	&=&\sum_{t=1}^{T}\mat{V}_{t}^{-1}\bullet(\mat{V}_{t}-\mat{V}_{t-1})\\
	&\leq&\sum_{t=1}^{T}\log\frac{|\mat{V}_{t}|}{|\mat{V}_{t-1}|}=\log\frac{|\mat{V}_{T}|}{|\mat{V}_{0}|}.
\end{eqnarray*}
Since $\mat{V}_{T}=\sum_{t=1}^{T}\mat{u}_{t}\mat{u}_{t}^{T}+\varepsilon\mat{I}_{d}$ and $\|\mat{u}_{t}\|\leq r$, the largest eigenvalue of $\mat{V}_{T}$ is at most $r^{2}T+\varepsilon$. Hence, the determinant of $\mat{V}_{T}$ can be bounded by $|\mat{V}_{T}|\leq(r^{2}T+\varepsilon)^{d}.$

Under the Lipschitzness of $f_t$, it is clearly that the difference of $f $ and its smoothed version $\hat{f}$  is no more than $L\delta$ .
And we can further tighten the expected upper bound of the proposed ONSEG algorithm to $\mathcal{O}(\sqrt{T})$.
\end{comment}

\begin{theorem}
In the proposed Online Newton Step Algorithm with Estimated Gradient, if each function $f_{t}$ is $L$-Lipschitz, then for $\delta=T^{-\frac{1}{2}}\sqrt{\frac{10d^{2}FDr\log T}{3(Lr+F)}}$ and $\gamma=\frac{\delta}{r}$, we have:
\begin{equation*}
	\mathbb{E}\left[\sum_{t=1}^Tf_t(\mat{x}_t)\right] - \min_{\mat{x}\in \mathcal{P}}\sum_{t=1}^{T}f_t(\mat{x}) \leq2dT^{\frac{1}{2}}\sqrt{\frac{30FD(Lr+F)\log T}{r}}+\frac{5d}{\alpha}\log T.
\end{equation*}
\end{theorem}
$\mat{Proof:}$
The proof is similar to the proof of Theorem \ref{theorem without L}. We now have an explicit Lipschitz constant, thus we can use it directly in Eq.\eqref{general results}. Plugging the chosen values of $\delta$ and  $\gamma=\frac{\delta}{r}$ gives the theorem.

\section{Empirical Evaluations}
\vspace{-0.1in}
\begin{table}[htbp]\centering
	\caption{Statistics of the datasets used in the experiments.}
	\begin{tabular}{|c|c|c|c|}\hline
		Dataset & $n$ & $d$ & type \\
		\hline
		abalone       &  4177    &  7       & regression  \\ \hline
		kin               &  3000  &  8       & regression      \\ \hline
		ionosphere  &  351     &  33     & classification     \\ \hline
		cancer    &  683     &  9   & classification      \\ \hline
		{SSE 180}    & {680}   &  {94}   & {portfolio}      \\ \hline
	\end{tabular}\label{tab datasets}
\end{table}

Empirical evaluations of the proposed method was performed on two regression datasets, two classification datasets, and one stock dataset, they are abalone, kin, ionosphere, cancer, and SSE 180. All datasets can be download from the libSVM repository\footnote{\url{https://www.csie.ntu.edu.tw/\~cjlin/libsvmtools/datasets/}} and EastMoney\footnote{\url{http://choice.eastmoney.com/}}
(see Table 1 for details of each dataset). We compare the proposed second-order bandit learning algorithm ONSEG with the first-order bandit learning algorithm OGDEG \cite{Flaxman2005Online}. In addition, in the scenario of online regression and online classification problems, OGD and ONS are baseline methods with the full information feedback.
To accelerate the computational efficiency, ONSEG and ONS employ Sherman-Morrson-Woodbury formula \cite{Brookes2011The}
$$
 (\mat{A}_t + \mat{g}_t\mat{g}_t^T)^{-1} = \mat{A}_t^{-1} - \frac{\mat{A}_t^{-1}\mat{g}_t\mat{g}_t^T\mat{A}_t^{-1}}{1+\mat{g}_t^T\mat{A}_t^{-1}\mat{g}_t}
$$
to compute $\mat{A}_{t+1}^{-1}$ in time $\mathcal{O}(d^{2})$ using only matrix-vector and vector-vector products after given $\mat{A}_{t}^{-1}$ and $\mat{g}_{t}$.
All experiments are performed in MATLAB 7.14 environment on
a single computer with 3.4 GHz Intel Core i5 processors and
8G RODRAM running under the Windows 10 operating system. The source code of the proposed ONSEG algorithm will be released upon the acceptance of the manuscript.

\paragraph{Online Regression}
We first evaluate different methods in terms of regression on the abalone and kin datasets. We select the least square loss $f_{t}(\mat{x})=\frac{1}{2}(\langle \mat{x}, \mat{z}_{t}\rangle-y_{t})^{2}$ as the loss function, and use the mean squared error $F(\mat{X}^t)\triangleq\frac{1}{t}\sum_{i=1}^{t}f_{i}(\mat{x}_i)$ as the metric to evaluate different online learning algorithms, i.e., ONSEG, ONS, OGDEG, and OGD. Parameter settings of all the compared methods are as follows: OGD sets the step size $\eta_{t}=\frac{D}{G\sqrt{t}}$, which changes with the increase of $t$ \cite{Hazan2006Efficient}. Similarly, OGDEG sets the step size $\nu=\frac{D}{F\sqrt{t}}$ \cite{Flaxman2005Online}. For ONS, we estimate $\beta=4.8501\times10^{-4}$ for the abalone dataset and $\beta=3.8063\times10^{-4}$ for the kin dataset according to \cite{Hazan2007Logarithmic}. And in ONSEG, the smoothed parameter $\delta$ is set as Theorem 1 and the reciprocal of the step size, i.e. $\beta$, is estimated to be $\beta=3.2813\times10^{-6}$ for abalone and $\beta=1.4715\times10^{-5}$ for kin. The experiments are performed over $T=150n$ iterations and the results are depicted in Figure \ref{Fig. mse}. $F(\mat{X}^t)$ reports the mean squared error of different algorithms w.r.t. number of iterations $t$. As expected, the proposed ONSEG outperforms OGDEG, showing it converges faster. And also, in terms of the running time, we can also find that the proposed ONSEG is much more efficient than methods that require gradient such as ONS and OGD.

\begin{figure*}[htbp]
	\begin{center}{
			\includegraphics[width=12cm]{pic1.jpg}}
	\end{center}
	{\caption{Comparison of different online learning algorithms (ONSEG, ONS, OGDEG and OGD) on the abalone and kin datasets w.r.t. regression.\label{Fig. mse}}}

\end{figure*}
\paragraph{Online Classification}
We evaluate different online learning methods in terms of the classification task. We select the logistic regression
$d(\mat{z}_t)=\frac{1}{1+\exp(-\langle \mat{x}, \mat{z}_{t}\rangle)}$ as the classifier, i.e., $\mathbb{P}(\hat{y}_t=1|\mat{z}_t)=d(\mat{z}_t)$. According to the maximum likelihood estimation principle, we define the loss function as $f_{t}(\mat{x})=\log(1+\exp(-y_{t}\langle \mat{x}, \mat{z}_{t}\rangle))$, where $y_t\in\{1,-1\}$.
Furthermore, the mean error rate is selected as the metric to evaluate different online learning algorithms. In this experiment, parameter settings are
similar to the last subsection. OGD sets the step size $\eta_{t}=\frac{D}{G\sqrt{t}}$. OGDEG sets the step size $\nu=\frac{D}{F\sqrt{t}}$. For ONS, we estimate $\beta=3.7\times10^{-3}$ for ionosphere and $\beta=2.5\times10^{-4}$ for cancer according to \cite{Hazan2007Logarithmic}. And in ONSEG, the smoothed parameter $\delta$ is set as Theorem 1, the reciprocal of the step size, i.e., $\beta$ is set to be $\beta=9.2022\times10^{-5}$ for ionosphere and $\beta=1.0948\times10^{-5}$ for cancer. Similarly, we run the experiments over $T=150n$ iterations. The empirical results are shown in Figure \ref{Fig me}. Generally, we have all the similar observations as the regression task.

\begin{figure*}[htpb]
	\begin{center}
		\includegraphics[width=12cm]{pic2.jpg}
	\end{center}
	\caption{Comparison of different online learning algorithms (ONSEG, ONS, OGDEG and OGD) on the ionosphere and cancer datasets w.r.t. classification.}
\label{Fig me}
\end{figure*}

\begin{figure*}[htpb]
	\begin{center}
		\includegraphics[width=8cm]{pic3.jpg}
	\end{center}
	\caption{Comparison of different online learning algorithms (ONSEG and OGDEG) on the stocks datasets w.r.t. online portfolio.}
	\label{Fig stock}
\end{figure*}

\paragraph{Online Portfolio}
We finally evaluate different bandit online learning methods in terms of the portfolio task \cite{Hazan2006Efficient}.
In this experiment, we use stock market data (94 stokes selected from stock index of Shanghai Stock Exchange) date from Feb 6$^{th}$, 2005 to Jan 31$^{th}$, 2019 (weekly data) to simulate the portfolio task, which is a limited information feedback scenario. ONS and OGD are no longer applicable due to the absence of gradient information. Hence, we only compare two bandit online learning algorithms here, i.e., OGDEG and ONSEG. We select the return rate function $f_{t}(\mat{x})=\langle \mat{x}, \mat{z}_{t}\rangle$ as the objective function where $\mat{x}$ satisfying $\|\mat{x}\|_1=1$ stands for the weighted vector of the portfolio, $\mat{z}_{t}$ denotes the vector of return rate corresponding to the current portfolio.
The mean return rate (mean weekly percentage yield) $F(\mat{X}^t)\triangleq\frac{1}{t}\sum_{i=1}^{t}f_{i}(\mat{x}_i)$ is selected as the metric to evaluate different bandit online learning algorithms.
Parameter settings of ONSEG and OGDEG are as follows: OGDEG sets the step size $\nu=\frac{D}{F\sqrt{t}}$; ONSEG sets the smoothed parameter $\delta$ as Theorem 1, the reciprocal of the step size, i.e., $\beta$ as $8.7142\times10^{-5}$.
We report the average return rate (over 100 trials of 94 random stocks from the SSE 180) of the algorithms in Figure \ref{Fig stock}. As expected, the proposed ONSEG with 2.88\%
mean weekly percentage yields outperforms OGDEG with 1.02\% return rate, showing that the proposed ONSEG is more efficient than OGDEG in the limited feedback information situation.

As a summary, expected gradient algorithms such as the proposed ONSEG are faster than the gradient algorithms such as ONS and OGD. In addition, the proposed second-order online learning method ONSEG converges faster than the first-order method OGDEG in the bandit feedback scenario. Hence, ONSEG provides a principled way to deal with large-scale bandit learning problems.

\section{Related Work}
In this section, we briefly review related work on bandit convex optimization algorithms which are closely related to the proposed ONSEG algorithm.
The recent studies of bandit convex optimization were largely pioneered by \cite{Kleinberg2004Nearly} and \cite{Flaxman2005Online}.
In particular, \cite{Flaxman2005Online} proposed to use a simple trick to approximate the gradient of a function with a single data sample. Meanwhile, the authors provided an intuitive understanding of the approximation through the gradient of a smoothed function and proved that the proposed algorithm with a one-point estimate of the gradient achieve an expected regret bound as $\mathcal{O}(T^{{5}/{6}})$ for convex bounded loss. For the setting of Lipschitz-continuous convex loss, a bound of $\mathcal{O}(T^{{3}/{4}})$ were obtained by \cite{Kleinberg2004Nearly} and \cite{Flaxman2005Online}. To improve the regret bound of bandit online learning, numerous learning algorithms have been proposed.
Among them, \cite{Dani2007The} proposed the Geometric Hedge algorithm that results in an optimal regret bound of $\mathcal{O}(\sqrt{T})$ for linear loss functions.
Motivated by the interior point methods, \cite{Abernethy2008Competing} proposed a new algorithm that achieves the same nearly-optimal regret bound for the linear optimization problem in bandit scenario.

For some specifical classes of nonlinear convex losses, several methods have been proposed \cite{Saha2011Improved,Bubeck2017Kernel,Yang2016Optimistic,Hazan2016Graduated,Hazan2014Bandit}.
Under the assumption of strongly convex loss, \cite{Agarwal2010Optimal} obtained an upper bound of $\mathcal{O}(T^{{2}/{3}})$.
The follow-up work \cite{Saha2011Improved} showed that for convex and smooth loss functions, we can make use of FTRL with a self-concordant barrier as regularization and attain a regret bound of $\mathcal{O}(T^{{2}/{3}})$ by sampling around the Dikin ellipsoid. In a recent paper, Hazan and Levy~\cite{Hazan2014Bandit} investigated the bandit convex optimization problem. Specifically, they assumed that the adversary is limited to choose strongly convex and smooth loss functions while the player have options to choose points from a constrained set. In this setting, they developed an algorithm that achieves a regret bound of $\mathcal{O}(\sqrt{T})$.
While a recent paper by \cite{Shamir2013On} shows that the lower bound of regret has to be $\Omega(\sqrt{T})$ even with the strongly convex and smooth assumptions.

\section{Conclusions}
In this paper, we propose a novel second-order online learning algorithm by extending the ONS algorithm to the bandit feedback scenario where we do not have access to the gradient of the loss function. Specifically, we present a simple trick to approximate the gradient of instantaneous loss function by evaluating the function at a single point. Theoretically, we bound the expected regret as $\mathcal{O}(T^{2/3})$ which is superior to the existing first-order online bandit learning algorithms as they only achieved an expected regret bound of $\mathcal{O}(T^{5/6})$ under mild assumptions of the loss functions.
Under the further $L$-Lipschitz continuous assumption of the loss function $f_{t}$, we can tighten the regret upper bound as $\mathcal{O}(\sqrt T)$ which is often desired in practical usage.
Empirically, we also show that the proposed ONSEG algorithm results in a significant improvement over: (1) first-order bandit online learning algorithm OGDEG in terms of convergence rate; and (2) online learning methods that require gradient in terms of running time.

\bibliographystyle{spmpsci}


\section{Introduction}

\begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{cccc}
\hspace{-0.10cm}
\includegraphics[width=0.215\textwidth]{./csnowman/snowmanblur.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/snowmanET.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/snowman_tao.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/snowman_pan.pdf}\\%event_edges
\hspace{-0.20cm}
(a) The Blurry Image
&(b) The Events
&(c) Tao \etal \cite{Tao_2018_CVPR}
&(d) Pan \etal \cite{pan2017deblurring}\\
\hspace{-0.10cm}
\includegraphics[width=0.215\textwidth]{./csnowman/snowman_jin.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/scheerlinck_events.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/scheerlinck.pdf}
&\includegraphics[width=0.215\textwidth]{./csnowman/snowman_our3.pdf}\\
\hspace{-0.10cm}
(e) Jin \etal \cite{Jin_2018_CVPR}
&(f) {\small\begin{tabular}[c]{@{}c@{}}Scheerlinck \etal \cite{Scheerlinck18arxiv}\\ (events only)\end{tabular}}
&(g) Scheerlinck \etal \cite{Scheerlinck18arxiv}
&(h) Ours\\
\end{tabular}
}
\end{center}
\vspace{-3mm}
 \caption{\em \label{fig:eventdeblur}
Deblurring and reconstruction results of our method compared with the state-of-the-art methods on our real {\it blurry event dataset}.
(a) The input blurry image.
(b) The corresponding event data.
(c) Deblurring result of Tao \etal \cite{Tao_2018_CVPR}.
(d) Deblurring result of Pan \etal \cite{pan2017deblurring}.
(e) Deblurring result of Jin \etal \cite{Jin_2018_CVPR}. Jin uses video as training data to train a supervised model to perform deblur, where the video can also be considered as similar information as the event data.
(f)-(g) Reconstruction results of Scheerlinck \etal \cite{Scheerlinck18arxiv}, (f) from only events, (g) from combining events and frames.
(h) Our reconstruction result. (Best viewed on screen).
}
\vspace{-2mm}
\end{figure*}

Event cameras (such as the Dynamic Vision Sensor (DVS) \cite{lichtsteiner2008128} and the Dynamic and Active-pixel Vision Sensor (DAVIS) \cite{brandli2014240}) are sensors that asynchronously measure the intensity changes at each pixel independently with microsecond temporal resolution\footnote{If nothing moves in the scene, no events are triggered.}.
The event stream encodes the motion information by measuring the precise pixel-by-pixel intensity changes. Event cameras are more robust to low lighting and highly dynamic scenes than traditional cameras since they are not affected by under/over exposure or motion blur associated with a synchronous shutter.

Due to the inherent differences between event cameras and standard cameras, existing computer vision algorithms designed for standard cameras cannot be applied to event cameras directly. Although the DAVIS \cite{brandli2014240} can provide the simultaneous output of the intensity frames and the event stream, there still exist major limitations with current event cameras:
\begin{itemize}
    \item {\bf Low frame-rate intensity images:} In contrast to the high temporal resolution of event data ($\geq 3\mu s$ latency), the current event cameras only output low frame-rate intensity images ($\geq 5ms$ latency).
    \item {\bf Inherent blurry effects:} When recording highly dynamic scenes, motion blur is a common issue due to the relative motion between the camera and the scene. The output of the intensity image from the APS tends to be blurry.
\end{itemize}

To address these above challenges, various methods have been proposed by reconstructing high frame-rate videos. The existing methods can be in general categorized as \textbf{1}) Event data only solutions \cite{Bardow16cvpr, Reinbacher16bmvc, Barua16wcav}, where the results tend to lack the texture and consistency of natural videos, as they fail to use the complementary information contained in the low frame-rate intensity image;
\textbf{2}) Low frame-rate intensity-image-only solutions \cite{Jin_2018_CVPR}, where an end-to-end learning framework has been proposed to learn regression between a single blurry image and a video sequence, whereas the rich event data are not used; and \textbf{3}) Jointly exploiting event data and intensity images \cite{Scheerlinck18arxiv, Shedligeri18arxiv, Brandli14iscas}, building upon the interaction between both sources of information. However, these methods fail to address the blur issue associated with the captured image frame. Therefore, the reconstructed high frame-rate videos can be degraded by blur.

Although blurry frames cause undesired image degradation, they also encode the relative motion between the camera and the observed scene. Taking full advantage of the encoded motion information would benefit the reconstruction of high frame-rate videos.

To this end, we propose an {\textbf{Event-based Double Integral (EDI)}} model to resolve the above problems by reconstructing a high frame-rate video from a single image (even blur) and its event sequence, where the blur effects have been reduced in each reconstructed frame. Our EDI model naturally relates the desired high frame-rate sharp video, the captured intensity frame and event data. Based on the EDI model, high frame-rate video generation is as simple as solving a non-convex optimization problem in a single scalar variable.

Our main contributions are summarized as follows.
\begin{enumerate}[1)]
\item We propose a simple and effective model, named the Event-based Double Integral (EDI) model, to restore a high frame-rate sharp video from a single image (even blur) and its corresponding event data.
\vspace{-2mm}
\item Using our proposed formulation of EDI, we propose a stable and general method to generate a sharp video under various types of blur by solving a single variable non-convex optimization problem, especially in low lighting and complex dynamic conditions.
\vspace{-2mm}
\item The frame rate of our reconstructed video can theoretically be as high as the event rate (200 times greater than the original frame rate in our experiments).
\end{enumerate}

\section{Related Work}

Event cameras such as the DAVIS and DVS \cite{brandli2014240,lichtsteiner2008128} report log intensity changes, inspired by human vision. Although several works try to explore
the advantages of the high temporal resolution provided by event cameras \cite{zhou2018semi, Kim16eccv, Rebecq17ral, Zhu17cvpr,Zhu-RSS-18,Gehrig18eccv,Kueng16iros}, how to make the best use of the event camera has not yet been fully investigated.

{\noindent{\bf Event-based image reconstruction.}}
Kim \etal \cite{Kim14bmvc} reconstruct high-quality images from an event camera under a strong assumption that the only movement is pure camera rotation, and later extend their work to handle 6-degree-of-freedom motion and depth estimation \cite{Kim16eccv}.
Bardow \etal \cite{Bardow16cvpr} aim to simultaneously recover optical flow and intensity images.
Reinbacher \etal \cite{Reinbacher16bmvc} restore intensity images via manifold regularization.
Barua \etal \cite{Barua16wcav} generate image gradients by dictionary learning and obtain a logarithmic intensity image via Poisson reconstruction.
However, the intensity images reconstructed by the previous approaches suffer from obvious artifacts as well as lack of texture
due to the spatial sparsity of event data.

To achieve more image detail in the reconstructed images, several methods trying to combine events with intensity images have been proposed.
The DAVIS \cite{brandli2014240} uses a shared photo-sensor array to simultaneously output events (DVS) and intensity images (APS).
Scheerlinck \etal \cite{Scheerlinck18arxiv} propose an asynchronous event-driven complementary filter to combine APS intensity images with events, and obtain continuous-time image intensities.
Brandli \etal \cite{Brandli14iscas} directly integrate events from a starting APS image frame, and each new frame resets the integration.
Shedligeri \etal \cite{Shedligeri18arxiv} first exploit two intensity images to estimate depth. Then, they use the event data only to reconstruct a pseudo-intensity sequence (using \cite{Reinbacher16bmvc}) between the two intensity images and use the pseudo-intensity sequence to estimate ego-motion using visual odometry. Using the estimated 6-DOF pose and depth, they directly warp the intensity image to the intermediate location.
Liu \etal \cite{Liu17vc} assume a scene should have static background. Thus, their method needs an extra sharp static foreground image as input and the event data are used to align the foreground with the background.

\vspace{1mm}

{\noindent{\bf Image deblurring.}}
Traditional deblurring methods usually make assumptions on the scenes (such as a static scene) or exploit multiple images (such as stereo, or video) to solve the deblurring problem.
Significant progress has been made in the field of single image deblurring. Methods using gradient based regularizers, such as Gaussian scale mixture \cite{fergus2006removing}, $l_1 \backslash l_2$ norm \cite{krishnan2011blind}, edge-based patch priors \cite{sun2013edge} and ${l}_0$-norm regularizer \cite{xu2013unnatural}, have been proposed.
Non-gradient-based priors such as the color line based prior \cite{lai2015blur}, and the extreme channel (dark/bright channel) prior \cite{pan2017deblurring, yan2017image} have also been explored. Another family of image deblurring methods tends to use multiple images \cite{cho2012video, hyun2015generalized, sellent2016stereo, Pan_2017_CVPR, pan2018depth}.

Driven by the success of deep neural networks, Sun \etal \cite{sun2015learning} propose a convolutional neural network (CNN) to estimate locally linear blur kernels. Gong \etal \cite{gong2017motion} learn optical flow from a single blurry image through a fully-convolutional deep neural network. The blur kernel is then obtained from the estimated optical flow to restore the sharp image.
Nah \etal~\cite{Nah_2017_CVPR} propose a multi-scale CNN that restores latent images in an end-to-end learning manner without assuming any restricted blur kernel model. Tao \etal \cite{Tao_2018_CVPR} propose a light and compact network, SRN-DeblurNet, to deblur the image.
However, deep deblurring methods generally need a large dataset to train the model and usually require sharp images provided as supervision. In practice, blurry images do not always have corresponding ground-truth sharp images.

\vspace{1mm}
{\noindent{\bf Blurry image to sharp video.}}
Recently, two deep learning based methods \cite{Jin_2018_CVPR,purohit2018bringing} propose to restore a video from a single blurry image with a fixed sequence length.
However, their reconstructed videos do not obey the 3D geometry of the scene and camera motion.
Although deep-learning based methods achieve impressive  performance in various scenarios, their success heavily depend on the consistency between the training datasets and the testing datasets, thus hinder the generalization ability for real-world applications.

\section{Formulation}
In this section, we develop an {\bf EDI} model of the relationships between the events, the latent image and the blurry image.
Our goal is to reconstruct a high frame-rate, sharp video from a single image and its corresponding events.
This model can tackle various blur types and work stably in highly dynamic contexts and low lighting conditions.

\subsection{Event Camera Model}

Event cameras are bio-inspired sensors that asynchronously report logarithmic intensity changes \cite{brandli2014240,lichtsteiner2008128}. Unlike conventional cameras that produce the full image at a fixed frame-rate, event cameras trigger events whenever the change in intensity at a given pixel exceeds a preset threshold. Event cameras do not suffer from the limited dynamic ranges typical of sensors with synchronous exposure time, and are able to capture high-speed motion with microsecond accuracy.

Inherent in the theory of event cameras is the concept of the latent
image $L_{xy}(t)$, denoting the instantaneous intensity at pixel
$(x, y)$ at time $t$, related to the rate of photon arrival at that pixel.
The latent image $L_{xy}(t)$ is not directly output by the camera.
Instead, the camera outputs a sequence of {\em events},
denoted by $(x,y,t,\sigma)$, which record
changes in the intensity of the latent image.
Here, $(x, y)$ are image coordinates, $t$ is the time the event takes place, and polarity $\sigma = \pm 1 $ denotes the direction (increase or decrease) of the intensity change at
that pixel and time. Polarity is given by,
{\small
\begin{align} \label{eq:log}
\sigma = \mathcal{T}\left( \log \Big( \frac{\mathbf{L}_{xy}(t)}{\mathbf{L}_{xy}(t_\text{ref})} \Big) , c \right),
\end{align}
}
where $\mathcal{T}(\cdot,\cdot)$ is a truncation function,
{\small
\begin{equation} \nonumber \label{eq:pkmodel}
\mathcal{T}(d,c) =
\begin{cases}
+1, & d \geq c,\\
0, & d\in(-c,c),\\
-1, & d \leq -c.
\end{cases}
\end{equation}
}
Here, $c$ is a threshold parameter determining whether an event should be recorded or not, $\mathbf{L}_{xy}(t)$ is the intensity at pixel $(x,y)$ in the image $\mathbf{L}(t)$
and $t_\text{ref}$ denotes the timestamp of the previous event. When an event is triggered, $\mathbf{L}_{xy}(t_\text{ref})$ at that pixel is updated to a new intensity level

\begin{figure}[t]
\begin{center}
\begin{tabular}{cccc}
\includegraphics[width=0.215\textwidth]{./chadeblur/chablur.pdf}
&\includegraphics[width=0.215\textwidth]{./chadeblur/chaETMatrix.pdf}\\
(a) The Blurry Image
&(b) The Events\\
\includegraphics[width=0.215\textwidth]{./chadeblur/chaexpet.pdf}
&\includegraphics[width=0.215\textwidth]{./chadeblur/chaET_ig.pdf}\\
(c) $E(t) = \int e(t) \, dt$
&(d) $\frac{1}{T}\int \exp(c\,\mathbf{E}(t)) dt$\\%[0.1in]
\includegraphics[width=0.215\textwidth]{./chadeblur/chavideo/cha_50.pdf}
&\includegraphics[width=0.215\textwidth]{./chadeblur/chavideo/cha_200.pdf}\\
\multicolumn{2}{c}{(e) Sample Frames of Our Reconstructed Video}\\
\end{tabular}
\end{center}
\vspace{-3mm}
\caption{\label{fig:eventsample} \em The event data and our reconstructed result, where (a) and (b) are the input of our method. (a) The intensity image from the event camera.
(b) Events from the event camera plotted in 3D space-time $(x, y, t)$ (blue: positive event; red: negative event).
(c) The first integral of several events during a small time interval.
(d) The second integral of events during the exposure time.
(e)Samples from our reconstructed video from $\mathbf{L}(0)$ to $\mathbf{L}(200)$.
}
\end{figure}

\subsection{Intensity Image Formation}

In addition to the event sequence, event cameras can provide a full-frame
grey-scale intensity image, at a much slower rate than the event sequence.
The grey-scale images may suffer from motion blur due to their long exposure time. A general model  of image formation is given by,
{\small
\begin{equation} \label{eq:avgmodel}
\mathbf{B} =  \frac{1}{T}\int_{f-T/2}^{f+T/2} \mathbf{L}(t) \, dt,
\end{equation}
}
where $\mathbf{B}$ is a blurry image, equal to the average value of
the latent image during the exposure time $[f-T/2, f+T/2]$.
This equation applies to each pixel $(x, y)$ independently, and
subscripts $x,y$ denoting pixel location are often omitted henceforth.

\subsection{Event-based Double Integral Model}
We aim to recover a sequence of latent intensity images by exploiting both the blur model and the event model.
We define $e_{xy}(t)$ as a function of continuous time $t$ such that
\vspace{-2mm}
\begin{equation} \nonumber \label{eq:et}
e_{xy}(t) = \sigma \,\, \delta_{t_0}(t).
\vspace{-1mm}
\end{equation}
whenever there is an event $(x, y, t_0, \sigma)$.
Here, $\delta_{t_0}(t)$ is an impulse function, with unit integral, at time $t_0$, and the sequence of events is turned into a continuous time signal, consisting of a sequence of impulses.
There is such a function $e_{xy}(t)$ for every point $(x,y)$ in the image.
Since each pixel can be treated separately, we omit the subscripts $x, y$

During an exposure period $[f-T/2, f+T/2]$, we define $\mathbf{E}(t)$ as the sum of events between time $f$ and $t$ at a given pixel,
\begin{equation} \nonumber \label{eq:Etwithet}
\begin{split}
\mathbf{E}(t) &= \int_{f}^t e(s) ds ,\\
\end{split}
\end{equation}
which represents the proportional change in intensity between time $f$ and $t$.
Except under extreme conditions, such as glare and no-light conditions,
the latent image sequence $\mathbf{L}(t)$ is expressed as,
\begin{equation}\label{eq:Ltsigma}
\begin{split}
\mathbf{L}(t)\ & = \mathbf{L}(f) \, \exp( c\,  \mathbf{E}(t)) = \mathbf{L}(f) \, \exp(c)^{\mathbf{E}(t)} ~.
\end{split}
\end{equation}
In particular, an event $(x,y,t,\sigma)$ is triggered when the intensity of a pixel $(x,y)$ increases or decreases by an amount $c$ at time $t$.
We put a tilde on top of things to denote logarithm, \eg $\widetilde{\mathbf{L}}(t)=\log({\mathbf{L}}(t))$.
\begin{equation}\label{eq:logLtwithEt}
\begin{split}
\widetilde{\mathbf{L}}(t)\ & = \widetilde{\mathbf{L}}(f) + c \, \mathbf{E}(t).\\
\end{split}
\end{equation}

Given a sharp frame, we can reconstruct a high frame-rate video from the sharp starting point $\mathbf{L}(f)$ by using Eq.~\eqref{eq:logLtwithEt}. When the input image is blurry, a trivial solution would be to first deblur the image with an existing deblurring method and then to reconstruct the video using Eq.~\eqref{eq:logLtwithEt} (see Fig.\ref{fig:baseline} for details).
However, in this way, the event data between intensity images is not fully exploited, thus resulting in inferior performance.
Instead, we propose to reconstruct the video by exploiting the inherent connection between event and blur, and present the following model.

As for the blurred image,
{\small
\begin{equation}\label{eq:blurevent}
\begin{split}
\mathbf{B} &=  \frac{1}{T} \int_{f-T/2}^{f+T/2} \mathbf{L}(t) dt\\
& = \frac{\mathbf{L}(f)}{T}\int_{f-T/2}^{f+T/2}  \exp \Big (c \int_{f}^{t} e(s) ds\Big)\ dt  ~.
\end{split}
\end{equation}
}
In this manner, we construct the relation between the captured blurry image $\mathbf{B}$ and the latent image $\mathbf{L}(f)$ through the double integral of the event. We name Eq.\eqref{eq:blurevent} the \textbf{Event-based Double Integral (EDI)} model.

Taking the logarithm on both sides of Eq.~\eqref{eq:blurevent} and rearranging, yields
{\small
\begin{equation}\label{eq:logEDIM}
\widetilde{\mathbf{L}}(f) = \widetilde{\mathbf{B}} - \log \left(\frac{1}{T}\int_{f-T/2}^{f+T/2} \exp(c \,\mathbf{E}(t)) dt\right),
\end{equation}
}
which shows a linear relation between the blurry image, the latent image and the integral of the events in the log space.

\subsection{High Frame-Rate Video Generation}
The right-hand side of Eq.~\eqref{eq:logEDIM} is known, apart from perhaps
the value of the contrast threshold $c$, the first term from
the grey-scale image, the second term from the event sequence,
it is possible to compute $\widetilde\mathbf{L}(f)$, and hence $\mathbf{L}(f)$ by
exponentiation.  Subsequently, from
Eq.~\eqref{eq:logLtwithEt} the latent image $\mathbf{L}(t)$ at any time may be computed.

To avoid accumulated errors of constructing a video from many frames
of a blurred video, it is more suitable to construct each frame $\mathbf{L}(t)$ using the closest blurred frame.

Theoretically, we could generate a video with frame-rate as high as the DVS's eps (events per second). However, as each event carries little information and is subject to noise, several events must be processed together to yield a reasonable image. We generate a reconstructed frame every 50-100 events, so for our experiments, the frame-rate of the reconstructed video is usually 200 times greater than the input low frame-rate video.
Furthermore, as indicated by Eq.~\eqref{eq:logEDIM}, the challenging blind motion deblurring problem has been reduced to a single variable optimization problem of how to find the best value of the contrast threshold $c$. In the following section, we use $\mathbf{L}(c,t)$ to present the latent sharp image $\mathbf{L}(t)$ with different $c$.

\begin{figure}[t]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=0.215\textwidth]{./ceyeandcomputer/boxes_6dof_988_blur.pdf}
& \includegraphics[width=0.215\textwidth]{./ceyeandcomputer/boxes_6dof_988_Nah.pdf}  \\
(a) The blurry image
&(b) Tao \etal \cite{Tao_2018_CVPR}\\
\includegraphics[width=0.215\textwidth]{./ceyeandcomputer/boxes_6dof_988_our_eye.pdf}
&\includegraphics[width=0.215\textwidth]{./ceyeandcomputer/boxes_6dof_988_ourcpt.pdf} \\
(c) By human observation
&(d) By energy minimization\\
\end{tabular}
\end{center}
\vspace{-2mm}
\caption{\label{fig:real23}
An example of our reconstruction result using different methods to estimate $c$, from the real dataset \cite{mueggler2017event}. (a) The blurry image. (b) Deblurring result of \cite{Tao_2018_CVPR} (c) Our result where $c$ is chosen by manual inspection. (d) Our result where $c$ is computed automatically by our proposed energy minimization \eqref{eq:solveK}.}
\label{fig:manually}
\end{figure}
\vspace{-1 mm}
 \begin{figure}[t]
 \begin{center}
 \includegraphics[width=0.405\textwidth]{./figure/psnrvsc.pdf}
 \end{center}
 \vspace{-3mm}
 \caption{\em \label{fig:deltaVsblur} The figure plot deblurring performance against the value of $c$. The image is clearer with higher PSNR value.}
 \vspace{-2mm}
 \end{figure}

\section{Optimization}

The unknown contrast threshold $c$ represents the minimum change in log intensity required to trigger an event.
By choosing an appropriate $c$ in Eq.~\eqref{eq:blurevent}, we can generate a sequence of sharper images.
To this end, we first need to evaluate the sharpness of the reconstructed images. Here, we propose two different methods to estimate the unknown variable $c$: manually chosen and automatically optimized.

\begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{cccc}
\includegraphics[width=0.213\textwidth]{./chadeblur/cha_mt.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/cha_start.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/varyc/c1.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/varyc/c2.pdf}\\[0.1in]
\includegraphics[width=0.213\textwidth]{./chadeblur/cha_mtedge.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/cha_i0edge.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/varyc/sc1.pdf}
&\includegraphics[width=0.213\textwidth]{./chadeblur/varyc/sc2.pdf}
\\
\end{tabular}
}
\end{center}
\vspace{-2.5 mm}
\caption{\label{fig:csample} \em At left, the edge image $M(f)$
and below, its Sobel edge map.  To the right are $3$ reconstructed
latent images using different values of $c$,
low 0.03, middle 0.11 and high 0.55.  Above, the reconstructed images, below, their Sobel
edge maps.  The optimal value of the threshold $c$ is found by computing the cross-correlation of such images with the edge map at the left. (Best viewed on screen).
}
\end{figure*

\begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{cccc}
\includegraphics[width=0.213\textwidth]{./cnewbaseline/rotate53blur.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/deblurjin.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/baseline1_002.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/baseline2_002.pdf}\\
(a) The Blur Image
&(b) Jin \etal \cite{Jin_2018_CVPR}
&(c) Baseline 1
&(d) Baseline 2\\
\includegraphics[width=0.213\textwidth]{./cnewbaseline/video/board_2.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/video/board_50.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/video/board_90.pdf}
&\includegraphics[width=0.213\textwidth]{./cnewbaseline/video/board_130.pdf}\\
\multicolumn{4}{c}{(f) Samples of Our Reconstructed Video}
\end{tabular}
}
\end{center}
\vspace{-2.5 mm}
 \caption{\em \label{fig:baseline} Deblurring and reconstruction results on our real {\it blurry event dataset}.
(a) Input blurry images.
(b) Deblurring result of \cite{Jin_2018_CVPR}.
(c) Baseline 1 for our method. We first use the state-of-the-art video-based deblurring method \cite{Jin_2018_CVPR} to recover a sharp image. Then use the sharp image as input to a state-of-the-art reconstruction method \cite{Scheerlinck18arxiv} to get the intensity image.
(d) Baseline 2 for our method. We first use method \cite{Scheerlinck18arxiv} to reconstruct an intensity image. Then use a deblurring method \cite{Jin_2018_CVPR} to recover a sharp image.
(e) Samples from our reconstructed video from $\mathbf{L}(0)$ to $\mathbf{L}(150)$.
(Best viewed on screen).
}
\end{figure*}

\subsection{Manually Chosen $c$}
According to our {\bf EDI} model in Eq.~\eqref{eq:blurevent}, given a value for $c$, we can obtain a sharp image.
Therefore, we develop a method for deblurring by manually inspecting the visual effect of the deblurred image.
In this way, we incorporate human perception into the reconstruction loop and the deblurred images should satisfy human observation.
In Fig.~\ref{fig:manually}, we give an example for manually chosen and automatically optimized results on dataset from \cite{mueggler2017event}.

\subsection{Automatically Chosen $c$}

To automatically find the best $c$, we need to build an evaluation
metric (energy function) that can evaluate the quality of the
deblurred image $\mathbf{L}(c,t)$. Specifically, we propose to exploit
different prior knowledge for sharp images and the event data.
\vspace{-1 mm}
\subsubsection{Edge Constraint for Event Data}

As mentioned before, when a proper $c$ is given, our reconstructed image $\mathbf{L}(c,t)$ will contain much sharper edges compared with the original input intensity image. Furthermore, event cameras inherently yield responses at moving intensity boundaries,
so edges in the latent image may be located where (and when) events occur.
This allows us to find latent image edges.
An edge at time $t$ corresponds to an event (at the pixel in question)
during some time interval around $t$ so we convolve the event sequence
with an exponentially decaying window, to obtain an edge map
\begin{equation} \nonumber \label{Mt}
\begin{split}
\mathbf{M}(t) &= \int_{0}^{T} \exp(-( \alpha |t-s|))  \, e(t) \, ds,\\
\end{split}
\end{equation}
where $ \alpha$ is a weight parameter for time attenuation, which we
set to $1$.
As $\mathbf{M}(t)$ mainly reports the intensity changes but not the intensity value itself, we need to change $\mathbf{M}(t)$ to an edge map $\mathcal{S}(\mathbf{M}(t))$ using the
Sobel filter, which is also applied to $\mathbf{L}(c,t)$. (See Fig. \ref{fig:csample} for details).

Here, we use cross-correlation between $\mathcal{S}(\mathbf{L}(c,t))$ and $\mathcal{S}(\mathbf{M}(t))$ to evaluate the sharpness of $\mathbf{L}(c,t)$.
{\small
\begin{equation}
\phi_{\rm{edge}}(\mathbf{L}(c,t)) = \sum_{x, y}
\mathcal{S}(\mathbf{L}(c,t))(x, y) \cdot \mathcal{S}(\mathbf{M}(t))(x, y) ~.
\end{equation}
}
\vspace{-4 mm}
\subsubsection{Regularizing the Intensity Image}
In our model, total variation is used to suppress noise in the latent image while preserving edges, and penalize the spatial fluctuations\cite{rudin1992nonlinear}. Therefore, we use conventional total variation (TV) based regularization
\begin{equation} \label{TVnorm}
\phi_{\rm{TV}}(\mathbf{L}(c,t)) = |\nabla \mathbf{L}(c,t)|_{1},
\end{equation}
where $\nabla$ represents the gradient operators.
\vspace{-1 mm}
\subsubsection{Energy Minimization}

The optimal $c$ can be estimate by solving Eq.~\eqref{eq:solveK},
\begin{equation}\label{eq:solveK}
\min_{c} \phi_{\rm{TV}}(\mathbf{L}(c,t)) + \lambda \phi_{\rm{edge}}(\mathbf{L}(c,t)) ,
\end{equation}
where $\lambda$ is a trade-off parameter. The response of cross-correlation reflect the matching rate of $\mathbf{L}(c,t)$ and $\mathbf{M}(t)$ which makes $\lambda<0$.
This single-variable minimization problem can be solved by the nonlinear least-squares method \cite{more1978levenberg}, Scatter-search\cite{ugray2007scatter} or Fibonacci search \cite{dunlap1997golden}.

In Fig.~\ref{fig:deltaVsblur}, we illustrate the clearness of the reconstructed image against the value of $c$. Meanwhile, we also provide the PSNR of the corresponding reconstructed image. As demonstrated in the figure, our proposed reconstruction metric could locate/identify the best deblurred image with peak PSNR properly.

{\small
\begin{table*}\footnotesize
\begin{center}
\caption{\em  {\em Quantitative comparisons on the Synthetic dataset \cite{Nah_2017_CVPR}.} This dataset provides videos can be used to generate not only blurry images but also event data. All methods are tested under the same blurry condition, where methods \cite{Nah_2017_CVPR,Jin_2018_CVPR,Tao_2018_CVPR,Zhang_2018_CVPR} use GoPro dataset \cite{Nah_2017_CVPR} to train their models. Jin \cite{Jin_2018_CVPR} achieves their best performance when the image is down-sampled to 45\% mentioned in their paper.}
\label{all_all}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
\hline
\multicolumn{9}{c}{Average result of the deblurred images on dataset\cite{Nah_2017_CVPR}}  \\ \hline
            & Pan \etal \cite{pan2017deblurring} & Sun \etal \cite{sun2015learning}  & Gong \etal \cite{gong2017motion}  & Jin \etal \cite{Jin_2018_CVPR} & Tao \etal \cite{Tao_2018_CVPR} & Zhang \etal \cite{Zhang_2018_CVPR} & Nah \etal \cite{Nah_2017_CVPR}  & Ours    \\ \hline
PSNR(dB)  & 23.50  & 25.30  & 26.05   & 26.98    & {\bf30.26}     & 29.18   & 29.08    & 29.06   \\ \hline
SSIM      & 0.8336 & 0.8511 & 0.8632  & 0.8922   & 0.9342    & 0.9306  & 0.9135   & {\bf{0.9430}}    \\ \hline
\multicolumn{9}{c}{Average result of the reconstructed videos on dataset\cite{Nah_2017_CVPR}}  \\ \hline
\multicolumn{1}{c|}{}     & \multicolumn{2}{c|}{Baseline 1 \cite{Tao_2018_CVPR} + \cite{Scheerlinck18arxiv}} & \multicolumn{2}{c|}{Baseline 2 \cite{Scheerlinck18arxiv} + \cite{Tao_2018_CVPR}} & \multicolumn{2}{c|}{Scheerlinck \etal \cite{Scheerlinck18arxiv}} & \multicolumn{1}{c|}{Jin \etal \cite{Jin_2018_CVPR}}    & Ours   \\ \hline
\multicolumn{1}{c|}{PSNR(dB)} & \multicolumn{2}{c|}{25.52}          & \multicolumn{2}{c|}{26.34}          & \multicolumn{2}{c|}{25.84}           & \multicolumn{1}{c|}{25.62}  & {\bf{28.49 }}  \\ \hline
\multicolumn{1}{c|}{SSIM} & \multicolumn{2}{c|}{0.7685}          & \multicolumn{2}{c|}{0.8090}          & \multicolumn{2}{c|}{0.7904}           & \multicolumn{1}{c|}{0.8556} & {\bf{0.9199 }} \\ \hline
\end{tabular}
\end{center}
\vspace{-3mm}
\end{table*}
}

\begin{figure*}[ht]
\begin{center}
\begin{tabular}{cccccc}
\multicolumn{2}{c}{
\hspace{-0.3 cm}
\begin{tabular}{cc}
\includegraphics[height=0.130\textwidth]{./cVideo/5_blur.pdf}
\hspace{-0.4 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/1Iter_5_blur.pdf}\\
\multicolumn{2}{c}{(a) The Blurry Image}
\end{tabular}
}
&\multicolumn{2}{c}{
\hspace{-0.6 cm}
\begin{tabular}{cc}
\includegraphics[height=0.130\textwidth]{./cVideo/5_Jin.pdf}
\hspace{-0.4 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/1input-esti4.pdf}\\
\multicolumn{2}{c}{(b) Jin \etal \cite{Jin_2018_CVPR}}
\end{tabular}
}
&\multicolumn{2}{c}{
\hspace{-0.6 cm}
\begin{tabular}{cc}
\includegraphics[height=0.130\textwidth]{./cVideo/5_our.pdf}
\hspace{-0.4 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/1Iter_5_clean05.pdf}\\
\multicolumn{2}{c}{(c) Ours}
\end{tabular}
}\\
\multicolumn{6}{l}{
\hspace{-0.3 cm}
\begin{tabular}{ccccccc}
\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti1.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti2.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti3.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti4.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti5.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti6.pdf}
\hspace{ 0.630 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2input-esti7.pdf}\\
\multicolumn{7}{c}{(d) The Reconstructed Video of \cite{Jin_2018_CVPR}}\\
\end{tabular}
}\\
\multicolumn{6}{l}{
\hspace{-0.3 cm}
\begin{tabular}{ccccccccccc}
\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean01.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean02.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean03.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean04.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean05.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean06.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean07.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean08.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean09.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean10.pdf}
\hspace{-0.39 cm}
&\includegraphics[height=0.130\textwidth]{./cVideo/2Iter_5_clean11.pdf}\\
\multicolumn{11}{c}{(e) The Reconstructed Video of Our Method}\\
\end{tabular}
}\\
\multicolumn{3}{c}{
\hspace{-0.3 cm}
\begin{tabular}{ccc}
\includegraphics[height=0.112\textwidth]{./cVideo/c_R/rein/image00149.png}
\hspace{-0.30 cm}
&\includegraphics[height=0.112\textwidth]{./cVideo/c_R/rein/image00178.png}
\hspace{-0.30 cm}
&\includegraphics[height=0.112\textwidth]{./cVideo/c_R/rein/image00210.png}\\
\multicolumn{3}{c}{ (f) Reinbacher \etal \cite{Reinbacher16bmvc}}\\
\end{tabular}
}
&\multicolumn{3}{c}{
\hspace{-0.55 cm}
\begin{tabular}{ccc}
\includegraphics[height=0.112\textwidth]{./cVideo/c_R/scheerlinck_results/crop/image0026.png}
\hspace{-0.30 cm}
&\includegraphics[height=0.112\textwidth]{./cVideo/c_R/scheerlinck_results/crop/image0030.png}
\hspace{-0.30 cm}
&\includegraphics[height=0.112\textwidth]{./cVideo/c_R/scheerlinck_results/crop/image0035.png}\\
\multicolumn{3}{c}{ (g) Scheerlinck \etal \cite{Scheerlinck18arxiv}}\\
\end{tabular}
}\\
\end{tabular}
\end{center}
\vspace{-2.5 mm}
\caption{\em \label{fig:VideoGoPro} An example of the reconstructed result on our synthetic event dataset based on the GoPro dataset~\cite{Nah_2017_CVPR}. \cite{Nah_2017_CVPR} provides videos to generate the blurry images and event data.
(a) The blurry image. The red close-up frame is for (b)-(e), the yellow close-up frame is for (f)-(g).
(b) The deblurring result of Jin \etal \cite{Jin_2018_CVPR}.
(c) Our deblurring result.
(d) The crop of their reconstructed images and the frame number is fixed at 7. Jin \etal \cite{Jin_2018_CVPR} uses the GoPro dataset added with 20 scenes as training data and  their model is supervised by 7 consecutive sharp frames.
(e) The crop of our reconstructed images.
(f) The crop of Reinbacher \cite{Reinbacher16bmvc} reconstructed images from only events.
(g) The crop of Scheerlinck \cite{Scheerlinck18arxiv} reconstructed image, they use both events and the intensity image.
For (e)-(g), the shown frames are the chosen examples, where the length of the reconstructed video is based on the number of events.
}
\vspace{-1mm}
\end{figure*}
\begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{ccccc}
\includegraphics[width=0.215\textwidth]{./cReal/textlowlightblur.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/textlowlightevent.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_pan.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_tao.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_Nah.pdf}\\
\includegraphics[width=0.215\textwidth]{./cReal/cvprtextblur.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/cvprtextevent.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_pan.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_tao.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_Nah.pdf}\\
(a) The Blurry Image
&(b) The Event
&(c) Pan \etal \cite{pan2017deblurring}
&(d) Tao \etal \cite{Tao_2018_CVPR}
&(e) Nah \etal \cite{Nah_2017_CVPR}\\
\includegraphics[width=0.215\textwidth]{./cReal/0044-esti4.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_rein2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_scheerlinck_events2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0044_scheerlinck2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/SHE_our.pdf}\\
\includegraphics[width=0.215\textwidth]{./cReal/0013-esti4.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_rein2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_scheerlinck_events2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_scheerlinck2.pdf}
&\includegraphics[width=0.215\textwidth]{./cReal/0013_our.pdf}\\
(f) Jin \etal \cite{Jin_2018_CVPR}
&(g) Reinbacher \etal \cite{Reinbacher16bmvc}
&(h)  {\small\begin{tabular}[c]{@{}c@{}}Scheerlinck \etal \cite{Scheerlinck18arxiv}\\ (events only)\end{tabular}}
&(i) Scheerlinck \etal \cite{Scheerlinck18arxiv}
&(j) Ours\\
\end{tabular}
}
\end{center}
\vspace{-2.5 mm}
 \caption{\em \label{fig:Real} Examples of reconstruction result on our real {\it blurry event dataset} in low lighting and complex dynamic conditions
(a) Input blurry images.
(b) The event information.
(c) Deblurring results of \cite{pan2017deblurring}.
(d) Deblurring results of \cite{Tao_2018_CVPR}.
(e) Deblurring results of \cite{Nah_2017_CVPR}.
(f) Deblurring results of \cite{Jin_2018_CVPR} and they use video as training data.
(g) Reconstruction result of \cite{Reinbacher16bmvc} from only events.
(h)-(i) Reconstruction results of \cite{Scheerlinck18arxiv}, (h) from only events, (i) from combining events and frames.
(j) Our reconstruction result.
Results in (c)-(f) show that real high dynamic settings and low light condition is still challenging in the deblurring area. Results in (g)-(h) show that while intensity information of a scene is still retained with an event camera recording, color, and delicate texture information cannot be recovered.
}\vspace{-1mm}
\end{figure*}
\vspace{-2 mm}
\section{Experiment}

\subsection{Experimental Setup}

\vspace{-1mm}
\noindent{\bf{Synthetic dataset.}}
In order to provide a quantitative comparison, we build a synthetic dataset based on the GoPro blurry dataset \cite{Nah_2017_CVPR}.
It supplies ground truth videos which are used to generate the blurry images. Similarly, we employ the ground-truth images to generate event data based on the methodology of \emph{event camera model}.

\noindent{\bf{Real dataset.}}
We evaluate our method on a public Event-Camera dataset \cite{mueggler2017event}, which provides a collection of sequences captured by the event camera for high-speed robotics.
Furthermore, we present our real {\it blurry event dataset}~\footnote{To be released with codes}, where each real sequence is captured with the DAVIS\cite{brandli2014240} under different conditions, such as indoor, outdoor scenery, low lighting conditions, and different motion patterns (\eg, camera shake, objects motion) that naturally introduce motion blur into the APS intensity images.

\noindent{\bf{Implementation details.}}
For all our real experiments, we use the DAVIS that shares photosensor array to simultaneously output events (DVS) and intensity images (APS).
The framework is implemented by using MATLAB with C++ wrappers. It takes around 1.5 second to process one image on a single i7 core running at 3.6 GHz.

\subsection{Experimental Results}
\vspace{-1mm}
We compare our proposed approach with state-of-the-art blind deblurring methods, including conventional deblurring methods \cite{pan2017deblurring,yan2017image}, deep based dynamic scene deblurring methods \cite{Nah_2017_CVPR,Jin_2018_CVPR,Tao_2018_CVPR,Zhang_2018_CVPR,sun2015learning}, and event-based image reconstruction methods \cite{Reinbacher16bmvc,Scheerlinck18arxiv}. Moreover, Jin \etal \cite{Jin_2018_CVPR} can restore a video from a single blurry image based on a deep network, where the middle frame in the restored odd-numbered sequence is the best.

In order to prove the effective of our \textbf{EDI} model, we show some baseline comparisons in Fig. \ref{fig:baseline} and Table \ref{all_all}.
For baseline 1, we first apply a state-of-the-art deblurring method~\cite{Tao_2018_CVPR} to recover a sharp image, and then the recovered image as an input is then fed to a reconstruction method~\cite{Scheerlinck18arxiv}.
For baseline 2, we first use the video reconstruction method to construct a sequence of intensity images, and then apply the deblurring method to each frame.
As seen in Table~\ref{all_all}, our approach obtains higher PSNR and SSIM in comparison to both baseline 1 and baseline 2. This also implies that our approach better exploits the event data to not only recover sharp images but also reconstruct high frame-rate videos.

In Table~\ref{all_all}, we show the quantitative comparisons with the state-of-the-art image deblurring approaches \cite{sun2015learning, pan2017deblurring, gong2017motion, Jin_2018_CVPR, Tao_2018_CVPR, Zhang_2018_CVPR, Nah_2017_CVPR}, and the video reconstruction method \cite{Scheerlinck18arxiv} on our synthetic dataset, respectively.
As indicated in Table~\ref{all_all}, our approach achieves the best performance on SSIM and competitive result on PSNR compared to the state-of-the-art methods, and attains significant performance improvements on high-frame video reconstruction.

In Fig.~\ref{fig:VideoGoPro}, we compare our generated video frames with the state-of-the-art deblurring methods \cite{ pan2017deblurring, Jin_2018_CVPR, Tao_2018_CVPR, Nah_2017_CVPR} qualitatively. Furthermore, image reconstruction methods \cite{Reinbacher16bmvc,Scheerlinck18arxiv} are also included for comparisons. Fig.~\ref{fig:VideoGoPro} shows that our method can generate more frames from a single blurry image and the recovered frames are much sharper.

We also report our reconstruction results on the real dataset, including text images and low-lighting images, in Fig.~\ref{fig:eventdeblur}, Fig.~\ref{fig:eventsample}, Fig.~\ref{fig:real23} and Fig.~\ref{fig:Real}. Compared with state-of-the-art deblurring methods, our method achieves superior results.
In comparison to existing event-based image reconstructed methods \cite{Reinbacher16bmvc, Scheerlinck18arxiv}, our reconstructed images are not only more realistic but also contain richer details.
More deblurring results and {\bf high-temporal resolution videos} are shown in the supplementary material.

\vspace{-1.5 mm}
\section{Conclusion}
\vspace{-1 mm}
In this paper, we propose a {\textbf{Event-based Double Integral (EDI)}} model to naturally connect intensity images and event data captured by the event camera, which also takes the blur generation process into account.
In this way, our model can be used to not only recover latent sharp images but also reconstruct intermediate frames at high frame-rate. We also propose a simple yet effective method to solve our EDI model.
Due to the simplicity of our optimization process, our method is efficient as well. Extensive experiments show that our method can generate high-quality high frame-rate videos efficiently under different conditions, such as low lighting and complex dynamic scenes.

\bibliographystyle{ieee}

\section{Datasets} \label{sec::dataset}

\subsection{Synthetic Dataset}\label{sec::Synthetic_dataset}

In order to qualitatively comparing our method with state-of-the-art deblurring methods \cite{ pan2017deblurring,yan2017image, Jin_2018_CVPR, Tao_2018_CVPR, Nah_2017_CVPR}, we build a synthetic dataset based on the GoPro blurry dataset \cite{Nah_2017_CVPR}. We use the provided videos from \cite{Nah_2017_CVPR} to generate event data.
The comparing results are presented in Fig.~\ref{fig:Gopr}. It clearly shows that our method can generate more frames from a single blurry image and the recovered frames are much sharper.

\subsection{Real Dataset}\label{sec::real_dataset}

A Dynamic and Active-pixel Vision Sensor (DAVIS) \cite{brandli2014240} asynchronously measures the intensity changes at each pixel independently with microsecond temporal resolution.
It uses a shared photo-sensor array to simultaneously output events from its Dynamic Vision Sensor (DVS) and intensity images from its Active Pixel Sensor (APS).

In all our real experiments, we use a DAVIS to build our real {\it Blurry event dataset}. The sequences are taken under different conditions, such as indoor, outdoor, low-lighting, and different motion patterns (camera shake, moving object), \etc.

Our intensity images are recorded at a frame rate from $5$ fps (frames per second) to 20 fps for different sequences. The resolution of the intensity images is $240\times180$. The maximum frame-rate of our recorded events is $200$ keps (thousands of events per second) since the events depend on the intensity changes of the scene.

\section{High Frame-Rate Videos}\label{sec::Video}

The input of our method is a single image and its event data during the exposure time. Given a sharp frame $\mathbf{L}(f)$, setting it as a starting point, we can reconstruct a high frame-rate video by using Eq.~\eqref{eq:L}.
\begin{equation} \label{eq:L}
\mathbf{L}(t) = \mathbf{L}(f)\exp \Big (c \int_{f}^{t} e(s) ds\Big).
\end{equation}

When the input image is blurry, a trivial solution would be to first deblur the image with an existing deblurring method and then using Eq.~\eqref{eq:L} to reconstruct the video (see Fig.\ref{fig:baseline1} for details).
However, in this way, the events between consecutive intensity images are not fully exploited, resulting in inferior performance.
We propose to exploit the inherent connection between event and blur to reconstruct the video,  and give the following model:
\begin{equation}\label{eq:logEDIM2}
\log (\mathbf{L}(f)) = \log (\mathbf{B}) - \log \left( \frac{1}{T} \int_{f-T/2}^{f+T/2} \exp(c \,\mathbf{E}(t)) dt \right).
\end{equation}

The right-hand side of Eq.~\eqref{eq:logEDIM2} is known, apart from perhaps
the value of the contrast threshold $c$, the first term from
the grey-scale image, the second term from the event sequence,
it is possible to compute $\log (\mathbf{L}(f))$, and hence $\mathbf{L}(f)$ by
exponentiation.  Subsequently, from
Eq.~\eqref{eq:L} the latent image $\mathbf{L}(t)$ at any time may be computed.

When tackling a video, we process each frame in the video separately to generate our reconstructed video.
To avoid accumulating errors, it is more suitable to construct each frame $\mathbf{L}(t)$ using the closest blurred frame.

Theoretically, we could generate a video with frame-rate as high as the DVS's eps (events per second). However, as each event carries little information and is subject to noise, several events must be processed together to yield a reasonable image. We generate a reconstructed frame every $50-100$ events, so for our experiments, the frame-rate of the reconstructed video is usually $200$ times greater than the input low frame-rate video. Our model (Eq. \eqref{eq:logEDIM2} ) can get a better result compared to the state-of-the-art deblurring methods. (see Fig.\ref{fig:baseline1} for an example.)

 \begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{cccc}
\includegraphics[width=0.230\textwidth]{./cnewbaseline/rotate53blur.pdf}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/deblurjin.pdf}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/rotate53_tao.png}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/rotate53_nah.png}\\
(a) Input blurry image
&(b) Jin \etal \cite{Jin_2018_CVPR}
&(c) Tao \etal \cite{Tao_2018_CVPR}
&(d) Nah \etal \cite{Nah_2017_CVPR}  \\
\includegraphics[width=0.230\textwidth]{./cnewbaseline/video/board_2.pdf}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/video/board_50.pdf}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/video/board_90.pdf}
&\includegraphics[width=0.230\textwidth]{./cnewbaseline/video/board_130.pdf}\\
\multicolumn{4}{c}{(f) Samples of our reconstructed video}
\end{tabular}
}
\end{center}
 \caption{\em \label{fig:baseline1} Deblurring and reconstruction results on our real {\it blurry event dataset}.
(a) Input blurry image.
(b) Deblurring result of \cite{Jin_2018_CVPR}.
(c) Deblurring result of \cite{Tao_2018_CVPR}.
(d) Deblurring result of \cite{Nah_2017_CVPR}.
(e) Samples of our reconstructed video from $\mathbf{L}(0)$ to $\mathbf{L}(150)$.
For baseline 1, we first apply a deblurring method to recover a sharp image, and the recovered image is then fed to a reconstruction method~\cite{Scheerlinck18arxiv}.
For baseline 2, we first use a video reconstruction method ~\cite{Scheerlinck18arxiv} to construct a sequence of intensity images, and then apply a deblurring method to each intensity image.
On synthetic dataset, we use \cite{Tao_2018_CVPR} as the deblurring method for its state-of-the-art performance.
On our real blurry event dataset, Jin \cite{Jin_2018_CVPR} achieves better results than \cite{Tao_2018_CVPR} (see Fig. 1 and 8 in our paper). Thus, we use Jin \cite{Jin_2018_CVPR} as the deblurring method.
}
\end{figure*}

We put several results of our reconstructed video in the supplementary material and details are given in Table \ref{table:imlist}. For all our videos, the left part is the input image and the right part is our reconstructed video.

\begin{table*}[]
\begin{center}
\caption{\label{table:imlist} \em Details  of our real \emph{blurry event dataset}}
\begin{tabular}{|c|c|c|c|}
\hline
\textbf{Num.} & \textbf{Video name} & \textbf{Condition}  & \textbf{Motion type}                                                                                \\ \hline
1             & Tea                 & indoor              & camera shake                                                                                \\ \hline
2             & text\_SHE           & indoor \& low light & \begin{tabular}[c]{@{}c@{}}moving object \\ (The text shown in the phone is also moving)\end{tabular} \\ \hline
3             & chessboard1         & indoor              & moving object                                                                                \\ \hline
4             & chessboard2         & indoor              & moving object                                                                                \\ \hline
5             & jumping             & indoor              & moving object                                                                                \\ \hline
6             & snowman             & indoor              & camera shake                                                                                \\ \hline
7             & pillow              & indoor              & moving object                                                                                \\ \hline
8             & outdoorrun               & outdoor \& dusk     & moving object and camera shake                                                                        \\ \hline
9             & runningman          & indoor              & moving object                                                                                \\ \hline
10            & lego         & indoor              & moving objects                                                                                \\ \hline
$11^*$            & nightrun         & outdoor \& low light             & moving object                                                                                \\ \hline
\multicolumn{4}{l}{$*$:Data from \cite{Scheerlinck18arxiv}.}  \\
\end{tabular}
\end{center}
\end{table*}

\section{Code}\label{sec::Code}
All our codes will be released after publication. Here, we only provide a testing code with data `snowman' due to the size limitation of supplementary material ($100$MB).
Please run `./snowman\_codefortest/maindalta.m', and manually change the two slide bars to visualize the reconstructed image. `Threshold c' is the threshold to trigger an event. `Frame t' is the reconstructed image at timestamp $t$. (see Fig. \ref{fig:deltaVsblur1}).

 \begin{figure*}[t]
 \begin{center}
 \includegraphics[width=0.9\textwidth]{./figure/shot.png}
 \end{center}
 \caption{\em \label{fig:deltaVsblur1} Our program interface.}
 \end{figure*}

\begin{figure*}[ht]
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tabular}{cccc}
\includegraphics[width=0.235\textwidth]{./cGOPR/3_clean.pdf}
&\includegraphics[width=0.235\textwidth]{cGOPR/3_blur.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/3_blur.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/3_pan.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/246_clean.pdf}
&\includegraphics[width=0.235\textwidth]{cGOPR/246_blur.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/246_jin.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/246_pan.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/404_clean.pdf}
&\includegraphics[width=0.235\textwidth]{cGOPR/404_blur.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/404_jin.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/404_pan.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/599_clean.pdf}
&\includegraphics[width=0.235\textwidth]{cGOPR/599_blur.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/599_jin.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/599_pan.pdf}\\
(a) Sharp images
&(b) Blurry images
&(c) Jin \etal \cite{Jin_2018_CVPR}
&(d) Pan \etal \cite{pan2017deblurring} \\
\includegraphics[width=0.235\textwidth]{./cGOPR/3_yan.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/3_tao.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/3_nah.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/3_our.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/246_yan.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/246_tao.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/246_nah.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/246_our.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/404_yan.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/404_tao.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/404_nah.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/404_our.pdf}\\
\includegraphics[width=0.235\textwidth]{./cGOPR/599_yan.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/599_tao.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/599_nah.pdf}
&\includegraphics[width=0.235\textwidth]{./cGOPR/599_our.pdf}\\
(e) Yan \etal \cite{yan2017image}
&(f) Tao \etal \cite{Tao_2018_CVPR}
&(g) Nah \etal \cite{Nah_2017_CVPR}
&(h) Ours\\
\end{tabular}
}
\end{center}
\caption{\label{fig:Gopr} Examples of deblurring results on our synthetic event dataset. (a) Sharp images. (b) Generated blurry images. (c) Deblurring results of \cite{Jin_2018_CVPR}. (d) Deblurring results of \cite{pan2017deblurring}. (e) Deblurring results of \cite{yan2017image}. (f) Deblurring results of \cite{Tao_2018_CVPR}. (g) Deblurring results of \cite{Nah_2017_CVPR}. (h) Our deblurring results. (Best view in color
on screen).}
\end{figure*}

\end{appendices}