# An Exact Solver for the Weston-Watkins SVM Subproblem

Yutong Wang  Clayton Scott

# Supplementary materials for
An Exact Solver for the Weston-Watkins SVM Subproblem

Yutong Wang  Clayton Scott

###### Abstract

Recent empirical evidence suggests that the Weston-Watkins support vector
machine is among the best performing multiclass extensions of the binary SVM.
Current state-of-the-art solvers repeatedly solve a particular subproblem
approximately using an iterative strategy. In this work, we propose an
algorithm that solves the subproblem exactly using a novel reparametrization
of the Weston-Watkins dual problem. For linear WW-SVMs, our solver shows
significant speed-up over the state-of-the-art solver when the number of
classes is large. Our exact subproblem solver also allows us to prove linear
convergence of the overall solver.

Machine Learning, ICML

##  1 Introduction

Support vector machines (SVMs) (Boser et al., 1992; Cortes & Vapnik, 1995) are
a powerful class of algorithms for classification. In the large scale studies
by Fernández-Delgado et al. (2014) and by Klambauer et al. (2017), SVMs are
shown to be among the best performing classifers.

The original formulation of the SVM handles only binary classification.
Subsequently, several variants of multiclass SVMs have been proposed (Lee et
al., 2004; Crammer & Singer, 2001; Weston & Watkins, 1999). However, as
pointed out by Doǧan et al. (2016), no variant has been considered canonical.

The empirical study of Doǧan et al. (2016) compared nine prominent variants of
multiclass SVMs and demonstrated that the Weston-Watkins (WW) and Crammer-
Singer (CS) SVMs performed the best with the WW-SVM holding a slight edge in
terms of both efficiency and accuracy. This work focuses on the computational
issues of solving the WW-SVM optimization efficiently.

SVMs are typically formulated as quadratic programs. State-of-the-art solvers
such as LIBSVM (Chang & Lin, 2011) and LIBLINEAR (Fan et al., 2008) apply
block coordinate descent to the associated dual problem, which entails
repeatedly solving many small subproblems. For the binary case, these
subproblems are easy to solve exactly.

The situation in the multiclass case is more complex, where the form of the
subproblem depends on the variant of the multiclass SVM. For the CS-SVM, the
subproblem can be solved exactly in $O(k\log k)$ time where $k$ is the number
of classes (Crammer & Singer, 2001; Duchi et al., 2008; Blondel et al., 2014;
Condat, 2016). However, for the WW-SVM, only iterative algorithms that
approximate the subproblem minimizer have been proposed, and these lack
runtime guarantees (Keerthi et al., 2008; Igel et al., 2008).

In this work, we propose an algorithm called _Walrus_ 111WW-subproblem
analytic log-linear runtime solver that finds the exact solution of the
Weston-Watkins subproblem in $O(k\log k)$ time. We implement Walrus in C++
inside the LIBLINEAR framework, yielding a new solver for the _linear_ WW-SVM.
For datasets with large number of classes, we demonstrate significant speed-up
over the state-of-the-art linear solver Shark (Igel et al., 2008). We also
rigorously prove the linear convergence of block coordinate descent for
solving the dual problem of linear WW-SVM, confirming an assertion of Keerthi
et al. (2008).

###  1.1 Related works

Existing literature on solving the optimization from SVMs largely fall into
two categories: linear and kernel SVM solvers. The seminal work of Platt
(1998) introduced the sequential minimal optimization (SMO) for solving kernel
SVMs. Subsequently, many SMO-type algorithms were introduced which achieve
faster convergence with theoretical guarantees (Keerthi et al., 2001; Fan et
al., 2005; Steinwart et al., 2011; Torres-Barrán et al., 2021).

SMO can be thought of as a form of _(block) coordinate descent_ where where
the dual problem of the SVM optimization is decomposed into small subproblems.
As such, SMO-type algorithms are also referred to as _decomposition methods_.
For binary SVMs, the smallest subproblems are $1$-dimensional and thus easy to
solve exactly. However, for multiclass SVMs with $k$ classes, the smallest
subproblems are $k$-dimensional. Obtaining exact solutions for the subproblems
is nontrivial.

Many works have studied the convergence properties of decomposition focusing
on asymptotics (List & Simon, 2004), rates (Chen et al., 2006; List & Simon,
2009), binary SVM without offsets (Steinwart et al., 2011), and multiclass
SVMs (Hsu & Lin, 2002). Another line of research focuses on primal convergence
instead of the dual (Hush et al., 2006; List & Simon, 2007; List et al., 2007;
Beck et al., 2018).

Although kernel SVMs include linear SVMs as a special case, solvers
specialized for linear SVMs can scale to larger data sets. Thus, linear SVM
solvers are often developed separately. Hsieh et al. (2008) proposed using
coordinate descent (CD) to solve the linear SVM dual problem and established
linear convergence. Analogously, Keerthi et al. (2008) proposed block
coordinate descent (BCD) for multiclass SVMs. Coordinate descent on the dual
problem is now used by the current state-of-the-art linear SVM solvers
LIBLINEAR (Fan et al., 2008), liquidSVM (Steinwart & Thomann, 2017), and Shark
(Igel et al., 2008).

There are other approaches to solving linear SVMs, e.g., using the cutting
plane method (Joachims, 2006), and stochastic subgradient descent on the
primal optimization (Shalev-Shwartz et al., 2011). However, these approaches
do not converge as fast as CD on the dual problem (Hsieh et al., 2008).

For the CS-SVM introduced by Crammer & Singer (2001), an exact solver for the
subproblem is well-known and there is a line of research on improving the
solver’s efficiency (Crammer & Singer, 2001; Duchi et al., 2008; Blondel et
al., 2014; Condat, 2016). For solving the kernel CS-SVM dual problem,
convergence of an SMO-type algorithm was proven in (Lin, 2002). For solving
the linear CS-SVM dual problem, linear convergence of coordinate descent was
proven by Lee & Chang (2019). Linear CS-SVMs with $\ell_{1}$-regularizer have
been studied by Babichev et al. (2019)

The Weston-Watkins SVM was introduced by Bredensteiner & Bennett (1999);
Weston & Watkins (1999); Vapnik (1998). Empirical results from Doǧan et al.
(2016) suggest that the WW-SVM is the best performing multiclass SVMs among
nine prominent variants. The WW-SVM loss function has also been successfully
used in natural language processing by Schick & Schütze (2020).

Hsu & Lin (2002) gave an SMO-type algorithm for solving the WW-SVM, although
without convergence guarantees. Keerthi et al. (2008) proposed using
coordinate descent on the linear WW-SVM dual problem with an iterative
subproblem solver. Furthermore, they asserted that the algorithm converges
linearly, although no proof was given. The software Shark (Igel et al., 2008)
features a solver for the linear WW-SVM where the subproblem is approximately
minimized by a greedy coordinate descent-type algorithm. MSVMpack (Didiot &
Lauer, 2015) is a solver for multiclass SVMs which uses the Frank-Wolfe
algorithm. The experiments of (van den Burg & Groenen, 2016) showed that
MSVMpack did not scale to larger number of classes for the WW-SVM. To our
knowledge, an exact solver for the subproblem has not previously been
developed.

###  1.2 Notations

Let $n$ be a positive integer. Define $[n]:=\\{1,\dots,n\\}$. All vectors are
assumed to be column vectors unless stated otherwise. If $v\in\mathbb{R}^{n}$
is a vector and $i\in[n]$, we use the notation $[v]_{i}$ to denote the $i$-th
component of $v$. Let $\mathbb{1}_{n}$ and $\mathbb{0}_{n}\in\mathbb{R}^{n}$
denote the vectors of all ones and zeros, respectively. When the dimension $n$
can be inferred from the context, we drop the subscript and simply write
$\mathbb{1}$ and $\mathbb{0}$.

Let $m$ be a positive integer. Matrices $\mathbf{w}\in\mathbb{R}^{m\times n}$
are denoted by boldface font. The $(j,i)$-th entry of $\mathbf{w}$ is denoted
by $w_{ji}$. The columns of $\mathbf{w}$ are denoted by the same symbol
$w_{1},\dots,w_{n}$ using regular font with a single subscript, i.e.,
$[w_{i}]_{j}=w_{ji}$. A column of $\mathbf{w}$ is sometimes referred to as a
_block_. We will also use boldface Greek letter to denote matrices, e.g.,
$\bm{\alpha}\in\mathbb{R}^{m\times n}$ with columns
$\alpha_{1},\dots,\alpha_{n}$.

The 2-norm of a vector $v$ is denoted by $\|v\|$. The Frobenius norm of a
matrix $\mathbf{w}$ is denoted by $\|\mathbf{w}\|_{F}$. The $m\times m$
identity and all-ones matrices are denoted by $\mathbf{I}_{m}$ and
$\mathbf{O}_{m}$, respectively. When $m$ is clear from the context, we drop
the subscript and simply write $\mathbf{I}$ and $\mathbf{O}$.

For referencing, section numbers from our supplementary materials will be
prefixed with an “A”, e.g., Section A.5.

##  2 Weston-Watkins linear SVM

Throughout this work, let $k\geq 2$ be an integer denoting the number of
classes. Let $\\{(x_{i},y_{i})\\}_{i\in[n]}$ be a training dataset of size $n$
where the instances $x_{i}\in\mathbb{R}^{d}$ and labels $y_{i}\in[k]$. The
Weston-Watkins linear SVM 222 Similar to other works on multiclass linear SVMs
(Hsu & Lin, 2002; Keerthi et al., 2008), the formulation P does not use
_offsets_. For discussions, see Section A.1.  solves the optimization

$\min_{\mathbf{w}\in\mathbb{R}^{d\times
k}}\frac{1}{2}\|\mathbf{w}\|_{F}^{2}+C\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in[k]:\\\
j\neq
y_{i}\end{subarray}}\mathtt{hinge}(w_{y_{i}}^{\prime}x_{i}-w_{j}^{\prime}x_{i})$
(P)

where $\mathtt{hinge}(t)=\max\\{0,1-t\\}$ and $C>0$ is a hyperparameter.

Note that if an instance $x_{i}$ is the zero vector, then for any
$\mathbf{w}\in\mathbb{R}^{d\times k}$ we have
$\mathtt{hinge}(w_{y_{i}}^{\prime}x_{i}-w_{j}^{\prime}x_{i})=1$. Thus, we can
simply ignore such an instance. Below, we assume that $\|x_{i}\|>0$ for all
$i\in[n]$.

###  2.1 Dual of the linear SVM

In this section, we recall the dual of P. Derivation of all results here can
be found in Hsu & Lin (2002); Keerthi et al. (2008).

We begin by defining the function $f:\mathbb{R}^{k\times n}\to\mathbb{R}$

$f(\bm{\alpha}):=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\alpha_{i}^{\prime}\alpha_{s}-\sum_{i\in[k]}\sum_{\begin{subarray}{c}j\in[k]:\\\
j\neq y_{i}\end{subarray}}\alpha_{ij}$

and the set

$\displaystyle\mathcal{F}:=\Big{\\{}$
$\displaystyle\bm{\alpha}\in\mathbb{R}^{k\times n}\mid$ $\displaystyle
0\leq\alpha_{ij}\leq C,\,\forall i\in[n],\,j\in[k],\,j\neq y_{i},$
$\displaystyle\alpha_{iy_{i}}=-\sum_{j\in[k]\setminus\\{y_{i}\\}}\alpha_{ij},\,\forall
i\in[n]\Big{\\}}.$

The dual problem of P is

$\min_{\bm{\alpha}\in\mathcal{F}}\,\,f(\bm{\alpha}).$ (D1)

The primal and dual variables $\mathbf{w}$ and $\bm{\alpha}$ are related via

$\mathbf{w}=-\sum_{i\in[n]}x_{i}\alpha_{i}^{\prime}.$ (1)

State-of-the-art solver Shark (Igel et al., 2008) uses coordinate descent on
the dual problem D1. It is also possible to solve the primal problem P using
stochastic gradient descent (SGD) as in Pegasos (Shalev-Shwartz et al., 2011).
However, the empirical results of Hsieh et al. (2008) show that CD on the dual
problem converges faster than SGD on the primal problem. Hence, we focus on
the dual problem.

###  2.2 Solving the dual with block coordinate descent

Block coordinate descent (BCD) is an iterative algorithm for solving the dual
problem D1 by repeatedly improving a candidate solution
$\bm{\alpha}\in\mathcal{F}$. Given an $i\in[n]$, an _inner iteration_ performs
the update $\bm{\alpha}\leftarrow\widetilde{\bm{\alpha}}$ where
$\widetilde{\bm{\alpha}}$ is a minimizer of the _$i$ -th subproblem_:

$\min_{\widehat{\bm{\alpha}}\in\mathcal{F}}\,\,f(\widehat{\bm{\alpha}})\,\,\mbox{such
that}\,\,\,\widehat{\alpha}_{s}=\alpha_{s},\,\forall s\in[n]\setminus\\{i\\}.$
(S1)

An _outer iteration_ performs the inner iteration once for each $i\in[n]$
possibly in a random order. By running several outer iterations, an
(approximate) minimizer of D1 is putatively obtained.

Later, we will see that it is useful to keep track of $\mathbf{w}$ so that 1
holds throughout the BCD algorithm. Suppose that $\bm{\alpha}$ and
$\mathbf{w}$ satisfy 1. Then $\mathbf{w}$ must be updated via

$\mathbf{w}\leftarrow\mathbf{w}-x_{i}(\widetilde{\alpha}_{i}-\alpha_{i})^{\prime}$
(2)

prior to updating $\bm{\alpha}\leftarrow\widetilde{\bm{\alpha}}$.

##  3 Reparametrization of the dual problem

In this section, we introduce a new way to parametrize the dual optimization
D1 which allows us to derive an algorithm for finding the exact minimizer of
S1.

Define the matrix
$\bm{\pi}:=\begin{bmatrix}\mathbb{1}&-\mathbf{I}\end{bmatrix}\in\mathbb{R}^{(k-1)\times
k}$. For each $y\in[k]$, let $\bm{\sigma}_{y}\in\mathbb{R}^{k\times k}$ be the
permutation matrix which switches the $1$st and the $y$th indices. In other
words, given a vector $v\in\mathbb{R}^{k}$, we have

$[\bm{\sigma}_{y}(v)]_{j}=\begin{cases}v_{1}&:j=y\\\ v_{y}&:j=1\\\
v_{j}&:j\not\in\\{1,y\\}.\end{cases}$

Define the function $g:\mathbb{R}^{(k-1)\times n}\to\mathbb{R}$

$g(\bm{\beta}):=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}-\sum_{i\in[n]}\mathbb{1}^{\prime}\beta_{i}$

and the set

$\displaystyle\mathcal{G}:=\Big{\\{}$
$\displaystyle\bm{\beta}\in\mathbb{R}^{(k-1)\times n}\mid$ $\displaystyle
0\leq\beta_{ij}\leq C,\,\forall i\in[n],\,j\in[k-1]\Big{\\}}.$

Consider the following optimization:

$\min_{\bm{\beta}\in\mathcal{G}}\,\,g(\bm{\beta}).$ (D2)

Up to a change of variables, the optimization D2 is equivalent to the dual of
the linear WW-SVM D1. In other words, D2 is a reparametrization of D1. Below,
we make this notion precise.

######  Definition 3.1.

Define a map $\Psi:\mathcal{G}\to\mathbb{R}^{k\times n}$ as follows: Given
$\bm{\beta}\in\mathcal{G}$, construct an element
$\Psi(\bm{\beta}):=\bm{\alpha}\in\mathbb{R}^{k\times n}$ whose $i$-th block is

$\alpha_{i}=-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}.$ (3)

The map $\Psi$ will serve as the change of variables map, where $\bm{\pi}$
reduces the dual variable’s dimension from $k$ for $\alpha_{i}$ to $k-1$ for
$\beta_{i}$. Furthermore, $\bm{\sigma}_{y_{i}}$ eliminates the dependency on
$y_{i}$ in the constraints. The following proposition shows that $\Psi$ links
the two optimization problems D1 and D2.

######  Proposition 3.2.

The image of $\Psi$ is $\mathcal{F}$, i.e., $\Psi(\mathcal{G})=\mathcal{F}$.
Furthermore, $\Psi:\mathcal{G}\to\mathcal{F}$ is a bijection and

$f(\Psi(\bm{\beta}))=g(\bm{\beta}).$

###### Sketch of proof.

Define another map $\Xi:\mathcal{F}\to\mathbb{R}^{(k-1)\times n}$ as follows:
For each $\bm{\alpha}\in\mathcal{F}$, define $\bm{\beta}:=\Xi(\bm{\alpha})$
block-wise by

$\beta_{i}:=\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}\alpha_{i})\in\mathbb{R}^{k-1}$

where

$\mathtt{proj}_{2:k}=\begin{bmatrix}\mathbb{0}&\mathbf{I}_{k-1}\end{bmatrix}\in\mathbb{R}^{(k-1)\times
k}.$

Then the range of $\Xi$ is in $\mathcal{G}$. Furthermore, $\Xi$ and $\Psi$ are
inverses of each other. This proves that $\Psi$ is a bijection. ∎

###  3.1 Reparametrized subproblem

Since the map $\Psi$ respects the block-structure of $\bm{\alpha}$ and
$\bm{\beta}$, the result below follows immediately from Proposition 3.2:

######  Corollary 3.3.

Let $\bm{\beta}\in\mathcal{G}$ and $i\in[n]$. Let
$\bm{\alpha}=\Psi(\bm{\beta})$. Consider

$\min_{\widehat{\bm{\beta}}\in\mathcal{G}}\,\,g(\widehat{\bm{\beta}})\,\,\mbox{such
that}\,\,\,\widehat{\beta}_{s}=\beta_{s},\,\forall s\in[n]\setminus\\{i\\}.$
(S2)

Let $\widetilde{\bm{\beta}}\in\mathcal{F}$ be arbitrary. Then
$\widetilde{\bm{\beta}}$ is a minimizer of S2 if and only if
$\widetilde{\bm{\alpha}}:=\Psi(\widetilde{\bm{\beta}})$ is a minimizer of S1.

Below, we focus on solving D2 with BCD, i.e., repeatedly performing the update
$\bm{\beta}\leftarrow\widetilde{\bm{\beta}}$ where $\widetilde{\bm{\beta}}$ is
a minimizer of S2 over different $i\in[n]$. By Corollary 3.3, this is
equivalent to solving D1 with BCD, up to the change of variables $\Psi$.

The reason we focus on solving D2 with BCD is because the subproblem can be
cast in a simple form that makes an exact solver more apparent. To this end,
we first show that the subproblem S2 is a quadratic program of a particular
form. Define the matrix $\bm{\Theta}:=\mathbf{I}_{k-1}+\mathbf{O}_{k-1}.$

######  Theorem 3.4.

Let $v\in\mathbb{R}^{k-1}$ be arbitrary and $C>0$. Consider the optimization

$\displaystyle\min_{b\in\mathbb{R}^{k-1}}\quad$
$\displaystyle\frac{1}{2}b^{\prime}\bm{\Theta}b-v^{\prime}b$ (4)
$\displaystyle s.t.\quad$ $\displaystyle 0\leq b\leq C.$

Then Algorithm 2, $\mathtt{solve\\_subproblem}(v,C)$, computes the unique
minimizer of 4 in $O(k\log k)$ time.

We defer further discussion of Theorem 3.4 and Algorithm 2 to the next
section. The quadratic program 4 is the _generic_ form of the subproblem S2,
as the following result shows:

######  Proposition 3.5.

In the situation of Corollary 3.3, let $\widetilde{\beta}_{i}$ be the $i$-th
block of the minimizer $\widetilde{\bm{\beta}}$ of S2. Then
$\widetilde{\beta}_{i}$ is the unique minimizer of 4 with

$v:=(\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i})/\|x_{i}\|_{2}^{2}+\bm{\Theta}\beta_{i}$

and $\mathbf{w}$ as in 1.

###  3.2 BCD for the reparametrized dual problem

As mentioned in Section 2.2, it is useful to keep track of $\mathbf{w}$ so
that 1 holds throughout the BCD algorithm. In Proposition 3.5, we see that
$\mathbf{w}$ is used to compute $v$. The update formula 2 for $\mathbf{w}$ in
terms of $\widetilde{\bm{\alpha}}$ can be cast in terms of $\bm{\beta}$ and
$\widetilde{\bm{\beta}}$ by using 3:

