Taming Binarized Neural Networks and Mixed-Integer Programs
There has been a great deal of recent interest in binarized neural networks,
especially because of their explainability. At the same time, automatic
differentiation algorithms such as backpropagation fail for binarized neural
networks, which limits their applicability. By reformulating the problem of
training binarized neural networks as a subadditive dual of a mixed-integer
program, we show that binarized neural networks admit a tame representation.
This, in turn, makes it possible to use the framework of Bolte et al. for
implicit differentiation, which offers the possibility for practical
implementation of backpropagation in the context of binarized neural networks.
  This approach could also be used for a broader class of mixed-integer
programs, beyond the training of binarized neural networks, as encountered in
symbolic approaches to AI and beyond.
Johannes Aspman, Georgios Korpas, Jakub Marecek
# Taming Binarized Neural Networks

###### Abstract

There has been a great deal of recent interest in binarized neural networks, especially because of their explainability. At the same time, automatic differentiation algorithms such as backpropagation fail for binarized neural networks, which limits their applicability. By reformulating the problem of training binarized neural networks as a subadditive dual of a mixed-integer program, we show that binarized neural networks admit a tame representation. This, in turn, makes it possible to use the framework of Bolte et al. for implicit differentiation, which offers the possibility for practical implementation of backpropagation in the context of binarized neural networks. This approach could also be used for a broader class of mixed-integer programs, beyond the training of binarized neural networks, as encountered in symbolic approaches to AI and beyond.

## 1 Introduction

There has been a great deal of recent interest in binarized neural networks (BNNs) [1, 2, 3], due to their impressive statistical performance [4, e.g.], the ease of distributing the computation [1, 2, 5, e.g.], and especially their explainability. This latter property, which is rather rarely encountered in other types of neural networks, stems precisely from the binary representation of the weights and activation functions of the network, which can be seen as logical rules. This explainability is increasingly mandated by regulation of artificial intelligence, including the General Data Protection Regulation and the AI Act in the European Union, and the Blueprint for an AI Bill of Rights pioneered by the Office of Science and Technology Policy of the White House.

The training of BNNs typically utilizes the Straight-Through-Estimator (STE) [6, 2, 4, 7, 8, 9, 10, 11], which is challenging [12]. The challenge comes from the fact that the weight updates in the back-propagation do not correspond to subgradients of the forward paths [12].
To address this challenge, we draw a new relationship between binarized neural networks and so-called _tame geometry_[13] in this article. We introduce a certain reformulation of the training of BNN, which allows us to make use of the results of implicit differentiation and non-smooth optimization when training the BNNs [14, 15, 16, 17] and, eventually, to obtain weight updates in the back-propagation that do correspond to subgradients of the forward paths in common software frameworks built around automated differentiation, such as TensorFlow or PyTorch. This builds on a long history of work on _tame topology_ and _o-minimal structures_[18, 13, 19, 20, 21, 22, 23, 24, 25, e.g.], long studied in topology, logic, and functional analysis.

Our reformulation proceeds as follows: In theory, the training of BNNs can be cast as a mixed-integer program (MIP). We formulate its sub-additive dual, wherein we leverage the insight that conic MIPs admit a strong dual in terms of non-decreasing subadditive functions. We show that this dual problem is tame, or definable in an o-minimal structure. This, in turn, makes it possible for the use of powerful methods from non-smooth optimization when training the BNN, such as a certain generalized derivative of [15] that comes equipped with a chain rule. Thus, one can use backpropagation, as usual in training of neural networks.

In the process, we establish a broader class of _nice_ MIPs that admit such a tame reformulation. A MIP is nice if its feasible set is compact, and the graph of the objective function has only a finite number of non-differentiable points. This class could be of independent interest, as it may contain a number of other problems, such as learning causal graphs, optimal decision trees, or certain problems in symbolic regression. We hope that this could bring closer the symbolic approaches, which can often be cast as MIPs, and approaches based on neural networks and backpropagation.

## 2 Background

Let us start by introducing the relevant background material. We begin by introducing the relevant notions of BNNs, MIPs, and their subadditive dual. We discuss how the BNN can be recast as a MIP, and thus, by strong duality, how training the BNN relates to a maximization problem over a set of subadditive functions. Our main goal is to link the BNN with tame geometry, and therefore we discuss the relevant background on o-minimal structures. Finally, we discuss results on implicit differentiation for tame functions, which offers a practical way of training the BNN once we have established its tameness.

