# Boosting as Frank-Wolfe

Ryotaro Mitsuboshi
Kyushu University/RIKEN AIP
<EMAIL_ADDRESS>
& Kohei Hatano
Kyushu University/RIKEN AIP
<EMAIL_ADDRESS>
&Eiji Takimoto
Kyushu University
<EMAIL_ADDRESS>

###### Abstract

Some boosting algorithms, such as LPBoost, ERLPBoost, and C-ERLPBoost, aim to
solve the soft margin optimization problem with the $\ell_{1}$-norm
regularization. LPBoost rapidly converges to an $\epsilon$-approximate
solution in practice, but it is known to take $\Omega(m)$ iterations in the
worst case, where $m$ is the sample size. On the other hand, ERLPBoost and
C-ERLPBoost are guaranteed to converge to an $\epsilon$-approximate solution
in $O(\frac{1}{\epsilon^{2}}\ln\frac{m}{\nu})$ iterations, where $\nu\in[1,m]$
is a hyperparameter. However, the overall computations are very high compared
to LPBoost.

To address this issue, we propose a generic boosting scheme that combines the
Frank-Wolfe algorithm and any secondary algorithm and switches one to the
other iteratively. We show that the scheme retains the same convergence
guarantee as ERLPBoost and C-ERLPBoost. One can incorporate any secondary
algorithm to improve in practice. This scheme comes from a unified view of
boosting algorithms for soft margin optimization. More specifically, we show
that LPBoost, ERLPBoost, and C-ERLPBoost are instances of the Frank-Wolfe
algorithm. In experiments on real datasets, one of the instances of our scheme
exploits the better updates of the second algorithm and performs comparably
with LPBoost.

_Keywords_ Boosting $\cdot$ Frank-Wolfe $\cdot$ Soft margin optimization

##  1 Introduction

Theory and algorithms for large-margin classifiers have been studied
extensively since those classifiers guarantee low generalization errors when
they have large margins over training examples (e.g., Schapire et al. (1998);
Mohri et al. (2018)). In particular, the $\ell_{1}$-norm regularized soft
margin optimization problem, defined later, is a formulation of finding sparse
large-margin classifiers based on the linear program (LP). This problem aims
to optimize the $\ell_{1}$-margin by combining multiple hypotheses from some
hypothesis class $\mathcal{H}$. The resulting classifier tends to be sparse,
so $\ell_{1}$-margin optimization is helpful for feature selection tasks. Off-
the-shelf LP solvers can solve the problem, but they are still not efficient
enough for a huge class $\mathcal{H}$.

Boosting is a framework for solving the $\ell_{1}$-norm regularized margin
optimization even though $\mathcal{H}$ is infinitely large. Various boosting
algorithms have been invented. LPBoost (Demiriz et al., 2002) is a practical
algorithm that often works effectively. Although LPBoost terminates rapidly,
It is shown that it takes $\Omega(m)$ iterations in the worst case, where $m$
is the number of training examples (Warmuth et al., 2007). Shalev-Shwartz and
Singer (2010) invented an algorithm called Corrective ERLPBoost (we call this
algorithm C-ERLPBoost for shorthand) in the paper on ERLPBoost (Warmuth et
al., 2008). C-ERLPBooost and ERLPBoost find $\epsilon$-approximate solutions
in $O(\ln(m/\nu)/\epsilon^{2})$ iterations, where $\nu\in[1,m]$ is the soft
margin parameter. The difference is the time complexity per iteration;
ERLPBoost solves a convex program (CP) for each iteration, while C-ERLPBooost
solves a sorting-like problem. Although ERLPBoost takes much time per
iteration, it takes fewer iterations than C-ERLPBoost in practical
applications. For this reason, ERLPBoost is faster than C-ERLPBoost. Our
primary motivation is to investigate boosting algorithms with provable
iteration bounds, which perform as fast as LPBoost.

This paper has two contributions. Our first contribution is to give a unified
view of boosting for soft margin optimization. We show that LPBoost,
ERLPBoost, and C-ERLPBoost are instances of the Frank-Wolfe algorithm.

Our second contribution is to propose a generic scheme for boosting based on
the unified view. Our scheme combines a standard Frank-Wolfe algorithm and
_any_ algorithm and switches one to the other at each iteration in a non-
trivial way. We show that this scheme guarantees the same convergence rate,
$O(\ln(m/\nu)/\epsilon^{2})$, as ERLPBoost and C-ERLPBoost. One can
incorporate any update rule to this scheme without losing the convergence
guarantee so that it takes advantage of better updates of the second algorithm
in practice. In particular, we propose to choose LPBoost as the secondary
algorithm, and we call the resulting algorithm Modified LPBoost (MLPBoost).

In experiments on real datasets, MLPBoost works comparably with LPBoost, and
MLPBoost is the fastest among theoretically guaranteed algorithms, as
expected.

Table 1 compares LPBoost, ERLPBoost, C-ERLPBoost, and MLPBoost.

Table 1: Comparison of the boosting algorithms. C-ERLPBoost solves the problem per iteration by sorting based algorithm, while our work and LPBoost solves linear programming (LP). ERLPBoost solves convex programming (CP) per iteration. In practice, the algorithms work fast in the order LPBoost, ERLPBoost, and C-ERLPBoost. As we show in section 5, our algorithm is as fast as LPBoost.  | LPBoost | C-ERLPBoost | ERLPBoost | One of our work
---|---|---|---|---
Iter. bound | $\Omega(m)$ | $O\left(\frac{1}{\epsilon^{2}}\ln\frac{m}{\nu}\right)$ | $O\left(\frac{1}{\epsilon^{2}}\ln\frac{m}{\nu}\right)$ | $O\left(\frac{1}{\epsilon^{2}}\ln\frac{m}{\nu}\right)$
Problem per iter. | LP | Sorting | CP | LP

##  2 Basic definitions

This paper considers binary classification boosting. We use the same notations
as in (Shalev-Shwartz and Singer, 2010). Let
$S:=((\bm{x}_{i},y_{i}))_{i=1}^{m}\in(\mathcal{X}\times\\{\pm 1\\})^{m}$ be a
sequence of $m$-examples, where $\mathcal{X}$ is some set. Let
$\mathcal{H}\subset[-1,+1]^{\mathcal{X}}$ be a set of hypotheses. For
simplicity, we assume $|\mathcal{H}|=|\\{h_{1},h_{2},\dots,h_{n}\\}|=n$. Note
that our scheme can use an infinite set $\mathcal{H}$. It is convenient to
regard each $h_{j}\in\mathcal{H}$ as a canonical basis vector
$\bm{e}_{j}\in\mathbb{R}^{n}$. Let
$A=(y_{i}h_{j}(\bm{x}_{i}))_{i,j}\in[-1,+1]^{m\times n}$ be a matrix of size
$m\times n$. We denote $m$-dimensional capped probability simplex as
$\mathcal{P}^{m}_{\nu}:=\\{\bm{d}\in[0,1/\nu]^{m}\mid\|\bm{d}\|_{1}=1\\}$,
where $\nu\in[1,m]$. We write $\mathcal{P}^{m}=\mathcal{P}^{m}_{1}$ for
shorthand. For a set $\mathcal{C}\subset\mathbb{R}^{n}$, we denote the convex
hull of $\mathcal{C}$ as $\mathop{\rm
CH}(\mathcal{C}):=\left\\{\sum_{k}w_{k}\bm{s}_{k}\mid\sum_{k}w_{k}=1,w_{k}\geq
0,\\{\bm{s}_{k}\\}_{k}\subset\mathcal{C}\right\\}$.

Next, we define some properties for convex functions.

######  Definition 1 (smooth function).

A function $f:\mathbb{R}^{m}\to\mathbb{R}$ is said to be $\eta$-smooth over a
convex set $\mathcal{C}\subset\mathbb{R}^{m}$ w.r.t. a norm $\|\cdot\|$ if

$\displaystyle\forall\bm{x},\bm{y}\in\mathcal{C},\quad f(\bm{y})\leq
f(\bm{x})+(\bm{y}-\bm{x})^{\top}\nabla
f(\bm{x})+\frac{\eta}{2}\|\bm{y}-\bm{x}\|^{2}.$ (1)

Similarly, we define the strongly convex function.

######  Definition 2 (strongly convex function).

A function $f:\mathbb{R}^{m}\to\mathbb{R}$ is said to be $\eta$-strongly
convex over a convex set $C\subset\mathbb{R}^{m}$ w.r.t. a norm $\|\cdot\|$ if

$\displaystyle\forall\bm{x},\bm{y}\in\mathcal{C},\quad f(\bm{y})\geq
f(\bm{x})+(\bm{y}-\bm{x})^{\top}\nabla
f(\bm{x})+\frac{\eta}{2}\|\bm{y}-\bm{x}\|^{2}.$

We also define Fenchel conjugate.

######  Definition 3 (Fenchel conjugate).

The Fenchel conjugate $f^{\star}$ of a function
$f:\mathbb{R}^{m}\to[-\infty,+\infty]$ is defined as

$\displaystyle
f^{\star}(\bm{\theta})=\sup_{\bm{d}\in\mathbb{R}^{m}}\left(\bm{d}^{\top}\bm{\theta}-f(\bm{d})\right).$

It is well known that if $f$ is a $1/\eta$-strongly convex function w.r.t. the
norm $\|\cdot\|$ for some $\eta>0$, $f^{\star}$ is an $\eta$-smooth function
w.r.t. the dual norm $\|\cdot\|_{\star}$. Further, if $f$ is a strongly convex
function, the gradient vector of $f^{\star}$ is written as

$\displaystyle\nabla
f^{\star}(\bm{\theta})=\arg\sup_{\bm{d}\in\mathbb{R}^{m}}\left(\bm{d}^{\top}\bm{\theta}-f(\bm{d})\right).$

One can find the proof of these properties here (Borwein and Lewis, 2006;
Shalev-Shwartz and Singer, 2010).

######  Lemma 1.

Let $f,\tilde{f}:\mathbb{R}^{m}\to(-\infty,+\infty]$ be functions such that

$\displaystyle\exists
c>0,\forall\bm{\theta},f(\bm{\theta})\leq\tilde{f}(\bm{\theta})\leq
f(\bm{\theta})+c.$

Then, $f^{\star}(\bm{\mu})-c\leq\tilde{f}^{\star}(\bm{\mu})\leq
f^{\star}(\bm{\mu})$ holds for all $\bm{\mu}$.

Finally, we show the duality theorem (Borwein and Lewis, 2006).

######  Theorem 1 (Borwein and Lewis (2006)).

Let $f:\mathbb{R}^{m}\to(-\infty,+\infty]$ and
$g:\mathbb{R}^{n}\to(-\infty,+\infty]$ be convex functions, and a linear map
$A:\mathbb{R}^{m}\to\mathbb{R}^{n}$. Define the Fenchel problems

$\displaystyle\gamma$
$\displaystyle=\inf_{\bm{d}}f(\bm{d})+g(A^{\top}\bm{d}),$ (2)
$\displaystyle\rho$
$\displaystyle=\sup_{\bm{w}}-f^{\star}(-A\bm{w})-g^{\star}(\bm{w}).$ (3)

Then, $\gamma\geq\rho$ holds. Further, $\gamma=\rho$ holds if 111For a set
$\mathcal{C}\subset\mathbb{R}^{n}$, $\mathop{\rm int}(C)=\\{\bm{w}\in
C\mid\forall\bm{v}\in\mathbb{R}^{n},\exists
t>0,\forall\tau\in[0,t],\bm{w}+\tau\bm{v}\in C\\}$ and
$\mathop{\rm dom}g-A^{\top}\mathop{\rm
dom}f=\\{\bm{w}-A^{\top}\bm{d}\mid\bm{w}\in\mathop{\rm
dom}g,\bm{d}\in\mathop{\rm dom}f\\}$.  $\bm{0}\in\mathop{\rm
int}\left(\mathop{\rm dom}g-A^{\top}\mathop{\rm dom}f\right)$. Furthermore,
points $\bar{\bm{d}}\in\mathcal{P}^{m}_{\nu}$ and
$\bar{\bm{w}}\in\mathcal{P}^{n}$ are optimal solutions for problems (2) and
(3), respectively, if and only if $-A\bar{\bm{w}}\in\partial f(\bar{\bm{d}})$
and $\bar{\bm{w}}\in\partial g(A^{\top}\bar{\bm{d}})$.

