UNIVERSAL REPRESENTATION OF GENERALIZED CONVEX FUNCTIONS AND THEIR GRADIENTS

## Abstract

Abstract Solutions to a wide range of optimization problems, from optimal transport theory to mathematical economics, often take the form of generalized convex functions (GCFs). This characterization can be used to convert nested bilevel optimization problems into single-level optimization problems. Despite this, the characterization has not been fully exploited in numerical optimization. When the solution to an optimization problem is known to belong to a particular class of objects, this information can be leveraged by parameterizing that class of objects and optimizing over this parameterization. The hallmark of a good parameterization is the Universal Approximation Property (UAP): that is, the parameterization approximates any object in the class arbitrarily well. For example, neural networks satisfy the UAP with respect to the class of continuous functions. Building on the literature concerned with the parameterization of convex functions, we extend these ideas to GCFs. We present a convex and potentially one-to-one parameterization of GCFs and their gradients that satisfies the UAP. We also compare this class to shallow neural networks and highlight their shared characteristics. The ideas pursued here have been implemented in the Python package gconvex , available online. Using it, we tackle the problem of finding the revenue-maximizing auction for multiple goods and demonstrate how our parameterization can effectively solve this problem.

## I 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:

$$ $\displaystyle\max_{\pi\in\Theta}$ $\displaystyle\sum_{i,j}\pi_{ij}\Phi(x_{i},y_{j})$ $\displaystyle s.t.$ $\displaystyle\forall i:\quad\sum_{j}\pi_{ij}=1,$ $\displaystyle\forall j:\quad\sum_{i}\pi_{ij}=1,$ $\displaystyle\forall i,j:\quad\pi_{ij}\geq 0$ $$

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:

- 1.
Potentially replacing $\mathcal{O}$ (one-to-one assignment) with another class of objects $\hat{\mathcal{O}}$ (fractional assignments) that are easier to handle.
- 2.
Defining a parameterization scheme $p:\Theta\to\hat{\mathcal{O}}$ mapping a subset of Euclidean space $\Theta\subseteq\mathbb{R}^{n}$ (doubly stochastic matrices) to $\hat{\mathcal{O}}$ (fractional assignments).
- 3.
Defining a gain (or loss) function $g:\hat{\mathcal{O}}\to\mathbb{R}$ (expected productivity) such that maximizers (or minimizers) of $g$ belong to $C$ (good assignments).
- 4.
Solving $\max_{\theta\in\Theta}g(p(\theta))$ (the linear program above).