Binarized Neural NetworksThere is some ambiguity in the literature as to what constitutes a binarized neural network (BNN). We will follow [26] and refer to a BNN as a neural network where the activation functions take values in the binary set \(\{0,1\}\). A BNN is characterized by a vector \(L=(L_{0},\ldots,L_{n})\) with \(|L|=n\) layers where each layer contains \(L_{\ell}\in\mathbb{N}_{>0}\) neurons \(x_{i}^{(\ell)}\), see Fig. 1. We allow the input layer \(x_{i}^{(0)}\) to take any real values, \(x_{i}^{(0)}\in\mathbb{R}\), while due to binarized activations, the following layers will have \(x_{i}^{(j>0)}\in\{0,1\}\). The neuron \(x_{i}^{(\ell)}\) in the layer \(\ell\) is connected with the neuron \(x_{j}^{(\ell+1)}\) in the layer \(\ell+1\) via a weight coefficient matrix \(w^{(\ell)}\in\mathbb{R}^{L_{\ell}\times L_{\ell+1}}\). Consider an
input vector \(\mathbf{x}=(x_{1}^{(0)},\ldots,x_{L_{0}}^{(0)})\). The _preactivation function_ of the BNN is given as

\[a_{j}^{(\ell+1)}(\mathbf{x})=\sum_{i\in L_{\ell+1}}w_{ij}^{(\ell)}\sigma_{j}^{(\ell) }(\mathbf{x}), \tag{1}\]

where \(\sigma^{(\ell)}(\mathbf{x})\) is the _activation_ function at layer \(\ell\) with

\[\sigma_{j}^{(\ell)}(\mathbf{x})=\begin{cases}\mathbf{x}&\text{if }\ell=0,\\ 1&\text{if }\ell>0\text{ and }a_{j}^{(\ell)}(\mathbf{x})\geq\lambda_{\ell},\\ 0&\text{otherwise},\end{cases} \tag{2}\]

where \(\lambda_{\ell}\in\mathbb{R}\) is a learnable parameter. Note again that the activation functions of all the neurons in the network of our BNN are constrained in the set \(\{0,1\}\) except for the input layer neurons. This set can be mapped to \(\{-1,1\}\) by a redefinition \(\tilde{\sigma}_{j}^{(\ell)}=2\sigma_{j}^{(\ell)}-1\).

The BNN can be viewed as a weight assignment \(w=\{w^{(1)},\ldots,w^{(L)}\}\) for a function

\[f_{w}:\mathbb{R}^{L_{0}} \rightarrow\{-1,1\}^{L_{n}} \tag{3}\] \[\mathbf{x}^{(0)} \mapsto\hat{\mathbf{y}}, \tag{4}\]

where \(\hat{\mathbf{y}}=\mathbf{x}^{(L_{N})}\) is the vector of output layer neurons. BNNs are trained by finding an optimal weight assignment \(W\) that fits and generalizes a training set \(S=\{(\mathbf{x}_{1},\mathbf{y}_{1}),\ldots,(\mathbf{x}_{m},\mathbf{y}_{m})\}\). The traditional approaches of backpropagation and gradient descent methods in usual deep learning architectures cannot be used directly for training BNNs. For optimizers to work as in standard neural network architectures, real-valued weights are required, so, in practice, when binarized weights and/or activation functions are utilized, one still uses real-valued weights for the optimization step. Another problem is related to the use of deterministic functions (2) or stochastic functions [1] for binarization. During backpropagation, the derivative of these functions is zero, which flattens the gradient. A common solution to these problems is to use the Saturated STE (Straight Through Estimator) [27] (see also [28]). Other possible

Figure 1: A BNN with \(|L|=4\) layers, \(L=(2,3,3,2)\). Each \(x_{j}^{(\ell)}\), for all \(j\) and \(\ell\), is constrained to take values in \(\{-1,1\}\) while the activations represented by the edges joining the nodes take values in \(\{-1,0,1\}\).
solutions include the Expectation BackPropagation (EBP) algorithm [29] which is a popular approach to training multilayer neural networks with discretized weights, and Quantized BackPropagation (QBP) [30]. Ref. [12] presents a comprehensive practical survey on the training approaches for BNNs. In this article, we suggest that BNNs can be efficiently trained using nonsmooth implicit differentiation [16].

Mixed-Integer ProgrammingA mixed-integer (linear) program (MIP) is an optimization problem of the form

\[\begin{array}{ll}\max&cx+hy\\ \mathrm{s.t.}&Ax+Gy\leq b\\ &x\in\mathbb{Z}_{\geq 0}\\ &y\in\mathbb{R}_{\geq 0}.\end{array} \tag{5}\]

As illustrated in Figure 2, the feasible set is a subset of the intersection of a polyhedron with the integral grid.

Recasting a BNN as a MIPThe interactions and relations between BNNs and MILPs have been studied in recent literature. For example, in Ref. [31] BNNs with weights restricted to \(\{-1,1\}\) are trained by a hybrid method based on constraint programming and mixed-integer programming. Generally, BNNs with activation functions taking values in a binary set and with arbitrary weights can be reformulated as a MIP [26]. However, the precise form of the corresponding MIP depends on the nature of the loss function. Generally, a loss function for a BNN with \(n\) layers is a map

\[\mathscr{L}:\{0,1\}\times\mathbb{R}^{L_{n}}\to\mathbb{R}, \tag{6}\]