With these notations, we define the soft margin optimization problem as the
dual problem of the edge minimization problem. The edge minimization problem
is defined as

$\displaystyle\min_{\bm{d}}\max_{j\in[n]}(\bm{d}^{\top}A)_{j}+f(\bm{d}),\quad\text{where}\quad
f(\bm{d})=\begin{cases}0&\bm{d}\in\mathcal{P}^{m}_{\nu}\\\
+\infty&\bm{d}\notin\mathcal{P}^{m}_{\nu}\end{cases}.$ (4)

The quantity $(\bm{d}^{\top}A)_{j}=\sum_{i=1}^{m}d_{i}y_{i}h_{j}(\bm{x}_{i})$
is often called the _edge_ of the hypothesis $h_{j}$ w.r.t. the distribution
$\bm{d}\in\mathcal{P}^{m}_{\nu}$. Shalev-Shwartz and Singer (2010) showed that
the $\ell_{1}$-norm regularized soft margin optimization problem is formulated
via Fenchel duality as

$\displaystyle\max_{\bm{w}\in\mathcal{P}^{n}}-f^{\star}(-A\bm{w})=\max_{\bm{w}\in\mathcal{P}^{n}}\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\bm{d}^{\top}A\bm{w}.$
(5)

Furthermore, the duality gap between (4) and (5) is zero. The soft margin
optimization aims to find an optimal combined hypothesis
$H_{T}=\sum_{j=1}^{n}\bar{w}_{j}h_{j}$, where $\bar{\bm{w}}\in\mathcal{P}^{n}$
is an optimal solution of (5). Although the edge minimization and soft margin
optimization problems are formulated as a linear program, solving the problem
for a huge class $\mathcal{H}$ is hard. Boosting is a standard approach to
dealing with the problem.

###  2.1 Boosting

Boosting is a protocol between two algorithms; the booster and the weak
learner. For each iteration $t=0,1,2,\dots,T$, the booster chooses a
distribution $\bm{d}_{t}\in\mathcal{P}^{m}_{\nu}$ over the training examples
$S$. Then, the weak learner returns a hypothesis $h_{j_{t+1}}\in\mathcal{H}$
to the booster that satisfies $({\bm{d}_{t}}^{\top}A)_{j_{t+1}}\geq g$ for
some unknown guarantee $g>0$. The boosting algorithm aims to produce a convex
combination $H_{T}=\sum_{t=1}^{T}w_{T,j_{t}}h_{j_{t}}$ of the hypotheses
$\\{h_{j_{1}},h_{j_{2}},\dots,h_{j_{T}}\\}\subset\mathcal{H}$ that satisfies

$\displaystyle-f^{\star}(-A\bm{w}_{T})=\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\bm{d}^{\top}A\bm{w}_{T}=\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\sum_{i=1}^{m}d_{i}y_{i}H_{T}(\bm{x}_{i})\geq
g-\epsilon$ (6)

for any predefined $\epsilon>0$. Suppose that the weak learner always returns
a max-edge hypothesis for any given distribution
$\bm{d}\in\mathcal{P}^{m}_{\nu}$. In that case, the goal is to find an
$\epsilon$-approximate solution of (5).

###  2.2 The Frank-Wolfe algorithms

We briefly introduce the standard Frank-Wolfe algorithm. The original Frank-
Wolfe (FW) algorithm is a first-order iterative algorithm invented by Frank
and Wolfe (1956). The FW algorithm solves the problems of the form:
$\min_{\bm{x}\in\mathcal{C}}f(\bm{x})$, where
$\mathcal{C}\subset\mathbb{R}^{m}$ is a closed convex set and
$f:\mathcal{C}\to\mathbb{R}$ is an $\eta$-smooth and convex function.

In each iteration $t$, the FW algorithm seeks an extreme point
$\bm{s}_{t+1}\in\arg\min_{\bm{s}\in\mathcal{C}}\bm{s}^{\top}\nabla
f(\bm{x}_{t})$. Then, it updates the iterate as
$\bm{x}_{t+1}=\bm{x}_{t}+\lambda_{t}(\bm{s}_{t+1}-\bm{x}_{t})$ for some
$\lambda_{t}\in[0,1]$. Although the classical result (Frank and Wolfe, 1956;
Jaggi, 2013) suggests $\lambda_{t}=2/(t+2)$, $\lambda_{t}$ has many choices.
For example, one can choose $\lambda_{t}$ as

$\displaystyle\lambda_{t}:=\mathop{\rm
clip}_{[0,1]}\frac{(\bm{x}_{t}-\bm{s}_{t+1})^{\top}\nabla
f(\bm{x}_{t})}{\eta\|\bm{s}_{t+1}-\bm{x}_{t}\|^{2}},$ (7)

where $\mathop{\rm clip}_{[0,1]}x=\max\\{0,\min\\{1,x\\}\\}$. This optimal
solution minimizes the right-hand side of the inequality (1) and is often
called the _short-step_ strategy. Alternatively, one can choose
$\lambda_{t}\in\arg\min_{\lambda\in[0,1]}f(\bm{x}_{t}+\lambda(\bm{s}_{t+1}-\bm{x}_{t}))$
by line search. This step size improve the objective more than the short-step
strategy. Since the FW algorithm aims to find an optimal solution, one can
choose $\bm{x}_{t+1}$ by solving the problem:
$\bm{x}_{t+1}\leftarrow\arg\min_{\bm{x}\in\mathop{\rm
CH}(\\{\bm{s}_{1},\dots,\bm{s}_{t+1}\\})}f(\bm{x})$. This update rule is
called the _Fully Corrective_ FW algorithm (e.g., Jaggi (2013)). Although the
fully corrective update yields $\bm{x}_{t+1}$ that most decreases the
objective over the convex hull, it loses the fast computational advantage per
iteration.

The FW algorithms converge to an $\epsilon$-approximate solution in
$O(\eta/\epsilon)$ iterations if the objective function is $\eta$-smooth
w.r.t. some norm over $\mathcal{C}$ (Jaggi, 2013; Frank and Wolfe, 1956). The
best advantage of the FW algorithm is the projection-free property; there is
no projection onto $\mathcal{C}$, so the running time per iteration is faster
than the projected gradient methods.

##  3 Related work

FWBoost (Wang et al., 2015) seems to be related to our work. FWBoost is a
boosting algorithm designed for minimizing a general loss function by the
Frank-Wolfe algorithm. Since the Frank-Wolfe algorithm works over the closed
convex set, they introduce the $\ell_{1}$-norm ball constraint. Note that the
objective function for the maximization problem (5) is not a strongly-smooth
function, so one cannot apply the FWBoost directly to guarantee the
convergence rate.

LPBoost (Demiriz et al., 2002) is a practical boosting algorithm for solving
problem (5). In each iteration $t$, LPBoost updates its distribution as an
optimal solution to problem

$\displaystyle\min_{\bm{d}}\max_{k\in[t]}(\bm{d}^{\top}A)_{j_{k}}+f(\bm{d}).$
(8)

That is, LPBoost uses an optimal solution to the edge minimization problem
over the hypothesis set
$\\{h_{j_{1}},h_{j_{2}},\dots,h_{j_{t}}\\}\subset\mathcal{H}$. LPBoost
converges to an $\epsilon$-accurate solution rapidly in practice. However,
Warmuth et al. (2007) proved that LPBoost converges in $\Omega(m)$ iterations
for the worst case. After that, the stabilized version of LPBoost, ERLPBoost,
was invented by Warmuth et al. (2008). ERLPBoost updates the distribution as
the solution of

$\displaystyle\min_{\bm{d}}\max_{k\in[t]}(\bm{d}^{\top}A)_{j_{k}}+f(\bm{d})+\frac{1}{\eta}\Delta(\bm{d}).$
(9)

Here, $\Delta(\bm{d})=\sum_{i=1}^{m}d_{i}\ln d_{i}+\ln m$ is the relative
entropy from the uniform distribution
$\frac{1}{m}\bm{1}\in\mathcal{P}^{m}_{\nu}$. They proved that ERLPBoost finds
a solution that achieves (6) in $O(\ln(m/\nu)/\epsilon^{2})$ iterations. They
also demonstrate that ERLPBoost tends to terminate in fewer iterations than
LPBoost. The disadvantage of ERLPBoost is its computational complexity;
ERLPBoost solves convex programs in each iteration. This disadvantage leads to
much more computation time than LPBoost. C-ERLPBoost (Shalev-Shwartz and
Singer, 2010) is the corrective version of ERLPBoost. This algorithm achieves
the same iteration bound with much faster computation per iteration than
LPBoost. C-ERLPBoost maintains the weight $\bm{w}_{t}\in\mathcal{P}^{n}$ that
only has non-zero values on $\\{w_{t,j_{1}},w_{t,j_{2}},\dots,w_{t,j_{t}}\\}$
corresponding to the past hypotheses
$\\{h_{j_{1}},h_{j_{2}},\dots,h_{j_{t}}\\}\subset\mathcal{H}$. C-ERLPBoost
updates its distribution over the training instances as

$\displaystyle\bm{d}_{t}\leftarrow\arg\min_{\bm{d}}\bm{d}^{\top}A\bm{w}_{t}+f(\bm{d})+\frac{1}{\eta}\Delta(\bm{d}).$
(10)

After receiving a hypothesis $h_{j_{t+1}}\in\mathcal{H}$ with the
corresponding basis $\bm{e}_{j+1}\in\mathcal{P}^{n}$, C-ERLPBoost updates the
weights on hypotheses as
$\bm{w}_{t+1}=\bm{w}_{t}+\lambda(\bm{e}_{j_{t+1}}-\bm{w}_{t})$, where
$\lambda_{t}\in[0,1]$ is some proper value. Although this update rule seems to
be a convex program, Shalev-Shwartz and Singer (2010) showed an algorithm that
solves (10) in $O(m\ln m)$ time. This algorithm seems better than LPBoost and
ERLPBoost. However, Warmuth et al. (2008) demonstrated that C-ERLPBoost takes
much more iterations than LPBoost and ERLPBoost. Therefore, the overall
computation time is worse than LPBoost.

##  4 Main results

We first show a unified view of the boosting algorithms via Fenchel duality.
From this view, LPBoost, ERLPBoost, and C-ERLPBoost can be seen as instances
of the Frank-Wolfe algorithm with different step sizes and objectives. Using
this knowledge, we derive a new boosting scheme.

###  4.1 A unified view of boosting for the soft margin optimization

This section assumes that the weak learner always returns a hypothesis
$h\in\mathcal{H}$ that maximizes the edge w.r.t. the given distribution. We
start by revisiting C-ERLPBoost. Recall that C-ERLPBoost (and ERLPBoost) aim
to solve the convex program

$\displaystyle\min_{\bm{d}}\max_{j\in[n]}(\bm{d}^{\top}A)_{j}+\tilde{f}^{\star}(\bm{d}),$
(11)

where $\tilde{f}=f+\frac{1}{\eta}\Delta$. Since $\frac{1}{\eta}\Delta$ is a
$\frac{1}{\eta}$-strongly convex function w.r.t. $\ell_{1}$-norm, so does
$\tilde{f}$. By Fenchel duality, the dual problem is

$\displaystyle\max_{\bm{w}\in\mathcal{P}^{n}}-\tilde{f}^{\star}(-A\bm{w})=-\min_{\bm{w}\in\mathcal{P}^{n}}\tilde{f}^{\star}(-A\bm{w})=-\min_{\bm{\theta}\in-A\mathcal{P}^{n}}\tilde{f}^{\star}(\bm{\theta}),$
(12)

