{\boldsymbol{x}}_{1}^{\star}+(\mu+2){\boldsymbol{x}}_{2}^{\star}\end{bmatrix}.$

Also, since
${\boldsymbol{x}}_{0}=\mathbf{0}\in\mathcal{X},{\boldsymbol{x}}^{\star}_{1},{\boldsymbol{x}}^{\star}_{2}\in\mathcal{X}$,
we can express $\hat{{\boldsymbol{x}}}_{1},\hat{{\boldsymbol{x}}}_{2}$ as a
convex combination as

$\displaystyle\hat{{\boldsymbol{x}}}_{1}=\bigg{(}\frac{\mu(\mu+1)}{\mu^{2}+3\mu+1}{\boldsymbol{x}}^{\star}_{1}+\frac{\mu}{\mu^{2}+3\mu+1}{\boldsymbol{x}}^{\star}_{2}+\frac{\mu+1}{\mu^{2}+3\mu+1}\mathbf{0}\bigg{)}\in\mathcal{X},$
$\displaystyle\hat{{\boldsymbol{x}}}_{2}=\bigg{(}\frac{\mu}{\mu^{2}+3\mu+1}{\boldsymbol{x}}^{\star}_{1}+\frac{\mu^{2}+2\mu}{\mu^{2}+3\mu+1}{\boldsymbol{x}}^{\star}_{2}+\frac{1}{\mu^{2}+3\mu+1}\mathbf{0}\bigg{)}\in\mathcal{X}.$

From the considered special case, we observe that the optimal solution
$\hat{{\boldsymbol{x}}}_{1},\hat{{\boldsymbol{x}}}_{2}\in\mathcal{X}$.
Although, the coefficients corresponding to
${\boldsymbol{x}}_{1}^{\star},{\boldsymbol{x}}_{2}^{\star}$ in
$\hat{{\boldsymbol{x}}}_{1}$ are positive, they don’t form a convex
combination ($\because$ they don’t add up to $1$). But the remaining
contribution can be attributed to $\mathbf{0}$. This makes
$\hat{{\boldsymbol{x}}}_{1}$ a convex combination of
${\boldsymbol{x}}_{1}^{\star},{\boldsymbol{x}}_{2}^{\star}$, and $\mathbf{0}$
each of which belongs to $\mathcal{X}$. Similar reasoning can be applied to
$\hat{{\boldsymbol{x}}}_{2}$. Therefore, the unconstrained optimization is
equivalent to the constrained optimization for $T=2$. Next, we proceed towards
proving the Lemma for any general $T>2$.
Notice that the optimal solution
$\hat{{\boldsymbol{x}}}=[\hat{{\boldsymbol{x}}}_{1},\ldots,\hat{{\boldsymbol{x}}}_{T}]$
of the unconstrained optimization in (37) can be expressed as the following
system of equations (by setting the gradient = $\mathbf{0}$):

$\displaystyle\mu(\hat{{\boldsymbol{x}}}_{1}-{\boldsymbol{x}}_{1}^{\star})+(\hat{{\boldsymbol{x}}}_{1}-\hat{{\boldsymbol{x}}}_{2})+\hat{{\boldsymbol{x}}}_{1}=\mathbf{0}$
$\displaystyle\implies\bigg{(}1+\frac{2}{\mu}\bigg{)}\hat{{\boldsymbol{x}}}_{1}-\frac{1}{\mu}\hat{{\boldsymbol{x}}}_{2}={\boldsymbol{x}}_{1}^{\star},$
(51)
$\displaystyle\mu(\hat{{\boldsymbol{x}}}_{t}-{\boldsymbol{x}}_{t}^{\star})+(\hat{{\boldsymbol{x}}}_{t}-\hat{{\boldsymbol{x}}}_{t-1})+(\hat{{\boldsymbol{x}}}_{t}-\hat{{\boldsymbol{x}}}_{t+1})=\mathbf{0}$
$\displaystyle\implies-\frac{1}{\mu}\hat{{\boldsymbol{x}}}_{t-1}+\bigg{(}1+\frac{2}{\mu}\bigg{)}\hat{{\boldsymbol{x}}}_{t}-\frac{1}{\mu}\hat{{\boldsymbol{x}}}_{t+1}={\boldsymbol{x}}_{t}^{\star},$
(52)
$\displaystyle\mu(\hat{{\boldsymbol{x}}}_{T}-{\boldsymbol{x}}_{T}^{\star})+(\hat{{\boldsymbol{x}}}_{T}-\hat{{\boldsymbol{x}}}_{T-1})=\mathbf{0}$
$\displaystyle\implies-\frac{1}{\mu}\hat{{\boldsymbol{x}}}_{T-1}+\bigg{(}1+\frac{1}{\mu}\bigg{)}\hat{{\boldsymbol{x}}}_{T}={\boldsymbol{x}}_{T}^{*}.$
(53)

Note that (52) holds for all $2\leq t\leq T-1$. Combining (51), (52), and (53)
we can express the optimal solution $\hat{{\boldsymbol{x}}}$ in the following
matrix notation:

$\displaystyle{\boldsymbol{H}}\hat{{\boldsymbol{x}}}={\boldsymbol{x}}^{*}\implies\begin{bmatrix}1+\frac{2}{\mu}&-\frac{1}{\mu}&\ldots&\ldots&0\\\
-\frac{1}{\mu}&1+\frac{2}{\mu}&-\frac{1}{\mu}&\ldots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
\ldots&\ldots&-\frac{1}{\mu}&1+\frac{2}{\mu}&-\frac{1}{\mu}\\\
0&\ldots&\ldots&-\frac{1}{\mu}&1+\frac{1}{\mu}\end{bmatrix}\begin{bmatrix}\hat{{\boldsymbol{x}}}_{1}\\\
\vdots\\\ \vdots\\\
\hat{{\boldsymbol{x}}}_{T}\end{bmatrix}=\begin{bmatrix}{\boldsymbol{x}}_{1}^{\star}\\\
\vdots\\\ \vdots\\\ {\boldsymbol{x}}_{T}^{\star}\end{bmatrix}.$ (54)

Observe that the matrix ${\boldsymbol{H}}$ has positive elements on it’s main
diagonal, negative elements = $-\frac{1}{\mu}$ on the diagonal above and below
the main diagonal, and elements $=0$ everywhere else. Also, ${\boldsymbol{H}}$
is strictly diagonally dominant (as per Definition 1), therefore invertible.

######  Definition 1.

A $n\times n$ square matrix ${\boldsymbol{X}}$ with elements $x_{ij}$, is said
to be diagonally dominant if, for every row of the matrix, the magnitude of
the diagonal entry in a row is larger than or equal to the sum of the
magnitudes of all the other off-diagonal entries in that row, i.e.

$\displaystyle\lvert x_{ii}\rvert\geq\sum_{j\neq i}\lvert x_{ij}\rvert,\forall
i.$ (55)

If a strict inequality is used in (55) then ${\boldsymbol{X}}$ is said to be
strictly diagonally dominant.

We now invoke [40, Thm. 2] to prove a bound on the $\infty$-norm of the matrix
${\boldsymbol{H}}$(54).

######  Theorem 7.

[40, Thm. 2] Assume a $n\times n$ matrix ${\boldsymbol{X}}$ with elements
$x_{ij}$, is diagonally dominant (refer to definition (1)) and let
$\alpha_{{\boldsymbol{X}}}:=\min_{k}(\lvert x_{kk}\rvert-\sum_{j\neq k}\lvert
x_{kj}\rvert)$. Then,
$\left\|{\boldsymbol{X}}^{-1}\right\|_{\infty}<\frac{1}{\alpha_{\mathcal{{\boldsymbol{X}}}}}$,
where $\left\|{\boldsymbol{A}}\right\|_{\infty}:=\max_{1\leq i\leq
n}\sum_{j=1}^{n}\lvert a_{ij}\rvert$ denotes the $\infty$-norm of a $n\times
n$ matrix ${\boldsymbol{A}}$ with elements $a_{ij}$.

For the matrix ${\boldsymbol{H}}=[h]_{ij}$ (54), we have
$\alpha_{{\boldsymbol{H}}}=\min_{k}(\lvert h_{kk}\rvert-\sum_{j\neq k}\lvert
h_{kj}\rvert)=1$. Also ${\boldsymbol{H}}$ is strictly diagonally dominant.
Thus, applying Theorem 7, we obtain

$\displaystyle\left\|{\boldsymbol{H}}^{-1}\right\|_{\infty}<1.$ (56)

Note that the entries of ${\boldsymbol{H}}$ are not positive. However, we show
that all the entries of ${\boldsymbol{H}}^{-1}=[\tilde{h}]_{ij}$ are positive.
The special structure of ${\boldsymbol{H}}$ has been studied in [41] and exact
analytical expressions for $\tilde{h}_{ij}$ can be found in [33]. However [33]
do not provide a rigorous proof for $\tilde{h}_{ij}>0$. We prove this in the
following Lemma.

######  Lemma 19.

The elements of ${\boldsymbol{H}}^{-1}=[\tilde{h}_{ij}]$ satisfy
$\tilde{h}_{ij}>0$, for all $1\leq i\leq T$ and $1\leq j\leq T$.

###### Proof.

Recall from (54) that each entry of ${\boldsymbol{H}}$ is a function of $\mu$.
From [33], the elements $\tilde{h}_{t,t+\tau}$ where $\tau\geq 0$ have a
closed form expression given by $\tilde{h}_{t,t+\tau}=\mu w_{t}v_{t+\tau}$,
where