Figure 2: An illustrative example of a mixed-integer set as subset of \(\mathbb{Z}\times\mathbb{R}\). This is given as the feasible set of the MIP (5).
which allows the BNN to be represented as

\[\begin{array}{ll}\min&\sum_{i=1}^{m}\mathscr{L}\left(y_{i},\hat{y}_{i}\right) \\ \text{s.t.}&\hat{y}^{i}=a^{L}\left(w^{(L)}a^{(L-1)}\left(\ldots a^{(1)}\left(w^{ (1)}x_{i}\right)\ldots\right)\right)\\ &w^{(\ell)}\in\mathbb{R}^{L_{\ell}\times L_{\ell+1}},\quad\forall\ell\\ &\lambda_{k}\in\mathbb{R},\quad\forall\ell.\end{array} \tag{7}\]

The loss function \(\mathscr{L}\) can be chosen in different ways; for example the 0-1 loss function \(\mathscr{L}(\hat{y},y)=I_{\hat{y},y}\), where \(I\) is the indicator function, or the square loss \(\mathscr{L}(\hat{y},y)=\|\hat{y}-y\|^{2}\).

**Lemma 1** (Rephrasing Theorem 2 in [26]).: _Training BNNs admits a representation as a mixed-integer program. For the classification variant and empirical error as a loss function, the mixed-integer program is linear. For the regression variant and linearly-representable loss functions, the mixed-integer program is linear._

For the proof of Lemma 1, the authors of [26] that for any real-valued solution \(w=\{w^{(1)},\ldots,w^{(L)}\}\) with real-valued \(\lambda\) there exists a \([0,1]\)-valued redefinition of these variables such that the input of each neuron at each layer is the same. Therefore, we can consider weights \(w\) and parameters \(\lambda\) being \([0,1]\)-valued. Furthermore, certain constrains need to be applied so as to bound from above and below the output of each activated neuron. For simplicity, consider the case of a unique input vector \(x\equiv x^{(0)}\). Then, they define \(x^{(\ell)}\equiv u^{(\ell)}\) such that \(\hat{y}=u^{(L)}\). This yields the following formulation of the BNN as a non-linear MIP:

\[\begin{array}{ll}\min&\mathscr{L}(y,u^{(L)})\\ \text{s.t.}&w^{(1)}x<M_{1}u^{(1)}+\lambda_{1}\\ &w^{(1)}x\geq M_{1}(u^{(1)}-1)+\lambda_{1}\\ &w^{(\ell)}u^{\ell-1}<M_{\ell}u^{\ell}+\lambda_{\ell},\quad\forall\ell>1\\ &w^{(\ell)}u^{(\ell-1)}\geq M_{\ell}(u^{(\ell)}-1)+\lambda_{\ell},\quad\forall \ell>1\\ &w^{(\ell)}\in[-1,1]^{d_{\ell}\times d_{\ell-1}}\\ &\lambda_{\ell}\in[-1,1]\forall\ell\in[L]\\ &u^{(\ell)}\in\{0,1\}^{d_{\ell}}\quad\forall\ell\in[L]\end{array} \tag{8}\]

where \(M_{1}:=(nr+1)\), \(\|x\|<r\) a Euclidean norm bound, \(n\) the dimension of \(x\), and \(M_{\ell}:=(d_{\ell-1}+1)\). By linearizing the products \(w^{(\ell)}x^{(\ell-1)}\) through the introduction of extra variables \(s^{(\ell)}_{ij}\in[-1,1]\) we get a MILP formulation of the BNN.

**Theorem 1** (MILP, paraphrasing Theorem 2 of [26]).: _The BNN (7) can be recast as a
mixed-integer linear program, given by_

\[\min \sum_{i=1}^{m}\mathscr{L}\left(y,u^{(L)}\right)\] (9) s.t. \[w^{(1)}x^{i}<M_{1}u^{(1)}+\lambda_{1}\] \[w^{(1)}x^{i}\geq M_{1}\left(u^{(1)}-1\right)+\lambda_{1}\] \[\sum_{l=1}^{d_{k-1}}s_{l}^{(k)}<M_{k}u^{(k)}+\lambda_{k},\quad \forall k\in[L]\backslash\{1\}\] \[\sum_{l=1}^{d_{k-1}}s_{l}^{(k)}\geq M_{k}\left(u^{(k)}-1\right)+ \lambda_{k},\quad\forall k\in[L]\backslash\{1\}\] \[s_{lj}^{(k)}\leq u_{j}^{(k)},\quad s_{lj}^{(k)}\geq-u_{j}^{(k)},\] \[\forall k\in[L]\backslash\{1\},l\in[d_{k-1}]\,,j\in[d_{k}]\] \[s_{lj}^{(k)}\leq w_{lj}^{(k)}+\left(1-u_{j}^{(k)}\right),\] \[\forall k\in[L]\backslash\{1\},l\in[d_{k-1}]\,,j\in[d_{k}]\] \[W^{k}\in[-1,1]^{d_{k}\times d_{k-1}}\quad\forall k\in[L]\] \[\lambda_{k}\in[-1,1]\quad\forall k\in[L]\] \[u^{i,k}\in\{0,1\}^{d_{k}}\quad\forall k\in[L],i\in[m]\] \[s_{l}^{i,k}\in[-1,1]^{d_{k}}\quad\forall i\in[m],k\in[L] \backslash\{1\},l\in[d_{k-1}]\]