where $-A\mathcal{P}^{n}=\\{-A\bm{d}\mid\bm{d}\in\mathcal{P}^{n}\\}$, with
zero duality gap. Further, $\tilde{f}^{\star}$ is an $\eta$-smooth function
w.r.t. $\ell_{\infty}$-norm. Thus, the soft margin optimization problem
becomes a minimization problem of a smooth function.

In each iteration $t$, C-ERLPBoost updates the distribution
$\bm{d}_{t}\in\mathcal{P}^{m}_{\nu}$ over examples as the optimal solution of
(10). This computation corresponds to the gradient computation
$\nabla\tilde{f}^{\star}(\theta_{t})$, where $\theta_{t}=-A\bm{w}_{t}$. Then,
obtain a basis vector $\bm{e}_{j_{t+1}}\in\mathcal{P}^{n}$ corresponding to
hypothesis $h_{j_{t+1}}\in\mathcal{H}$ that maximizes the edge;
$j_{t+1}\in\arg\max_{j\in[n]}(\bm{d}_{t}^{\top}A)_{j}$. We can write this
calculation regarding the gradient of $\tilde{f}^{\star}$;

$\displaystyle\arg\max_{\bm{e}_{j}:j\in[n]}\bm{d}_{t}^{\top}A\bm{e}_{j}=\arg\min_{\bm{e}_{j}:j\in[n]}(-A\bm{e}_{j})^{\top}\nabla\tilde{f}^{\star}(\bm{\theta}_{t})=\arg\min_{\bm{\theta}\in-A\mathcal{P}^{n}}\bm{\theta}^{\top}\nabla\tilde{f}^{\star}(\bm{\theta}_{t}).$

Thus, finding a hypothesis that maximizes edge corresponds to solving linear
programming in the Frank-Wolfe algorithm. Further, C-ERLPBoost updates the
weights as $\bm{w}_{t+1}=\bm{w}_{t}+\lambda_{t}(\bm{e}_{j_{t+1}}-\bm{w}_{t})$,
where $\lambda_{t}$ is the short-step 222They also suggests the line search
update. This case yields a better progress than short-step, so the same
iteration bound holds. , as in eq. (7). From these observations, we can say
that the C-ERLPBoost is an instance of the Frank-Wolfe algorithm. Since
$\tilde{f}^{\star}$ is $\eta$-smooth, we can say that this algorithm converges
in $O(\eta/\epsilon)$ iterations for a max-edge weak learner.

Similarly, we can say that LPBoost and ERLPBoost are instances of the Frank-
Wolfe algorithm. Let $J_{t}:=\\{j_{1},j_{2},\dots,j_{t}\\}$ be the set of
indices corresponding to the hypotheses
$\\{h_{j_{1}},h_{j_{2}},\dots,h_{j_{t}}\\}$ and
$\mathcal{E}_{t}:=\\{\bm{e}_{j}\mid j\in J_{t}\\}$ be the corresponding basis
vectors. LPBoost and ERLPBoost update the distribution as the optimal
solutions $\bm{d}_{t}^{\rm{L}}\in\partial f^{\star}(-A\bm{w}_{t}^{\rm L})$ and
$\bm{d}_{t}^{\rm{E}}=\nabla\tilde{f}^{\star}(-A\bm{w}_{t}^{\rm E})$, where

(LPBoost)
$\displaystyle\bm{w}_{t}^{\rm{L}}\leftarrow\arg\max_{\bm{w}\in\mathop{\rm
CH}(\mathcal{E}_{t})}-f^{\star}(-A\bm{w}),$ (13) (ERLPBoost)
$\displaystyle\bm{w}_{t}^{\rm{E}}\leftarrow\arg\max_{\bm{w}\in\mathop{\rm
CH}(\mathcal{E}_{t})}-\tilde{f}^{\star}(-A\bm{w}).$ (14)

Therefore, we can say that LPBoost and ERLPBoost are instances of the fully-
corrective FW algorithm for objectives $f^{\star}$ and $\tilde{f}^{\star}$,
respectively. Under the max-edge weak learner assumption, one can derive the
same iteration bound for ERLPBoost since $\tilde{f}^{\star}$ is $\eta$-smooth.
We summarize these connections to the following theorem.

######  Theorem 2.

LPBoost, ERLPBoost, and C-ERLPBoost are instances of the FW algorithm.

###  4.2 Generic schemes for margin-maximizing boosting

0: Training examples
$S=\left((\bm{x}_{i},y_{i})\right)_{i=1}^{m}\in(\mathcal{X}\times\\{\pm
1\\})^{m}$, a hypothesis set $\mathcal{H}\subset[-1,+1]^{\mathcal{X}}$, a FW
algorithm $\mathcal{F}$, a secondary algorithm $\mathcal{B}$, and parameters
$\nu>0$ and $\epsilon>0$.

1: Set $A=\left(y_{i}h_{j}(\bm{x}_{i})\right)_{i,j}\in[-1,+1]^{m\times n}$.

2: Send $\bm{d}_{0}=\frac{1}{m}\bm{1}$ to the weak learner and obtain a
hypothesis $h_{j_{1}}\in\mathcal{H}$.

3: Set $\bm{w}_{1}=\bm{e}_{j_{1}}$.

4: for $t=1,2,\dots,T$ do

5: Compute the distribution
$\bm{d}_{t}=\nabla\tilde{f}^{\star}(-A\bm{w}_{t})=\arg\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\left[\bm{d}^{\top}A\bm{w}_{t}+\frac{1}{\eta}\Delta(\bm{d})\right]$.

6: Obtain a hypothesis $h_{j_{t+1}}\in\mathcal{H}$ and the corresponding basis
vector $\bm{e}_{j_{t+1}}\in\mathcal{P}^{n}$.

7: Set $\epsilon_{t}:=\min_{0\leq\tau\leq
t}(\bm{d}_{\tau}^{\top}A)_{j_{\tau+1}}+\tilde{f}^{\star}(-A\bm{w}_{t})$ and
let $\mathcal{E}_{t+1}:=\\{\bm{e}_{j_{\tau}}\\}_{\tau=1}^{t+1}$.

8: if $\epsilon_{t}\leq\epsilon/2$ then

9: Set $T=t$, break.

10: end if

11: Compute the FW weight
$\bm{w}_{t+1}^{(1)}=\mathcal{F}(A,\bm{w}_{t},\bm{e}_{j_{t+1}},\mathcal{E}_{t},\bm{d}_{t})$.

12: Compute the secondary weight
$\bm{w}_{t+1}^{(2)}=\mathcal{B}(A,\mathcal{E}_{t+1})$.

13: Update the weight
$\bm{w}_{t+1}\leftarrow\arg\min_{\bm{w}_{t+1}^{(k)}:k\in\\{1,2\\}}\tilde{f}^{\star}(-A\bm{w}_{t+1}^{(k)})$.

14: end for

14: Combined classifier $H_{T}=\sum_{t=1}^{T}w_{T,t}h_{t}$.

Algorithm 1 A theoretically guaranteed boosting scheme

0: A matrix $A=\left(y_{i}h_{j}(\bm{x}_{i})\right)_{i,j}\in[-1,+1]^{m\times
n}$ and a set of basis vectors $\mathcal{E}_{t+1}\subset\mathcal{P}^{n}$.

0: $\bm{w}\leftarrow\arg\max_{\bm{w}\in\mathop{\rm
CH}(\mathcal{E}_{t+1})}\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\bm{d}^{\top}A\bm{w}$.

Algorithm 2 LPBoost rule $\mathcal{B}(A,\mathcal{E}_{t+1})$

0: $\bm{w}_{t+1}^{(1)}=\bm{w}_{t}+\lambda_{t}(\bm{e}_{j_{t+1}}-\bm{w}_{t})$,
where $\lambda_{t}=\mathop{\rm
clip}_{[0,1]}\frac{\bm{d}_{t}^{\top}A(\bm{e}_{j+1}-\bm{w}_{t})}{\eta\|A(\bm{e}_{j+1}-\bm{w}_{t})\|_{\infty}^{2}}$.

Algorithm 3 Short step rule
$\mathcal{F}(A,\bm{w}_{t},\bm{e}_{j_{t+1}},\mathcal{E}_{t},\bm{d}_{t})$

We propose FW-like boosting schemes from the above observations, shown in
Algorithm 1. Algorithm 1 takes two update rules, a FW update rule
$\mathcal{F}$ and a secondary update rule $\mathcal{B}$. Both algorithms
return a weight $\bm{w}\in\mathcal{P}^{n}$. Intuitively, the FW update rule
$\bm{w}_{t}^{(1)}$ is a safety net for the convergence guarantee. Further, the
convergence analysis only depends on the FW update $\bm{w}_{t+1}^{(1)}$, so
that one can incorporate any update rule to $\mathcal{B}$. For example, one
can use the update rule (14) as $\mathcal{B}(A,\mathcal{E}_{t+1})$. Algorithm
1 becomes ERLPBoost in this case since $\bm{w}_{t+1}=\bm{w}_{t+1}^{(2)}$ holds
for any $t$. Even though this setting, the convergence guarantee holds so that
we can prove the same convergence rate for ERLPBoost by our general analysis.

Recall that our primary objective is to find a weight vector $\bm{w}$ that
optimizes the linear program (5). The most practical algorithm, LPBoost,
solves the optimization problem over past hypotheses, so using the solution as
$\mathcal{B}$ is a natural choice. Algorithm 2 summarizes this update. Note
that the LPBoost update differs from the fully-corrective FW algorithm since
the objective function is $\tilde{f}^{\star}$, not $f^{\star}$.

Furthermore, as described in (Shalev-Shwartz and Singer, 2010), one can
compute the distribution $\bm{d}_{t}=\nabla\tilde{f}^{\star}(-A\bm{w}_{t})$ by
a sorting-based algorithm, which takes $O(m\ln m)$ iterations333They also
suggest a linear time algorithm, see (Herbster and Warmuth, 2001). . Thus, the
time complexity per iteration depends on the secondary algorithm
$\mathcal{B}$.

Before getting into the convergence analysis, we first justify the stopping
criterion in Algorithm 2. This criterion is similar to the one in C-ERLPBoost
but better than it. Therefore, our algorithms tend to converge in early
iterations.

######  Lemma 2.

Let $\epsilon_{t}:=\min_{0\leq\tau\leq
t}(\bm{d}_{\tau}^{\top}A)_{j_{\tau+1}}+\tilde{f}^{\star}(-A\bm{w}_{t})$ be the
optimality gap defined in Algorithm 2 and let $\eta=2\ln(m/\nu)/\epsilon$.
Then, $\epsilon_{t}\leq\epsilon/2$ implies $-f^{\star}(-A\bm{w}_{t})\geq
g-\epsilon$.

###### Proof.

By the weak-learnability assumption, $\epsilon_{t}\geq
g+\tilde{f}^{\star}(-A\bm{w}_{t})$. The statement follows from Lemma 1. ∎

Now, we prove the convergence rate for our scheme. This theorem shows the same
convergence guarantee for ERLPBoost and C-ERLPBoost.

######  Theorem 3 (A convergence rate for Algorithm 1).

Assume that the weak learner returns a hypothesis $h_{j_{t+1}}\in\mathcal{H}$
that satisfies $(\bm{d}_{t}^{\top}A)_{j_{t+1}}\geq g$ for some unknown
guarantee $g$. Let $\mathcal{F}$ be a FW update with classic step
$\lambda_{t}=\frac{2}{t+2}$, or short-step as in Algorithm 3. Then, for any
secondary algorithm $\mathcal{B}$, Algorithm 1 converges to an
$\epsilon$-accurate solution of (5) in
$O\left(\frac{1}{\epsilon^{2}}\ln\frac{m}{\nu}\right)$ iterations.

###### Proof.

First of all, we prove the bound for the classic step size. We start by
showing the recursion

$\displaystyle\epsilon_{t+1}\leq(1-\lambda_{t})\epsilon_{t}+2\eta\lambda_{t}^{2}.$
(15)