For example, in the regression setting, we seek a function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ that fits our data well. Here, $\mathcal{O}=\{f\mid f:\mathbb{R}^{n}\to\mathbb{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\mathbb{R}^{m\times n}\}$, (2) parameterizing them by their coefficients $\Theta=\mathbb{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:

- •
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.
- •
$\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.
- •
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:
–
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}$.
–
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.
- •
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.

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 [1] 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.

## II 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 [2, 3, 4, 5].

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) [6]. [7] 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 [8] 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 [9]. [10] and [11] show how the maximum can be replaced with the Log-Sum-Exp (LSE) function to yield smooth approximations. Other works, such as [12] and [13], propose more sophisticated multi-layered parameterizations, while [14] 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:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is the gradient of some scalar-valued function $g:\mathbb{R}^{n}\to\mathbb{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 [15].

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

$$ $\displaystyle f_{n}(x)=\frac{1}{n}\sin(nx)\to 0,\qquad f^{\prime}(x)=\cos(nx)\not\to 0.$ $$

As discussed in Section V, this problem disappears when the functions(and their limits) are convex. [16] uses this fact to construct universal approximators for gradients of convex functions.

[17] and [18] pursue a different approach by parameterizing the second derivative (the symmetric positive definite Hessian) and integrating it via neural ordinary differential equations [19].

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 [20, 21, 22, 23].

Generalized convex functions have received attention over the past 50 years. For surveys, see [24, 25, 1, 26]. 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 [27, 28, 29]. 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.

## III Background

Throughout this paper we assume $X$ and $Y$ are subsets of Euclidean spaces. We write arbitrary subsets with a tilde; for example, $\tilde{X}$ denotes an arbitrary subset of $X$. The exposition below recalls the standard facts about convex conjugation and then introduces the generalized transforms used throughout the paper.

### III.A Convexity

Let $f:\,X\to\overline{\mathbb{R}}$ be an extended-real-valued function. The Legendre transform (convex conjugate) of $f$ is the function on the dual space $X^{*}$ defined by

$$ $\displaystyle f^{*}$ $\displaystyle\,:X^{*}\to\overline{\mathbb{R}}$ $\displaystyle f^{*}$ $\displaystyle(y)=\sup_{x\in X}\{\langle x,y\rangle-f(x)\}$ $$

The Legendre transform is central to convex analysis: a function is convex if and only if it coincides with the Legendre transform (conjugate) of another function. Equivalently, each convex function may be represented as the upper envelope of its affine supporting functions (its subgradients).

In general, $f^{**}\leq f$, with equality if and only if $f$ is convex and lower semicontinuous (Fenchel–Moreau theorem). Another fundamental result is the Fenchel–Young inequality:

$$ $\displaystyle\langle x,y\rangle\leq f(x)+f^{*}(y)$ $$

with equality precisely when $y$ is a subgradient of $f$ at $x$.

These are essential properties conferred by convexity, and analogues of them will be desirable in the generalized theory.

### III.B Generalized convexity

Since the Legendre transform is defined via a supremum over affine functions, a natural generalization replaces the inner product with a more general bivariate function $\Phi:X\times Y\to\mathbb{R}$.

We also allow the supremum to be taken over a subset $\tilde{X}\subseteq X$. When $f$ is defined on $\tilde{X}$, we denote its $\tilde{X}$-transform (also called the $\tilde{X}$-conjugate) by a superscript $\tilde{X}$:

$$ $\displaystyle f^{\tilde{X}}_{\Phi}$ $\displaystyle\,:Y\to\overline{\mathbb{R}}$ $\displaystyle f^{\tilde{X}}_{\Phi}$ $\displaystyle(y)=\sup_{x\in\tilde{X}}\{\Phi(x,y)-f(x)\}$ $$

When $\Phi(x,y)=\langle x,y\rangle$ and $\tilde{X}=X$, these definitions recover the classical Legendre transform and biconjugation.

Standard convexity theory typically considers functions defined on all of $X$, but for our purposes, it is convenient to work with functions defined on arbitrary subsets. We say a function $f$ is $\tilde{X}$-convex (respectively, $\tilde{Y}$-convex) if it is the restriction of a $\tilde{X}$-transform (respectively, $\tilde{Y}$-transform) of some function $g$ to the domain of $f$:

$$ $\displaystyle f=(g^{\tilde{X}})_{|\mathrm{dom}(f)}$ $$

Let $\mathcal{C}^{\tilde{X}}(\tilde{Y})$ (respectively, $\mathcal{C}^{\tilde{Y}}(\tilde{X})$) denote the set of all $\tilde{X}$-convex functions with domain $\tilde{Y}$. Again, this coincides with the standard notion of convexity when $\Phi$ is the inner product and $\tilde{X}=X,\tilde{Y}=Y$.

Before proceeding, we establish a few properties of generalized convexity that demonstrate its similarity to standard convexity. These properties will be useful in subsequent sections.

###### Lemma 1 (Basic Properties) .

If $f,g:\tilde{X}\to\mathbb{R}$, then for all $(x,y)\in\tilde{X}\times\tilde{Y}$:

$$ $\displaystyle\Phi(x,y)\leq f^{\tilde{X}}(y)+f(x)$ $\displaystyle f^{\tilde{Y}\tilde{X}}(x)\leq f(x)$ $\displaystyle f\leq g\implies f^{\tilde{X}}\geq g^{\tilde{X}}$ $$

###### Proof.

By definition of the $\tilde{X}$-transform,

$$ $\displaystyle f^{\tilde{X}}(y)$ $\displaystyle=\sup_{x^{\prime}\in\tilde{X}}\Phi(x^{\prime},y)-f(x^{\prime})$ $\displaystyle\geq\Phi(x,y)-f(x),$ $$

which yields the first inequality.

For the second property,

$$ $\displaystyle f^{\tilde{Y}\tilde{X}}(x)$ $\displaystyle=\sup_{y\in\tilde{Y}}\Phi(x,y)-f^{\tilde{X}}(y)$ $\displaystyle\leq\sup_{y\in\tilde{Y}}f(x)=f(x),$ $$

where the inequality follows from the first property.

For the third property, if $f\leq g$ then

$$ $\displaystyle g^{\tilde{X}}(y)$ $\displaystyle=\sup_{x\in\tilde{X}}\Phi(x,y)-g(x)$ $\displaystyle\leq\sup_{x\in\tilde{X}}\Phi(x,y)-f(x)=f^{\tilde{X}}(y).$ $$

∎

The next lemma records a simple monotonicity with respect to enlarging the set over which the transform is taken.

###### Lemma 2 (Enlarging Lemma) .

If $f$ is $\tilde{Y}_{1}$-convex and $\tilde{Y}_{1}\subseteq\tilde{Y}_{2}$, then $f$ is $\tilde{Y}_{2}$-convex.

###### Proof.

If $f=(g_{1}^{\tilde{Y}_{1}})_{|\mathrm{dom}(f)}$ for some $g_{1}$ on $\tilde{Y}_{1}$, define

$$ $g_{2}(y)=\begin{cases}g_{1}(y),&y\in\tilde{Y}_{1},\\ +\infty,&y\in\tilde{Y}_{2}\setminus\tilde{Y}_{1}.\end{cases}$ $$

Then $g_{2}^{\tilde{Y}_{2}}$ restricts to the same function on $\mathrm{dom}(f)$, so $f$ is $\tilde{Y}_{2}$-convex.
∎

A useful analogue to the invariance under biconjugation property of convex functions is the following:

###### Lemma 3 (Generalized Biconjugation) .

Let $f:\,\tilde{X}\to\mathbb{R}$. Then $f$ is $\tilde{Y}$-convex if and only if

$$ $f=(f^{\tilde{Y}\tilde{X}})_{|\tilde{X}}$ $$

###### Proof.

If $f$ equals its generalized biconjugate on $\tilde{X}$ then it is, by definition, the transform of $f^{\tilde{X}}$ and hence $\tilde{Y}$-convex. Conversely, suppose $f$ is $\tilde{Y}$-convex so there is $g$ with $f=(g^{\tilde{Y}})_{|\tilde{X}}$. Applying the $\tilde{X}$-transform and then the $\tilde{Y}$-transform yields

$$ $f^{\tilde{X}}=(g^{\tilde{Y}})^{\tilde{X}}=g^{\tilde{X}\tilde{Y}}\leq g,$ $$

where the last inequality is implied by Lemma [1](https://arxiv.org/html/2509.04477v1#Thmlemma1). Restricting back to $\tilde{X}$ and taking transforms gives

$$ $(f^{\tilde{Y}\tilde{X}})_{|\tilde{X}}\geq(g^{\tilde{Y}})_{|\tilde{X}}=f,$ $$

which together with the general inequality $f^{\tilde{Y}\tilde{X}}\leq f$ proves equality.
∎

As a simple corollary, distinct $\tilde{Y}$-convex functions have distinct $\tilde{X}$-transforms.

###### Corollary 1 .

If $f,g:\,\tilde{X}\to\mathbb{R}$ are $\tilde{Y}$-convex and $f\neq g$, then $f^{\tilde{X}}\neq g^{\tilde{X}}$.

###### Lemma 1 (Basic Properties) .

###### Proof.

###### Lemma 2 (Enlarging Lemma) .

###### Proof.

###### Lemma 3 (Generalized Biconjugation) .

###### Proof.

###### Corollary 1 .

## IV Applications of Generalized Convexity

### IV.A Optimal Transport

An optimal transport problem concerns relating a distribution of mass $\mu\in\Delta(X)$ on one space to a distribution of mass $\eta\in\Delta(Y)$ on another space in a ”sensible, cost-minimizing” way. The phrase ”sensible, cost-minimizing” is intentionally broad and may be interpreted in several ways, as discussed below.

Minimizing a cost is equivalent to maximizing its negation. Hence, we work with the surplus function $\Phi(x,y)=-c(x,y)$ and frame the problem as a maximization to keep the analogy with convexity clearer.

The original problem, defined by Monge, is to find the optimal transportation map $\gamma:X\to Y$ that preserves measures:

$$ $\displaystyle\sup_{\gamma:X\to Y}$ $\displaystyle;\mathbb{E}_{\mu}[\Phi(x,\gamma(x))]$ s.t. $\displaystyle\gamma_{\#}\mu=\eta$ $$

where $\gamma_{\#}\mu$ denotes the pushforward of $\mu$ under $\gamma$.

This turned out to be a difficult problem as even the existence of measure-preserving maps is a subtle issue. For example, if $X=\{x_{1},x_{2}\}$ and $Y=\{y_{1}\}$ with uniform measures, there is no measure-preserving map.

Significant progress was made by considering a relaxation first formulated by Kantorovich: finding a transportation plan $\pi\in\Pi(\mu,\eta)$, where a coupling $\Pi(\mu,\eta)$ is the set of all joint distributions on $X\times Y$ with marginals $\mu$ and $\eta$.

The Kantorovich problem is:

$$ $\displaystyle\sup_{\pi\in\Pi(\mu,\eta)}$ $\displaystyle;\mathbb{E}_{\pi}[\Phi(x,y)]$ $$

The space of transportation plans(couplings) is weak-* compact under mild regularity conditions, which ensures the existence of an optimal plan.

Because the Kantorovich problem is a linear program, it admits a dual. The dual solutions are intimately related to generalized convexity:

$$ $\displaystyle\inf_{\phi:X\to\mathbb{R},\psi:Y\to\mathbb{R}}$ $\displaystyle\mathbb{E}_{\mu}[\phi(x)]+\mathbb{E}_{\eta}[\psi(y)]$ s.t. $\displaystyle\forall(x,y)\in X\times Y$ $\displaystyle\phi(x)+\psi(y)\geq\Phi(x,y)$ $$

We refer to $\phi$ and $\psi$ as Kantorovich potentials. A basic fact from optimal transport theory is that it is without loss to assume $\phi$ is $Y$-convex and $\psi=\phi^{X}$. To see this, let $(\hat{\phi},\hat{\psi})$ be optimal:

$$ $\displaystyle\hat{\psi}(y)$ $\displaystyle\geq\Phi(x,y)-\hat{\phi}(x)$ $\displaystyle\implies\hat{\psi}(y)$ $\displaystyle\geq\sup_{x\in X}{\Phi(x,y)-\hat{\phi}(x)}=\hat{\phi}^{X}(y)$ $$

So $\hat{\phi}^{X}\leq\hat{\psi}$, and by the Fenchel–Young inequality,

$$ $\displaystyle\Phi(x,y)\leq\hat{\phi}(x)+\hat{\phi}^{X}(y)$ $$

Thus, $\hat{\phi}^{X}$ is feasible and at least as good as $\hat{\psi}$, so we can replace $\hat{\psi}$ by $\hat{\phi}^{X}$. Similarly, we can replace $\hat{\phi}$ by $\hat{\phi}^{YX}$. The new $\phi=\hat{\phi}^{YX}$ is $Y$-convex and $\hat{\psi}=\hat{\phi}^{X}=\hat{\phi}^{XYX}=\phi^{X}$.

Hence, the Kantorovich dual problem can be rewritten as:

$$ $\displaystyle\inf_{\phi\in\mathcal{C}^{Y}(X)}\;\mathbb{E}_{\mu}[\phi(x)]+\mathbb{E}_{\eta}[\phi^{X}(y)]$ $$

Another key result from the literature is that

$$ $\displaystyle\pi(x,y)>0\implies\nabla\phi(x)=\nabla_{x}\Phi(x,y)$ $$

When $\nabla_{x}\Phi(x,\cdot)$ is a diffeomorphism, we can invert it to get the transportation map $\gamma:X\to Y$:

$$ $\displaystyle\gamma(x)=(\nabla_{x}\Phi(x,\cdot))^{-1}(\nabla\phi(x))$ $$

This diffeomorphism property, also called the twist condition, may be viewed as a relaxation of the single-crossing property (Spence–Mirrlees condition) used in mechanism design [30, 31].

Another classic result is Brenier’s theorem [32], which states that for

$$ $\displaystyle c(x,y)=\left\lVert x-y\right\rVert_{2}^{2}$ $$

the optimal transport map is gradient of a convex function.

In summary, generalized convex functions and their gradients characterize the solutions to the Kantorovich and Monge problems, respectively.

### IV.B Mathematical Economics

The following is a general setting for mechanism design problems: there are outcomes $X$, each priced according to a pricing scheme $t:X\to\mathbb{R}$. An agent has a type $y\in Y$ unknown to the seller affecting how much they value each outcome. Their utility $u(x,y)$ is the value $\Phi(x,y)$ they get from the outcome, given their type, minus their payment $t(x)$:

$$ $\displaystyle u(x,y)=\Phi(x,y)-t(x)$ $$

The buyer chooses the outcome that maximizes their utility given their type. Let’s assume $X$ to be compact so that there exists a utility maximizing outcome. The indirect utility $v:Y\to\mathbb{R}$ is the maximum utility an agent of type $y$ can secure:

$$ $\displaystyle v(y)=\max_{x\in X}{\Phi(a(x),y)-t(x)}$ $$

Hence, the indirect utility is an $X$-convex function.

The seller wants to maximize their profit (or any other objective) by choosing the optimal price function $t$. The challenge is that the buyer will respond to changes in prices and change their behavior. Hence we are dealing with a bilevel optimization problem. As bilevel optimization problems are generally hard, we use the revelation principle to simplify the problem.

By the revelation principle, regardless of our objective, it is without loss of generality to restrict attention to direct revelation incentive compatible(DRIC) mechanisms: mechanisms where agents are asked for their type and have no incentive to misreport. Any mechanism has a DRIC equivalent, that is one that generates the same indirect utility for the buyer and the same profit for the seller. Intuitively, for any mechanism, there exists a DRIC mechanism mimicking it by asking the players for their types and simulating their optimal strategy.

So we focus on finding a DRIC. Since now both the price and outcome only depend on the reported type, a DRIC is characterized by a pair of functions $(a,t)$, where $a:Y\to X$ is the allocation function deciding what outcome to assign to each type and $t:Y\to\mathbb{R}$ is the payment function deciding how much to charge each type. So the indirect utility is:

$$ $\displaystyle v(y)=\max_{\hat{y}\in Y}\Phi(a(\hat{y}),y)-t(\hat{y})$ $$

Since the mechanism is IC, we can apply the envelope theorem:

$$ $\displaystyle\nabla v(y)=\nabla_{y}\Phi(a(y),y)$ $$

When $\nabla_{y}\Phi(\cdot,y)$ is invertible, we have $a(y)=(\nabla_{y}\Phi(\cdot,y))^{-1}(\nabla v(y))$, so the outcome is determined by the gradient of the indirect utility $v$. Again, this is a relaxation of the single crossing property. Using this, we can write the payment in terms of the indirect utility:

$$ $\displaystyle t(y)=$ $\displaystyle\Phi(a(y),y)-v(y)$ $\displaystyle=$ $\displaystyle\Phi(a(y),y)-v(y_{0})+v(y_{0})-v(y)$ $\displaystyle=$ $\displaystyle\Phi(a(y),y)-v(y_{0})$ $\displaystyle-\int_{0}^{1}(y-y_{0})^{T}\nabla v(y_{0}+\lambda(y-y_{0}))\,d\lambda$ $$

Thus, any DSIC mechanism is characterized by the choice of an indirect utility function, which needs to be an $X$-convex function as pointed out earlier. The only caveat is that the indirect utility function should be non-negative; otherwise, agents will not participate(individual rationality). Therefore, for any objective, the optimization problem faced by the market maker reduces to finding a non-negative $X$-convex function that maximizes some functional, i.e the revenue.

For example, when maximizing revenue, the problem can be formulated as:

$$ $\displaystyle\max_{v\in\mathcal{C}^{X}(Y),v\geq 0}\Phi((\nabla_{y}\Phi(\cdot,y))^{-1}(\nabla v(y)),y)-v(y_{0})$ $\displaystyle+\int_{0}^{1}\nabla v(y_{0}+t(y-y_{0}))(y-y_{0})\,dt$ $$

See [33] for a more detailed discussion.

## V 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.

### V.A 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)$:

$$ $\displaystyle\mathcal{FC}^{Y}(X)=\bigcup_{\tilde{Y}\subseteq Y\land|\tilde{Y}|<\infty}\mathcal{C}^{\tilde{Y}}(X)$ $$

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 $\mathbb{R}^{\tilde{Y}}$.

In the language of the first section, we have:

$$ $\displaystyle\mathcal{O}$ $\displaystyle=\mathcal{C}^{Y}(X)$ $\displaystyle\hat{\mathcal{O}}$ $\displaystyle=\mathcal{FC}^{Y}(X)\subseteq\mathcal{O}$ $\displaystyle\Theta_{\tilde{Y}}$ $\displaystyle=\mathbb{R}^{\tilde{Y}}$ $\displaystyle p_{\tilde{Y}}:$ $\displaystyle\Theta_{\tilde{Y}}\to\mathcal{C}^{\tilde{Y}}(X)$ $\displaystyle p_{\tilde{Y}}(r)$ $\displaystyle=r^{\tilde{Y}}$ $$

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

###### Proposition 1 .

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

$$ $\displaystyle|f-g|_{\infty}<\epsilon$ $$

###### Proof.

Since $\Phi$ has a Lipschitz constant $\lambda$, for any $y_{1},y_{2}\in Y$,

$$ $\displaystyle|y_{1}-y_{2}|<\frac{\epsilon}{2\lambda}\implies|c(x,y_{1})-c(x,y_{2})|<\frac{\epsilon}{2}$ $$

Since $f$ is $Y$-convex,

$$ $\displaystyle f(x)=f^{YX}(x)=\sup{y\in Y}{c(x,y)-f^{X}(y)}$ $$

where $f^{X}$ is $X$-convex and also has Lipschitz constant $\lambda$. Thus,

$$ $\displaystyle|y_{1}-y_{2}|<\frac{\epsilon}{2\lambda}\implies|f^{X}(y_{1})-f^{X}(y_{2})|<\frac{\epsilon}{2}$ $$

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^{YX}=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

$$ $\displaystyle c(x,y)-f^{X}(y)<c(x,y_{i})-f^{X}(y_{i})+\epsilon$ $$

Therefore,

$$ $\displaystyle f^{YX}(x)$ $\displaystyle=\sup_{y\in Y}\{c(x,y)-f^{X}(y)\}$ $\displaystyle<\sup_{y_{i}\in\tilde{Y}}\{c(x,y_{i})-f^{X}(y_{i})+\epsilon\}$ $\displaystyle=f^{\tilde{Y}X}(x)+\epsilon$ $$

∎

###### Proposition 2 .

Finitely $Y$-convex functions are also $Y$-convex.

$$ $\displaystyle\mathcal{FC}^{Y}(X)\subseteq\mathcal{C}^{Y}(X)$ $$

###### Proof.

Special case of lemma 2.
∎

Combining Propositions 1 and 2 we obtain:

###### Theorem 1 .

The finitely $Y$-convex functions are dense in the space of $Y$-convex functions:

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

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

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 [16]), 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 [34] for a thorough introduction.

###### Definition 1 .

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

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.

###### Proposition 3 .

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.

###### 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.
∎

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

###### Proposition 4 .

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$.

###### Proof.

If $\Phi$ has semiconvexity constant $K$, then for any $f\in\mathcal{C}^{\tilde{Y}}(X)$,

$$ $\displaystyle f(x)+\frac{K}{2}|x|^{2}$ $\displaystyle=\sup_{y\in\tilde{Y}}{\Phi(x,y)+\frac{K}{2}|x|^{2}-g(y)}$ $$

which is the supremum of convex functions and hence convex.
∎

Using this, we have:

###### Theorem 2 .

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)$.

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:

$$ $\displaystyle\operatorname{LSE}^{\tau}(x_{1},\dots,x_{n})=\frac{1}{\tau}\ln\left(\sum_{i=1}^{n}e^{\tau x_{i}}\right)$ $$

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.

$$ $\displaystyle f^{\tilde{Y}^{\tau}}(x)=\frac{1}{\tau}\ln\sum_{y\in\tilde{Y}}e^{\tau(c(x,y)-f(y))}$ $$

###### Proposition 1 .

###### Proof.

###### Proposition 2 .

###### Proof.

###### Theorem 1 .

###### Definition 1 .

###### Proposition 3 .

###### Proof.

###### Proposition 4 .

###### Proof.

###### Theorem 2 .

### V.B 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:

$$ $\displaystyle f^{Y}(y)=\sup_{y\in[0,1]}{x+y-x}=x$ $\displaystyle g^{Y}(y)=\sup_{y\in[0,1]}{x+y-1}=x$ $$

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}}$