This gives the first step in our aim to link the theory of tame geometry, or o-minimality, to BNNs. The next step is to look at the dual problem of this MILP.

Subadditive dualIn the context of MIPs, the notion of duality is much more involved than in convex optimization. Only recently [32, 33], it is emerging that subadditive duals [34, 35, 36, 37, 38, 39] can be used to establish strong duality for MIPs. To introduce the subadditive dual, we use the modern language of [33, 32]:

**Definition 1** (Regular cone).: _A cone \(K\subseteq\mathbb{R}^{m}\) is called regular if it is closed, convex, pointed and full-dimensional._

If \(x-y\in K\), we write \(x\succeq_{K}y\) and similarily, if \(x\in\text{int}(K)\) we write \(x\succ_{K}0\).

**Definition 2** (Subadditive and non-decreasing functions).: _A function \(f\,:\,\mathbb{R}^{m}\to\mathbb{R}\) is called:_

* subadditive _if_ \(f(x+y)\leq f(x)+f(y)\) _for all_ \(x,y\in\mathbb{R}^{m}\)
* non-decreasing _with respect to a regular cone_ \(K\subseteq\mathbb{R}^{m}\) _if_ \(x\succeq_{K}y\implies f(x)\geq f(y)\)_._

The set of subadditive functions that are non-decreasing with respect to a regular cone \(K\subseteq\mathbb{R}^{m}\) is denoted \(\mathcal{F}_{K}\) and for \(f\in\mathcal{F}_{K}\) we further define \(\bar{f}(x)\coloneqq\limsup_{\delta\to 0^{+}}\frac{\bar{f}(\delta x)}{\delta}\). Note that this is the upper \(x\)-directional derivative of \(f\) at zero.

Let us start by stating the relation between subadditive functions and MIPs. To this end, we consider a generic conic MIP,

\[z^{*}\coloneqq \inf c^{T}x+d^{T}y, \tag{10}\] \[\text{s.t. }Ax+Gy\succeq_{K}b,\] \[x\in\mathbb{Z}^{n_{1}},\] \[y\in\mathbb{R}^{n_{2}}.\]

Note that problem (10) is a generalization of the primal form of a MILP, as in Thm. 1, which is recovered by setting \(K=\mathbb{R}^{m}_{+}\). We define the subadditive dual problem of (10) as

\[\rho^{*}\coloneqq \sup f(b), \tag{11}\] \[\text{s.t. }f(A^{j})=-f(-A^{j})=c_{j},\quad j=1,\ldots,n_{1},\] \[\bar{f}(G^{k})=-\bar{f}(-G^{k})=d_{k},\quad k=1,\ldots,n_{2},\] \[f(0)=0,\] \[f\in\mathcal{F}_{K},\]

where \(A^{j}\) and \(G^{j}\) denotes the \(j\)'th column of the matrices \(A\) and \(G\), respectively, and \(c_{j},d_{k}\) are the components of the corresponding vectors from the primal MIP.

In general, the subadditive dual (11) is a weak dual to the primal conic MIP (10), where any dual feasible solution provides a lower bound for the optimal value of the primal [40, 41, 33]. Under the assumptions of feasibility, strong duality holds:

**Theorem 2** (Theorem 3 of [32]).: _If the primal conic MIP (10) and the subadditive dual (11) are both feasible, then (11) is a strong dual of (10). Furthermore, if the primal problem is feasible, then the subadditive dual is feasible if and only if the conic dual of the continuous relaxation of (10) is feasible._

That is: Theorem 2 provides a sufficient condition for the subadditive dual to be equivalent to (10). A sufficient condition for the dual feasibility is that the conic MIP has a bounded feasible region.

Properties of subadditive functionsTo show our main result, Theorem 4, we will need to introduce some structural properties of subadditive functions. These are discussed in detail in [42, 43, 44]. For example, if \(f,g\) are two non-decreasing subadditive functions on \(\mathbb{R}^{m}\), then the following hold:

* \(f+g\) is subadditive;
* the composition \(g\circ f\) is subadditive;
* if further \(f\) is non-negative and \(g\) positive on the positive quadrant \(\mathbb{R}^{m}_{+}\) then \(f(x)g(x)\) is subadditive on \(\mathbb{R}^{m}_{+}\).

