source/src/sections/_I_introduction.tex

\section{Introduction}
As this paper is concerned with parameterization, we start by defining it and demonstrating how it fits into the broader optimization picture.

Consider the problem of finding a "good" one-to-one assignment $f: X \to Y$ of workers $X = \{x_1, \dots, x_n \}$ to $n$ jobs $Y = \{ y_1, \dots, y_n \}$. A "good" assignment can be defined in many ways; here we aim to maximize productivity denoted by $\Phi$: $$\sum_{x_i \in X} \Phi(x_i, f(x_i)).$$ Because searching over the space of one-to-one assignments is combinatorial, we often relax the problem by allowing fractional assignments where each worker can be assigned a distribution over jobs rather than a single job. We then parameterize the space of such assignments by doubly stochastic $n \times n$ matrices and solve the following linear program:

\begin{align*}
  \max_{\pi \in \Theta}& \sum_{i,j} \pi_{ij} \Phi(x_i, y_j)\\
  s.t. & \forall i: \quad \sum_{j} \pi_{ij} = 1, \\
       & \forall j: \quad \sum_{i} \pi_{ij} = 1, \\
       & \forall i,j: \quad \pi_{ij} \geq 0
\end{align*}

This follows a standard cookbook recipe ubiquitous in applied mathematics. The typical task is to find an object $o \in \mathcal{O}$ (the one-to-one assignment) that satisfies some criterion $C$ (assignments maximizing the productivity), i.e., finding $o \in C \subseteq \mathcal{O}$. The cookbook recipe consists of:
\begin{enumerate}
\item Potentially replacing $\mathcal{O}$ (one-to-one assignment) with another class of objects $\hat{\mathcal{O}}$ (fractional assignments) that are easier to handle.
\item Defining a parameterization scheme $p: \Theta \to \hat{\mathcal{O}}$ mapping a subset of Euclidean space $\Theta \subseteq \R^n$ (doubly stochastic matrices) to $\hat{\mathcal{O}}$ (fractional assignments).
\item Defining a gain (or loss) function $g: \hat{\mathcal{O}} \to \R$ (expected productivity) such that maximizers (or minimizers) of $g$ belong to $C$ (good assignments).
\item Solving $\max_{\theta \in \Theta} g(p(\theta))$ (the linear program above).
\end{enumerate}

For example, in the regression setting, we seek a function $f: \R^n \to \R^m$ that fits our data well. Here, $\mathcal{O} = \{f \mid f: \R^n \to \R^m\}$ and $C$ encodes the notion of a good fit. The linear regression approach consists of (1) restricting to linear functions and setting $\hat{\mathcal{O}} = \{ f \mid f(x) = Ax, A\in \R^{m \times n} \}$, (2) parameterizing them by their coefficients $\Theta = \R^{m \times n}$; (3) replacing the notion of a good fit with the minimization of regularized mean squared error; and (4) solving the resulting optimization problem.

A neural network approach differs in step (1) by taking $\hat{\mathcal{O}}$ to be the set of all functions $X \to Y$ that can be represented by a neural network of a given architecture, parameterized by the network's weights and biases.

The success of this approach hinges on a few key properties:
\begin{itemize}
\item Maximizing $g$ should lead to satisfaction of criterion $C$. For example, minimizing mean squared error should yield a good fit, although this can fail due to overfitting.
\item $\hat{\mathcal{O}}$ should cover $\mathcal{O}$; that is, for any $o \in \mathcal{O}$, there should be a parametrization $p(\theta)$ equal or close to it. In linear regression, for instance, functions in $C$ may not be well-approximated by linear functions. In the case of neural networks, the Universal Approximation Property (UAP) guarantees this will not be an issue provided $\mathcal{O}$ satisfies reasonable regularity conditions.
\item The difference $\hat{\mathcal{O}} - \mathcal{O}$ should not be too large. When nonempty, we are solving a relaxation of the original problem, which can cause two issues:
\begin{itemize}
\item The result of the optimization may not belong to $\mathcal{O}$ (e.g., in the assignment problem, the optimizer may yield a non-deterministic assignment). In that case some "rounding" procedure is needed to project the solution back to $\mathcal{O}$.
\item Optimization may become more cumbersome due to the enlarged set of alternatives. For example, in regression, using neural networks can be unnecessarily complicated if the data actually follows a linear model.
\end{itemize}
\item Local methods do a reasonable job of finding optima; for that, convexity of $\Theta$ is a must. Additional regularity of $g \circ p$ can also be helpful.
\end{itemize}

Ensuring the first property is often straightforward, as the criterion often times is defined as the maximizer of some function to begin with. The remaining points largely depend on the chosen parameterization scheme. A major reason for the success of neural networks with various architectures is that they can parameterize different function spaces in a way that satisfies these properties. We shall explore this more in Section~II.

Convex functions and their gradients are two particularly important classes of functions arising in applications. One appeal of convex functions is that they are easy to minimize: they possess subgradients everywhere, and every local minimum is global, making local methods such as gradient descent very effective. Since neural networks are not necessarily convex, using neural networks to find convex functions faces the challenges described above in point (3). As reviewed in Section~II, recent works have developed parameterizations for convex functions and their gradients.

In practice, many objects of interest are not convex, but share important characteristics with convex functions. Since the 1940s, researchers have explored relaxations of convexity that are more general but still tractable. Generalized convexity is one such concept (see \cite{singer1997abstract} for a survey). Section~III provides a primer on generalized convexity and its occurrence in optimal transport and mathematical economics.

Despite recent advances in parametrizing convex functions and their gradients, relatively little work has addressed generalized convex functions (GCFs). Consequently, numerical optimization techniques have yet to fully exploit generalized convexity. This is important because GCFs can be used to transform bilevel optimization problems into single-level ones. The goal of this paper is to address this gap by providing a parametrization scheme for GCFs and their gradients.

The remainder of the paper is organized as follows. Section II reviews the relevant literature, particularly parametrizations of convex functions and their gradients. Section III gives a brief background on convexity and generalized convexity. Section IV presents examples of generalized convexity in applications, particularly in optimal transport theory and mechanism design. Section V introduces a parametrization scheme for the space of GCFs and proves its desirable properties. Section VI then draws a parallel between the new parametrization and neural networks. Finally, Section VII applies the theory to optimal multi-object auction design, demonstrating the practical utility of the parametrization.