$\displaystyle
w_{t}=\frac{\rho}{1-\rho^{2}}\bigg{(}\frac{1}{\rho^{t}}-\rho^{t}\bigg{)},v_{t}=c_{1}\frac{1}{\rho^{T-t}}+c_{2}\rho^{T-t},v_{T}=\frac{1}{(\xi-1)w_{T}-w_{T-1}},$
(57) $\displaystyle
c_{1}:=v_{T}\bigg{(}\frac{(\xi-1)\rho-\rho^{2}}{1-\rho^{2}}\bigg{)},c_{2}:=v_{T}\frac{1-(\xi-1)\rho}{1-\rho^{2}},$

and
$\rho:=\frac{\sqrt{\mu+4}-\sqrt{\mu}}{\sqrt{\mu+4}+\sqrt{\mu}},\xi:=\mu+2$.
Note that since ${\boldsymbol{H}}$ is symmetric, ${\boldsymbol{H}}^{-1}$ is
symmetric as well. Therefore, to prove that all entries $\tilde{h}_{ij}>0$, it
is sufficient to consider the elements $\tilde{h}_{t,t+\tau}$ where $\tau\geq
0$. The collection of elements $\\{\tilde{h}_{t,t+\tau}:1\leq t\leq
T,0\leq\tau\leq T-\tau\\}$, corresponds to the elements in the upper
triangular block of ${\boldsymbol{H}}^{-1}$. Note that $\rho<1$, and thus
$w_{t}>0$, for all $1\leq t\leq T$.

To prove the Lemma, it is sufficient to show that $v_{t}>0$, for all $1\leq
t\leq T$. To prove this, we first show that $v_{T}>0$. From (57), $v_{T}$
depends on $w_{T}$ and $w_{T-1}$ which are given by

$\displaystyle
w_{T}=\frac{\rho}{1-\rho^{2}}\bigg{(}\frac{1}{\rho^{T}}-\rho^{T}\bigg{)},w_{T-1}=\frac{\rho}{1-\rho^{2}}\bigg{(}\frac{1}{\rho^{T-1}}-\rho^{T-1}\bigg{)}.$
(58)

Consider the function $\zeta(x)=\frac{1}{x}-x$ that is monotonically
decreasing in $x$, since $\zeta^{\prime}(x)=-\frac{1}{x^{2}}-1<0$. Since
$\rho^{t}$ decreases as $t$ increases ($\because\rho<1$), the quantity
$\frac{1}{\rho^{t}}-\rho^{t}$ increases as $t$ increases. Therefore,
$w_{T}>w_{T-1}$. This implies that $v_{T}=\frac{1}{(\xi-1)w_{T}-w_{T-1}}>0$,
since $\xi>2$. Next we show that $v_{t}>0$ for all $1\leq t\leq T-1$.

Since $v_{T}>0$ and $\rho<1$, we have
$c_{1}=v_{T}\rho\big{(}\frac{(\mu+1)-\rho}{1-\rho^{2}}\big{)}>0$. Note that,
we have substituted $\xi=\mu+2$ to obtain $c_{1}$. Similarly,
$c_{2}=v_{T}\frac{1-(\mu+1)\rho}{1-\rho^{2}}$. To prove that $c_{2}>0$, it is
sufficient to prove that the quantity $1-(\mu+1)\rho>0$. Note that
$1-(\mu+1)\rho=1-(\mu+1)\frac{\sqrt{\mu+4}-\sqrt{\mu}}{\sqrt{\mu+4}+\sqrt{\mu}}>0,$
for all $\mu>0$. Therefore, $c_{2}>0$.

Since $c_{1}>0$ and $c_{2}>0$, we have $v_{t}>0$, for all $1\leq t\leq T-1$.
With $v_{t}>0,w_{t}>0$, for all $1\leq t\leq T$, we have
$\tilde{h}_{t,t+\tau}>0$. This completes the proof. ∎

From (54), the optimal solution $\hat{{\boldsymbol{x}}}_{k}$ can be expressed
as

$\displaystyle\hat{{\boldsymbol{x}}}_{k}=\sum_{j=1}^{T}\tilde{h}_{kj}{\boldsymbol{x}}^{\star}_{j}.$

Observe from (56) that for every $k$,
$\sum_{j=1}^{T}\lvert\tilde{h}_{kj}\rvert<1$. Also, since $\tilde{h}_{kj}>0$
(from Lemma 19), we can express $\hat{{\boldsymbol{x}}}_{k}$ as

$\displaystyle\hat{{\boldsymbol{x}}}_{k}=\sum_{j=1}^{T}\tilde{h}_{kj}{\boldsymbol{x}}^{\star}_{j}+\big{(}1-\sum_{j=1}^{T}\tilde{h}_{kj}\big{)}\mathbf{0}.$

This clearly implies $\tilde{{\boldsymbol{x}}}_{k}\in\mathcal{X}$, for all
$k$, since ${\boldsymbol{x}}_{t}^{\star}\in\mathcal{X},$ for all $1\leq t\leq
T$, $\mathbf{0}\in\mathcal{X}$, and $\mathcal{X}$ is convex. This completes
the proof. ∎

######  Lemma 20.

If the functions $f_{t}$ are identically equal to a function $f$, i.e.,
$f_{t}=f$, for all $1\leq t\leq T$, the cost incurred by the $\mathsf{OPT}$
can be lower bounded by

$\displaystyle C_{\mathsf{OPT}}\geq
Tf({\boldsymbol{x}}^{\star})+\frac{\mu}{2(\mu+1)}\left\|{\boldsymbol{x}}^{\star}\right\|^{2},$

where
${\boldsymbol{x}}^{\star}:=\operatorname*{arg\,min}_{{\boldsymbol{x}}\in\mathcal{X}}f({\boldsymbol{x}})$.

###### Proof.

Continuing from step (37) as in the proof of Lemma (5), we have the following:

$\displaystyle C_{\mathsf{OPT}}\geq
Tf({\boldsymbol{x}}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathbb{R}^{d}\\}_{t=1}^{T}}\sum_{t=1}^{T}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$

Define $C_{\mathsf{OPT}}(j)$ to be the following:

$\displaystyle
C_{\mathsf{OPT}}(j):=Tf({\boldsymbol{x}}^{\star})+\min_{\\{{\boldsymbol{x}}_{t}\in\mathbb{R}^{d}\\}_{t=1}^{j}}\sum_{t=1}^{j}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\big{)},$

It is trivial to notice that $\\{C_{\mathsf{OPT}}(j)\\}_{j=1}^{T}$ is a
monotonically increasing sequence. To obtain a lower bound on
$C_{\mathsf{OPT}}$, we can use $C_{\mathsf{OPT}}(1)$ and obtain the following:

$\displaystyle C_{\mathsf{OPT}}\geq C_{\mathsf{OPT}}(T)\geq
C_{\mathsf{OPT}}(1)=Tf({\boldsymbol{x}}^{\star})+\min_{{\boldsymbol{x}}_{1}\in\mathbb{R}^{d}}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}\right\|^{2}\big{)},$
(59)

The unconstrained minimizer of
$\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}\right\|^{2}$
is given by

$\displaystyle\operatorname*{arg\,min}_{{\boldsymbol{x}}_{1}\in\mathbb{R}^{d}}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}^{\star}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}\right\|^{2}\big{)}=\frac{\mu}{\mu+1}{\boldsymbol{x}}^{\star}.$

Therefore, (59) reduces to

$\displaystyle C_{\mathsf{OPT}}\geq
Tf({\boldsymbol{x}}^{\star})+\frac{\mu}{2}\|{\frac{\mu}{\mu+1}{\boldsymbol{x}}^{\star}-{\boldsymbol{x}}^{\star}}\|^{2}+\frac{1}{2}\|{\frac{\mu}{\mu+1}{\boldsymbol{x}}^{\star}}\|^{2}=Tf({\boldsymbol{x}}^{\star})+\frac{\mu}{2(\mu+1)}\left\|{\boldsymbol{x}}^{\star}\right\|^{2}.$

This completes the proof. ∎

Note that the result of Lemma 20 is similar to the bound in Lemma 5 and
implies that as $\mu\to 0$, the cost incurred by the $\mathsf{OPT}$ is lower
bounded by
$\Omega(Tf({\boldsymbol{x}}^{\star})+\mu\left\|{\boldsymbol{x}}^{\star}\right\|^{2})$.

###  Appendix E Upper bounding $C_{\mathcal{A}_{o}}$ when
$\sum_{t=1}^{T}\left\|f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}=\mathcal{O}(\mathcal{P}_{2,T}^{\star})$

We show that as long as the quantity $\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}=\mathcal{O}(\mathcal{P}_{2,T}^{*})$,
we get the same order-wise (with respect to $L,\mu$) bound on the competitive
ratio as Theorem 1. Let $\sum_{t=1}^{T}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t}^{\star})\right\|^{2}=\gamma\mathcal{P}_{2,T}^{\star}$
for some constant $\gamma>0$ (that is independent of $T$ and other problem
parameters, i.e., $\mu,L$, etc.). Then, the upper bound on
$C_{\mathcal{A}_{o}}$ in Lemma 4 is a function of $\alpha$, which can
therefore be minimized with respect to $\alpha$ as done in the following
steps:

$\displaystyle C_{\mathcal{A}_{o}}$
$\displaystyle\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\frac{\gamma}{2\alpha}\mathcal{P}_{2,T}^{\star}+\alpha(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+2\mathcal{P}_{2,T}^{\star})+(L+5)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+2\mathcal{P}_{2,T}^{*}),$
$\displaystyle\leq\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+\big{(}\frac{\gamma}{2\alpha}+2\alpha+2L+10\big{)}\big{(}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\mathcal{P}_{2,T}^{\star}),$
(60)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+(2L+2\sqrt{\gamma}+10)(\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\mathcal{P}_{2,T}^{*}),$

