# Generalized Optimization: A First Step Towards Category Theoretic Learning
Theory

Dan Shiebler
<EMAIL_ADDRESS>
University of Oxford

###### Abstract

The Cartesian reverse derivative is a categorical generalization of reverse-
mode automatic differentiation. We use this operator to generalize several
optimization algorithms, including a straightforward generalization of
gradient descent and a novel generalization of Newton’s method. We then
explore which properties of these algorithms are preserved in this generalized
setting. First, we show that the transformation invariances of these
algorithms are preserved: while generalized Newton’s method is invariant to
all invertible linear transformations, generalized gradient descent is
invariant only to orthogonal linear transformations. Next, we show that we can
express the change in loss of generalized gradient descent with an inner
product-like expression, thereby generalizing the non-increasing and
convergence properties of the gradient descent optimization flow. Finally, we
include several numerical experiments to illustrate the ideas in the paper and
demonstrate how we can use them to optimize polynomial functions over an
ordered ring.

##  1 Background

Given a convex differentiable function
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$, there are many algorithms that we can
use to minimize it. For example, if we pick a step size $\alpha$ and a
starting point $x_{0}\in\mathbb{R}^{n}$ we can apply the gradient descent
algorithm in which we repeatedly iterate $x_{t+1}=x_{t}-\alpha*\nabla
l(x_{t})$. For small enough $\alpha$ this strategy is guaranteed to get close
to the $x$ that minimizes $l$ (Boyd and Vandenberghe, 2004).

Algorithms like gradient descent are often useful even when $l$ is non-convex.
For example, under relatively mild conditions we can show that taking small
enough gradient descent steps will never increase the value of any
differentiable $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ (Boyd and Vandenberghe,
2004). The modern field of deep learning consists largely of applying gradient
descent and other algorithms that can be efficiently computed with reverse-
mode automatic differentiation to optimize non-convex functions (LeCun et al.,
2015).

While gradient descent is particularly popular, it is not the only gradient-
based optimization algorithm that is widely used in practice. Both the
momentum and Adagrad algorithms use placeholder variables that store
information from previous gradient updates to improve stability. Newton’s
method, which rescales the gradient with the inverse Hessian matrix, is
popular for many applications but less commonly used in deep learning due to
the difficulty of efficiently implementing it with reverse-mode automatic
differentiation. Each of these algorithms have different invariance properties
that affect their stability under dataset transformations: for example,
Newton’s method enjoys an invariance to linear rescaling that gradient descent
lacks.

Given the utility of these algorithms it is natural to explore when they can
be generalized beyond differentiable functions. For example, if we replace the
gradient in gradient descent with a representative of the subgradient, a
simple generalization of the gradient for non-differentiable functions
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the convergence and stability
properties of gradient descent are preserved (Boyd and Vandenberghe, 2004).
Going one step further, some authors have begun to explore generalizations of
differentiation beyond Euclidean spaces. Cockett et al. (2019) introduce
Cartesian reverse derivative categories in which we can define an operator
that shares certain properties with reverse-mode automatic differentiation
(RD.1 to RD.7 in Definition 13 of Cockett et al. (2019)). Reverse derivative
categories are remarkably general: the category of Euclidean spaces and
differentiable functions between them is of course a reverse derivative
category, as are the categories of polynomials over semirings and the category
of Boolean circuits (Wilson and Zanasi, 2021).

In this paper we explore whether the convergence and invariance properties of
optimization algorithms built on top of the gradient and Hessian generalize to
optimization algorithms built on top of Cockett et al. (2019)’s Cartesian
reverse derivative. Our contributions are as follows:

  * $\bullet$

We use Cockett et al. (2019)’s Cartesian reverse derivative to define
generalized analogs of several optimization algorithms, including a novel
generalization of Newton’s method.

  * $\bullet$

We derive novel results on the transformation invariances of these generalized
algorithms.

  * $\bullet$

We define the notion of an optimization domain over which we can apply these
generalized algorithms and study their convergence properties.

  * $\bullet$

We characterize the properties that an optimization domain must satisfy in
order to support generalized gradient-based optimization and we provide novel
results that the optimization domain of polynomials over ordered rings
satisfies these properties.

  * $\bullet$

We include several numerical experiments to illustrate the ideas in the paper
and demonstrate how we can use them to optimize polynomial functions over an
ordered ring. The code to run these experiments is on Github at
tinyurl.com/ku3pjz56.

##  2 Standard Optimization

As we described in Section 1, gradient descent optimizes an objective function
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ by starting at a point
$x_{0}\in\mathbb{R}^{n}$ and progressing the discrete dynamical system
$x_{t+1}=x_{t}-\alpha*\nabla l(x_{t})$. Rewriting this as
$x_{t+\alpha}=x_{t}-\alpha*\nabla l(x_{t})$ and taking the
$lim_{\alpha\rightarrow 0}$ of this system yields the differential equation
$\frac{\partial x}{\partial t}(t)=-\nabla l(x(t))$, which we can think of as
the continuous limit of gradient descent. More generally we have:

######  Definition 2.1.

An optimizer for $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ with dimension $k$ is
a continuous function $d:\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$.

Intuitively, an optimizer defines both a continuous and a discrete dynamical
system

  * $\bullet$

Continuous System: $\left(\frac{\partial x}{\partial t}(t),\frac{\partial
y}{\partial t}(t),\cdots\right)=d(x(t),y(t),\cdots)$

  * $\bullet$

Discrete System: $\left(x_{t+1},y_{t+1},\cdots)=(x_{t},y_{t},\cdots)+\alpha
d(x_{t},y_{t},\cdots\right)$

Note that the discrete dynamical system is the Euler’s method discretization
of the continuous system. We can think of an optimizer with dimension $k>1$ as
using information beyond the previous value $x_{t}$ to determine $x_{t+1}$.

In practice we usually work with optimizers that define dynamical systems in
which $l(x(t))$ and $l(x_{t})$ get closer to the minimum value of $l$ as $t$
increases. Given $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ we can construct the
following examples:

  * $\bullet$

The gradient descent optimizer for $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
$d(x)=-\nabla l(x)$. This optimizer has dimension $1$.

  * $\bullet$

The Newton’s method optimizer for $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
$d(x)=-\nabla^{2}(l(x))^{-1}\nabla l(x)$. This optimizer has dimension $1$ and
uses the inverse Hessian matrix to increase the stability of each update.

  * $\bullet$

The momentum optimizer for $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
$d(x,y)=(y,-y-\nabla l(x))$. This optimizer has dimension $2$ and uses a
placeholder variable to track the value of the previous update steps and
simulate the momentum of a ball rolling down a hill.

  * $\bullet$

The Adagrad optimizer for $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
$d(x,y)=(-\nabla l(x)/\sqrt{y},\nabla l(x)^{2})$. This optimizer has dimension
$2$ and uses a placeholder variable to reweight updates based on the magnitude
of previous updates (Duchi et al., 2011).

###  2.1 Optimization Schemes

######  Definition 2.2.

An optimization scheme
$u:(\mathbb{R}^{n}\rightarrow\mathbb{R})\rightarrow(\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn})$
is a family of functions (indexed by $n$) that maps objectives
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ to optimizers
$d:\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$.

For example, the gradient descent optimization scheme is $u(l)(x)=-\nabla
l(x)$ and the momentum optimization scheme is $u(l)(x,y)=(y,-y-\nabla l(x))$.

In some situations we may be able to improve the convergence rate of the
dynamical systems defined by optimization schemes by precomposing an
invertible function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$. That is,
rather than optimize the function $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ we
optimize $l\circ f:\mathbb{R}^{m}\rightarrow\mathbb{R}$. However, for many
optimization schemes there are classes of transformations to which they are
invariant: applying any such transformation to the data cannot change the
trajectory.

######  Definition 2.3.

Suppose $f:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is an invertible
transformation and write $f_{k}$ for the map $(f\times
f\times\cdots):\mathbb{R}^{km}\rightarrow\mathbb{R}^{kn}$. The optimization
scheme $u$ is invariant to $f$ if $u(l\circ f)=f_{k}^{-1}\circ u(l)\circ
f_{k}$.

######  Proposition 1.

Recall that an invertible linear transformation is a function $f(x)=Ax$ where
the matrix $A$ has an inverse $A^{-1}$ and an orthogonal linear transformation
is an invertible linear transformation where $A^{-1}=A^{T}$. Newton’s method
is invariant to all invertible linear transformations, whereas both gradient
descent and momentum are invariant to orthogonal linear transformations.
(Proof in Appendix A.1).