$\displaystyle\mathbf{w}\leftarrow\mathbf{w}-x_{i}(\widetilde{\alpha}_{i}-\alpha_{i})^{\prime}=\mathbf{w}+x_{i}(\widetilde{\beta}_{i}-\beta_{i})^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}.$

We now have all the ingredients to state the reparametrized block coordinate
descent pseudocode in Algorithm 1.

1: $\bm{\beta}\leftarrow\mathbf{0}_{(k-1)\times n}$

2: $\mathbf{w}\leftarrow\mathbf{0}_{d\times k}$

3: while not converged do

4: for $i\leftarrow 1$ to $n$ do

5:
$v\leftarrow(\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i})/\|x_{i}\|_{2}^{2}+\bm{\Theta}\beta_{i}$

6: $\widetilde{\beta}_{i}\leftarrow\mathtt{solve\\_subproblem}(v,C)$
(Algorithm 2)

7:
$\mathbf{w}\leftarrow\mathbf{w}+x_{i}(\widetilde{\beta}_{i}-\beta_{i})^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}$

8: $\beta_{i}\leftarrow\widetilde{\beta}_{i}$

9: end for

10: end while

Algorithm 1 Block coordinate descent on D2

Multiplying a vector by the matrices $\bm{\Theta}$ and $\bm{\pi}$ both only
takes $O(k)$ time. Multiplying a vector by $\bm{\sigma}_{y_{i}}$ takes $O(1)$
time since $\bm{\sigma}_{t_{i}}$ simply swaps two entries of the vector.
Hence, the speed bottlenecks of Algorithm 1 are computing
$\mathbf{w}^{\prime}x_{i}$ and
$x_{i}(\widetilde{\beta}_{i}-\beta_{i})^{\prime}$, both taking $O(dk)$ time
and running $\mathtt{solve\\_subproblem}(v,C)$, which takes $O(k\log k)$ time.
Overall, a single inner iteration of Algorithm 1 takes $O(dk+k\log k)$ time.
If $x_{i}$ is $s$-sparse (only $s$ entries are nonzero), then the iteration
takes $O(sk+k\log k)$ time.

###  3.3 Linear convergence

Similar to the binary case (Hsieh et al., 2008), BCD converges _linearly_ ,
i.e., it produces an $\epsilon$-accurate solution in $O(\log(1/\epsilon))$
outer iterations:

######  Theorem 3.6.

Algorithm 1 has global linear convergence. More precisely, let
$\bm{\beta}^{t}$ be $\bm{\beta}$ at the end of the $t$-th iteration of the
outer loop of Algorithm 1. Let
$g^{*}=\min_{\bm{\beta}\in\mathcal{G}}g(\bm{\beta})$. Then there exists
$\Delta\in(0,1)$ such that

$g(\bm{\beta}^{t+1})-g^{*}\leq\Delta(g(\bm{\beta}^{t})-g^{*}),\qquad\forall
t=0,1,2\dots$ (5)

where $\Delta$ depends on the data $\\{(x_{i},y_{i})\\}_{i\in[n]}$, $k$ and
$C$.

Luo & Tseng (1992) proved asymptotic333 Asymptotic in the sense that 5 is only
guaranteed after $t>t_{0}$ for some unknown $t_{0}$.  linear convergence for
cyclic coordinate descent for a certain class of minimization problems where
the subproblem in each coordinate is _exactly_ minimized. Furthermore, Luo &
Tseng (1992) claim that the same result holds if the subproblem is
_approximately_ minimized, but did not give a precise statement (e.g.,
approximation in which sense).

Keerthi et al. (2008) asserted without proof that the results of Luo & Tseng
(1992) can be applied to BCD for WW-SVM. Possibly, no proof was given since no
solver, exact nor approximate with approximation guarantees, was known at the
time. Theorem 3.6 settles this issue, which we prove in Section A.4 by
extending the analysis of Luo & Tseng (1992); Wang & Lin (2014) to the
multiclass case.

##  4 Sketch of proof of Theorem 3.4

Throughout this section, let $v\in\mathbb{R}^{k-1}$ and $C>0$ be fixed. We
first note that 4 is a minimization of a strictly convex function over a
compact domain, and hence has unique minimizer
$\widetilde{b}\in\mathbb{R}^{k-1}$. Furthermore, it is the unique point
satisfying the KKT conditions, which we present below. Our goal is to sketch
the argument that Algorithm 2 outputs the minimizer upon termination. The full
proof can be found in Section A.5.

###  4.1 Intuition

We first study the structure of the minimizer $\widetilde{b}$ in and of
itself. The KKT conditions for a point $b\in\mathbb{R}^{k-1}$ to be optimal
for 4 are as follows:

$\displaystyle\forall i\in[k-1],\exists\lambda_{i},\mu_{i}\in\mathbb{R}$
satisfying
$\displaystyle[(\mathbf{I}+\mathbf{O})b]_{i}+\lambda_{i}-\mu_{i}=v_{i}\quad$
stationarity (KKT) $\displaystyle C\geq b_{i}\geq 0\quad$ primal feasibility
$\displaystyle\lambda_{i}\geq 0,\mbox{ and }\mu_{i}\geq 0\quad$ dual
feasibility $\displaystyle\lambda_{i}(C-b_{i})=0,\mbox{ and
}\mu_{i}b_{i}=0\quad$ complementary slackness

Below, let $\max_{i\in[k-1]}v_{i}=:v_{\max}$, and $\langle
1\rangle,\dots,\langle k-1\rangle$ be an argsort of $v$, i.e., $v_{\langle
1\rangle}\geq\dots\geq v_{\langle k-1\rangle}.$

######  Definition 4.1.

The _clipping map_ $\mathtt{clip}_{C}:\mathbb{R}^{k-1}\to[0,C]^{k-1}$ is the
function defined as follows: for $w\in\mathbb{R}^{k-1}$,
$[\mathtt{clip}_{C}(w)]_{i}:=\max\\{0,\min\\{C,w_{i}\\}\\}$.

Using the KKT conditions, we check that
$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})$ for some
(unknown) $\widetilde{\gamma}\in\mathbb{R}$ and that
$\widetilde{\gamma}=\mathbb{1}^{\prime}\widetilde{b}$.

###### Proof.

Let $\widetilde{\gamma}\in\mathbb{R}$ be such that
$\mathbf{O}\widetilde{b}=\widetilde{\gamma}\mathbb{1}$. The stationarity
condition can be rewritten as
$\widetilde{b}_{i}+\lambda_{i}-\mu_{i}=v_{i}-\widetilde{\gamma}$. Thus, by
complementary slackness and dual feasibility, we have

$\widetilde{b}_{i}\begin{cases}\leq
v_{i}-\widetilde{\gamma}&:\widetilde{b}_{i}=C\\\
=v_{i}-\widetilde{\gamma}&:\widetilde{b}_{i}\in(0,C)\\\ \geq
v_{i}-\widetilde{\gamma}&:\widetilde{b}_{i}=0\end{cases}$

Note that this is precisely
$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})$. ∎

For $\gamma\in\mathbb{R}$, let
$b^{\gamma}:=\mathtt{clip}_{C}(v-{\gamma}\mathbb{1})\in\mathbb{R}^{k-1}$.
Thus, the $(k-1)$-dimensional vector $\widetilde{b}$ can be recovered from the
scalar $\widetilde{\gamma}$ via $b^{\widetilde{\gamma}}$, reducing the search
space from $\mathbb{R}^{k-1}$ to $\mathbb{R}$.

However, the search space $\mathbb{R}$ is still a continuum. We show that the
search space for $\widetilde{\gamma}$ can be further reduced to a finite set
of candidates. To this end, let us define

$\displaystyle I_{\mathfrak{u}}^{\gamma}$
$\displaystyle:=\\{i\in[k-1]:b^{\gamma}_{i}=C\\}$ $\displaystyle
I_{\mathfrak{m}}^{\gamma}$
$\displaystyle:=\\{i\in[k-1]:b^{\gamma}_{i}\in(0,C)\\}.$

Note that $I_{\mathfrak{u}}^{\gamma}$ and $I_{\mathfrak{m}}^{\gamma}$ are
determined by their cardinalities, denoted $n_{\mathfrak{u}}^{\gamma}$ and
$n_{\mathfrak{m}}^{\gamma}$, respectively. This is because

$\displaystyle I_{\mathfrak{u}}^{\gamma}$ $\displaystyle=\\{\langle
1\rangle,\langle 2\rangle,\dots,\langle n_{\mathfrak{u}}^{\gamma}\rangle\\}$
$\displaystyle I_{\mathfrak{m}}^{\gamma}$ $\displaystyle=\\{\langle
n_{\mathfrak{u}}^{\gamma}+1\rangle,\langle
n_{\mathfrak{u}}^{\gamma}+2\rangle,\dots,\langle
n_{\mathfrak{u}}^{\gamma}+n_{\mathfrak{m}}^{\gamma}\rangle\\}.$

Let $\llfloor k\rrfloor:=\\{0\\}\cup[k-1]$. By definition,
$n_{\mathfrak{m}}^{\gamma},n_{\mathfrak{u}}^{\gamma}\in\llfloor k\rrfloor$.
For $(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\llfloor k\rrfloor^{2}$, define
$S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$,
$\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\in\mathbb{R}$ by

$\displaystyle S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\sum_{i=n_{\mathfrak{u}}+1}^{n_{\mathfrak{u}}+n_{\mathfrak{m}}}v_{\langle
i\rangle},$ (6)
$\displaystyle\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\left(C\cdot
n_{\mathfrak{u}}+S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\right)/(n_{\mathfrak{m}}+1).$
(7)

Furthermore, define
$\widehat{b}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\in\mathbb{R}^{k-1}$ such
that, for $i\in[k-1]$, the $\langle i\rangle$-th entry is

$\displaystyle\widehat{b}_{\langle
i\rangle}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\begin{cases}C&:i\leq n_{\mathfrak{u}}\\\ v_{\langle
i\rangle}-\gamma^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}&:n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$

Using the KKT conditions, we check that

$\widetilde{b}=\widehat{b}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}=\mathtt{clip}_{C}(v-\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}\mathbb{1}).$

###### Proof.

It suffices to prove that
$\widetilde{\gamma}=\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}$.
To this end, let $i\in[k-1]$. If $i\in I_{\mathfrak{m}}^{\widetilde{\gamma}}$,
then $\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}$. If $i\in
I_{\mathfrak{u}}^{\widetilde{\gamma}}$, then $\widetilde{b}_{i}=C$. Otherwise,
$\widetilde{b}_{i}=0$. Thus

$\widetilde{\gamma}=\mathbb{1}^{\prime}\widetilde{b}=C\cdot
n_{\mathfrak{u}}^{\widetilde{\gamma}}+S^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}-\widetilde{\gamma}\cdot
n_{\mathfrak{m}}^{\widetilde{\gamma}}$ (8)

Solving for $\widetilde{\gamma}$, we have

$\widetilde{\gamma}=\left(C\cdot
n_{\mathfrak{u}}^{\widetilde{\gamma}}+S^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}\right)/(n_{\mathfrak{m}}^{\widetilde{\gamma}}+1)=\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})},$

as desired. ∎

Now, since
$(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})\in\llfloor
k\rrfloor^{2}$, to find $\widetilde{b}$ we can simply check for each
$(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\llfloor k\rrfloor^{2}$ if
$\widehat{b}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$ satisfies the KKT
conditions. However, this naive approach leads to an $O(k^{2})$ runtime.

To improve upon the naive approach, define

$\Re:=\\{(n_{\mathfrak{m}}^{\gamma},n_{\mathfrak{u}}^{\gamma}):\gamma\in\mathbb{R}\\}.$
(9)

Since
$(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})\in\Re$,
to find $\widetilde{b}$ it suffices to search through
$(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\Re$ instead of $\llfloor
k\rrfloor^{2}$. Towards enumerating all elements of $\Re$, a key result is
that the function
$\gamma\mapsto(I_{\mathfrak{m}}^{\gamma},I_{\mathfrak{u}}^{\gamma})$ is
locally constant outside of the set of discontinuities:

$\mathtt{disc}:=\\{v_{i}:i\in[k-1]\\}\cup\\{v_{i}-C:i\in[k-1]\\}.$

###### Proof.

Let $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}\in\mathbb{R}$ satisfy the
following: 1) $\gamma_{1}<\gamma_{2}<\gamma_{3}<\gamma_{4}$, 2)
$\gamma_{1},\gamma_{4}\in\mathtt{disc}$, and 3) $\gamma\not\in\mathtt{disc}$
for all $\gamma\in(\gamma_{1},\gamma_{4})$. Assume for the sake of
contradiction that
$(I_{\mathfrak{m}}^{\gamma_{2}},I_{\mathfrak{u}}^{\gamma_{2}})\neq(I_{\mathfrak{m}}^{\gamma_{3}},I_{\mathfrak{u}}^{\gamma_{3}})$.
Then $I_{\mathfrak{m}}^{\gamma_{2}}\neq I_{\mathfrak{m}}^{\gamma_{3}}$ or
$I_{\mathfrak{u}}^{\gamma_{2}}\neq I_{\mathfrak{u}}^{\gamma_{3}}$. Consider
the case $I_{\mathfrak{m}}^{\gamma_{2}}\neq I_{\mathfrak{m}}^{\gamma_{3}}$.
Then at least one of the sets $I_{\mathfrak{m}}^{\gamma_{2}}\setminus
I_{\mathfrak{m}}^{\gamma_{3}}$ and $I_{\mathfrak{m}}^{\gamma_{3}}\setminus
I_{\mathfrak{m}}^{\gamma_{2}}$ is nonempty. Consider the case when
$I_{\mathfrak{m}}^{\gamma_{2}}\setminus I_{\mathfrak{m}}^{\gamma_{3}}$ is
nonempty. Then there exists $i\in[k-1]$ such that $v_{i}-\gamma_{2}\in(0,C)$
but $v_{i}-\gamma_{3}\not\in(0,C)$. This implies that there exists some
$\gamma^{\prime}\in(\gamma_{2},\gamma_{3})$ such that
$v_{i}-\gamma^{\prime}\in\\{0,C\\}$, or equivalently,
$\gamma^{\prime}\in\\{v_{i},v_{i}-C\\}$. Hence,
$\gamma^{\prime}\in\mathtt{disc}$, which is a contradiction. For the other
cases not considered, similar arguments lead to the same contradiction. ∎

Thus, as we sweep $\gamma$ from $+\infty$ to $-\infty$, we observe finitely
many distinct tuples of sets
$(I_{\mathfrak{m}}^{\gamma},I_{\mathfrak{u}}^{\gamma})$ and their
cardinalities $(n_{\mathfrak{m}}^{\gamma},n_{\mathfrak{u}}^{\gamma})$. Using
the index $t=0,1,2\dots$, we keep track of these data in the variables
$(I_{\mathfrak{m}}^{t},I_{\mathfrak{u}}^{t})$ and
$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})$. For this proof sketch, we make
the assumption that $|\mathtt{disc}|=2(k-1)$, i.e., no elements are repeated.

By construction, the maximal element of $\mathtt{disc}$ is $v_{\max}$. When
$\gamma>v_{\max}$, we check that
$n_{\mathfrak{m}}^{\gamma}=n_{\mathfrak{u}}^{\gamma}=\emptyset$. Thus, we put
$I_{\mathfrak{m}}^{0}=I_{\mathfrak{u}}^{0}=\emptyset$ and
$(n_{\mathfrak{m}}^{0},n_{\mathfrak{u}}^{0})=(0,0).$

Now, suppose $\gamma$ has swept across $t-1$ points of discontinuity and that
$I_{\mathfrak{m}}^{t-1},I_{\mathfrak{u}}^{t-1},n_{\mathfrak{m}}^{t-1},n_{\mathfrak{u}}^{t-1}$
have all been defined. Suppose that $\gamma$ crossed a single new point of
discontinuity $\gamma^{\prime}\in\mathtt{disc}$. In other words,
$\gamma^{\prime\prime}<\gamma<\gamma^{\prime}$ where $\gamma^{\prime\prime}$
is the largest element of $\mathtt{disc}$ such that
$\gamma^{\prime\prime}<\gamma^{\prime}$.

By the assumption that no elements of $\mathtt{disc}$ are repeated, exactly
one of the two following possibilities is true:

$\displaystyle\mbox{there exists }i\in[k-1]\mbox{ such that
}\gamma^{\prime}=v_{i},$ (Entry) $\displaystyle\mbox{there exists
}i\in[k-1]\mbox{ such that }\gamma^{\prime}=v_{i}-C.$ (Exit)

Under the Entry case, the index $i$ gets added to $I_{\mathfrak{m}}^{t-1}$
while $I_{\mathfrak{u}}^{t-1}$ remains unchanged. Hence, we have the updates

$\displaystyle
I_{\mathfrak{m}}^{t}:=I_{\mathfrak{m}}^{\gamma}=I_{\mathfrak{m}}^{t-1}\cup\\{i\\},\quad
I_{\mathfrak{u}}^{t}:=I_{\mathfrak{u}}^{\gamma}=I_{\mathfrak{u}}^{t-1}$ (10)
$\displaystyle
n_{\mathfrak{m}}^{t}:=n_{\mathfrak{m}}^{\gamma}=n_{\mathfrak{m}}^{t-1}+1,\quad
n_{\mathfrak{u}}^{t}:=n_{\mathfrak{u}}^{\gamma}=n_{\mathfrak{u}}^{t-1}.$ (11)

Under the Exit case, the index $i$ moves from $I_{\mathfrak{m}}^{t-1}$ to
$I_{\mathfrak{u}}^{t-1}$. Hence, we have the updates

$\displaystyle
I_{\mathfrak{m}}^{t}:=I_{\mathfrak{m}}^{\gamma}=I_{\mathfrak{m}}^{t-1}\setminus\\{i\\},\quad
I_{\mathfrak{u}}^{t}:=I_{\mathfrak{u}}^{\gamma}=I_{\mathfrak{u}}^{t-1}\cup\\{i\\}$
(12) $\displaystyle
n_{\mathfrak{m}}^{t}:=n_{\mathfrak{m}}^{\gamma}=n_{\mathfrak{m}}^{t-1}-1,\quad
n_{\mathfrak{u}}^{t}:=n_{\mathfrak{u}}^{\gamma}=n_{\mathfrak{u}}^{t-1}+1.$
(13)

Thus, $\\{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})\\}_{t=0}^{2(k-1)}=\Re.$
The case when $\mathtt{disc}$ has repeated elements requires more careful
analysis which is done in the full proof. Now, we have all the ingredients for
understanding Algorithm 2 and its subroutines.

###  4.2 A walk through of the solver

If $v_{\max}\leq 0$, then $\widetilde{b}=\mathbb{0}$ satisfies the KKT
conditions. Algorithm 2-line 3 handles this exceptional case. Below, we assume
$v_{\max}>0$.

1: Input: $v\in\mathbb{R}^{k-1}$

2: Let $\langle 1\rangle,\dots,\langle k-1\rangle$ sort $v$, i.e., $v_{\langle
1\rangle}\geq\dots\geq v_{\langle k-1\rangle}.$

3: if $v_{\langle 1\rangle}\leq 0$ then HALT and output:
$\mathbb{0}\in\mathbb{R}^{k-1}$.

4: $n_{\mathfrak{u}}^{0}:=0$, $n_{\mathfrak{m}}^{0}:=0$, $S^{0}:=0$

5: $(\delta_{1},\dots,\delta_{\ell})\leftarrow\mathtt{get\\_up\\_dn\\_seq}()$
(Subroutine 3)

6: for $t=1,\dots,\ell$ do

7:
$(n_{\mathfrak{m}}^{t},\,n_{\mathfrak{u}}^{t},\,S^{t})\leftarrow\mathtt{update\\_vars}()$
(Subroutine 4).

8: $\widehat{\gamma}^{t}:=(C\cdot
n_{\mathfrak{u}}^{t}+S^{t})/(n_{\mathfrak{m}}^{t}+1)$

9: if $\mathtt{KKT\\_cond}()$ (Subroutine 5) returns true then