$$ $\displaystyle f=f^{\tilde{Y}X}$ $$

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

### V.C Convexity of the Parameter Space

Without enforcing one-to-oneness of the parametrization, the parameter space is convex as $\mathbb{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:

$$ $\displaystyle\forall x\in X\,\exists j\neq i:\;c(x,y_{i})-f(y_{i})$ $\displaystyle<$ $\displaystyle c(x,y_{j})-f(y_{j})$ $$

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\mathbb{R}^{\tilde{Y}}$ to be *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}}$:

$$ $\displaystyle\forall y\in\tilde{Y}\,\exists x_{y}\in X:\quad r^{\tilde{Y}}(x_{y})=\Phi(x_{y},y)-r(y)$ $$

The following theorem demonstrates the importance of lean parametrizations.

###### Theorem 3 .

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.

###### Proof.

If $r=(r^{X\tilde{Y}})_{|\tilde{Y}}$, then

$$ $\displaystyle r(y)$ $\displaystyle=\sup_{x\in X}{\Phi(x,y)-r^{\tilde{Y}}(x)}$ $\displaystyle=\Phi(x_{y},y)-r^{\tilde{Y}}(x_{y})$ $$

Conversely, if $r$ is lean, then

$$ $\displaystyle r^{X\tilde{Y}}(y)$ $\displaystyle=\sup_{x\in X}\{\Phi(x,y)-r^{\tilde{Y}}(x)\}$ $\displaystyle\geq\Phi(x_{y},y)-r^{\tilde{Y}}(x_{y})$ $\displaystyle=r(y)$ $$

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

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

