Idea description

Build a positively homogeneous convex network by representing every intermediate unit as a compact polytope and composing units with Minkowski sums, convex-hull unions, and positive dilations. This gives an explicitly convex and monotone architecture whose geometric complexity can be controlled independently of the number of sampled linear pieces, potentially producing smaller ICNNs for structured convex functions.

Formulas

$$f_P(x)=\max_{p\in P}p^\top x,$$

$$\varphi(P+Q)=f_{P+Q}=f_P+f_Q,\qquad \varphi(\operatorname{conv}(P\cup Q))=f_{\operatorname{conv}(P\cup Q)}=\max\{f_P,f_Q\},$$

$$\varphi(\lambda P)=f_{\lambda P}=\lambda f_P,\qquad \lambda\geq0,$$

$$\widehat f(x)=\max_{r=1,\ldots,R}\left(\sum_{j=1}^{m}\alpha_{rj}f_{P_j}(x)\right),\qquad \alpha_{rj}\geq0,$$

Mathematical statement

The paper defines $\mathcal{F}^{d}$ as positively homogeneous convex CPWL functions on $\mathbb{R}^{d}$, and $\mathcal{P}^{d}$ as polytopes in $\mathbb{R}^{d}$. The bijection $\varphi(P)=f_P$ maps a polytope $P$ to its support function $f_P(x)=\max_{p\in P}p^{\top}x$. It satisfies $f_{P+Q}=f_P+f_Q$, $f_{\operatorname{conv}(P\cup Q)}=\max\{f_P,f_Q\}$, and $f_{\lambda P}=\lambda f_P$ for $\lambda\geq0$. For monotone functions, the corresponding polytopes lie in $\mathbb{R}_{\geq0}^{d}$. The implementation exploits these exact identities: a sum of convex units is a Minkowski sum, a max over branches is a convex hull of their union, and a nonnegative scalar is a polytope dilation. Convexity and coordinatewise monotonicity are therefore enforced structurally.

Implementation notes

Integrate this as a replacement for the scalar hidden representation in a homogeneous ICNN or monotone score network. Use input $x\in\mathbb{R}^d$, optionally augmenting it with a constant coordinate to model biases. Maintain each feature $h_j(x)=f_{P_j}(x)$ as a polytope represented by a finite set of nonnegative generator points $V_j$, with a fixed cap on the number of retained points. For branch $r$, form the Minkowski sum $Q_r=\sum_j\alpha_{rj}P_j$, where $\alpha_{rj}=\operatorname{softplus}(u_{rj})$ guarantees nonnegative dilation. The branch output is $s_r(x)=\max_{q\in Q_r}q^\top x$. Exact enumeration creates a Cartesian product, so use beam search: initialize $C=\{0\}$; for each $j$, replace $C$ by the top $B$ vectors $c+\alpha_{rj}v$, ranked by dot product with the current input, for $c\in C,v\in V_j$; then set $s_r=\max_{c\in C}c^\top x$. Return $\max_r s_r$, corresponding to the support function of $\operatorname{conv}(Q_1\cup\cdots\cup Q_R)$. The exact mathematics is the Minkowski-sum, convex-hull, and dilation identities; beam width $B$, vertex pruning, and finite generator caps are approximations. First test on synthetic convex regression targets formed as maxima of sums of nonnegative linear forms, comparing a standard ICNN, maxout ICNN, and this model at equal parameters. Measure validation error, convexity violations under finite differences, active-generator count, and wall-clock time. Success is lower error or fewer retained generators at the same exact convexity guarantee.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a positively homogeneous monotone convex network using nonnegative polytope generators, support functions, Minkowski sums, and max branches. Minkowski, convex-hull/max, dilation, and homogeneity sweeps matched their predictions with errors below 1e-15; finite convexity and monotonicity violations were at numerical zero. On a matched synthetic target, the polytope model reached validation MSE 0.000392 with 57 parameters versus ICNN MSE 0.00352 with 204 parameters, while taking 8.64s versus 1.92s, so the accuracy/compactness signal is real but not a speed win.

Agent confidence: 8/10

Baseline: ICNN: validation MSE 0.00351514, 204 parameters, 1.92 s, convex violation 1.44e-6, monotonicity violation 0
Idea: Newton-polytope model: validation MSE 0.000391735, 57 parameters, 8.64 s, convex violation 1.07e-6, monotonicity violation 0; exact identity and homogeneity sweep errors <= 8.9e-16

Limitations: Only a small synthetic regression task was tested, with a target generated from the same support-function family; no real dataset, maxout ICNN, FLOP-normalized comparison, learned beam pruning under varying inputs, or larger-scale polytope complexity study was performed.

How to run: python3 polytope_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.11540) Sep 2, 2026

Beats the tuned baseline by 60.7% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Custom_convex_monotone_support_regression
Model: custom_branch_support_net
Paired seeds: 8
Baseline mean: 0.1503
Idea mean: 0.0591
Effect (Δ): -0.0912 (−60.7%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±35.7%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

The custom task is a small synthetic benchmark with 400 training and 200 test examples, not a real-world dataset. Beam-search pruning, generator-cap scaling, FLOP/parameter parity, and larger datasets were not tested. The local custom track requires the harness runner's documented validate_and_promote step before it becomes permanently registered in bench/custom_tracks.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Worked ✓

Agent confidence: 7/10

The Newton-polytope support-function network significantly outperformed the matched unconstrained branch-support baseline on the structurally matched convex-monotone regression task: mean MSE 0.059063 versus 0.150308, paired delta -0.091245, 8/8 wins, permutation p=0.0081. The trained-model signature confirmed convexity and coordinatewise monotonicity within the 1e-6 numerical tolerance. The custom track is supplied in the experiment folder with registration metadata for bench promotion; no built-in track had the required mathematical structure.

Baseline: Best lr=0.01; full 8-seed mean MSE 0.15030818991363049, std 0.06322827323846641; sweep means: lr=0.001 -> 43.01560401916504, lr=0.003 -> 7.67546808719635, lr=0.01 -> 0.12174218706786633.
Idea: Best lr=0.01; full 8-seed mean MSE 0.059063241351395845, std 0.017577170847583323; paired delta -0.09124494856223464, 8/8 wins, permutation p=0.0081.

Benchmark result