10: HALT and output: $\widehat{b}^{t}\in\mathbb{R}^{k-1}$ where
$\widehat{b}_{\langle i\rangle}^{t}:=\begin{cases}C&:i\leq
n_{\mathfrak{u}}^{t}\\\ v_{\langle
i\rangle}-\gamma^{t}&:n_{\mathfrak{u}}^{t}<i\leq
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\\\
0&:n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}<i.\end{cases}$

11: end if

12: end for

Algorithm 2 $\mathtt{solve\\_subproblem}(v,C)$

Algorithm 2-line 4 initializes the state variables $n_{\mathfrak{m}}^{t}$ and
$n_{\mathfrak{u}}^{t}$ as discussed in the last section. The variable $S^{t}$
is also initialized and will be updated to maintain
$S^{t}=S^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$ where the latter is
defined at 6.

Algorithm 2-line 5 calls Subroutine 3 to construct the $\mathtt{vals}$ ordered
set, which is similar to the set of discontinuities $\mathtt{disc}$, but
different in three ways: 1) $\mathtt{vals}$ consists of tuples
$(\gamma^{\prime},\delta^{\prime})$ where $\gamma^{\prime}\in\mathtt{disc}$
and $\delta^{\prime}\in\\{\mathtt{up},\mathtt{dn}\\}$ is a decision variable
indicating whether $\gamma^{\prime}$ satisfies the Entry or the Exit
condition, 2) $\mathtt{vals}$ is sorted so that the $\gamma^{\prime}$s are in
descending order, and 3) only positive values of $\mathtt{disc}$ are needed.
The justification for the third difference is because we prove that Algorithm
2 always halts before reaching the negative values of $\mathtt{disc}$.
Subroutine 3 returns the list of symbols $(\delta_{1},\dots,\delta_{\ell})$
consistent with the ordering.

1:
$\mathtt{vals}\leftarrow\\{(v_{i},\mathtt{dn}):v_{i}>0,\,i=1,\dots,k-1\\}\,\,\cup\,\,\\{(v_{i}-C,\mathtt{up}):v_{i}>C,\,i=1,\dots,k-1\\}$
as a multiset, where elements may be repeated.

2: Order the set
$\mathtt{vals}=\\{(\gamma_{1},\delta_{1}),\dots,(\gamma_{\ell},\delta_{\ell})\\}$
such that $\gamma_{1}\geq\dots\geq\gamma_{\ell}$, $\ell=|\mathtt{vals}|$, and
for all $j_{1},j_{2}\in[\ell]$ such that $j_{1}<j_{2}$ and
$\gamma_{j_{1}}=\gamma_{j_{2}}$, we have $\delta_{j_{1}}=\mathtt{dn}$ implies
$\delta_{j_{2}}=\mathtt{dn}$. Note that by construction, for each
$t\in[\ell]$, there exists $i\in[k-1]$ such that $\gamma_{t}=v_{i}$ or
$\gamma_{t}=v_{i}-C$.

3: Output: sequence $(\delta_{1},\dots,\delta_{\ell})$ whose elements are
retrieved in order from left to right.

Subroutine 3 $\mathtt{get\\_up\\_dn\\_seq}$ _Note: all variables from
Algorithm 2 are assumed to be visible here._

In the “for” loop, Algorithm 2-line 7 calls Subroutine 4 which updates the
variables $n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t}$ using 11 or 13,
depending on $\delta_{t}$. The variable $S^{t}$ is updated accordingly so that
$S^{t}=S^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$.

1: if $\delta_{t}=\mathtt{up}$ then

2: $n_{\mathfrak{u}}^{t}:=n_{\mathfrak{u}}^{t-1}+1$,
$n_{\mathfrak{m}}^{t}:=n_{\mathfrak{m}}^{t-1}-1$

3: $S^{t}:=S^{t-1}-v_{\langle n_{\mathfrak{u}}^{t-1}\rangle}$

4: else

5: $n_{\mathfrak{m}}^{t}:=n_{\mathfrak{m}}^{t-1}+1$,
$n_{\mathfrak{u}}^{t}:=n_{\mathfrak{u}}^{t-1}$.

6: $S^{t}:=S^{t-1}+v_{\langle
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\rangle}$

7: end if

8: Output: $(n_{\mathfrak{m}}^{t},\,n_{\mathfrak{u}}^{t},\,S^{t})$

Subroutine 4 $\mathtt{update\\_vars}$ _Note: all variables from Algorithm 2
are assumed to be visible here._

We skip to Algorithm 2-line 9 which constructs the putative solution
$\widehat{b}^{t}$. Observe that
$\widehat{b}^{t}=\widehat{b}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$
where the latter is defined in the previous section.

Going back one line, Algorithm 2-line 8 calls Subroutine 5 which checks if the
putative solution $\widehat{b}^{t}$ satisfies the KKT conditions. We note that
this can be done _before_ the putative solution is constructed.

1: $\mathtt{kkt\\_cond}\leftarrow true$

2: if $n_{\mathfrak{u}}^{t}>0$ then

3:
$\mathtt{kkt\\_cond}\leftarrow\mathtt{kkt\\_cond}\land\left(C+\widehat{\gamma}^{t}\leq
v_{\langle n_{\mathfrak{u}}^{t}\rangle}\right)$ _Note: $\land$ denotes the
logical “and”._

4: end if

5: if $n_{\mathfrak{m}}^{t}>0$ then

6: $\mathtt{kkt\\_cond}\leftarrow\mathtt{kkt\\_cond}\land\left(v_{\langle
n_{\mathfrak{u}}^{t}+1\rangle}\leq C+\widehat{\gamma}^{t}\right)$

7:
$\mathtt{kkt\\_cond}\leftarrow\mathtt{kkt\\_cond}\land\left(\widehat{\gamma}^{t}\leq
v_{\langle n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\rangle}\right)$

8: end if

9: if $n_{\mathfrak{d}}^{t}:=k-1-n_{\mathfrak{u}}^{t}-n_{\mathfrak{m}}^{t}>0$
then

10: $\mathtt{kkt\\_cond}\leftarrow\mathtt{kkt\\_cond}\land\left(v_{\langle
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}+1\rangle}\leq\widehat{\gamma}^{t}\right)$

11: end if

12: Output: $\mathtt{kkt\\_cond}$

Subroutine 5 $\mathtt{KKT\\_cond}$ _Note: all variables from Algorithm 2 are
assumed to be visible here._

For the runtime analysis, we note that Subroutines 5 and 4 both use $O(1)$
FLOPs without dependency on $k$. The main “for” loop of Algorithm 2 (line 6
through 11) has $O(\ell)$ runtime where $\ell\leq 2(k-1)$. Thus, the
bottlenecks are Algorithm 2-line 2 and 5 which sort lists of length at most
$k-1$ and $2(k-1)$, respectively. Thus, both lines run in $O(k\log k)$ time.

##  5 Experiments

LIBLINEAR is one of the state-of-the-art solver for linear SVMs (Fan et al.,
2008). However, as of the latest version 2.42, the linear Weston-Watkins SVM
is not supported. We implemented our linear WW-SVM subproblem solver, _Walrus_
(Algorithm 2), along with the BCD Algorithm 1 as an extension to LIBLINEAR.
The solver and code for generating the figures are available444See Section
A.6..

We compare our implementation to _Shark_ (Igel et al., 2008), which solves the
dual subproblem S1 using a form of greedy coordinate descent. For comparisons,
we reimplemented Shark’s solver also as a LIBLINEAR extension. When clear from
the context, we use the terms “Walrus” and “Shark” when referring to either
the subproblem solver or the overall BCD algorithm.

We perform benchmark experiments on 8 datasets from “LIBSVM Data:
Classification (Multi-class)555See Section A.6.2.” spanning a range of $k$
from $3$ to $1000$. See Table 1.

Table 1: Data sets used. Variables $k,\,n$ and $d$ are, respectively, the
number of classes, training samples, and features.
Data set | $k$ | $n$ | $d$
---|---|---|---
dna | 3 | 2,000 | 180
satimage | 6 | 4,435 | 36
mnist | 10 | 60,000 | 780
news20 | 20 | 15,935 | 62,061
letter | 26 | 15,000 | 16
rcv1 | 53 | 15,564 | 47,236
sector | 105 | 6,412 | 55,197
aloi | 1,000 | 81,000 | 128

In all of our experiments, Walrus and Shark perform identically in terms of
testing accuracy. We report the accuracies in Section A.6.3. Below, we will
only discuss runtime.

For measuring the runtime, we start the timer after the data sets have been
loaded into memory and before the state variables $\bm{\beta}$ and
$\mathbf{w}$ have been allocated. The primal objective is the value of P at
the current $\mathbf{w}$ and the dual objective is $-1$ times the value of D2
at the current $\bm{\beta}$. The duality gap is the primal minus the dual
objective. The objective values and duality gaps are measured after each
_outer_ iteration, during which the timer is paused.

For solving the subproblem, Walrus is guaranteed to return the minimizer in
$O(k\log k)$ time. On the other hand, to the best of our knowledge, Shark does
not have such guarantee. Furthermore, Shark uses a doubly-nested for loop,
each of which has length $O(k)$, yielding a worst-case runtime of $O(k^{2})$.
For these reasons, we hypothesize that Walrus scales better with larger $k$.

As exploratory analysis, we ran Walrus and Shark on the satimage and sector
data sets666 The regularizers are set to the corresponding values from Table 5
of the supplementary material of Doǧan et al. (2016) chosen by cross-
validation. , which has $6$ and $105$ classes, respectively. The results,
shown in Figure 1, support our hypothesis: Walrus and Shark are equally fast
for satimage while Walrus is faster for sector.

Figure 1: Runtime comparison of Walrus and Shark. Abbreviations: pr. = primal
and du. = dual. The X-axes show time elapsed.

We test our hypothesis on a larger scale by running Walrus and Shark on the
datasets in Table 1 over the grid of hyperparameters
$C\in\\{2^{-6},2^{-5},\dots,2^{2},2^{3}\\}$. The results are shown in Figure 2
where each dot represents a triplet $(\mbox{{data set}},C,\delta)$ where
$\delta$ is a quantity we refer to as the _duality gap decay_. The Y-axis
shows the comparative metric of runtime
$\mathtt{ET}_{\mathtt{Walrus}}^{\delta}/\mathtt{ET}_{\mathtt{Shark}}^{\delta}$
to be defined next.

Consider a single run of Walrus on a fixed data set with a given
hyperparameter $C$. Let $\mathtt{DG}_{\mathtt{Walrus}}^{t}$ denote the duality
gap achieved by Walrus at the end of the $t$-th outer iteration. Let
$\delta\in(0,1)$. Define $\mathtt{ET}_{\mathtt{Walrus}}^{\delta}$ to be the
elapsed time at the end of the $t$-th iteration where $t$ is minimal such that
$\mathtt{DG}_{\mathtt{Walrus}}^{t}\leq\delta\cdot\mathtt{DG}_{\mathtt{Walrus}}^{1}$.
Define $\mathtt{DG}_{\mathtt{Shark}}^{t}$ and
$\mathtt{ET}_{\mathtt{Shark}}^{\delta}$ similarly. In all experiments
$\mathtt{DG}_{\mathtt{Walrus}}^{1}/\mathtt{DG}_{\mathtt{Shark}}^{1}\in[0.99999,1.00001]$.
Thus, the ratio
$\mathtt{ET}_{\mathtt{Walrus}}^{\delta}/\mathtt{ET}_{\mathtt{Shark}}^{\delta}$
measures how much faster Shark is relative to Walrus.

From Figure 2, it is evident that in general Walrus converges faster on data
sets with larger number of classes. Not only does Walrus beat Shark for large
$k$, but it also seems to not do much worse for small $k$. In fact Walrus
seems to be at least as fast as Shark for all datasets except satimage.

The absolute amount of time saved by Walrus is often more significant on
datasets with larger number of classes. To illustrate this, we let $C=1$ and
compare the times for the duality gap to decay by a factor of $0.01$. On the
data set satimage with $k=6$, Walrus and Shark take $0.0476$ and $0.0408$
seconds, respectively. On the data set aloi with $k=1000$, Walrus and Shark
take $188$ and $393$ seconds, respectively.

We remark that Figure 2 also suggests that Walrus tends to be faster during
early iterations but can be slower at late stages of the optimization. To
explain this phenomenon, we note that Shark solves the subproblem using an
iterative descent algorithm and is set to stop when the KKT violations fall
below a hard-coded threshold. When close to optimality, Shark takes fewer
descent steps, and hence less time, to reach the stopping condition on the
subproblems. On the other hand, Walrus takes the same amount of time
regardless of proximity to optimality.

For the purpose of grid search, a high degree of optimality is not needed. In
Section A.6.3, we provide empirical evidence that stopping early versus late
does not change the result of grid search-based hyperparameter tuning.
Specifically, Table 7 shows that running the solvers until $\delta\approx
0.01$ or until $\delta\approx 0.001$ does not change the cross-validation
outcomes.

Finally, the optimization 4 is a convex quadratic program and hence can be
solved using general-purpose solvers (Voglis & Lagaris, 2004). However, we
find that Walrus, being specifically tailored to the optimization 4, is orders
of magnitude faster. See Tables 8 and 9 in the Appendix.

Figure 2:  X-coordinates jittered for better visualization.

##  6 Discussions and future works

We presented an algorithm called Walrus for exactly solving the WW-subproblem
which scales with the number of classes. We implemented Walrus in the
LIBLINEAR framework and demonstrated empirically that BCD using Walrus is
significantly faster than state-of-the-art linear WW-SVM solver Shark on
datasets with a large number of classes, and comparable to Shark for small
number of classes.

One possible direction for future research is whether Walrus can improve
_kernel_ WW-SVM solver. Another direction is lower-bounding time complexity of
solving the WW-subproblem 4.

## Acknowledgements

The authors were supported in part by the National Science Foundation under
awards 1838179 and 2008074, by the Department of Defense, Defense Threat
Reduction Agency under award HDTRA1-20-2-0002, and by the Michigan Institute
for Data Science.

## References

  * Babichev et al. (2019) Babichev, D., Ostrovskii, D., and Bach, F.  Efficient primal-dual algorithms for large-scale multiclass classification.  _arXiv preprint arXiv:1902.03755_ , 2019.
  * Beck et al. (2018) Beck, A., Pauwels, E., and Sabach, S.  Primal and dual predicted decrease approximation methods.  _Mathematical Programming_ , 167(1):37–73, 2018\.
  * Blondel et al. (2014) Blondel, M., Fujino, A., and Ueda, N.  Large-scale multiclass support vector machine training via Euclidean projection onto the simplex.  In _2014 22nd International Conference on Pattern Recognition_ , pp. 1289–1294. IEEE, 2014.
  * Boser et al. (1992) Boser, B. E., Guyon, I. M., and Vapnik, V. N.  A training algorithm for optimal margin classifiers.  In _Proceedings of the Fifth Annual Workshop on Computational Learning Theory_ , pp. 144–152, 1992.
  * Bredensteiner & Bennett (1999) Bredensteiner, E. J. and Bennett, K. P.  Multicategory classification by support vector machines.  In _Computational Optimization_ , pp. 53–79. Springer, 1999.
  * Chang & Lin (2011) Chang, C.-C. and Lin, C.-J.  Libsvm: A library for support vector machines.  _ACM transactions on intelligent systems and technology (TIST)_ , 2(3):1–27, 2011.
  * Chen et al. (2006) Chen, P.-H., Fan, R.-E., and Lin, C.-J.  A study on SMO-type decomposition methods for support vector machines.  _IEEE Trans. Neural Networks_ , 17(4):893–908, 2006.
  * Chiu et al. (2020) Chiu, C.-C., Lin, P.-Y., and Lin, C.-J.  Two-variable dual coordinate descent methods for linear SVM with/without the bias term.  In _Proceedings of the 2020 SIAM International Conference on Data Mining_ , pp. 163–171. SIAM, 2020.
  * Condat (2016) Condat, L.  Fast projection onto the simplex and the $l_{1}$ ball.  _Mathematical Programming_ , 158(1-2):575–585, 2016.
  * Cortes & Vapnik (1995) Cortes, C. and Vapnik, V.  Support-vector networks.  _Machine Learning_ , 20(3):273–297, 1995.
  * Crammer & Singer (2001) Crammer, K. and Singer, Y.  On the algorithmic implementation of multiclass kernel-based vector machines.  _Journal of Machine Learning Research_ , 2(Dec):265–292, 2001.
  * Didiot & Lauer (2015) Didiot, E. and Lauer, F.  Efficient optimization of multi-class support vector machines with msvmpack.  In _Modelling, Computation and Optimization in Information Systems and Management Sciences_ , pp. 23–34. Springer, 2015.
  * Doǧan et al. (2016) Doǧan, U., Glasmachers, T., and Igel, C.  A unified view on multi-class support vector classification.  _The Journal of Machine Learning Research_ , 17(1):1550–1831, 2016.
  * Duchi et al. (2008) Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T.  Efficient projections onto the $l_{1}$-ball for learning in high dimensions.  In _Proceedings of the 25th International Conference on Machine Learning_ , pp. 272–279, 2008.
  * Fan et al. (2005) Fan, R.-E., Chen, P.-H., and Lin, C.-J.  Working set selection using second order information for training support vector machines.  _Journal of Machine Learning Research_ , 6(Dec):1889–1918, 2005.
  * Fan et al. (2008) Fan, R.-E., Chang, K.-W., Hsieh, C.-J., Wang, X.-R., and Lin, C.-J.  Liblinear: A library for large linear classification.  _Journal of Machine Learning Research_ , 9:1871–1874, 2008\.
  * Fernández-Delgado et al. (2014) Fernández-Delgado, M., Cernadas, E., Barro, S., and Amorim, D.  Do we need hundreds of classifiers to solve real world classification problems?  _Journal of Machine Learning Research_ , 15(1):3133–3181, 2014.
  * Hsieh et al. (2008) Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, S. S., and Sundararajan, S.  A dual coordinate descent method for large-scale linear SVM.  In _Proceedings of the 25th International Conference on Machine Learning_ , pp. 408–415, 2008.
  * Hsu & Lin (2002) Hsu, C.-W. and Lin, C.-J.  A comparison of methods for multiclass support vector machines.  _IEEE Transactions on Neural Networks_ , 13(2):415–425, 2002.
  * Hush et al. (2006) Hush, D., Kelly, P., Scovel, C., and Steinwart, I.  QP algorithms with guaranteed accuracy and run time for support vector machines.  _Journal of Machine Learning Research_ , 7(May):733–769, 2006.
  * Igel et al. (2008) Igel, C., Heidrich-Meisner, V., and Glasmachers, T.  Shark.  _Journal of Machine Learning Research_ , 9(Jun):993–996, 2008.
  * Joachims (2006) Joachims, T.  Training linear SVMs in linear time.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 217–226, 2006.
  * Keerthi et al. (2001) Keerthi, S. S., Shevade, S. K., Bhattacharyya, C., and Murthy, K. R. K.  Improvements to Platt’s SMO algorithm for SVM classifier design.  _Neural Computation_ , 13(3):637–649, 2001.
  * Keerthi et al. (2008) Keerthi, S. S., Sundararajan, S., Chang, K.-W., Hsieh, C.-J., and Lin, C.-J.  A sequential dual method for large scale multi-class linear SVMs.  In _Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 408–416, 2008.
  * Klambauer et al. (2017) Klambauer, G., Unterthiner, T., Mayr, A., and Hochreiter, S.  Self-normalizing neural networks.  In _Advances in Neural Information Processing Systems_ , pp. 971–980, 2017.
  * Lee & Chang (2019) Lee, C.-P. and Chang, K.-W.  Distributed block-diagonal approximation methods for regularized empirical risk minimization.  _Machine Learning_ , pp. 1–40, 2019.
  * Lee et al. (2004) Lee, Y., Lin, Y., and Wahba, G.  Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data.  _Journal of the American Statistical Association_ , 99(465):67–81, 2004.
  * Lin (2002) Lin, C.-J.  A formal analysis of stopping criteria of decomposition methods for support vector machines.  _IEEE Transactions on Neural Networks_ , 13(5):1045–1052, 2002.
  * List & Simon (2004) List, N. and Simon, H. U.  A general convergence theorem for the decomposition method.  In _International Conference on Computational Learning Theory_ , pp. 363–377. Springer, 2004.
  * List & Simon (2007) List, N. and Simon, H. U.  General polynomial time decomposition algorithms.  _Journal of Machine Learning Research_ , 8(Feb):303–321, 2007.
  * List & Simon (2009) List, N. and Simon, H. U.  SVM-optimization and steepest-descent line search.  In _Proceedings of the 22nd Annual Conference on Computational Learning Theory_ , 2009.
  * List et al. (2007) List, N., Hush, D., Scovel, C., and Steinwart, I.  Gaps in support vector optimization.  In _International Conference on Computational Learning Theory_ , pp. 336–348. Springer, 2007.
  * Luo & Tseng (1992) Luo, Z.-Q. and Tseng, P.  On the convergence of the coordinate descent method for convex differentiable minimization.  _Journal of Optimization Theory and Applications_ , 72(1):7–35, 1992.
  * Luo & Tseng (1993) Luo, Z.-Q. and Tseng, P.  Error bounds and convergence analysis of feasible descent methods: a general approach.  _Annals of Operations Research_ , 46(1):157–178, 1993.
  * Platt (1998) Platt, J.  Sequential minimal optimization: A fast algorithm for training support vector machines.  Technical report, 1998.
  * Schick & Schütze (2020) Schick, T. and Schütze, H.  It’s not just size that matters: Small language models are also few-shot learners.  _arXiv preprint arXiv:2009.07118_ , 2020.
  * Shalev-Shwartz et al. (2011) Shalev-Shwartz, S., Singer, Y., Srebro, N., and Cotter, A.  Pegasos: Primal estimated sub-gradient solver for SVM.  _Mathematical Programming_ , 127(1):3–30, 2011\.
  * Steinwart & Thomann (2017) Steinwart, I. and Thomann, P.  liquidSVM: A fast and versatile SVM package.  _arXiv preprint arXiv:1702.06899_ , 2017.
  * Steinwart et al. (2011) Steinwart, I., Hush, D., and Scovel, C.  Training SVMs without offset.  _Journal of Machine Learning Research_ , 12(1), 2011.
  * Torres-Barrán et al. (2021) Torres-Barrán, A., Alaíz, C. M., and Dorronsoro, J. R.  Faster SVM training via conjugate SMO.  _Pattern Recognition_ , 111:107644, 2021.  ISSN 0031-3203.
  * van den Burg & Groenen (2016) van den Burg, G. and Groenen, P.  Gensvm: A generalized multiclass support vector machine.  _The Journal of Machine Learning Research_ , 17(1):7964–8005, 2016.
  * Vapnik (1998) Vapnik, V.  Statistical learning theory, 1998.
  * Voglis & Lagaris (2004) Voglis, C. and Lagaris, I. E.  Boxcqp: An algorithm for bound constrained convex quadratic problems.  In _Proceedings of the 1st International Conference: From Scientific Computing to Computational Engineering, IC-SCCE, Athens, Greece_ , 2004\.
  * Wang & Lin (2014) Wang, P.-W. and Lin, C.-J.  Iteration complexity of feasible descent methods for convex optimization.  _The Journal of Machine Learning Research_ , 15(1):1523–1548, 2014.
  * Weston & Watkins (1999) Weston, J. and Watkins, C.  Support vector machines for multi-class pattern recognition.  In _Proc. 7th European Symposium on Artificial Neural Networks, 1999_ , 1999.