###### Theorem 4 .

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

###### 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:

$$ $\displaystyle\forall x\in X:\Phi(x,\hat{y})-f(\hat{y})-\lambda h(\hat{y})$ $\displaystyle<$ $\displaystyle\Phi(x,y_{x})-f(y_{x})-\lambda h(y_{x})$ $$

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

$$ $\displaystyle\forall y\in\tilde{Y}:\quad\Phi(x_{\hat{y}},y)-f(y)\leq\Phi(x_{\hat{y}},\hat{y})-f(\hat{y})$ $$

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

$$ $\displaystyle\Phi(x_{\hat{y}},\hat{y})-f(\hat{y})-\lambda h(\hat{y})$ $\displaystyle<$ $\displaystyle\Phi(x_{\hat{y}},y_{x_{\hat{y}}})-f(y_{x_{\hat{y}}})-\lambda h(y_{x_{\hat{y}}})$ $$

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

$$ $\displaystyle\Phi(x_{\hat{y}},y_{\hat{x}})-f(y_{\hat{x}})\leq\Phi(x_{\hat{y}},\hat{y})-f(\hat{y})$ $$

Summing them gives:

$$ $\displaystyle 0$ $\displaystyle<\lambda(h(\hat{y})-h(y_{\hat{x}}))$ $\displaystyle\Rightarrow 0$ $\displaystyle<h(\hat{y})-h(y_{\hat{x}})$ $$

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