Let us note that, when we set \(K=\mathbb{R}^{m}_{+}\) in (11) we have that \(f(x)\) is non-negative on \(\mathbb{R}^{m}_{+}\) due to the combination of being non-decreasing, subadditive and having the condition \(f(0)=0\).

Following [44], we define properties NT (as in "no trumps") and WNT (for "weak no trumps"):

**Definition 3** (Nt, Def. 1 in [44]).: _For a family \((A_{k})_{k\in\mathbb{N}}\) of subsets of \(\mathbb{R}^{n}\) we say that \(\textbf{NT}(A_{k})\) holds, if for every bounded/convergent sequence \(\{a_{j}\}\) in \(\mathbb{R}^{n}\) some \(A_{k}\) contains a translate of a subsequence of \(\{a_{j}\}\)._

**Definition 4** (Wmt, Def. 2 in [44]).: _Let \(f\,:\,\mathbb{R}^{n}\to\mathbb{R}\). We call \(f\) a **WNT**-function, or \(f\in\textbf{WNT}\), if \(\textbf{NT}(\{F^{j}\}_{j\in\mathbb{N}^{*}})\) holds, where \(F^{j}\coloneqq\{x\in\mathbb{R}^{n}\,:\,|f(x)|<j\}\)._

We have the following theorem by Csiszar and Erdos [45], nicely explained in [46]:

**Theorem 3** (No trumps theorem, [45]).: _If \(T\) is an interval and \(T=\bigcup_{j\in\mathbb{N}^{*}}T_{j}\) with each \(T_{j}\) measurable/Baire, then \(\textbf{NT}(\{T_{k}\,:\,k\in\mathbb{N}^{*}\})\) holds._

Here, Baire refers to the functions having "the Baire property", or the set being open modulo some meager set. Note that this is not necessarily related to being definably Baire as in Def. 7.

The following properties are shown in [44]:

* If \(f\) is subadditive and locally bounded above at a point, then it is locally bounded at every point.
* If \(f\in\textbf{WNT}\) is subadditive, then it is locally bounded.
* If \(f\in\textbf{WNT}\) is subadditive and \(\inf_{t<0}f(tx)/t\) is finite for all \(x\), then \(f\) is Lipschitz.

Tame topologyThe subject of tame topology goes back to Grothendieck and his famous "Esquisse d'un programme" [18]. Grothendieck claimed that modern topology was riddled with false problems, which he ascribed to the fact that much of modern progress had been made by analysts. What he proposed was the invention of a geometers version of topology, lacking these artificial problems from the onset. In later years, this tame topology has been linked to the model theoretic concept of o-minimal structures, which promises to be a good candidates for Grothendieck's dream.

o-minimal structures are a generalisation of the (semi-)algebraic sets, or the sets of polynomial equations (and inequalities). As such they provide us with a large class of sets and functions that are in general non-smooth and non-convex, while capturing most (if not all) of the popular settings used in modern neural networks and machine learning [14].

An o-minimal structure over \(\mathbb{R}\) is a collection of subsets of \(\mathbb{R}^{m}\) that satisfies certain finiteness properties, such as closure under boolean operations, closure under projections and fibrations. Formally,
**Definition 5** (o-minimal structure).: _An o-minimal structure on \(\mathbb{R}\) is a sequence \(\mathcal{S}=(\mathcal{S}_{m})_{m\in\mathbb{N}}\) such that for each \(m\geq 1\):_

1. \(\mathcal{S}_{m}\) _is a boolean algebra of subsets of_ \(\mathbb{R}^{m}\)_;_
2. _if_ \(A\in\mathcal{S}_{m}\)_, then_ \(\mathbb{R}\times A\) _and_ \(A\times\mathbb{R}\) _belongs to_ \(\mathcal{S}_{m+1}\)_;_
3. \(\mathcal{S}_{m}\) _contains all diagonals, for example_ \(\{(x_{1},\ldots,x_{m})\in\mathbb{R}^{m}\,:\,x_{1}=x_{m}\}\in\mathcal{S}_{m}\)_;_
4. _if_ \(A\in\mathcal{S}_{m+1}\)_, then_ \(\pi(A)\in\mathcal{S}_{m}\)_;_
5. _the sets in_ \(\mathcal{S}_{1}\) _are exactly the finite unions of intervals and points._

Typically, we refer to a set included in an o-minimal structure as being _definable_ in that structure, and similarly, a function, \(f\,:\,\mathbb{R}^{m}\to\mathbb{R}^{n}\), is called definable in an o-minimal structure whenever its corresponding graph, \(\Gamma(f)=\{(x,y)\,|\,f(x)=y\}\subseteq\mathbb{R}^{m\times n}\), is definable. A set, or function, is called _tame_ to indicate that it is definable in some o-minimal structure, without specific reference to which structure.