By using the definition of $\bm{w}_{t+1}$ and the $\eta$-smoothness of
$\tilde{f}^{\star}$,

$\displaystyle\epsilon_{t}-\epsilon_{t+1}$
$\displaystyle\geq\tilde{f}^{\star}(-A\bm{w}_{t})-\tilde{f}^{\star}(-A\bm{w}_{t}^{(1)})$
$\displaystyle=\tilde{f}^{\star}(-A\bm{w}_{t})-\tilde{f}^{\star}(-A\bm{w}_{t}+\lambda_{t}A(\bm{w}_{t}-\bm{e}_{{j_{t}+1}}))$
$\displaystyle\geq\lambda_{t}(A(\bm{e}_{j_{t+1}}-\bm{w}_{t}))^{\top}\nabla\tilde{f}^{\star}(-A\bm{w}_{t})-2\eta\lambda_{t}^{2},$
(16)

where eq. (16) holds since $A\in[-1,+1]^{m\times n}$ and
$\bm{e}_{j_{t+1}},\bm{w}_{t}\in\mathcal{P}^{n}$. By the non-negativity of the
entropy function and the definition of $\bm{d}_{t}$, we get

$\displaystyle\lambda_{t}(A(\bm{e}_{j_{t+1}}-\bm{w}_{t}))^{\top}\nabla\tilde{f}^{\star}(-A\bm{w}_{t})$
$\displaystyle=\lambda_{t}\bm{d}_{t}^{\top}A(\bm{e}_{j_{t+1}}-\bm{w}_{t})$
$\displaystyle\geq\lambda_{t}\left[\min_{0\leq\tau\leq
t}(\bm{d}_{\tau}^{\top}A)_{j_{\tau+1}}-\bm{d}_{t}^{\top}A\bm{w}_{t}-\frac{1}{\eta}\Delta(\bm{d}_{t})\right]$
$\displaystyle=\lambda_{t}\left[\min_{0\leq\tau\leq
t}(\bm{d}_{\tau}^{\top}A)_{j_{\tau+1}}+\tilde{f}^{\star}(-A\bm{w}_{t})\right]=\lambda_{t}\epsilon_{t}.$
(17)

Combining eq. (16) and (17), we obtain (15).

Now, we prove the following inequality by induction on $t$.

$\displaystyle\epsilon_{t}\leq\frac{8\eta}{t+2},\quad\forall t=1,2,\dots$ (18)

For the base case $t=1$, the inequality (18) holds;
$\epsilon_{1}\leq(1-\lambda_{0})\epsilon_{0}+2\eta\lambda_{0}^{2}=2\eta\leq\frac{8\eta}{1+2}$.
Assume that (18) holds for $t\geq 1$. By the inductive assumption,

$\displaystyle\epsilon_{t+1}\leq(1-\lambda_{t})\epsilon_{t}+2\eta\lambda_{t}^{2}\leq\frac{t}{t+2}\frac{8\eta}{t+2}+2\eta\left(\frac{2}{t+2}\right)^{2}=8\eta\frac{t}{t+2}\frac{t+1}{t+2}\leq\frac{8\eta}{t+3}.$

Therefore, (18) holds for all $t\geq 1$.

By the definition of $\eta$, $\epsilon_{T}\leq\frac{\epsilon}{2}$ holds after
$T\geq\frac{32}{\epsilon^{2}}\ln\frac{m}{\nu}-2$ iterations. Lemma 2 yields
the convergence rate.

For the short-step case, that is, the case where we employ Algorithm 3 as
$\mathcal{F}$, we get a similar recursion:

$\displaystyle\epsilon_{t}-\epsilon_{t+1}$
$\displaystyle\geq\tilde{f}^{\star}(-A\bm{w}_{t})-\tilde{f}^{\star}(-A\bm{w}_{t}^{(1)})$
$\displaystyle\geq\lambda_{t}(A(\bm{e}_{j_{t+1}}-\bm{w}_{t}))^{\top}\nabla\tilde{f}^{\star}(-A\bm{w}_{t})-\frac{\eta}{2}\lambda_{t}^{2}\|A(\bm{w}_{t}-\bm{e}_{j_{t+1}})\|_{\infty}^{2}$
(19)
$\displaystyle\geq\lambda(A(\bm{e}_{j_{t+1}}-\bm{w}_{t}))^{\top}\nabla\tilde{f}^{\star}(-A\bm{w}_{t})-2\eta\lambda^{2},\quad\quad\forall\lambda\in[0,1].$

Optimizing $\lambda$ in RHS and applying the inequality (17), we get
$\epsilon_{t}-\epsilon_{t+1}\geq\epsilon_{t}^{2}/8\eta$. With this inequality,
one can easily verify that the same iteration bound (18) holds for this case.
See the appendix for the rest proof. ∎

Theorem 3 shows a convergence guarantee for the _classic step_ and the _short-
step_. The line search step
$\lambda_{t}\leftarrow\arg\min_{\lambda\in[0,1]}\tilde{f}^{\star}\left(-A(\bm{w}_{t}+\lambda(\bm{e}_{j_{t+1}}-\bm{w}_{t}))\right)$
always yields better progress than the _short-step_ , so the same iteration
bound holds.

#### Other variants of the boosting scheme.

1: Let $\bm{w}_{t}=\sum_{\bm{e}\in E_{t}}\alpha_{t,\bm{e}}\bm{e}$ be the
current representation of $\bm{w}_{t}$ w.r.t. the basis vectors
$E_{t}\subset\mathcal{E}_{t}$ with positive coefficients
$\\{\alpha_{t,\bm{e}}\\}_{\bm{e}\in E_{t}}$.

2: Compute an _away_ basis $\bm{e}^{\rm Away}\in\arg\min_{\bm{e}\in
E_{t}}\bm{d}_{t}^{\top}A\bm{e}$ and set
$\lambda_{t,\max}=\alpha_{t,\bm{e}^{\rm Away}}$.

3: Compute the step size
$\lambda_{t}\leftarrow\arg\min_{\lambda\in[0,\lambda_{t,\max}]}\tilde{f}^{\star}(-A(\bm{w}_{t}+\lambda(\bm{e}_{t+1}-\bm{e}^{\rm
Away})))$.

3: $\bm{w}_{t+1}^{(1)}=\bm{w}_{t}+\lambda_{t}(\bm{e}_{j_{t+1}}-\bm{e}^{\rm
Away})$.

Algorithm 4 Pairwise rule
$\mathcal{F}(A,\bm{w}_{t},\bm{e}_{j_{t+1}},\mathcal{E}_{t},\bm{d}_{t})$

The FW update rule $\bm{w}_{t+1}^{(1)}$ of Algorithm 3 comes from the FW
algorithm with short-step sizes. One can apply other updates rules as
$\mathcal{F}$. Pairwise Frank-Wolfe (PFW) is the one of a state-of-the-art
Frank-Wolfe algorithm (Lacoste-Julien and Jaggi, 2015). The basic idea of PFW
is to move the weight from the most worthless hypothesis to the newly attained
one. Algorithm 4 is the scheme that applies the PFW. By a similar argument,
one can prove the convergence rate for Algorithm 4.

######  Corollary 1 (A convergence rate for Algorithm 4).

Let $k(t)=|\\{\tau\in[t]\mid\lambda_{\tau}<\lambda_{\tau,\max}\\}|$ be the
number of good steps by iteration $t$. Then, Algorithm 4 converges with rate
$O(\eta/k(t))$.

Note that PFW guarantees the convergence rate for a finite class
$\mathcal{H}$, while the short-step FW guarantees for all $\mathcal{H}$,
including infinite classes.

##  5 Experiments

|
---|---
Figure 1: Comparison of the algorithm for the 0-th fold of Ringnorm dataset
with parameters $\epsilon=0.01$ and $\nu=0.1m$. _Left:_ soft margin objective
value vs. computation time (seconds). _Right:_ test error vs. computation time
(seconds).

We compare LPBoost, ERLPBoost, and our scheme on Gunnar Rätsch’s benchmark
dataset 444Datasets are obtained from
http://theoval.cmp.uea.ac.uk/~gcc/matlab/default.html#benchmarks. . We use a
server with Intel Xeon Gold 6124 CPU 2.60GHz processors. We call our scheme
with secondary Algorithm 2 as MLPBoost. MLPB. (SS) and MLPB. (PFW) are
MLPBoosts with FW algorithms 3 and 4, respectively. The gradient boosting
algorithms, like XGBoost (Chen and Guestrin, 2016) or LightGBM (Ke et al.,
2017), solve different problems, so we do not compare our work to them. Note
that the FW column corresponds to C-ERLPBoost.

In order to solve the sub-problems of LPBoost, ERLPBoost, and MLPBoost, we use
the Gurobi optimizer 9.0.1 555We use the Gurobi optimizer. See
https://www.gurobi.com/. .

#### Settings.

We set the capping parameters $\nu\in N:=\\{pm\mid p=0.1,0.2,\dots,0.5\\}$ and
the tolerance parameter $\epsilon=0.01$, where $m$ is the number of training
instances. We use the weak learner that returns the best decision tree of
depth 2.

#### Computation time.

We measure the CPU time and the System time using /usr/bin/time -v command.
Some algorithms do not converge in a few days, so we abort the experiment by
timeout 20000s command. We measure the running time with capping parameters
over $N$ for each dataset and took their average. Table 2 shows the results.
The FW column is the FW algorithm with short-steps, and PFW is the Pairwise FW
algorithm. As the table shows, MLPB. (SS) and MLPB. (PFW) terminates much
faster than FW and PFW, respectively. These results indicate that LPBoost rule
$\mathcal{B}$, shown in Algorithm 2, significantly improves the objective. See
the appendix for further comparisons.

Table 2:  Comparison of the computation time (seconds). Each cell is the average computation time over the capping parameters over $N$. Some algorithm does not terminate in a few hours so we abort them within some appropriate time.  |  | Shape
---
| LPB.
---
| ERLPB.
---
| MLPB.
---
(SS only)
| MLPB.
---
(PFW only)
| MLPB.
---
(SS)
| MLPB.
---
(PFW)
Banana | $(5300,3)$ | $168.26$ | $3434.75$ | $>10^{4}$ | $>10^{4}$ | $1418.41$ | $1398.68$
B.Cancer | $(263,10)$ | $3.61$ | $73.45$ | $180.16$ | $270.50$ | $23.43$ | $19.81$
Diabetes | $(768,9)$ | $47.53$ | $1478.77$ | $>10^{4}$ | $3471.77$ | $201.46$ | $270.51$
F.Solar | $(144,10)$ | $2.30$ | $2.46$ | $13.34$ | $80.73$ | $31.64$ | $46.45$
German | $(1000,21)$ | $77.56$ | $1391.91$ | $>10^{4}$ | $5692.32$ | $181.43$ | $201.88$
Heart | $(270,14)$ | $10.03$ | $193.58$ | $>10^{3}$ | $183.09$ | $44.11$ | $24.26$
Image | $(2086,19)$ | $8.25$ | $107.52$ | $>10^{3}$ | $502.83$ | $32.01$ | $10.51$
R.norm | $(7400,21)$ | $22.09$ | $1148.16$ | $>10^{4}$ | $3350.87$ | $26.76$ | $36.73$
Splice | $(2991,61)$ | $19.35$ | $490.92$ | $>10^{4}$ | $943.98$ | $122.08$ | $37.88$
Thyroid | $(215,6)$ | $0.70$ | $0.66$ | $367.51$ | $0.35$ | $2.71$ | $0.61$
Titanic | $(24,4)$ | $0.25$ | $0.13$ | $0.58$ | $0.10$ | $1.96$ | $0.12$
Twonorm | $(7400,21)$ | $105.40$ | $13031.38$ | $>10^{4}$ | $989.54$ | $478.22$ | $397.91$
Waveform | $(5000,22)$ | $437.29$ | $9018.54$ | $>10^{4}$ | $>10^{4}$ | $2243.07$ | $1619.56$