###  A.1 Regarding offsets

In this section, we review the literature on SVMs in particular with regard to
offsets.

For binary kernel SVMs, Steinwart et al. (2011) demonstrates that kernel SVMs
without offset achieve comparable classification accuracy as kernel SVMs with
offset. Furthermore, they propose algorithms that solve kernel SVMs without
offset that are significantly faster than solvers for kernel SVMs with offset.

For binary linear SVMs, Hsieh et al. (2008) introduced coordinate descent for
the dual problem associated to linear SVMs without offsets, or with the bias
term included in the $\mathbf{w}$ term. Chiu et al. (2020) studied whether the
method of Hsieh et al. (2008) can be extended to allow offsets, but found
evidence that the answer is negative. For multiclass linear SVMs, Keerthi et
al. (2008) studied block coordinate descent for the CS-SVM and WW-SVM, both
without offsets. We are not aware of a multiclass analogue to Chiu et al.
(2020) although the situation should be similar.

The previous paragraph discussed coordinate descent in relation to the offset.
Including the offset presents challenges to primal methods as well. In Section
6 of Shalev-Shwartz et al. (2011), the authors argue that including an
unregularized offset term in the primal objective leads to slower convergence
guarantee. Furthermore, Shalev-Shwartz et al. (2011) observed that including
an unregularized offset did not significantly change the classification
accuracy.

The original Crammer-Singer (CS) SVM was proposed without offsets (Crammer &
Singer, 2001). In Section VI of (Hsu & Lin, 2002), the authors show the CS-SVM
with offsets do _not_ perform better than CS-SVM without offsets. Furthermore,
CS-SVM with offsets requires twice as many iterations to converge than
without.

###  A.2 Proof of Proposition 3.2

Below, let $i\in[n]$ be arbitrary. First, we note that
$-\bm{\pi}^{\prime}=\begin{bmatrix}-\mathbb{1}^{\prime}\\\
\mathbf{I}_{k-1}\end{bmatrix}$ and so

$\bm{\pi}^{\prime}\beta_{i}=\begin{bmatrix}-\mathbb{1}^{\prime}\beta_{i}\\\
\beta_{i}\end{bmatrix}.$ (14)

Now, let $j\in[k]$, we have by 3 that

$[\alpha_{i}]_{j}=[-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}]_{j}=[-\bm{\pi}^{\prime}\beta_{i}]_{\bm{\sigma}_{y_{i}}(j)}.$
(15)

Note that if $j\neq y_{i}$, then $\bm{\sigma}_{y_{i}}(j)\neq 1$ and so
$[\alpha_{i}]_{j}=[-\bm{\pi}^{\prime}\beta_{i}]_{\bm{\sigma}_{y_{i}}(j)}=[\beta_{i}]_{\bm{\sigma}_{y_{i}}(j)-1}\in[0,C]$.
On the other hand, if $j=y_{i}$, then $\bm{\sigma}_{y_{i}}(y_{i})=1$ and
$[\alpha_{i}]_{y_{i}}=[-\bm{\pi}^{\prime}\beta_{i}]_{1}=-\mathbb{1}^{\prime}\beta_{i}=-\sum_{t\in[k-1]}[\beta_{i}]_{t}=-\sum_{t\in[k]:t\neq
y_{i}}[\beta_{i}]_{\bm{\sigma}_{y_{i}}(t)-1}=-\sum_{t\in[k]:t\neq
y_{i}}[\alpha_{i}]_{t}$. Thus, $\bm{\alpha}\in\mathcal{F}$. This proves that
$\Psi(\mathcal{G})\subseteq\mathcal{F}$.

Next, let us define another map $\Xi:\mathcal{F}\to\mathbb{R}^{(k-1)\times n}$
as follows: For each $\bm{\alpha}\in\mathcal{F}$, define
$\bm{\beta}:=\Xi(\bm{\alpha})$ block-wise by

$\beta_{i}:=\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}\alpha_{i})\in\mathbb{R}^{k-1}$

where

$\mathtt{proj}_{2:k}=\begin{bmatrix}\mathbb{0}&\mathbf{I}_{k-1}\end{bmatrix}\in\mathbb{R}^{(k-1)\times
k}.$

By construction, we have for each $j\in[k-1]$ that
$[\beta_{i}]_{j}=[\bm{\sigma}_{y_{i}}\alpha_{i}]_{j+1}=[\bm{\sigma}_{y_{i}}\alpha_{i}]_{j+1}=[\alpha_{i}]_{\bm{\sigma}_{y_{i}}(j+1)}$
Since $j+1\neq 1$ for any $j\in[k-1]$, we have that
$\bm{\sigma}_{y_{i}}(j+1)\neq y_{i}$ for any $j\in[k-1]$. Thus,
$[\beta_{i}]_{j}=[\alpha_{i}]_{\bm{\sigma}_{y_{i}}(j+1)}\in[0,C]$. This proves
that $\Xi(\mathcal{F})\subseteq\mathcal{G}$.

Next, we prove that for all $\bm{\alpha}\in\mathcal{F}$ and
$\bm{\beta}\in\mathcal{G}$, we have $\Xi(\Psi(\bm{\beta}))=\bm{\beta}$ and
$\Psi(\Xi(\bm{\alpha}))=\bm{\alpha}$.

By construction, the $i$-th block of $\Xi(\Psi(\bm{\beta}))$ is given by

$\displaystyle\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}(-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}))$
$\displaystyle=-\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i})$
$\displaystyle=-\mathtt{proj}_{2:k}(\bm{\pi}^{\prime}\beta_{i})$
$\displaystyle=-\begin{bmatrix}\mathbb{0}&\mathbf{I}_{k-1}\end{bmatrix}\begin{bmatrix}\mathbb{1}^{\prime}\\\
-\mathbf{I}_{k-1}\end{bmatrix}\beta_{i}$
$\displaystyle=\mathbf{I}_{k-1}\beta_{i}=\beta_{i}.$

For the second equality, we used the fact that
$\bm{\sigma}_{y}^{2}=\mathbf{I}$ for all $y\in[k]$. Thus,
$\Xi(\Psi(\bm{\beta}))=\bm{\beta}$.

Next, note that the $i$-th block of $\Psi(\Xi(\bm{\alpha}))$ is, by
construciton,

$-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}\alpha_{i})=-\bm{\sigma}_{y_{i}}\pi^{\prime}\begin{bmatrix}\mathbb{0}&\mathbf{I}_{k-1}\end{bmatrix}\bm{\sigma}_{y_{i}}\alpha_{i}=-\bm{\sigma}_{y_{i}}\begin{bmatrix}\mathbb{0}&\pi^{\prime}\end{bmatrix}\bm{\sigma}_{y_{i}}\alpha_{i}$
(16)

Recall that $\pi^{\prime}=\begin{bmatrix}\mathbb{1}^{\prime}\\\
-\mathbf{I}_{k-1}\end{bmatrix}$ and so
$\begin{bmatrix}\mathbb{0}&\pi^{\prime}\end{bmatrix}=\begin{bmatrix}0&\mathbb{1}^{\prime}\\\
\mathbb{0}&-\mathbf{I}_{k-1}\end{bmatrix}$. Therefore,

$\left[\begin{bmatrix}\mathbb{0}&\pi^{\prime}\end{bmatrix}\bm{\sigma}_{y_{i}}\alpha_{i}\right]_{1}=\sum_{j=2}^{k}[\bm{\sigma}_{y_{i}}\alpha_{i}]=\sum_{j\in[k]:j\neq
y_{i}}[\alpha_{i}]_{j}=-[\alpha_{i}]_{y_{i}}=-[\bm{\sigma}_{y_{i}}\alpha_{i}]_{1}$

and, for $j=2,\dots,k$,

$\left[\begin{bmatrix}\mathbb{0}&\pi^{\prime}\end{bmatrix}\bm{\sigma}_{y_{i}}\alpha_{i}\right]_{j}=-[\bm{\sigma}_{y_{i}}\alpha_{i}]_{j}.$

Hence, we have just shown that
$\begin{bmatrix}\mathbb{0}&\pi^{\prime}\end{bmatrix}\bm{\sigma}_{y_{i}}\alpha_{i}=-\bm{\sigma}_{y_{i}}\alpha_{i}$.
Continuing from 16, we have

$-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\mathtt{proj}_{2:k}(\bm{\sigma}_{y_{i}}\alpha_{i})=-\bm{\sigma}_{y_{i}}(-\bm{\sigma}_{y_{i}}\alpha_{i})=\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{i}}\alpha_{i}=\alpha_{i}.$

This proves that $\Psi(\Xi(\bm{\alpha}))=\bm{\alpha}$. Thus, we have shown
that $\Psi$ and $\Xi$ are inverses of one another. This proves that $\Psi$ is
a bijection.

Finally, we prove that

$f(\Psi(\bm{\beta}))=g(\bm{\beta}).$

Recall that

$f(\bm{\alpha}):=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\alpha_{i}^{\prime}\alpha_{s}-\sum_{i\in[k]}\sum_{\begin{subarray}{c}j\in[k]:\\\
j\neq y_{i}\end{subarray}}\alpha_{ij}$

Thus,

$\alpha_{i}^{\prime}\alpha_{s}=(-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i})^{\prime}(-\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s})=\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}^{\prime}\bm{\pi}^{\prime}\beta_{s}$

On the other hand, 3 implies that
$\bm{\sigma}_{y_{i}}\alpha_{i}=-\bm{\pi}^{\prime}\beta_{i}$. Hence

$\sum_{j\in[k]\setminus\\{y_{i}\\}}\alpha_{ij}=\sum_{j\in[k]:j\neq
1}[\alpha_{i}]_{\bm{\sigma}_{y_{i}}(j)}=\sum_{j\in[k]:j\neq
1}[\bm{\sigma}_{y_{i}}\alpha_{i}]_{j}=\sum_{j\in[k]:j\neq
1}[-\bm{\pi}^{\prime}\beta_{i}]_{j}=\sum_{j\in[k-1]}[\beta_{i}]_{j}=\mathbb{1}^{\prime}\beta_{i}.$

Thus,

$f(\bm{\alpha}):=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\alpha_{i}^{\prime}\alpha_{s}-\sum_{i\in[k]}\sum_{\begin{subarray}{c}j\in[k]:\\\
j\neq
y_{i}\end{subarray}}\alpha_{ij}=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}^{\prime}\bm{\pi}^{\prime}\beta_{s}-\sum_{i\in[k]}\mathbb{1}^{\prime}\beta_{i}=g(\bm{\beta})$

as desired. Finally, we note that $\bm{\sigma}_{y}=\bm{\sigma}_{y}^{\prime}$
for all $y\in[k]$. This concludes the proof of Proposition 3.2. ∎

###  A.3 Proof of Proposition 3.5

We prove the following lemma which essentially unpacks the succinct
Proposition 3.5:

######  Lemma A.1.

Recall the situation of Corollary 3.3: Let $\bm{\beta}\in\mathcal{G}$ and
$i\in[n]$. Let $\bm{\alpha}=\Psi(\bm{\beta})$. Consider

$\min_{\widehat{\bm{\beta}}\in\mathcal{G}}\,\,g(\widehat{\bm{\beta}})\,\,\mbox{such
that}\,\,\,\widehat{\beta}_{s}=\beta_{s},\,\forall s\in[n]\setminus\\{i\\}.$
(17)

Let $\mathbf{w}$ be as in 1, i.e.,
$\mathbf{w}=-\sum_{i\in[n]}x_{i}\alpha_{i}^{\prime}.$ Then a solution to 17 is
given by
$[\beta_{1},\dots,\beta_{i-1},\widetilde{\beta_{i}},\beta_{i+1},\dots,\beta_{n}]$
where $\widetilde{\beta_{i}}$ is a minimizer of

$\min_{\widehat{\beta}_{i}\in\mathbb{R}^{k-1}}\,\,\frac{1}{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}-\widehat{\beta}_{i}^{\prime}\left((\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i})/\|x_{i}\|_{2}^{2}+\bm{\Theta}\beta_{i}\right)\,\,\mbox{such
that}\,\,0\leq\widehat{\beta}_{i}\leq C.$

Furthermore, the above optimization has a unique minimizer which is equal to
the minimizer of 4 where

$v:=(\mathbb{1}-\bm{\rho}_{y_{i}}\bm{\pi}\mathbf{w}^{\prime}x_{i}+\bm{\Theta}\beta_{i}\|x_{i}\|_{2}^{2})/\|x_{i}\|_{2}^{2}$

and $\mathbf{w}$ is as in 1.

###### Proof.

First, we prove a simple identity:

$\bm{\pi}\bm{\pi}^{\prime}=\begin{bmatrix}\mathbb{1}&-\mathbf{I}_{k-1}\end{bmatrix}\begin{bmatrix}\mathbb{1}^{\prime}\\\
-\mathbf{I}_{k-1}\end{bmatrix}=\mathbf{I}+\mathbf{O}=\bm{\Theta}.$ (18)

Next, recall that by definition, we have

$g(\bm{\beta}):=\left(\frac{1}{2}\sum_{s,t\in[n]}x_{s}^{\prime}x_{t}\beta_{t}^{\prime}\bm{\pi}\bm{\sigma}_{y_{t}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}\right)-\left(\sum_{s\in[n]}\mathbb{1}^{\prime}\beta_{s}\right).$

Let us group the terms of $g(\bm{\beta})$ that depends on $\beta_{i}$:

$\displaystyle g(\bm{\beta})$
$\displaystyle=\frac{1}{2}x_{i}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}$
$\displaystyle\quad+\frac{1}{2}\sum_{s\in[n]:s\neq
i}x_{s}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}$
$\displaystyle\quad+\frac{1}{2}\sum_{t\in[n]:t\neq
i}x_{i}^{\prime}x_{t}\beta_{t}^{\prime}\bm{\pi}\bm{\sigma}_{y_{t}}\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}$
$\displaystyle\quad+\frac{1}{2}\sum_{s,t\in[n]}x_{s}^{\prime}x_{t}\beta_{t}^{\prime}\bm{\pi}\bm{\sigma}_{y_{t}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}-\sum_{s\in[n]}\mathbb{1}^{\prime}\beta_{s}$
$\displaystyle=\frac{1}{2}x_{i}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\Theta}\beta_{i}\qquad\because\bm{\sigma}_{y_{i}}^{2}=\mathbf{I}\mbox{
and }\lx@cref{creftype~refnum}{equation: pi pi transpose is Theta}$
$\displaystyle\quad+\sum_{s\in[n]:s\neq
i}x_{s}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}$
$\displaystyle\quad-\mathbb{1}^{\prime}\beta_{i}$
$\displaystyle\quad+\underbrace{\frac{1}{2}\sum_{s,t\in[n]}x_{s}^{\prime}x_{t}\beta_{t}^{\prime}\bm{\pi}\bm{\sigma}_{y_{t}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}-\sum_{s\in[n]:s\neq
i}\mathbb{1}^{\prime}\beta_{s}}_{=:C_{i}}$

where $C_{i}$ is a scalar quantity which does not depend on $\beta_{i}$. Thus,
plugging in $\widehat{\bm{\beta}}$, we have

$g(\widehat{\bm{\beta}})=\frac{1}{2}\|x_{i}\|_{2}^{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}+\sum_{s\in[n]:s\neq
i}x_{s}^{\prime}x_{i}\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}-\mathbb{1}^{\prime}\widehat{\beta}_{i}+C_{i}.$
(19)

Furthermore,

$\displaystyle\sum_{s\in[n]:s\neq
i}x_{s}^{\prime}x_{i}\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}$
$\displaystyle=\sum_{s\in[n]:s\neq
i}\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}x_{s}^{\prime}x_{i}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\left(\sum_{s\in[n]:s\neq
i}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}x_{s}^{\prime}\right)x_{i}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\left(-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}x_{i}^{\prime}+\sum_{s\in[n]}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}x_{s}^{\prime}\right)x_{i}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\left(-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}x_{i}^{\prime}-\sum_{s\in[n]}\alpha_{s}x_{s}^{\prime}\right)x_{i}\qquad\because\lx@cref{creftype~refnum}{equation:
beta alpha relation via transposition}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\left(-\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}x_{i}^{\prime}+\mathbf{w}^{\prime}\right)x_{i}\qquad\because\lx@cref{creftype~refnum}{equation:
primal-dual variable relation}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\left(-\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{i}}\bm{\pi}^{\prime}\beta_{i}\|x_{i}\|^{2}_{2}+\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}\right)$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\left(\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}-\bm{\pi}\bm{\pi}^{\prime}\beta_{i}\|x_{i}\|^{2}_{2}\right)\qquad\because\bm{\sigma}_{y_{i}}^{2}=\mathbf{I}$
$\displaystyle=\widehat{\beta}_{i}^{\prime}\left(\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}-\bm{\Theta}\beta_{i}\|x_{i}\|^{2}_{2}\right)\qquad\because\lx@cref{creftype~refnum}{equation:
pi pi transpose is Theta}$

Therefore, we have

$\displaystyle g(\widehat{\bm{\beta}})$
$\displaystyle=\frac{1}{2}\|x_{i}\|_{2}^{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}+\widehat{\beta}_{i}^{\prime}\left(\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}-\bm{\Theta}\beta_{i}\|x_{i}\|_{2}^{2}-\mathbb{1}\right)+C_{i}$
$\displaystyle=\frac{1}{2}\|x_{i}\|_{2}^{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}-\widehat{\beta}_{i}^{\prime}\left(\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}+\bm{\Theta}\beta_{i}\|x_{i}\|_{2}^{2}\right)+C_{i}$

