source/src/sections/_II_related_work.tex

\section{Related Work}

The effectiveness of neural networks is partly due to their Universal Approximation Property (UAP): any sufficiently regular function can be approximated by a large enough neural network, whether shallow or deep. Neural networks can thus be viewed as effective parameterizations of general functions. There is a rich literature investigating the UAP for neural networks, including but not limited to \cite{hornik1989multilayer, pinkus1999approximation, liang2016deep, lu2021deep}.

However, neural networks or any universal approximators are not always the best tool for every problem, as they may disregard domain knowledge and problem structure. Exploiting inherent symmetries and structure can justify focusing on more specialized function classes.

For example, in image recognition tasks, the presence of a car in an image is a local property and is invariant to the car's position within the image. This motivates focusing on functions that are translation invariant, which leads to the use of Convolutional Neural Networks (CNNs) \cite{lecun1989backpropagation}. \cite{yarotsky2022universal} shows that CNNs are universal approximators for translation-invariant functions, which explains their effectiveness in image recognition. Similar symmetry-driven approaches have been explored in many domains; see \cite{bronstein2021geometric} for a survey.

Closer to our context is the literature on parameterizing and approximating convex functions. Perhaps the most natural scheme is the max-affine parameterization: any convex function can be represented as the supremum of possibly infinitely many affine functions (its subgradients). Choosing maximum of finitely many affine functions underlies max-affine regression, as explored in \cite{balazs2015near}. \cite{calafiore2019log} and \cite{kim2022parameterized} show how the maximum can be replaced with the Log-Sum-Exp (LSE) function to yield smooth approximations. Other works, such as \cite{warin2023groupmax} and \cite{amos2017input}, propose more sophisticated multi-layered parameterizations, while \cite{magnani2009convex} study piecewise linear convex functions.

Another line of research concerns the approximation and parameterization of gradients of functions. In contrast to the one-dimensional case, not every vector field $f: \R^n \to \R^n$ is the gradient of some scalar-valued function $g: \R^n \to \R$. If $f = \nabla g$, then the Jacobian of $f$ coincides with the Hessian of $g$: $J_f = H_g$. When $g$ is smooth, its Hessian is symmetric; therefore, a necessary condition for a vector field $f$ to be a gradient (i.e., $f = \nabla g$) is that the Jacobian of $f$ is symmetric.

A naive idea is to parametrize gradients by differentiating parametrizations of scalar functions. For example, one may use derivatives of neural networks to approximate derivatives of functions. However, this approach can fail \cite{saremi2019approximating}.

Even if $f_n \to f$, it does not necessarily follow that $\nabla f_n \to \nabla f$, as illustrated by the following example:

\begin{align*}
f_n(x) = \frac{1}{n} \sin(nx) \to 0, \qquad f'(x) = \cos(nx) \not\to 0.
\end{align*}

As discussed in Section V, this problem disappears when the functions(and their limits) are convex. \cite{chaudhari2024gradient} uses this fact to construct universal approximators for gradients of convex functions.

\cite{richter2021input} and \cite{lorraine2024jacnet} pursue a different approach by parameterizing the second derivative (the symmetric positive definite Hessian) and integrating it via neural ordinary differential equations \cite{chen2018neural}.

The above parameterizations of convex functions and their gradients can be used whenever the objective depends on a convex function or its gradient. A growing literature leverages these ideas to solve optimization problems in various domains \cite{chen2018optimal, huang2020convex, makkuva2020optimal, alvarez2021optimizing}.
% #TODO cite more applied convex

Generalized convex functions have received attention over the past 50 years. For surveys, see \cite{van1993theory, pallaschke2013foundations, singer1997abstract, rubinov2013abstract}. These functions are ubiquitous in many areas of applied mathematics, particularly in optimal transport theory and mathematical economics. After introducing GCFs in Section III, we will showcase some of their applications in Section IV. While there has been substantial work on parameterizations of convex functions and their gradients, very little has been done for GCFs. This paper aims to fill this gap by providing analogous results for parameterization and approximation of GCFs.

In the absence of such parametrizations, computational approaches to problems where the objective involves GCFs have often defaulted to more generic tools such as deep neural networks, sacrificing theoretical guarantees in the process \cite{shen2020reinforcement, pmlr-v119-deng20d, balcan2008reducing}. This historical lack of suitable numerical optimization machinery has also pushed researchers to focus on simpler problems with analytical solutions. The methods developed in this paper aim to enable the study richer problems involving GCFs via computational approaches.