where $(a)$ follows by minimizing the upper bound in (60) with respect to
$\alpha$, the optimal choice of $\alpha$ being
$\operatorname*{arg\,min}_{\alpha>0}\big{(}\frac{\gamma}{2\alpha}+2\alpha\big{)}=\frac{\sqrt{\gamma}}{2}$.
Next, proceeding similarly as the proof of Theorem 1, the competitive ratio of
the OMGD algorithm is bounded by
$\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}\leq
4(L+\sqrt{\gamma}+5)+\frac{16(L+\sqrt{\gamma}+5)}{\mu},$ which is order-wise
(with respect to $L,\mu$) same as the result of Theorem 1.

###  Appendix F Proof of Lemma 6

We consider $\mathcal{X}={\mathbb{R}}^{d}$. Let $T=2$ and consider
$f_{1}({\boldsymbol{x}})=\frac{\mu}{2}\left\|{\boldsymbol{x}}-{\boldsymbol{\theta}}\right\|^{2}$,
where ${\boldsymbol{\theta}}\neq\mathbf{0}$, and
$f_{2}({\boldsymbol{x}})=\frac{L}{2}\left\|{\boldsymbol{x}}\right\|^{2}$,
where $L\geq\mu$. Note that both $f_{1}$ and $f_{2}$ and $L$-smooth and
$\mu$-strongly convex. Consider the starting point
${\boldsymbol{x}}_{0}=\mathbf{0}$. For this choice of functions,
$\mathcal{A}_{o}$ selects
${\boldsymbol{x}}_{1}={\boldsymbol{x}}_{0}=\mathbf{0}$. However, it takes
$K=\lceil\frac{L+\mu}{2\mu}\ln 4\rceil$ gradient steps with step size
$\frac{1}{L}$, starting at ${\boldsymbol{z}}_{2}^{(0)}=\mathbf{0}$. The
progress from ${\boldsymbol{z}}_{2}^{(k-1)}$ to ${\boldsymbol{z}}_{2}^{(k)}$
happens through the following update:

$\displaystyle{\boldsymbol{z}}_{2}^{(k)}={\boldsymbol{z}}_{2}^{(k-1)}-\frac{\mu}{L}({\boldsymbol{z}}_{2}^{(k-1)}-{\boldsymbol{\theta}})={\boldsymbol{z}}_{2}^{(k-1)}\big{(}1-\frac{\mu}{L}\big{)}+\frac{\mu}{L}{\boldsymbol{\theta}}.$

The final action ${\boldsymbol{z}}_{2}^{(K)}$ is obtained by unrolling the
recursion and is given by

$\displaystyle{\boldsymbol{z}}_{2}^{(K)}$
$\displaystyle={\boldsymbol{z}}_{2}^{(K-1)}\big{(}1-\frac{\mu}{L}\big{)}+\frac{\mu}{L}{\boldsymbol{\theta}},$
$\displaystyle={\boldsymbol{z}}_{2}^{(K-2)}\big{(}1-\frac{\mu}{L}\big{)}^{2}+\frac{\mu}{L}{\boldsymbol{\theta}}\big{(}1+\big{(}1-\frac{\mu}{L}\big{)}\big{)},$
$\displaystyle={\boldsymbol{z}}_{2}^{(K-3)}\big{(}1-\frac{\mu}{L}\big{)}^{3}+\frac{\mu}{L}{\boldsymbol{\theta}}\big{(}1+\big{(}1-\frac{\mu}{L}\big{)}+\big{(}1-\frac{\mu}{L}\big{)}^{2}\big{)},$
$\displaystyle\hskip 8.53581pt\vdots\hskip 42.67912pt\vdots\hskip
42.67912pt\vdots\hskip 42.67912pt,\vdots\hskip 42.67912pt\vdots$
$\displaystyle={\boldsymbol{z}}_{2}^{(0)}\big{(}1-\frac{\mu}{L}\big{)}^{K}+\frac{\mu}{L}{\boldsymbol{\theta}}\sum_{i=0}^{K-1}\big{(}1-\frac{\mu}{L}\big{)}^{i},$
$\displaystyle={\boldsymbol{z}}_{2}^{(0)}\big{(}1-\frac{\mu}{L}\big{)}^{K}+{\boldsymbol{\theta}}\big{(}1-\big{(}1-\frac{\mu}{L}\big{)}^{K}\big{)},$
$\displaystyle={\boldsymbol{\theta}}\big{(}1-\big{(}1-\frac{\mu}{L}\big{)}^{K}\big{)}.$
(61)

Since $\mathcal{A}_{o}$ selects
${\boldsymbol{x}}_{2}={\boldsymbol{z}}_{2}^{(K)}$, the resulting cost incurred
by $\mathcal{A}_{o}$ is

$C(\mathcal{A}_{o})=\frac{\mu}{2}\left\|{\boldsymbol{\theta}}\right\|^{2}+\frac{L+1}{2}\left\|{\boldsymbol{x}}_{2}\right\|^{2}=\frac{\mu}{2}\left\|{\boldsymbol{\theta}}\right\|^{2}+\frac{L+1}{2}\big{(}1-\big{(}1-\frac{\mu}{L}\big{)}^{K}\big{)}^{2}\left\|{\boldsymbol{\theta}}\right\|^{2}.$

Since $e^{x}\geq 1+x$, for all $x\in\mathbb{R}$, we have
$e^{-\frac{\mu}{L}}\geq\big{(}1-\frac{\mu}{L}\big{)}\implies
1-\big{(}1-\frac{\mu}{L}\big{)}^{K}\geq 1-e^{-K\frac{\mu}{L}}$. The quantity
$1-e^{-K\frac{\mu}{L}}$ can be lower bounded in the following way:

$\displaystyle 1-e^{-K\frac{\mu}{L}}=1-e^{-\lceil\frac{L+\mu}{2\mu}\ln
4\rceil\frac{\mu}{L}}\geq 1-e^{-\frac{L+\mu}{2\mu}\frac{\mu}{L}\ln
4}=1-e^{-\frac{L+\mu}{L}\ln
2}=1-\frac{1}{2^{1+\frac{\mu}{L}}}\geq\frac{1}{2}.$

Therefore, $C_{\mathcal{A}_{o}}$ can be lower bounded by

$C_{\mathcal{A}_{o}}\geq\frac{\mu}{2}\left\|{\boldsymbol{\theta}}\right\|^{2}+\frac{L+1}{8}\left\|{\boldsymbol{\theta}}\right\|^{2}.$

The $\mathsf{OPT}$ on the other hand incurs the following cost:

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle=\min_{{\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2}}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{\theta}}\right\|^{2}+\frac{L}{2}\left\|{\boldsymbol{x}}_{2}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}\right\|^{2}+\frac{1}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{x}}_{2}\right\|^{2}\big{)},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\min_{{\boldsymbol{x}}_{1}}\big{(}\frac{\mu}{2}\left\|{\boldsymbol{x}}_{1}-{\boldsymbol{\theta}}\right\|^{2}+\left\|{\boldsymbol{x}}_{1}\right\|^{2}\big{)}=\frac{\mu}{\mu+2}\left\|{\boldsymbol{\theta}}\right\|^{2},$

where $(a)$ follows by setting ${\boldsymbol{x}}_{2}=\mathbf{0}$ in the
$\mathsf{OPT}$’s minimization problem. Therefore, the competitive ratio of the
OMGD algorithm $\mathcal{A}_{o}$ is lower bounded by

$\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}\geq\frac{(4\mu+L+1)(\mu+2)}{8\mu}.$

Note that $(4\mu+L+1)(\mu+2)=4\mu^{2}+8\mu+(L+1)(\mu+2)>8\mu+2(L+1)+\mu(L+1)$.
Hence, $\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}$ can be lower bounded by
$\frac{C_{\mathcal{A}_{o}}}{C_{\mathsf{OPT}}}\geq
1+\frac{L+1}{4\mu}+\frac{L+1}{8}.$ This completes the proof.

###  Appendix G Proof of Lemma 8

Sufficient to consider $d=1$ (one-dimensional case) and
$\mathcal{X}={\mathbb{R}}$. Consider the case when an algorithm $\mathcal{A}$
is slow and $\epsilon_{t}=\mathcal{O}(\mu)$ and $\mu\rightarrow 0$. Let
$f_{t}(x)=(x-1)^{2}$, for all $t=1,\dots,T$. On account of $\mathcal{A}$ being
slow, the earliest time $t$ such that $\mathcal{A}$’s action
$x_{t}\geq\frac{1}{2}$ is $\Omega(\frac{1}{\mu})$. Thus, the cost of
$\mathcal{A}$ is at least $\Omega(\frac{1}{\mu})$. An algorithm $\mathcal{B}$
that chooses $x_{t}=1$, for all $t$ has the cost of $1$. Thus,
$C_{\mathsf{OPT}}\leq 1$, and consequently the competitive ratio of
$\mathcal{A}$ is at least $\Omega(\frac{1}{\mu})$.