Thus, 17 is equivalent to

$\displaystyle\min_{\widehat{\bm{\beta}}\in\mathcal{G}}\quad$
$\displaystyle\frac{1}{2}\|x_{i}\|_{2}^{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}-\widehat{\beta}_{i}^{\prime}\left(\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i}+\bm{\Theta}\beta_{i}\|x_{i}\|_{2}^{2}\right)+C_{i}$
$\displaystyle s.t.\quad$
$\displaystyle\,\widehat{\beta}_{s}=\beta_{s},\,\forall
s\in[n]\setminus\\{i\\}.$

Dropping the constant $C_{i}$ and dividing through by $\|x_{i}\|_{2}^{2}$ does
not change the minimizers. Hence, 17 has the same set of minimizers as

$\displaystyle\min_{\widehat{\bm{\beta}}\in\mathcal{G}}\quad$
$\displaystyle\frac{1}{2}\widehat{\beta}_{i}^{\prime}\bm{\Theta}\widehat{\beta}_{i}-\widehat{\beta}_{i}^{\prime}\left((\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i})/\|x_{i}\|_{2}^{2}+\bm{\Theta}\beta_{i}\right)$
$\displaystyle s.t.\quad$
$\displaystyle\,\widehat{\beta}_{s}=\beta_{s},\,\forall
s\in[n]\setminus\\{i\\}.$

Due to the equality constraints, the only free variable is
$\widehat{\beta}_{i}$. Note that the above optimization, when restricted to
$\widehat{\beta}_{i}$, is equivalent to the optimization 4 with

$v:=(\mathbb{1}-\bm{\pi}\bm{\sigma}_{y_{i}}\mathbf{w}^{\prime}x_{i})/\|x_{i}\|_{2}^{2}+\bm{\Theta}\beta_{i}$

and $\mathbf{w}$ is as in 1. The uniqueness of the minimizer is guaranteed by
Theorem 3.4. ∎

###  A.4 Global linear convergence

Wang & Lin (2014) established the global linear convergence of the so-called
_feasible descent method_ when applied to a certain class of problems. As an
application, they prove global linear convergence for coordinate descent for
solving the dual problem of the binary SVM with the hinge loss. Wang & Lin
(2014) considered optimization problems of the following form:

$\min_{x\in\mathcal{X}}f(x):=g(\mathbf{E}x)+b^{\prime}x$ (20)

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a function such that $\nabla f$ is
Lipschitz continuous, $\mathcal{X}\subseteq\mathbb{R}^{n}$ is a polyhedral
set, $\operatorname*{arg\,min}_{x\in\mathcal{X}}f(x)$ is nonempty,
$g:\mathbb{R}^{m}\to\mathbb{R}$ is a strongly convex function such that
$\nabla g$ is Lipschitz continuous, and $\mathbf{E}\in\mathbb{R}^{m\times n}$
and $b\in\mathbb{R}^{n}$ are fixed matrix and vector, respectively.

Below, let $\mathcal{P}_{\mathcal{X}}:\mathbb{R}^{n}\to\mathcal{X}$ denote the
orthogonal projection on $\mathcal{X}$.

######  Definition A.2.

In the context of 20, an iterative algorithm that produces a sequence
$\\{x^{0},x^{1},x^{2},\dots\\}\subseteq\mathcal{X}$ is a _feasible descent
method_ if there exists a sequence
$\\{\epsilon^{0},\epsilon^{1},\epsilon^{2},\dots\\}\subseteq\mathbb{R}^{n}$
such that for all $t\geq 0$

$\displaystyle x^{t+1}$
$\displaystyle=\mathcal{P}_{\mathcal{X}}\left(x^{t}-\nabla
f(x^{t})+{\epsilon}^{t}\right)$ (21) $\displaystyle\|{\epsilon}^{t}\|$
$\displaystyle\leq B\|x^{t}-x^{t+1}\|$ (22) $\displaystyle
f(x^{t})-f(x^{t+1})$ $\displaystyle\geq\Gamma\|x^{t}-x^{t+1}\|^{2}$ (23)

where $B,\Gamma>0$.

One of the main result of (Wang & Lin, 2014) is

######  Theorem A.3 (Theorem 8 from (Wang & Lin, 2014)).

Suppose an optimization problem $\min_{x\in\mathcal{X}}f(x)$ is of the form 20
and $\\{x^{0},x^{1},x^{2},\dots\\}\subseteq\mathcal{X}$ is a sequence
generated by a feasible descent method. Let
$f^{*}:=\min_{x\in\mathcal{X}}f(x)$. Then there exists $\Delta\in(0,1)$ such
that

$f(x^{t+1})-f^{*}\leq\Delta(f(x^{t})-f^{*}),\quad\forall t\geq 0.$

Now, we begin verifying that the WW-SVM dual optimization and the BCD
algorithm for WW-SVM satisfies the requirements of Theorem A.3.

Given $\bm{\beta}\in\mathbb{R}^{(k-1)\times n}$, define its vectorization

$\mathrm{vec}(\bm{\beta})=\begin{bmatrix}\beta_{1}\\\ \vdots\\\
\beta_{n}\end{bmatrix}\in\mathbb{R}^{(k-1)n}.$

Define the matrix
$\mathbf{P}_{is}=\bm{\pi}\bm{\sigma}_{y_{i}}x_{i}^{\prime}x_{s}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\in\mathbb{R}^{(k-1)\times(k-1)}$,
and $\mathbf{Q}\in\mathbb{R}^{(k-1)n\times(k-1)n}$ by

$\mathbf{Q}=\begin{bmatrix}\mathbf{P}_{11}&\mathbf{P}_{12}&\cdots&\mathbf{P}_{1n}\\\
\mathbf{P}_{21}&\mathbf{P}_{22}&\cdots&\mathbf{P}_{2n}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{P}_{n1}&\mathbf{P}_{n2}&\cdots&\mathbf{P}_{nn}\\\ \end{bmatrix}.$

Let

$\mathbf{E}=\begin{bmatrix}x_{1}\bm{\sigma}_{y_{1}}\bm{\pi}^{\prime}\\\
x_{2}\bm{\sigma}_{y_{2}}\bm{\pi}^{\prime}\\\ \vdots\\\
x_{n}\bm{\sigma}_{y_{n}}\bm{\pi}^{\prime}\\\ \end{bmatrix}.$

We observe that $\mathbf{Q}=\mathbf{E}^{\prime}\mathbf{E}$. Thus, $\mathbf{Q}$
is symmetric and positive semi-definite. Let $\|\mathbf{Q}\|_{op}$ be the
operator norm of $\mathbf{Q}$.

######  Proposition A.4.

The optimization D2 is of the form 20. More precisely, the optimization D2 can
be expressed as

$\min_{\bm{\beta}\in\mathcal{G}}\quad
g(\bm{\beta})=\varphi(\mathbf{E}\mathrm{vec}(\bm{\beta}))-\mathbb{1}^{\prime}\mathrm{vec}(\bm{\beta})$
(24)

where the feasible set $\mathcal{G}$ is a nonempty polyhedral set (i.e.,
defined by a system of linear inequalities, hence convex), $\varphi$ is
strongly convex, and $\nabla g$ is Lipschitz continuous with Lipschitz
constant $L:=\|\mathbf{Q}\|_{op}$. Furthermore, 24 has at least one minimizer.

###### Proof.

Observe

$\displaystyle g(\bm{\beta})$
$\displaystyle=\frac{1}{2}\sum_{i,s\in[n]}x_{s}^{\prime}x_{i}\beta_{i}^{\prime}\bm{\pi}\bm{\sigma}_{y_{i}}\bm{\sigma}_{y_{s}}\bm{\pi}^{\prime}\beta_{s}-\sum_{i\in[n]}\mathbb{1}^{\prime}\beta_{i}$
$\displaystyle=\frac{1}{2}\mathrm{vec}(\bm{\beta})^{\prime}\mathbf{Q}\mathrm{vec}(\bm{\beta})-\mathbb{1}^{\prime}\mathrm{vec}(\bm{\beta})$
$\displaystyle=\frac{1}{2}(\mathbf{E}\mathrm{vec}(\bm{\beta}))^{\prime}(\mathbf{E}\mathrm{vec}(\bm{\beta}))-\mathbb{1}^{\prime}\mathrm{vec}(\bm{\beta})$
$\displaystyle=\varphi(\mathbf{E}\mathrm{vec}(\bm{\beta}))-\mathbb{1}^{\prime}\mathrm{vec}(\bm{\beta})$

where $\varphi(\bullet)=\frac{1}{2}\|\bullet\|^{2}$. Note that
$\mathrm{vec}(\nabla
g(\bm{\beta}))=\mathbf{Q}\mathrm{vec}(\bm{\beta})-\mathbb{1}$. Hence, the
Lipschitz constant of $g$ is $\|\mathbf{Q}\|_{op}$. For the “Furthermore”
part, note that the above calculation shows that 24 is a quadratic program
where the second order term is positive semi-definite and the constraint set
is convex. Hence, 24 has at least one minimizer. ∎

Let $B=[0,C]^{k-1}$. Let $\bm{\beta}^{t}$ be $\bm{\beta}$ at the end of the
$t$-iteration of the outer loop of Algorithm 1. Define

$\bm{\beta}^{t,i}:=[\beta_{1}^{t+1},\cdots,\beta_{i}^{t+1},\beta_{i+1}^{t},\cdots,\beta_{n}^{t}].$

By construction, we have

$\beta^{t+1}_{i}=\operatorname*{arg\,min}_{\beta\in
B}g\left([\beta_{1}^{t+1},\cdots,\beta_{i-1}^{t+1},\beta,\beta_{i+1}^{t},\cdots,\beta_{n}^{t}]\right)$
(25)

For each $i=1,\dots,n$, let

$\nabla_{i}g(\bm{\beta})=\left[\frac{\partial
g}{\partial\beta_{1i}}(\bm{\beta}),\frac{\partial
g}{\partial\beta_{2i}}(\bm{\beta}),\dots,\frac{\partial
g}{\partial\beta_{(k-1)i}}(\bm{\beta})\right]^{\prime}.$

By Lemma 24 (Wang & Lin, 2014), we have

$\beta_{i}^{t+1}=\mathcal{P}_{B}(\beta_{i}^{t+1}-\nabla_{i}g(\bm{\beta}^{t,i}))$

where $\mathcal{P}_{B}$ denotes orthogonal projection on to $B$. Now, define
$\bm{\epsilon}^{t}\in\mathbb{R}^{(k-1)\times n}$ such that

$\epsilon_{i}^{t}=\beta_{i}^{t+1}-\beta_{i}^{t}-\nabla_{i}g(\bm{\beta}^{t,i})+\nabla_{i}g(\bm{\beta}^{t}).$

######  Proposition A.5.

The BCD algorithm for the WW-SVM is a feasible descent method. More precisely,
the sequence $\\{\bm{\beta}^{0},\bm{\beta}^{1},\dots\\}$ satisfies the
following conditions:

$\displaystyle\bm{\beta}^{t+1}$
$\displaystyle=\mathcal{P}_{\mathcal{G}}\left(\bm{\beta}^{t}-\nabla
g(\bm{\beta}^{t})+\bm{\epsilon}^{t}\right)$ (26)
$\displaystyle\|\bm{\epsilon}^{t}\|$
$\displaystyle\leq(1+\sqrt{n}L)\|\bm{\beta}^{t}-\bm{\beta}^{t+1}\|$ (27)
$\displaystyle g(\bm{\beta}^{t})-g(\bm{\beta}^{t+1})$
$\displaystyle\geq\Gamma\|\bm{\beta}^{t}-\bm{\beta}^{t+1}\|^{2}$ (28)

where $L$ is as in Proposition A.4,
$\Gamma:=\min_{i\in[n]}\frac{\|x_{i}\|^{2}}{2}$, $\mathcal{G}$ is the feasible
set of D2, and $\mathcal{P}_{\mathcal{G}}$ is the orthogonal projection onto
$\mathcal{G}$.

The proof of Proposition A.5 essentially generalizes Proposition 3.4 of (Luo &
Tseng, 1993) to the higher dimensional setting:

###### Proof.

Recall that $\mathcal{G}=B^{\times n}:=B\times\cdots\times B$. Note that the
$i$-th block of $\bm{\beta}^{t}-\nabla g(\bm{\beta}^{t})+\bm{\epsilon}^{t}$ is

${\beta}^{t}_{i}-\nabla_{i}g(\bm{\beta}^{t})+\epsilon_{i}^{t}={\beta}^{t}_{i}-\nabla_{i}g(\bm{\beta}^{t})+(\beta_{i}^{t+1}-\beta_{i}^{t}-\nabla_{i}g(\bm{\beta}^{t,i})+\nabla_{i}g(\bm{\beta}^{t}))=\beta_{i}^{t+1}-\nabla_{i}g(\bm{\beta}^{t,i}).$

Thus, the $i$-th block of $\mathcal{P}_{\mathcal{G}}(\bm{\beta}^{t}-\nabla
g(\bm{\beta}^{t})+\bm{\epsilon}^{t})$ is

$\mathcal{P}_{B}(\beta_{i}^{t+1}-\nabla_{i}g(\bm{\beta}^{t,i}))=\beta_{i}^{t+1}.$

This is precisely the identity 26.

Next, we have

$\displaystyle\|\epsilon^{t}_{i}\|$
$\displaystyle\leq\|\beta_{i}^{t+1}-\beta_{i}^{t}\|+\|\nabla_{i}g(\bm{\beta}^{t,i})-\nabla_{i}g(\bm{\beta}^{t})\|$
$\displaystyle\leq\|\beta_{i}^{t+1}-\beta_{i}^{t}\|+L\|\bm{\beta}^{t,i}-\bm{\beta}^{t}\|$
$\displaystyle\leq\|\beta_{i}^{t+1}-\beta_{i}^{t}\|+L\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|.$

From this, we get that

$\displaystyle\|\bm{\epsilon}^{t}\|$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\|\epsilon^{t}_{i}\|^{2}}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{n}(\|\beta_{i}^{t+1}-\beta_{i}^{t}\|+L\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|)^{2}}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{n}\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}}+\sqrt{\sum_{i=1}^{n}L^{2}\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|^{2}}$
$\displaystyle=\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|+\sqrt{n}L\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|$
$\displaystyle=(1+\sqrt{n}L)\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|.$

Thus, we conclude that
$\|\bm{\epsilon}^{t}\|\leq(1+\sqrt{n}L)\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|$
which is 27.

Finally, we show that

$g(\bm{\beta}^{t,i-1})-g(\bm{\beta}^{t,i})+\nabla_{i}g(\bm{\beta}^{t,i})^{\prime}(\beta_{i}^{t+1}-\beta_{i}^{t})\geq\Gamma\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}$

where $\Gamma:=\min_{i\in[n]}\frac{\|x_{i}\|^{2}}{2}$.

######  Lemma A.6.

Let
$\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}\in\mathbb{R}^{k-1}$
be arbitrary. Then there exist $v\in\mathbb{R}^{k-1}$ and $C\in\mathbb{R}$
which depend only on
$\beta_{1},\dots,\beta_{i-1},\beta_{i+1},\dots,\beta_{n}$, but not on $\beta$,
such that

$g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)=\frac{1}{2}\|x_{i}\|^{2}\beta^{\prime}\beta-v^{\prime}\beta-C.$

In particular, we have

$\nabla_{i}g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)=\|x_{i}\|^{2}\beta-v.$

###### Proof.

The result follows immediately from the identity 19. ∎

######  Lemma A.7.

Let
$\beta_{1},\cdots,\beta_{i-1},\beta,\eta,\beta_{i+1},\cdots,\beta_{n}\in\mathbb{R}^{k-1}$
be arbitrary. Then we have

$\displaystyle
g\left([\beta_{1},\cdots,\beta_{i-1},\eta,\beta_{i+1},\cdots,\beta_{n}]\right)-g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)$
$\displaystyle\qquad+\nabla_{i}g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)^{\prime}(\beta-\eta)$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}\|\eta-\beta\|^{2}$

###### Proof.

Let $v,C$ be as in Lemma A.6. We have

$\displaystyle
g\left([\beta_{1},\cdots,\beta_{i-1},\eta,\beta_{i+1},\cdots,\beta_{n}]\right)-g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}\|\eta\|^{2}-v^{\prime}\eta-\frac{\|x_{i}\|^{2}}{2}\|\beta\|^{2}+v^{\prime}\beta$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}(\|\eta\|^{2}-\|\beta\|^{2})+v^{\prime}(\beta-\eta)$

and

$\nabla_{i}g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)^{\prime}(\beta-\eta)=(\|x_{i}\|^{2}\beta-v)^{\prime}(\beta-\eta)=\|x_{i}\|^{2}(\|\beta\|^{2}-\beta^{\prime}\eta)-v^{\prime}(\beta-\eta).$

Thus,

$\displaystyle
g\left([\beta_{1},\cdots,\beta_{i-1},\eta,\beta_{i+1},\cdots,\beta_{n}]\right)-g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)$
$\displaystyle\qquad+\nabla_{i}g\left([\beta_{1},\cdots,\beta_{i-1},\beta,\beta_{i+1},\cdots,\beta_{n}]\right)^{\prime}(\beta-\eta)$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}(\|\eta\|^{2}-\|\beta\|^{2})+v^{\prime}(\beta-\eta)+\|x_{i}\|^{2}(\|\beta\|^{2}-\beta^{\prime}\eta)-v^{\prime}(\beta-\eta)$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}(\|\eta\|^{2}-\|\beta\|^{2})+\|x_{i}\|^{2}(\|\beta\|^{2}-\beta^{\prime}\eta)$
$\displaystyle=\|x_{i}\|^{2}\left(\frac{1}{2}(\|\eta\|^{2}-\|\beta\|^{2})+(\|\beta\|^{2}-\beta^{\prime}\eta)\right)$
$\displaystyle=\|x_{i}\|^{2}\left(\frac{1}{2}(\|\eta\|^{2}+\|\beta\|^{2})-\beta^{\prime}\eta\right)$
$\displaystyle=\frac{\|x_{i}\|^{2}}{2}\|\eta-\beta\|^{2}$

as desired. ∎

Applying Lemma A.7, we have

$g(\bm{\beta}^{t,i-1})-g(\bm{\beta}^{t,i})+\nabla_{i}g(\bm{\beta}^{t,i})^{\prime}(\beta_{i}^{t+1}-\beta_{i}^{t})\geq\frac{\|x_{i}\|^{2}}{2}\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}.$

Since 25 is true, we have by Lemma 24 of (Wang & Lin, 2014) that

$\nabla_{i}g(\bm{\beta}^{t,i})^{\prime}(\beta_{i}^{t}-\beta_{i}^{t+1})\geq 0$

Equivalently,
$\nabla_{i}g(\bm{\beta}^{t,i})^{\prime}(\beta_{i}^{t+1}-\beta_{i}^{t})\leq 0$.
Thus, we deduce that

$g(\bm{\beta}^{t,i-1})-g(\bm{\beta}^{t,i})\geq\frac{\|x_{i}\|^{2}}{2}\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}\geq\Gamma\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}$

Summing the above identity over $i\in[n]$, we have

$g(\bm{\beta}^{t,0})-g(\bm{\beta}^{t,n})=\sum_{i=1}^{n}g(\bm{\beta}^{t,i-1})-g(\bm{\beta}^{t,i})\geq\Gamma\sum_{i=1}^{n}\|\beta_{i}^{t+1}-\beta_{i}^{t}\|^{2}=\Gamma\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|^{2}$

Since $(\bm{\beta}^{t,0})=\bm{\beta}^{t}$ and
$\bm{\beta}^{t,n}=\bm{\beta}^{t+1}$, we conclude that
$g(\bm{\beta}^{t})-g(\bm{\beta}^{t+1})\geq\Gamma\|\bm{\beta}^{t+1}-\bm{\beta}^{t}\|^{2}.$
∎

To conclude the proof of Theorem 3.6, we note that Proposition A.5 and
Proposition A.4 together imply that the requirements of Theorem 8 from (Wang &
Lin, 2014) (restated as Theorem A.3 here) are satisfied for the BCD algorithm
for WW-SVM. Hence, we are done. ∎

