arXiv:2604.22355v1 [cs.LG] 24 Apr 2026
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Kang Liu 1 Jianchen Hu 1 2 Abstract A standard paradigm is to learn a parameterized convex surrogate fΘ (x) and subsequently solve the downstream Classical ReLU-based Input Convex Neural Nettask: works (ICNNs) are equivalent to the optimal value min fΘ (x), (1) functions of Linear Programming (LP). This inx∈X trinsic structural equivalence restricts their repwhere X is a feasible set and Θ denotes the network paramresentational capacity to piecewise-linear polyeters. For the widely used ReLU-ICNN, while prior literhedral functions. To overcome this representaature has observed connections between its forward pass tional bottleneck, we propose the SOC-ICNN, an and linear programming (LP) (Amos et al., 2017), we take architecture that generalizes the underlying opa step further to rigorously formalize finite-width ReLUtimization class from LP to Second-Order Cone ICNNs as exact LP value-function networks. In this view, Programming (SOCP). By explicitly injecting posthe network output identically equals the optimal value of itive semi-definite curvature and Euclidean norma parameterized LP. This perspective clarifies both their based conic primitives, our formulation introstructural strength (the natural representation of continuous duces native smooth curvature into the represenpiecewise-linear (CPWL) convex polyhedra) and their funtation while preserving a rigorous optimizationdamental intrinsic limitation: they cannot natively encode theoretic interpretation. We formally prove that smooth curvature or non-polyhedral conic geometries, such SOC-ICNNs strictly expand the representational as Euclidean norms. More critically, this CPWL confinespace of ReLU-ICNNs without increasing the ment implies a severe parameter inefficiency: as we later asymptotic order of forward-pass complexity. Exquantify, approximating even a simple quadratic function tensive experiments demonstrate that SOC-ICNN to high accuracy forces a ReLU-ICNN to approximate the substantially improves function approximation, input space with an exponentially growing number of linear while delivering competitive downstream decipieces. Recent theoretical work further substantiates this by sion quality. The code is available at https: proving lower bounds on the depth complexity of ICNNs //github.com/Kanyooo/SOC-ICNN. and characterizing the exact conditions under which a ReLU network can be convex (Gagneux et al., 2025; Bakaev et al., 2025).
Keywords: Input Convex Neural Networks, Value Function, Linear Programming, Second-Order Cone Programming
1 School of Future Technology, Xi’an Jiaotong University, Xi’an, China 2 School of Automation Science and Engineering, Xi’an Jiaotong University, Xi’an, China. Correspondence to: Jianchen Hu <[email protected]>.
Recent research has sought to improve ICNN expressivity predominantly along two lines. The first line enriches local nonlinearities, for instance, by employing smoother activations (e.g., Softplus) or learnable univariate basis functions, as seen in Input Convex Kolmogorov-Arnold Networks (ICKAN) (Deschatre & Warin, 2025). The second line focuses on improving trainability through tailored initialization schemes or architectural adaptations (Hoedt & Klambauer, 2023). While these approaches enhance empirical flexibility and training stability, they incur a fundamental trade-off: by departing from the ReLU-based piecewise-linear structure, they sacrifice the exact valuefunction interpretation that gives ReLU-ICNNs their transparent optimization-theoretic grounding. Moreover, they remain strictly confined within approximation frameworks that cannot exactly represent non-polyhedral convex sets like Euclidean norm balls.
Preprint. April 27, 2026.
Another relevant trajectory builds upon differentiable con-
1. Introduction Input Convex Neural Networks (ICNNs) rigorously guarantee the convexity of their outputs with respect to specified inputs. Unlike generic black-box models, a convex surrogate enables tractable and exact global optimization over the decision variables, which is a critical advantage in downstream applications such as structured prediction, inverse optimization, optimal transport, and parametric decision-making (Amos et al., 2017; Makkuva et al., 2020; Rosemberg et al., 2024).
1
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
vex optimization layers, where a convex program is explicitly embedded as a neural network layer and differentiated via its solution map (Agrawal et al., 2019; Besançon et al., 2024). More recently, Learning Parametric Convex Functions (PCF) has been proposed to fit disciplinedprogramming-compatible convex families directly from data (Schaller et al., 2025). While these methods successfully output optimal decisions for given parameters, they intrinsically rely on solver-in-the-loop routines during inference, thereby incurring substantially higher computational overhead than direct feed-forward evaluation. Furthermore, they often require the optimization template or disciplined structure to be specified a priori.
The remainder of this paper is organized as follows: Section 2 reviews related work. Section 3 details the architectural design of the proposed SOC-ICNN. Section 4 provides a rigorous theoretical analysis. Finally, Section 5 presents extensive empirical evaluations, followed by conclusions in Section 6.
2. Related Work ICNNs and their expressive extensions. ICNNs were introduced in (Amos et al., 2017) as neural architectures with built-in input convexity, including both fully input-convex and partially input-convex constructions, thereby enabling optimization-aware prediction and inference. Since then, ICNNs have been used as structured convex surrogates in applications such as optimal transport (Makkuva et al., 2020), value-function learning for optimal power flow (Rosemberg et al., 2024), two-stage stochastic programming (Liu et al., 2025), and power system contingency screening with provable reliability guarantees (Christianson et al., 2025).
In this paper, we pursue a fundamentally different structural route that overcomes the limitations of both local-nonlinearity enhancements and solver-dependent approaches. Since ReLU-ICNNs are strictly LP value-function networks, a natural question arises: Can we elevate the architecture to a richer convex optimization class while strictly preserving both the transparent optimization interpretation and rapid forward inference? Among mathematical programming extensions beyond LP, Second-Order Cone Programming (SOCP) emerges as the most rigorous and natural candidate. It elegantly unifies quadratic curvature and normbased geometry, which together cover a vast class of smooth and structured convex objectives. Motivated by this, we propose the SOC-ICNN, which augments the polyhedral ReLU backbone with two explicit geometric primitives: (1) quadratic branch to inject positive semi-definite (PSD) curvature: α2 ∥Bx+e∥22 . (2) conic branch to capture Euclidean norm geometry: λ∥Ax + d∥2 .
A central limitation of finite-width ReLU-ICNNs, however, is that their representable class is tied to polyhedral, piecewise-linear convex functions. Existing work has mainly addressed this limitation by enriching the parameterization or extending the backbone within the ICNN framework. One line adapts ICNNs to sequential and controloriented settings, including input-convex recurrent models for optimal control (Chen et al., 2019), input-convex LSTM architectures for real-time optimization (Wang et al., 2023), and recurrent variants that further incorporate Lipschitz constraints for robustness and efficient process modeling (Wang et al., 2024). Another line enriches the internal parameterization of input-convex models. In particular, ICKAN (Deschatre & Warin, 2025) introduces learnable univariate basis functions into input-convex architectures, improving empirical flexibility beyond standard ReLU-based constructions. Concurrently, theoretical investigations have characterized the necessary and sufficient conditions under which a ReLU network is convex (Gagneux et al., 2025), and have established lower bounds on the depth complexity of ICNNs, highlighting fundamental expressivity limitations (Bakaev et al., 2025).
Because both primitives are convex, their non-negative linear combination strictly preserves convexity. Crucially, each primitive admits a SOCP epigraph lift. Consequently, the entire forward pass of the network can be mathematically formulated as the optimal value of a finite-dimensional SOCP. The proposed SOC-ICNN therefore constitutes an architectural upgrade from LP to SOCP, simultaneously breaking the parameter-inefficient CPWL bottleneck and retaining a rigorous optimization-theoretic interpretation. The primary contributions of this paper are twofold:
While these approaches enlarge the practical approximation power of ICNNs, they do not explicitly upgrade the underlying optimization-theoretic structure beyond the LP/polyhedral regime. In contrast, our goal is not merely to enrich the local nonlinearity or change the network backbone, but to lift the value-function class itself, moving from LP value functions to SOCP value functions.
1. Architectural generalization: We propose SOCICNN, systematically elevating the underlying mathematical structure of ICNNs from LP to SOCP value functions by explicitly injecting curvature and conic geometric primitives. 2. Theoretical guarantees: We formally prove that the SOC-ICNN strictly expands the representational function class of classical ReLU-ICNNs, doing so without increasing the asymptotic order of forward-pass computational complexity.
Parametric convex models and differentiable convex programs. Another related line of work builds optimizationaware models by embedding or learning convex programs 2
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
directly. Early work such as OptNet (Amos & Kolter, 2017) introduced differentiable optimization layers based on quadratic programs. Differentiable convex optimization layers then generalized this idea to disciplined convex programs and cone programs, including SOCPs (Agrawal et al., 2019), and DiffOpt (Besançon et al., 2024) further develops this perspective through differentiable optimization via model transformations. More recently, BPQP (Pan et al., 2024) introduces a differentiable convex optimization framework that reformulates the backward pass as a decoupled quadratic program for enhanced efficiency, and comprehensive surveys have synthesized developments at the intersection of optimization theory and deep learning (Katyal, 2024). Learning Parametric Convex Functions (PCF) has been proposed to fit disciplined-programming-compatible convex families directly from data (Schaller et al., 2025), and very recent work explores constructing convex surrogates for parametric nonconvex optimization via compositions of convex and monotonic terms (Wang et al., 2026).
optimal value of the following linear program: fReLU (x) = min
{zℓ }L ℓ=1
s.t. zℓ ≥ Wℓ x + Uℓ zℓ−1 + bℓ ,
Proof sketch. The equivalence is straightforward. Since the ReLU activation operates as σ(a) = max{a, 0} elementwise, the forward pass inherently computes the componentwise minimum feasible solution satisfying the linear inequalities above. Because the output weights are nonnegative (c ≥ 0), the objective function is monotonically non-decreasing with respect to zL . By induction, this smallest feasible solution optimally minimizes the objective, rendering the LP optimum identical to the network’s forward value. The details are given in Appendix A.1. Proposition 1 reveals that finite-width ReLU-ICNNs are polyhedral value-function models. Consequently, to systematically enhance their representational capacity while strictly preserving this transparent value-function interpretation, the most principled direction is to enlarge the underlying optimization class (e.g., from LP to SOCP) rather than heuristically modifying the activation functions. 3.2. Fundamental Limitations of LP Value Functions To understand the representational bottleneck of classical architectures, we first rigorously define their hypothesis space. Because the forward pass of a ReLU-ICNN equals the optimal value of the parametric LP in (3), the resulting function fReLU (x) is intrinsically confined to be continuous, convex, and piecewise linear (CPWL). The following proposition formalizes this structural limitation. Proposition 2 (CPWL structure). Any finite-depth, finitewidth ReLU-ICNN represents a function fReLU : Rd0 → R that can be written exactly as a finite max-affine convex function: fReLU (x) = max a⊤ (4) j x + βj ,
3. Method This section introduces the proposed SOC-ICNN by first formalizing ReLU-ICNNs as LP value functions. We then rigorously expose the fundamental representational bottleneck of this LP class so that we elevate the backbone to SOCP and finally prove its exact SOCP formulation. 3.1. ReLU-ICNN as an LP value-function backbone Given an input x ∈ Rd0 , a standard ReLU-ICNN is defined recursively by zℓ = σ(Wℓ x + Uℓ zℓ−1 + bℓ ) , ℓ = 1, . . . , L, where z0 = 0, σ(t) = max{t, 0} acts elementwise, and the nonnegativity weights Uℓ ≥ 0, c ≥ 0 are imposed elementwise1 . The output is
j∈J
where J is a finite index set representing the number of linear regions. In particular, fReLU is strictly continuous, convex, and piecewise linear.
(2)
Proof sketch. Dualizing the LP in (3) yields a linear maximization problem over a bounded polyhedron (the boundedness follows from the non-negative chain constraints ⊤ 0 ≤ νL ≤ c and 0 ≤ νℓ ≤ Uℓ+1 νℓ+1 , where νℓ are dual multiplies). Since a linear function over a polyhedron attains its maximum at an extreme point, and the number of extreme points is finite, the primal value function is the maximum of finitely many affine functions. A complete derivation is provided in Appendix A.3.
Under this construction, the forward pass of a ReLU-ICNN can be mathematically interpreted as the optimal value of a parameterized linear program. Proposition 1 (LP Value-Function Representation). For any input x, the output fReLU (x) is exactly equal to the 1
Uℓ =
a c
b d
(3)
z0 = 0, zℓ ≥ 0, ℓ = 1, . . . , L.
These methods typically begin from a prescribed optimization template and rely on differentiating through the corresponding solution map or learning a disciplinedprogramming-compatible expression tied to a solver layer. By contrast, we construct a direct feed-forward architecture whose forward pass itself admits an exact SOCP valuefunction interpretation, thereby lifting ICNNs from polyhedral LP geometry to conic SOCP geometry while retaining fast inference.
fReLU (x) = c⊤ zL + v ⊤ x + b0 .
c⊤ zL + v ⊤ x + b0
≥ 0 means that a, b, c, d are nonnegative.
3
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
p the diameter diam(Pi ) ≤ 4 ε/µ. The isodiametric inequality (which states that among all measurable sets of a given diameter, the Euclidean ball has the maximal volume) then impliespthe volume of each piece is bounded: d0 vol(Pi ) ≤ ωd0 (2 ε/µ)p . Summing over all N pieces gives vol(Ω) ≤ N ωd0 (2 ε/µ)d0 , which rearranges to (8). A complete proof is provided in Appendix A.4.
Regional Flat Limitation. An immediate consequence of Proposition 2 is a strict polyhedral description of the subgradients. For any input x and any subgradient g ∈ ∂fReLU (x), L X g=v+ Wℓ⊤ νℓ , (5) ℓ=1
where {νℓ } are confined to the fixed polyhedral constraints specified in (23). This reveals a critical flaw: the gradient mapping x 7→ ∂fReLU (x) is piecewise constant (i.e., its Jacobian is zero almost everywhere). Consequently, all firstorder curvature information is lost—the function is locally flat on each linear region, and any second-order derivative is identically zero wherever defined.
This lower bound formally establishes the curse of dimensionality for classical ICNNs: Any finite-width ReLU-ICNN must utilize at least Ω(ε−d0 /2 ) affine pieces to approximate a smooth, curved convex surface to an accuracy of ε. The exponent d0 /2 is intrinsic to the geometry of polyhedral approximation, forcing the required network width/depth to explode as the target curvature µ or dimension d0 increases.
The regional flat limitation identified above leads to a severe quantitative bottleneck. Since a ReLU-ICNN is a collection of flat hyperplanes, approximating a target with smooth curvature (e.g., a strongly convex function) requires infinite hyperplanes. The following proposition quantifies the exponential parameter cost (in terms of the number of linear pieces N ) requirement.
These fundamental limitations motivate a decisive structural upgrade. Rather than combating the CPWL bottleneck with heuristic modifications as in (Deschatre & Warin, 2025), we directly enlarge the underlying optimization class from LP to SOCP. By explicitly injecting curvature and conic primitives, we equip the network with native capacity to represent smooth and non-polyhedral geometries without suffering exponential parameter blowup.
Proposition 3 (CPWL lower bound for strongly convex targets). Let Ω ⊂ Rd0 be a compact convex set with nonzero volume vold0 (Ω) > 0, and let the target f : Ω → R be µ-strongly convex on Ω. If a CPWL function g(x) = max a⊤ (6) i x + bi
3.3. SOC-ICNN Architecture The fundamental limitation of LP value functions is their purely polyhedral geometry. To overcome this, we augment the standard ReLU-ICNN backbone with two explicit structural primitives. From a neural network perspective, this results in a topology where the input x is processed through three parallel computational branches before being aggregated. Also, the Convolutional SOC-ICNN extensions are provided in Appendix C.
1≤i≤N
composed of N affine pieces satisfies the uniform error bound ∥f − g∥L∞ (Ω) ≤ ε, (7) then the number of required pieces N is strictly lowerbounded by N≥
vold0 (Ω) µ d0 /2 , ωd0 2d0 ε
(8)
Quadratic primitive. For each h = 1, . . . , H, we introduce a quadratic branch defined as
where ωd0 = vold0 (B2d0 ) is the volume of the Euclidean unit ball in Rd0 .
αh 2 ∥Bh x + eh ∥2 , 2
Proof sketch. Recall that a function f is µ-strongly convex on Ω if for all x, y ∈ Ω and t ∈ [0, 1],
αh ≥ 0,
(9)
where Bh ∈ Rmh ×d0 and eh ∈ Rmh . Architecturally, this branch applies a learnable affine transformation to the input, routes the resulting vector through a squared ℓ2 -norm pooling operator, and scales it by a non-negative learnable weight αh . This term provides an explicit PSD curvature primitive. Figure 1 illustrates the detailed data flow.
µ f (tx+(1−t)y) ≤ tf (x)+(1−t)f (y)− t(1−t)∥x−y∥22 . 2 Let Ai = {x ∈ Ω : g(x) = a⊤ i x + bi } be the active region of the i-th affine piece. These sets cover Ω. By eliminating overlaps, we construct a measurable partition F Pi ⊆ Ai such that Ω = i Pi . For any x, y ∈ Ai , applying the strong convexity condition to the midpoint m = (x + y)/2 and using the uniformperror bound ∥f − g∥L∞ (Ω) ≤ ε yields ∥x − y∥2 ≤ 4 ε/µ. Thus,
x
Bh x + eh
2 1 2 ∥ · ∥2
×αh
Out
Figure 1. Detailed computational flow of a single quadratic branch.
4
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Conic primitive. For each g = 1, . . . , G, we introduce a conic branch defined as: λg ∥Ag x + dg ∥2 ,
λg ≥ 0,
3.4. SOCP lifting and value-function interpretation Both additional components admit standard SOCP epigraph representations. For the quadratic term, let Qm+2 = (ξ, η, w) ∈ R+ × R+ × Rm 2ξη ≥ ∥w∥22 r (12) denote the rotated second-order cone. Introducing auxiliary variables qh and sh with
(10)
where Ag ∈ Rkg ×d0 and dg ∈ Rkg . Similarly, this branch projects the input via an affine layer, passes it through an unsquared standard ℓ2 -norm operator, and scales the output by λg . This term acts as an explicit Euclidean norm primitive (Figure 2). ×λg
∥ · ∥2
Ag x + dg
x
qh = Bh x + eh ,
h +2 (sh , 1, qh ) ∈ Qm , r
(13)
one obtains
Out
1 ∥Bh x + eh ∥22 . 2 Since the coefficient of sh in the objective is αh ≥ 0, the optimum tightens this epigraph constraint. sh ≥
Figure 2. Detailed computational flow of a single conic branch.
Combining the outputs of these two parallel branches with the main ReLU backbone yields the unified SOC-ICNN forward pass: fSOC (x) =fReLU (x) +
H X αh h=1
+
G X
2
For the norm term, let Qk+1 = (u, t) ∈ Rk × R ∥u∥2 ≤ t
2 ∥Bh x + eh ∥2
(14)
denote the standard second-order cone. Introducing auxiliary variables ug and tg with
(11)
λg ∥Ag x + dg ∥2 .
ug = Ag x + dg ,
(ug , tg ) ∈ Qkg +1 ,
(15)
g=1
one obtains tg ≥ ∥Ag x + dg ∥2 .
The three terms in (11) play distinct and complementary geometric roles. The ReLU backbone captures the polyhedral (piecewise-linear) structure, the quadratic branch injects explicit smooth curvature, and the norm branch captures second-order conic geometry. Thus, the SOC-ICNN extends classical ReLU-ICNNs from purely polyhedral value functions into a unified class of structured convex functions encompassing piecewise-linear, quadratic, and conic components. The overall parallel topology is summarized in Figure 3.
Again, because the objective coefficient is λg ≥ 0, the optimum tightens this constraint. We now state the main structural result of the paper. Theorem 1 (SOC-ICNN as an SOCP value function). For every input x, the unified architecture in (11) is equal to the optimal value of the following SOCP:
fSOC (x) = min c⊤ zL + v ⊤ x + b0 +
Quadratic Branch X αh 2 ∥Bh x + eh ∥2 2 h
x
ReLU-ICNN Backbone zℓ = σ(Wℓ x + Uℓ zℓ−1 + bℓ ) Uℓ ≥ 0, c ≥ 0
η
s.t.
Σ
H X
αh sh +
h=1
G X
λg tg
g=1
zℓ ≥ Wℓ x + Uℓ zℓ−1 + bℓ , ℓ = 1, . . . , L, z0 = 0, zℓ ≥ 0, ℓ = 1, . . . , L, h +2 qh = Bh x + eh , (sh , 1, qh ) ∈ Qm , h = 1, . . . , H, r
fSOC (x)
ug = Ag x + dg , (ug , tg ) ∈ Qkg +1 , g = 1, . . . , G, (16)
with η = {zℓ , sh , qh , tg , ug }.
X Conic Branch λg ∥Ag x + dg ∥2 g
Proof sketch. Let V (x) denote the optimal value of (16). We prove that V (x) = fSOC (x).
Figure 3. The unified SOC-ICNN architecture. The input passes through three parallel branches: the quadratic branch injects PSD curvature, the conic branch provides Euclidean norm primitives, and the ReLU-ICNN backbone (shown with its defining layerwise recursion and non-negativity constraints) captures polyhedral piecewise-linear structure. All outputs are summed to yield a convex function that exactly corresponds to an SOCP value function.
1) Upper bound V (x) ≤ fSOC (x). Take the ReLU forward variables z̄ℓ produced by the backbone, so that c⊤ z̄L + v ⊤ x + b0 = fReLU (x). 5
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Set q̄h = Bh x + eh , s̄h = 12 ∥q̄h ∥22 , and ūg = Ag x + h +2 dg , t̄g = ∥ūg ∥2 . Then (s̄h , 1, q̄h ) ∈ Qm and r kg +1 (ūg , t̄g ) ∈ Q , so this choice is feasible for (16). Its objective value is exactly (11). Hence
4. Theoretical Analysis This section establishes the theoretical foundations of the proposed SOC-ICNN. Having exposed the fundamental CPWL bottleneck of classical ReLU-ICNNs in Section 3.2, we now answer a constructive question: Can the explicit curvature and conic primitives of SOC-ICNN strictly expand the representable function class, and how much parameter efficiency do we gain by absorbing curvature directly into the architecture? We structure our analysis in three progressive steps: (1) We prove that the SOC-ICNN naturally circumvents the CPWL bottleneck through exact structural representation; (2) We show that this exactness translates into a strictly superior approximation rate for complex downstream targets; and (3) We verify that these representational gains do not increase the asymptotic order of forward-pass complexity.
V (x) ≤ fSOC (x). 2) Lower bound V (x) ≥ fSOC (x). Take any feasible point of (16). By Proposition 1, the ReLU constraints imply c⊤ zL + v ⊤ x + b0 ≥ fReLU (x). Moreover, the cone constraints imply sh ≥
1 ∥Bh x + eh ∥22 , 2
tg ≥ ∥Ag x + dg ∥2 .
Multiplying by the nonnegative coefficients αh , λg and summing yields H X
αh sh ≥
h=1 G X
H X αh h=1
λg tg ≥
g=1
G X
2
4.1. Exact Structured Representations and Strict Extension Having established the CPWL bottleneck, a natural question arises: Can we design a convex architecture that directly absorbs curvature, thereby escaping this exponential lower bound? This is precisely what the structural branches of the SOC-ICNN achieve. We first define a family of structured convex functions, parameterized by r (the rank capacity of the quadratic term) and G (the number of conic terms):
∥Bh x + eh ∥22 ,
λg ∥Ag x + dg ∥2 .
g=1
Therefore the total objective value is at least fReLU (x) +
H X αh h=1
2
∥Bh x + eh ∥22 +
G X
GSOC (r, G) = {a⊤ x + b +
λg ∥Ag x + dg ∥2 ,
g=1
+
G X
1 ⊤ x Qx 2 (17)
λg ∥Ag x + dg ∥2 | Q ⪰ 0, rank(Q) ≤ r, λg ≥ 0}.
g=1
so V (x) ≥ fSOC (x). Combining the two inequalities proves the claim. A complete derivation is given in Appendix A.2.
The next proposition demonstrates that every function in this curved geometric class can be represented exactly by an SOC-ICNN, confirming that our architecture strictly extends the representational capacity of ReLU-ICNNs without suffering from the CPWL approximation error.
Since fReLU (x) is convex in x, squared Euclidean norms and Euclidean norms composed with affine maps are convex, and nonnegative linear combinations preserve convexity, fSOC (x) remains globally convex with respect to the input.
Proposition 4 (Exact representation and strict extension). For any target function f ∈ GSOC (r, G), there exists a finitewidth SOC-ICNN such that its forward pass exactly matches the target:
Remark 1 (Passthrough structures and gradient richness). In ReLU-ICNNs, non-negative weights (Uℓ ≥ 0) restrict gradients to the non-negative orthant, requiring unconstrained “passthrough” connections (Wℓ x) to express negative slopes. In contrast, SOC-ICNN eliminates this necessity while its internal affine weights (Bh , Ag ) are completely unconstrained. Because norms are symmetric convex functions, it can naturally span the full gradient space (e.g., the quadratic gradient αh Bh⊤ (Bh x + eh ) freely expresses negative slopes).
fSOC (x) ≡ f (x),
∀x ∈ Rd0 .
Moreover, let FReLU and FSOC denote the function classes represented by finite-width ReLU-ICNNs and SOC-ICNNs, respectively. We have the strict inclusion: FReLU ⊊ FSOC .
(18)
In particular, every non-CPWL member of GSOC (r, G) (e.g., f (x) = 12 ∥x∥22 ) strictly belongs to FSOC \ FReLU . 6
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Proof sketch. Since Q ⪰ 0 with rank at most r, we can decompose Q = B ⊤ B. Thus, 12 x⊤ Qx = 12 ∥Bx∥22 , which is perfectly implemented by a single quadratic branch in our architecture. Each norm term λg ∥Ag x + dg ∥2 is perfectly implemented by a conic branch. The linear residual a⊤ x+b is absorbed into the ReLU backbone by setting hidden layers to zero depth. Hence, exact representation holds. Strict inclusion follows because finite-width ReLU-ICNNs are strictly CPWL (Proposition 2), whereas GSOC (r, G) contains functions with smooth curvature. A detailed proof is in Appendix A.5.
the SOC-ICNN completely bypasses this cost, achieving an N −2/d0 rate strictly based on the smoothness L̃ of the residual h. 4.3. Forward Complexity Finally, we confirm that these representational gains do not compromise the speed of inference. Let the ReLU backbone have width m per layer and depth L. A standard forward pass requires TReLU = Θ(Lm2 + Ld0 m) operations. Each quadratic branch adds O(d0 mh ) operations, and each conic branch adds O(d0 kg ) operations. Summing over all branches, the total forward complexity of the SOC-ICNN is: ! H G X X 2 TSOC = Θ Lm + Ld0 m + d0 mh + d0 kg .
4.2. Structural Absorption and Parameter Efficiency While Proposition 4 proves exactness for perfectly quadratic or conic functions, real-world objective functions are rarely this clean; they often contain additional residual complexities. The true power of the SOC-ICNN lies in its ability to absorb the dominant curvature into its explicit branches, leaving only a well-behaved residual for the ReLU backbone to approximate. Consider a target function decomposed as: f (x) = q(x) + h(x),
h=1
(21) Under the typical architectural regime where the number of structural branches is bounded (H, G = O(1)) and their capacities scale with the network width (mh , kg = O(m)), this simplifies exactly to: TSOC = Θ Lm2 + Ld0 m . (22)
(19)
where q ∈ GSOC (r, G) captures the primary curvature and conic components, and h is a convex residual that is smoother, meaning its gradient is L̃-Lipschitz continuous on a compact domain Ω: ∥∇h(x) − ∇h(y)∥2 ≤ L̃∥x − y∥2 ,
Therefore, the SOC-ICNN provides a rigorous structural upgrade from LP to SOCP value functions while strictly maintaining the asymptotic forward complexity of classical ReLU-ICNNs. Here “asymptotic complexity” refers to the growth rate of floating-point operations with respect to network width m, depth L, and input dimension d0 , using standard big-Θ notation.
∀x, y ∈ Ω.
Proposition 5 (Constructive structural absorption bound). Assume that the target f admits the decomposition in (19). Then for every integer parameter budget N ≥ 1, there exists an SOC-ICNN ϕN whose ReLU backbone utilizes at most N affine pieces, achieving the approximation rate: ∥f − ϕN ∥L∞ (Ω) ≤ CΩ L̃ N −2/d0 ,
g=1
5. Experiments We evaluate three central claims of SOC-ICNN. First, by directly comparing the network forward pass with the optimal value returned by an external convex solver, we verify the exact equivalence between SOC-ICNN and the SOCP formulation in Theorem 1. Second, under controlled parameter budgets, we assess whether structured curvature injection improves approximation efficiency over ReLU-ICNN and smooth activation variants, where Softplus-ICNN represents the line of enhancing flexibility through smoother nonlinearities, while our internal variants Quad and Norm isolate the contributions of quadratic and norm-based conic geometry, respectively. Third, we evaluate downstream decision quality on parametric convex optimization tasks and compare classical neural convex surrogates against differentiable convex optimization baselines and learned parametric convex models (Agrawal et al., 2019; Besançon et al., 2024; Schaller et al., 2025), in order to test whether improved surrogate geometry translates into better end-to-end optimization performance.
(20)
where CΩ > 0 depends only on the geometry of Ω. Proof sketch. By Proposition 4, the curved component q is represented exactly by the structural branches with zero approximation error. For the residual h, we construct a δ-net on Ω with δ ≍ N −1/d0 . By placing hyperplanes tangent to h at these net points, convexity and the L̃-Lipschitz gradient guarantee that the max-affine approximation gN satisfies ∥h − gN ∥∞ ≤ CΩ L̃N −2/d0 . This gN is realizable by a ReLU-ICNN utilizing at most N pieces. Combining this bounded ReLU backbone with the exact representation of q yields ϕN . A full constructive proof is in Appendix A.6. This result is mathematically significant: while a pure ReLUICNN would require an exponential N ≳ ε−d0 /2 pieces just to approximate the curvature q (due to Proposition 3), 7
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
5.1. Experiment 1: Value-Function Equivalence
lies, namely SOCP, logistic, log-sum-exp, and Huber, under three feasible sets: simplex, box, and capped simplex. Each task instance is parameterized by a context vector θ ∈ R8 , and the ground-truth objective consists of a quadratic–linear backbone plus a family-specific convex structured term.
We verify that the forward pass of SOC-ICNN exactly solves the SOCP in Theorem 1. For networks with d0 = 100, width 256, depth 6, and two quadratic / norm blocks, both passthrough settings yield a primal–dual gap of ∼10−14 and a solver absolute error of ∼5.6 × 10−7 across 150 random trials. All feasibility constraints, including the ReLU chain constraints, the rotated SOC constraints, and the standard SOC constraints, are satisfied to machine precision, confirming both optimality and feasibility of the lifted formulation. Closed-form inference is 3–4× faster than solving the lifted program externally. Full diagnostic tables are provided in Appendix B.1.
We compare five neural convex surrogates: ReLU-ICNN and its smooth-activation variant Softplus-ICNN (Amos et al., 2017), together with the internal curvature-injection variants Norm, Quad, and SOC. We further compare against two optimization-based baselines, namely DCP (Agrawal et al., 2019) and PCF (Schaller et al., 2025). For each task and dimension d ∈ {10, 20, 50}, we use 1000 training instances, 1000 validation instances, and 200 test instances. Each model is trained from sampled candidate points, and downstream decisions are obtained by optimizing the learned surrogate with the same projected-gradient procedure using 5 random restarts and 200 steps per restart.
5.2. Experiment 2: Structural Efficiency under Controlled Parameter Budgets We evaluate whether the explicit geometric primitives of SOC-ICNN translate into improved approximation efficiency. For each input dimension d ∈ {5, 10, 20, 50}, we first define a compact anchor SOC-ICNN with depth 2, hidden width hd , one quadratic block of rank d, and one norm block of dimension d. To ensure a fair comparison, we set the parameter budget for all other ICNN variants to be at least that of the anchor by increasing the backbone depth while keeping the hidden width identical. The compared neural baselines include the classical ReLU-ICNN and its smooth-activation variant Softplus-ICNN (Amos et al., 2017), together with the internal ablations Quad and Norm. All models are trained on 6,000 uniformly sampled points from [−3, 3]d , validated on 1,000 points, and tested on 2,000 points, with three random seeds per configuration.
The results are given in Appendix B.3. We report test relative ℓ2 error, mean regret f (x̂) − f (x⋆ ), decision error ∥x̂ − x⋆ ∥2 , training time, and decision time. The results reveal a clear mismatch between upstream fitting quality and downstream decision quality. In particular, low test prediction error does not necessarily imply low regret: Softplus often attains competitive test errors, yet its downstream regret is consistently much worse than that of the betterperforming curvature-injected models. This confirms that, for decision-focused learning, pointwise surrogate accuracy alone is insufficient; the geometry of the learned convex landscape matters. Among the neural models, Quad is the most robust variant across tasks and dimensions, while SOC remains competitive in several settings. By contrast, the Norm module does not provide uniformly positive gains: its additional flexibility does not consistently translate into better downstream decisions and can be less stable than the simpler Quad design. In terms of efficiency, the neural surrogates enjoy substantially lower decision time than DCP and remain competitive with PCF, while avoiding the large regret degradation observed for Softplus. Taken together, these results suggest that structured curvature injection is a useful inductive bias for downstream optimization, but simpler forms of curvature control can be more reliable than the more elaborate Norm-based parameterization on the current benchmark.
The target set comprises ten convex functions with diverse curvature profiles: isotropic and anisotropic quadratics, Euclidean and weighted ℓ2 norms, sums of Softplus activations, log-sum-exp with quadratic regularization, Huber and ℓ1 losses, a hybrid mixed function, and a composite target adapted from the ICKAN literature (Deschatre & Warin, 2025). Complete results for all functions and dimensions are provided in Appendix B.2. SOC-ICNN consistently achieves the lowest relative error across all functions and dimensions, often by a substantial margin, while using comparable or fewer parameters than the alternatives. These results confirm that the explicit injection of curvature and conic primitives provides a clear parameter-efficiency advantage over purely polyhedral or smooth-activation ICNNs.
6. Conclusion and Discussion 5.3. Experiment 3: Downstream Decision Quality
In this work, we proposed SOC-ICNN, which elevates ReLU-ICNNs from LP to SOCP value-function networks, achieving superior parameter efficiency without increasing asymptotic complexity. While SOC-ICNN learns convex surrogates directly from data without requiring problem
We evaluate whether improved surrogate geometry leads to improved end-to-end decisions when the learned convex surrogate is optimized downstream. Six parametric convex optimization tasks are constructed from four structural fami-
8
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
structure a priori, solver-based methods may still be preferable when the exact analytical form is known and fixed. Fusing explicit solver priors with SOC-ICNNs remains a promising direction.
Hoedt, P.-J. and Klambauer, G. Principled weight initialisation for Input-Convex Neural Networks. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), pp. 46093–46104, New Orleans, Louisiana, USA, 2023.
References
Katyal, C. Differentiable convex optimization layers in neural architectures: Foundations and perspectives. arXiv preprint arXiv:2412.20679, December 2024.
Agrawal, A., Amos, B., et al. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019), Vancouver, BC, Canada, 2019.
Liu, Y., Oliveira, F., et al. ICNN-enhanced 2SP: Leveraging Input Convex Neural Networks for Solving Two-Stage Stochastic Programming. arXiv preprint arXiv:2505.05261, May 2025.
Amos, B. and Kolter, J. Z. OptNet: Differentiable optimization as a layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 136–145, Sydney, Australia, 2017.
Makkuva, A., Taghvaei, A., et al. Optimal transport mapping via Input Convex Neural Networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 6672–6681, Virtual Event, 2020.
Amos, B., Xu, L., et al. Input Convex Neural Networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 146–155, Sydney, Australia, 2017.
Pan, J., Ye, Z., et al. BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), Vancouver, BC, Canada, 2024. Spotlight.
Arora, R., Basu, A., et al. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), Vancouver, BC, Canada, 2018.
Rosemberg, A. W., Tanneau, M., et al. Learning optimal power flow value functions with Input-Convex Neural Networks. Electr. Power Syst. Res., 235(1):110643, October 2024.
Bakaev, E., Brunck, F., et al. On the depth of monotone ReLU neural networks and ICNNs. arXiv preprint arXiv:2505.06169, May 2025.
Schaller, M., Bemporad, A., et al. Learning parametric convex functions. arXiv preprint arXiv:2506.04183, June 2025.
Besançon, M., Garcia, J. D., et al. Flexible differentiable optimization via model transformations. INFORMS J. Comput., 36(2):456–478, 2024.
Wang, R., Patrinos, P., et al. Parametric nonconvex optimization via convex surrogates. arXiv preprint arXiv:2604.05640, April 2026.
Chen, Y., Shi, Y., et al. Optimal control via neural networks: A convex approach. In International Conference on Learning Representations (ICLR), New Orleans, LA, USA, 2019.
Wang, Z., Yu, D., et al. Real-time machine-learning-based optimization using input convex LSTM. arXiv preprint arXiv:2311.07202, November 2023.
Christianson, N., Cui, W., et al. Fast and reliable N -k contingency screening with Input-Convex Neural Networks. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, volume 283 of Proceedings of Machine Learning Research, pp. 527–539, Ann Arbor, MI, USA, 2025.
Wang, Z., Li, Y., et al. Input convex lipschitz recurrent neural networks for robust and efficient process modeling and optimization. arXiv preprint arXiv:2401.07494, January 2024.
Deschatre, T. and Warin, X. Input Convex Kolmogorov Arnold Networks. arXiv preprint arXiv:2505.21208, May 2025. Gagneux, A., Massias, M., et al. Convexity in ReLU neural networks: Beyond ICNNs? J. Math. Imaging Vis., 67(4): 40, 2025. 9
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
A. Additional Derivations and Proofs This appendix provides the complete derivations required by the main text. The presentation follows the main storyline of the paper. We first prove the LP value-function form of ReLU-ICNNs, then establish the main theorem showing that SOC-ICNN is an SOCP value function. We next prove the theoretical statements used in Section 4: the CPWL structure of finite-width ReLU-ICNNs, the lower bound for approximating strongly convex targets, the exact representability and strict extension result for SOC-ICNNs, the structural absorption bound, and finally the complexity calculation. A.1. Proof of the LP value-function form of ReLU-ICNN Let z̄ℓ = σ(Wℓ x + Uℓ z̄ℓ−1 + bℓ ) ,
ℓ = 1, . . . , L,
denote the hidden states produced by the forward pass, with z̄0 = 0. Since ReLU satisfies σ(a) = max{a, 0} elementwise, for every layer ℓ we have z̄ℓ ≥ Wℓ x + Uℓ z̄ℓ−1 + bℓ ,
z̄ℓ ≥ 0.
Hence {z̄ℓ }L ℓ=1 is feasible for (3), and therefore val (3) ≤ c⊤ z̄L + v ⊤ x + b0 = fReLU (x). To prove the reverse inequality, take any feasible point {zℓ }L ℓ=1 of (3). We show by induction that zℓ ≥ z̄ℓ , ∀ℓ = 1, . . . , L. For ℓ = 1, feasibility gives z1 ≥ W1 x + b1 ,
z1 ≥ 0,
hence z1 ≥ max{W1 x + b1 , 0} = z̄1 . Assume now that zk ≥ z̄k for some k ∈ {1, . . . , L−1}. Since Uk+1 ≥ 0 elementwise, monotonicity of matrix multiplication implies Uk+1 zk ≥ Uk+1 z̄k . Using feasibility once more, zk+1 ≥ Wk+1 x + Uk+1 zk + bk+1 ≥ Wk+1 x + Uk+1 z̄k + bk+1 , and zk+1 ≥ 0. Therefore zk+1 ≥ max{Wk+1 x + Uk+1 z̄k + bk+1 , 0} = z̄k+1 . The induction is complete. In particular, zL ≥ z̄L . Since c ≥ 0, we obtain c⊤ zL ≥ c⊤ z̄L . Hence every feasible point of (3) has objective value at least fReLU (x), which implies val (3) ≥ fReLU (x). Combining both inequalities yields val (3) = fReLU (x). 10
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
A.2. Proof of Theorem 1 Let V (x) denote the optimal value of the SOCP in (16). We prove that V (x) = fSOC (x). We first show that V (x) ≤ fSOC (x). By the forward definition of the ReLU backbone, there exist hidden variables z̄1 , . . . , z̄L such that c⊤ z̄L + v ⊤ x + b0 = fReLU (x). For each quadratic branch h, define q̄h = Bh x + eh ,
s̄h =
1 ∥Bh x + eh ∥22 . 2
h +2 Then (s̄h , 1, q̄h ) ∈ Qm . For each conic branch g, define r
t̄g = ∥Ag x + dg ∥2 ,
ūg = Ag x + dg , so that (ūg , t̄g ) ∈ Qkg +1 . Therefore,
H G {z̄ℓ }L ℓ=1 , {s̄h , q̄h }h=1 , {t̄g , ūg }g=1
is feasible for (16). Its objective value is c⊤ z̄L + v ⊤ x + b0 +
H X
αh s̄h +
G X
λg t̄g ,
g=1
h=1
which equals fReLU (x) +
H X αh h=1
2
∥Bh x + eh ∥22 +
G X
λg ∥Ag x + dg ∥2 = fSOC (x).
g=1
Hence V (x) ≤ fSOC (x). We now prove the reverse inequality. Take any feasible point of (16). By Proposition 1, the ReLU constraints imply c⊤ zL + v ⊤ x + b0 ≥ fReLU (x). h +2 For the quadratic branches, feasibility of (sh , 1, qh ) ∈ Qm together with qh = Bh x + eh implies r
1 ∥Bh x + eh ∥22 . 2
sh ≥ Multiplying by αh ≥ 0 and summing over h gives H X
αh sh ≥
h=1 kg +1
Similarly, feasibility of (ug , tg ) ∈ Q
H X αh h=1
2
∥Bh x + eh ∥22 .
and ug = Ag x + dg implies tg ≥ ∥Ag x + dg ∥2 ,
and therefore
G X
λg tg ≥
g=1
G X
λg ∥Ag x + dg ∥2 .
g=1
Adding the three parts yields c⊤ z L + v ⊤ x + b 0 +
H X
αh sh +
G X g=1
h=1
Thus V (x) ≥ fSOC (x). Combining both inequalities proves V (x) = fSOC (x). 11
λg tg ≥ fSOC (x).
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
A.3. Proof of Proposition 2 Starting from (3), we dualize the LP, introduce dual variables νℓ ≥ 0 for the constraints zℓ − Uℓ zℓ−1 − Wℓ x − bℓ ≥ 0, and µℓ ≥ 0 for the constraints zℓ ≥ 0. The Lagrangian is L = c⊤ zL + v ⊤ x + b0 −
L X
νℓ⊤ (zℓ − Uℓ zℓ−1 − Wℓ x − bℓ ) −
ℓ=1
= v ⊤ x + b0 +
L X
L X
µ⊤ ℓ zℓ
ℓ=1
⊤ νℓ⊤ (Wℓ x + bℓ ) + zL (c − νL − µL ) +
ℓ=1
L−1 X
⊤ zℓ⊤ Uℓ+1 νℓ+1 − νℓ − µℓ .
ℓ=1
To have a finite lower bound when minimizing over zℓ , the coefficients of zℓ must vanish. This gives the stationarity conditions ⊤ Uℓ+1 νℓ+1 − νℓ − µℓ = 0,
c − νL − µL = 0,
ℓ = 1, . . . , L − 1.
Since µℓ ≥ 0, these are equivalent to the chain constraints ⊤ 0 ≤ νℓ ≤ Uℓ+1 νℓ+1 ,
0 ≤ νL ≤ c,
ℓ = 1, . . . , L − 1.
(23)
Because each Uℓ+1 has nonnegative entries, the chain constraints imply that each νℓ is bounded. Hence the dual feasible region N defined by (23) is a nonempty bounded polyhedron. The dual problem therefore reads " v ⊤ x + b0 +
fReLU (x) = max
{νℓ }∈N
L X
# νℓ⊤ (Wℓ x + bℓ ) .
ℓ=1
Since a linear function over a polyhedron attains its maximum at an extreme point, and the number of extreme points of N is finite, there exists a finite index set J such that fReLU (x) = max v + j∈J
L X
!⊤ (j)
Wℓ⊤ νℓ
x+
! L X (j) b0 + (νℓ )⊤ bℓ .
ℓ=1
ℓ=1
Defining aj = v +
L X
(j)
Wℓ⊤ νℓ ,
βj = b0 +
ℓ=1
L X
(j)
(νℓ )⊤ bℓ ,
ℓ=1
we obtain the finite max-affine form fReLU (x) = max{a⊤ j x + βj }. j∈J
The subgradient expression in (5) follows immediately from the standard subdifferential formula for max-affine functions: every subgradient is a convex combination of active slopes, hence can still be written in the form g=v+
L X ℓ=1
with {νℓ } satisfying the same chain constraints (23). 12
Wℓ⊤ νℓ ,
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
A.4. Proof of Proposition 3 Let g(x) = max {a⊤ i x + bi }, 1≤i≤N
and define the active region of the ith affine piece by Ai = x ∈ Ω g(x) = a⊤ i x + bi . Since g and each a⊤ i x + bi are continuous, each Ai is a closed set, hence Lebesgue measurable. Clearly Ω = Fix one active region Ai , and take any x, y ∈ Ai . Let m=
x+y . 2
Because x, y lie on the same active affine piece, and ∥f − g∥L∞ (Ω) ≤ ε, we have |f (x) − ℓi (x)| ≤ ε,
|f (y) − ℓi (y)| ≤ ε,
|f (m) − g(m)| ≤ ε,
where ℓi (x) = a⊤ i x + bi . By µ-strong convexity, f (x) + f (y) µ − ∥x − y∥22 . 2 8
f (m) ≤
Substituting the uniform error bounds and using the fact that ℓi is affine yields µ ∥x − y∥22 ≤ 2ε. 8 Therefore
r ε ∥x − y∥2 ≤ 4 . µ p Hence every active region has diameter at most 4 ε/µ.
Applying the isodiametric inequality to each Ai gives vold0 (Ai ) ≤ ωd0 Since Ω ⊆
diam(Ai ) 2
d0
r d0 ε ≤ ωd0 2 . µ
SN
i=1 Ai , the subadditivity of Lebesgue measure implies
vold0 (Ω) ≤
N X
vold0 (Ai ) ≤ N ωd0
i=1
r d0 ε , 2 µ
which rearranges to N≥
vold0 (Ω) µ d0 /2 . ωd0 2d0 ε
A.5. Proof of Proposition 4 Take any G X 1 f (x) = a⊤ x + b + x⊤ Qx + λg ∥Ag x + dg ∥2 ∈ GSOC (r, G). 2 g=1
Since Q ⪰ 0 and rank(Q) ≤ r, there exists a matrix B ∈ Rr×d0 such that Q = B ⊤ B, and hence 1 1 ⊤ x Qx = ∥Bx∥22 . 2 2 13
SN
i=1 Ai .
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Therefore: (i) the affine term a⊤ x + b is represented by the affine part of the ReLU backbone (by setting the hidden layers to zero depth); (ii) the quadratic term is represented exactly by one quadratic branch; (iii) each norm term λg ∥Ag x + dg ∥2 is represented exactly by one conic branch. This yields an exact SOC-ICNN representation of f . To prove strict inclusion, note first that FReLU ⊆ FSOC is immediate by setting H = 0 and G = 0. On the other hand, Proposition 2 shows that every finite-width ReLU-ICNN is CPWL, whereas GSOC (r, G) contains many non-CPWL functions, such as nondegenerate PSD quadratic forms (e.g., f (x) = 21 ∥x∥22 ) and nondegenerate Euclidean norm compositions. Since these functions are representable by SOC-ICNN but not by finite-width ReLU-ICNN, we conclude that FReLU ⊊ FSOC . A.6. Proof of Proposition 5 Assume q ∈ GSOC (r, G),
f (x) = q(x) + h(x),
d0
and that ∇h is L̃-Lipschitz on a compact convex domain Ω ⊂ R . By Proposition 4, the structured part q is represented exactly by the SOC branches. Fix an integer N ≥ 1. Let δ = cΩ N −1/d0 where cΩ is a constant depending only on Ω such that the covering number of Ω by Euclidean balls of radius δ satisfies M ≤ N . (Standard covering arguments give cΩ = diam(Ω)/2 suffices, but any fixed constant works; we absorb it into CΩ later.) Let XN = {x1 , . . . , xM } be the centers of such a covering, so M ≤ N and every point in Ω is within distance δ of some xi . For each net point xi , define the tangent plane ℓi (x) = h(xi ) + ∇h(xi )⊤ (x − xi ), and let gN (x) = max ℓi (x). 1≤i≤M
Since h is convex, each tangent plane is a global lower support, so gN (x) ≤ h(x) for all x ∈ Ω. By gradient Lipschitz continuity, the standard descent lemma gives h(x) ≤ ℓi (x) +
L̃ ∥x − xi ∥22 , 2
∀x ∈ Ω.
For any x ∈ Ω, choose a net point xi with ∥x − xi ∥2 ≤ δ. Then h(x) − gN (x) ≤ h(x) − ℓi (x) ≤
L̃ 2 L̃ δ ≤ c2Ω N −2/d0 . 2 2
Therefore, ∥h − gN ∥L∞ (Ω) ≤ CΩ L̃ N −2/d0 , where CΩ = c2Ω /2 depends only on Ω. Finally, gN is a finite max-affine convex function. It can be represented exactly by a finite-width ReLU-ICNN: one can construct a network with M − 1 hidden units in a single layer that computes the pointwise maximum (see, e.g., the constructive proof in (Arora et al., 2018) or a simple two-layer architecture). Adding this ReLU backbone to the exact SOC representation of q gives an SOC-ICNN ϕN such that ∥f − ϕN ∥L∞ (Ω) ≤ CΩ L̃ N −2/d0 . A.7. Proof of the complexity formulas Assume the ReLU backbone has width m in each of its L layers. Each layer computes two dominant matrix-vector products: Uℓ zℓ−1 with cost Θ(m2 ), and Wℓ x with cost Θ(d0 m). Summing over all layers gives TReLU = Θ(Lm2 + Ld0 m). 14
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
For the quadratic branches, the dominant cost of the hth branch is the affine map Bh x+eh , which costs Θ(d0 mh ). Summing over h = 1, . . . , H yields ! H X ∆TQuad = Θ d0 mh . h=1
For the conic branches, the dominant cost of the gth branch is the affine map Ag x + dg , which costs Θ(d0 kg ). Summing over g = 1, . . . , G yields ! G X ∆TSOC = Θ d0 kg . g=1
Combining all terms gives the overall SOC-ICNN forward complexity 2
TSOC = Θ Lm + Ld0 m + d0
H X h=1
mh + d0
G X
! kg
.
g=1
Under the common regime H, G = O(1) and mh , kg = O(m), this simplifies to the same asymptotic order as the backbone alone.
B. Experiment Results B.1. Full Results for Experiment 1 B.1.1. S ETTING Table 1 reports the complete diagnostic metrics for the value-function equivalence experiment. Across 150 trials with both passthrough settings, the closed-form forward pass and the external CVXPY solver agree to high precision. We detail the meaning of each metric below: • Primal-Dual Gap: The difference between the closed-form forward value (primal) and the explicit dual objective evaluated using the extracted dual variables. A gap of ∼ 10−14 confirms strong duality and numerical optimality. • Forward vs. Solver Abs. Error: The absolute difference |fSOC (x) − VCVXPY (x)|. Values < 10−6 verify exact equivalence. • ReLU Primal Violation: The maximum violation of the ReLU primal constraints zℓ ≥ Wℓ x + Uℓ zℓ−1 + bℓ and zℓ ≥ 0. Zero indicates strict feasibility. ⊤ • ReLU Dual Box Violation: The maximum violation of the dual box constraints 0 ≤ νℓ ≤ Uℓ+1 νℓ+1 (derived in Appendix A.3). Zero confirms dual feasibility.
• ReLU Complementarity Slack: The absolute value of the inner product νℓ⊤ (zℓ − Wℓ x − Uℓ zℓ−1 − bℓ ). Zero verifies complementary slackness for the ReLU block. • Quad./Norm Epi. Violation: Violation of the conic epigraph constraints, e.g., sh ≥ 12 ∥qh ∥22 for the quadratic branch. Zero indicates the auxiliary variables lie strictly within or on the cone. • Quad./Norm Tightness Slack: The absolute difference |sh − 12 ∥qh ∥22 |. Since the objective coefficient αh > 0, this should be zero at optimality, confirming the epigraph constraint is active (tight). • Norm Dual Ball/Align. Violation: The violation of the dual norm cone constraints ∥µg ∥2 ≤ λg and the alignment condition µ⊤ g ug = λg tg . Zero confirms dual feasibility and complementarity for the SOC branch. • Solver Feasibility: The same violation metrics evaluated on the solution returned by the CVXPY solver, verifying that the external solver also finds a correct optimal solution. 15
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
B.1.2. R ESULTS Table 1. Experiment 1: Full Diagnostic Metrics for Value-Function Equivalence Metric
Passthrough = False
Passthrough = True
Mean
Mean
Max
Trials Solver Success Rate
150 1.0
Max 150 1.0
Optimality Gaps 1.06 × 10−14 4.26 × 10−14 2.88 × 10−14 1.14 × 10−13 5.57 × 10−7 7.68 × 10−7 5.57 × 10−7 7.68 × 10−7
Primal-Dual Gap Forward vs. Solver Abs. Error
Closed-Form Feasibility ReLU Primal Violation 0 0 0 0 ReLU Dual Box Violation 0 0 0 0 ReLU Complementarity Slack 0 0 0 0 Quadratic Epigraph Violation 0 0 0 0 Quadratic Tightness Slack 0 0 0 0 Norm Epigraph Violation 0 0 0 0 Norm Tightness Slack 0 0 0 0 Norm Dual Ball Violation 8.88 × 10−18 4.44 × 10−16 8.88 × 10−18 4.44 × 10−16 Norm Dual Alignment Violation 0 0 0 0 ReLU Primal Violation Quadratic Epigraph Violation Quadratic Tightness Slack Norm Epigraph Violation Norm Tightness Slack
Solver Feasibility (CVXPY) 6.80 × 10−16 9.99 × 10−16 3.91 × 10−15 7.11 × 10−15 0 0 0 0 1.46 × 10−7 1.65 × 10−7 1.46 × 10−7 1.65 × 10−7 0 0 0 0 1.69 × 10−7 2.61 × 10−7 1.69 × 10−7 2.61 × 10−7 Runtime (ms) 6.22 ± 0.84 24.80 ± 2.55
Closed-Form Forward CVXPY Solver
– –
6.66 ± 1.43 19.71 ± 4.34
– –
B.2. Full Results for Experiment 2 Target Functions The ten convex functions used in Experiment 2 are defined as follows (x ∈ Rd , all operations elementwise unless specified). • QuadraticIso (isotropic quadratic): f (x) = 12 ∥x∥22 . • QuadraticAniso (anisotropic quadratic): f (x) = 12
Pd
i−1 2 i=1 wi xi , wi = 0.5 + 2 · d−1 .
• NormEuclid (Euclidean norm): f (x) = ∥x∥2 . qP d i−1 2 • NormAniso (anisotropic norm): f (x) = i=1 wi xi , wi = 1 + 9 · d−1 . q P (1) P (2) 2 • Mixed (hybrid convex): f (x) = 0.25 wi x2i + 0.7 wi xi + maxk {a⊤ k x + bk }. • SoftplusSum: f (x) =
Pd
i=1 log(1 + e
xi
). x
Pd • LogSumExpQuad: f (x) = log i=1 e i + 0.1∥x∥22 . Pd • Huber: f (x) = i=1 hδ (xi ), δ = 1. • L1Norm: f (x) = ∥x∥1 . • ICKANPaperTarget: f (x) =
Pd
i=1 (|xi | + |1 − xi |) + 0.25
16
P
wi x2i , wi ∈ [0.5, 2.0].
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Metrics For each configuration we report the relative ℓ2 test error (RelErr, mean ± std over 3 seeds) and the number of trainable parameters (Params). Training time (seconds) is also provided for completeness.
Results Tables 2–11 present results for each function. SOC-ICNN consistently achieves the lowest relative error across most functions and dimensions, particularly when the target exhibits explicit curvature or conic structure. Table 2. Huber function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.828 ± 0.025 0.830 ± 0.002 0.855 ± 0.005 Softplus-ICNN 0.765 ± 0.018 0.802 ± 0.010 0.843 ± 0.007 Quad-ICNN 0.452 ± 0.053 0.285 ± 0.015 0.168 ± 0.009 Norm-ICNN 0.523 ± 0.009 0.548 ± 0.007 0.614 ± 0.002 SOC-ICNN 0.246 ± 0.066 0.155 ± 0.021 0.087 ± 0.009
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 3. L1Norm function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.860 ± 0.005 0.885 ± 0.010 0.900 ± 0.003 Softplus-ICNN 0.829 ± 0.011 0.860 ± 0.010 0.892 ± 0.003 Quad-ICNN 0.536 ± 0.007 0.374 ± 0.004 0.245 ± 0.002 Norm-ICNN 0.644 ± 0.020 0.680 ± 0.005 0.728 ± 0.002 SOC-ICNN 0.390 ± 0.018 0.266 ± 0.015 0.177 ± 0.004
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 4. NormEuclid function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.732 ± 0.030 0.655 ± 0.009 0.601 ± 0.015 Softplus-ICNN 0.659 ± 0.013 0.597 ± 0.010 0.563 ± 0.013 Quad-ICNN 0.340 ± 0.106 0.127 ± 0.018 0.073 ± 0.001 Norm-ICNN 0.295 ± 0.031 0.135 ± 0.006 0.075 ± 0.002 SOC-ICNN 0.159 ± 0.013 0.079 ± 0.024 0.038 ± 0.001
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 5. LogSumExpQuad function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.719 ± 0.010 0.701 ± 0.013 0.697 ± 0.007 Softplus-ICNN 0.713 ± 0.056 0.672 ± 0.003 0.675 ± 0.009 Quad-ICNN 0.398 ± 0.020 0.176 ± 0.029 0.056 ± 0.011 Norm-ICNN 0.379 ± 0.044 0.232 ± 0.020 0.195 ± 0.007 SOC-ICNN 0.255 ± 0.096 0.058 ± 0.021 0.020 ± 0.001
17
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions Table 6. QuadraticIso function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.869 ± 0.017 0.889 ± 0.004 0.897 ± 0.002 Softplus-ICNN 0.841 ± 0.004 0.868 ± 0.004 0.893 ± 0.001 Quad-ICNN 0.566 ± 0.021 0.400 ± 0.011 0.236 ± 0.014 Norm-ICNN 0.654 ± 0.009 0.690 ± 0.005 0.732 ± 0.004 SOC-ICNN 0.393 ± 0.019 0.279 ± 0.015 0.167 ± 0.002
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 7. QuadraticAniso function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.914 ± 0.006 0.924 ± 0.005 0.934 ± 0.001 Softplus-ICNN 0.899 ± 0.004 0.913 ± 0.003 0.929 ± 0.004 Quad-ICNN 0.720 ± 0.003 0.577 ± 0.005 0.407 ± 0.004 Norm-ICNN 0.779 ± 0.012 0.798 ± 0.003 0.825 ± 0.002 SOC-ICNN 0.575 ± 0.016 0.457 ± 0.007 0.300 ± 0.007
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 8. NormAniso function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.879 ± 0.012 0.858 ± 0.006 0.840 ± 0.005 Softplus-ICNN 0.859 ± 0.009 0.831 ± 0.004 0.814 ± 0.007 Quad-ICNN 0.616 ± 0.031 0.333 ± 0.015 0.151 ± 0.008 Norm-ICNN 0.696 ± 0.017 0.618 ± 0.006 0.548 ± 0.005 SOC-ICNN 0.441 ± 0.010 0.230 ± 0.016 0.076 ± 0.006
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 9. Mixed function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.913 ± 0.014 0.901 ± 0.002 0.903 ± 0.001 Softplus-ICNN 0.891 ± 0.014 0.884 ± 0.003 0.894 ± 0.003 Quad-ICNN 0.683 ± 0.023 0.484 ± 0.009 0.247 ± 0.005 Norm-ICNN 0.753 ± 0.004 0.737 ± 0.005 0.739 ± 0.003 SOC-ICNN 0.530 ± 0.026 0.342 ± 0.018 0.179 ± 0.013 P1-ICKAN 8.94 ± 0.09 10.34 ± 0.30 11.90 ± 0.12
d=5 d=10 d=20 822 822 848 853 527 694
1491 1491 1592 1602 1083 1379
2709 2709 3110 3130 2451 2749
Table 10. SoftplusSum function: relative ℓ2 error and parameter count. RelErr (mean ± std) Model
d=5
d=10
Params d=20
ReLU-ICNN 0.731 ± 0.046 0.787 ± 0.012 0.837 ± 0.009 Softplus-ICNN 0.706 ± 0.035 0.756 ± 0.008 0.816 ± 0.011 Quad-ICNN 0.514 ± 0.083 0.336 ± 0.045 0.204 ± 0.014 Norm-ICNN 0.468 ± 0.026 0.502 ± 0.025 0.582 ± 0.005 SOC-ICNN 0.357 ± 0.081 0.243 ± 0.003 0.158 ± 0.016
18
d=5 d=10 d=20 822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions Table 11. ICKANPaperTarget function: relative ℓ2 error and parameter count. RelErr (mean ± std) d=5
Model
d=10
Params d=20
d=5 d=10 d=20
ReLU-ICNN 0.948 ± 0.002 0.956 ± 0.005 0.963 ± 0.001 Softplus-ICNN 0.935 ± 0.004 0.950 ± 0.003 0.959 ± 0.002 Quad-ICNN 0.817 ± 0.004 0.752 ± 0.003 0.650 ± 0.003 Norm-ICNN 0.862 ± 0.006 0.881 ± 0.000 0.900 ± 0.001 SOC-ICNN 0.734 ± 0.006 0.674 ± 0.003 0.580 ± 0.003
822 822 848 853 527
1491 1491 1592 1602 1083
2709 2709 3110 3130 2451
Table 12. Approximation results for all functions at d = 50 (RelErr, mean ± std).
Function
ReLU-ICNN
Softplus-ICNN
Quad-ICNN
Norm-ICNN
SOC-ICNN
Huber
0.821 ± 0.005 0.875 ± 0.002 0.345 ± 0.017 0.585 ± 0.013 0.873 ± 0.006 0.915 ± 0.003 0.695 ± 0.001 0.861 ± 0.004 0.799 ± 0.007 0.951 ± 0.001
0.815 ± 0.005 0.870 ± 0.003 0.338 ± 0.019 0.569 ± 0.018 0.863 ± 0.007 0.909 ± 0.004 0.683 ± 0.004 0.847 ± 0.004 0.792 ± 0.002 0.947 ± 0.001
0.068 ± 0.002 0.114 ± 0.004 0.054 ± 0.001 0.021 ± 0.000 0.102 ± 0.004 0.179 ± 0.003 0.066 ± 0.002 0.093 ± 0.002 0.115 ± 0.001 0.460 ± 0.001
0.691 ± 0.003 0.782 ± 0.004 0.039 ± 0.002 0.190 ± 0.004 0.781 ± 0.002 0.856 ± 0.000 0.431 ± 0.007 0.750 ± 0.003 0.672 ± 0.004 0.920 ± 0.001
0.038 ± 0.001 0.089 ± 0.001 0.029 ± 0.001 0.007 ± 0.000 0.077 ± 0.004 0.149 ± 0.002 0.044 ± 0.001 0.071 ± 0.003 0.097 ± 0.002 0.392 ± 0.001
L1Norm NormEuclid LogSumExpQuad QuadraticIso QuadraticAniso NormAniso Mixed SoftplusSum ICKANPaperTarget
Table 13. Parameter counts for ICNN variants at d = 50. Model
Parameters
ReLU-ICNN Softplus-ICNN Quad-ICNN Norm-ICNN SOC-ICNN
9,683 9,683 9,528 9,578 9,423
B.3. Full Results for Experiment 3 Task construction.
Each task instance is defined by a context parameter θ ∈ R8 , and the goal is to solve min fθ (x).
x∈X
We consider three feasible sets: • Simplex: {x ∈ Rd | x ≥ 0,
Pd
i=1 xi = 1}.
• Box: {x ∈ Rd | 0 ≤ xi ≤ 1, ∀i}. • Budget (capped simplex): {x ∈ Rd | 0 ≤ xi ≤ 1,
Pd
i=1 xi = B} with B = 0.3d.
The objective function has a common quadratic–linear backbone plus a family-specific structured term: fθ (x) =
d d X αX wi (xi − mi (θ))2 + ci (θ)xi +fstruct (x; θ). 2 i=1 i=1 | {z } backbone
19
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Here α = 0.35 for the logistic and log-sum-exp families and α = 1.0 for the SOCP and Huber families; wi ∈ [0.8, 1.6] are sampled once and fixed per task; and m(θ) = m0 + M θ,
c(θ) = c0 + Cθ
are affine maps with random coefficients fixed within each task. We construct six tasks from four structural families: • SOCP family (simplex socp, box socp): fstruct (x; θ) =
J X
λj (θ) ∥Aj x − dj (θ)∥2 ,
j=1
with J = 1 for the single-cone tasks and J = 2 for the two-cone task budget twocone socp. The cone weights and offsets depend affinely on θ through softplus-transformed coefficients. • Logistic family (simplex logistic): fstruct (x; θ) =
K X
⊤ βk (θ) log 1 + eak x−bk (θ) ,
k=1
where K = max(6, ⌊d/3⌋). • LogSumExp family (box logsumexp): fstruct (x; θ) =
2 X
βj (θ) logsumexp(Aj x − bj (θ)).
j=1
• Huber family (budget huber): fstruct (x; θ) =
K X
( βk (θ) hδ (a⊤ k x − bk (θ)),
k=1
hδ (t) =
t2 , |t| ≤ δ, 2δ|t| − δ 2 , |t| > δ,
with δ = 0.35 and K = max(8, ⌊d/2⌋). All random matrices and vectors are drawn once per task and dimension, then fixed across all instances. Experimental protocol. For each task and dimension d ∈ {10, 20, 50}, we generate 1000 training instances, 1000 validation instances, and 200 test instances. Each training instance contains 64 candidate points for supervised learning of the surrogate objective. We compare five neural convex surrogates (ReLU, Softplus, Norm, Quad, and SOC) against two differentiable optimization baselines (PCF and DCP). At test time, the learned surrogate is optimized by projected gradient descent with 5 random restarts and 200 steps per restart. Metrics. To keep the appendix tables compact, we report the number of trainable parameters (Params), the relative ℓ2 test error (Test RelErr), the downstream regret f (x̂) − f (x⋆ ) (Regret), the decision error ∥x̂ − x⋆ ∥2 , the wall-clock training time in seconds (Train), and the decision-time cost in milliseconds (Infer). Entries are reported as mean ± standard deviation over random seeds. Neural surrogates use 3 seeds; PCF and DCP use 2–3 seeds depending on the configuration. Results. Tables 14–16 summarize the complete results. The overall strongest baseline is PCF, which achieves the lowest regret in most task–dimension settings. Within the neural surrogate family, however, the results still support the value of structured curvature injection: Quad is the most robust variant overall, while SOC remains competitive on several SOCPand logistic-type tasks. A second consistent observation is the mismatch between upstream fitting and downstream decision quality: Softplus can attain relatively small test errors, yet often yields much worse regret than the better-performing 20
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
curvature-injected models. Finally, the learned neural surrogates are substantially faster than DCP at both training and inference time, while remaining competitive with PCF in decision-time cost. The additional flexibility introduced by the Norm module does not translate into uniformly better downstream decisions, indicating that more elaborate curvature parameterizations are not always advantageous on this benchmark. Table 14. Experiment 3 full results at dimension d = 10. Task
Model
Params
Test RelErr
Regret
box logsumexp
DCP PCF Norm Quad ReLU SOC Softplus
1245 753 21777 21586 26371 21968 26371
0.058 ± 0.002 0.032 ± 0.001 0.078 ± 0.014 0.096 ± 0.026 0.072 ± 0.010 0.081 ± 0.019 0.115 ± 0.001
box socp
DCP PCF Norm Quad ReLU SOC Softplus
1245 753 21777 21586 26371 21968 26371
budget huber
DCP PCF Norm Quad ReLU SOC Softplus
∥x − x̂∥2
Train (s)
Infer (s)
0.089 ± 0.005 0.057 ± 0.009 0.293 ± 0.015 0.261 ± 0.027 0.358 ± 0.023 0.299 ± 0.017 0.522 ± 0.078
0.423 ± 0.034 461.3 ± 0.5 0.288 ± 0.029 237.4 ± 1.0 0.567 ± 0.025 123.2 ± 2.6 0.517 ± 0.019 111.7 ± 10.6 0.724 ± 0.038 114.0 ± 0.7 0.574 ± 0.024 84.7 ± 9.7 0.979 ± 0.082 114.1 ± 0.6
9.60 ± 0.01 1.68 ± 0.00 1.30 ± 0.01 1.07 ± 0.00 0.81 ± 0.00 1.55 ± 0.01 0.81 ± 0.01
0.094 ± 0.004 0.062 ± 0.003 0.166 ± 0.056 0.155 ± 0.058 0.117 ± 0.022 0.202 ± 0.011 0.171 ± 0.010
0.225 ± 0.020 0.124 ± 0.003 0.325 ± 0.037 0.214 ± 0.029 0.328 ± 0.016 0.218 ± 0.015 0.718 ± 0.145
0.480 ± 0.035 463.7 ± 3.3 0.343 ± 0.010 240.5 ± 7.6 0.569 ± 0.026 119.1 ± 10.4 0.391 ± 0.025 105.8 ± 24.1 0.533 ± 0.032 115.0 ± 0.1 0.395 ± 0.019 113.0 ± 20.8 0.827 ± 0.102 114.5 ± 0.1
9.61 ± 0.05 1.68 ± 0.00 1.30 ± 0.01 1.08 ± 0.01 0.82 ± 0.01 1.56 ± 0.02 0.82 ± 0.01
1245 753 21777 21586 26371 21968 26371
0.072 ± 0.007 0.041 ± 0.002 0.106 ± 0.043 0.072 ± 0.011 0.063 ± 0.004 0.089 ± 0.014 0.057 ± 0.001
0.368 ± 0.046 0.139 ± 0.033 0.211 ± 0.022 0.140 ± 0.022 0.211 ± 0.003 0.161 ± 0.004 0.501 ± 0.006
0.807 ± 0.007 462.6 ± 0.3 12.19 ± 0.02 0.516 ± 0.048 235.2 ± 0.1 4.49 ± 0.04 0.632 ± 0.036 127.1 ± 0.6 3.22 ± 0.02 0.529 ± 0.021 116.1 ± 9.2 3.02 ± 0.02 0.631 ± 0.018 114.0 ± 0.7 2.72 ± 0.03 0.571 ± 0.006 114.8 ± 14.9 3.33 ± 0.01 0.907 ± 0.028 114.2 ± 0.5 2.72 ± 0.04
budget twocone socp DCP PCF Norm Quad ReLU SOC Softplus
1245 753 21777 21586 26371 21968 26371
0.064 ± 0.007 0.038 ± 0.002 0.033 ± 0.001 0.046 ± 0.004 0.050 ± 0.005 0.035 ± 0.006 0.049 ± 0.001
0.516 ± 0.049 0.217 ± 0.014 0.240 ± 0.037 0.228 ± 0.012 0.249 ± 0.018 0.228 ± 0.025 0.676 ± 0.035
0.674 ± 0.028 0.422 ± 0.017 0.477 ± 0.039 0.468 ± 0.016 0.483 ± 0.021 0.461 ± 0.025 0.749 ± 0.020
simplex logistic
DCP PCF Norm Quad ReLU SOC Softplus
1245 753 21777 21586 26371 21968 26371
0.012 ± 0.002 0.004 ± 0.001 0.078 ± 0.025 0.069 ± 0.013 0.028 ± 0.009 0.170 ± 0.037 0.013 ± 0.000
0.334 ± 0.032 0.206 ± 0.025 0.202 ± 0.011 0.139 ± 0.018 0.171 ± 0.033 0.184 ± 0.013 0.388 ± 0.008
0.600 ± 0.019 462.5 ± 0.2 11.98 ± 0.02 0.442 ± 0.029 235.1 ± 0.4 4.26 ± 0.01 0.444 ± 0.013 126.2 ± 0.9 3.08 ± 0.03 0.410 ± 0.016 99.5 ± 5.9 2.89 ± 0.02 0.428 ± 0.032 114.1 ± 0.6 2.63 ± 0.05 0.433 ± 0.011 118.2 ± 10.7 3.25 ± 0.01 0.610 ± 0.009 114.3 ± 1.1 2.61 ± 0.02
simplex socp
DCP PCF Norm Quad ReLU SOC Softplus
1245 753 21777 21586 26371 21968 26371
0.101 ± 0.009 0.065 ± 0.007 0.088 ± 0.031 0.084 ± 0.032 0.110 ± 0.026 0.121 ± 0.066 0.085 ± 0.005
0.170 ± 0.019 0.093 ± 0.016 0.102 ± 0.013 0.091 ± 0.013 0.086 ± 0.010 0.091 ± 0.010 0.234 ± 0.024
0.373 ± 0.011 464.5 ± 3.7 11.99 ± 0.01 0.276 ± 0.028 236.3 ± 1.8 4.28 ± 0.03 0.276 ± 0.013 107.3 ± 25.8 3.15 ± 0.03 0.268 ± 0.020 106.4 ± 16.7 2.90 ± 0.05 0.263 ± 0.013 114.7 ± 0.7 2.66 ± 0.03 0.270 ± 0.016 132.8 ± 3.8 3.26 ± 0.01 0.388 ± 0.008 114.8 ± 0.8 2.62 ± 0.04
464.3 ± 3.2 12.39 ± 0.24 234.9 ± 0.3 4.45 ± 0.01 126.7 ± 1.3 3.21 ± 0.02 110.0 ± 9.6 3.01 ± 0.02 113.4 ± 0.6 2.74 ± 0.03 134.3 ± 0.7 3.33 ± 0.01 109.9 ± 4.6 2.69 ± 0.00
Table 15. Experiment 3 full results at dimension d = 20. Task
Model
Params
Test RelErr
Regret
∥x − x̂∥2
Train (s)
Infer (s)
box logsumexp
DCP PCF Norm Quad
1815 1263 25127 24546
0.058 ± 0.000 0.031 ± 0.002 0.171 ± 0.039 0.122 ± 0.020
0.187 ± 0.001 0.094 ± 0.002 0.788 ± 0.030 0.614 ± 0.020
0.707 ± 0.019 0.435 ± 0.018 1.123 ± 0.046 0.914 ± 0.018
460.7 ± 0.3 234.2 ± 0.5 92.4 ± 8.7 76.7 ± 0.9
9.65 ± 0.02 1.68 ± 0.01 1.27 ± 0.00 1.07 ± 0.00
21
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions Table 15 – continued from previous page Task
Test RelErr
Regret
∥x − x̂∥2
Model
Params
Train (s)
Infer (s)
ReLU SOC Softplus
29261 0.110 ± 0.015 0.804 ± 0.042 1.204 ± 0.042 107.1 ± 11.1 25708 0.121 ± 0.030 0.671 ± 0.010 0.967 ± 0.023 71.8 ± 6.7 29261 0.111 ± 0.005 1.033 ± 0.034 1.458 ± 0.057 114.7 ± 0.6
0.81 ± 0.00 1.52 ± 0.00 0.81 ± 0.00
box socp
DCP PCF Norm Quad ReLU SOC Softplus
1815 1263 25127 24546 29261 25708 29261
0.095 ± 0.009 0.060 ± 0.001 0.099 ± 0.020 0.110 ± 0.024 0.185 ± 0.033 0.131 ± 0.042 0.144 ± 0.007
0.602 ± 0.099 0.209 ± 0.022 0.414 ± 0.008 0.306 ± 0.014 0.738 ± 0.132 0.385 ± 0.031 1.116 ± 0.038
0.840 ± 0.060 0.489 ± 0.021 0.701 ± 0.010 0.571 ± 0.021 0.908 ± 0.088 0.659 ± 0.019 1.147 ± 0.004
budget huber
DCP PCF Norm Quad ReLU SOC Softplus
1815 1263 25127 24546 29261 25708 29261
0.084 ± 0.008 0.057 ± 0.004 0.669 ± 0.501 0.512 ± 0.174 0.468 ± 0.266 0.371 ± 0.040 0.098 ± 0.004
0.583 ± 0.015 0.310 ± 0.005 0.496 ± 0.044 0.365 ± 0.060 0.467 ± 0.038 0.391 ± 0.051 1.031 ± 0.111
1.036 ± 0.043 460.0 ± 0.1 12.19 ± 0.03 0.793 ± 0.020 234.2 ± 0.1 4.40 ± 0.00 1.016 ± 0.025 119.9 ± 7.3 3.19 ± 0.01 0.901 ± 0.030 80.8 ± 11.2 3.01 ± 0.01 1.024 ± 0.021 113.3 ± 2.4 2.71 ± 0.03 0.933 ± 0.006 108.2 ± 20.9 3.33 ± 0.01 1.303 ± 0.058 115.2 ± 0.9 2.71 ± 0.03
budget twocone socp DCP PCF Norm Quad ReLU SOC Softplus
1815 1263 25127 24546 29261 25708 29261
0.061 ± 0.001 0.037 ± 0.001 0.036 ± 0.003 0.097 ± 0.037 0.081 ± 0.016 0.061 ± 0.021 0.084 ± 0.033
0.695 ± 0.120 0.389 ± 0.040 0.536 ± 0.043 0.403 ± 0.015 0.477 ± 0.047 0.477 ± 0.025 1.199 ± 0.300
0.870 ± 0.083 462.1 ± 0.5 12.18 ± 0.03 0.656 ± 0.037 237.0 ± 3.6 4.44 ± 0.01 0.780 ± 0.038 125.0 ± 2.4 3.22 ± 0.01 0.692 ± 0.012 91.3 ± 21.8 3.01 ± 0.02 0.748 ± 0.045 110.3 ± 8.7 2.71 ± 0.01 0.736 ± 0.027 121.9 ± 18.8 3.33 ± 0.00 1.077 ± 0.126 85.6 ± 41.7 2.70 ± 0.02
simplex logistic
DCP PCF Norm Quad ReLU SOC Softplus
1815 1263 25127 24546 29261 25708 29261
0.010 ± 0.001 0.003 ± 0.000 0.215 ± 0.009 0.296 ± 0.084 0.139 ± 0.036 0.172 ± 0.050 0.013 ± 0.003
0.467 ± 0.030 0.284 ± 0.029 0.349 ± 0.023 0.300 ± 0.042 0.305 ± 0.028 0.320 ± 0.021 0.493 ± 0.031
0.747 ± 0.015 460.2 ± 0.2 11.97 ± 0.02 0.606 ± 0.021 234.9 ± 0.2 4.24 ± 0.02 0.666 ± 0.019 93.0 ± 48.6 3.07 ± 0.02 0.687 ± 0.012 100.5 ± 16.3 2.85 ± 0.02 0.684 ± 0.015 102.5 ± 8.7 2.66 ± 0.06 0.671 ± 0.018 116.4 ± 6.2 3.23 ± 0.01 0.792 ± 0.016 89.3 ± 6.5 2.61 ± 0.01
simplex socp
DCP PCF Norm Quad ReLU SOC Softplus
1815 1263 25127 24546 29261 25708 29261
0.086 ± 0.001 0.063 ± 0.006 0.329 ± 0.183 0.589 ± 0.133 0.465 ± 0.279 0.728 ± 0.100 0.134 ± 0.017
0.267 ± 0.030 0.165 ± 0.006 0.177 ± 0.020 0.167 ± 0.010 0.197 ± 0.016 0.181 ± 0.014 0.354 ± 0.035
0.442 ± 0.021 465.3 ± 7.4 12.01 ± 0.05 0.372 ± 0.013 236.5 ± 3.6 4.28 ± 0.05 0.355 ± 0.021 112.2 ± 14.9 3.10 ± 0.04 0.349 ± 0.016 105.9 ± 8.3 2.89 ± 0.04 0.380 ± 0.030 84.4 ± 17.0 2.67 ± 0.05 0.352 ± 0.020 118.9 ± 25.5 3.25 ± 0.00 0.488 ± 0.027 49.8 ± 3.6 2.64 ± 0.05
460.2 ± 0.2 234.2 ± 0.6 102.8 ± 7.2 77.7 ± 5.3 99.3 ± 23.2 74.0 ± 5.1 115.8 ± 0.6
9.62 ± 0.03 1.69 ± 0.01 1.28 ± 0.01 1.08 ± 0.01 0.82 ± 0.01 1.52 ± 0.01 0.82 ± 0.01
Table 16. Experiment 3 full results at dimension d = 50. Task
Model
Params
Test RelErr
Regret
∥x − x̂∥2
Train (s)
Infer (s)
box logsumexp
DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.047 ± 0.002 0.029 ± 0.001 0.042 ± 0.000 0.042 ± 0.001 0.058 ± 0.000 0.040 ± 0.000 0.083 ± 0.003
0.679 ± 0.007 0.549 ± 0.002 1.583 ± 0.057 1.688 ± 0.067 1.592 ± 0.018 1.597 ± 0.034 2.638 ± 0.067
1.488 ± 0.013 1.030 ± 0.005 1.633 ± 0.031 1.788 ± 0.076 1.724 ± 0.028 1.601 ± 0.043 2.575 ± 0.048
460.5 ± 0.1 235.8 ± 0.2 80.0 ± 1.7 61.5 ± 6.4 99.6 ± 14.1 61.4 ± 5.9 117.5 ± 0.6
9.66 ± 0.00 1.67 ± 0.00 1.28 ± 0.00 1.07 ± 0.01 0.81 ± 0.00 1.53 ± 0.00 0.81 ± 0.00
box socp
DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.071 ± 0.001 0.041 ± 0.001 0.034 ± 0.001 0.039 ± 0.001 0.068 ± 0.000 0.036 ± 0.001 0.078 ± 0.002
2.881 ± 0.189 0.628 ± 0.010 1.676 ± 0.095 1.346 ± 0.087 2.032 ± 0.283 1.376 ± 0.019 3.917 ± 0.293
1.813 ± 0.055 0.796 ± 0.017 1.243 ± 0.051 1.145 ± 0.044 1.402 ± 0.083 1.085 ± 0.012 2.008 ± 0.067
460.5 ± 0.9 237.1 ± 1.2 111.2 ± 7.5 63.0 ± 5.1 94.7 ± 10.0 55.4 ± 10.2 117.0 ± 0.5
9.62 ± 0.00 1.68 ± 0.01 1.28 ± 0.00 1.08 ± 0.00 0.81 ± 0.00 1.53 ± 0.02 0.82 ± 0.00
22
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions Table 16 – continued from previous page Task
Model
Params
Test RelErr
Regret
∥x − x̂∥2
budget huber
DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.056 ± 0.002 0.038 ± 0.004 0.035 ± 0.000 0.035 ± 0.000 0.057 ± 0.001 0.035 ± 0.001 0.060 ± 0.000
1.674 ± 0.151 1.220 ± 0.002 1.650 ± 0.049 1.270 ± 0.038 1.665 ± 0.220 1.617 ± 0.010 3.864 ± 0.049
1.880 ± 0.040 1.561 ± 0.033 1.833 ± 0.029 1.682 ± 0.027 1.872 ± 0.124 1.839 ± 0.008 2.538 ± 0.012
460.6 ± 0.1 12.19 ± 0.04 235.8 ± 0.1 4.47 ± 0.01 94.1 ± 6.5 3.23 ± 0.01 59.1 ± 2.9 3.05 ± 0.01 117.3 ± 0.6 2.73 ± 0.03 50.8 ± 8.5 3.34 ± 0.01 117.4 ± 0.6 2.76 ± 0.04
budget twocone socp DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.062 ± 0.002 0.037 ± 0.001 0.026 ± 0.000 0.029 ± 0.000 0.061 ± 0.005 0.026 ± 0.001 0.060 ± 0.000
1.815 ± 0.053 0.809 ± 0.094 1.254 ± 0.040 1.145 ± 0.072 1.333 ± 0.122 1.309 ± 0.013 3.487 ± 0.179
1.523 ± 0.028 1.005 ± 0.042 1.247 ± 0.015 1.212 ± 0.016 1.305 ± 0.062 1.282 ± 0.018 1.981 ± 0.036
462.3 ± 1.2 12.25 ± 0.02 236.0 ± 0.3 4.45 ± 0.00 80.2 ± 4.8 3.21 ± 0.01 56.0 ± 6.3 3.03 ± 0.01 99.6 ± 24.3 2.73 ± 0.03 64.3 ± 11.3 3.33 ± 0.01 116.2 ± 2.1 2.76 ± 0.05
simplex logistic
DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.007 ± 0.001 0.001 ± 0.000 0.097 ± 0.032 0.095 ± 0.057 0.046 ± 0.018 0.082 ± 0.040 0.008 ± 0.001
0.575 ± 0.003 0.394 ± 0.050 0.450 ± 0.020 0.363 ± 0.033 0.411 ± 0.035 0.367 ± 0.018 0.604 ± 0.037
0.608 ± 0.027 0.516 ± 0.017 0.558 ± 0.010 0.532 ± 0.016 0.560 ± 0.021 0.524 ± 0.005 0.597 ± 0.011
460.4 ± 0.7 12.03 ± 0.01 236.3 ± 0.2 4.30 ± 0.02 76.1 ± 42.4 3.07 ± 0.01 55.0 ± 24.6 2.87 ± 0.02 91.7 ± 17.4 2.64 ± 0.00 89.6 ± 9.7 3.24 ± 0.00 98.0 ± 23.8 2.64 ± 0.04
simplex socp
DCP PCF Norm Quad ReLU SOC Softplus
3525 2793 101961 99010 117275 104912 117275
0.057 ± 0.003 0.028 ± 0.002 0.656 ± 0.174 1.174 ± 0.334 0.578 ± 0.064 0.859 ± 0.211 0.105 ± 0.017
0.425 ± 0.008 0.286 ± 0.014 0.356 ± 0.004 0.347 ± 0.006 0.365 ± 0.011 0.354 ± 0.004 0.449 ± 0.007
0.490 ± 0.008 0.423 ± 0.014 0.430 ± 0.015 0.434 ± 0.008 0.449 ± 0.005 0.428 ± 0.001 0.481 ± 0.024
467.4 ± 10.1 12.22 ± 0.29 238.2 ± 2.3 4.31 ± 0.05 112.6 ± 14.8 3.14 ± 0.01 116.4 ± 13.2 2.94 ± 0.04 109.2 ± 6.2 2.66 ± 0.03 126.1 ± 22.3 3.27 ± 0.02 76.8 ± 20.5 2.64 ± 0.04
Train (s)
Infer (s)
C. Extension to Convolutional SOC-ICNNs In the main text, the proposed SOC-ICNN is presented in fully connected form for clarity. We now show that the same construction extends directly to convolutional architectures. This extension does not change the underlying optimization class: it only replaces dense affine maps by convolutional linear operators with parameter sharing and sparse structure. Consequently, the convexity results, the LP value-function interpretation of the ReLU backbone in Proposition 1, and the SOCP value-function interpretation in Theorem 1 all remain valid. C.1. Convolution as a Structured Linear Operator Let the input be a tensor X ∈ RC0 ×H0 ×W0 . For any tensor Y , let vec(Y ) denote its vectorization into a column vector. Fix a discrete convolution operator K together with its stride, padding, and dilation. Then there exists a matrix T (K) such that vec(K(Y )) = T (K) vec(Y ).
(24)
The matrix T (K) is the usual sparse Toeplitz / block-Toeplitz matrix induced by the convolution. Thus, every convolutional layer is still a linear map with respect to the input tensor, and every affine convolutional layer is of the form Y 7→ K(Y ) + B for some bias tensor B. Therefore, after vectorization, a convolutional architecture is simply a fully connected architecture with highly structured sparse matrices. This observation is the only fact needed to transfer the value-function interpretation from the fully connected setting to the convolutional setting. 23
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
C.2. Convolutional ReLU-ICNN Backbone We define the convolutional ReLU-ICNN backbone recursively as follows. Let Z0 = 0, and for ℓ = 1, . . . , L define Zℓ = σ Wℓ (X) + Uℓ (Zℓ−1 ) + Bℓ , (25) where: • Wℓ is an unconstrained input-to-hidden convolutional affine map; • Uℓ is a hidden-to-hidden convolutional linear map whose kernel coefficients are constrained to be elementwise nonnegative; • Bℓ is a bias tensor; • σ(t) = max{t, 0} is applied elementwise. The scalar output is defined by fReLU-CNN (X) = ⟨C, ZL ⟩ + ⟨V, X⟩ + b0 ,
(26)
where C ≥ 0 elementwise, V is unconstrained, and ⟨·, ·⟩ denotes the Euclidean inner product between same-sized tensors. This is the exact convolutional analogue of the fully connected ReLU-ICNN in Section 3, with dense affine maps replaced by convolutional affine maps. C.3. Convolutional Backbone Remains Convex We now make explicit why replacing dense layers by convolutional layers does not destroy input convexity. Proposition 6 (Convexity of the convolutional ReLU-ICNN backbone). The function X 7→ fReLU-CNN (X) defined by (25)–(26) is convex with respect to the input tensor X. Proof. The proof follows the same inductive logic as for standard ICNNs, but we spell it out because the convolutional case is easy to misunderstand. Step 1: Convolution is affine in the input. For each layer ℓ, both Wℓ (X) and Uℓ (Zℓ−1 ) are affine / linear with respect to their arguments. Hence, if each entry of Zℓ−1 (X) is a convex function of X, then each entry of Uℓ (Zℓ−1 (X)) is a nonnegative linear combination of translated entries of Zℓ−1 (X), and is therefore convex in X. More explicitly, fix an output channel and spatial position index p. The corresponding entry of Uℓ (Zℓ−1 (X)) can be written as XX Uℓ (Zℓ−1 (X)) p = u(ℓ) pqr [Zℓ−1 (X)]q,r , q
r
(ℓ) (ℓ) where the coefficients upqr are the convolution kernel coefficients. Because Uℓ ≥ 0 elementwise, we have upqr ≥ 0 for all
indices. Thus, if each [Zℓ−1 (X)]q,r is convex in X, then the above sum is convex in X. Step 2: The pre-activation is convex.
Define the pre-activation tensor Sℓ (X) = Wℓ (X) + Uℓ (Zℓ−1 (X)) + Bℓ .
Since Wℓ (X) is affine in X, Uℓ (Zℓ−1 (X)) is convex in X by Step 1, and adding a bias preserves convexity, every entry of Sℓ (X) is convex in X. Step 3: ReLU preserves convexity because it is convex and monotone nondecreasing. For each scalar entry s(X) of Sℓ (X), the corresponding activation is σ(s(X)) = max{s(X), 0}. Since s(X) is convex and σ is a convex, nondecreasing scalar function, the composition σ ◦ s is convex. Equivalently, one may directly note that max{s(X), 0} is the maximum of two convex functions, hence convex. Therefore, every entry of Zℓ (X) is convex in X. 24
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Step 4: Induction over layers.
At layer ℓ = 1, we have Z1 (X) = σ(W1 (X) + B1 ),
whose entries are convex because W1 (X) + B1 is affine. Applying Steps 1–3 inductively proves that every entry of every hidden tensor Zℓ (X) is convex in X. Step 5: Final readout preserves convexity.
The output
fReLU-CNN (X) = ⟨C, ZL (X)⟩ + ⟨V, X⟩ + b0 is the sum of: (i) a nonnegative linear combination of convex entries of ZL (X), because C ≥ 0 elementwise; (ii) an affine term ⟨V, X⟩ + b0 . Hence fReLU-CNN (X) is convex in X. The key point is therefore unchanged from the fully connected setting: the hidden-to-hidden operator must preserve convexity, and this is ensured by constraining its coefficients to be nonnegative. A convolutional kernel is just a structured collection of linear coefficients; as long as those coefficients are nonnegative, the ICNN convexity argument survives verbatim. C.4. LP Value-Function Interpretation of the Convolutional Backbone The previous proposition establishes convexity directly. We now show that the convolutional ReLU backbone also admits the same LP value-function interpretation as Proposition 1. Proposition 7 (Convolutional LP value-function representation). For every input tensor X, the output fReLU-CNN (X) equals the optimal value of the following linear program: fReLU-CNN (X) = min
{Zℓ }L ℓ=1
s.t.
⟨C, ZL ⟩ + ⟨V, X⟩ + b0 Zℓ ≥ Wℓ (X) + Uℓ (Zℓ−1 ) + Bℓ , Zℓ ≥ 0,
ℓ = 1, . . . , L,
(27)
ℓ = 1, . . . , L,
Z0 = 0. Proof. The argument is exactly parallel to Proposition 1. For fixed input X, the ReLU recursion in (25) computes the componentwise smallest feasible activation tensor satisfying the linear inequalities in (27). Because the output coefficient tensor C is elementwise nonnegative, the objective is monotone nondecreasing in the entries of ZL . Hence the smallest feasible tensor minimizes the objective, and the LP optimum equals the forward output. Equivalently, after vectorizing all tensors, (27) becomes min
{zℓ }L ℓ=1
s.t.
c⊤ zL + v ⊤ x + b0 zℓ ≥ Wℓ x + Uℓ zℓ−1 + bℓ , zℓ ≥ 0,
ℓ = 1, . . . , L,
(28)
ℓ = 1, . . . , L,
z0 = 0, where x = vec(X), zℓ = vec(Zℓ ), and the matrices Wℓ , Uℓ are precisely the structured sparse matrices induced by the convolutional operators Wℓ , Uℓ . This is exactly the LP form in Proposition 1. Thus, moving from fully connected layers to convolutional layers changes only the parameterization of the affine operators, not the underlying LP value-function nature of the ReLU-ICNN backbone. C.5. Convolutional SOC-ICNN We now augment the convolutional ReLU backbone with the same two geometric primitives used in the main text. 25
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Quadratic convolutional branch. define the h-th quadratic branch by
For each h = 1, . . . , H, let Bh be an affine convolutional operator acting on X. We
αh 2 ∥Bh (X) + Eh ∥F , 2 where Eh is a bias tensor and ∥ · ∥F denotes the Frobenius norm.
αh ≥ 0,
(29)
Conic convolutional branch. For each g = 1, . . . , G, let Ag be another affine convolutional operator acting on X. We define the g-th conic branch by λg ∥Ag (X) + Dg ∥F , λg ≥ 0, (30) where Dg is a bias tensor. The full convolutional SOC-ICNN is then defined as
fSOC-CNN (X) = fReLU-CNN (X) +
H X αh h=1
2
2
∥Bh (X) + Eh ∥F +
G X
λg ∥Ag (X) + Dg ∥F .
(31)
g=1
The role of the three terms is exactly the same as in (11): the convolutional ReLU backbone captures polyhedral structure, the quadratic convolutional branches inject explicit PSD curvature, and the conic convolutional branches inject Euclidean norm geometry at the level of feature maps. C.6. Convolutional SOC-ICNN Remains Convex We now make explicit why the full convolutional SOC-ICNN still preserves input convexity. Proposition 8 (Convexity of convolutional SOC-ICNN). The function X 7→ fSOC-CNN (X) defined in (31) is convex with respect to the input tensor X. Proof. By Proposition 6, the backbone term fReLU-CNN (X) is convex in X. For each quadratic branch, the map X 7→ Bh (X) + Eh is affine in X, because Bh is an affine convolutional operator. Hence X 7→
αh ∥Bh (X) + Eh ∥2F 2
is convex for every αh ≥ 0, since the squared Frobenius norm of an affine map is convex. Likewise, for each conic branch, the map X 7→ Ag (X) + Dg is affine in X, so X 7→ λg ∥Ag (X) + Dg ∥F is convex for every λg ≥ 0, since the Frobenius norm is convex and convexity is preserved under composition with affine maps. Finally, a nonnegative sum of convex functions is convex. Therefore, fSOC-CNN (X) = fReLU-CNN (X) +
H X αh h=1
2
∥Bh (X) + Eh ∥2F +
G X
λg ∥Ag (X) + Dg ∥F
g=1
is convex in X. This proposition shows that the transition from dense affine maps to convolutional affine maps does not alter the convexanalytic foundation of SOC-ICNN. The reason is simple but fundamental: convexity in the main text relies only on affine dependence on the input, nonnegative hidden-to-hidden coefficients in the ICNN backbone, and convex norm / squared-norm primitives. Convolution preserves all three properties. 26
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
C.7. SOCP Value-Function Interpretation We now state the convolutional counterpart of Theorem 1. For each quadratic branch, introduce an auxiliary tensor Qh = Bh (X) + Eh and an epigraph variable sh satisfying (sh , 1, vec(Qh )) ∈ Qnr h +2 ,
(32)
where nh = dim(vec(Qh )). For each conic branch, introduce an auxiliary tensor Ug = Ag (X) + Dg and an epigraph variable tg satisfying (vec(Ug ), tg ) ∈ Qmg +1 ,
(33)
where mg = dim(vec(Ug )). Theorem 2 (Convolutional SOC-ICNN as an SOCP value function). For every input tensor X, the output in (31) is exactly equal to the optimal value of the following SOCP: fSOC-CNN (X) = min ⟨C, ZL ⟩ + ⟨V, X⟩ + b0 + η
s.t.
H X
αh sh +
λg tg
g=1
h=1
Zℓ ≥ Wℓ (X) + Uℓ (Zℓ−1 ) + Bℓ , Zℓ ≥ 0,
G X
ℓ = 1, . . . , L, (34)
ℓ = 1, . . . , L,
Z0 = 0, Qh = Bh (X) + Eh ,
(sh , 1, vec(Qh )) ∈ Qnr h +2 , mg +1
Ug = Ag (X) + Dg ,
(vec(Ug ), tg ) ∈ Q
,
h = 1, . . . , H, g = 1, . . . , G,
where η = {Zℓ , Qh , sh , Ug , tg }. Proof. The proof is the exact convolutional analogue of Theorem 1. Let V (X) denote the optimal value of (34). Upper bound: V (X) ≤ fSOC-CNN (X). Take the forward activations Z̄ℓ produced by the convolutional ReLU backbone, so that ⟨C, Z̄L ⟩ + ⟨V, X⟩ + b0 = fReLU-CNN (X). For each quadratic branch, set Q̄h = Bh (X) + Eh ,
s̄h =
1 ∥Q̄h ∥2F . 2
Then (s̄h , 1, vec(Q̄h )) ∈ Qnr h +2 . For each conic branch, set Ūg = Ag (X) + Dg ,
t̄g = ∥Ūg ∥F .
Then (vec(Ūg ), t̄g ) ∈ Qmg +1 . Therefore this choice is feasible for (34), and its objective value is exactly fReLU-CNN (X) +
H X αh h=1
2
∥Bh (X) + Eh ∥2F +
G X
λg ∥Ag (X) + Dg ∥F = fSOC-CNN (X).
g=1
Hence, V (X) ≤ fSOC-CNN (X). 27
SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Lower bound: V (X) ≥ fSOC-CNN (X).
Take any feasible point of (34). By Proposition 7,
⟨C, ZL ⟩ + ⟨V, X⟩ + b0 ≥ fReLU-CNN (X). Moreover, the rotated cone constraints imply sh ≥
1 1 ∥Qh ∥2F = ∥Bh (X) + Eh ∥2F , 2 2
and the standard cone constraints imply tg ≥ ∥Ug ∥F = ∥Ag (X) + Dg ∥F . Multiplying by the nonnegative coefficients αh , λg and summing yields H X
αh sh ≥
h=1
and
G X
H X αh h=1
λg tg ≥
g=1
G X
2
∥Bh (X) + Eh ∥2F ,
λg ∥Ag (X) + Dg ∥F .
g=1
Therefore every feasible objective value in (34) is at least fReLU-CNN (X) +
H X αh h=1
2
∥Bh (X) + Eh ∥2F +
G X
λg ∥Ag (X) + Dg ∥F = fSOC-CNN (X).
g=1
Hence, V (X) ≥ fSOC-CNN (X). Combining the two inequalities proves V (X) = fSOC-CNN (X).
C.8. Relation to the Main Theoretical Results The convolutional extension is not a different theory, but a different parameterization of the same theory. Proposition 9 (Equivalence after vectorization). After vectorization, every convolutional SOC-ICNN can be written as a fully connected SOC-ICNN whose affine operators are structured sparse matrices induced by convolution. Consequently, the representational and optimization-theoretic conclusions of the main text extend directly to the convolutional setting. Proof. By (24), every convolutional operator admits a matrix representation after vectorization. Applying this to all operators Wℓ , Uℓ , Bh , Ag transforms the convolutional model into the fully connected form of (3), (11), and (16), except that the corresponding matrices are sparse and share parameters according to convolutional structure. Therefore: (i) Proposition 1 becomes Proposition 7; (ii) Theorem 1 becomes Theorem 2; and (iii) the function-class enlargement argument of Proposition 4 carries over directly, since the quadratic and conic branches remain exact structured primitives after vectorization. In particular, the strict enlargement from polyhedral LP geometry to conic SOCP geometry is unchanged. What changes is only the inductive bias: the convolutional version is tailored to spatially structured inputs and benefits from local connectivity and parameter sharing, while retaining the same convexity guarantees and the same exact value-function interpretation. Remark 2 (On allowed CNN modules). The above extension applies directly to any linear convolutional module, including standard convolutions, strided convolutions, dilated convolutions, transposed convolutions, 1 × 1 convolutions, and average pooling. To preserve the exact LP/SOCP value-function interpretation in the present form, one should avoid inserting additional nonlinear operators such as batch normalization inside the convex backbone, unless they are analyzed separately. 28