source/src/sections/_V_parametrization.tex

\section{Parametrization}
As noted in the previous section, certain optimization problems of interest can be formulated as finding a generalized convex function that maximizes a given functional.

The first step toward numerically solving such problems is to find an appropriate parameterization scheme that satisfies the Universal Approximation Property (UAP) and has a convex parameter set. It may also be desirable for the parameterization to be injective. This is non-trivial, as $\mathcal{C}^{Y}(X)$ is infinite-dimensional and not necessarily a convex set.

Due to the symmetry between $X$ and $Y$, we focus on parameterizing $\mathcal{C}^{Y}(X)$, the space of $Y$-convex functions defined over $X$. The same ideas apply to $\mathcal{C}^{X}(Y)$. Throughout, we assume both $X$ and $Y$ are compact and that the surplus $\Phi$ is locally Lipschitz. This implies that any $Y$-convex function is also Lipschitz, as it is the supremum of a family of Lipschitz functions sharing the same Lipschitz constant.

\subsection{Finite Dimensional Approximation}

We define a function to be finitely $Y$-convex if it is the $\tilde{Y}$-transform of some function where $\tilde{Y} \subseteq Y$ is finite. Denote the space of all finitely $Y$-convex functions defined over $X$ by $\mathcal{FC}^Y(X)$:
\begin{align*}
\mathcal{FC}^Y(X) = \bigcup_{\tilde{Y} \subseteq Y \land |\tilde{Y}|<\infty} \mathcal{C}^{\tilde{Y}}(X)
\end{align*}

Parametrizing $\mathcal{FC}^Y(X)$ is straightforward. Fix a finite $\tilde{Y}$. We know that $\tilde{Y}$-convex functions are the $\tilde{Y}$-transform of another function defined on $\tilde{Y}$. Thus, the space $\mathcal{C}^{\tilde{Y}}$ can be parameterized by the finite-dimensional vector space of functions $\R^{\tilde{Y}}$.

In the language of the first section, we have:

\begin{align*}
    \mathcal{O} &= \mathcal{C}^Y(X) \\
    \hat{\mathcal{O}} &= \mathcal{FC}^Y(X) \subseteq \mathcal{O} \\
    \Theta_{\tilde{Y}} &= \R^{\tilde{Y}} \\
    p_{\tilde{Y}}: &\Theta_{\tilde{Y}} \to \mathcal{C}^{\tilde{Y}}(X) \\
    p_{\tilde{Y}}(r) &= r^{\tilde{Y}}
\end{align*}

Our first theorem shows that finitely $Y$-convex functions can uniformly approximate $Y$-convex functions.

\begin{proposition}
Given any $\epsilon > 0$, there is a finite $\tilde{Y} \subseteq Y$ such that for any $Y$-convex function $f \in \mathcal{C}^Y(X)$, there exists $g \in \mathcal{C}^{\tilde{Y}}(X)$ such that
\begin{align*}
|f - g|_{\infty} < \epsilon
\end{align*}
\end{proposition}

\begin{proof}
Since $\Phi$ has a Lipschitz constant $\lambda$, for any $y_1, y_2 \in Y$,
\begin{align*}
|y_1 - y_2| < \frac{\epsilon}{2\lambda} \implies |c(x, y_1) - c(x, y_2)| < \frac{\epsilon}{2}
\end{align*}
Since $f$ is $Y$-convex,
\begin{align*}
f(x) = f^{YX}(x) = \sup{y \in Y} {c(x, y) - f^X(y)}
\end{align*}

where $f^X$ is $X$-convex and also has Lipschitz constant $\lambda$. Thus,
\begin{align*}
|y_1 - y_2| < \frac{\epsilon}{2\lambda} \implies |f^X(y_1) - f^X(y_2)| < \frac{\epsilon}{2}
\end{align*}

Since $X \times Y$ is compact and metric, it is totally bounded. So we can cover $Y$ with finitely many balls of radius $\frac{\epsilon}{2\lambda}$; let the centers be $\tilde{Y} = \{y_1, \dots, y_k\}$.