#### The worst case for LPBoost.

Although LPBoost outperforms the running time in Table 2, it takes $m/2$
iterations for the worst case (Warmuth et al., 2007). Even in this case,
MLPBoost and ERLPBoost terminate in 2 iterations.

#### Test errors.

For each dataset in the benchmark datasets, we first split them into
train/test sets. Then, we perform the $5$-fold cross-validation over the
training set, varying the capping parameter $\nu\in N$ to find the best one.
Finally, train the algorithm using the whole training set with the best
parameter and measure the test error with the test set. Table 3 summarizes the
result. Since all the variants of MLPBoost solve the same problem, we only
show MLPB. (SS) for comparison. As the table shows, MLPBoosts achieve small
test errors for most datasets.

Table 3: Test errors for $5$-fold cross validation for the best parameters.
| LPB. | ERLPB. | MLPB. (SS)
---|---|---|---
Banana | 0.28 | 0.37 | 0.10
B.Cancer | 0.40 | 0.49 | 0.28
Diabetes | 0.26 | 0.26 | 0.24
F.Solar | 0.38 | 0.52 | 0.69
German | 0.28 | 0.35 | 0.27
Heart | 0.24 | 0.29 | 0.17
Image | 0.10 | 0.20 | 0.02
Ringnorm | 0.18 | 0.18 | 0.03
Splice | 0.11 | 0.10 | 0.05
Thyroid | 0.09 | 0.05 | 0.05
Titanic | 0.60 | 0.60 | 0.60
Twonorm | 0.03 | 0.04 | 0.03

##  6 Conclusion

We explored a relationship between the boosting algorithms for soft margin
optimization and Frank-Wolfe algorithms via Fenchel duality. Using this
unified view, we derived a scheme that can incorporate any secondary algorithm
without losing the convergence guarantee. Even though our work is the fastest
in the theoretically guaranteed boosting algorithms, LPBoost is still the
fastest. We left the problem of inventing a faster boosting algorithm with a
theoretical guarantee as future work.

## References

  * Schapire et al. [1998] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wen Sun Lee.  Boosting the margin: a new explanation for the effectiveness of voting methods.  _The Annals of Statistics_ , 26(5):1651–1686, 1998.
  * Mohri et al. [2018] Mehryar Mohri, Afshin Rostamizadeh, and Amee Talwalker.  _Foundation of Machine Learning_.  The MIT Press, second edition, 2018.
  * Demiriz et al. [2002] A Demiriz, K P Bennett, and J Shawe-Taylor.  Linear Programming Boosting via Column Generation.  _Machine Learning_ , 46(1-3):225–254, 2002.
  * Warmuth et al. [2007] M Warmuth, K Glocer, and G Rätsch.  Boosting Algorithms for Maximizing the Soft Margin.  In _Advances in Neural Information Processing Systems 20 (NIPS 2007)_ , pages 1585–1592, 2007.
  * Shalev-Shwartz and Singer [2010] Shai Shalev-Shwartz and Yoram Singer.  On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms.  _Mach. Learn._ , 80(2-3), 2010.
  * Warmuth et al. [2008] Manfred K. Warmuth, Karen A. Glocer, and S. V. N. Vishwanathan.  Entropy regularized lpboost.  In _Algorithmic Learning Theory, 19th International Conference, ALT 2008, Budapest, Hungary, October 13-16, 2008. Proceedings_ , volume 5254 of _Lecture Notes in Computer Science_ , pages 256–271. Springer, 2008.
  * Borwein and Lewis [2006] Jonathan M. Borwein and Adrian S. Lewis.  _Convex Analysis_ , pages 65–96.  Springer New York, 2006.
  * Frank and Wolfe [1956] Marguerite Frank and Philip Wolfe.  An algorithm for quadratic programming.  _Naval Research Logistics Quarterly_ , 3(1-2):95–110, 1956.
  * Jaggi [2013] Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In _Proceedings of the 30th International Conference on Machine Learning, ICML 2013_ , volume 28 of _JMLR Workshop and Conference Proceedings_ , pages 427–435. JMLR.org, 2013.
  * Wang et al. [2015] Chu Wang, Yingfei Wang, E Weinan, and Robert E. Schapire.  Functional frank-wolfe boosting for general loss functions.  _ArXiv_ , abs/1510.02558, 2015.
  * Herbster and Warmuth [2001] Mark Herbster and Manfred K. Warmuth.  Tracking the best linear predictor.  _J. Mach. Learn. Res._ , 1:281–309, sep 2001.
  * Lacoste-Julien and Jaggi [2015] Simon Lacoste-Julien and Martin Jaggi.  On the global linear convergence of frank-wolfe optimization variants.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 496–504, 2015.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, page 785–794. Association for Computing Machinery, 2016.
  * Ke et al. [2017] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu.  Lightgbm: A highly efficient gradient boosting decision tree.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 3146–3154, 2017.

##  Appendix A Technical lemmas and proofs

The following lemma shows the maximum value of the relative entropy from the
uniform distribution over the capped probability simplex
$\mathcal{P}^{m}_{\nu}$.

######  Lemma 3.

$\max_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\Delta(\bm{d})\leq\ln\frac{m}{\nu}$.

###### Proof.

Since the relative entropy from the uniform distribution achieves its maximal
value at the extreme points of $\mathcal{P}^{m}_{\nu}$, a maximizer has the
form

$\displaystyle\bm{d}=(\underbrace{1/\nu,1/\nu,\dots,1/\nu}_{k\text{
elements}},s,0,0,\dots,0),\quad s=1-\frac{k}{\nu}\leq\frac{1}{\nu}$

for some $k\in[m]$. Plugging the maximizer into $\Delta(\bm{d})$, we can write
the objective function as $\Delta(\bm{d})=(k/\nu)\ln(m/\nu)+s\ln(sm)$. If
$s=0$, $\Delta(\bm{d})=\ln(m/\nu)$ holds since $k=\nu$. If $s>0$, $k/\nu<1$ so
that

$\displaystyle\Delta(\bm{d})\leq\frac{k}{\nu}\ln\frac{m}{\nu}+\left(1-\frac{k}{\nu}\right)\ln\frac{m}{\nu}=\ln\frac{m}{\nu}.$

∎

Therefore, by setting $\eta=\frac{2}{\epsilon}\ln\frac{m}{\nu}$, the entropy
term does not exceed $\frac{\epsilon}{2}$.

The following lemma shows the dual problem of the edge minimization.

######  Lemma 4.

Let $f:\mathbb{R}^{m}\to\\{0,+\infty\\}$, $g:\mathbb{R}^{n}\to\mathbb{R}$ be
functions defined as

$\displaystyle f(\bm{d})=\begin{cases}0&\bm{d}\in\mathcal{P}^{m}_{\nu}\\\
+\infty&\bm{d}\notin\mathcal{P}^{m}_{\nu}\end{cases},\qquad\qquad\qquad
g(\bm{\theta})=\max_{j\in[n]}\theta_{j}.$

Then, the dual problem of edge minimization

$\displaystyle\min_{\bm{d}}f(\bm{d})+g(A^{\top}\bm{d})$ (20)

is the soft margin maximization

$\displaystyle\max_{\bm{w}\in\mathcal{P}^{n}}-f^{\star}(-A\bm{w}).$ (21)

Further, the strong duality holds.

###### Proof.

We can use Theorem 1 to derive the dual problem. Since

$\displaystyle\bm{g}^{\star}(\bm{w})=\begin{cases}0&\bm{w}\in\mathcal{P}^{n}\\\
+\infty&\bm{w}\notin\mathcal{P}^{n}\end{cases},$

one can verify the dual form is given as (21). To prove the strong duality, it
is enough to prove $\bm{0}\in\mathop{\rm int}\left(\mathop{\rm
dom}g-A^{\top}\mathop{\rm dom}f\right)$. By definition, $\mathop{\rm
dom}g=\mathbb{R}^{n}$ and $\mathop{\rm dom}f=\mathcal{P}^{m}_{\nu}$ and hence

$\displaystyle\mathop{\rm dom}g-A^{\top}\mathop{\rm
dom}f=\left\\{\bm{w}-A^{\top}\bm{d}\mid\bm{w}\in\mathbb{R}^{n},\bm{d}\in\mathcal{P}^{m}_{\nu}\right\\}.$

Obviously, $\bm{0}\in\mathop{\rm int}(\mathop{\rm dom}g-A^{\top}\mathop{\rm
dom}f)$ and thus the strong duality holds. ∎

Since

$\displaystyle
f^{\star}(-A\bm{w})=\sup_{\bm{d}}\left[-\bm{d}^{\top}A\bm{w}-f(\bm{d})\right]=\max_{\bm{d}\in\mathcal{P}^{m}_{\nu}}-\bm{d}^{\top}A\bm{w}=\min_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\bm{d}^{\top}A\bm{w},$

we can write the dual problem (21) explicitly:

$\displaystyle\max_{\bm{w}\in\mathcal{P}^{n}}-f^{\star}(-A\bm{w})=-\min_{\bm{w}\in\mathcal{P}^{n}}\max_{\bm{d}\in\mathcal{P}^{m}_{\nu}}\bm{d}^{\top}A\bm{w}.$

We get the dual problem for the regularized edge minimization problem by a
similar derivation.

######  Corollary 2.

Let $f,g$ be the functions defined in Lemma 4 and let
$\Delta(\bm{d})=\sum_{i=1}^{m}d_{i}\ln d_{i}+\ln(m)$ be the relative entropy
function from the uniform distribution. Define $\tilde{f}=f+(1/\eta)\Delta$
for some $\eta>0$. Then, the dual problem of

$\displaystyle\min_{\bm{d}}\tilde{f}(\bm{d})+g(A^{\top}\bm{d})\qquad\text{ is
}\qquad\max_{\bm{w}\in\mathcal{P}^{n}}-\tilde{f}^{\star}(-A\bm{w}).$

###  A.1 Proof of Lemma 1

###### Proof.

By the definition of Fenchel conjugate,

$\displaystyle\tilde{f}^{\star}(\bm{\theta})$
$\displaystyle=\sup_{\bm{d}}\left\\{\bm{d}^{\top}\bm{\theta}-\tilde{f}(\bm{d})\right\\}\geq\sup_{\bm{d}}\left\\{\bm{d}^{\top}\bm{\theta}-f(\bm{d})-c\right\\}=f^{\star}(\bm{\theta})-c,$
$\displaystyle\tilde{f}^{\star}(\bm{\theta})$
$\displaystyle=\sup_{\bm{d}}\left\\{\bm{d}^{\top}\bm{\theta}-\tilde{f}(\bm{d})\right\\}\leq\sup_{\bm{d}}\left\\{\bm{d}^{\top}\bm{\theta}-f(\bm{d})\right\\}=f^{\star}(\bm{\theta}).$

∎

By Lemma 3 and 1, we get $\tilde{f}^{\star}(-A\bm{w})-\frac{\epsilon}{2}\leq
f(-A\bm{w})\leq\tilde{f}^{\star}(-A\bm{w})$ for all $-A\bm{w}$ if
$\eta\geq\frac{2}{\epsilon}\ln\frac{m}{\nu}$.

###  A.2  Proof of Theorem 3 for the short-step FW rule 3

Recall that in the proof of Theorem 3, we showed the inequality
$\epsilon_{t}-\epsilon_{t+1}\geq\frac{1}{8\eta}\epsilon_{t}^{2}$ for the
short-step case. We prove $\epsilon_{t}\leq\frac{8\eta}{t+2}$ by induction on
$t$. For the base case, $t=1$, by Lemma 1,

$\displaystyle\epsilon_{1}=\min_{\tau\in\\{0,1\\}}(\bm{d}_{\tau}^{\top}A)_{j_{\tau+1}}+\tilde{f}^{\star}(-A\bm{w}_{1})\leq
1+f^{\star}(-A\bm{w}_{1})\leq 2\leq\frac{8\eta}{1+2}.$