The moderate sounding definition of o-minimal structures turns out to include many non-trivial examples. First of all, by construction we of course have that the collection of semialgebraic sets is an o-minimal structure, denoted \(\mathbb{R}_{\text{semialg}}\). If this was the only example of an o-minimal structure, it would not have been a very interesting construction. The research in o-minimal structures really took off in the middle of the nineties after Wilkie [47] proved that we can add the graph of the real exponential function, \(x\mapsto e^{x}\), to \(\mathbb{R}_{\text{semialg}}\) to again find an o-minimal structure, denoted \(\mathbb{R}_{\text{exp.}}\). As a result, the sigmoid function, which is a prevalent activation function in numerous neural networks, can be considered tame. Another important structure is found by including the set of restricted real analytic functions, where the domain of an analytic function is restricted to lie in a finite subset of the original domain in a particular way. This gives rise to an o-minimal structure denoted \(\mathbb{R}_{\text{an.}}\)[48]. A classical example of this would be the function \(\sin(x)\), where we restrict \(x\) to lie in a finite interval \(x\in[0,\alpha]\subset\mathbb{R}\) for some \(\alpha<\infty\). Note that without this restriction on the argument, \(\sin(x)\) is not tame. Furthermore, we can construct a very important o-minimal structure by combining \(\mathbb{R}_{\text{exp.}}\) with \(\mathbb{R}_{\text{an.}}\). This gives the structure denoted \(\mathbb{R}_{\text{an,exp.}}\)[48]. It is important to note that the fact that \(\mathbb{R}_{\text{an,exp.}}\) is an o-minimal structure is a non-trivial result. It does not generally hold that the combination of two o-minimal structures gives another o-minimal structure.

We thus see that o-minimal structures captures a very large class of, generally, non-smooth non-convex functions. More importantly, they include in principle all classes of functions widely used in modern machine learning applications. The great benefit of this class is that they are still _nice_ enough such that we can have some control over their behaviour and for example prove convergence to optimal points [49, 14, 15, 50, 51].

Perhaps the most fundamental results regarding o-minimal structures are the monotonicity and cell decomposition theorems. The former states that any tame function of one variable can be divided into a _finite_ union of open intervals, and points, such that it is continuous and either constant or strictly monotone on each interval. The cell decomposition theorem generalizes this to higher dimensions by introducing the concept of a cell, which is the analogue of the interval or point in one dimension. The theorem
then states that any tame function or set can be decomposed into a finite union of definable cells. A related notion is that of stratification of a set. Generally, a stratification is a way of partitioning a set into a collection of submanifolds called strata. There exists many different types of stratifications, characterized by how the different strata are joined together. Two important such conditions are given by the Whitney and Verdier stratifications. Both of these are applicable to tame sets [52, 53]. These results are at the core of many of the strong results on tame functions in non-smooth optimization.

Some more details on tame geometry and o-minimality are given in the supplementary material.

Locally o-minimal structuresThere exists a few variants of weakenings of the o-minimal structures. One such example is what is called _locally o-minimal structures_[21, 22, 23, 24, 25].

**Definition 6** (Locally o-minimal structure, [22]).: _A definably complete structure \(\mathbb{K}\) extending an ordered field is locally o-minimal if, for every definable function \(f:\mathbb{K}\to\mathbb{K}\), the sign of \(f\) is eventually constant._

Here, definably complete means that every definable subset of \(\mathbb{K}\) has a supremum in \(\mathbb{K}\sqcup\{\pm\infty\}\) and \(X\subseteq\mathbb{K}\) is nowhere dense if \(\text{Int}(\bar{X})\) is empty. Every o-minimal expansion of an ordered field is a definably complete structure (but the converse is not true). Note also that every o-minimal structure is locally o-minimal [22]. Locally o-minimal structures satisfy a property called _definably Baire_:

**Definition 7** (Definably Baire, from [24]).: _A definably complete structure \(\mathbb{K}\) expanding an ordered field is definably Baire if \(\mathbb{K}\) is not the union of a definable increasing family of nowhere dense subsets._

Finally, when we work with structures expanding \((\mathbb{R},+,\cdot,<)\) we have that local o-minimality implies o-minimality [23], while the same is generically not true when we do not have multiplication.

Non-smooth differentiationBolte et al., [15], introduced a generalized derivative, called a conservative set-valued field, for non-smooth functions. The main idea behind this construction is that the conservative fields come equipped with a chain rule. Namely, given a locally Lipschitz function \(f:\,\mathbb{R}^{m}\to\mathbb{R}\), we say that \(D:\,\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\) is a conservative field for \(f\) if and only if the function \(t\mapsto f(x(t))\) satisfies

\[\frac{\mathrm{d}}{\mathrm{d}t}f(x(t))=\langle v,\dot{x}(t)\rangle,\quad\forall v \in D(x(t)), \tag{12}\]

for any absolutely continuous curve \(x:\,[0,1]\to\mathbb{R}^{m}\) and for almost all \(t\in[0,1]\). Having a chain rule is key for applications to backpropagation algorithms and automatic differentiation in machine learning.