Next, consider the case when an algorithm $\mathcal{A}$ is slow and
$\epsilon_{t}=\mathcal{O}(\frac{1}{L})$ and $L\rightarrow\infty$. Let
$f_{t}(x)=\frac{L}{2}(x-1)^{2}$, for all $t=1,\dots,T$. On account of
$\mathcal{A}$ being slow, the earliest time $t$ such $\mathcal{A}$’s action
$x_{t}\geq\frac{1}{2}$ is $\Omega(L)$. Thus the cost of $\mathcal{A}$ is at
least $\Omega(L^{2})$. An algorithm $\mathcal{B}$ that chooses $x_{t}=1$, for
all $t$ has the cost of $1$. Thus, $C_{\mathsf{OPT}}\leq 1$. Therefore the
competitive ratio of $\mathcal{A}$ is at least $\Omega(L^{2})$. Combining both
the cases completes the proof.

###  Appendix H Proof of Lemma 9

Sufficient to consider $d=1$ (one-dimensional case) and
$\mathcal{X}={\mathbb{R}}$. With the limited information setting, any online
algorithm $\mathcal{A}$ chooses $x_{1}=x_{0}={0}$, since otherwise
$f_{1}(x)=\frac{L}{2}x^{2}$ and $\mathcal{A}$’s competitive ratio is
unbounded. Let $f_{1}(x)=\frac{L}{2}(x-1)^{2}$. Then the cost of $\mathcal{A}$
is $\frac{L}{2}$. $\mathsf{OPT}$ on the other hand chooses $x_{1}=1$ and pays
only the switching cost of $\frac{1}{2}$. Thus, the competitive ratio of
$\mathcal{A}$ is at least $L$. This completes the proof.

###  Appendix I Proof of Lemma 10

Sufficient to consider $d=1$ (one-dimensional case) and
$\mathcal{X}={\mathbb{R}}$. Choose $f_{t}(x)=\frac{\mu}{2}x^{2}$, for all
$t=1,\dots,T^{\prime}$. Any online algorithm $\mathcal{A}$ has to choose
$x_{t}=0$, for all $t=1,\dots,T^{\prime}$ since otherwise its cost is non-zero
while that of $\mathsf{OPT}$ is $0$. Let
$f_{T^{\prime}+1}(x)=\frac{L}{2}(x-1)^{2}$. Since $\mathcal{A}$ chooses its
action $x_{T^{\prime}+1}$ before any information about $f_{T^{\prime}+1}$ is
revealed, thus, $x_{T^{\prime}+1}=0$ as well and $\mathcal{A}$’s cost is at
least $\frac{L}{2}$ . The $\mathsf{OPT}$, however, knowing the full sequence
$\\{f_{t}\\}_{t=1}^{T^{\prime}+1}$, moves its actions slowly towards $1$ as a
function of $\mu$, and as shown in [27] for this choice of functions,
$\mathsf{OPT}$’s cost is $\mathcal{O}(\sqrt{\mu})$ as
$T^{\prime}\rightarrow\infty$ and $\mu\to 0^{+}$. Thus, letting
$T^{\prime}\rightarrow\infty$ the competitive ratio of $\mathcal{A}$ is at
least $\Omega\left(\frac{L}{\sqrt{\mu}}\right)$ as $\mu\to 0$. This completes
the proof.

###  Appendix J Proof of Theorem 2

We first bound the quantity
$\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|$
for $\mathcal{A}_{o}$ as follows.

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=2}^{T}\big{(}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}^{\star}\right\|+\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|\big{)},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{t=2}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1}^{\star}\right\|+\mathcal{P}_{T}^{\star},$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{1}{2}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\sum_{t=2}^{T-1}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|+\mathcal{P}_{T}^{\star},$
$\displaystyle\leq\frac{1}{2}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\sum_{t=2}^{T}\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|+\mathcal{P}_{T}^{\star},,$

where $(a)$ follows from the triangle inequality, $(b)$ follows from the
contraction bound (10) attained by $\mathcal{A}_{o}$, and $(c)$ follows since
$\mathcal{A}_{o}$ chooses
${\boldsymbol{x}}_{1}={\boldsymbol{x}}_{0}=\mathbf{0}$. Rearranging, we obtain

$\displaystyle\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\leq\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+2\mathcal{P}_{T}^{\star}\implies\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\leq
2\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+2\mathcal{P}_{T}^{\star}.$ (62)

From the convexity of $f$, we have the following:

$\displaystyle
f_{t}({\boldsymbol{x}}_{t})-f_{t}({\boldsymbol{x}}_{t}^{\star})\leq\langle\nabla
f({\boldsymbol{x}}_{t}),{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\rangle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\|\nabla
f_{t}({\boldsymbol{x}}_{t})\right\|\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\stackrel{{\scriptstyle(b)}}{{\leq}}G\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|,$

where $(a)$ follows from the Cauchy-Schwarz inequality, while $(b)$ follows
from assumption A3. Summing over $t=1,\ldots,T$, we obtain the following:

$\displaystyle\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})-f_{t}({\boldsymbol{x}}_{t}^{\star})\leq
G\sum_{t=1}^{T}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t}^{\star}\right\|\stackrel{{\scriptstyle\eqref{cumulative_sum}}}{{\leq}}2G(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}),$
$\displaystyle\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t})+\frac{1}{2}\left\|{\boldsymbol{x}}_{t}-{\boldsymbol{x}}_{t-1}\right\|^{2}\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+2G(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star})+5\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+10\mathcal{P}_{2,T}^{\star},$
(63)

where $(a)$ follows from the bound on the total switching cost attained by
$\mathcal{A}_{o}$ as given by Lemma 3. Finally, we can bound the regret as
follows.

$\displaystyle
R_{d}(\mathcal{A}_{o})=C_{\mathcal{A}_{o}}-C_{\mathsf{OPT}}\stackrel{{\scriptstyle\text{\eqref{actual_lower_bound},
\eqref{cost_bounded_subgradient}}}}{{\leq}}2G(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{*})+5\left\|{\boldsymbol{x}}_{1}^{*}\right\|^{2}+\bigg{(}10-\frac{\mu}{2(\mu+4)}\bigg{)}\mathcal{P}_{2,T}^{\star}.$

This completes the proof.

###  Appendix K Proof of Corollary 1

When $\mathcal{X}$ has a finite diameter, we can bound the quantity
$\alpha_{1}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\alpha_{2}\mathcal{P}_{2,T}^{*}$,
where $\alpha_{1},\alpha_{2}>0$ by the following:

$\displaystyle\alpha_{1}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}+\alpha_{2}\mathcal{P}_{2,T}^{*}\stackrel{{\scriptstyle(a)}}{{\leq}}\max(\alpha_{1},\alpha_{2})D(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}),$
(64)

where $(a)$ holds because
$\alpha_{1}\left\|{\boldsymbol{x}}_{1}^{\star}\right\|^{2}\leq\max(\alpha_{1},\alpha_{2})D\left\|{\boldsymbol{x}}_{1}^{\star}\right\|$,
and each of the terms
$\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|^{2}$
in $\mathcal{P}_{2,T}^{\star}$ can be bounded by
$D\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}_{t-1}^{\star}\right\|$.
Therefore, we can bound $R_{d}(\mathcal{A}_{o})$ for the OMGD algorithm by the
following:

$\displaystyle R_{d}(\mathcal{A}_{o})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\bigg{(}2G+D\bigg{(}10-\frac{\mu}{2(\mu+4)}\bigg{)}\bigg{)}(\left\|{\boldsymbol{x}}_{1}^{\star}\right\|+\mathcal{P}_{T}^{\star}),$
(65)

where $(a)$ follows by applying (64) to the regret bound on
$R_{d}(\mathcal{A}_{o})$ in Theorem 2. This completes the proof.

###  Appendix L Discussion regarding bound (16)

We begin by proving the bound (16) in the following manner:

$\displaystyle R_{d}(\mathcal{A}_{o})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})+(L+5)(\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}+2{\mathcal{P}}_{2,T}^{\star})-\sum_{t=1}^{T}f_{t}({\boldsymbol{x}}_{t}^{\star})-\frac{\mu}{2\mu+8}({\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}),$
$\displaystyle=\big{(}2L+10-\frac{\mu}{2\mu+8}\big{)}({\mathcal{P}}_{2,T}^{\star}+\left\|{\boldsymbol{x}}^{\star}_{1}\right\|^{2}),$
(66)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\big{(}2L+10-\frac{\mu}{2\mu+8}\big{)}\big{(}\sum_{t=2}^{T}\left\|{\boldsymbol{x}}_{t}^{\star}-{\boldsymbol{x}}^{\star}_{t-1}\right\|+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|\big{)}^{2},$
(67) $\displaystyle\leq\big{(}2L+10-\frac{\mu}{2\mu+8}\big{)}V_{T}^{2},$

where $(a)$ follows from the bounds on $C_{\mathcal{A}_{o}}$ and
$C_{\mathsf{OPT}}$ in Theorem 1, while $(b)$ follows by the trivial inequality
$\sum_{i=1}^{T}a_{i}^{2}\leq\big{(}\sum_{i=1}^{T}a_{i}\big{)}^{2},$ for all
$a_{1},\ldots,a_{T}\geq 0$. Intuitively, when
$\mathcal{P}_{T}^{\star}+\left\|{\boldsymbol{x}}_{1}^{\star}\right\|$ is
sufficiently large (which is the case when the optimizers
${\boldsymbol{x}}_{t}^{\star}$ and ${\boldsymbol{x}}_{t-1}^{\star}$ are far
apart), moving from step (66) to (67) adds in a significant number of extra
terms. Therefore, (67) is meaningful only in the $V_{T}\to 0^{+}$ regime.

###  Appendix M Proof of Lemma 15