Note that Adagrad is not invariant to orthogonal linear transformations due to
the fact that it tracks a nonlinear function of past gradients (sum of
squares). In order to interpret these invariance properties it is helpful to
consider how they affect the discrete dynamical system defined by an
optimization scheme.

######  Proposition 2.

Given an objective function $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and an
optimization scheme
$u:(\mathbb{R}^{n}\rightarrow\mathbb{R})\rightarrow(\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn})$
that is invariant to the invertible linear function
$f:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$, the discrete system defined by
the optimizer $u(l\circ f)$:

$\displaystyle y_{t+1}=y_{t}+\alpha u(l\circ f)(y_{t})$

cannot converge faster than the discrete system defined by the optimizer
$u(l)$:

$\displaystyle x_{t+1}=x_{t}+\alpha u(l)(x_{t})$

(Proof in Appendix A.2).

Propositions 1 and 2 together give some insight into why Newton’s method can
perform so much better than gradient descent for applications where both
methods are computationally feasible (Boyd and Vandenberghe, 2004). Whereas
gradient descent can be led astray by bad data scaling, Newton’s method steps
are always scaled optimally and therefore cannot be improved by data
rescaling.

It is important to note that Proposition 2 only applies to linear
transformation functions $f$. Since Euler’s method is itself a linear method,
it does not necessarily preserve non-linear invariance properties.

##  3 Generalized Optimization

In this section we assume readers have a basic familiarity with Category
Theory. We recommend that readers who would like a detailed introduction to
the field check out “Basic Category Theory” (Leinster, 2016) or “Seven
Sketches in Compositionality” (Fong and Spivak, 2019).

###  3.1 Cartesian and Reverse Derivative Categories

We begin by recalling some basic terminology and notation. A category is a
collection of objects and morphisms between them. Morphisms are closed under
an associative composition operation, and each object is equipped with an
identity morphism. An example category is the collection of sets (objects) and
functions (morphisms) between them. We call the set of morphisms between the
objects $A$ and $B$ in the category $\mathbf{C}$ the hom-set
$\mathbf{C}[A,B]$.

A category is Cartesian when there exists a product operation $\times$ that
allows us to combine objects, a pairing operation $\langle-,-\rangle$ that
allows us to combine morphisms, projection maps $\pi_{0}:A\times B\rightarrow
A,\pi_{1}:A\times B\rightarrow B$ and a terminal object $*$ such that every
object $A$ is equipped with a unique map $!_{A}:A\rightarrow*$ from $A$ to the
terminal object $*$. Given an object $A$ or morphism $f$ in a Cartesian
category, in this work we write $A^{k}$ and $f^{k}$ to respectively denote $A$
and $f$ tensored with themselves $k$ times.

Now recall the following definition from Richard F Blute (2009); Cockett et
al. (2019):

######  Definition 3.1.

A Cartesian left additive category is a Cartesian category $\mathbf{C}$ in
which the hom-set of each pair of objects $B,C$ is a commutative monoid, with
addition operation $+$ and zero maps (additive identities)
$0_{BC}:B\rightarrow C$, such that:

  * $\bullet$

For any morphism $h:A\rightarrow B$ and $f,g:B\rightarrow C$ we have:

$\displaystyle(f+g)\circ h=(f\circ h)+(g\circ h):A\rightarrow C\qquad
0_{BC}\circ h=0_{AC}:A\rightarrow C$

  * $\bullet$

For any projection map $\pi_{i}:C\rightarrow D$ and $f,g:B\rightarrow C$ we
have:

$\displaystyle\pi_{i}\circ(f+g)=(\pi_{i}\circ f)+(\pi_{i}\circ g):B\rightarrow
D\qquad\pi_{i}\circ 0_{BC}=0_{BD}:B\rightarrow D$

We write $0_{A}$ for the additive identity of the hom-set $\mathbf{C}[*,A]$.

Intuitively, in a Cartesian left additive category we can add morphisms in a
way that is compatible with postcomposition and the Cartesian structure.
Certain Cartesian left additive categories are equipped with additional
structure that behaves similarly to derivatives:

######  Definition 3.2.

A Cartesian reverse derivative category is a Cartesian left-additive category
$\mathbf{C}$ equipped with a Cartesian reverse derivative combinator $R$ that
assigns to each morphism $f:A\rightarrow B$ in $\mathbf{C}$ a morphism
$R[f]:A\times B\rightarrow A$ in $\mathbf{C}$ such that $R$ satisfies the
following equations (Definition 13 of (Cockett et al., 2019)):

  * RD.1

$R[f+g]=R[f]+R[g]$ and $R[0]=0$;

  * RD.2

$R[f]\circ\langle a,b+c\rangle=R[f]\circ\langle a,b\rangle+R[f]\circ\langle
a,c\rangle$ and $R[f]\circ\langle a,0\rangle=0$;

  * RD.3

$R[1]=\pi_{1},R[\pi_{0}]=\iota_{0}\circ\pi_{1}$ and
$R[\pi_{1}]=\iota_{1}\circ\pi_{1}$;

  * RD.4

$R[\langle f,g\rangle]=R[f]\circ(1\times\pi_{0})+R[g]\circ(1\times\pi_{1})$
and $R[!_{A}]=0$;

  * RD.5

$R[g\circ f]=R[f]\circ(1\times R[g])\circ\langle\pi_{0},\langle
f\circ\pi_{0},\pi_{1}\rangle\rangle$;

  * RD.6

$\pi_{1}\circ R[R[R[f]]]\circ(\iota_{0}\times 1)\circ\langle
1\times\pi_{0},0\times\pi_{1}\rangle=R[f]\circ(1\times\pi_{1})$;

  * RD.7

$\displaystyle\pi_{1}\circ R[R[\pi_{1}\circ R[R[f]]\circ(\iota_{0}\times
1)]]\circ(\iota_{0}\times 1)=$
$\displaystyle\langle\pi_{0}\times\pi_{0},\pi_{1}\times\pi_{1}\rangle\circ\pi_{1}\circ
R[R[\pi_{1}\circ R[R[f]]\circ(\iota_{0}\times 1)]]\circ(\iota_{0}\times 1)$

where $\iota_{0}:A\rightarrow A\times B$ and $\iota_{1}:B\rightarrow A\times
B$ are the Cartesian injection maps (Cockett et al., 2019).

The conditions RD.1 to RD.7 mirror the properties of the derivative operation.
For example, $R$ must commute with addition (RD.1) and compose according to a
chain rule (RD.5).

######  Definition 3.3.

A Cartesian differential category $\mathbf{C}$ is a Cartesian left-additive
category equipped with a Cartesian derivative combinator $D$ that assigns to
each morphism $f:A\rightarrow B$ in $\mathbf{C}$ a morphism $D[f]:A\times
A\rightarrow B$ in $\mathbf{C}$ such that $D$ satisfies the following
equations (Definition 4 in Cockett et al. (2019), adapted from Definition
2.1.1 in (Richard F Blute, 2009)):

  * CDC.1

$D[f+g]=D[f]+D[g]$ and $D[0]=0$;

  * CDC.2

$D[f]\circ\langle a,b+c\rangle=D[f]\circ\langle a,b\rangle+D[f]\circ\langle
a,c\rangle$ and $D[f]\circ\langle a,0\rangle=0$;

  * CDC.3

$D[1]=\pi_{1},D[\pi_{0}]=\pi_{0}\circ\pi_{1}$ and
$D[\pi_{1}]=\pi_{1}\circ\pi_{1}$;

  * CDC.4

$D[\langle f,g\rangle]=\langle D[f],D[g]\rangle$;

  * CDC.5

$D[g\circ f]=D[g]\circ\langle f\circ\pi_{0},D[f]\rangle$;

  * CDC.6

$D[D[f]]\circ\langle\langle a,b\rangle,\langle
0,c\rangle\rangle=D[f]\circ\langle a,c\rangle$;

  * CDC.7

$D[D[f]]\circ\langle\langle a,b\rangle,\langle
c,d\rangle\rangle=D[D[f]]\circ\langle\langle a,c\rangle,\langle
b,d\rangle\rangle$.

By Theorem 16 in (Cockett et al., 2019), every Cartesian reverse derivative
category $\mathbf{C}$ is also a Cartesian differential category where for any
morphism $f:A\rightarrow B$ in $\mathbf{C}$:

$\displaystyle D[f]=\pi_{1}\circ R[R[f]]\circ(\langle
id_{A},0_{AB}\rangle\times id_{A}):A\times A\rightarrow B$

Going forward, when we refer to the Cartesian derivative combinator $D$ of a
Cartesian reverse derivative category this is the construction that we are
referring to.

The canonical example of a Cartesian reverse derivative category that we will
consider is the category $\mathbf{Euc}$ of Euclidean spaces and infinitely
differentiable maps between them. The terminal object $*$ in $\mathbf{Euc}$ is
$\mathbb{R}^{0}$, the Cartesian reverse derivative of the map
$f:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$ is
$R[f](x,x^{\prime})=J_{f}(x)^{T}x^{\prime}$, and the Cartesian derivative of
$f$ is $D[f](x,x^{\prime})=J_{f}(x)x^{\prime}$ where $J_{f}(x)$ is the
Jacobian of $f$ evaluated at $x\in\mathbb{R}^{a}$. Recall that the Jacobian of
$f:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$ is a $b\times a$ matrix whose
$i,j$th element is $\frac{\partial f_{i}}{\partial x_{j}}$.

As another example, given a commutative ring $r$ we can form the category
$\mathbf{Poly}_{r}$ in which objects are natural numbers and the morphisms
from $n$ to $m$ are tuples of $m$ polynomials with $n$ variables and
coefficients in $r$. That is, a morphism $P:n\rightarrow m$ is a map
$P(x)=\left(p_{1}(x),\cdots,p_{m}(x)\right)$ where $x=(x_{1},\cdots,x_{n})$
and $p_{i}$ is a polynomial. $\mathbf{Poly}_{r}$ is a Cartesian reverse
derivative category in which the terminal object $*$ is $0$ and the reverse
derivative of $P(x)=\left(p_{1}(x),\cdots,p_{m}(x)\right)$ is:

$\displaystyle R[P](x,x^{\prime})=\left(\sum_{i=1}^{m}\frac{\partial
p_{i}}{\partial x_{1}}(x)x^{\prime}_{i},\cdots,\sum_{i=1}^{m}\frac{\partial
p_{i}}{\partial x_{n}}(x)x^{\prime}_{i}\right)$

where $\frac{\partial p_{i}}{\partial x_{j}}(x)$ is the formal derivative of
$p_{i}$ in $x_{j}$, evaluated at $x$ (Cockett et al., 2019).

The linear maps in a Cartesian reverse derivative category $\mathbf{C}$ are
those for which $D[f]=f\circ\pi_{1}$. The linear maps of $\mathbf{C}$ form a
subcategory of $\mathbf{C}$ equipped with a stationary on objects involution
$(\textunderscore)^{\dagger}:\mathbf{C}^{op}\rightarrow\mathbf{C}$ such that
for any linear map $f$ we have $R[f]=f^{\dagger}\circ\pi_{1}$ (Cockett et al.,
2019).

The linear maps in $\mathbf{Euc}$ are exactly the linear maps in the
traditional sense, and given a linear map
$f:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$ in $\mathbf{Euc}$ where $f(x)=Mx$
we have $f^{\dagger}:\mathbb{R}^{b}\rightarrow\mathbb{R}^{a}$ where
$f^{\dagger}(x)=M^{T}x$. That is, $\dagger$ is a generalization of the
transpose. Similarly, the linear maps in $\mathbf{Poly}_{r}$ are those that
can be expressed as $P(x)=\left(p_{1}(x),\cdots,p_{m}(x)\right)$ where
$p_{i}(x)=\sum_{i=1}^{n}r_{i}x_{i}$ for $r_{i}\in r$ (Cockett et al., 2019).

###  3.2 Optimization Domain

######  Definition 3.4.

An optimization domain is a tuple $(\mathbf{Base},X)$ such that each morphism
$f:A\rightarrow B$ in the Cartesian reverse derivative category
$\mathbf{Base}$ has an additive inverse $-f$ and each homset $\mathbf{C}[*,A]$
out of the terminal object $*$ is further equipped with a multiplication
operation $fg$ and a multiplicative identity map $1_{A}:*\rightarrow A$ to
form a commutative ring with the left additive structure $+$. $X$ is an object
in $\mathbf{Base}$ such that the homset $f\in\mathbf{C}[*,X]$ is further
equipped with a total order $f\leq g$ to form an ordered commutative ring.

Given an optimization domain $(\mathbf{Base},X)$ the object $X$ represents the
space of objective values to optimize and we refer to morphisms into $X$ as
objectives. We abbreviate the map $1_{B}\circ!_{A}:A\rightarrow B$ as
$1_{AB}$, where $!_{A}:A\rightarrow*$ is the unique map into the terminal
object $*$. For example, the objectives in the standard domain
$(\mathbf{Euc},\mathbb{R})$ are functions
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$. If $r$ is an ordered commutative ring
then we can form the $r$-polynomial domain $(\mathbf{Poly}_{r},1)$ in which
objectives are $r$-polynomials $l_{P}:n\rightarrow 1$.

######  Definition 3.5.

We say that an objective $l:A\rightarrow X$ is bounded below in
$(\mathbf{Base},X)$ if there exists some $x:*\rightarrow X$ such that for any
$a:*\rightarrow A$ we have $x\leq l\circ a$.

In both the standard and $r$-polynomial domains an objective is bounded below
if its image has an infimum.

####  3.2.1 Generalized Gradient and Generalized $n$-Derivative

######  Definition 3.6.

The generalized gradient of the objective $l:A\rightarrow X$ in
$(\mathbf{Base},X)$ is $R[l]_{1}:A\rightarrow A$ where:

$\displaystyle R[l]_{1}=R[l]\circ\langle id_{A},1_{AX}\rangle$

In the standard domain the generalized gradient of
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is just the gradient
$R[l]_{1}(x)=\nabla l(x)$ and in the $r$-polynomial domain the generalized
gradient of $l_{P}:n\rightarrow 1$ is $R[l_{P}]_{1}(x)=\left(\frac{\partial
l_{P}}{\partial x_{1}}(x),\cdots,\frac{\partial l_{P}}{\partial
x_{n}}(x)\right)$ where $\frac{\partial l_{P}}{\partial x_{i}}$ is the formal
derivative of the polynomial $l_{P}$ in $x_{i}$.

######  Definition 3.7.

The generalized $n$-derivative of the morphism $f:X\rightarrow A$ in
$(\mathbf{Base},X)$ is $D_{n}[f]:X\rightarrow A$ where:

$\displaystyle D_{1}[f]=D[f]\circ\langle id_{X},1_{XX}\rangle\qquad
D_{n}[f]=D[D_{n-1}[f]]\circ\langle id_{X},1_{XX}\rangle$

In the standard domain the generalized $n$-derivative of
$f:\mathbb{R}\rightarrow\mathbb{R}$ is the $n$-derivative
$f^{(n)}=\frac{\partial^{n}f}{\partial x^{n}}$ and in the $r$-polynomial
domain the generalized $n$-derivative of $l_{P}:1\rightarrow 1$ is the formal
$n$-derivative $\frac{\partial^{n}l_{P}}{\partial x^{n}}$.

The derivative over the reals has a natural interpretation as a rate of
change. We can generalize this as follows:

######  Definition 3.8.

We say that a morphism $f:X\rightarrow X$ in $\mathbf{Base}$ is $n$-smooth in
$(\mathbf{Base},X)$ if whenever $D_{k}[f]\circ t\geq 0_{X}:*\rightarrow X$ for
all $t_{1}\leq t\leq t_{2}:*\rightarrow X$ and $k\leq n$ we have that $f\circ
t_{1}\leq f\circ t_{2}:*\rightarrow X$.

Intuitively, $f$ is $n$-smooth if it cannot decrease on any interval over
which its generalized derivatives of order $n$ and below are non-negative.
Some examples include:

  * $\bullet$

Any map $f:\mathbb{R}\rightarrow\mathbb{R}$ is $1$-smooth in the standard
domain by the mean value theorem.

  * $\bullet$

When $r$ is a dense subring of a real-closed field then any polynomial
$l_{P}:1\rightarrow 1$ is $1$-smooth in the $r$-polynomial domain (Nombre,
2021).

  * $\bullet$