$$ $\displaystyle\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}})$ $$

So $g=f+h$ is not lean, which is a contradiction.
∎

###### Theorem 3 .

###### Proof.

###### Theorem 4 .

###### Proof.

## VI Comparison to Neural Networks

A shallow neural network with one hidden layer consists of an $n$-dimensional input layer $x$, a hidden layer $h$ of dimension $m$, and an output layer $o$. It can be expressed as:

$$ $\displaystyle h_{i}(x)$ $\displaystyle=\sigma(w^{i}\cdot x+b_{i}),\qquad i=1,\ldots,m$ $\displaystyle o(x)$ $\displaystyle=a(h)$ $$

Each neuron in the hidden layer computes an affine transformation of the input $x$ followed by a nonlinear activation function $\sigma$. The output layer aggregates the hidden layer outputs $h$ using an aggregation function $a$. In theory, any non-polynomial function can serve as an activation, but in practice, common choices include the ReLU, sigmoid, and tanh functions. The output layer may implement a simple sum or a more complex operation such as max pooling.

Figure: Figure 1: Comparison between finitely convex functions and neural networks: The left side shows a shallow neural network with an $n$-dimensional input layer, a single $m$-dimensional hidden layer, and a one-dimensional output layer. $\sigma$ is an arbitrary nonlinear activation function, $w^{i}$ is the weight vector for the $i$-th neuron in the hidden layer, and $b_{i}$ is the bias for the $i$-th neuron. The right side shows a $\tilde{Y}$-convex function $r^{\tilde{Y}}$with $\tilde{Y}=\{y^{1},y^{2},\dots,y^{m}\}$.