###  A.5 Proof of Theorem 3.4

The goal of this section is to prove Theorem 3.4. The time complexity analysis
has been carried out at the end of Section 4 of the main article. Below, we
focus on the part of the theorem on the correctness of the output. Throughout
this section, $k\geq 2$, $C>0$ and $v\in\mathbb{R}^{k-1}$ are assumed to be
fixed. Additional variables used are summarized in Table 2.

Table 2: Variables used in Section A.5
Variable(s) | defined in | nota bene
---|---|---
$t$ | Algorithm 2 | iteration index
$\ell,\mathtt{vals},\delta_{t},\gamma_{t}$ |  Subroutine 3 |  $t\in[\ell]$ is an iteration index
$\mathtt{up},\mathtt{dn}$ |  Subroutine 3 | symbols
$\widetilde{b},\widetilde{\gamma},v_{\max}$ | Lemma A.9 |
$\langle 1\rangle,\dots,\langle k-1\rangle$ | Algorithm 2 |
$n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t},S^{t},\widehat{\gamma}^{t},\widehat{b}^{t}$ | Algorithm 2 |  $t\in[\ell]$ is an iteration index
$\llfloor k\rrfloor$, $I_{\mathfrak{u}}^{\gamma},I_{\mathfrak{m}}^{\gamma},n_{\mathfrak{u}}^{\gamma},n_{\mathfrak{m}}^{\gamma}$ | Definition A.10 |  $\gamma\in\mathbb{R}$ is a real number
$S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$, $\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$, $\widehat{b}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$ | Definition A.13 | $(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\llfloor k\rrfloor^{2}$
$\mathtt{vals}^{+}$ | Definition A.18 |
$\mathtt{u}(j),\mathtt{d}(j)$ | Definition A.19 |  $j\in[k-1]$ is an integer
$\mathtt{crit}_{1}$, $\mathtt{crit}_{2}$ | Definition A.20 |
$\mathtt{KKT\\_cond}()$ |  Subroutine 5 |

####  A.5.1 The clipping map

First, we recall the clipping map:

######  Definition A.8.

The _clipping map_ $\mathtt{clip}_{C}:\mathbb{R}^{k-1}\to[0,C]^{k-1}$ is the
function defined as follows: for $w\in\mathbb{R}^{k-1}$,
$[\mathtt{clip}_{C}(w)]_{i}:=\max\\{0,\min\\{C,w_{i}\\}\\}$.

######  Lemma A.9.

Let $v_{\max}=\max_{i\in[k-1]}v_{i}$. The optimization 4 has a unique global
minimum $\widetilde{b}$ satisfying the following:

  1. 1.

$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})$ for some
$\widetilde{\gamma}\in\mathbb{R}$

  2. 2.

$\widetilde{\gamma}=\sum_{i=1}^{k-1}\widetilde{b}_{i}$. In particular,
$\widetilde{\gamma}\geq 0$.

  3. 3.

If $v_{i}\leq 0$, then $\widetilde{b}_{i}=0$. In particular, if $v_{\max}\leq
0$, then $\widetilde{b}=\mathbb{0}$.

  4. 4.

If $v_{\max}>0$, then $0<\widetilde{\gamma}<v_{\max}$.

###### Proof.

We first prove part 1. The optimization 4 is a minimization over a convex
domain with strictly convex objective, and hence has a unique global minimum
$\widetilde{b}$. For each $i\in[k-1]$, let $\lambda_{i},\mu_{i}\in\mathbb{R}$
be the dual variables for the constraints $0\geq b_{i}-C$ and $0\geq-b_{i}$,
respectively. The Lagrangian for the optimization 4 is

$\mathcal{L}(b,\lambda,\mu)=\frac{1}{2}b^{\prime}(\mathbf{I}+\mathbf{O})b-v^{\prime}b+(b-C)^{\prime}\lambda+(-b)^{\prime}\mu.$

Thus, the stationarity (or gradient vanishing) condition is

$0=\nabla_{b}\mathcal{L}(b,\lambda,\mu)=(\mathbf{I}+\mathbf{O})b-v+\lambda-\mu.$

The KKT conditions are as follows:

for all $i\in[k-1]$, the following holds:
$\displaystyle[(\mathbf{I}+\mathbf{O})b]_{i}+\lambda_{i}-\mu_{i}$
$\displaystyle=v_{i}\quad\mbox{stationarity}$ (29) $\displaystyle C\geq b_{i}$
$\displaystyle\geq 0\quad\mbox{primal feasibility}$ (30)
$\displaystyle\lambda_{i}$ $\displaystyle\geq 0\quad\mbox{dual feasibility}$
(31) $\displaystyle\mu_{i}$ $\displaystyle\geq 0\quad\quad\mbox{{"}}$ (32)
$\displaystyle\lambda_{i}(C-b_{i})$ $\displaystyle=0\quad\mbox{complementary
slackness}$ (33) $\displaystyle\mu_{i}b_{i}$
$\displaystyle=0\quad\quad\mbox{{"}}$ (34)

29 to 34 are satisfied if and only if $b=\widetilde{b}$ is the global minimum.

Let $\widetilde{\gamma}\in\mathbb{R}$ be such that
$\widetilde{\gamma}\mathbb{1}=\mathbf{O}\widetilde{b}$. Note that by
definition, part 2 holds. Furthermore, 29 implies

$\widetilde{b}=v-\widetilde{\gamma}\mathbb{1}-\lambda+\mu.$ (35)

Below, fix some $i\in[k-1]$. Note that $\lambda_{i}$ or $\mu_{i}$ cannot both
be nonzero. Otherwise, 33 and 34 would imply that $C=\widetilde{b}_{i}=0$, a
contradiction. We claim the following:

  1. 1.

If $v_{i}-\widetilde{\gamma}\in[0,C]$, then $\lambda_{i}=\mu_{i}=0$ and
$\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}$.

  2. 2.

If $v_{i}-\widetilde{\gamma}>C$, then $\widetilde{b}_{i}=C$.

  3. 3.

$v_{i}-\widetilde{\gamma}<0$, then $\widetilde{b}_{i}=0$.

We prove the first claim. To this end, suppose
$v_{i}-\widetilde{\gamma}\in[0,C]$. We will show $\lambda_{i}=\mu_{i}=0$ by
contradiction. Suppose $\lambda_{i}>0$. Then we have $C=\widetilde{b}_{i}$ and
$\mu_{i}=0$. Now, 35 implies that
$C=\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}-\lambda_{i}$. However, we now
have $v_{i}-\widetilde{\gamma}-\lambda_{i}\leq C-\lambda_{i}<C$, a
contradiction. Thus, $\lambda_{i}=0$. Similarly, assuming $\mu_{i}>0$ implies

$0=\widetilde{b}_{i}=v_{i}-\lambda+\mu_{i}\geq 0+\mu_{i}>0,$

a contradiction. This proves the first claim.

Next, we prove the second claim. Note that

$C\geq\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}-\lambda_{i}+\mu_{i}>C-\lambda_{i}+\mu_{i}\implies
0>-\lambda_{i}+\mu_{i}\geq-\lambda_{i}.$

In particular, we have $\lambda_{i}>0$ which implies $C=\widetilde{b}_{i}$ by
complementary slackness.

Finally, we prove the third claim. Note that

$0\leq\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}-\lambda_{i}+\mu_{i}<-\lambda_{i}+\mu_{i}\leq\mu_{i}$

Thus, $\mu_{i}>0$ and so $0=\widetilde{b}_{i}$ by complementary slackness.
This proves that
$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})$, which
concludes the proof of part 1.

For part 2, note that $\widetilde{\gamma}=\sum_{i=1}^{k-1}\widetilde{b}_{i}$
holds by definition. The “in particular” portion follows immediately from
$\widetilde{b}\geq 0$.

We prove part 3 by contradiction. Suppose there exists $i\in[k-1]$ such that
$v_{i}\leq 0$ and $\widetilde{b}_{i}>0$. Thus, by 34, we have $\mu_{i}=0$. By
29, we have $b_{i}+\widetilde{\gamma}\leq
b_{i}+\widetilde{\gamma}+\lambda_{i}=v_{i}\leq 0$. Thus, we have
$-\widetilde{\gamma}\geq b_{i}>0$, or equivalently, $\widetilde{\gamma}<0$.
However, this contradicts part 2. Thus, $\widetilde{b}_{i}=0$ whenever
$v_{i}\leq 0$. The “ in particular” portion follows immediately from the
observation that $v_{\max}\leq 0$ implies that $v_{i}\leq 0$ for all
$i\in[k-1]$.

For part 4, we first prove that $\widetilde{\gamma}<v_{\max}$ by
contradiction. Suppose that $\widetilde{\gamma}\geq v_{\max}$. Then we have
$v-\widetilde{\gamma}\mathbb{1}\leq v-v_{\max}\mathbb{1}\leq\mathbb{0}$. Thus,
by part 1, we have
$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})=\mathbb{0}$.
By part 2, we must have that
$\widetilde{\gamma}=\sum_{i=1}^{k-1}\widetilde{b}_{i}=0$. However,
$\widetilde{\gamma}\geq v_{\max}>0$, which is a contradiction.

Finally, we prove that $\widetilde{\gamma}>0$ again by contradiction. Suppose
that $\widetilde{\gamma}=0$. Then part 2 and the fact that
$\widetilde{b}\geq\mathbb{0}$ implies that $\widetilde{b}=\mathbb{0}$.
However, by part 1, we have $\widetilde{b}=\mathtt{clip}_{C}(v)$. Now, let
$i^{*}$ be such that $v_{i^{*}}=v_{\max}$. This implies that
$\widetilde{b}_{i^{*}}=\mathtt{clip}_{C}(v_{\max})>0$, a contradiction. ∎

####  A.5.2 Recovering $\widetilde{\gamma}$ from discrete data

######  Definition A.10.

For $\gamma\in\mathbb{R}$, let
$b^{\gamma}:=\mathtt{clip}_{C}(v-{\gamma}\mathbb{1})\in\mathbb{R}^{k-1}$.
Define

$\displaystyle I_{\mathfrak{u}}^{\gamma}$
$\displaystyle:=\\{i\in[k-1]:b^{\gamma}_{i}=C\\}$ $\displaystyle
I_{\mathfrak{m}}^{\gamma}$
$\displaystyle:=\\{i\in[k-1]:b^{\gamma}_{i}\in(0,C)\\}$ $\displaystyle
n_{\mathfrak{u}}^{\gamma}$
$\displaystyle:=|I_{\mathfrak{u}}^{\gamma}|,\quad\mbox{ and }\quad
n_{\mathfrak{m}}^{\gamma}:=|n_{\mathfrak{m}}^{\gamma}|.$

Let $\llfloor k\rrfloor:=\\{0\\}\cup[k-1]$. Note that by definition,
$n_{\mathfrak{m}}^{\gamma},n_{\mathfrak{u}}^{\gamma}\in\llfloor k\rrfloor$.

Note that $I_{\mathfrak{u}}^{\gamma}$ and $I_{\mathfrak{m}}^{\gamma}$ are
determined by their cardinalities. This is because

$\displaystyle I_{\mathfrak{u}}^{\gamma}$ $\displaystyle=\\{\langle
1\rangle,\langle 2\rangle,\dots,\langle n_{\mathfrak{u}}^{\gamma}\rangle\\}$
$\displaystyle I_{\mathfrak{m}}^{\gamma}$ $\displaystyle=\\{\langle
n_{\mathfrak{u}}^{\gamma}+1\rangle,\langle
n_{\mathfrak{u}}^{\gamma}+2\rangle,\dots,\langle
n_{\mathfrak{u}}^{\gamma}+n_{\mathfrak{m}}^{\gamma}\rangle\\}.$

######  Definition A.11.

Define

$\mathtt{disc}^{+}:=\\{v_{i}:i\in[k-1],\,v_{i}>0\\}\cup\\{v_{i}-C:i\in[k-1],v_{i}-C>0\\}\cup\\{0\\}.$

Note that $\mathtt{disc}^{+}$ is slightly different from $\mathtt{disc}$ as
defined in the main text.

######  Lemma A.12.

Let $\gamma^{\prime},\gamma^{\prime\prime}\in\mathtt{disc}^{+}$ be such that
$\gamma\not\in\mathtt{disc}^{+}$ for all
$\gamma\in(\gamma^{\prime},\gamma^{\prime\prime})$. The functions

$\displaystyle(\gamma^{\prime},\gamma^{\prime\prime})\ni\gamma$
$\displaystyle\mapsto I_{\mathfrak{m}}^{\gamma}$
$\displaystyle(\gamma^{\prime},\gamma^{\prime\prime})\ni\gamma$
$\displaystyle\mapsto I_{\mathfrak{u}}^{\gamma}$

are constant.

###### Proof.

We first prove $I_{\mathfrak{m}}^{\lambda}=I_{\mathfrak{m}}^{\rho}$. Let
$\lambda,\rho\in(\gamma^{\prime},\gamma^{\prime\prime})$ be such that
$\lambda<\rho$. Assume for the sake of contradiction that
$I_{\mathfrak{m}}^{\lambda}\neq I_{\mathfrak{m}}^{\rho}$. Then either 1)
$i\in[k-1]$ such that $v_{i}-\lambda\in(0,C)$ but $v_{i}-\rho\not\in(0,C)$ or
2) $i\in[k-1]$ such that $v_{i}-\lambda\not\in(0,C)$ but $v_{i}-\rho\in(0,C)$.
This implies that there exists some $\gamma\in(\lambda,\rho)$ such that
$v_{i}-\gamma\in\\{0,C\\}$, or equivalently, $\gamma\in\\{v_{i},v_{i}-C\\}$.
Hence, $\gamma\in\mathtt{disc}^{+}$, which is a contradiction. Thus, for all
$\lambda,\rho\in(\gamma^{\prime},\gamma^{\prime\prime})$, we have
$I_{\mathfrak{m}}^{\lambda}=I_{\mathfrak{m}}^{\rho}$.

Next, we prove $I_{\mathfrak{u}}^{\lambda}=I_{\mathfrak{u}}^{\rho}$. Let
$\lambda,\rho\in(\gamma^{\prime},\gamma^{\prime\prime})$ be such that
$\lambda<\rho$. Assume for the sake of contradiction that
$I_{\mathfrak{u}}^{\lambda}\neq I_{\mathfrak{u}}^{\rho}$. Then either 1)
$i\in[k-1]$ such that $v_{i}-\lambda\geq C$ but $v_{i}-\rho<C$ or 2)
$i\in[k-1]$ such that $v_{i}-\lambda<C$ but $v_{i}-\rho\geq C$. This implies
that there exists some $\gamma\in(\lambda,\rho)$ such that $v_{i}-\gamma=C$,
or equivalently, $\gamma=v_{i}=C$. Hence, $\gamma\in\mathtt{disc}^{+}$, which
is a contradiction. Thus, for all
$\lambda,\rho\in(\gamma^{\prime},\gamma^{\prime\prime})$, we have
$I_{\mathfrak{u}}^{\lambda}=I_{\mathfrak{u}}^{\rho}$. ∎

######  Definition A.13.

For $(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\llfloor k\rrfloor^{2}$, define
$S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$,
$\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\in\mathbb{R}$ by

$\displaystyle S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\sum_{i=n_{\mathfrak{u}}+1}^{n_{\mathfrak{u}}+n_{\mathfrak{m}}}v_{\langle
i\rangle},$
$\displaystyle\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\left(C\cdot
n_{\mathfrak{u}}+S^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\right)/(n_{\mathfrak{m}}+1).$

Furthermore, define
$\widehat{b}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}\in\mathbb{R}^{k-1}$ such
that, for $i\in[k-1]$, the $\langle i\rangle$-th entry is

$\displaystyle\widehat{b}_{\langle
i\rangle}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$
$\displaystyle:=\begin{cases}C&:i\leq n_{\mathfrak{u}}\\\ v_{\langle
i\rangle}-\gamma^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}&:n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$

Below, recall $\ell$ as defined on Subroutine 3-line 2.

######  Lemma A.14.

Let $t\in[\ell]$. Let $n_{\mathfrak{m}}^{t}$, $n_{\mathfrak{u}}^{t}$, and
$\widehat{b}^{t}$ be as in the for loop of Algorithm 2. Then
$\widehat{\gamma}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}=\widehat{\gamma}^{t}$
and
$\widehat{b}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}=\widehat{b}^{t}$.

###### Proof.

It suffices to show that
$S^{t}=S^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$ where the former is
defined as in Algorithm 2 and the latter is defined as in Definition A.13. In
other words, it suffices to show that

$S^{t}=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t}<j\leq
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}}v_{\langle j\rangle}.$ (36)

We prove 36 by induction. The base case $t=0$ follows immediately due to the
initialization in Algorithm 2-line 4.

Now, suppose that 36 holds for $S^{t-1}$:

$S^{t-1}=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t-1}<j\leq
n_{\mathfrak{u}}^{t-1}+n_{\mathfrak{m}}^{t-1}}v_{\langle j\rangle}.$ (37)

Consider the first case that $\delta_{t}=\mathtt{up}$. Then we have
$n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}=n_{\mathfrak{u}}^{t-1}+n_{\mathfrak{m}}^{t-1}$
and $n_{\mathfrak{u}}^{t}=n_{\mathfrak{u}}^{t-1}+1$. Thus, we have

$\displaystyle S^{t}$ $\displaystyle=S^{t-1}-v_{\langle
n^{t-1}_{\mathfrak{u}}\rangle}\quad\because\mbox{Subroutine~{}\ref{algorithm:
update variables}-line~{}3,}$
$\displaystyle=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t-1}+1<j\leq
n_{\mathfrak{u}}^{t-1}+n_{\mathfrak{m}}^{t-1}}v_{\langle
j\rangle}\quad\because\lx@cref{creftype~refnum}{equation: induction step of Si
identity}$ $\displaystyle=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t}<j\leq
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}}v_{\langle j\rangle}$

which is exactly the desired identity in 36.

Consider the second case that $\delta_{t}=\mathtt{dn}$. Then we have
$n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}=n_{\mathfrak{u}}^{t-1}+n_{\mathfrak{m}}^{t-1}+1$
and $n_{\mathfrak{u}}^{t}=n_{\mathfrak{u}}^{t-1}$. Thus, we have

$\displaystyle S^{t}$ $\displaystyle=S^{t-1}+v_{\langle
n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}\rangle}\quad\because\mbox{Subroutine~{}\ref{algorithm:
update variables}-line~{}6,}$
$\displaystyle=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t-1}+1<j\leq
n_{\mathfrak{u}}^{t-1}+n_{\mathfrak{m}}^{t-1}+1}v_{\langle
j\rangle}\quad\because\lx@cref{creftype~refnum}{equation: induction step of Si
identity}$ $\displaystyle=\sum_{j\in[k-1]\,:\,n_{\mathfrak{u}}^{t}<j\leq
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}}v_{\langle j\rangle}$

which, again, is exactly the desired identity in 36. ∎

######  Lemma A.15.

Let $\widetilde{\gamma}$ be as in Lemma A.9. Then we have

$\widetilde{b}=\widehat{b}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}=\mathtt{clip}_{C}(v-\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}\mathbb{1}).$

###### Proof.

It suffices to prove that
$\widetilde{\gamma}=\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}$.
To this end, let $i\in[k-1]$. If $i\in I_{\mathfrak{m}}^{\widetilde{\gamma}}$,
then $\widetilde{b}_{i}=v_{i}-\widetilde{\gamma}$. If $i\in
I_{\mathfrak{u}}^{\widetilde{\gamma}}$, then $\widetilde{b}_{i}=C$. Otherwise,
$\widetilde{b}_{i}=0$. Thus

$\widetilde{\gamma}=\mathbb{1}^{\prime}\widetilde{b}=C\cdot
n_{\mathfrak{u}}^{\widetilde{\gamma}}+S^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}-\widetilde{\gamma}\cdot
n_{\mathfrak{m}}^{\widetilde{\gamma}}$

Solving for $\widetilde{\gamma}$, we have

$\widetilde{\gamma}=\left(C\cdot
n_{\mathfrak{u}}^{\widetilde{\gamma}}+S^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}\right)/(n_{\mathfrak{m}}^{\widetilde{\gamma}}+1)=\widehat{\gamma}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})},$

