cs.LGNov 18, 2026

Structure-Preserving Neural Approximation of Convex, Semiconvex, and Quasiconvex Functions

Authors: Yeachan Park, Yeoneung Kim

Organizations: Sejong University, 209 Neungdong-ro, Gwangjin-gu, Seoul, 05006, Seoul, South Korea · Yonsei University, 50 Yonsei-ro, Seodaemun-gu, Seoul, 03722, Seoul, South Korea

Abstract

Input convex neural networks provide a natural way to enforce convexity globally through architectural constraints. We study how this structure-preserving approximation framework extends to semiconvex, quasiconvex, and convex transformable functions. For C1,1C^{1,1} convex functions on compact convex domains, we establish the sharp W1,pW^{1,p} minimax rate m−1/dm^{-1/d} under max-affine approximation with mm affine pieces, and show that every max-affine function admits an exact bounded-width ICNN representation with complexity linear in mm. The same W1,pW^{1,p} approximation rate extends to semiconvex functions through quadratic lifting and to convex transformable functions through monotone composition. For general Lipschitz quasiconvex functions, we develop a quantitative finite-probe approximation theory based on monotone responses to affine projections and obtain a structure-preserving IqCNN with an L∞L^\infty approximation guarantee. We further show that these approximation results extend to ReLU-transferable smooth activations, including Softplus and ELU. Numerical experiments on PDE-based approximation problems compare the proposed architectures with parameter-matched MLPs and validation-tuned shape penalties, demonstrating global structural validity without penalty tuning while maintaining competitive approximation accuracy. Overall, the results identify recoverable convex latent structure as the key mechanism enabling gradient-level structure-preserving approximation beyond convexity.

Figures & tables

Explore similar work

Apr 24, 2026

SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions

Classical ReLU-based Input Convex Neural Networks (ICNNs) are equivalent to the optimal value functions of Linear Programming (LP). This intrinsic structural equivalence restricts their representational capacity to piecewise-linear polyhedral functions. To overcome this representational bottleneck, we propose the SOC-ICNN, an architecture that generalizes the underlying optimization class from LP to Second-Order Cone Programming (SOCP). By explicitly injecting positive semi-definite curvature and Euclidean norm-based conic primitives, our formulation introduces native smooth curvature into the representation while preserving a rigorous optimization-theoretic interpretation. We formally prove that SOC-ICNNs strictly expand the representational space of ReLU-ICNNs without increasing the asymptotic order of forward-pass complexity. Extensive experiments demonstrate that SOC-ICNN substantially improves function approximation, while delivering competitive downstream decision quality. The code is available at https://anonymous.4open.science/r/SOC-ICNN-4B18/.
Apr 29, 2026

Hyper Input Convex Neural Networks for Shape Constrained Learning and Optimal Transport

We introduce Hyper Input Convex Neural Networks (HyCNNs), a novel neural network architecture designed for learning convex functions. HyCNNs combine the principles of Maxout networks with input convex neural networks (ICNNs) to create a neural network that is always convex in the input, theoretically capable of leveraging depth, and performs reliably when trained at scale compared to ICNNs. Concretely, we prove that HyCNNs require exponentially fewer parameters than ICNNs to approximate quadratic functions up to a given precision. Throughout a series of synthetic experiments, we demonstrate that HyCNNs outperform existing ICNNs and MLPs in terms of predictive performance for convex regression and interpolation tasks. We further apply HyCNNs to learn high-dimensional optimal transport maps for synthetic examples and for single-cell data, where they oftentimes outperform ICNN-based neural optimal transport methods and other baselines across a wide range of setting.
May 9, 2025

On the Depth of Monotone ReLU Neural Networks and ICNNs

We study two models of ReLU\mathsf{ReLU} neural networks: monotone networks (ReLU+\mathsf{ReLU}^+) and input convex neural networks (ICNN\mathsf{ICNN}). Our focus is on expressivity, mostly in terms of depth, and our motivation is to gain a better understanding of the depth required to exactly represent functions using neural networks with ReLU activations, a subject that has received a lot of attention lately. We prove several lower bounds on the depth required to represent functions by monotone ReLU networks and ICNN\mathsf{ICNN}. For the maximum function MAXn\mathsf{MAX}_n computing the maximum of nn real numbers, we show that ReLU+\mathsf{ReLU}^+ networks cannot compute MAXn\mathsf{MAX}_n, or even approximate it. We prove a sharp lower bound of n−1n-1 on the ICNN\mathsf{ICNN} depth complexity of MAXn\mathsf{MAX}_n. We also prove depth separations between ReLU\mathsf{ReLU} networks and ICNN\mathsf{ICNN}s; for every kk, there is a depth-22 ReLU\mathsf{ReLU} network of size O(k2)O(k^2) that cannot be simulated by a depth-kk ICNN\mathsf{ICNN}. The proofs are based on deep connections between neural networks and polyhedral geometry, and also use isoperimetric properties of triangulations.