As Figure [1](https://arxiv.org/html/2509.04477v1#S6.F1) shows, this structure is similar to our definition of finitely convex functions. The key differences are: (1) the inner product is replaced by the surplus function $\Phi(\cdot,\cdot)$; (2) the activation function $\sigma$ is the identity function; and (3) the aggregation function $a$ is $\max$. It is not surprising that no additional nonlinear activation is needed in the hidden layer, since the surplus function itself may be highly nonlinear.

Therefore, the results presented in this paper can be seen from the perspective of shallow neural networks. Although in theory a sufficiently wide shallow network can approximate any function that a deep network can, in practice deep networks are often more effective. Beyond empirical evidence, theoretical work suggests reasons for this: shallow, wide networks are more prone to memorizing training data, while deep networks are more likely to extract underlying structure.

This suggests that there may be more powerful alternatives to our finitely convex functions, which could perform better in practice by trading network width for depth.

## VII Numerical Experiments

In this section, we present the numerical experiments conducted to evaluate the performance of our proposed method. We consider the problem of designing the revenue-maximizing auction involving multiple goods and a single buyer, as introduced in Section IV-B.

We know that selling goods separately is generally not optimal. In multi-product screening models, the optimal mechanism often features bundling and nonlinear pricing. For example, [35] showed that when consumers have multi-dimensional types, optimal pricing schedules may involve bundling and exclusion regions rather than independent prices for each good. [36] demonstrated that even in the two-good case, the optimal allocation exhibits “bunching,” with multiple consumer types mapped to the same contract; this implies that the optimal mechanism cannot be reduced to separate selling. [37] proved that pure bundling can strictly dominate separate selling in revenue, while [38] established that in general the optimal mechanism may require randomization over bundles, ruling out any simple deterministic scheme as fully optimal.

Beyond theoretical complications, computing optimal mechanisms poses severe numerical difficulties. The design problem is naturally a nested optimization: the seller chooses a mechanism to maximize revenue, while each buyer solves their own utility-maximization problem given the mechanism. This bilevel structure means that every candidate mechanism requires solving a second optimization, making the search problem computationally expensive. Moreover, the space of mechanisms is extremely high-dimensional as a DSIC mechanism depends on two functions $(a,t)$.

Keeping things simple and in line with the theoretical literature, we use the formalism of Section IV-B and consider the problem of selling multiple items to a single buyer. We set the outcome space $X=[0,1]^{n}$ (the probability of receiving each of the $n$ items), the type space $Y=[0,1]^{n}$ (the value the buyer has for each item), and the surplus kernel $\Phi(x,y)=\langle x,y\rangle$. We also assume that buyer types follow the uniform distribution. As discussed above, the mechanism design problem can be viewed as finding the indirect utility function, which is generalized convex. We parameterize such functions and search over them to find the best mechanism.

**TABLE I: Mechanism performance. This table reports the average per-item profit, surplus, and utility of the mechanisms found by our method. For comparison, we also report the revenue of the Straight-Jacket auction (SJa), which is known exactly only for $n\leq 12$. For all available cases, the revenuegconvex achieved by our mechanisms is virtually identical to that of SJa.**
| Number of Items | Mean Profit per Item | Revenue From SJa | Mean Surplus per Item | Mean Utility per Item |
| --- | --- | --- | --- | --- |
| 1 | 0.250 | 0.250 | 0.377 | 0.127 |
| 2 | 0.274 | 0.274 | 0.407 | 0.133 |
| 5 | 0.314 | 0.315 | 0.444 | 0.130 |
| 10 | 0.346 | 0.347 | 0.468 | 0.122 |
| 20 | 0.377 | — | 0.479 | 0.102 |

Even though the theoretical foundations discussed in this paper and supplementing code are able to tackle more complicated problems, such as the monopolist problem where seller incurs production cost or ones with non-linear surplus kernels, we refrain from them since they are not as widely understood.

We consider five cases $n\in\{1,2,5,10,20\}$. For $n\leq 6$ [39] proves that the Straight-Jacket auction (SJa) is optimal. [40] computes the revenue provided by the Straight-Jacket auction for $n\leq 12$. In particular, for $n=1,2,5,10$, the revenue is $0.25,0.549,1.576,3.478$. Table [I](https://arxiv.org/html/2509.04477v1#S7.T1) summarizes the results of our experiments. We see that the mechanisms found by our method achieve virtually identical revenue to SJa for all available cases.

Figure: (a)
Refer to caption: figs/1d_allocation.png

Figure [2](https://arxiv.org/html/2509.04477v1#S7.F2) visualizes the mechanism found for the single item case while [3](https://arxiv.org/html/2509.04477v1#S7.F3) does the same for the two item case.

Figure: (a)
Refer to caption: figs/a_1_heatmap.png

## VIII Conclusion

After providing a short review of generalized convexity and its applications, we developed a framework for parameterizing generalized convex functions. We showed that finitely $Y$-convex functions form a dense subset of all $Y$-convex functions, establishing their universal approximation property for both generalized convex functions and their gradients under mild regularity conditions. We also demonstrated that the parameterization has a convex parameter space and can be made injective.

We highlighted structural parallels between finitely convex parameterizations and shallow neural networks, suggesting that deeper analogues may offer practical advantages, as observed with deep networks in machine learning.

On the applied side, the methods presented were implemented in the [gconvex](https://github.com/MoeenNehzati/gconvex) package and used for finding revenue-maximizing mechanisms in multi-item auctions. We compared the results with existing benchmarks and found that our approach achieves virtually the same profits.

This work provides a foundation for future applied research in mathematical economics and optimal transport. Finding deep architectures for finitely convex functions and answering whether, similar to neural networks, local methods find global optima are important questions left to future work.

## References

- [1]
I. Singer, “Abstract convex analysis,” *(No Title)*, 1997.
- [2]
K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are
universal approximators,” *Neural networks*, vol. 2, no. 5, pp.
359–366, 1989.
- [3]
A. Pinkus, “Approximation theory of the mlp model in neural networks,”
*Acta numerica*, vol. 8, pp. 143–195, 1999.
- [4]
S. Liang and R. Srikant, “Why deep neural networks for function
approximation?” *arXiv preprint arXiv:1610.04161*, 2016.
- [5]
J. Lu, Z. Shen, H. Yang, and S. Zhang, “Deep network approximation for smooth
functions,” *SIAM Journal on Mathematical Analysis*, vol. 53, no. 5,
pp. 5465–5506, 2021.
- [6]
Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and
L. D. Jackel, “Backpropagation applied to handwritten zip code
recognition,” *Neural computation*, vol. 1, no. 4, pp. 541–551, 1989.
- [7]
D. Yarotsky, “Universal approximations of invariant maps by neural networks,”
*Constructive Approximation*, vol. 55, no. 1, pp. 407–474, 2022.
- [8]
M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković, “Geometric
deep learning: Grids, groups, graphs, geodesics, and gauges,” *arXiv
preprint arXiv:2104.13478*, 2021.
- [9]
G. Balázs, A. György, and C. Szepesvári, “Near-optimal max-affine
estimators for convex regression,” in *Artificial Intelligence and
Statistics*. PMLR, 2015, pp. 56–64.
- [10]
G. C. Calafiore, S. Gaubert, and C. Possieri, “Log-sum-exp neural networks and
posynomial models for convex and log-log-convex data,” *IEEE
transactions on neural networks and learning systems*, vol. 31, no. 3, pp.
827–838, 2019.
- [11]
J. Kim and Y. Kim, “Parameterized convex universal approximators for
decision-making problems,” *IEEE Transactions on Neural Networks and
Learning Systems*, vol. 35, no. 2, pp. 2448–2459, 2022.
- [12]
X. Warin, “The groupmax neural network approximation of convex functions,”
*IEEE Transactions on Neural Networks and Learning Systems*, 2023.
- [13]
B. Amos, L. Xu, and J. Z. Kolter, “Input convex neural networks,” in
*International conference on machine learning*. PMLR, 2017, pp. 146–155.
- [14]
A. Magnani and S. P. Boyd, “Convex piecewise-linear fitting,”
*Optimization and Engineering*, vol. 10, pp. 1–17, 2009.
- [15]
S. Saremi, “On approximating $\nabla f$ with neural networks,” *arXiv
preprint arXiv:1910.12744*, 2019.
- [16]
S. Chaudhari, S. Pranav, and J. M. Moura, “Gradient networks,” *IEEE
Transactions on Signal Processing*, 2024.
- [17]
J. Richter-Powell, J. Lorraine, and B. Amos, “Input convex gradient
networks,” *arXiv preprint arXiv:2111.12187*, 2021.
- [18]
J. Lorraine and S. Hossain, “Jacnet: Learning functions with structured
jacobians,” *arXiv preprint arXiv:2408.13237*, 2024.
- [19]
R. T. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud, “Neural ordinary
differential equations,” *Advances in neural information processing
systems*, vol. 31, 2018.
- [20]
Y. Chen, Y. Shi, and B. Zhang, “Optimal control via neural networks: A convex
approach,” *arXiv preprint arXiv:1805.11835*, 2018.
- [21]
C.-W. Huang, R. T. Chen, C. Tsirigotis, and A. Courville, “Potential flows:
Universal probability distributions with optimal transport and convex
optimization,” *arXiv preprint arXiv:2012.05942*, 2020.
- [22]
A. Makkuva, A. Taghvaei, S. Oh, and J. Lee, “Optimal transport mapping via
input convex neural networks,” in *International Conference on Machine
Learning*. PMLR, 2020, pp. 6672–6681.
- [23]
D. Alvarez-Melis, Y. Schiff, and Y. Mroueh, “Optimizing functionals on the
space of probabilities with input convex neural networks,” *arXiv
preprint arXiv:2106.00774*, 2021.
- [24]
M. L. van De Vel, *Theory of convex structures*. Elsevier, 1993, vol. 50.
- [25]
D. E. Pallaschke and S. Rolewicz, *Foundations of mathematical
optimization: convex analysis without linearity*. Springer Science & Business Media, 2013, vol. 388.
- [26]
A. M. Rubinov, *Abstract convexity and global optimization*. Springer Science & Business Media, 2013,
vol. 44.
- [27]
W. Shen, B. Peng, H. Liu, M. Zhang, R. Qian, Y. Hong, Z. Guo, Z. Ding, P. Lu,
and P. Tang, “Reinforcement mechanism design: With applications to dynamic
pricing in sponsored search auctions,” in *Proceedings of the AAAI
conference on artificial intelligence*, vol. 34, no. 02, 2020, pp.
2236–2243.
- [28]
Y. Deng, S. Lahaie, and V. Mirrokni, “Robust pricing in dynamic mechanism
design,” in *Proceedings of the 37th International Conference on
Machine Learning*, ser. Proceedings of Machine Learning Research, H. D. III
and A. Singh, Eds., vol. 119. PMLR,
13–18 Jul 2020, pp. 2494–2503. [Online]. Available:
[https://proceedings.mlr.press/v119/deng20d.html](https://proceedings.mlr.press/v119/deng20d.html)
- [29]
M.-F. Balcan, A. Blum, J. D. Hartline, and Y. Mansour, “Reducing mechanism
design to algorithm design via machine learning,” *Journal of Computer
and System Sciences*, vol. 74, no. 8, pp. 1245–1270, 2008.
- [30]
J. A. Mirrlees, “An exploration in the theory of optimum income taxation,”
*The review of economic studies*, vol. 38, no. 2, pp. 175–208, 1971.
- [31]
M. Spence, “Job market signaling,” in *Uncertainty in economics*. Elsevier, 1978, pp. 281–306.
- [32]
Y. Brenier, “Polar factorization and monotone rearrangement of vector-valued
functions,” *Communications on pure and applied mathematics*, vol. 44,
no. 4, pp. 375–417, 1991.
- [33]
I. Ekeland, “Notes on optimal transportation,” *Economic Theory*, pp.
437–459, 2010.
- [34]
P. Cannarsa and C. Sinestrari, *Semiconcave Functions, Hamilton—Jacobi
Equations, and Optimal Control*. Springer, 2004.
- [35]
M. Armstrong, “Multiproduct nonlinear pricing,” *Econometrica: Journal
of the Econometric Society*, pp. 51–75, 1996.
- [36]
J.-C. Rochet and P. Choné, “Ironing, sweeping, and multidimensional
screening,” *Econometrica*, pp. 783–826, 1998.
- [37]
A. M. Manelli and D. R. Vincent, “Bundling as an optimal selling mechanism for
a multiple-good monopolist,” *Journal of Economic Theory*, vol. 127,
no. 1, pp. 1–35, 2006.
- [38]
——, “Multidimensional mechanism design: Revenue maximization and the
multiple-good monopoly,” *Journal of Economic theory*, vol. 137, no. 1,
pp. 153–185, 2007.
- [39]
Y. Giannakopoulos and E. Koutsoupias, “Duality and optimality of auctions for
uniform distributions,” in *Proceedings of the fifteenth ACM conference
on Economics and computation*, 2014, pp. 259–276.
- [40]
M. Joswig, M. Klimm, and S. Spitz, “Generalized permutahedra and optimal
auctions,” *SIAM Journal on Applied Algebra and Geometry*, vol. 6,
no. 4, pp. 711–739, 2022.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: My main concern about this paper lies in its theoretical contribution. The current version appears to lack technical novelty. Specifically, Sections 3.2 and 5 seem to be a collection of properties related to generalized convexity. Could the authors provide a more detailed summary of the technical novelty and contributions?

Regarding the experimental section, the authors only conduct experiments on a few illustrative cases. I am wondering whether there are any experiments on real-world benchmarks, such as CIFAR or similar datasets.
soundness: 2
strengths: The overall framework of this paper is clear. The concept of generalized convexity could be an interesting topic for further exploration.
summary: This paper studies generalized convex functions (GCFs) and their gradients. The authors present the applications about the general GCFs, and then provide a new differentiable layer with a convex parameter space where it and its gradient are universal approximators for GCFs and their gradients
respectively. Finally, they also conduct experiments to demonstrate its effectiveness in learning optimal pricing mechanisms when selling multiple goods.
weaknesses: The theoretical contribution of this paper is limited. The work appears to summarize several properties related to generalized convexity but does not provide any particularly insightful perspectives. In addition, some important lemmas and theorems, such as Theorem 5.3, lack sufficient explanation. I believe that including several necessary remarks would be more helpful for readers.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: see the Weaknesses
soundness: 4
strengths: - It tackles an important theoretical gap by attempting to unify convex and generalized convex structures within a learnable, differentiable framew.
- The link between generalized convexity and bilevel optimization (e.g., mechanism design, optimal transport) is conceptually appealing.
- The mathematical framework, if rigorously developed, could provide a new lens for understanding structure-preserving function approximation.
summary: This paper attempts to establish a unified theory for Generalized Convex Functions (GCFs) and their gradients in the context of parameterization and universal approximation. It proposes a differentiable finite representation — finitely Y-convex functions — as an alternative to neural network architectures. The authors claim that:
- They provide universal approximation theorems for GCFs and their gradients;
- They prove gradient convergence under semiconvexity assumptions;
- They demonstrate an application to multi-item mechanism design.
weaknesses: - In the introduction, the paper argues that GCFs can transform bilevel problems into single-level optimization problems, yet all subsequent examples (e.g., mechanism design and optimal transport) already presuppose the existence of GCF representations via the Φ-transform.
This creates a circular argument:
  “We study GCFs because they simplify bilevel optimization; we know they simplify it because we assume the problem already admits a GCF form.”

- The notion of generalized convexity was formalized long ago in Singer (1997) and Rubinov (2013). The paper fails to clearly articulate whether its novelty lies in the parameterization of the function space or in an extension of existing approximation theorems. This ambiguity undermines the conceptual contribution.

- Theorem 5.1 (GCF UAP) merely asserts that “Proposition 5.1 + 5.2 ⇒ density,” yet Proposition 5.1’s proof relies on Φ being globally Lipschitz.
Since Φ is only assumed to be locally Lipschitz, there is no guarantee of a global constant on compact domains.
→ Therefore, the universal approximation claim is not rigorously established.

- If GCFs truly simplify bilevel optimization, the paper should demonstrate clear advantages under nonlinear or non-Euclidean Φ functions (e.g., adversarial or transport-type cost functions).
However, all experiments use the trivial linear Φ(x, y) = ⟨x, y⟩, which reduces to the standard convex setting.
Hence, the results fail to support the “generalized” claim.

- The manuscript, in my ability, is difficult to read and overly terse. Many claims (e.g., “we show,” “we extend”) are stated without actual derivations or rigorous proofs, which makes the paper opaque to readers outside the narrow mathematical optimization community.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: - In theorem 3.2, shouldn't it be f = (f^{XY})_X instead of f = (f^{YX})_X.
- The paper focuses on approximation of the gradient  of finite approximations to these generalized convex functions, but often, it is the parameters of the approximation that we'd like to learn using gradient methods, which is different from approximating the gradient of a generalized convex function wrt to its input. What can be said about learning the parameters  of these approximations using gradient methods?
soundness: 3
strengths: The main strength lies in its theoretical originality—generalizing convex-function parameterizations to the broader and practically relevant class of GCFs. The paper provides rigorous proofs and smooth differentiable variants, filling a gap in the literature on universal approximators for generalized convex functions and their gradients. 
Conceptually, it bridges convex analysis with neural network design, suggesting new structured architectures that preserve generalized convexity.
summary: The paper introduces a new differentiable parameterization for generalized convex functions (GCFs) and their gradients, extending prior work on convex and input-convex neural networks. It proves universal approximation results for both functions and gradients under mild semiconvexity conditions and establishes a convex parameter space that enables stable first-order optimization. The authors connect their construction to neural network architectures, interpreting finitely convex functions as shallow networks with max aggregation. 
They validate the approach on a mechanism design problem, showing it recovers known optimal auction outcomes. Overall, the work offers a unified theoretical framework linking convex analysis and learnable, structured function classes.
weaknesses: **Novelty**: This seems to be a direct extension of the work Balazs et al 2015 for convex functions. Here, the scalar product is replaced by the function $phi(x,y)$, but the results do not present any particular challenge to prove. Besides, the experimental validation choses phi to be a scalar product, so the motivation for general $phi$ in practical problems is weak.   

**Narrow empirical validation** Experiments focus solely on mechanism design and fail to demonstrate the method’s potential on broader or more recognizable machine learning tasks. The paper does not showcase improvements in adversarial training, optimal transport, or robust optimization—domains explicitly cited as motivations. As a result, the contribution may seem more mathematical than impactful for mainstream ML practice. The computational scalability and practical guidance for applying the method in high-dimensional settings remain underexplored. To strengthen the work, additional experiments on modern ML problems would be essential to illustrate the method’s real-world relevance and power.


**Clarity**: I found parts of the paper are unclear and confusing. In particular, in the section 4.2 on mechanism design and the experimental details in section 7 related to it. Specifically, I did not understand how the expected revenu of the seller is defined, why is the problem a bilevel problem, what is learned and how. A full description of the objectives to optimize, the algorithms should be provided. Although the code is provided, I could not understand it without knowing beforehand these elements. 
Also, some notions are introduced but without proper reference to the literature: in particular DRIC seems to be a standard concept in economics, but no reference is provided for it. I found section 4.2 on mechanism design a bit obscure. For instance, I don't understand how the seller maximizes their revenue by optimizing the price. What is the objective function that they optimize



**Soundness**: The proof of proposition 5.1 assumes implicitly that X,Y are compact, this was stated nowhere in the main paper.


Decision: Reject