Since $\tilde{Y} \subseteq Y$, we have $f^{\tilde{Y} X} \leq f^{Y X} = f$. To show the reverse inequality, observe that any $y \in Y$ is within distance $\frac{\epsilon}{2\lambda}$ of some $y_i \in \tilde{Y}$, so

\begin{align*}
    c(x, y) - f^X(y) < c(x, y_i) - f^X(y_i) + \epsilon
\end{align*}

Therefore,

\begin{align*}
    f^{YX}(x) &= \sup_{y \in Y} \{c(x, y) - f^X(y)\} \\
              &< \sup_{y_i \in \tilde{Y}} \{c(x, y_i) - f^X(y_i) + \epsilon\} \\
              &= f^{\tilde{Y} X}(x) + \epsilon
\end{align*}
\end{proof}


\begin{proposition}
Finitely $Y$-convex functions are also $Y$-convex.

\begin{align*}
\mathcal{FC}^Y(X) \subseteq \mathcal{C}^Y(X)
\end{align*}

\end{proposition}
\begin{proof}
    Special case of lemma 2.
\end{proof}
% check numebering of lemmas and theorems
Combining Propositions 1 and 2 we obtain:

\begin{theorem}
The finitely $Y$-convex functions are dense in the space of $Y$-convex functions:

\begin{align*}
\overline{\mathcal{FC}^Y(X)} = \mathcal{C}^Y(X)
\end{align*}

Hence, our parameterization of $\mathcal{FC}^Y(X)$ is a universal approximator for $\mathcal{C}^Y(X)$.
\end{theorem}

This may not be enough, as sometimes we need to approximate the gradients of $Y$-convex functions, and approximating a function does not necessarily imply approximating its gradient.

As shown in the literature (see \cite{chaudhari2024gradient}), if $f_n \to f$ and all $f_n$ and $f$ are convex, then $\nabla f_n \to \nabla f$ where the gradient exists. We extend this result to a larger class of functions, namely semiconvex functions; see \cite{cannarsa2004semiconcave} for a thorough introduction.

\begin{definition}
A function $f: X \to \overline{\R}$ is semiconvex if there exists a constant $K \in \R^+$ such that $f + \frac{K}{2} |x|^2$ is convex.
\end{definition}

This is a much weaker condition than convexity. For example, any continuously twice differentiable function is semiconvex on a compact domain. Intuitively, semiconvexity only requires the absence of downward kinks, since any finite negative curvature can be compensated by adding a sufficiently large positive quadratic term.

\begin{proposition}
If $f_n \to f$ uniformly and all $f_n$s and $f$ are semiconvex with the same constant $K$, then $\nabla f_n \to \nabla f$ uniformly where the gradients exist.
\end{proposition}
\begin{proof}
We can rely on the results concerning convex functions. Define $h_n(x) = f_n(x) + K|x|^2$ and $h(x) = f(x) + K|x|^2$. Then $h_n$ and $h$ are convex, so $\nabla h_n \to \nabla h$ uniformly where defined. Since $\nabla f_n = \nabla h_n - K \nabla |x|^2$ and $\nabla f = \nabla h - K \nabla |x|^2$, we obtain $\nabla f_n \to \nabla f$ uniformly where the gradients exist.
\end{proof}

Hence, a natural question is: Are $Y$-convex functions semiconvex?

\begin{proposition}
If $\Phi: X \times Y \to \mathbb{R}$ is semiconvex with constant $K$, then all $\tilde{Y}$-convex functions are semiconvex with the same constant $K$.
\end{proposition}
\begin{proof}
If $\Phi$ has semiconvexity constant $K$, then for any $f \in \mathcal{C}^{\tilde{Y}}(X)$,
\begin{align*}
f(x) + \frac{K}{2} |x|^2 &= \sup_{y \in \tilde{Y}} {\Phi(x, y) + \frac{K}{2} |x|^2 - g(y)}
\end{align*}
which is the supremum of convex functions and hence convex.
\end{proof}

Using this, we have:

\begin{theorem}
If $\Phi$ is semiconvex, then $\nabla \mathcal{FC}^Y(X) = \{\nabla f : f \in \mathcal{FC}^Y(X)\}$ is dense in $\nabla \mathcal{C}^Y(X) = \{ \nabla f : f \in \mathcal{C}^Y(X)\}$.

$$\overline{\nabla \mathcal{FC}^Y(X)} = \nabla \mathcal{C}^Y(X)$$

In other words, $\nabla \mathcal{FC}^Y(X)$ are universal approximators for $\nabla \mathcal{C}^Y(X)$.
\end{theorem}

Hence, we can approximate both $Y$-convex functions and their gradients with finitely $Y$-convex functions, generalizing the classic result that convex functions and their gradients can be approximated by max-affine functions and their derivatives.

Since finitely $Y$-convex functions are defined as a finite maximum, they are not smooth. For certain applications, we may prefer to work with smoothed versions. In the standard convex setting, some recent works have focused on replacing the maximum in max-affine regression with a smooth approximation, the log-sum-exp function $\operatorname{LSE}$ and retain the UAP:
%TODO prove this
\begin{align*}
\operatorname{LSE}^\tau(x_1, \dots, x_n) = \frac{1}{\tau} \ln \left( \sum_{i=1}^n e^{\tau x_i} \right)
\end{align*}

where $\tau$ is the temperature parameter and $\operatorname{LSE}^\tau \to \max$ as $\tau \to \infty$. Working with this smoothed version has the advantage of a known gradient and Hessian.

It can be shown that the same ideas apply to $Y$-convex functions: UAP is retained when the maximum in the definition of $FC^Y(X)$ is replaced with $\operatorname{LSE}^\tau$ of a high enough temperature.

\begin{align*}
f^{\tilde{Y}^\tau}(x) = \frac{1}{\tau} \ln \sum_{y \in \tilde{Y}} e^{\tau (c(x, y) - f(y))}
\end{align*}

\subsection{One-to-One Parametrization}

As a first observation, note that the $\tilde{Y}$-transform is not injective. For example, let $\Phi: [0,1]^2 \to \mathbb{R}$ be given by $\Phi(x, y) = x + y$ and consider $f, g: [0,1] \to \mathbb{R}$ defined by $f(y) = y$ and $g(y) = 1$. Then:
\begin{align*}
f^Y(y) = \sup_{y \in [0,1]} { x + y - x } = x \\
g^Y(y) = \sup_{y \in [0,1]} { x + y - 1 } = x
\end{align*}
Thus, two different parametrizations can represent the same function.

From Lemma 1, we know that $\tilde{Y}$-transform is injective on $X$-convex functions. It's also surjective since for any $f \in \mathcal{C}^{\tilde{Y}(X)}$ we have:
$f^{\tilde{Y} X} = g^{\tilde{Y} X \tilde{Y}}$
\begin{align*}
    f = f^{\tilde{Y} X}
\end{align*}

Therefore, setting $\Theta_{\tilde{Y}} = \mathcal{C}^{X}(\tilde{Y})$ makes the parameterization one-to-one. 

\subsection{Convexity of the Parameter Space}
Without enforcing one-to-oneness of the parametrization, the parameter space is convex as $\R^{\tilde{Y}}$ is is convex. We will show that convexity still holds after restricting to $C^{X}(\tilde{Y})$. When $\tilde{Y}$ is finite, the $\tilde{Y}$-transform of a function $f$ takes the maximum over a family of functions $c(\cdot, y_i) - f(y_i)$. The maximum is insensitive to changes in arguments that are always dominated by others. For example, if for $i$ we have:

\begin{align*}
\forall x \in X \, \exists j \neq i:\; c(x, y_i) - f(y_i) &<\\
c(x, y_j) - f(y_j)&
\end{align*}

one can perturb the value of $f(y_i)$ without affecting the resulting function, yielding a different parametrization of the same function.

Motivated by this, we define a $\tilde{Y}$-parameterization $r \in \R^{\tilde{Y}}$ to be \emph{lean} if $r^{\tilde{Y}}$ depends on the values of $r$ for all $y \in \tilde{Y}$. In other words, no $\Phi(\cdot, y) - r(y)$ is strictly dominated everywhere by $r^{\tilde{Y}}$:

\begin{align*}
\forall y \in \tilde{Y}\, \exists x_y \in X: \quad r^{\tilde{Y}}(x_y) = \Phi(x_y, y) - r(y)
\end{align*}

The following theorem demonstrates the importance of lean parametrizations.

\begin{theorem}
If the supremum in the $X$-transform is attained (for example, when $X$ is compact), then a $\tilde{Y}$-parametrization $r$ is lean if and only if $r = (r^{X \tilde{Y}})_{| \tilde{Y}}$, that is, $r$ is $X$-convex.
\end{theorem}

\begin{proof}
If $r = (r^{X \tilde{Y}})_{| \tilde{Y}}$, then
\begin{align*}
r(y) &= \sup_{x \in X} { \Phi(x, y) - r^{\tilde{Y}}(x) } \\
&= \Phi(x_y, y) - r^{\tilde{Y}}(x_y)
\end{align*}

Conversely, if $r$ is lean, then
\begin{align*}
    r^{X \tilde{Y}}(y) &= \sup_{x \in X} \{ \Phi(x, y) - r^{\tilde{Y}}(x) \} \\
    &\geq \Phi(x_y, y) - r^{\tilde{Y}}(x_y) \\
    &= r(y)
\end{align*}

Since from Lemma 1 we already have the other direction of the inequality, we can conclude $r = (r^{X \tilde{Y}})_{| \tilde{Y}}$
\end{proof}

Hence, we can work with leanness instead of $X$-convexity for parametrizations.

\begin{theorem}
The lean subset of $\mathcal{C}^{\tilde{Y}}(X)$ is a convex set.
\end{theorem}

\begin{proof}
Take $f,g \in \mathcal{C}^{\tilde{Y}}(X)$. We'll show $(1-\lambda) f + \lambda g$ is lean for $\lambda \in (0,1)$. Assume it's not. Define $h = g-f$ so

$$(1-\lambda)f + \lambda g = f + \lambda h$$

Since it's not lean, there exists $\hat{y}$ such:

\begin{align*}
\forall x \in X: \Phi(x, \hat{y}) - f(\hat{y}) - \lambda h(\hat{y}) &<\\
\Phi(x, y_x) - f(y_x) - \lambda h(y_x)&
\end{align*}

On the other hand, since $f$ is lean, $\hat{y}$ matters for some $x_{\hat{y}}$ such that

\begin{align*}
\forall y \in \tilde{Y}:\quad \Phi(x_{\hat{y}}, y) - f(y) \leq \Phi(x_{\hat{y}}, \hat{y}) - f(\hat{y})
\end{align*}

Plugging $x=x_{\hat{y}}$ into the first inequality to get:

\begin{align*}
    \Phi(x_{\hat{y}}, \hat{y}) - f(\hat{y}) - \lambda h(\hat{y}) &< \\
    \Phi(x_{\hat{y}}, y_{x_{\hat{y}}}) - f(y_{x_{\hat{y}}}) - \lambda h(y_{x_{\hat{y}}})&
\end{align*}

and $y = y_{\hat{x}}$ into the second, we get:

\begin{align*}
\Phi(x_{\hat{y}}, y_{\hat{x}}) - f(y_{\hat{x}}) \leq \Phi(x_{\hat{y}}, \hat{y}) - f(\hat{y})
\end{align*}

Summing them gives:

\begin{align*}
0 &< \lambda (h(\hat{y}) - h(y_{\hat{x}})) \\
\Rightarrow 0 &< h(\hat{y}) - h(y_{\hat{x}})
\end{align*}

So $(1-\lambda)(h(\hat{y}) - h(y_{\hat{x}}))$ is positive. Adding it to the first inequality, we have:

\begin{align*}
\Phi(\hat{x}, \hat{y}) - f(\hat{y}) - h(\hat{y}) < \Phi(\hat{x}, y_{\hat{x}}) - f(y_{\hat{x}}) - h(y_{\hat{x}})
\end{align*}

So $g = f + h$ is not lean, which is a contradiction.
\end{proof}