Sufficient to consider $d=1$ (one-dimensional case) and
$\mathcal{X}={\mathbb{R}}$. With the limited information setting, any online
algorithm $\mathcal{A}$ has to choose $x_{1}=x_{0}=0$, since otherwise the
adversary can choose $f_{1}(x)=\frac{L}{2}x^{2}$ and $\mathcal{A}$’s
competitive ratio is unbounded.

Choose $f_{1}(x)=\frac{\mu}{2}(x-\theta)^{2}$, where
$\frac{\sqrt{129}-9}{2\mu}\geq\theta>\frac{1}{\mu}$ and
$f_{2}(x)=\frac{\mu}{2}x^{2}$. As argued earlier for any $\mathcal{A}$,
$x_{1}=0$. Thus, as a function of $\mathcal{A}$’s action $x_{2}$ at time
$t=2$, the cost of $\mathcal{A}$ is

$\displaystyle C_{\mathcal{A}}$
$\displaystyle=\frac{\mu}{2}\theta^{2}+\frac{\mu}{2}x_{2}^{2}+\lvert
x_{2}\rvert\geq\frac{\mu}{2}\theta^{2},$

where the last inequality follows since $\frac{\mu}{2}x_{2}^{2}+\lvert
x_{2}\rvert\geq 0$ irrespective of the choice of $x_{2}$. For the considered
choice of $f_{1}$, $f_{2}$, the $\mathsf{OPT}$ solves the following
optimization problem:

$\displaystyle C_{\mathsf{OPT}}$
$\displaystyle=\min_{x_{1},x_{2}}\big{(}\frac{\mu}{2}(x_{1}-\theta)^{2}+\frac{\mu}{2}x_{2}^{2}+\lvert
x_{1}\rvert+\lvert x_{1}-x_{2}\rvert\big{)},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\min_{x_{1}}\big{(}\frac{\mu}{2}(x_{1}-\theta)^{2}+2\lvert
x_{1}\rvert\big{)},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\min_{x_{1}\geq
0}\big{(}\frac{\mu}{2}(x_{1}-\theta)^{2}+2x_{1}\big{)}=2\big{(}\theta-\frac{1}{\mu}\big{)},$

where $(a)$ follows by setting $x_{2}=0$ in the $\mathsf{OPT}$’s optimization
problem. Further, since $\theta>\frac{1}{\mu}$, we have $\min_{x_{1}\geq
0}\big{(}\frac{\mu}{2}(x_{1}-\theta)^{2}+2x_{1}\big{)}=2\big{(}\theta-\frac{1}{\mu}\big{)}$
in $(b)$. Therefore, the competitive ratio of $\mathcal{A}$ can be lower
bounded by

$\displaystyle\text{cr}_{\mathcal{A}}\geq\frac{\mu\theta^{2}}{4\big{(}\theta-\frac{1}{\mu}\big{)}}.$

The condition $\theta<\frac{\sqrt{129}-9}{2\mu}$ implies

$\displaystyle\theta^{2}+\frac{9}{\mu}\theta-\frac{12}{\mu^{2}}\leq
0\iff\frac{\mu\theta^{2}}{4\big{(}\theta-\frac{1}{\mu}\big{)}}\geq\frac{1}{8}\big{(}2\mu\theta+\frac{12}{\mu\theta}+3\big{)}.$

For the chosen $f_{1},f_{2}$, we have
$\mathcal{P}_{T}^{\star}=\theta,\mathcal{P}_{2,T}^{\star}=\theta^{2},$ and
$\lvert x_{1}^{\star}\rvert=\theta$. Therefore, the quantity in (23) is equal
to

$\displaystyle\mu(\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\lvert
x_{1}^{\star}\rvert^{2}}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert}{\mathcal{P}_{2,T}^{\star}+\lvert
x_{1}^{\star}\rvert^{2}}=2\mu\theta+\frac{12}{\mu\theta}+3.$

Therefore, for the considered problem instance, we have

$\displaystyle\text{cr}_{\mathcal{A}}\geq\frac{1}{8}\bigg{(}\mu(\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert)+\frac{3}{2}\frac{\big{(}\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert\big{)}^{2}}{\mathcal{P}_{2,T}^{\star}+\lvert
x_{1}^{\star}\rvert^{2}}+\frac{12}{\mu}\frac{\mathcal{P}_{T}^{\star}+\lvert
x_{1}^{\star}\rvert}{\mathcal{P}_{2,T}^{\star}+\lvert
x_{1}^{\star}\rvert^{2}}\bigg{)},$

which completes the proof.


# PAON: A New Neuron Model using Padé Approximants

###### Abstract

Convolutional neural networks (CNN) are built upon the classical McCulloch-
Pitts neuron model, which is essentially a linear model, where the
nonlinearity is provided by a separate activation function. Several
researchers have proposed enhanced neuron models, including quadratic neurons,
generalized operational neurons, generative neurons, and super neurons, with
stronger nonlinearity than that provided by the pointwise activation function.
There has also been a proposal to use Padé approximation as a generalized
activation function. In this paper, we introduce a brand new neuron model
called Padé neurons ($\operatorname{\textit{Paon}}$s), inspired by the Padé
approximants, which is the best mathematical approximation of a transcendental
function as a ratio of polynomials with different orders. We show that
$\operatorname{\textit{Paon}}$s are a super set of all other proposed neuron
models. Hence, the basic neuron in any known CNN model can be replaced by
$\operatorname{\textit{Paon}}$s. In this paper, we extend the well-known
ResNet to PadéNet (built by $\operatorname{\textit{Paon}}$s) to demonstrate
the concept. Our experiments on the single-image super-resolution task show
that PadéNets can obtain better results than competing architectures.

Index Terms—  Padé approximants, neuron model, non-linearity, super-resolution

##  1 Introduction

Convolutional neural networks (CNN) have become an accurate and reliable tool
for solving many scientific and industrial problems. Although the rise of deep
CNN is relatively recent [1], the ideas behind their basic building block, the
neuron model, are not new [2, 3].

The classical McCulloch-Pitts neuron, linearly combines each input element
with different weights and then passes the result from a non-linear binary
activation function. Later, many studies investigated more powerful activation
functions to increase the capability of neurons leaving the linear part of the
model intact. Although the rectified linear unit ($\operatorname{ReLU}$) [4]
remains as the most popular choice following [1], other variants, such as
leaky $\operatorname{ReLU}$ [5], Gaussian error linear unit [6] and sigmoid
linear unit [7] are also commonly used. Noting that these are pre-determined
and hand-crafted non-linearities, Molina et al. [8] proposed to learn the
activation function for each layer via Padé approximation initializing the
coefficients from a decided non-linearity.

Based on the idea that a neuron model should not be limited to a pointwise
nonlinearity introduced by the activation, new inherently nonlinear neuron
models have been proposed. In this thread of research, quadratic neurons [9,
10, 11, 12] propose to operate on both first and second powers of their
inputs. Generalized operational perceptrons [13] propose to replace the
weighted linear combination and addition operations in the classical neuron
model with different mathematical functions. Generative neurons [14] are
inspired by the Taylor series expansion for polynomial approximation of
arbitrary nonlinear functions by operating on the higher order powers of the
input, and were applied to different image processing tasks [15, 16]. Super
neurons [17] aim to expand the receptive field of generative neurons via
learnable shifts applied to convolution kernels. More details are in Section
2.

Inspired by these works, this paper presents a new and more powerful
inherently nonlinear neuron model called $\operatorname{\textit{Paon}}$ using
Padé approximation of nonlinear functions. $\operatorname{\textit{Paon}}$s can
learn any nonlinear function as a ratio of polynomials, which is a more
powerful alternative to Taylor series expansion. We show that
$\operatorname{\textit{Paon}}$s are a super set of other known neuron models
and can replace the classic neuron model in any CNN.

Fig. 1: Illustration of a Padé neuron ($\operatorname{\textit{Paon}}$) for
$[M/N]=[2/3]$, where $w_{0}$ is bias for numerator, $(\cdot)^{k}$ takes
$k^{\text{th}}$ power of the input in element-wise manner,
$\frac{(\cdot)}{(\cdot)}$ implements either Eq. (5) or (6), and
$\mathbf{\ast}$ is convolution. The shifter module shifts the input features.

##  2 Related Works

There have been several attempts to define more powerful generalized
activations or inherently non-linear neuron models, which are discussed in
detail below:

Quadratic neurons. Quadratic neurons define a nonlinear relationship between
its inputs and outputs by operating on the input $x$ as well as the square of
the input $x^{2}$ given by

$f(x)=A(x^{2})+B(x),$ (1)

where $A$ is a quadratic function of $x$, $B$ is linear in $x$. Here, the bias
is omitted for simplicity.

This general formulation was employed in various studies. Cheung and Leung [9]
used $x^{\text{T}}w_{1}x+w_{2}x$, authors of [10] modified the second term as
$w_{2}x^{2}$. The study [18] obtained quadratic expression via multiplying two
filtered inputs as $(w_{1}x)\odot(w_{2}x)$, where $\odot$ is element-wise
(Hadamard) product. [11] added $w_{3}x$ to the previous expression, and [12]
used low-rank approximation to calculate quadratic terms. Unlike the quadratic
neurons, the proposed $\operatorname{\textit{Paon}}$s do not restrict
themselves to only second order polynomials.