as desired. ∎

####  A.5.3 Checking the KKT conditions

######  Lemma A.16.

Let $(n_{\mathfrak{m}},n_{\mathfrak{u}})\in\llfloor k\rrfloor^{2}$. To
simplify notation, let $b:=\widehat{b}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$,
$\gamma:=\widehat{\gamma}^{(n_{\mathfrak{m}},n_{\mathfrak{u}})}$. We have
$\mathbf{O}b=\gamma\mathbb{1}$ and for all $i\in[k-1]$ that

$[(\mathbf{I}+\mathbf{O})b]_{\langle i\rangle}=\begin{cases}C+\gamma&:i\leq
n_{\mathfrak{u}}\\\ v_{\langle i\rangle}&:n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
\gamma&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$ (38)

Furthermore, $b$ satisfies the KKT conditions 29 to 34 if and only if, for all
$i\in[k-1]$,

$v_{\langle i\rangle}\begin{cases}\geq C+\gamma&:i\leq n_{\mathfrak{u}}\\\
\in[\gamma,C+\gamma]&:n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
\leq\gamma&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$ (39)

###### Proof.

First, we prove $\mathbf{O}b=\gamma\mathbb{1}$ which is equivalent to
$[\mathbf{O}b]_{j}=\gamma$ for all $j\in[k-1]$. This is a straightforward
calculation:

$\displaystyle[\mathbf{O}b]_{j}=\mathbb{1}^{\prime}b$
$\displaystyle=\sum_{i\in[k-1]}b_{\langle i\rangle}$
$\displaystyle=\sum_{i\in[k-1]\,:\,i\leq n_{\mathfrak{u}}}b_{\langle
i\rangle}+\sum_{i\in[k-1]\,:\,n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}}b_{\langle
i\rangle}+\sum_{i\in[k-1]\,:\,n_{\mathfrak{u}}+n_{\mathfrak{m}}<i}b_{\langle
i\rangle}$ $\displaystyle=\sum_{i\in[k-1]\,:\,i\leq
n_{\mathfrak{u}}}C+\sum_{i\in[k-1]\,:\,n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}}v_{\langle i\rangle}-\gamma$
$\displaystyle=C\cdot
n_{\mathfrak{u}}+S^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}-n_{\mathfrak{m}}\gamma$
$\displaystyle=\gamma.$

Since $[(\mathbf{I}+\mathbf{O})b]_{i}=[\mathbf{I}b]_{i}+[\mathbf{O}b]_{i}$,
the identity 38 now follows immediately.

Next, we prove the “Furthermore” part. First, we prove the “only if”
direction. By assumption, we have $b=\widetilde{b}$ and so
$\gamma=\widetilde{\gamma}$. Furthermore, from Lemma A.9 we have
$\widetilde{b}=\mathtt{clip}_{C}(v-\widetilde{\gamma}\mathbb{1})$ and so
$b=\mathtt{clip}_{C}(v-\gamma\mathbb{1})$. To proceed, recall that by
construction, we have

$b_{\langle i\rangle}=\begin{cases}C&:i\leq n_{\mathfrak{u}}\\\
v-\gamma&:n_{\mathfrak{u}}<i\leq n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i\end{cases}$

Thus, if $i\leq n_{\mathfrak{u}}$, then $C=b_{\langle
i\rangle}=[\mathtt{clip}_{C}(v-\gamma\mathbb{1})]_{\langle i\rangle}$ implies
that $v_{\langle i\rangle}-\gamma\geq C$. If $n_{\mathfrak{u}}<i\leq
n_{\mathfrak{u}}+n_{\mathfrak{m}}$, then $b_{\langle i\rangle}=v_{\langle
i\rangle}-\gamma$. Since $b_{j}\in[0,C]$ for all $j\in[k-1]$, we have in
particular that $v_{\langle i\rangle}-\gamma\in[0,C]$. Finally, if
$n_{\mathfrak{u}}+n_{\mathfrak{m}}<i$, then $0=b_{\langle
i\rangle}=[\mathtt{clip}_{C}(v-\gamma\mathbb{1})]_{\langle i\rangle}$ implies
that $v-\gamma\leq 0$. In summary,

$v_{\langle i\rangle}-\gamma\begin{cases}\geq C&:i\leq n_{\mathfrak{u}}\\\
\in[0,C]&:n_{\mathfrak{u}}<i\leq n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\ \leq
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$

Note that the above identity immediately implies 39.

Next, we prove the “if” direction. Using 38 and 39, we have

$[(\mathbf{I}+\mathbf{O})b]_{\langle i\rangle}-v_{\langle
i\rangle}\begin{cases}\leq 0&:i\leq n_{\mathfrak{u}}\\\
=0&:n_{\mathfrak{u}}<i\leq n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\ \geq
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$

For each $i\in[k-1]$, define $\lambda_{i},\mu_{i}\in\mathbb{R}$ where

$\lambda_{\langle i\rangle}=\begin{cases}-([(\mathbf{I}+\mathbf{O})b]_{\langle
i\rangle}-v_{\langle i\rangle})&:i\leq n_{\mathfrak{u}}\\\
0&:n_{\mathfrak{u}}<i\leq n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
0&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i\end{cases}$

and

$\mu_{\langle i\rangle}=\begin{cases}0&:i\leq n_{\mathfrak{u}}\\\
0&:n_{\mathfrak{u}}<i\leq n_{\mathfrak{u}}+n_{\mathfrak{m}}\\\
[(\mathbf{I}+\mathbf{O})b]_{\langle i\rangle}-v_{\langle
i\rangle}&:n_{\mathfrak{u}}+n_{\mathfrak{m}}<i.\end{cases}$

It is straightforward to verify that all of 29 to 34 are satisfied for all
$i\in[k-1]$, i.e., the KKT conditions hold at $b$. ∎

Recall that we use indices with angle brackets $\langle 1\rangle,\langle
2\rangle,\dots,\langle k-1\rangle$ to denote a fixed permutation of $[k-1]$
such that

$v_{\langle 1\rangle}\geq v_{\langle 2\rangle}\geq\dots\geq v_{\langle
k-1\rangle}.$

######  Corollary A.17.

Let $t\in[\ell]$ and $\widetilde{b}$ be the unique global minimum of the
optimization 4. Then $\widehat{b}^{t}=\widetilde{b}$ if and only if
$\mathtt{KKT\\_cond}()$ returns true during the $t$-th iteration of Algorithm
2.

###### Proof.

First, by Lemma A.9 we have $\widehat{b}^{t}=\widetilde{b}$ if and only if
$\widehat{b}^{t}$ satisfies the KKT conditions 29 to 34. From Lemma A.14, we
have
$\widehat{b}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}=\widehat{b}^{t}$
and
$\widehat{\gamma}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}=\widehat{\gamma}^{t}$.
To simplify notation, let
$\gamma=\widehat{\gamma}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$. By
Lemma A.16, $\widehat{b}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}$
satisfies the KKT conditions 29 to 34 if and only if the following are true:

$v_{\langle i\rangle}\begin{cases}\geq C+\gamma&:i\leq n_{\mathfrak{u}}^{t}\\\
\in[\gamma,C+\gamma]&:n_{\mathfrak{u}}^{t}<i\leq
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\\\
\leq\gamma&:n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}<i.\end{cases}$

Since $v_{\langle 1\rangle}\geq v_{\langle 2\rangle}\geq\cdots$, the above
system of inequalities holds for all $i\in[k-1]$ if and only if

$\begin{cases}C+\gamma\leq v_{\langle n^{t}_{\mathfrak{u}}\rangle}&:\mbox{if
$n^{t}_{\mathfrak{u}}>0$.}\\\ \gamma\leq v_{\langle
n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}\rangle}\mbox{ and }v_{\langle
n^{t}_{\mathfrak{u}}+1\rangle}\leq C+\gamma&:\mbox{if
$n^{t}_{\mathfrak{m}}>0$,}\\\ v_{\langle
n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}+1\rangle}\leq\gamma&:\mbox{if
$n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}<k-1$.}\end{cases}$

Note that the above system holds if and only if $\mathtt{KKT\\_cond}()$
returns true. ∎

####  A.5.4 The variables $n_{\mathfrak{m}}^{t}$ and $n_{\mathfrak{u}}^{t}$

######  Definition A.18.

Define the set
$\mathtt{vals}^{+}=\\{(v_{j},\mathtt{dn},j):v_{j}>0,\,j=1,\dots,k-1\\}\,\,\cup\,\,\\{(v_{j}-C,\mathtt{up},j):v_{j}>C,\,j=1,\dots,k-1\\}$.
Sort the set
$\mathtt{vals}^{+}=\\{(\gamma_{1},\delta_{1},j_{1}),\dots,(\gamma_{\ell},\delta_{\ell},j_{\ell})\\}$
so that the ordering of
$\\{(\gamma_{1},\delta_{1}),\dots,(\gamma_{\ell},\delta_{\ell})\\}$ is
identical to $\mathtt{vals}$ from Subroutine 3-line 2.

To illustrate the definitions, we consider the following running example

$\setcounter{MaxMatrixCols}{12}\begin{matrix}\langle j\rangle&=&\langle
1\rangle&\langle 2\rangle&\langle 3\rangle&\langle 4\rangle&\langle
5\rangle&\langle 6\rangle&\langle 7\rangle&\langle 8\rangle&\langle
9\rangle&\langle 10\rangle\\\ \hline\cr v_{\langle
j\rangle}&=&1.8&1.4&1.4&1.4&1.2&0.7&0.4&0.4&0.1&-0.2\end{matrix}$
$\setcounter{MaxMatrixCols}{16}\begin{matrix}t&=&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\
\hline\cr\gamma_{t}&=&1.8&1.4&1.4&1.4&1.2&0.8&0.7&0.4&0.4&0.4&0.4&0.4&0.2&0.1\\\
\delta_{t}&=&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}&\mathtt{up}&\mathtt{up}&\mathtt{up}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}\end{matrix}$

######  Definition A.19.

Define

$\mathtt{u}(j):=\max\\{\tau\in[\ell]:v_{\langle
j\rangle}-C=\gamma_{\tau}\\},\quad\mbox{and}\quad\mathtt{d}(j):=\max\\{\tau\in[\ell]:v_{\langle
j\rangle}=\gamma_{\tau}\\},$ (40)

where $\max\emptyset=\ell+1$.

Below, we compute $\mathtt{d}(3),\mathtt{d}(6)$ and $\mathtt{u}(3)$ for our
running example.

$\setcounter{MaxMatrixCols}{16}\begin{matrix}&&&&&\mathtt{d}(3)&&&\mathtt{d}(6)&&&&&\mathtt{u}(3)&&\\\
&&&&&\downarrow&&&\downarrow&&&&&\downarrow&&\\\
t&=&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\
\hline\cr\gamma_{t}&=&1.8&1.4&1.4&1.4&1.2&0.8&0.7&0.4&0.4&0.4&0.4&0.4&0.2&0.1\\\
\delta_{t}&=&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}&\mathtt{up}&\mathtt{up}&\mathtt{up}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}\end{matrix}$

######  Definition A.20.

Define the following sets

$\displaystyle\mathtt{crit}_{1}(v)$
$\displaystyle=\\{\tau\in[\ell]:\gamma_{\tau}>\gamma_{\tau+1}\\}$
$\displaystyle\mathtt{crit}_{2}(v)$
$\displaystyle=\\{\tau\in[\ell]:\gamma_{\tau}=\gamma_{\tau+1},\,\delta_{\tau}=\mathtt{up},\,\delta_{\tau+1}=\mathtt{dn}\\}$

where $\gamma_{\ell+1}=0$.

Below, we illustrate the definition in our running example. The arrows
$\downarrow$ and $\Downarrow$ point to elements of $\mathtt{crit}_{1}(v)$ and
$\mathtt{crit}_{2}(v)$, respectively.

$\setcounter{MaxMatrixCols}{16}\begin{matrix}&&\downarrow&&&\downarrow&\downarrow&\downarrow&\downarrow&&&\Downarrow&&\downarrow&\downarrow&\downarrow\\\
t&=&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\
\hline\cr\gamma_{t}&=&1.8&1.4&1.4&1.4&1.2&0.8&0.7&0.4&0.4&0.4&0.4&0.4&0.2&0.1\\\
\delta_{t}&=&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}&\mathtt{up}&\mathtt{up}&\mathtt{up}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}\end{matrix}$

Later, we will show that Algorithm 2 will halt and output the global optimizer
$\widetilde{b}$ on or before the $t$-th iteration where
$t\in\mathtt{crit}_{1}(v)\cup\mathtt{crit}_{2}(v)$.

######  Lemma A.21.

Suppose that $t\in\mathtt{crit}_{1}(v)$. Then

$\\#\\{j\in[k-1]:\mathtt{d}(j)\leq
t\\}=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{dn}\\},\quad\mbox{ and
}\quad\\#\\{j\in[k-1]:\mathtt{u}(j)\leq
t\\}=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}.$

###### Proof.

First, we observe that

$\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}=\\#\\{(\gamma,\delta,j^{\prime})\in\mathtt{vals}^{+}:\delta=\mathtt{up},\,\gamma\geq\gamma_{t}\\}$

Next, note that $j\mapsto(\gamma_{\mathtt{d}(j)},\mathtt{up},\langle
j\rangle)$ is a bijection from $\\{j\in[k-1]:\mathtt{d}(j)\leq t\\}$ to
$\\{(\gamma,\delta,j^{\prime})\in\mathtt{vals}^{+}:\delta=\mathtt{up},\,\gamma\geq\gamma_{t}\\}$.
To see this, we view the permutation $\langle 1\rangle,\langle 2\rangle,\dots$
viewed as a bijective mapping $\langle\cdot\rangle:[k-1]\to[k-1]$ given by
$j\mapsto\langle j\rangle$. Denote by $\rangle\cdot\langle$ the inverse of
$\langle\cdot\rangle$. Then the (two-sided) inverse to
$j\mapsto(\gamma_{\mathtt{d}(j)},\mathtt{up},\langle j\rangle)$ is clearly
given by $(\gamma,\mathtt{up},j^{\prime})\mapsto\rangle j^{\prime}\langle$.
This proves the first identity of the lemma.

The proof of the second identity is completely analogous. ∎

######  Lemma A.22.

The functions $\mathtt{u}$ and $\mathtt{d}:[k-1]\to[\ell+1]$ are non-
decreasing. Furthermore, for all $j\in[k-1]$, we have
$\mathtt{u}(j)<\mathtt{d}(j)$.

###### Proof.

Let $j^{\prime},j^{\prime\prime}\in[k-1]$ be such that
$j^{\prime}<j^{\prime\prime}$. By the sorting, we have $v_{\langle
j^{\prime}\rangle}\geq v_{\langle j^{\prime\prime}\rangle}$. Now, suppose that
$\mathtt{d}(j^{\prime})>\mathtt{d}(j^{\prime\prime})$, then by construction we
have $\gamma_{\mathtt{d}(j^{\prime})}<\gamma_{\mathtt{d}(j^{\prime\prime})}$.
On the other hand, we have

$\gamma_{\mathtt{d}(j^{\prime})}=v_{\langle j^{\prime}\rangle}\geq v_{\langle
j^{\prime\prime}\rangle}=\gamma_{\mathtt{d}(j^{\prime\prime})}$

which is a contradiction.

For the “Furthermore” part, suppose the contrary that
$\mathtt{u}(j)\geq\mathtt{d}(j)$. Then we have
$\gamma_{\mathtt{u}(j)}\leq\gamma_{\mathtt{d}(j)}$. However, by definition, we
have $\gamma_{\mathtt{u}(j)}=v_{\langle j\rangle}>v_{\langle
j\rangle}-C=\gamma_{\mathtt{d}(j)}$. This is a contradiction. ∎

######  Lemma A.23.

Let $t\in\mathtt{crit}_{1}(v)$. Then
$n^{t}_{\mathfrak{u}}=\\#\\{j\in[k-1]:\mathtt{u}(j)\leq t\\}$. Furthermore,
$[n^{t}_{\mathfrak{u}}]=\\{j\in[k-1]:\mathtt{u}(j)\leq t\\}$. Equivalently,
for each $j\in[k-1]$, we have $j\leq n^{t}_{\mathfrak{u}}$ if and only if
$\mathtt{u}(j)\leq t$.

###### Proof.

First, we note that

$\displaystyle n^{t}_{\mathfrak{u}}$
$\displaystyle=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}\quad\because\mbox{Subroutine~{}\ref{algorithm:
update variables}-line~{}2}$ $\displaystyle=\\#\\{j\in[k-1]:\mathtt{u}(j)\leq
t\\}\quad\because\mbox{\lx@cref{creftype~refnum}{lemma: u d level set
cardinality identity}}$

This proves the first part. For the “Furthermore” part, let
$N:=\\#\\{j\in[k-1]:\mathtt{u}(j)\leq t\\}$. Since $\mathtt{u}$ is monotonic
non-decreasing (Lemma A.22), we have $\\{j\in[k-1]:\mathtt{u}(j)\leq
t\\}=[N].$ Since $N=n^{t}_{\mathfrak{u}}$ by the first part, we are done. ∎

######  Lemma A.24.

Let $\hat{t},\check{t}\in\mathtt{crit}_{1}(v)$ be such that there exists
$t\in[\ell]$ where

$n^{t}_{\mathfrak{m}}=\\#\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}-\\#\\{j\in[k-1]:\mathtt{u}(j)\leq\hat{t}\,\\}.$
(41)

Then $\mathtt{d}(j)\leq\check{t}$ and $\hat{t}<\mathtt{u}(j)$ if and only if
$n^{\hat{t}}_{\mathfrak{u}}<j\leq
n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}$.

###### Proof.

By Lemma A.23 and 41, we have
$\\#\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}=n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}$.
By Lemma A.22, $\mathtt{d}$ is monotonic non-decreasing and so
$[n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}]=\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}$.
Now,

$\displaystyle\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t},\,\hat{t}<\mathtt{u}(j)\\}$
$\displaystyle=\,$
$\displaystyle\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}\cap\\{j\in[k-1]:\hat{t}<\mathtt{u}(j)\\}$
$\displaystyle=\,$
$\displaystyle\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}\setminus\\{j\in[k-1]:\mathtt{u}(j)\leq\hat{t}\,\\}$
$\displaystyle=\,$
$\displaystyle[n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}]\setminus[n^{\hat{t}}_{\mathfrak{u}}],$

where in the last equality, we used Lemma A.23. ∎

######  Corollary A.25.

Let $t\in\mathtt{crit}_{1}(v)$. Then $\mathtt{d}(j)\leq t$ and
$t<\mathtt{u}(j)$ if and only if $n^{t}_{\mathfrak{u}}<j\leq
n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}$.

###### Proof.

We apply Lemma A.24 with $t=\hat{t}=\check{t}$, which requires checking that

$n^{t}_{\mathfrak{m}}=\\#\\{j\in[k-1]:\mathtt{d}(j)\leq
t\\}-\\#\\{j\in[k-1]:\mathtt{u}(j)\leq t\\}.$

This is true because from Subroutine 4-line 2 and 5, we have

$n^{t}_{\mathfrak{m}}=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{dn}\\}-\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}.$

Applying Lemma A.21, we are done. ∎

######  Lemma A.26.

Let $t\in\mathtt{crit}_{1}(v)$. Let $\varepsilon>0$ be such that for all
$\tau,\tau^{\prime}\in\mathtt{crit}_{1}(v)$ where $\tau^{\prime}<\tau$, we
have $\gamma_{\tau^{\prime}}-\varepsilon>\gamma_{\tau}$. Then
$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})=(n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon},n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon})$.

###### Proof.

We claim that

$v_{\langle
j\rangle}-\gamma_{t}+\varepsilon\begin{cases}<0&:t<\mathtt{d}(j)\\\
\in(0,C)&:\mathtt{d}(j)\leq t<\mathtt{u}(j)\\\ >C&:\mathtt{u}(j)\leq
t.\end{cases}$ (42)

To prove the $t<\mathtt{d}(j)$ case of 42, we have

$\displaystyle v_{\langle j\rangle}-\gamma_{t}+\varepsilon$
$\displaystyle=\gamma_{{\mathtt{d}(j)}}-\gamma_{t}+\varepsilon\quad\because\lx@cref{creftype~refnum}{equation:
definition of u(j) and d(j)}$
$\displaystyle<-\varepsilon+\varepsilon=0\quad\because\mbox{ $t<\mathtt{d}(j)$
implies that $\gamma_{t}-\varepsilon>\gamma_{{\mathtt{d}(j)}}$.}$