Automatic differentiation for non-smooth elementary functions is subtle and even the well-known Clarke generalized gradient is known to introduce complications in this setting. Having a derivative flexible enough to include automatic differentiation was therefore indeed the main motivation behind the work of Bolte et al. In many
ways, we can see the conservative fields as a generalization of the Clarke derivatives. More details are also provided in the supplementary material.

The conservative fields thus provide a flexible calculus for non-smooth differentiation that is applicable to many machine learning situations. In [16], a non-smooth implicit differentiation using the conservative Jacobians is developed. This can be seen as a form of automatic subdifferentiation (backpropagation). The automatic subdifferentiation is an automated application of the chain rule, made available through the use of the conservative fields. It amounts to calculating the conservative Jacobians of the underlying functions. This "conservative subgradient descent" is given by picking an initial value for the parameters, captured by a vector \(v_{0}\) followed by performing the following update in steps

\[\begin{split} v_{k+1}&=v_{k}+\alpha_{k}g_{k},\\ g_{k}&\in J(v_{k}),\end{split} \tag{13}\]

with \((\alpha_{k})_{k\in\mathbb{N}}\) a sequences of step-sizes and \(J(v_{k})\) the conservative Jacobian [16].

This gives a formal mathematical model for propagating derivatives which can be applied to guarantee local convergence of mini-batch stochastic gradient descent with backpropagation for a large number of machine learning problems. In particular, and of great importance for us, these results hold for locally Lipschitz tame functions.

Next, we will show that the subadditive dual of the MIP formulation of the BNN (7) is locally Lipschitz and tame. This will allow us to use the machinery of [15, 16] discussed above when training the BNN.

## 3 Main Result

We will now present the main result of the paper. To do so, we will restrict to a certain subset of conic MIPs, defined below, termed as "nice" conic MIPs, with a natural notion of "niceness" coming from the original problem (BNNs).

**Definition 8**.: _Let us consider a conic MIP (10). Under the following conditions:_

1. _the feasible set is compact,_
2. _the graph of the objective function has a finite number of non-differentiable points,_

_we call the conic MIP "nice"._

From the perspective of applications to BNNs these are natural assumptions. Firstly, the compactness is included in the condition for strong duality of the subadditive dual of the MIP. Secondly, the objective function of the MIP corresponds to the loss function of the BNN, which naturally is given by a finite union of smooth components.

**Proposition 1**.: _The conic MIP of Theorem 1 is nice._

Proof.: The feasible set is a product of \(\{0,1\}\) and a set \(S\). For any product of \(\{0,1\}\), we obtain a finite value within \(S\). The feasible set is hence compact. The objective function is a finite sum of loss functions for the original BNN, as such it has a finite number of non-differentiable points.
**Theorem 4**.: _Let us consider a nice conic MIP (10) as in Def. 8. For this MIP, there exists an equivalent reformulation which is definable in an o-minimal structure._

Proof.: Let us consider the subadditive dual (11) as the representation of the conic MIP (10). This dual is equivalent by Theorem 2. Furthermore, this dual is locally o-minimal by considering the no-trumps theorem (Theorem 3) together with the fact that \(f(x)\) is non-decreasing and subadditive. By [23, Remark 22], a compact subset of a locally o-minimal structure is o-minimal. When we assume that the feasible region of the mixed-integer set is compact (Property A), we thus obtain o-minimality.

**Corollary 1**.: _Training BNNs allow for implicit differentiation and chain rule._

Proof.: This follows from Proposition 1, Theorem 4, and from the work of [15, 16] discussed above, when one realizes that the subadditive dual is locally Lipschitz. Lipschitzity is from [44]: If \(f\in\mathbf{WNT}\) is subadditive and \(\inf_{t<0}f(tx)/t\) is finite for all \(x\), then \(f\) is Lipschitz. 

This corollary thus provides us with a practical way of training the BNNs, by utilizing the results of [15, 16] to optimize over the subadditive dual of the corresponding MILP.

Let us finally note that, in general, non-decreasing subadditive functions are not tame. A counterexample is given by the Cantor staircase function [54]. This means that in general, the subadditive dual of a conic MIP need not fall under the tame setting and the nice property is necceseary for our main result.

## 4 An Example

To make the above discussion more clear, we present a simple example outlining how the training of a BNN could make use of the implicit differentiation of Bolte et al. [16]. To this end, we consider three final layers of a BNN inspired by Example 1 of [38], illustrated in Fig. 3, where there are a number of binary weights \(v_{i}\), \(w_{i}\) to be learned. The pen-ultimate two layers yield a bi-variate continuous-valued output layer \((y_{1},y_{2})\). Instead of the usual empirical risk, we consider an objective function involving weighted difference from values of the dependent variable in the training data (assumed to be zero), as well as one of the weights in the pen-ultimate layer, for the sake of a more interesting illustration:

\[\begin{split} z^{*}&:=\min_{x,y}\,2(y_{1}-0)+(y_{2}- 0)+\tfrac{1}{2}x_{1},\\ &\text{s.t.}\,x_{1}-\tfrac{3}{2}x_{2}+y_{1}-y_{2}=b,\\ &\qquad\sum_{i}v_{i}=x_{1}\\ &\qquad\sum_{i}w_{i}=x_{2}\\ &\qquad v_{i},w_{i}\in\{0,1\},\,x_{1},x_{2}\in\mathbb{Z}_{+},\,y _{1},y_{2}\in\mathbb{R}_{+}.\end{split} \tag{14}\]
We note that our theory does cover the case of the usual empirical risk with square loss function, but the illustrations would be more involved due to the non-linearity in the square loss.

Following the definition (11), the subadditive dual of (14) is:

\[\rho^{*}\coloneqq\max_{f\in\mathcal{F}_{\mathbb{R}_{+}}}f(b), \tag{15}\] \[\text{s.t.}\ f(1)\leq\tfrac{1}{2},\] \[\ f(-\tfrac{3}{2})\leq 0,\] \[\ f(1)\leq 2,\] \[\ f(-1)\leq 1,\] \[\ f(0)=0.\]

The subadditive dual problem is obviously an infinite-dimensional optimization problem over the whole space of subadditive functions \(\mathcal{F}_{\mathbb{R}_{+}}\). However, as shown in [55], the subadditive functions of MILPs are Chvatal functions, i.e., piece-wise linear. We can thus utilize this knowledge to enumerate the space of subadditive functions relevant for our problem by the slopes, breakpoints and number of segments of the piecewise linear function. When we consider nice MILPs as in (8), we thus obtain a finite-dimensional problem. It is furthermore evident that we can approximate this problem by truncating in the number of segments of the piecewise linear functions.

For the above example, we start with approximating \(f\) by a piecewise-linear function having two segments. By visual inspection of the behaviour of the value function \(f(b)\) (in solid lines) near the origin in Fig. 4, we see that we can approximate \(f(b)\) by

\[\tilde{f}(b)\coloneqq\begin{cases}&2b,\quad b>0,\\ &-b,\quad b\leq 0,\end{cases} \tag{16}\]

based on the directional derivatives. This crude approximation is shown in Fig. 4 as dashed lines. A conservative field for this function is given by

\[D_{\tilde{f}}(b)=\begin{cases}2,&b>0,\\ [-1,2],&b=0,\\ -1,&b<0.\end{cases} \tag{17}\]

Figure 3: A graphical representation of tree final layers of a BNN we use as an example. See (14) for the corresponding MILP.
It is now clear that we can use the conservative fields of [15, 16] to train over this approximation of the the piecewise linear subadditive dual of the primal problem (14).

More generally, we can introduce slope variables \(s_{1}\) and \(s_{2}\) as well as a breaking point \(p\), to parametrize the two-segment approximation:

\[\tilde{f}(b)\coloneqq\begin{cases}&s_{1}b,\quad b>p,\\ &s_{2}b,\quad b\leq p.\end{cases} \tag{18}\]

and thus find the best two-segment approximation of the piecewise linear subadditive dual of the primal problem (14), which in this case coincides with (16) above. Next, we can increase the precision of the approximation by introducing more and more segments of this approximating function, and optimize over the slopes and break points of the segments, and possibly also the number of segments. Following [56], we have studied formulations based on the optimal regression trees for piecewise regression. See the Supplementary material for details.

## 5 Conclusions and Limitations

We have introduced a link between binarized neural networks, and more broadly, nice conic MIPs, and tame geometry. This makes it possible to reuse pre-existing theory and practical implementations of automatic differentiation. Breaking new ground, we leave many questions open. The foremost question is related to the efficiency of algorithms for constructing the subadditive dual. Although Guzelsoy and Ralphs [38, Section 4, Constructing Dual Functions] survey seven very different algorithms, their computational complexity and relative merits are not well understood. For any of those, an efficient implementation (in the sense of output-sensitive algorithm) would provide

Figure 4: The value function, \(f(b)\), of the example (15) together with the simple approximation, \(\tilde{f}(b)\), given by (16).
a solid foundation for further empirical experiments. Given the immense number of problems in symbolic AI, which can be cast as MIPs, and the excellent scalability of existing frameworks based on automatic differentiation, the importance of these questions cannot be understated.

AcknowledgementThe research of Jakub Marecek and Johannes Aspman has been supported by European Union's Horizon Europe research and innovation programme under grant agreement No. GA 101070568 (Human-compatible AI with guarantees).

DisclaimerThis paper was prepared for information purposes and is not a product of HSBC Bank Plc. or its affiliates. Neither HSBC Bank Plc. nor any of its affiliates make any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, but limited to, the completeness, accuracy, reliability of information contained herein and the potential legal, compliance, tax or accounting effects thereof.