Generalized Operational Perceptrons. Quadratic neurons are only able to
express functions that are second order at most. Kıranyaz et al. [13]
introduce a new neuron model, which replace linear scaling of input with
weights and addition of the results with a selected set of complex
mathematical operations. Generalized operational perceptrons can apply various
functions as their “nodal” operator, such as exponentiation, taking sinusoidal
and so on, as well as scaling by linear weights as in a common neuron.
Moreover, its “pool” operation (addition in a regular neuron) can be some
other appropriate operation such as median operator. However, it is
computationally very expensive both to choose those operations and apply them
since they take more resources compared to addition and multiplication.
Moreover, the choices are very architecture-dependent; if, say, a structural
change is desired to be made by adding one more layer, another extensive
search has to be done again to find the specific operations.

Generative Neurons. Noticing that huge computation necessity, the study [14]
proposes generative neurons. They basically try to approximate the required
mapping function by truncated Taylor series expansion around the point $0$;
i.e., they apply Maclaurin series expansion up to pre-determined order. By
this way, generative neurons aim to work around the computation burden of the
generalized operational perceptrons while still trying to be able to catch an
equivalent non-linearity. However, since they are linear combination of
different positive orders of the input, which can go out of the range for safe
computation zone, and Taylor series approximation is the best around a
specific point and worse on other further points, the output of generative
neurons [14] had to be limited by $\tanh$ activation, which is known to be a
source of vanishing gradients, thus, impediments the training of deep models.
On the contrary, in $\operatorname{\textit{Paon}}$s, higher ordered
approximations can be calculated as a ratio of two polynomials. Thanks to this
property, in many cases PadéNets do not require any limiting activation and
can benefit from the common non-linearities that are known to overcome the
vanishing gradient problem. Moreover, for a given approximation order, Padé
approximant can follow the target transcendental function closer than the
Taylor series expansion around a point [19]. Thus, for the same amount of non-
linearity, $\operatorname{\textit{Paon}}$s serve as a more efficient way.

Super Neurons. The generative neuron has a local receptive field; i.e., all
kernels for different powers pull information from the same location on a
feature map. Superneurons [17] introduce shifts, which are randomly
initialized and optimized via back propagation during training. In contrast,
$\operatorname{\textit{Paon}}$s learn the shifts from the data via the
$\operatorname{Shifter}$ module.

Padé Activation Unit (PAU). The study [8] proposes to use Padé approximant as
an activation, so called Padé activation unit ($\operatorname{PAU}$). They
pre-determine the orders for rational polynomials as well as some starting
coefficients for preferred activation as an initial non-linearity. In
$\operatorname{PAU}$, however, the activation function is learned for a whole
layer and tends to have the same shape as the non-linearity whose Padé
approximation is used as a starting point for coefficients. In PadéNets, every
single element in each neuron learns its own approximation. Thus, a single
neuron in a layer with $k\times k$ kernel actually learns $k^{2}$ different
Padé approximant as a ratio of two polynomials. Thus it brings higher degrees
of freedom to our choice, and provides element-wise non-linearity to each
kernel addition to the one coming from the activation function.

(a)

(b)

Fig. 2: (2): The architecture for the super-resolution experiments. (2):
Normal and wide residual block structure. For wide residual block (WRB), $w$
is bigger than $1$ while for normal block (RB), it is $1$.

##  3 PAON: Padé Approximant Neuron Model

Padé approximant is the best approximation of a transcendental function by a
ratio of two polynomials with given orders. Let $f_{[M/N]}(x)$ denote an
approximation expression for function $f$ with $M$\- and $N$-degree
polynomials in numerator and denominator, respectively. Then, the Padé
approximant for the function $f$ can be written as

$f_{[M/N]}(x)=\dfrac{P_{M}(x)}{Q_{N}(x)}=\left.{\sum_{k=0}^{M}a_{k}x^{k}}\middle/{\sum_{k=0}^{N}b_{k}x^{k}}\right.$
(2)

where $a_{k}$s and $b_{k}$s are the coefficients of polynomials in numerator
and denominator, respectively. Conventionally, Padé approximant coefficients
are normalized such that $b_{0}=1$. Thus, if we rewrite the expression,

$f_{[M/N]}(x)=\dfrac{\displaystyle\sum_{k=0}^{M}a_{k}x^{k}}{1+\displaystyle\sum_{k=1}^{N}b_{k}x^{k}}=\dfrac{a_{0}+\displaystyle\sum_{k=1}^{M}a_{k}x^{k}}{1+\displaystyle\sum_{k=1}^{N}b_{k}x^{k}}.$
(3)

If we think $a_{k}$s and $b_{k}$s as convolutional kernels and $a_{0}$ as the
bias term, then we have a neuron model:

$f_{[M/N]}(x)=\dfrac{P_{M}(x)}{Q_{N}(x)}=\dfrac{w_{0}+\displaystyle\sum_{k=1}^{M}w_{mk}\ast
x^{k}}{1+\displaystyle\sum_{l=1}^{N}w_{nl}\ast x^{l}},$ (4)

where $w_{mk}$ and $w_{nl}$ are kernels of numerator and denominator for the
input of order $k$ and $l$, respectively, and $w_{0}$ is the bias term for
numerator. Fig. 1 shows the workflow of a Padé neuron
($\operatorname{\textit{Paon}}$) for $[M/N]=[2/3]$.

Singularity of Pade Approximants. One thing to note about this neuron model is
that the denominator has the potential to be equal or very close to $0$.
Although the weights can be initialized to prevent this at the beginning,
learning of coefficients with gradient descent does not guarantee it to remain
away from zero. To mathematically ensure that the divisor is always nonzero,
we propose two variants of the Padé neurons. First, we take the absolute value
of each individual power in the denominator so that it is guaranteed to divide
each element in the numerator by a number greater than or equal to $1$. So,
the final expression for the Padé neuron with absolute value,
$\operatorname{\textit{Paon}}$-$A$, becomes

$f_{[M/N]}(x)=\dfrac{w_{0}+\displaystyle\sum_{k=1}^{M}w_{mk}\ast
x^{k}}{1+\displaystyle\sum_{l=1}^{N}\left|w_{nl}\ast x^{l}\right|}.$ (5)

The second variant is inspired by the work [20]. Although this method was
proposed for diagonal Padé approximants, i.e., $M=N$, we observe that it can
be used for $\lvert M-N\rvert=\\{0,1\\}$ without any further modification.
This smoothed variant of the Padé neuron, $\operatorname{\textit{Paon}}$-$S$,
can be written as

$f_{[M/N]}(x)=\dfrac{Q_{N}(x)P_{M}(x)+Q_{N-1}(x)P_{M-1}(x)}{Q_{N}^{2}(x)+Q_{N-1}^{2}(x)},$
(6)

where $P_{M}(x)$ and $Q_{N}(x)$ are as defined in Eq. (4).

Eqs. (5) and (6) tell that every kernel element in a
$\operatorname{\textit{Paon}}$ adapts itself so that each weight group in a
kernel learn their specific Padé approximant. It brings more non-linearity as
it introduces the higher orders of features to the model both as the numerator
and denominator. Moreover, thanks to its being a ratio of polynomials, it
behaves more stable for higher order approximations, thus, it does not need to
limit its output with bounded activation functions such as $\tanh$.

Shifter. $\operatorname{Shifter}$ module consists of averaging, $1\times 1$
convolution and a non-linear activation function together with some viewing
operations for shape consistency. When it takes a negative number as shift
parameter, it is deactivated. When the shift parameter $b$ is a positive
integer, it performs gradient-based optimization to find the best shift in the
range $[-b,b]$, and when $b=0$, it computes the best shift for each channel
without any restriction. The convolution weights and bias in
$\operatorname{Shifter}$ module are initialized as zero to make sure that the
module learns the amount of shift only when it does not hurt the performance.

Paons as Superset of Existing Neuron Models. Padé neurons are the super set of
the aforementioned neuron models. For $M=1$, $N=0$ and
$\operatorname{Shifter}$ is not active, the $\operatorname{\textit{Paon}}$
becomes an ordinary neuron111In Padé approximant, when $N$ is $0$, the
denominator becomes $1$.. When $M=2$, $N=0$, it shows the properties of a
quadratic neuron. For $M\geq 2$ and $N=0$, they behave as a generative neuron,
and when the $\operatorname{Shifter}$ branch is activated, it behaves as a
super neuron with improved performance since it learns the effective shifts
from the data. Thus, $\operatorname{\textit{Paon}}$s can easily replace any
neuron model in a convolutional network.

##  4 Experiments

###  4.1 Architecture

We show the performance of PadéNets on the single-image super resolution
problem. The basic architecture chosen for this task is a widely used one
since the seminal paper [21]. In this architecture, a single feature
extraction layer is followed by a series of blocks for residual feature
refinement. For simplicity, we chose residual [22] and wide residual blocks
[23] with scaled residuals [24] as our feature refinement blocks. The initial
features are added back to the refined residual features. The sum is processed
by a feature upsampler module, which contains a layer, an activation, and a
PixelShuffler layer [25]. The employed architecture is shown in Fig. 2, and
Fig. 2 shows the structure of a residual and wide residual block. The
learnable scaler layer for each output channel is initialized from $0.1$.

We check the performance of PadéNets by comparing various architectures: a
wide residual network network composed of convolutional layers and
$\operatorname{GELU}$ activation (called ResNet), a network with convolutional
layer and $\operatorname{PAU}$ activation (called $\operatorname{PAU}$-Net), a
SelfONN, a SuperONN, and PadéNet. In all of the models, we keep the
convolutions at the initial feature extractor, ath the end of feature
refinement, and the final image constructor part (upsampler and final layer)
the same degrees as $[1/0]$ to be able to keep track of the number of
parameters.