For any $r$, the polynomial $l_{P}=\sum_{k=0}^{n}c_{k}t^{k}:1\rightarrow 1$ of
degree $n$ is $n$-smooth in the $r$-polynomial domain since for any $t_{1}$ we
can use the binomial theorem to write:

$\displaystyle
l_{P}(t)=\sum_{k=0}^{n}c_{k}t^{k}=\sum_{k=0}^{n}c_{k}(t_{1}+(t-t_{1}))^{k}=l_{P}(t_{1})+\sum_{k=1}^{n}c^{\prime}_{k}(t-t_{1})^{k}$

where $c^{\prime}_{k}$ is a constant such that
$(c^{\prime}_{k})(k!)=D_{k}[l_{P}](t_{1})$. Note that $c^{\prime}_{k}$ must
exist by the definition of the formal derivative of $l_{P}$, and must be non-
negative if $D_{k}[l_{P}](t_{1})$ is non-negative.

###  3.3 Optimization Functors

In this section we generalize optimization schemes (Section 2.1) to arbitrary
optimization domains. This will enable us to characterize the invariance
properties of our generalized optimization schemes in terms of the categories
out of which they are functorial. Given an optimization domain
$(\mathbf{Base},X)$ we can define the following categories:

######  Definition 3.9.

The objects in the category $\mathbf{Objective}$ over the optimization domain
$(\mathbf{Base},X)$ are objectives $l:A\rightarrow X$ such that there exists
an inverse function $R[l]_{1}^{-1}:A\rightarrow A$ where $R[l]_{1}^{-1}\circ
R[l]_{1}=R[l]_{1}\circ R[l]_{1}^{-1}=id_{A}:A\rightarrow A$, and the morphisms
between $l:A\rightarrow X$ and $l^{\prime}:B\rightarrow X$ are morphisms
$f:A\rightarrow B$ where $l^{\prime}\circ f=l$.

Note that $\mathbf{Objective}$ is a subcategory of the slice category
$\mathbf{Base}/X$.

In the standard domain the objects in $\mathbf{Objective}$ are objectives
$l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ such that the function $\nabla
l:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is invertible. In the
$r$-polynomial domain, the objects in $\mathbf{Objective}$ are $r$-polynomials
$l_{P}:n\rightarrow 1$ such that the function $\langle\frac{\partial
l_{P}}{\partial x_{1}},\cdots,\frac{\partial l_{P}}{\partial
x_{n}}\rangle:n\rightarrow n$ is invertible.

######  Definition 3.10.

A generalized optimizer over the optimization domain $(\mathbf{Base},X)$ with
state space $A\in\mathbf{Base}$ and dimension $k\in\mathbb{N}$ is an
endomorphism $d:A^{k}\rightarrow A^{k}$ in $\mathbf{Base}$. The objects in the
category $\mathbf{Optimizer}$ over $(\mathbf{Base},X)$ are generalized
optimizers, and the morphisms between the generalized optimizers
$d:A^{k}\rightarrow A^{k}$ and $d^{\prime}:B^{k}\rightarrow B^{k}$ are
$\mathbf{Base}$-morphisms $f:A\rightarrow B$ such that $f^{k}\circ
d=d^{\prime}\circ f^{k}:A^{k}\rightarrow B^{k}$. Note that morphisms only
exist between generalized optimizers with the same dimension. The composition
of morphisms in $\mathbf{Optimizer}$ is the same as in $\mathbf{Base}$.

Recall that $A^{k}$ and $f^{k}$ are respectively $A$ and $f$ tensored with
themselves $k$ times. In the standard domain a generalized optimizer with
dimension $k$ is a tuple $(\mathbb{R}^{n},d)$ where
$d:\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$ is an optimizer (Definition
2.1).

######  Definition 3.11.

Given a subcategory $\mathbf{D}$ of $\mathbf{Objective}$, an optimization
functor over $\mathbf{D}$ is a functor
$\mathbf{D}\rightarrow\mathbf{Optimizer}$ that maps the objective
$l:A\rightarrow X$ to a generalized optimizer over $(\mathbf{Base},X)$ with
state space $A$.

Optimization functors are generalizations of optimization schemes (Definition
2.2) that map objectives to generalized optimizers. Explicitly, an
optimization scheme $u$ that maps $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ to
$u(l):\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$ defines an optimization
functor in the standard domain.

The invariance properties of optimization functors are represented by the
subcategory $\mathbf{D}\subseteq\mathbf{Objective}$ out of which they are
functorial. Concretely, consider the following categories:

  * $\bullet$

$\mathbf{Objective}_{I}$: The subcategory of $\mathbf{Objective}$ in which
morphisms are limited to invertible linear morphisms $l$ in $\mathbf{Base}$.

  * $\bullet$

$\mathbf{Objective}_{\perp}$: The subcategory of $\mathbf{Objective}_{I}$ in
which the inverse of $l$ is $l^{\dagger}$.

In both the standard domain and $r$-polynomial domain, the morphisms in
$\mathbf{Objective}_{I}$ are linear maps defined by an invertible matrix and
the morphisms in $\mathbf{Objective}_{\perp}$ are linear maps defined by an
orthogonal matrix (matrix inverse is equal to matrix transpose). We will now
generalize Proposition 1 by defining generalized gradient descent and momentum
functors that are functorial out of $\mathbf{Objective}_{\perp}$ and a
generalized Newton’s method functor that is functorial out of
$\mathbf{Objective}_{I}$.

######  Definition 3.12.

Generalized gradient descent sends the objective $l:A\rightarrow X$ to the
generalized optimizer $-R[l]_{1}:A\rightarrow A$ with dimension $1$.

######  Definition 3.13.

Generalized momentum sends the objective $l:A\rightarrow X$ to the generalized
optimizer
$\langle\pi_{1},-\pi_{1}-(R[l]_{1}\circ\pi_{0})\rangle:A^{2}\rightarrow A^{2}$
with dimension $2$.

Generalized momentum and generalized gradient descent have a very similar
structure, with the major difference between the two being that generalized
momentum uses a placeholder variable and generalized gradient descent does
not. In the standard domain we have that $-R[l]_{1}(x)=-\nabla l(x)$ and
$(\langle\pi_{1},-\pi_{1}-(R[l]_{1}\circ\pi_{0})\rangle)(x,y)=(y,-y-\nabla
l(x))$, so generalized gradient descent and generalized momentum are
equivalent to the gradient descent and momentum optimization schemes that we
defined in Section 2.1. Similarly, in the $r$-polynomial domain generalized
gradient descent maps $l_{P}:n\rightarrow 1$ to $-R[l_{P}]_{1}:n\rightarrow n$
and generalized momentum maps $l_{P}$ to
$\langle\pi_{1},-\pi_{1}-(R[l_{P}]_{1}\circ\pi_{0})\rangle:n^{2}\rightarrow
n^{2}$ where:

$\displaystyle\langle\pi_{1},-\pi_{1}-(R[l_{P}]_{1}\circ\pi_{0})\rangle(x,x^{\prime})=\left(x^{\prime},-x^{\prime}-\left(\frac{\partial
l_{P}}{\partial x_{1}}(x),\cdots,\frac{\partial l_{P}}{\partial
x_{n}}(x)\right)\right)$

Since Newton’s method involves the computation of an inverse Hessian it is not
immediately obvious how we can express it in terms of Cartesian reverse
derivatives. However, by the inverse function theorem we can rewrite the
inverse Hessian as the Jacobian of the inverse gradient function, which makes
this easier. That is:

$\displaystyle(\nabla^{2}l)(x)^{-1}=J_{\nabla l}(x)^{-1}=J_{(\nabla
l)^{-1}}(\nabla l(x))$ (1)

where $J_{\nabla l}(x)=(\nabla^{2}l)(x)$ is the Hessian of $l$ at $x$,
$J_{(\nabla l)^{-1}}(\nabla l(x))$ is the Jacobian of the inverse gradient
function evaluated at $\nabla l(x)$, and the second equality holds by the
inverse function theorem. We can therefore generalize the Newton’s method term
$-\nabla^{2}(l)^{-1}\nabla l$ as $-R[R[l]_{1}^{-1}]\circ\langle
R[l]_{1},R[l]_{1}\rangle:X\rightarrow X$ and generalize Newton’s method as
follows:

######  Definition 3.14.

Generalized Newton’s method sends the objective $l:A\rightarrow X$ to the
generalized optimizer $-R[R[l]_{1}^{-1}]\circ\langle
R[l]_{1},R[l]_{1}\rangle:A\rightarrow A$ with dimension $1$.