For the inductive case, assume that $\epsilon_{t}\leq\frac{8\eta}{t+2}$ for
$t\geq 1$. By the inequality
$\epsilon_{t}-\epsilon_{t+1}\geq\frac{1}{8\eta}\epsilon_{t}^{2}$, we have

$\displaystyle\epsilon_{t+1}\leq\left(1-\frac{1}{8\eta}\epsilon_{t}\right)\epsilon_{t}.$
(22)

By simple calculation, one can see that the maximizer $\epsilon$ of the RHS
over $\mathbb{R}$ is $\epsilon=4\eta$. By the inductive assumption,
$\epsilon_{t}\leq\frac{8\eta}{t+2}$. Since $\frac{8\eta}{t+2}$ is the
maximizer of (22) over $[0,\frac{8\eta}{t+2}]$, we can plug this value into
(22).

$\displaystyle\epsilon_{t+1}\leq\left(1-\frac{1}{8\eta}\frac{8\eta}{t+2}\right)\frac{8\eta}{t+2}=\frac{t+1}{t+2}\frac{8\eta}{t+2}\leq\frac{8\eta}{t+3}$

Therefore, $\epsilon_{t}\leq\frac{8\eta}{t+2}$ holds for all $t\geq 1$. Thus,
we obtain the desired result.

##  Appendix B Additional experiments

This section includes experiments, not in the main paper. We first show the
comparison of boosting algorithms, LPBoost, ERLPBoost, C-ERLPBoost, and our
scheme. Since C-ERLPBoost is an instance of the short-step FW algorithm, we
call it FW. We call our scheme with secondary algorithm 2 as MLPBoost. Figure
2 shows the convergence curve. MLPB. (SS) is MLPBoost with FW algorithm 3, and
MLPB. (PFW) is MLPBoost with Pairwise FW algorithm 4. As expected, our
algorithm converges faster than ERLPBoost and is competitive with LPBoost.

|  |
---|---|---
|  |
|  |
|  |
Figure 2: Time vs. soft margin objective with parameters $\nu=0.1m$ and
$\epsilon=0.01$. Note that the time axis is log-scale. For many datasets,
MLPBoosts tend to achieve a large margin rapidly.

Further, we compare the test error decrease. Figure 3 shows the test error
curves. MLPB. (SS) achieves low test errors in most datasets.

|  |
---|---|---
|  |
|  |
|  |
Figure 3: Time vs. test errors for the 0th fold of each dataset with
parameters $\nu=0.1m$ and $\epsilon=0.01$. Note that the time axis is log-
scale. For many datasets, MLPBoost tends to decrease the test error.

Now, we compare MLPBoosts to the Frank-Wolfe algorithms, FW and PFW. Figure 4
shows the number of $\mathcal{B}$ updates. This figure shows that the
secondary update $\mathcal{B}$ yields better progress in early iterations. In
the latter half, $\mathcal{F}$ yields better progress.

|  |
---|---|---
|  |
|  |
|  |
Figure 4: The number of $\mathcal{B}$ updates for each benchmark dataset with
parameters $\nu=0.1m$ and $\epsilon=0.01$. The dotted line indicates the
linear function for comparison. Since the shape of the titanic dataset is the
same as the F. Solar dataset, we omit it.

Finally, we verify the effectiveness of the secondary update $\mathcal{B}$,
shown in algorithm 2. For comparison, we measured the soft margin objective
and time for FW, PFW, MLPB. (SS), and MLPB. (PFW). FW is the FW algorithm with
short-steps, and PFW is the Pairwise FW algorithm. MLPB. (SS) and MLPB. (PFW)
are MLPBoosts with algorithms 3 and 4, respectively. Figure 5 shows the
results. As this figure shows, the secondary update $\mathcal{B}$ improves the
objective value significantly.

|  |
---|---|---
|  |
|  |
|  |
Figure 5: Comparison of the FW algorithms and MLPBoosts. As this figure shows,
the secondary update $\mathcal{B}$ yields huge progress.


# Performance Enhancement Leveraging Mask-RCNN on Bengali Document Layout
Analysis

Shrestha Datta  Computer Science and Engineering
Shahjalal University of Science and Technology
Sylhet, Bangladesh
<EMAIL_ADDRESS>Md Adith Mollah  Computer Science and Engineering
Shahjalal University of Science and Technology
Sylhet, Bangladesh
<EMAIL_ADDRESS>Raisa Fairooz  Computer Science and Engineering
Shahjalal University of Science and Technology
Sylhet, Bangladesh
<EMAIL_ADDRESS>Tariful Islam Fahim  Computer Science and
Engineering
Shahjalal University of Science and Technology
Sylhet, Bangladesh
<EMAIL_ADDRESS>
###### Abstract

Understanding digital documents is like solving a puzzle, especially
historical ones. Document Layout Analysis (DLA) helps with this puzzle by
dividing documents into sections like paragraphs, images, and tables. This is
crucial for machines to read and understand these documents. In the DL Sprint
2.0 competition, we worked on understanding Bangla documents. We used a
dataset called BaDLAD with lots of examples. We trained a special model called
Mask R-CNN to help with this understanding. We made this model better by step-
by-step hyperparameter tuning, and we achieved a good dice score of 0.889.
However, not everything went perfectly. We tried using a model trained for
English documents, but it didn’t fit well with Bangla. This showed us that
each language has its own challenges. Our solution for the DL Sprint 2.0 is
publicly available at
https://www.kaggle.com/competitions/dlsprint2/discussion/432201 along with
notebooks, weights, and inference notebook.

###### Index Terms:

Instant Segmentation, Mask-RCNN, DLA

##  I Introduction

Deciphering the structure of intricate digital documents is a fundamental
stride in transforming them into intelligible machine-readable formats,
pivotal for practical applications. With the burgeoning advances in machine
learning and the realm of deep neural networks, the task of deciphering and
transcribing documents, especially those of historical significance, remains
an intricate conundrum. This is where Document Layout Analysis (DLA) emerges
as a beacon of understanding. DLA is a preprocessing phase of document
transcription. It segments a document into semantic units such as paragraphs,
text-boxes, images, and tables. This is essential for OCR, as it allows the
OCR engine to correctly identify and extract text from documents.

The DL Sprint 2.0 competition [2] was a challenge to develop a DLA system for
Bangla documents. The competition dataset, BaDLAD[4], contains 33,695 human-
annotated document samples from six domains.

We approached this challenge by training a Mask R-CNN model[3] for instance
segmentation. Mask R-CNN is a state-of-the-art object detection model that can
be used to segment objects in images. We fine-tuned the Mask R-CNN model on
the BaDLAD dataset, and we also used hyperparameter optimization to improve
the performance of our model.

Our final submission achieved a dice score of 0.88900. This is a competitive
result, and it shows that our approach is a promising step toward developing a
robust DLA system for Bangla documents.

In addition to our work on the Mask R-CNN model, we also experimented with
using pre-trained weights from an English document layout analysis model.
However, this did not yield a significant improvement in performance. We
believe that this is because the English document layout analysis model was
not trained on a dataset that is representative of the challenges of Bangla
document layout analysis.

##  II Methodology

###  II-A Dataset Overview

In order to improve the performance of Bengali document layout analysis, a
multi-domain large Bengali Document Layout Analysis Dataset: BaDLAD has been
used to train on the respective model. The dataset contains 3,695 human-
annotated document samples from six domains - i) books and magazines ii)
public domain govt. documents iii) liberation war documents iv) new newspapers
v) historical newspapers and vi) property deeds; with 710K polygon annotations
for four unit types: text-box, paragraph, image, and table.

###  II-B Model Overview

For instance, segmenting objects within images Mask R-CNN R 50 FPN 3x model
architecture has been used following COCO (Common Objects in Context) format.
For efficiency and effectiveness in image analysis tasks, ResNet-50 backbone
architecture is used along with Feature Pyramid Network, assisting the model
for better understanding objects at different scales within an image.
Moreover, the model is trained for three times the standard number of epochs
that are typically used during the training phase. Typically Mask R-CNN (M
R-CNN) models are trained for 10000 to 50000 iterations.

###  II-C Tuned Hyperparameters Synopsis

####  II-C1 Base Learning Rate

The base learning rate, determines the step size of gradient descent when the
model updates its parameters during model training.

####  II-C2 Pretrained Weights

The initial weights for the model to start training from. The model
architecture loads the pre-trained model weights if mentioned, instead of
untrained initialized weights.

####  II-C3 Maximum Iteration

The maximum number of training iterations. The training process will stop
after executing the specified maximum number of iterations.

####  II-C4 Gamma

A factor by which the learning rate is multiplied after each step. It Controls
the rate of learning rate decay after specified steps.

####  II-C5 Warmup Iterations

The number of warm-up iterations at the beginning of training where the
learning rate gradually increases from a lower value to the base learning rate
helps to avoid instability while training.

###  II-D Other Hyperparameters

####  II-D1 Batch Size

In the mini-batch, the gradient descent is applied based on each batch. We
have used the mini-batch method with a batch size of 8 images per batch.

####  II-D2 Workers

We have utilized 2 workers to run two batches in parallel.

###  II-E Performance Metric

In this section, we discuss the performance metric used to evaluate the
effectiveness of our method. The Dice score is a commonly used performance
metric for measuring the similarity between two sets. It is often used in
medical image segmentation tasks to quantify the agreement between the
predicted and ground truth segmentations.

The Dice score (also known as the F1 score or the Sørensen-Dice coefficient)
is defined as follows:

$\text{Dice Score}=\frac{2\times\text{Intersection}}{\text{Total
Predicted}+\text{Total Ground Truth}}$ (1)

Where:

Intersection $\displaystyle=\text{Number of overlapping pixels in}$ predicted
and ground truth segmentations Total Predicted $\displaystyle=\text{Total
number of pixels}$ in predicted segmentation Total Ground Truth
$\displaystyle=\text{Total number of pixels}$ in ground truth segmentation

The Dice score ranges from 0 to 1, with 1 indicating perfect overlap between
the predicted and ground truth segmentations, and 0 indicating no overlap.

Dice score provides a meaningful measure of segmentation accuracy, allowing us
to assess the quality of our method’s predictions. Although dice score is a
good measure for instance segmentation tasks of computer vision but it still
has limitations in certain situations.

###  II-F Final Sequential Submission Approach

Sub. | Pretrained Weight | Tr. Split | B. LR | Warmup Iter.
---|---|---|---|---
1 | None | 75% | 0.007 | 100
2 | Output from sub. 1 | 75% | 0.001 | 100
3 | Output from sub. 2 | 75% | 0.0005 | 0
4 | Output from sub. 3 | 75% | 0.00001 | 0
5 | Output from sub. 4 | 75% | 0.000001 | 0
6 | Output from sub. 5 | 99% | 0.000001 | 0
TABLE I: Training Configuration Part 1: Showing training hyperparameters pre-trained weights, train dataset percentage in train-test split(Tr. Split), Base learning Rate(B. LR), and initial warmup iterations(Warmup Iter.) for each submission Sequence(sub.) Sub. | No. of Iter. | Gamma | Dice Score
---|---|---|---
1 | 22k | 0.0001 | 0.88223
2 | 22k | 0.0001 | 0.88783
3 | 22k | 0.0001 | 0.88842
4 | 22k | 0.00001 | 0.8887
5 | 22k | 0.00001 | 0.88894
6 | 5k | 0.00001 | 0.88900
TABLE II: Training Configuration Part 2: Showing training hyperparameters
number of iterations(No. of Iter.) and gamma for each submission
Sequence(sub.) and corresponding dice score in percentage(Accuracy)

Our final submission sequence is decomposed into 6 steps, each of which has
been tinkered with different hyperparameter values in order to improve the
performance of the respective model on the provided dataset.

In terms of the first submission of the final submission sequence, no pre-
trained base model is injected for pre-trained weights. Rather, training
commenced from scratch by considering a training split of 75%, a base learning
rate of 0.007, a warmup iteration value of 100, a gamma value of .0001, and a
maximum iteration of 22000 eventually providing dice score of 0.88223.