Table 1: PNSR scores on DIV2K$\times 2$ validation set. “FL”, “LL” and “AL”
denote first layer, last layer and all layers are
$\operatorname{\textit{PaLa}}$, respectively. All values are calculated using
$\operatorname{\textit{Paon}}$-$S$, except for the
$\operatorname{\textit{Paon}}$-$A$ column.

No Shift | Shift |  $\operatorname{\textit{Paon}}$-$A$ |  $\operatorname{\textit{Paon}}$-$S$ | FL | LL | AL
---|---|---|---|---|---|---
$34.32$ | $\mathbf{34.36}$ | $34.35$ | $\mathbf{34.36}$ | $34.29$ | $34.30$ | $\mathbf{34.36}$

Before the final comparison, we investigate the performance of PadéNet in
different setups. We check which $\operatorname{\textit{Paon}}$ is better,
whether or not the $\operatorname{Shifter}$ is helpful, and which layers in RB
to be converted into Pade neuron layers ($\operatorname{\textit{PaLa}}$). The
results are shown in Table 1. According to those metrics, we continue with
$\operatorname{\textit{Paon}}$-$S$ with $\operatorname{Shifter}$ is activated
in both of the layers in the residual block.

Image boundaries are processed in 3x3 convolutions and
$\operatorname{Shifter}$ module according to circular extension [26].

For the final comparison, architecture details are given in Table 2. Note that
SelfONN and SuperONN have $\tanh$ activations. In the experiments with
$\operatorname{GELU}$, those two networks became unstable, so we used $\tanh$
in residual blocks as proposed in their studies.

Table 2: Model configurations. Degrees denote the degree of
numerator/denominator polynomials $[M/N]$. The degree for
$\operatorname{PAU}$-Net is the degree of the $\operatorname{PAU}$ activation.
RB and WRB denote residual block and wide RB, respectively.

| ResNet |  $\operatorname{PAU}$-Net | (Self/Super)ONN | PadéNet
---|---|---|---|---
Degrees | $[1/0]$ | $[7/6]$ | $[3/0]$ | $[2/1]$
Activation | $\operatorname{GELU}$ | $\operatorname{PAU}$ | $\tanh$ | $\operatorname{GELU}$
Block Type | WRB | WRB | RB | RB
Blocks, $R$ | $3$ | $3$ | $3$ | $3$
Channels | $48$ | $48$ | $48$ | $48$

###  4.2 Training Details

For the training, we use DF2K dataset [27] as it has more images compared to
DIV2K [28, 29]. The models are trained on $64\times 64$ patches scaled to
$[-1,1]$ range with $25$ batch size for $5\times 10^{5}$ iterations to perform
on $\times 2$ and $\times 4$ super-resolution. The data are augmented with
random rotation, horizontal and vertical flip, and color channel shuffling.
Also, in the experiments, we noted that adding a small amount of Gaussian
noise during training improves the validation score of the network. Therefore,
we add Gaussian noise with $40\text{ dB}$ SNR into the cropped patches. The
model tries to minimize the loss function with $\alpha=1.5$ and $c=2$,
proposed in [30]. We use Adan optimizer [31] with $10^{-3}$ learning rate and
cosine annealing scheduler [32] until the learning rate becomes $10^{-6}$. The
best model is saved with respect to its validation PSNR on the DIV2K
validation set.

For comparison, the standard sets in super-resolution that are BSD100 [33],
Manga109 [34], Set5 [35], Set14 [36] Urban100 [37] are used. For all of the
compared models, PSNR, SSIM and LPIPS metrics are reported to compare the
performance. PSNR is calculated from RGB images [38]. For SSIM [39], Y channel
of YCbCR image is used. LPIPS [40] results are reported from both AlexNet [1]
and VGG [41].

###  4.3 Results and Discussion

Table 3: Quantitative comparison. The top two scores in each cell are
PSNR($\uparrow$) and SSIM($\uparrow$), and the bottom two are
LPIPS($\downarrow$) calculated via AlexNet and VGGNet, respectively. The best
and second best scores for each dataset are shown in red and blue.

| $\times 2$ | $\times 4$
---|---|---
| ResNet |  $\operatorname{PAU}$-Net | SelfONN | SuperONN | PadéNet | ResNet |  $\operatorname{PAU}$-Net | SelfONN | SuperONN | PadéNet
BSD100 | $30.64/0.8903$ | $30.63/0.8903$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}30.65}/0.8904$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}30.65}/0.8905$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}30.68}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.8909}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}26.13}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.7133}$ | $26.11/0.7127$ | $26.12/0.7125$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}26.13}/0.7131$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}26.16}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.7138}$
$0.1513/0.1580$ | $0.1516/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1576}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1508}/0.1584$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1501}/0.1578$ | $0.1516/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1574}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.3877}/0.3434$ | $0.3892/0.3434$ | $0.3892/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.3432}$ | $0.3893/0.3444$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.3884}/0.3439$
Manga109 | $35.60/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9724}$ | $35.60/0.9723$ | $35.62/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9724}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}35.63}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9724}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}35.70}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.9727}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}28.16}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.8924}$ | $28.11/0.8912$ | $28.14/0.8908$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}28.16}/0.8922$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}28.28}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.8941}$
$0.0242/0.0568$ | $0.0241/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0561}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0235}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0566}$ | $0.0236/0.0567$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0234}/0.0569$ | $0.1166/0.1720$ | $0.1172/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1696}$ | $0.1168/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1685}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1156}/0.1728$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1161}/0.1726$
Set5 | $35.50/0.9548$ | $35.51/0.9548$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}35.57}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9550}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}35.54}/0.9549$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}35.54}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.9551}$ | $29.78/0.8775$ | $29.81/0.8771$ | $29.85/0.8774$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}29.88}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.8776}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}29.90}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.8788}$
$0.0591/0.0964$ | $0.0591/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0955}$ | $0.0585/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0957}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0582}/0.0964$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0580}/0.0958$ | $0.1808/0.2184$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1807}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.2172}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1799}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.2156}$ | $0.1812/0.2185$ | $0.1812/0.2192$
Set14 | $30.99/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9074}$ | $30.97/0.9073$ | $31.11/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9074}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}31.12}/0.9073$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}31.14}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.9080}$ | $26.29/0.7594$ | $26.23/0.7594$ | $26.32/0.7591$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}26.35}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.7598}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}26.37}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.7604}$
$0.0985/0.1462$ | $0.0994/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1457}$ | $0.0985/0.1466$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0984}/0.1462$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0981}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1456}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.2947}/0.3090$ | $0.2952/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.3080}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.2951}/0.3085$ | $0.2956/0.3092$ | $0.2958/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.3078}$
Urban100 | $29.76/0.9148$ | $29.75/0.9147$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}29.82}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9153}$ | $29.80/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.9153}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}29.90}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.9165}$ | $24.27/0.7598$ | $24.23/0.7582$ | $24.26/0.7585$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}24.30}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.7608}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}24.35}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.7624}$
$0.0763/0.1198$ | $0.0767/0.1198$ | $0.0757/0.1193$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.0750}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1191}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.0742}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.1183}$ | $0.2540/0.2944$ | $0.2559/0.2946$ | $0.2559/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.2940}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.2517}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.2942}$ | ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.2515}/{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.2940}$

The quantitative resulst are shown in Table 3. It can be seen that PadéNet
surpasses all the models in every fidelity metrics, PSNR and SSIM, for nearly
all the datasets. The PSNR difference with wide ResNet can be as much as
$0.15\text{ dB}$. This indicates that although the number of parameters are
close to each other, a model equipped with function approximation capability
can serve better in the signal reconstruction. Moreover, comparison with
$\operatorname{PAU}$-Net shows that increasing the approximation capability of
the network via introducing the Padé approximants to the each kernel element
increases the expressive capability of the models. Finally, using Padé
approximant rather than Taylor series expansion in the neurons proves to be a
better strategy, thanks to the more accurate approximation capability of
former over the latter. This shows that the networks built with
$\operatorname{\textit{Paon}}$ can harness the most of the input information
and express the desired function that a neural network tries to approximate in
a better way.

Fig. 3: Visual comparison for $\times 2$ SR on img_058.png from Urban100
dataset. Crops from left to right are outputs of ResNet,
$\operatorname{PAU}$-Net, SelfONN, SuperONN and PadéNet.

Figs. 3 and 4 show the qualitative results of the models. Since the $\times 2$
SR is a relatively easier problem than $\times 4$ SR, the nuances are harder
to detect. In Fig. 3, it can be seen that the cropped region has some high
frequency content. Inspecting the images, it can be claimed that the most
successful model to reconstruct those details is PadéNet. The other models
either cause aliasing, or fail to reconstruct a straight line (in case of
SelfONN). The difference is clearer in Fig. 4. The table cover normally has
square patterns, which all models fail to reconstruct. But PadéNet is again
the closest one to bring the perpendicular lines into the image. Although the
Resnet also shows them, the output of PadéNet has more details.

Fig. 4: Visual comparison for $\times 4$ SR on barbara.png from Set14 dataset.
Crops from left to right are outputs of ResNet, $\operatorname{PAU}$-Net,
SelfONN, SuperONN and PadéNet.

##  5 Conclusion and Future Work

In this paper, we introduce a new neuron model called Pade approximant
neurons, or $\operatorname{\textit{Paon}}$ in short. It enhances the non-
linear capability of a regular convolutional neuron via utilizing the higher
order polynomials and Padé approximants on each of the kernel element. Its
construction makes it the super set of the previously proposed neuron models
such as quadratic neurons, generative neurons and super neurons. We show an
application of $\operatorname{\textit{Paon}}$s on the singe-image super-
resolution problem. Quantitative results show that (1) it outperforms the
regular neuron model thanks to its highly non-linear nature and (2)
$\operatorname{\textit{Paon}}$ surpasses the recently proposed generative and
super neurons thanks to its better approximation capability and learnable
shifter module.