Equation 1 implies that generalized Newton’s method in the standard domain is
equivalent to the Newton’s method optimization scheme that we defined in
Section 2.1. In the $r$-polynomial domain generalized Newton’s Method maps the
polynomial $l_{P}:n\rightarrow 1$ to $-R[R[l_{P}]_{1}^{-1}]\circ\langle
R[l_{P}]_{1},R[l_{P}]_{1}\rangle:n\rightarrow n$ where:

$\displaystyle-R[R[l_{P}]_{1}^{-1}]\circ\langle
R[l_{P}]_{1},R[l_{P}]_{1}\rangle(x)=$
$\displaystyle-\begin{pmatrix}\frac{\partial(R[l_{P}]_{1}^{-1})_{1}}{\partial
x_{1}}(R[l_{P}]_{1}(x))&\dots&\frac{\partial(R[l_{P}]_{1}^{-1})_{1}}{\partial
x_{n}}(R[l_{P}]_{1}(x))\\\ \vdots&\ddots&\\\
\frac{\partial(R[l_{P}]_{1}^{-1})_{n}}{\partial
x_{1}}(R[l_{P}]_{1}(x))&&\frac{\partial(R[l_{P}]_{1}^{-1})_{n}}{\partial
x_{n}}(R[l_{P}]_{1}(x))\end{pmatrix}^{T}\left(\frac{\partial l_{P}}{\partial
x_{1}}(x),\cdots,\frac{\partial l_{P}}{\partial x_{n}}(x)\right)$

Note that $(R[l_{P}]_{1}^{-1})_{i}$ is the $i$th projection of the inverse of
the reverse derivative map. We now generalize Proposition 1:

######  Proposition 3.

Generalized Newton’s method is a functor from $\mathbf{Objective}_{I}$ to
$\mathbf{Optimizer}$, whereas both generalized gradient descent and
generalized momentum are functors from $\mathbf{Objective}_{\perp}$ to
$\mathbf{Optimizer}$. (Proof in Appendix A.3)

Proposition 3 implies that the invariance properties of our optimization
functors mirror the invariance properties of their optimization scheme
counterparts. Not only does Proposition 3 directly imply Proposition 1, but it
also implies that the invariance properties that gradient descent, momentum,
and Newton’s method enjoy are not dependent on the underlying category over
which they are defined.

###  3.4 Generalized Optimization Flows

In Section 2 we demonstrated how we can derive continuous and discrete
dynamical systems from an optimizer
$d:\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$. In this section we extend this
insight to generalized optimizers.

To do this, we define a morphism $s:X\rightarrow A^{k}$ whose Cartesian
derivative is defined by a generalized optimizer $d:A^{k}\rightarrow A^{k}$.
Since we can interpret morphisms in $\mathbf{Base}[*,X]$ as either times $t$
or objective values $x$, the morphism $s:X\rightarrow A^{k}$ describes how the
state of our dynamical system evolves in time. Formally we can put this
together in the following structure:

######  Definition 3.15.

A generalized optimization flow over the optimization domain
$(\mathbf{Base},X)$ with state space $A\in\mathbf{Base}$ and dimension
$k\in\mathbb{N}$ is a tuple $(l,d,s,\tau)$ where $l:A\rightarrow X$ is an
objective, $d:A^{k}\rightarrow A^{k}$ is a generalized optimizer,
$s:X\rightarrow A^{k}$ is a morphism in $\mathbf{Base}$ and $\tau$ is an
interval in $\mathbf{Base}[*,X]$ such that for $t\in\tau$ we have $d\circ
s\circ t=D_{1}[s]\circ t:*\rightarrow A^{k}$.

Intuitively, $l$ is an objective, $d$ is a generalized optimizer, and $s$ is
the state map that maps times in $\tau$ to the system state such that $d\circ
s:X\rightarrow A^{k}$ describes the Cartesian derivative of the state map
$D_{1}[s]$.

In the standard domain we can define a generalized optimization flow
$(l,d,s,\mathbb{R})$ from an optimizer
$d:\mathbb{R}^{kn}\rightarrow\mathbb{R}^{kn}$ and an initial state
$s_{0}\in\mathbb{R}^{kn}$ by defining a state map
$s:\mathbb{R}\rightarrow\mathbb{R}^{kn}$ where
$s(t)=s_{0}+\int_{0}^{t}d(s(t^{\prime}))dt^{\prime}$. We can think of a state
map in the standard domain as a simulation of Euler’s method with
infinitesimal $\alpha$:

$\displaystyle lim_{\alpha\rightarrow 0}s(t+\alpha)=lim_{\alpha\rightarrow
0}s(t)+\alpha d(x_{t})$

######  Definition 3.16.

A generalized optimization flow $(l,d,s,\tau)$ over the optimization domain
$(\mathbf{Base},X)$ is an $n$-descending flow if for any $t\in\tau$ and $k\leq
n$ we have:

$\displaystyle D_{k}[l\circ\pi_{0}\circ s]\circ t\leq 0_{X}:*\rightarrow X$

Note that if $(l,d,s,\tau)$ is an $n$-descending flow and $l\circ\pi_{0}\circ
s:X\rightarrow X$ is $n$-smooth (Definition 3.8), then $l\circ\pi_{0}\circ s$
must be monotonically decreasing in $t$ on $\tau$.

######  Definition 3.17.

The generalized optimization flow $(l,d,s,\tau)$ over the optimization domain
$(\mathbf{Base},X)$ converges if for any $\delta>0_{X}:*\rightarrow X$ there
exists some $t\in\tau$ such that for any $t\leq t^{\prime}\in\tau$ we have
$-\delta\leq(l\circ\pi_{0}\circ s\circ t^{\prime})-(l\circ\pi_{0}\circ s\circ
t)\leq\delta$

In the standard domain this reduces to a familiar definition of convergence
that is similar to what Ang (2020) uses: a flow converges if there exists a
time $t$ after which the value of the objective $l$ does not change by more
than an arbitrarily small amount.

Now suppose $(l,d,s,\tau)$ is an $n$-descending flow, $l\circ\pi_{0}\circ
s:X\rightarrow X$ is $n$-smooth and $l$ is bounded below (Definition 3.5).
Since $l\circ\pi_{0}\circ s$ must decrease monotonically in $t$ it must be
that $(l,d,s,\tau)$ converges. In the next section we give examples of
optimization flows defined by the generalized gradient that satisfy these
conditions.

####  3.4.1 Generalized Gradient Flows

######  Definition 3.18.

A generalized gradient flow is a generalized optimization flow of the form
$(l,-R[l]_{1},s,\tau)$.

Given a smooth objective $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ an example
generalized gradient flow in the standard domain is $(l,-\nabla
l,s,\mathbb{R})$ where $s(t)=s_{0}+\int_{0}^{t}-\nabla
l(s(t^{\prime}))dt^{\prime}$ for some $s_{0}\in\mathbb{R}^{n}$. One of the
most useful properties of a generalized gradient flow is that we can write its
Cartesian derivative with an inner product-like structure:

######  Proposition 4.

Given a choice of time $t\in\tau$ and a generalized gradient flow
$(l,-R[l]_{1},s,\tau)$ we can write the following:

$\displaystyle D_{1}[l\circ\pi_{0}\circ s]\circ t=-R[l]_{s_{t}}^{\dagger}\circ
R[l]_{s_{t}}\circ 1_{X}:*\rightarrow X$

where $R[l]_{s_{t}}=R[l]\circ\langle s\circ
t\circ!_{X},id_{X}\rangle:X\rightarrow A$. (Proof in Appendix A.4)

Intuitively, $s\circ t:*\rightarrow A$ is the state at time $t$ and
$R[l]_{s_{t}}\circ 1_{X}:*\rightarrow A$ is the value of the generalized
gradient of $l$ at time $t$. To understand the importance of this result
consider the following definition:

######  Definition 3.19.

$(\mathbf{Base},X)$ supports generalized gradient-based optimization when any
generalized gradient flow over $(\mathbf{Base},X)$ is a $1$-descending flow.

Intuitively, an optimization domain supports generalized gradient-based
optimization if loss decreases in the direction of the gradient. Proposition 4
is important because it helps us identify the optimization domains for which
this holds. For example, Proposition 4 implies that both the standard domain
and any $r$-polynomial domain support generalized gradient-based optimization:

  * $\bullet$