Starting from the second submission sequence till the final one, a cumulative
approach has been taken in terms of using pre-trained weights. In the case of
the second submission, the first submission’s pre-trained model weight is
injected along with one particular change for the base learning rate having
the value of 0.001 and keeping every parameter the same as the previous one
providing a dice score of 0.88783, huge improvements over the former one.

The warmup iterations value has been considered from 100 to 0 from the 3rd
submission sequence. For the 3rd, 4th and 5th sequence of submissions, a
similar cumulative approach has been applied for adding pre-trained weights of
previous submissions to continue its training in the current submissions with
updated hyperparameters. Only the learning rate has been different in these
submissions eventually providing a dice score of 0.88894.

Finally, in the last submission, a total of 110,000 iteration version of the
model weights has been considered to continue training with a maximum
iteration value of 5000 more iterations, train split of 99% and learning rate
of 0.000001. So the final version of the submission is the result of the model
being iterated over 115,000 times eventually providing the best dice score for
our latest submission, which is 0.88900.

##  III Results and Analysis

In this section, we will discuss and analyze our results with respect to the
hyperparameters tuned at each step of the training. We tested our model on the
test data provided by DL sprint 2.0 based on the dice score from the equation
(1). The results for each submission are given in the table II.

At the first step of our training, we tried training a model from scratch on
the DL Sprint 2.0 dataset and training a Mask-RCNN model pre-trained on the
PubLayNet dataset [1]. Although using the pre-trained model gave a better
score for the first 10,000 iterations it did not yield any better results on
further training even a total of 22, 000 iterations compared to the trained
model from scratch. The trained model from scratch for 22k iterations obtains
a score of 0.88223 which we selected as our model for further training.

For the second step, as the model showed a high variation of performance at
each iteration as we continued to increase our training iterations, so we
decreased the initial learning rate to 0.001. Thus training for a further
22,000 iterations yielded a score of 0.88783.

Continuing to our third step, as we continued training the model further on
small learning rates the model continued to show slight improvement of score
compared to larger similar learning rates of previous steps. So, we tried to
keep the learning rate smaller at 0.0005 in this step. As larger learning
rates showed variation in scores, we changed the number of warmup steps to 0,
so that the learning rate does not increase with iterations initially. In this
way, after training for further 22,000 iterations, we got a score of 0.88842.

For the fourth and fifth steps, we continued to observe the same behavior of
the learning rate causing us to decrease it further to 0.00001 for the fourth
step and 0.000001 for the fifth step. As the learning rate is becoming too low
and the model is showing stable improvements on further training, to keep the
learning rate stable we decreased the gamma to 10 times making it 0.00001 for
both steps. We continued training our model for 22,000 iterations on the
fourth step and further for 22,000 iterations on the fifth step resulting in a
score of 0.8887 and 0.88894 respectively.

In the sixth step of our continuation of training, we noticed a stable
improvement in model performance just by increasing the training data making
the training data to validation data ratio of 99:1 compared to the previous
75% of our training data. With this hyperparameter change and continuing our
training for 5,000 iterations lead our model to improve to a score of 0.889.

In total, we trained our model for 115k iterations with varying
hyperparameters at each step reaching a model performance dice score of 0.889.
We can see that the model training shows a gradual increase in performance
with increasing iterations and selecting proper hyperparameters after specific
iterations as depicted in the table II. We can also see that increasing
training data after some iteration increases the model performance.

##  IV Conclusion

In this paper, we presented our approach to the DL Sprint 2.0 competition. We
trained a Mask R-CNN model for instance segmentation on the BaDLAD dataset,
and we also used hyperparameter optimization to improve the performance of our
model. Our final submission achieved a dice score of 0.889.

We believe that our approach is a promising step towards developing a robust
DLA system for Bangla documents. However, there is still more work to be done.
In the future, we plan to improve our approach by enhancing the dataset and by
incorporating more advanced techniques.

We hope that our work has the potential to add value to the field of document
layout analysis. DLA is a key technology for many applications, such as OCR,
machine translation, and search. By developing better DLA systems for Bangla
documents, we can make these applications more accessible to the millions of
people who speak Bangla.

We have observed that using proper hyperparameters can improve the model’s
performance with further training. Also increasing the dataset also increases
the performance of the model.

## References

  * [1] CaseDrive.  publaynet-models.  https://github.com/CaseDrive/publaynet-models, 2022.
  * [2] Md Asif Haider, Salman Khondker, Sameen53, Sushmit, and Tahsin.  Dl sprint 2.0 - buet cse fest 2023, 2023.  https://kaggle.com/competitions/dlsprint2.
  * [3] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 2980–2988, 2017.
  * [4] Md. Istiak Hossain Shihab, Md. Rakibul Hasan, Mahfuzur Rahman Emon, Syed Mobassir Hossen, Md. Nazmuddoha Ansary, Intesur Ahmed, Fazle Rabbi Rakib, Shahriar Elahi Dhruvo, Souhardya Saha Dip, Akib Hasan Pavel, Marsia Haque Meghla, Md. Rezwanul Haque, Sayma Sultana Chowdhury, Farig Sadeque, Tahsin Reasat, Ahmed Imtiaz Humayun, and Asif Shahriyar Sushmit.  Badlad: A large multi-domain bengali document layout analysis dataset, 2023.


# Numerical study of RF power coupling in fusion-relevant single- and multi-
driver H- ion sources

D. Zielke,11footnotetext: Corresponding author. S. Briefi  U. Fantz

###### Abstract

ITER’s large and powerful neutral beam injection system is based on an ion
source utilizing a modular concept, where eight cylindrical drivers are
attached to one common expansion and extraction region. In each driver, a
plasma is sustained via inductive coupling with powers of up to 100 kW at a
driving radio frequency (RF) of 1 MHz to produce fusion-relevant hydrogen
beams. These high powers impose great stress on the electric system. Recent
measurements at the single-driver test bed BATMAN Upgrade showed that the RF
power transfer efficiency $\eta$, which measures the ratio of power absorbed
by plasma to total RF power, is only around 0.5, leaving room for
optimization. In multi-driver test beds such as ELISE with four drivers $\eta$
is found to be even further decreased to around 0.4. To explain this
difference, a previously validated self-consistent 2D RF power coupling fluid
model is applied. For the same absorbed power per driver, the model shows
virtually the same spatial distributions of plasma parameters and power
absorption in single- and multi-driver sources. However, the coil current is
slightly increased in the multi-driver model due to a changed spatial
distribution of the magnetic RF field in the region surrounding the drivers.
Typically, in multi-driver sources conductive shields are applied to cancel
the electromagnetic interference between individual drivers. These shields are
found to affect the spatial distribution of the RF fields more severely, the
effect being highly dependent on the distance between the RF coil and the
shield. In the case of the ELISE ion source a further decrease of $\eta$ is
calculated by the model being in good agreement with experimental
measurements.

##  1 Introduction

Neutral beam injection (NBI) systems as envisaged for the ITER experiment [1]
produce large and powerful hydrogen or deuterium beams, which are injected
into a magnetically confined high temperature plasma to heat it to fusion-
relevant temperatures [6]. For this purpose, a modular ion source concept is
foreseen, where multiple cylindrical drivers are attached to one rectangular
expansion and extraction region [3]. Figure 1 shows the size scaling from the
single-driver prototype ion source at the BATMAN Upgrade (BUG) test bed
towards the multi-driver test beds ELISE with four drivers, and the full size
ITER ion source at the SPIDER test bed with eight drivers [3].

Figure 1: Size scaling of the modular radio frequency ion source concept: one
driver at the BUG test bed (left), four drivers at the ELISE test bed
(middle), and the full size ITER ion source at the SPIDER test bed with eight
drivers (right). Figure based on Heinemann et al. [3].

RF coils with six to eight windings are wrapped around each driver and
connected to RF generators via capacitive matching networks and transmission
lines. At the BUG and ELISE test beds, matching transformers are used to
separate the RF generators which are on ground potential from the ion sources,
which are on a high negative potential of up to $-60\,\mathrm{kV}$. At the
SPIDER and other ITER sources both the RF generators as well as the ion
sources are on a high negative potential, wherefore no matching transformer is
necessary. In the multi-driver test beds each two horizontal drivers are
connected in series and supplied by one common RF power generator operating at
a radio frequency (RF) of 1 MHz. As shown in figure 1, one striking difference
between the single- and multi-driver sources (besides that the BUG test bed is
in air and all others are in vacuum vessels) is that in the latter case
cylindrical conductive electromagnetic shields (EMS) are introduced around
each RF coil. This was done to suppress the electrostatic and electromagnetic
coupling between the drivers [2].

In these ion sources negative hydrogen ions are produced mainly on the surface
of a cesiated plasma facing grid in the expansion by conversion of impinging
atoms and positive ions. Hence it is mandatory to sustain a hot and dense
plasma in the drivers, where typical plasma densities and electron
temperatures are around $10^{18}\,\mathrm{m}^{-3}$ and 10 eV, respectively and
the hydrogen atomic to molecular ratio is around 0.5. Up to 100 kW of RF power
per driver has to be delivered by the RF generators to achieve the ITER
performance [6]. These high powers entail high currents and voltages in the RF
coils and matching networks, rendering the system prone to RF breakdowns and
failures. It has been determined experimentally at the prototype RF ion source
of the BUG test bed that the fraction of generator power which is absorbed by
the driver plasma does not exceed 0.6 in a single-driver ion source [7]. The
considerable loss power was found to be distributed between Joule heating
losses in the skin of the RF coil (25%) and eddy current losses in the
internal Faraday shield (75%). The latter has to be present in RF ion sources
to protect the dielectric cylindrical wall material from plasma sputtering and
the plasma from impurities [12].

To optimize the RF power coupling a numerical fluid-electromagnetic model was
developed and benchmarked successfully [9]. The model calculates the RF fields
and the macroscopic plasma quantities self-consistently in the operating
regime of RF ion sources, i.e. at large power densities in the order of 10
Wcm-3, low RF of 1 MHz and at the ITER required low gas pressure of 0.3 Pa.
Among the various investigated external parameters, increasing the axial
driver length (from 17 cm to 30 cm) and driving frequency (from 1 MHz to 2
MHz) were identified to yield promising improvements for the RF power
coupling, wherefore less losses in the Faraday shield and RF coil are to be
expected [11].

When compared to single-driver ion sources, the fraction of absorbed power in
multi-driver ion sources is even further decreased. This has been
experimentally observed at the ELISE test bed, where the fraction of absorbed
power ranges around 0.4 ($<0.6$ for the single-driver sources) under typical
operating conditions. Similar values were found by Jain et al. [10] at the
SPIDER test bed. This raises the questions why less RF power per driver is
coupled to a multi-driver plasma, when compared to a single-driver plasma and
how this could be optimized. To answer this questions the self-consistent
fluid-electromagnetic model is applied in both cases. The model is described
in section 2 and the calculated distributions of relevant quantities such as
plasma density and electromagnetic fields are discussed in section 3. A
conclusion as drawn from the model results is given in section 4.

##  2 Model

To represent multi-driver setups, the cylindrical symmetry as assumed in our
previous work [9] is not appropriate, wherefore the equations and the modeling
domains used in this work are in 2D cartesian coordinates, as shown in figure
2.

Figure 2: Simulation domains corresponding to a horizontal cut for the single-
driver (left) and multi-driver (right). The latter has electromagnetic shields
surrounding each RF coil.