As future work, we intend to check its performance on different image-related
tasks. Also, the increase on the $\operatorname{Shifter}$ performance would be
the next step to further increase the neuron performance.

## References

  * [1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton,  “Imagenet classification with deep convolutional neural networks,”  Advances in Neural Info. Proc. Systems, vol. 25, 2012.
  * [2] W. S. McCulloch and W. Pitts,  “A logical calculus of the ideas immanent in nervous activity,”  The bulletin of Mathematical Biophysics, vol. 5, pp. 115–133, 1943.
  * [3] Frank Rosenblatt,  The Perceptron, a Perceiving and Recognizing Automaton Project Para,  Report: Cornell Aeronautical Laboratory. 1957.
  * [4] Kevin Jarrett, Koray Kavukcuoglu, Marc’Aurelio Ranzato, and Yann LeCun,  “What is the best multi-stage architecture for object recognition?,”  in IEEE Int. Conf. on Comp. Vis. (ICCV), 2009, pp. 2146–2153.
  * [5] A. L. Maas, A. Y. Hannun, A. Y. Ng, et al.,  “Rectifier nonlinearities improve neural network acoustic models,”  in Int. Conf. Mach. Learn. (ICML). Atlanta, GA, 2013, vol. 30, p. 3.
  * [6] D. Hendrycks and K. Gimpel,  “Gaussian error linear units (GELUs),”  preprint arXiv:1606.08415, 2016.
  * [7] Stefan Elfwing, Eiji Uchibe, and Kenji Doya,  “Sigmoid-weighted linear units for neural network function approximation in reinforcement learning,”  Neural networks, vol. 107, pp. 3–11, 2018.
  * [8] A. Molina, P. Schramowski, and K. Kersting,  “Padé activation units: End-to-end learning of flexible activation functions in deep networks,”  in Int. Conf on Learning Repr. (ICLR), 2019.
  * [9] K. F. Cheung and C. S. Leung,  “Rotational quadratic function neural networks,”  in IEEE Int. Joint Conf. on Neural Networks, 1991, pp. 869–874.
  * [10] Srdjan Milenkovic, Zoran Obradovic, and Vanco Litovski,  “Annealing based dynamic learning in second-order neural networks,”  in Proceedings of International Conference on Neural Networks (ICNN’96). IEEE, 1996, vol. 1, pp. 458–463.
  * [11] Z. Xu, F. Yu, J. Xiong, and X. Chen,  “Quadralib: A performant quadratic neural network library for architecture optimization and design exploration,”  Proc. of Machine Learning and Systems, vol. 4, pp. 503–514, 2022.
  * [12] Chuangtao Chen, Grace Li Zhang, Xunzhao Yin, Cheng Zhuo, Ulf Schlichtmann, and Bing Li,  “Expressivity enhancement with efficient quadratic neurons for convolutional neural networks,”  arXiv preprint arXiv:2306.07294, 2023.
  * [13] Serkan Kıranyaz, Turker Ince, Alexandros Iosifidis, and Moncef Gabbouj,  “Operational neural networks,”  Neural Computing and Applications, vol. 32, pp. 6645–6668, 2020.
  * [14] Serkan Kıranyaz, Junaid Malik, Habib Ben Abdallah, Turker Ince, Alexandros Iosifidis, and Moncef Gabbouj,  “Self-organized operational neural networks with generative neurons,”  Neural Networks, vol. 140, pp. 294–308, 2021.
  * [15] O. Keleş, A. M. Tekalp, J. Malik, and S. Kıranyaz,  “Self-organized residual blocks for image super-resolution,”  in IEEE Int. Conf. on Image Processing (ICIP), 2021, pp. 589–593.
  * [16] M. A. Yılmaz, O. Keleş, H. Güven, A. M. Tekalp, J. Malik, and S. Kıranyaz,  “Self-organized variational autoencoders (self-vae) for learned image compression,”  in IEEE Int. Conf. on Image Processing (ICIP), 2021, pp. 3732–3736.
  * [17] S. Kiranyaz, J. Malik, M. Yamac, M. Duman, I. Adalioglu, E. Guldogan, T. Ince, and M. Gabbouj,  “Super neurons,”  IEEE Trans. on Emerging Topics in Comp. Intel., 2023.
  * [18] Jie Bu and Anuj Karpatne,  “Quadratic residual networks: A new class of neural networks for solving forward and inverse problems in physics involving pdes,”  in SIAM Int. Conf. on Data Mining (SDM). SIAM, 2021, pp. 675–683.
  * [19] G. A. Baker and P. Graves-Morris,  “Padé approximants,” 1996.
  * [20] B Beckermann and V. Ka.liaguine,  “The diagonal of the padé table and the approximation of the weyl function of second-order difference operators,”  Constructive approximation, vol. 13, pp. 481–510, 1997.
  * [21] C. Ledig, L. Theis, F. Huszár, J. Caballero, A. Cunningham, et al.,  “Photo-realistic single image super-resolution using a generative adversarial network,”  in IEEE/CVF Conf. on Comp. vis. and Patt. Recog. (CVPR), 2017, pp. 4681–4690.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun,  “Deep residual learning for image recognition,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR), 2016, pp. 770–778.
  * [23] S Zagoruyko and N. .Komodakis,  “Wide residual networks,”  arXiv preprint arXiv:1605.07146, 2016.
  * [24] C. Szegedy, S. Ioffe, V. Vanhoucke, and A. Alemi,  “Inception-v4, inception-resnet and the impact of residual connections on learning,”  in AAAI Conf. on artificial intelligence, 2017, vol. 31.
  * [25] W. Shi, J. Caballero, F. Huszár, J. Totz, A. P. Aitken, R. Bishop, D. Rueckert, and Z. Wang,  “Real-time single image and video super-resolution using an efficient sub-pixel convolutional neural network,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR), 2016, pp. 1874–1883.
  * [26] J. Woods, J. Biemond, and A. Tekalp,  “Boundary value problem in image restoration,”  in ICASSP ’85. IEEE International Conference on Acoustics, Speech, and Signal Processing, 1985, vol. 10, pp. 692–695.
  * [27] B. Lim, S. Son, H. Kim, S. Nah, and K. Mu Lee,  “Enhanced deep residual networks for single image super-resolution,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR) Workshops, 2017, pp. 136–144.
  * [28] E. Agustsson and R. Timofte,  “Ntire 2017 challenge on single image super-resolution: Dataset and study,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR) Workshops, July 2017.
  * [29] R. Timofte, E. Agustsson, L. Van Gool, et al.,  “Ntire 2017 challenge on single image super-resolution: Methods and results,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR) Workshops, July 2017.
  * [30] J. T Barron,  “A general and adaptive robust loss function,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR), 2019, pp. 4331–4339.
  * [31] X. Xie, H. Zhou, P a.nd Li, Z. Lin, and S. Yan,  “Adan: Adaptive nesterov momentum algorithm for faster optimizing deep models,”  arXiv preprint arXiv:2208.06677, 2022.
  * [32] Ilya Loshchilov and Frank Hutter,  “Sgdr: Stochastic gradient descent with warm restarts,”  arXiv preprint arXiv:1608.03983, 2016.
  * [33] D. Martin, C. Fowlkes, D. Tal, and J. Malik,  “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,”  in IEEE Int. Conf. on Comp. Vis. (ICCV), 2001, vol. 2, pp. 416–423.
  * [34] Y. Matsui, K. Ito, Y. Aramaki, A. Fujimoto, T. Ogawa, T. Yamasaki, and K. Aizawa,  “Sketch-based manga retrieval using manga109 dataset,”  Multimedia Tools and Applications, vol. 76, pp. 21811–21838, 2017.
  * [35] Marco Bevilacqua, Aline Roumy, Christine Guillemot, and Marie-Line Alberi Morel,  “Low-complexity single-image super-resolution based on nonnegative neighbor embedding,”  in British Machine Vision Conference (BMVC), 2012.
  * [36] R. Zeyde, M. Elad, and M. Protter,  “On single image scale-up using sparse-representations,”  in Int. Conf. on Curves and Surfaces, Avignon, France, June 24-30, 2010, Revised Selected Papers 7. Springer, 2012, pp. 711–730.
  * [37] J.-B. Huang, A. Singh, and N. Ahuja,  “Single image super-resolution from transformed self-exemplars,”  in IEEE/CVF Conf. Comp.Vis. Patt.Recog.(CVPR), 2015, pp. 5197–5206.
  * [38] O. Keleş, M. A. Yılmaz, A. M. Tekalp, C. Korkmaz, and Z. Doğan,  “On the computation of psnr for a set of images or video,”  in Picture Coding Symp. (PCS), 2021, pp. 1–5.
  * [39] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli,  “Image quality assessment: from error visibility to structural similarity,”  IEEE Trans. on Image Processing, vol. 13, no. 4, pp. 600–612, 2004.
  * [40] R. Zhang, P. Isola, A. A. Efros, E. Shechtman, and O. Wang,  “The unreasonable effectiveness of deep features as a perceptual metric,”  in IEEE/CVF Conf. on Comp. Vis. and Patt. Recog. (CVPR), 2018, pp. 586–595.
  * [41] K. Simonyan and A. Zisserman,  “Very deep convolutional networks for large-scale image recognition,”  arXiv preprint arXiv:1409.1556, 2014.