In the standard domain we have that:

$\displaystyle-R[l]_{s_{t}}^{\dagger}\circ R[l]_{s_{t}}\circ
1_{\mathbb{R}}=-\nabla l(s(t))^{T}\nabla l(s(t))=-\|\nabla l(s(t))\|^{2}$

which must be non-positive by the definition of a norm. As a result, any
generalized gradient flow $(l,-R[l],s,\tau)$ in the standard domain converges
if $l$ is bounded below.

  * $\bullet$

In the $r$-polynomial domain we have that:

$\displaystyle-R[l_{P}]_{s_{t}}^{\dagger}\circ R[l_{P}]_{s_{t}}\circ
1_{1}=-\sum_{i=1}^{n}\frac{\partial l_{P}}{\partial
x_{i}}(s_{t})R[l_{P}]_{s_{t}}(1_{1})_{i}=-\sum_{i=1}^{n}\frac{\partial
l_{P}}{\partial x_{i}}(s_{t})\frac{\partial l_{P}}{\partial x_{i}}(s_{t})$

which must be non-positive since in an ordered ring no negative element is a
square. If $r$ is a dense subring of a real-closed field then any generalized
gradient flow $(l,-R[l],s,\tau)$ in the $r$-polynomial domain converges if $l$
is bounded below (since $l\circ\pi_{0}\circ s:X\rightarrow X$ must be
$1$-smooth, see Section 3.2.1).

##  4 Example and Experiment

We start this section with a demonstration of the structure and behavior of an
example optimization flow. We then build on this example to define an
algorithm for finding integer minima of multivariate polynomials. We
demonstrate that this algorithm consistently outperforms random search.

###  4.1 Illustrative Example - Integer Polynomial State Map

Suppose $l_{P}:1\rightarrow 1$ is an objective and $u$ is an optimization
functor in the integer polynomial domain $\mathbf{Poly}_{\mathbb{Z}}$. Given a
choice of integer $x_{0}\in\mathbb{Z}$, we can follow the pattern laid out in
Section 2 and form a discrete dynamical system $x_{t+1}=x_{t}+u(l_{P})(x)$.

Now suppose that for some $\tau=1,2,\cdots,m$ we would like to construct an
optimization flow $(l_{P},u(l_{P}),s,\tau)$ that traces out the values of this
dynamical system. The state map $s$ must be an integer polynomial that
satisfies two properties:

  1. 1.

The integer polynomial $s$ intersects the discrete dynamical system at each
$t\in\tau$:

$\displaystyle s(t+1)=s(t)+u(l_{P})(s(t))$

  2. 2.

By the definition of an optimization flow it must be that $u(l_{P})$ defines
the derivative of $s$. That is, for $t\in\tau$:

$\displaystyle u(l_{P})(s(t))=\frac{\partial s}{\partial t}(t)$

By Proposition 4 we expect that $s$ will move towards the minima of $l_{P}$ at
each step.

There may be no, some, or an infinite number of integer polynomials
$s(t)=p_{1}t+p_{2}t^{2}+\cdots+p_{n}t^{n}$ that satisfy these conditions. For
example, consider the simple case in which $l_{P}(x)=ax^{2}+b$ and
$u(l_{P})=-R[l_{P}]=-\frac{\partial l_{P}}{\partial x}$. In this case the
condition $u(l_{P})(s(t))-\frac{\partial s}{\partial t}(t)=0$ becomes:

$\displaystyle u(l_{P})(s(t))-\frac{\partial s}{\partial t}(t)=$
$\displaystyle-\frac{\partial l_{P}}{\partial x}(s(t))-\frac{\partial
s}{\partial t}(t)=$ $\displaystyle-2as(t)-\frac{\partial s}{\partial t}(t)=$
$\displaystyle-\left(2ap_{0}+2ap_{1}t+2ap_{2}t^{2}+\cdots+2ap_{n}t^{n}\right)-\left(p_{1}+2p_{2}t+3p_{3}t^{2}+\cdots+np_{n}t^{n-1}\right)=$
$\displaystyle(2ap_{0}+p_{1})+(2ap_{1}+2p_{2})t+(2ap_{2}+3p_{3})t^{2}+\cdots+(2ap_{n}+np_{n})t^{n-1}+2p_{n}t^{n}=0$

and $s(t+1)-s(t)-u(l_{P})(s(t))=0$ becomes:

$\displaystyle s(t+1)-s(t)-u(l_{P})(s(t))=$ $\displaystyle
s(t+1)-s(t)+\frac{\partial l_{P}}{\partial x}(s(t))=$ $\displaystyle
s(t+1)-s(t)+2as(t)=$ $\displaystyle s(t+1)+(2a-1)s(t)=$
$\displaystyle\left(p_{0}+p_{1}(t+1)+\cdots+p_{n}(t+1)^{n}\right)+\left((2a-1)p_{0}+(2a-1)p_{1}t+\cdots+(2a-1)p_{n}t^{n}\right)=$
$\displaystyle\sum_{i=0}^{n}p_{i}((t+1)^{i}+(2a-1)t^{i})=0$

Evaluated at each $t=1,2,\cdots,m$ this forms a linear Diophantine system with
$2m+1$ unique equations. There are therefore infinitely many degree $2m+2$
polynomials $s$ that satisfy these equations. We show two examples in Figure
1. As we would expect from Proposition 4, we see that each step the dynamical
system takes is in the right direction.

Figure 1:  Example integer polynomial state maps
$s(t)=p_{1}t+p_{2}t^{2}+\cdots+p_{n}t^{n}$ for $\tau=1,2,\cdots,6$. If
$l_{P}=x^{2}$ (left) and $l_{P}=2x^{2}-1$ (right) then
$(l_{P},-R[l_{P}]_{1},s,\tau)$ forms a gradient flow.

###  4.2 Experiment - Integer Gradient Descent

Although Figure 1 shows that each step the dynamical system takes is in the
right direction, these steps are too large to minimize the function, which can
cause $s$ to oscillate or diverge. In the standard domain we would mitigate
this problem by choosing a smaller step size (aka learning rate) $\alpha$ for
the dynamical system $x_{t+1}=x_{t}-\alpha\frac{\partial l_{P}}{\partial
x}(x_{t})$, but this is not possible in the integer polynomial domain since
there are no $\alpha$ between $0$ and $1$. Instead, we can simply modify the
dynamical system to instead take steps of size $1$ in the direction of the
negative gradient.

We can assess how well this method performs at finding integer minima of
arbitrary multivariate polynomials by testing it on randomly generated
polynomials. In Table 1 we show that this method consistently outperforms
random search at finding minima of polynomials that can be written as a sum of
squared terms (which are guaranteed to have both a global minimum and a global
integer minimum).

Number of Steps ($N$) |  Frequency that Integer Gradient Descent is Better than Random Search
---|---
5 | 0.740 ($\pm$ 0.019)
10 | 0.763 ($\pm$ 0.019)
50 | 0.769 ($\pm$ 0.020)
100 | 0.807 ($\pm$ 0.011)
Table 1: In this experiment we randomly generate polynomials $l_{P}$ as sums
of squared terms and use both integer gradient descent and random search to
minimize $l_{P}$. In integer gradient descent we sample a point and take $N$
steps in the gradient direction. In random search we sample $N$ points (log-
uniformly) and choose the best one. We then compute the frequency with which
gradient descent finds a better $x$ than random search. The number of
variables, terms, and coefficient values are sampled from $[1,10]$. Means and
standard errors from $100$ experiments of $10$ polynomials each are shown. The
code to run these experiments is on Github at tinyurl.com/ku3pjz56.

##  5 Discussion and Future Work

In recent years researchers have begun to study categorical generalizations of
machine learning. This research has proceeded on many fronts: Fritz (2020) and
Cho and Jacobs (2019) introduce synthetic perspectives on probability theory,
Fong et al. (2019) introduce a functorial perspective on the backpropagation
algorithm and Elliott (2018); Richard F Blute (2009); Cruttwell et al. (2021)
explore categorical formulations of automatic differentiation. Some authors
have also begun to explore categorical generalizations of classical machine
learning techniques. Cho and Jacobs (2019) introduce a generalized perspective
on Bayesian updating and Wilson and Zanasi (2021) introduce a generalized
perspective on gradient descent that can be used to learn Boolean circuits.