It has been verified that the spatial plasma parameter profiles do not change
significantly when using cartesian instead of cylindrical coordinates. The two
different simulation domains represent horizontal cuts of the single- and
multi-driver setups. Further improvements regarding the description of the RF
power coupling are that the model in this work is fully time dependent, i.e.
no time harmonic approximation is used, neither in the electron momentum
balance, where also the viscous stress tensor and the Lorentz force are
retained, nor in Maxwell’s equations. This comes with the drawback, that the
time steps during the solving process become very small (0.001 of the RF
period, i.e. in the order of 1 ns). For this reason the neutral molecules and
atoms (which have a time-scale of around 0.1 s) have to be described as a
uniform background. The effect of neutral depletion is nevertheless accounted
for by using the appropriate input values of $n_{\mathrm{H}_{2}}=3\cdot
10^{19}\,\mathrm{m}^{-3}$ and $n_{\mathrm{H}}=1.5\cdot
10^{19}\,\mathrm{m}^{-3}$, as calculated for a filling gas pressure of 0.3 Pa
from a version of the model, where the neutrals are treated as fluids [9]. All
other equations and boundary conditions are as described in our previous work
[9], with the one further exception, that also the impact of the RF magnetic
field on the electron heat flux is considered in this work, as described
elsewhere [8]. The grey shaded surfaces in figure 2 represent perfect
conductors, such as the driver and source backplates, as well as the
electromagnetic shields. Here the electric component of the RF field is set to
zero, i.e. $E_{z}=0$. The relation between the calculated RF coil current
amplitude $I_{\mathrm{coil}}$, which is applied at each of the six coil
windings (depicted as small circles left and right of each driver) and the
tangential component of the magnetic RF field $B_{\mathrm{RF,tan}}$ is

$I_{\mathrm{coil}}=\frac{1}{\mu_{0}}\oint_{\mathrm{L}}B_{\mathrm{RF,tan}}\mathrm{d}L,$
(2.1)

where the integral is along the circumference of each coil winding. The system
is excited by an integral controller which ramps up $I_{\mathrm{coil}}$ to
ensure that the absorbed power by the plasma is as specified by the user. This
steady state is typically reached after approximately 70 RF cycles. The RF
power transfer efficiency $\eta$, as the quantity which should be optimized,
calculates the ratio of power absorbed by the plasma $P_{\mathrm{plasma}}$ and
total delivered generator power $P_{\mathrm{RF}}$,

$\eta=\frac{P_{\mathrm{plasma}}}{P_{\mathrm{RF}}}=\frac{P_{\mathrm{plasma}}}{P_{\mathrm{plasma}}+\frac{1}{2}R_{\mathrm{net}}I_{\mathrm{coil}}^{2}}.$
(2.2)

Herein it is convenient to express the losses in the RF network as a product
of a network resistance $R_{\mathrm{net}}$ and the square of the RF coil
current $I_{\mathrm{coil}}$. The network resistance is not in the focus of
this study, wherefore it is a model input. Its value of
$R_{\mathrm{net,SD}}=0.6\,\Omega$ has been determined experimentally for the
single-driver ion source at the BUG test bed [7]. To keep things as simple as
possible the driver diameters in the multi-driver model are kept the same as
in the single-driver (see figure 2) and the network resistance is simply
doubled, i.e. $R_{\mathrm{net,MD}}=1.2\,\Omega$ is used. Note that the
experimentally obtained value for the upper two drivers at ELISE is
$1.28\,\Omega$ and thus slightly larger. The deviation is most likely caused
by eddy current losses in the electromagnetic shields and the fact that the
drivers in ELISE are slightly larger in the experimental setup (driver inner
diameter of 27.6 cm instead of 23.7 cm). This entails a larger Faraday shield
surface, where eddy currents are driven and a longer RF coil.

##  3 Results

###  3.1 Single- and multi-driver setup without electromagnetic shields

Figure 3 shows a comparison of the spatial profile of the electron density in
the single- and multi-driver setup, averaged over one RF period in steady
state, when 25 kW of power are absorbed in each driver plasma. In this first
comparison, no electromagnetic shields are used in the multi-driver setup.

Figure 3: Comparison of calculated electron density profiles in a single- and
multi-driver setup (without electromagnetic shields around the RF coils) for
an absorbed power of 25 kW by the plasma in each driver.

The shape shows the typical depletion of electrons near the RF coil (see dark
blue regions), where the RF Lorentz force tends to push the plasma away from
the RF coils. Power absorption profiles (not shown) and plasma parameter
profiles are virtually the same in each driver of both setups. Using in the
multi-driver case the doubled plasma power and network resistance in equation
(2.2) it can be shown that for $\eta$ to remain unchanged, it is necessary
that also $I_{\mathrm{coil}}$ does not change. However, the model shows that
this is not the case, i.e. the respective RF coil currents to produce these
plasmas are $I_{\mathrm{coil,SD}}=263\,$A for the single-driver and
$I_{\mathrm{coil,MD}}=284\,$A for the multi-driver setup.

Figure 4: Comparison of the $y$-component of the RF magnetic field $B_{y}$ at
a phase of $\pi/2$ along the lines as depicted in figure 3.

Hence the coil current is increased by around 8%. As a result,
$\eta_{\mathrm{SD}}=55\%>\eta_{\mathrm{MD}}=50\%$. The reason for the lower
$\eta_{\mathrm{MD}}$ is electromagnetic mutual coupling between the two
drivers. This can be seen exemplarily in figure 4, where the $y$-components of
the magnetic RF fields (at a phase $\phi=\pi/2$) along the lines as depicted
in figure 3 are compared. For better comparability, the field from the single-
driver setup has been shifted onto the left driver of the multi-driver setup.
As can be seen, $B_{y}$ (representative for $B_{\mathrm{RF,tan}}$) at the
positions of the coils is larger in the case of the multi-driver setup.
According to equation (2.1) this results in a larger $I_{\mathrm{coil}}$ and
consequently a lower $\eta$.

###  3.2 Effect of electromagnetic shields

To avoid mutual coupling between individual drivers in multi-driver setups
conductive cylindrical electromagnetic shields (EMS) are wrapped around each
coil and attached to the grounded source backplates [2], as shown in figure 1.
To investigate how the RF power coupling is affected by the EMS, the
simulation domain including the EMS is used, as shown in figure 2, right. As a
boundary condition at the conducting electromagnetic shield, $E_{z}=0$ is
used. Figure 5 shows the resulting distribution of the RF magnetic field
amplitude, illustrated for an exemplary distance of 1 cm between RF coil and
EMS.

Figure 5: Distributions of the magnetic RF field for the case without EMS
(left) and with EMS (right). A close distance of 1 cm is used to emphasize the
shielding effect.

The white arrows represent the direction and relative strength of the RF
magnetic field amplitude. On the left, no EMS is present, wherefore the
magnetic RF field amplitude around each RF coil winding is uniform and
comparatively low. In contrast to that, on the right, the distribution is
highly anisotropic. Consequently the current that has to be applied at the RF
coil windings to reach the same absorbed plasma power is larger in this case.

For a distance of 4 cm, as in the ELISE ion source, the model calculates an RF
power transfer efficiency of 0.46. This is larger than the experimentally
obtained value, which is $0.3\pm 0.1$ without applying a magnetic filter
field. Note that the latter is typically applied in the expansion to decrease
the electron temperature and density, which helps to reduce the number of co-
extracted electrons as well as the destruction processes of negative hydrogen
ions [4]. The overestimation of $\eta$ by the model could be caused by 3D
effects, as e.g. conductive support structure to hold the EMS, which decreases
the effective distance, as shown in figure 1. The distance $d$ between the RF
coil and the EMS is a crucial parameter. Thus the single-driver setup is used
to quantify the impact of $d$ on the RF power transfer efficiency isolated
from any other effects encountered in multi-driver sources. The resulting
behavior is shown in figure 6.

Figure 6: RF power transfer efficiency $\eta$ as a function of the distance
between RF coil and EMS in a single-driver setup.

As the solid black line shows, for large distances $\eta$ approaches the value
of a setup, where no EMS is present, i.e. around 0.55. However, when the
distance is decreased $\eta$ decreases non-linearly to around 0.2 at 1 cm. In
this extreme case, a generator output power of 125 kW per driver would be
necessary to sustain a plasma with an absorbed power of 25 kW. The black
square represents the multi-driver model of the ELISE ion source with
$d=4\,$cm. Note that it almost perfectly fits onto the curve. This justifies
using a model with a single driver to investigate the distance effect and also
shows that this is the main effect, which affects the RF power coupling. As
another example the SPIDER ion source, where the distance equals 2.5 cm is
also plotted onto the curve as a grey square. In the two cases RF generator
powers of 54 kW and 61 kW per driver are required, respectively.

In order to assess the optimization possibilities for the RF power coupling,
two measures as proposed in an earlier work [11] are applied in the multi-
driver model with EMS. The two resulting curves show that both measures, i.e.
applying 2 MHz and increasing the axial driver length from 17 cm to 30 cm are
beneficial. For the case of ELISE, where $d=4\,$cm, $\eta$ could be increased
to around 0.57 and 0.68, respectively. Furthermore, when both measures are
combined at the same time, the model predicts that an RF power transfer
efficiency of 0.74 is reachable. Nevertheless, the negative effect of the EMS
on the RF power transfer efficiency is persistent, as the model predicts
values of up to 0.9 without them [11].

##  4 Conclusion

A state-of-the-art 2D fluid-electromagnetic model has been further developed
and applied to self-consistently describe the power coupling in fusion-
relevant single- and multi-driver RF ion sources. At the same absorbed plasma
power per driver, the numerically calculated plasma parameters in single- and
multi-driver setups coincide. However, a slightly decreased RF power transfer
efficiency is found in multi-driver setups, even without electromagnetic
shields present. The cause for this decrease is mutual electromagnetic
coupling, i.e. the presence of a second driver in close vicinity of the first
one changes the distribution of the magnetic RF field. Moreover, the
electromagnetic shields present in multi-driver RF ion sources are identified
to considerably lower the RF power transfer efficiency. This is caused by a
drastic change of the magnetic RF field distribution, which is more nonuniform
around the individual coil windings when an electromagnetic shield is present.
The nonuniform distribution leads to a larger RF coil current and consequently
a lower RF power transfer efficiency. The decrease in RF power transfer
efficiency is found to be highly nonlinear with decreasing distance between
the coil and electromagnetic shield. Measures to increase the power transfer
to the plasma as already found in previous works could be applied in multi-
driver ion sources as well. By enlarging the axial driver length from 17 cm to
30 cm and increasing the driving frequency from 1 MHz to 2 MHz at the ELISE
ion source the model predicts an increase of the RF power transfer efficiency
from 0.46 to 0.74.

## Acknowledgments

This work has been carried out within the framework of the EUROfusion
Consortium and has received funding from the Euratom research and training
programme 2014-2018 and 2019-2020 under grant agreement No 633053. The views
and opinions expressed herein do not necessarily reflect those of the European
Commission.

This work has been carried out within the framework of the EUROfusion
Consortium, funded by the European Union via the Euratom Research and Training
Programme (Grant Agreement No 101052200 — EUROfusion). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Commission. Neither the
European Union nor the European Commission can be held responsible for them.

## References

  * [1] _www.iter.org_
  * [2] W. Kraus et al.  _Re. Sci. Instrum._ 83, 2 (2012) 02B104
  * [3] B. Heinemann et al.  _New J. Phys._ 19, 1 (2017) 015001
  * [4] U. Fantz et al.  _Plasma Sources Sci. Technol._ 23, 4 (2014) 044002
  * [5] U. Fantz et al.  _Nucl. Fusion_ 57, 11 (2017) 116007
  * [6] R. Hemsworth et al.  _New J. Phys._ 19, 2 (2017) 025005
  * [7] D. Zielke et al.  _J. Phys. D_ 54, 15 (155202) 155202
  * [8] D. Zielke et al.  _Plasma Sources Sci. Technol._ 30, 6 (2021) 065011
  * [9] D. Zielke et al.  _Plasma Sources Sci. Technol._ 31, 3 (2022) 035019
  * [10] P. Jain et al.  _Plasma Phys. Control. Fusion_ 64, 9 (2022) 095018
  * [11] D. Zielke et al.  _submitted to Nucl. Fusion_ (2022)
  * [12] W. Kraus et al.  _Fusion Eng. Des._ 56-57 (2001) 499-503