To prove the $\mathtt{d}(j)\leq t<\mathtt{u}(j)$ case of 42, we note that

$\displaystyle v_{\langle j\rangle}-\gamma_{t}+\varepsilon$
$\displaystyle=\gamma_{{\mathtt{d}(j)}}-\gamma_{t}+\varepsilon\quad\lx@cref{creftype~refnum}{equation:
definition of u(j) and d(j)}$
$\displaystyle\geq\varepsilon>0\quad\because\mbox{$\mathtt{d}(j)\leq t$
implies $\gamma_{{\mathtt{d}(j)}}\geq\gamma_{t}$.}$

For the other inequality,

$\displaystyle v_{\langle j\rangle}-\gamma_{t}+\varepsilon$
$\displaystyle=\gamma_{{\mathtt{u}(j)}}+C-\gamma_{t}+\varepsilon\quad\because\lx@cref{creftype~refnum}{equation:
definition of u(j) and d(j)}$
$\displaystyle<-\varepsilon+C+\varepsilon=C\quad\because\mbox{$t<\mathtt{u}(j)$
implies $\gamma_{t}-\varepsilon>\gamma_{{\mathtt{u}(j)}}$.}$

Finally, we prove the $\mathtt{u}(j)\leq t$ case of 42. Note that

$\displaystyle v_{\langle j\rangle}-\gamma_{t}+\varepsilon$
$\displaystyle=\gamma_{{\mathtt{u}(j)}}+C-\gamma_{t}+\varepsilon\quad\because\lx@cref{creftype~refnum}{equation:
definition of u(j) and d(j)}$ $\displaystyle\geq
C+\varepsilon>C\quad\because\mbox{$\mathtt{u}(j)\leq t$ implies that
$\gamma_{{\mathtt{u}(j)}}\geq\gamma_{t}$.}$

Thus, we have proven 42. By Lemma A.23 and Corollary A.25, 42 can be rewritten
as

$v_{\langle
j\rangle}-\gamma_{t}+\varepsilon\begin{cases}<0&:n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}<j,\\\
\in(0,C)&:n^{t}_{\mathfrak{u}}<j\leq
n^{t}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}},\\\ >C&:j\leq
n^{t}_{\mathfrak{u}}.\end{cases}$ (43)

Thus, we have $I_{\mathfrak{u}}^{\gamma_{t}-\varepsilon}=\\{\langle
1\rangle,\dots,\langle n_{\mathfrak{u}}^{t}\rangle\\}$ and
$I_{\mathfrak{m}}^{\gamma_{t}-\varepsilon}=\\{\langle
n_{\mathfrak{u}}^{t}+1\rangle,\dots,\langle
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\rangle\\}$. By the definitions of
$n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon}$ and
$n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon}$, we are done. ∎

######  Lemma A.27.

Let $t\in\mathtt{crit}_{2}(v)$. Then
$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})=(n_{\mathfrak{m}}^{\gamma_{t}},n_{\mathfrak{u}}^{\gamma_{t}})$.

###### Proof.

Let $\hat{t}\in\mathtt{crit}_{1}(v)$ be such that
$\gamma_{\hat{t}}=\gamma_{t}$, and
$\check{t}=\max\\{\tau\in\mathtt{crit}_{1}(v):\gamma_{\tau}>\gamma_{t}\\}$. We
claim that

$v_{\langle j\rangle}-\gamma_{\hat{t}}\begin{cases}\leq
0&:\check{t}<\mathtt{d}(j),\\\
\in(0,C)&:\mathtt{d}(j)\leq\check{t},\,\hat{t}<\mathtt{u}(j),\\\ \geq
C&:\mathtt{u}(j)\leq\hat{t}.\end{cases}$ (44)

Note that by definition, we have $\gamma_{\check{t}}>\gamma_{\hat{t}}$, which
implies that $\check{t}<\hat{t}$.

Consider the first case of 44 that $\check{t}<\mathtt{d}(j)$. See the running
example Figure 3. We have by construction that $v_{\langle
j\rangle}=\gamma_{\mathtt{d}(j)}$ and so $v_{\langle
j\rangle}-\gamma_{t}=\gamma_{\mathtt{d}(j)}-\gamma_{\check{t}}\leq 0.$

$\setcounter{MaxMatrixCols}{16}\begin{matrix}&&&&&&&&\check{t}&&&t&&\hat{t}&&\mathtt{d}(9)\\\
&&&&&&&&\downarrow&&&\Downarrow&&\downarrow&&\downarrow\\\
&&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\
\hline\cr\gamma_{t}&=&1.8&1.4&1.4&1.4&1.2&0.8&0.7&0.4&0.4&0.4&0.4&0.4&0.2&0.1\\\
\delta_{t}&=&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}&\mathtt{up}&\mathtt{up}&\mathtt{up}&\mathtt{dn}&\mathtt{dn}&\mathtt{up}&\mathtt{dn}\end{matrix}$
Figure 3: Example of a critical iterate type 2. The first case that
$\check{t}<\mathtt{d}(j)$ where $j=9$.

Next, consider the case when $\mathtt{d}(j)\leq\check{t}$ and
$\hat{t}<\mathtt{u}(j)$. Thus,

$\displaystyle v_{\langle j\rangle}-\gamma_{\hat{t}}$
$\displaystyle>v_{\langle
j\rangle}-\gamma_{\check{t}}\quad\because\gamma_{\check{t}}>\gamma_{t}$
$\displaystyle=\gamma_{\mathtt{d}(j)}-\gamma_{\check{t}}\quad\because\mbox{definition
of $\mathtt{d}(j)$}$ $\displaystyle\geq
0\quad\because\mathtt{d}(j)\leq\check{t}\implies\gamma_{\mathtt{d}(j)}\geq\gamma_{\check{t}}.$

On the other hand

$\displaystyle v_{\langle j\rangle}-\gamma_{\hat{t}}$
$\displaystyle=\gamma_{\mathtt{u}(j)}+C-\gamma_{\hat{t}}\quad\quad\because\mbox{definition
of $\mathtt{u}(j)$}$
$\displaystyle<C\quad\because\hat{t}<\mathtt{u}(j)\implies\gamma_{\hat{t}}>\gamma_{\mathtt{u}(j)}$

Thus, we’ve shown that in the second case, we have $v_{\langle
j\rangle}-\gamma_{\hat{t}}\in(0,C)$.

We consider the final case that $\mathtt{u}(j)\leq\hat{t}$. We have

$\displaystyle v_{\langle j\rangle}-\gamma_{\hat{t}}$
$\displaystyle=\gamma_{\mathtt{u}(j)}+C-\gamma_{\hat{t}}\quad\because\mbox{definition
of $t$}$ $\displaystyle\geq
C\quad\because\mathtt{u}(j)\leq\hat{t}\implies\gamma_{\mathtt{u}(j)}\geq\gamma_{\hat{t}}.$

Thus, we have proven 44.

Next, we claim that $t,\hat{t},\check{t}$ satisfy the condition 41 of Lemma
A.24, i.e.,

$n^{t}_{\mathfrak{m}}=\\#\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}-\\#\\{j\in[k-1]:\mathtt{u}(j)\leq\hat{t}\,\\}.$

To this end, we first recall that

$n^{t}_{\mathfrak{m}}=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{dn}\\}-\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}.$

By assumption on $t$, for all $\tau$ such that $\check{t}<\tau\leq t$, we have
$\delta_{\tau}=\mathtt{up}$. Thus,

$\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{dn}\\}=\\#\\{\tau\in[\check{t}\,]:\delta_{\tau}=\mathtt{dn}\\}=\\#\\{j\in[k-1]:\mathtt{d}(j)\leq\check{t}\,\\}$

where for the last equality, we used Lemma A.21. Similarly, for all $\tau$
such that $t<\tau\leq\hat{t}$, we have $\delta_{\tau}=\mathtt{dn}$. Thus, we
get that analogous result

$n^{t}_{\mathfrak{u}}=\\#\\{\tau\in[t]:\delta_{\tau}=\mathtt{up}\\}=\\#\\{\tau\in[\hat{t}\,]:\delta_{\tau}=\mathtt{up}\\}=\\#\\{j\in[k-1]:\mathtt{u}(j)\leq\hat{t}\,\\}=n^{\hat{t}}_{\mathfrak{u}}.$
(45)

Thus, we have verified the condition 41 of Lemma A.24. Now, applying Lemma
A.23 and Lemma A.24, we get

$v_{\langle j\rangle}-\gamma_{\hat{t}}\begin{cases}\leq
0&:n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}<j,\\\
\in(0,C)&:n^{\hat{t}}_{\mathfrak{u}}<j\leq
n^{\hat{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}\\\ \geq C&:j\leq
n^{\hat{t}}_{\mathfrak{u}}.\end{cases}$ (46)

By 45 and that $\gamma_{t}=\gamma_{\hat{t}}$, the above reduces to

$v_{\langle j\rangle}-\gamma_{{t}}\begin{cases}\leq
0&:n^{{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}<j,\\\
\in(0,C)&:n^{{t}}_{\mathfrak{u}}<j\leq
n^{{t}}_{\mathfrak{u}}+n^{t}_{\mathfrak{m}}\\\ \geq C&:j\leq
n^{{t}}_{\mathfrak{u}}.\end{cases}$ (47)

Thus, $I_{\mathfrak{u}}^{\gamma_{t}}=\\{\langle 1\rangle,\dots,\langle
n_{\mathfrak{u}}^{t}\rangle\\}$ and $I_{\mathfrak{m}}^{\gamma_{t}}=\\{\langle
n_{\mathfrak{u}}^{t}+1\rangle,\dots,\langle
n_{\mathfrak{u}}^{t}+n_{\mathfrak{m}}^{t}\rangle\\}$. By the definitions of
$n_{\mathfrak{u}}^{\gamma_{t}}$ and $n_{\mathfrak{m}}^{\gamma_{t}}$, we are
done. ∎

####  A.5.5 Putting it all together

If $v_{\max}\leq 0$, then Algorithm 2 returns $\mathbb{0}$.

Otherwise, by Lemma A.9, we have $\widetilde{\gamma}\in(0,v_{\max})$.

######  Lemma A.28.

Let $t\in[\ell]$ be such that
$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})=(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})$.
Then during the $t$-th loop of Algorithm 2 we have
$\widetilde{b}=\widehat{b}^{t}$ and $\mathtt{KKT\\_cond}()$ returns true.
Consequently, Algorithm 2 returns the optimizer $\widetilde{b}$ on or before
the $t$-th iteration.

###### Proof.

We have

$\displaystyle\widetilde{b}$
$\displaystyle=\widehat{b}^{(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})}\quad\because\mbox{
\lx@cref{creftype~refnum}{lemma: reco comp identity at optimality} }$
$\displaystyle=\widehat{b}^{(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})}\quad\because\mbox{Assumption}$
$\displaystyle=\widehat{b}^{t}\quad\because\mbox{
\lx@cref{creftype~refnum}{lemma: algorithm output and reco identity}. }$

Thus, by Corollary A.17 $\mathtt{KKT\\_cond}()$ returns true on the $t$-th
iteration. This means that Algorithm 2 halts on or before iteration $t$. Let
$\tau\in[\ell]$ be the iteration where Algorithm 2 halts and outputs
$\widehat{b}^{\tau}$. Then $\tau\leq t$. Furthermore, by Corollary A.17,
$\widehat{b}^{\tau}=\widetilde{b}$, which proves the “Consequently” part of
the lemma. ∎

By Lemma A.28, it suffices to show that
$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})=(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})$
for some $t\in[\ell]$.

We first consider the case when $\widetilde{\gamma}\neq\gamma_{t}$ for any
$t\in\mathtt{crit}_{1}(v)$. Thus, there exists $t\in\mathtt{crit}_{1}(v)$ such
that $\gamma_{t+1}<\widetilde{\gamma}<\gamma_{t}$, where we recall that
$\gamma_{\ell+1}:=0$.

Now, we return to the proof of Theorem 3.4.

$\displaystyle(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})$
$\displaystyle=(n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon},n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon})\quad\because\mbox{\lx@cref{creftype~refnum}{lemma:
realizability of type 1}}$
$\displaystyle=(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}})\quad\because\mbox{\lx@cref{creftype~refnum}{lemma:
comp is locally constant}, and that both $\widetilde{\gamma}$ and
$\gamma_{i}-\varepsilon\in(\gamma_{t+1},\gamma_{t})$}.$

Thus, Lemma A.28 implies the result of Theorem 3.4 under the assumption that
$\widetilde{\gamma}\neq\gamma_{t}$ for any $t\in\mathtt{crit}_{1}(v)$.

Next, we consider when $\widetilde{\gamma}=\gamma_{t}$ for some
$t\in\mathtt{crit}_{1}(v)$. There are three possibilities:

  1. 1.

There does not exist $j\in[k-1]$ such that $v_{\langle j\rangle}=\gamma_{t}$,

  2. 2.

There does not exist $j\in[k-1]$ such that $v_{\langle
j\rangle}-C=\gamma_{t}$,

  3. 3.

There exist $j_{1},j_{2}\in[k-1]$ such that $v_{\langle
j_{1}\rangle}=\gamma_{t}$ and $v_{\langle j_{2}\rangle}-C=\gamma_{t}$.

First, we consider case 1. We claim that

$(n_{\mathfrak{m}}^{\gamma_{t}},n_{\mathfrak{u}}^{\gamma_{t}})=(n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon^{\prime}},n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon^{\prime}})\quad\mbox{for
all $\varepsilon^{\prime}>0$ sufficiently small}.$ (48)

We first note that
$n_{\mathfrak{u}}^{\gamma_{t}}=n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon^{\prime}}$
for all $\varepsilon^{\prime}>0$ sufficiently small. To see this, let
$i\in[k-1]$ be arbitrary. Note that

$\displaystyle i\in I_{\mathfrak{u}}^{\gamma_{t}}\iff v_{i}-\gamma_{t}\geq C$
$\displaystyle\iff v_{i}-\gamma_{t}+\varepsilon^{\prime}\geq
C,\,\forall\epsilon^{\prime}>0,\mbox{ sufficiently small}$ $\displaystyle\iff
i\in
I_{\mathfrak{u}}^{\gamma_{t}-\varepsilon^{\prime}},\forall\epsilon^{\prime}>0,\mbox{
sufficiently small.}$

Next, we show that
$n_{\mathfrak{m}}^{\gamma_{t}}=n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon^{\prime}}$
for all $\varepsilon^{\prime}>0$ sufficiently small. To see this, let
$i\in[k-1]$ be arbitrary. Note that

$\displaystyle i\in I_{\mathfrak{m}}^{\gamma_{t}}\iff
v_{i}-\gamma_{t}\in(0,C)$
$\displaystyle\overset{\dagger}{\iff}v_{i}-\gamma_{t}+\varepsilon^{\prime}\in(0,C),\,\forall\epsilon^{\prime}>0,\mbox{
sufficiently small}$ $\displaystyle\iff i\in
I_{\mathfrak{m}}^{\gamma_{t}-\varepsilon^{\prime}},\forall\epsilon^{\prime}>0,\mbox{
sufficiently small}$

where at “$\overset{\dagger}{\iff}$”, we used the fact that
$v_{i}-\gamma_{t}\neq 0$ for any $i\in[k-1]$. Thus, we have proven 48. Taking
$\varepsilon^{\prime}>0$ so small so that both 48 and the condition in Lemma
A.26 hold, we have

$(n_{\mathfrak{m}}^{t},n_{\mathfrak{u}}^{t})=(n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon^{\prime}},n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon^{\prime}})=(n_{\mathfrak{m}}^{\gamma_{t}},n_{\mathfrak{u}}^{\gamma_{t}})=(n_{\mathfrak{m}}^{\widetilde{\gamma}},n_{\mathfrak{u}}^{\widetilde{\gamma}}).$

This proves Theorem 3.4 under case 1.

Next, we consider case 2. We claim that

$(n_{\mathfrak{m}}^{\gamma_{t}},n_{\mathfrak{u}}^{\gamma_{t}})=(n_{\mathfrak{m}}^{\gamma_{t}+\varepsilon^{\prime\prime}},n_{\mathfrak{u}}^{\gamma_{t}+\varepsilon^{\prime\prime}})\quad\mbox{for
all $\varepsilon^{\prime\prime}>0$ sufficiently small.}$ (49)

We first note that
$n_{\mathfrak{u}}^{\gamma_{t}}=n_{\mathfrak{u}}^{\gamma_{t}-\varepsilon^{\prime\prime}}$
for all $\varepsilon^{\prime\prime}>0$ sufficiently small. To see this, let
$i\in[k-1]$ be arbitrary. Note that

$\displaystyle i\in I_{\mathfrak{u}}^{\gamma_{t}}\iff v_{i}-\gamma_{t}\geq C$
$\displaystyle\overset{\ddagger}{\iff}v_{i}-\gamma_{t}-\varepsilon^{\prime\prime}\geq
C,\,\forall\epsilon^{\prime\prime}>0,\mbox{ sufficiently small}$
$\displaystyle\iff i\in
I_{\mathfrak{u}}^{\gamma_{t}+\varepsilon^{\prime\prime}},\forall\epsilon^{\prime\prime}>0,\mbox{
sufficiently small.}$

where at “$\overset{\ddagger}{\iff}$”, we used the fact that
$v_{i}-\gamma_{t}\neq C$ for any $i\in[k-1]$. Next, we show that
$n_{\mathfrak{m}}^{\gamma_{t}}=n_{\mathfrak{m}}^{\gamma_{t}-\varepsilon^{\prime\prime}}$
for all $\varepsilon^{\prime\prime}>0$ sufficiently small. To see this, let
$i\in[k-1]$ be arbitrary. Note that

$\displaystyle i\in I_{\mathfrak{m}}^{\gamma_{t}}\iff
v_{i}-\gamma_{t}\in(0,C)$
$\displaystyle\overset{\ddagger}{\iff}v_{i}-\gamma_{t}-\varepsilon^{\prime\prime}\in(0,C),\,\forall\epsilon^{\prime\prime}>0,\mbox{
sufficiently small}$ $\displaystyle\iff i\in
I_{\mathfrak{m}}^{\gamma_{t}+\varepsilon^{\prime\prime}},\forall\epsilon^{\prime\prime}>0,\mbox{
sufficiently small}$

where again at “$\overset{\ddagger}{\iff}$”, we used the fact that
$v_{i}-\gamma_{t}\neq C$ for any $i\in[k-1]$. Thus, we have proven 49. Since
$\widetilde{\gamma}=\gamma_{t}\in(0,v_{\max})$ and $\gamma_{1}=v_{\max}$, we
have in particular that $\gamma_{t}<\gamma_{1}$. Thus, there exists
$\tau\in\mathtt{crit}_{1}(v)$ such that $\tau<t$ and
$\gamma_{t}<\gamma_{\tau}$. Furthermore, we can choose $\tau$ such that for
all $\gamma\in(\gamma_{t},\gamma_{\tau})$,
$\gamma\not\in\mathtt{crit}_{1}(v)$. Let $\varepsilon^{\prime\prime}>0$ be so
small that
$\gamma_{t}+\varepsilon^{\prime\prime},\gamma_{\tau}-\varepsilon^{\prime\prime}\in(\gamma_{t},\gamma_{\tau})$,
and furthermore both 49 and the condition in Lemma A.26 hold. We have

$\displaystyle(n_{\mathfrak{m}}^{\tau},n_{\mathfrak{u}}^{\tau})$
$\displaystyle=(n_{\mathfrak{m}}^{\gamma_{\tau}-\varepsilon^{\prime\prime}},n_{\mathfrak{u}}^{\gamma_{\tau}-\varepsilon^{\prime\prime}})\quad\because\mbox{
\lx@cref{creftype~refnum}{lemma: realizability of type 1} }$
$\displaystyle=(n_{\mathfrak{m}}^{\gamma_{t}+\varepsilon^{\prime\prime}},n_{\mathfrak{u}}^{\gamma_{t}+\varepsilon^{\prime\prime}})\quad\because\mbox{
\lx@cref{creftype~refnum}{lemma: comp is locally constant} and