Despite this progress, there has been relatively little research on the
properties of these generalized algorithms. That is, although categorical
machine learning has started to gain traction, categorical learning theory is
still far behind. In this paper we aim to reduce this gap by exploring the
properties of optimizers generalized over other categories.

However, there is still much to do. For example, although we identify the
properties that a generalized optimization flow must possess in order to
converge, our construction does not distinguish between flows that converge to
minima or to arbitrary points. Furthermore, there are many variations of
gradient-based optimizers that our formulation does not capture, such as
stochastic optimizers like stochastic gradient descent and mini-batch gradient
descent.

Another potential future direction for this work is to explore generalizations
of constrained optimization. Optimization algorithms like gradient descent and
Newton’s method can be adapted to solve constrained optimization problems, and
we may be able to do the same for their generalized analogs. This may enable
us to adapt the technique for minimizing integer polynomials that we introduce
in Section 4 towards solving integer programs, which is an NP-hard problem
with an enormous number of practical applications.

We believe that this line of research will accelerate future machine learning
research by helping researchers better understand the foundational components
of the algorithms that they use. This generalized perspective may also help us
better understand the domains over which different algorithms will be
successful.

## References

  * Ang (2020) Andersen Ang.  Convergence of gradient flow.  _Course notes at UMONS_ , 2020.
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe.  _Convex Optimization_.  Cambridge University Press, March 2004.  ISBN 0521833787.  URL http://www.amazon.com/exec/obidos/redirect?tag=citeulike-20&path=ASIN/0521833787.
  * Cho and Jacobs (2019) Kenta Cho and Bart Jacobs.  Disintegration and Bayesian inversion via string diagrams.  _Mathematical Structures in Computer Science_ , 29(7):938–971, 2019.
  * Cockett et al. (2019) Robin Cockett, Geoffrey Cruttwell, Jonathan Gallagher, Jean-Simon Pacaud Lemay, Benjamin MacAdam, Gordon Plotkin, and Dorette Pronk.  Reverse derivative categories.  _arXiv e-prints arXiv:1910.07065_ , 2019.
  * Cruttwell et al. (2021) G. S. H. Cruttwell, Bruno Gavranović, Neil Ghani, Paul Wilson, and Fabio Zanasi.  Categorical foundations of gradient-based learning.  _arXiv e-prints arXiv:2103.01931_ , 2021.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of machine learning research_ , 12(7), 2011.
  * Elliott (2018) Conal Elliott.  The simple essence of automatic differentiation.  _Proceedings of the ACM on Programming Languages_ , 2(ICFP):1–29, 2018.
  * Fong and Spivak (2019) Brendan Fong and David I. Spivak.  _An Invitation to Applied Category Theory: Seven Sketches in Compositionality_.  Cambridge University Press, 2019.  doi: 10.1017/9781108668804.
  * Fong et al. (2019) Brendan Fong, David Spivak, and Rémy Tuyéras.  Backprop as functor: A compositional perspective on supervised learning.  In _2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)_ , pages 1–13. IEEE, 2019.
  * Fritz (2020) Tobias Fritz.  A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics.  _Advances in Mathematics_ , 370:107239, 2020.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Leinster (2016) Tom Leinster.  _Basic Category Theory_.  Cambridge University Press, 2016.
  * Nombre (2021) Nombre.  Does the derivative of a polynomial over an ordered ring behave like a rate of change?  2021\.  URL https://math.stackexchange.com/q/4170920.
  * Richard F Blute (2009) Robert A.G. Seely Richard F Blute, J. R. B Cockett.  Cartesian differential categories.  _Theory and Applications of Categories_ , 22(23):622–672, 2009.
  * Wilson and Zanasi (2021) Paul Wilson and Fabio Zanasi.  Reverse derivative ascent: A categorical approach to learning boolean circuits.  _Electronic Proceedings in Theoretical Computer Science_ , 333:247–260, Feb 2021.  ISSN 2075-2180.  doi: 10.4204/eptcs.333.17.  URL http://dx.doi.org/10.4204/EPTCS.333.17.

##  Appendix A Appendix - Proofs

###  A.1 Proof of Proposition 1

###### Proof.

First, we will show that the Newton’s method optimizer scheme
$NEW(l)(x)=-(\nabla^{2}l(x))^{-1}\nabla l(x)$ is invariant to invertible
linear transformations. Consider any function of the form $f(x)=Ax$ where $A$
is invertible. We have:

$\displaystyle NEW(l\circ f)(x)=$ $\displaystyle-(\nabla^{2}(l\circ
f)(x))^{-1}\nabla(l\circ f)(x)=$
$\displaystyle-A^{-1}(\nabla^{2}l(Ax))^{-1}A^{-T}A^{T}\nabla l(Ax)=$
$\displaystyle-A^{-1}(\nabla^{2}l(Ax))^{-1}\nabla l(Ax)=$
$\displaystyle-f^{-1}((\nabla^{2}l(f(x)))^{-1}\nabla l(f(x)))=$ $\displaystyle
f^{-1}(NEW(l)(f(x)))$

Next, we will show that the gradient descent optimizer scheme
$GRAD(l)(x)=\nabla l(x)$ is invariant to orthogonal linear transformations,
but not to linear transformations in general. Consider any function of the
form $f(x)=Ax$ where $A$ is an orthogonal matrix. Then the following holds
only when $A^{T}=A^{-1}$:

$\displaystyle GRAD(l\circ f)(x)=$ $\displaystyle-\nabla(l\circ f)(x)=$
$\displaystyle-A^{T}(\nabla l(Ax))=$ $\displaystyle-A^{-1}(\nabla l(Ax))=$
$\displaystyle-f^{-1}(GRAD(l)(f(x)))$

Next, we will show that the momentum optimizer scheme $MOM(l)(x,y)=(y,y+\nabla
l(x))$ is also invariant to orthogonal linear transformations, but not to
linear transformations in general. Consider any function of the form $f(x)=Ax$
where $A$ is an orthogonal matrix. Then the following holds only when
$A^{T}=A^{-1}$:

$\displaystyle MOM(l\circ f)(x,y)_{x}=y=A^{T}Ay=f^{-1}(MOM(l)(f(x),f(y)))_{x}$
$\displaystyle MOM(l\circ f)(x,y)_{y}=-y-\nabla(l\circ
f)(x))=-A^{-1}Ay-A^{T}\nabla l(Ax))=f^{-1}(MOM(l)(f(x),f(y)))_{y}$

∎

###  A.2 Proof of Proposition 2

###### Proof.

Consider starting at some point $x_{0}\in\mathbb{R}^{kn}$ and repeatedly
taking Euler steps $x_{t+\alpha}=x_{t}+\alpha u(l)(x_{t})$. Now suppose
instead that we start at the point $y_{0}=f_{k}^{-1}x_{0}$ and take Euler
steps $y_{t+\alpha}=y_{t}+\alpha u(l\circ f)(y_{t})$.

We will prove by induction that $y_{t+\alpha}=f_{k}^{-1}(x_{t+\alpha})$, and
therefore the two sequences converge at the same rate. The base case holds by
definition and by induction we can see that:

$\displaystyle y_{t+\alpha}=y_{t}+\alpha u(l\circ
f)(y_{t})=f_{k}^{-1}(x_{t})+\alpha
f_{k}^{-1}(u(l)(x_{t}))=f_{k}^{-1}(x_{t+\alpha})$

∎

###  A.3 Proof of Proposition 3

###### Proof.

Since generalized gradient descent, generalized momentum and generalized
Newton’s method all act as the identity on morphisms, we simply need to show
that each functor maps a morphism in its source category to a morphism in its
target category.

First we show that generalized Newton’s method
$NEW(l)=R[R[l]_{1}^{-1}]\circ\langle R[l]_{1},R[l]_{1}\rangle$ is a functor
out of $\mathbf{Objective}_{I}$. Given an objective $l:A\rightarrow X$ and an
invertible linear map $f:B\rightarrow A$ we have:

$\displaystyle f\circ NEW(l\circ f):B\rightarrow A$ $\displaystyle f\circ
NEW(l\circ f)=$ $\displaystyle-f\circ R[R[l\circ f]_{1}^{-1}]\circ\langle
R[l\circ f]_{1},R[l\circ f]_{1}\rangle=^{*}$ $\displaystyle-f\circ f^{-1}\circ
R[R[l]_{1}^{-1}]\circ(f^{-\dagger}\times f^{-\dagger})\circ\langle
f^{\dagger}\circ R[l]_{1}\circ f,f^{\dagger}\circ R[l]_{1}\circ f\rangle=$
$\displaystyle-R[R[l]_{1}^{-1}]\circ\langle f^{-\dagger}\circ f^{\dagger}\circ
R[l]_{1}\circ f,f^{-\dagger}\circ f^{\dagger}\circ R[l]_{1}\circ f\rangle=$
$\displaystyle-R[R[l]_{1}^{-1}]\circ\langle R[l]_{1},R[l]_{1}\rangle\circ f=$
$\displaystyle NEW(l)\circ f$

where $*$ holds by:

$\displaystyle R[R[l\circ f]_{1}^{-1}]:B\times B\rightarrow B$ $\displaystyle
R[R[l\circ f]_{1}^{-1}]=^{**}$ $\displaystyle R[f^{-1}\circ R[l]_{1}^{-1}\circ
f^{-\dagger}]=$ $\displaystyle R[f^{-\dagger}]\circ(id_{B}\times R[f^{-1}\circ
R[l]_{1}^{-1}])\circ\langle\pi_{0},\langle
f^{-\dagger}\circ\pi_{0},\pi_{1}\rangle\rangle=$ $\displaystyle f^{-1}\circ
R[f^{-1}\circ R[l]_{1}^{-1}]\circ\langle
f^{-\dagger}\circ\pi_{0},\pi_{1}\rangle=$ $\displaystyle f^{-1}\circ
R[R[l]_{1}^{-1}]\circ(id_{A}\times R[f^{-1}])\circ\langle\pi_{0},\langle
R[l]_{1}^{-1}\circ\pi_{0},\pi_{1}\rangle\rangle\circ\langle
f^{-\dagger}\circ\pi_{0},\pi_{1}\rangle=$ $\displaystyle f^{-1}\circ
R[R[l]_{1}^{-1}]\circ(id_{A}\times f^{-\dagger})\circ\langle
f^{-\dagger}\circ\pi_{0},\pi_{1}\rangle=$ $\displaystyle f^{-1}\circ
R[R[l]_{1}^{-1}]\circ(f^{-\dagger}\times f^{-\dagger})$

and where $**$ holds by:

$\displaystyle R[l\circ f]_{1}^{-1}:B\rightarrow B$ $\displaystyle R[l\circ
f]_{1}^{-1}=f^{-1}\circ R[l]_{1}^{-1}\circ R[f^{-1}]\circ(1_{A}\times
id_{B})=f^{-1}\circ R[l]_{1}^{-1}\circ f^{-\dagger}$

Next we show that generalized gradient descent $GRAD(l)=(1,A,R[l]_{1})$ is a
functor out of $\mathbf{Objective}_{\perp}$. Given an objective
$l:A\rightarrow X$ and an invertible linear map $f:B\rightarrow A$ where
$f\circ f^{\dagger}=id_{A}$ and $f^{\dagger}\circ f=id_{B}$ we have:

$\displaystyle f\circ GRAD(l\circ f):B\rightarrow A$ $\displaystyle f\circ
GRAD(l\circ f)=$ $\displaystyle-f\circ R[l\circ f]_{1}=$ $\displaystyle-f\circ
R[l\circ f]\circ\langle id_{B},1_{BX}\rangle=$ $\displaystyle-f\circ
R[f]\circ(id_{B}\times R[l]_{1})\circ\langle id_{B},f\rangle=$
$\displaystyle-f\circ f^{\dagger}\circ\pi_{1}\circ(id_{B}\times
R[l]_{1})\circ\langle id_{B},f\rangle=$
$\displaystyle-\pi_{1}\circ(id_{B}\times R[l]_{1})\circ\langle
id_{B},f\rangle=$ $\displaystyle-R[l]_{1}\circ f=$ $\displaystyle GRAD(l)\circ
f$

Next we show that generalized momentum
$MOM(l)=(1,A,\langle\pi_{1},\pi_{1}+(R[l]_{1}\circ\pi_{0})\rangle)$ is a
functor out of $\mathbf{Objective}_{\perp}$. Given an objective
$l:A\rightarrow X$ and an invertible linear map $f:B\rightarrow A$ where
$f\circ f^{\dagger}=id_{A}$ and $f^{\dagger}\circ f=id_{B}$ we have:

$\displaystyle f\circ MOM(l\circ f):B^{2}\rightarrow A^{2}$ $\displaystyle
f^{2}\circ MOM(l\circ f)=$ $\displaystyle(f\times f)\circ MOM(l\circ f)=$
$\displaystyle(f\times f)\circ\langle\pi_{1},-\pi_{1}-(R[l\circ
f]_{1}\circ\pi_{0})\rangle=$ $\displaystyle=\langle
f\circ\pi_{1},f\circ(-\pi_{1}-(R[l\circ f]_{1}\circ\pi_{0}))\rangle=$
$\displaystyle\langle f\circ\pi_{1},-f\circ\pi_{1}-(f\circ R[l\circ
f]_{1}\circ\pi_{0})\rangle=$ $\displaystyle\langle
f\circ\pi_{1},-f\circ\pi_{1}-(R[l]_{1}\circ f\circ\pi_{0})\rangle=$
$\displaystyle\langle\pi_{1},-\pi_{1}-(R[l]_{1}\circ\pi_{0})\rangle\circ(f\times
f)=$ $\displaystyle MOM(l)\circ(f\times f)=$ $\displaystyle MOM(l)\circ f^{2}$

∎

###  A.4 Proof of Proposition 4

###### Proof.

For $D_{1}[l\circ\pi_{0}\circ s]\circ t:1\rightarrow X$ we have that:

$\displaystyle D_{1}[l\circ\pi_{0}\circ s]\circ t=$ $\displaystyle
D_{1}[l\circ s]\circ t=$ $\displaystyle D[l\circ s]\circ\langle
t,1_{X}\rangle=$ $\displaystyle D[l]\circ\langle
s\circ\pi_{0},D[s]\rangle\circ\langle t,1_{X}\rangle=$ $\displaystyle
D[l]\circ\langle s,D[s]\circ\langle id_{X},1_{X}\rangle\rangle\circ t=$
$\displaystyle D[l]\circ\langle s,d\circ s\rangle\circ t=$ $\displaystyle
D[l]\circ\langle s,-R[l]\circ\langle id_{A},1_{AX}\rangle\circ s\rangle\circ
t=$ $\displaystyle-D[l]\circ\langle s,R[l]\circ\langle
s,1_{X}\rangle\rangle\circ t=$ $\displaystyle-\pi_{1}\circ
R[R[l]]\circ(\langle id_{A},1_{AX}\rangle\times id_{A})\circ\langle
s,R[l]\circ\langle s,1_{X}\rangle\rangle\circ t=$ $\displaystyle-\pi_{1}\circ
R[R[l]]\circ\langle\langle s,1_{X}\rangle,R[l]\circ\langle
s,1_{X}\rangle\rangle\circ t=$ $\displaystyle-\pi_{1}\circ
R[R[l]]\circ\langle\langle s\circ t,1_{X}\rangle,R[l]\circ\langle
s,1_{X}\rangle\rangle=$ $\displaystyle-\pi_{1}\circ R[R[l]]\circ(\langle
s\circ t,1_{X}\rangle\times id_{A})\circ R[l]\circ\langle s\circ
t,1_{X}\rangle=$ $\displaystyle-\pi_{1}\circ R[R[l]]\circ(\langle s\circ
t,1_{X}\rangle\times id_{A})\circ R[l]_{s_{t}}\circ 1_{X}=$
$\displaystyle-R[R[l]\circ\langle s\circ
t\circ!_{X},id_{X}\rangle]\circ\langle 1_{X},R[l]_{s_{t}}\rangle\circ 1_{X}=$
$\displaystyle-(R[l]\circ\langle s\circ
t\circ!_{X},id_{X}\rangle)^{\dagger}\circ\pi_{1}\circ\langle
1_{X},R[l]_{s_{t}}\rangle\circ 1_{X}=$ $\displaystyle-(R[l]\circ\langle s\circ
t\circ!_{X},id_{X}\rangle)^{\dagger}\circ R[l]_{s_{t}}\circ 1_{X}=$
$\displaystyle-R[l]_{s_{t}}^{\dagger}\circ R[l]_{s_{t}}\circ 1_{X}$

∎