Pith. sign in

REVIEW 5 minor 22 references

Approximation Depth of Convex Polytopes

T0 review · 0 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that, for every depth $d$ below $\lceil \log_2(n+1)\rceil$, every polytope of depth $d$ misses the $n$-simplex by empty-corner distance at least $n+1-2^d$, and that simplices are the only convex bodies whose outer…

desk verdict A sharp inapproximability result for simplices in the depth model, with a clean main proof and a few terse corners that a referee can fix. read the letter →

arxiv 2507.07779 v1 pith:T5FUN74D submitted 2025-07-10 math.MG cs.CGcs.LGmath.CO

Egor Bakaev , Florestan Brunck , Amir Yehudayoff This is my paper · ORCID
classification math.MGcs.CGcs.LGmath.CO MSC 52A2052B1152B12
keywords approximationdepthconvexpolytopesMinkowskisumsimplexempty-cornerdistancecomplexityouteradditivezonotopes
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how well a target polytope can be approximated by polytopes of limited "depth," where depth counts the number of alternating rounds of Minkowski sums and convex hulls of unions used to build the polytope, the same hierarchy that describes convex functions computed by ReLU networks with a given number of hidden layers. Its central result is that simplices are essentially inapproximable at insufficient depth: for every $d < \lceil \log_2(n+1)\rceil$, the best possible empty-corner distance from the $n$-dimensional simplex to any depth-$d$ polytope is exactly $n+1-2^d$. Consequently, no sequence of depth-$d$ polytopes can converge to the simplex in the Hausdorff metric until $d$ reaches the simplex's exact depth complexity. Along the way the paper proves that simplices are the only convex bodies for which the outer homothety coefficient is additive under Minkowski sums, and this additivity is what makes the distance computation exact. The result matters because the simplex is the universal generator for piecewise-linear convex functions, so the distance lower bound transfers to a positive approximation error for shallow networks, measured against uniform directions on the sphere.

What carries the argument

The central object is the empty-corner distance $D_e(L;\Delta_n)$. For the smallest homothet $\Delta_o(L)$ of the simplex containing $L$, each vertex $v$ of $\Delta_o(L)$ has an empty corner of size $E_v(L;\Delta_o(L))$ measuring the largest homothet of $\Delta_n$ inside $\Delta_o(L)$ with vertex $v$ that avoids $L$; the distance is the sum of these sizes divided by the size of $\Delta_o(L)$. The co-distance $\operatorname{co-}D_e = n+1-D_e$ is the quantity that behaves well. The key identity is Claim 15: for a Minkowski sum $L = L_1 + L_2$, the empty-corner sizes add termwise, $E_v(L,\Delta_o(L)) = E_v(L_1,\Delta_o(L_1)) + E_v(L_2,\Delta_o(L_2))$, which implies $D_e(L)$ lies between $D_e(L_1)$ and $D_e(L_2)$. Theorem 3 gives the conjugate inequality for $K * L = \operatorname{conv}(K \cup L)$: $\operatorname{co-}D_e(K * L) \le \operatorname{co-}D_e(K) + \operatorname{co-}D_e(L)$. Running these two inequalities over the inductive definition of $P_{n,d}$ is what forces the value $n+1-2^d$.

What would settle it

The theorem would be refuted by exhibiting a single polytope $P \in P_{n,d}$ with $d < \lceil \log_2(n+1)\rceil$ and $D_e(P;\Delta_n) < n+1-2^d$; the smallest nontrivial case is $n=3, d=1$, where the formula says every centrally symmetric body, i.e. every zonotope, has $D_e = 2$, so a zonotope with $D_e < 2$ would be a direct counterexample.

Watch

Extended reading notes

Core claim

For the simplex $\Delta_n$, the depth hierarchy has an exact approximation profile. Theorem 5 states that for $0 < d < \lceil \log_2(n+1)\rceil$ the minimum empty-corner distance from $\Delta_n$ to a non-point depth-$d$ polytope is $n+1-2^d$, and the minimum is attained. Thus the previously known lower bound on the depth complexity of the simplex is stable: before depth $\lceil \log_2(n+1)\rceil$, approximation is not merely impossible to make exact, it is bounded away from zero by a forced discrete gap. The proof rests on two structural facts: Minkowski sums cannot reduce the distance (Theorem 2 gives $\operatorname{co-}D_e(L) \le \max_j \operatorname{co-}D_e(L_j)$), and the convex hull of a union can at most add the two co-distances (Theorem 3 gives $\operatorname{co-}D_e(L_1 * L_2) \le \operatorname{co-}D_e(L_1) + \operatorname{co-}D_e(L_2)$). Together with the value $\operatorname{co-}D_e = n-1$ for centrally symmetric bodies (Lemma 4, which gives the depth-one base case), the induction forces the exact formula. The paper also proves Theorem 8: a convex body is outer additive if and only if it is a simplex, and Lemmas 6 and 7 relate the empty-corner distance to the in-out distance, transferring the obstruction to the functional and network setting.

Load-bearing premise

The argument that forces the exact value $n+1-2^d$ depends on Claim 15: for Minkowski sums, the empty-corner sizes add exactly, a property proved only for simplices, so if that additivity failed for some summands in the depth hierarchy the induction would no longer force the gap.

Editorial extensions

If this is right

  • If Theorem 5 is correct, then for every $d < \lceil \log_2(n+1)\rceil$ no sequence of depth-$d$ polytopes converges to $\Delta_n$; the distance is bounded below by $n+1-2^d$, and the bound is sharp by an explicit construction.
  • The depth-one case is exactly Lemma 4: every centrally symmetric body, in particular every zonotope, sits at distance $n-1$ from the simplex, so no amount of Minkowski summing improves on the formula at $d=1$.
  • On the function side, the lower bound translates to a uniform positive gap: for fixed $n$ and any depth-$d$ network with $d < \lceil \log_2(n+1)\rceil$, the expected absolute difference between its support function and that of the simplex, over uniform directions on the sphere, is at least some $\varepsilon_0(n) > 0$.
  • The characterization of outer additivity shows the trivial-approximation phenomenon is not an accident of the chosen distance: simplices are the only convex bodies for which the outer coefficient is exactly additive under Minkowski sums.
  • Because the exact gap $n+1-2^d$ is attained, the theorem gives a sharp non-asymptotic tradeoff between depth and approximation quality rather than only an asymptotic inapproximability statement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial: because the exact gap $n+1-2^d$ is attained by a simple construction, the theorem yields a computable certificate: any proposed depth-$d$ approximation can be checked against the empty-corner profile, giving a direct lower-bound test for network depth.
  • Editorial: since the proof of outer additivity needs only interval summands, the characterization of simplices suggests a practical finite test for recognizing simplex-shaped convex bodies: test additivity against pairs of intervals in sufficiently many directions.
  • Editorial: a natural testable extension is to replace the simplex by another simplex-faced indecomposable polytope and ask whether an analogous exact corner-distance formula holds; the proof here is simplex-specific, so such an extension would require a new additive quantity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the approximation of polytopes by polytopes of bounded "depth" in a model where depth is measured by the number of alternating layers of Minkowski sums and convex hulls of unions. The main result, Theorem 5, gives an exact formula for the minimum empty-corner distance from the n-dimensional simplex to any depth-d polytope for 0<d<ceil(log2(n+1)), namely n+1-2^d. This implies that simplices cannot be approximated by polytopes of insufficient depth. A secondary result, Theorem 8, characterizes simplices as the only "outer additive" convex bodies. The proofs use support functions, barycentric coordinates, and additivity properties of empty-corner sizes under Minkowski sums.

Significance. The main theorem is a sharp, parameter-free inapproximability result with a clean and surprising formula. It strengthens Valerdi's depth-complexity lower bound for simplices and transfers to a lower bound on the expected L1 deviation of support functions, which is relevant to the expressivity of rectified linear unit networks. The proof is elementary and self-contained, and the key additivity lemma (Claim 15) is a nice observation. The characterization of simplices as the only outer additive convex bodies is also attractive and independent of the main line. The paper is clearly written and the central claims are well supported.

minor comments (5)
  1. [Section 4.2, proof of Theorem 3] The equality Ev(L;H)=min{Ev(L1;H), Ev(L2;H)} is stated without proof; the subsequent argument only uses the trivial inequality direction, so the equality should either be proven or, if not needed, removed to avoid confusion.
  2. [Section 2.2, Claim 12] The step "It follows that F is a supporting hyperplane of K" needs justification; the fact that conv(Bu∪{x}) lies on ∂K implies that the affine hull of that set, and hence any hyperplane containing it, is a supporting hyperplane of K, but this should be spelled out for the reader.
  3. [Section 4.2, proof of Theorem 5] The reduction for point terms (when Kj or Lj lies in Pn,0) does not explicitly address the case when both Kj and Lj are singletons; a sentence explaining that such terms can be dropped because translations do not affect the empty-corner distance would complete the induction argument.
  4. [Section 5.2, proof of Lemma 16] The phrase "By translation if needed, we can assume without loss of generality that H' = k∆o(L)" is correct but may confuse readers because H' and ∆o(L) are not necessarily concentric; a brief remark that the origin is moved to the center of the homothety mapping one to the other would help.
  5. [Title and typographical issues] The title contains a spurious space in "APPROXIMA TION"; the paper should be proofread for similar typographical errors.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 5 is derived from geometric inequalities and external theorems, not from a quantity defined as the result.

full rationale

I walked the derivation chain. The central quantity De(L) is defined directly from outer and inner homothet coefficients relative to the simplex, so no 'prediction' is renamed from a fitted input. Claim 15, the additivity step for empty-corner sizes, is stated and proved from support-function additivity and barycentric coordinates; although it is the load-bearing structural fact, it is not assumed as the target result. The lower bound in Theorem 5 is then obtained by induction using Theorems 2 and 3, with the base case De(Pn,1) = n-1 coming from Lemma 4. The cited lower bound of Valerdi [21] is mentioned only for context: Theorem 5 is strictly stronger and is proved without assuming it. The self-citations [3, 21] are motivational and do not carry the proof. The Akopyan-Karasev Kadets-type theorem is an external, machine-independent result used only in Lemma 7 and Claim 18, not to force the main conclusion. I found no fitted constants, no parameter calibrated to a subset and then called a prediction, and no definition that presupposes the theorem's conclusion. The characterization of simplices as outer additive bodies is also derived internally via Theorem 8 and does not circularly depend on the approximation results. The paper is self-contained against external benchmarks, so the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces mathematical definitions (empty-corner distance, co-distance, outer additivity) that are not physical entities and carry no hidden parameters. The main proofs use standard convex geometry facts plus one imported theorem. No free parameters are fitted to data.

assumptions (6)
  • standard math Additivity of support functions under Minkowski sums
    Used in Claim 9 and Claim 15 to show outer additivity of simplices and additivity of empty-corner sizes.
  • standard math Barycentric coordinate representation and facet-distance formula (Lemma 14)
    Provides the coordinate system used throughout Section 4 to compute empty-corner sizes.
  • standard math Caratheodory's theorem and the consequence that 0 in conv(U) yields a positive linear combination
    Used in Lemma 19 to produce the finite set of supporting half-spaces.
  • domain assumption Akopyan-Karasev Kadets-type theorem (Theorem 20)
    Imported external result used in Claim 18 to bound the sum of inner coefficients of an inductive covering.
  • domain assumption Density of smooth strictly convex bodies
    Used in Claim 18 to prove the inequality for general convex bodies by approximation.
  • domain assumption Uniqueness of the smallest enclosing simplex Delta_o(L)
    Relies on the fact that the intersection of two homothets of a simplex with nonempty intersection is a homothet; stated in the introduction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation Depth of Convex Polytopes." pith.science (2026). https://pith.science/paper/T5FUN74D

@misc{pith2026250707779,
  author       = {Pith},
  title        = {Pith review of: Approximation Depth of Convex Polytopes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T5FUN74D}},
  note         = {Machine review of arXiv:2507.07779}
}
read the original abstract

We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a given depth. Our main results imply that simplices can only be ``trivially approximated''. On the way, we obtain a characterization of simplices as the only ``outer additive'' convex bodies.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages

  1. [1]

    Arseniy Akopyan and Roman Karasev, Kadets-type theorems for partitions of a convex body , Discrete & Computational Geometry 48 (2012), 766–776. ↑5, ↑15

    work page 2012

  2. [2]

    Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee, Understanding deep neural networks with rectified linear units , International Conference on Learning Representa- tions, 2018. ↑3

    work page 2018

  3. [3]

    Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, and Amir Yehu- dayoff, On the depth of monotone ReLU neural networks and ICNNs , arXiv preprint arXiv:2505.06169 (2025). ↑1, ↑2

    arXiv 2025

  4. [4]

    2, 325–341

    K´ aroly B¨ or¨ oczky Jr,Approximation of general smooth convex bodies, Advances in Mathemat- ics 153 (2000), no. 2, 325–341. ↑1

    work page 2000

  5. [5]

    6, 906–917

    Hennie Daniels and Marina Velikova, Monotone and partially monotone neural networks , IEEE Transactions on Neural Networks 21 (2010), no. 6, 906–917. ↑2

    work page 2010

  6. [6]

    2, 91–100

    William J Firey and Branko Gr¨ unbaum, Addition and decomposition of convex polytopes , Israel Journal of Mathematics 2 (1964), no. 2, 91–100. ↑1

    work page 1964

  7. [7]

    Peter M Gruber, Approximation of convex bodies , Convexity and its Applications, Springer, 1983, pp. 131–162. ↑1

    work page 1983

  8. [8]

    Grunbaum, Convex polytopes, Springer-Verlag, New York, 2003

    B. Grunbaum, Convex polytopes, Springer-Verlag, New York, 2003. ↑1, ↑2

    work page 2003

Show all 22 references
  1. [9]

    ↑1 18 BAKAEV, BRUNCK, AND YEHUDAYOFF

    Christian Haase, Christoph Hertrich, and Georg Loho, Lower bounds on the depth of integral ReLU neural networks via lattice polytopes , arXiv:2302.12553 (2023). ↑1 18 BAKAEV, BRUNCK, AND YEHUDAYOFF

    2023 arXiv

  2. [10]

    Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella, Towards lower bounds on the depth of ReLU neural networks , Advances in Neural Information Processing Systems 34 (2021), 3336–3348. ↑1

    2021

  3. [11]

    Michael Kallay, Indecomposable polytopes, Israel Journal of Mathematics 41 (1982), 235–243. ↑1

    1982

  4. [12]

    Daniel A Klain, Containment and inscribed simplices , Indiana University Mathematics Jour- nal (2010), 1231–1244. ↑14

    2010

  5. [13]

    Dan Mikulincer and Daniel Reichman, Size and depth of monotone neural networks: Inter- polation and approximation , IEEE Transactions on Neural Networks and Learning Systems (2024). ↑2

    2024

  6. [14]

    28, Princeton university press, 1997

    R Tyrrell Rockafellar, Convex analysis , vol. 28, Princeton university press, 1997. ↑9

    1997

  7. [15]

    151, Cambridge university press, 2013

    Rolf Schneider, Convex bodies: the Brunn–Minkowski theory , vol. 151, Cambridge university press, 2013. ↑2

    2013

  8. [16]

    G. C. Shephard, Approximation problems for convex polyhedra, Mathematika 11 (1964), no. 1, 9–18. ↑1

    1964

  9. [17]

    Shephard, Decomposable convex polyhedra, Mathematika 10 (1963), no

    Geoffrey C. Shephard, Decomposable convex polyhedra, Mathematika 10 (1963), no. 2, 89–95. ↑1, ↑3

    1963

  10. [18]

    Joseph Sill, Monotonic networks , Advances in neural information processing systems 10 (1997). ↑2

    1997

  11. [19]

    Aishwarya Sivaraman, Golnoosh Farnadi, Todd Millstein, and Guy Van den Broeck, Counterexample-guided learning of monotonic neural networks , Advances in Neural Infor- mation Processing Systems 33 (2020), 11936–11948. ↑2

    2020

  12. [20]

    1, 287–295

    Gabor Toth, Asymmetry of convex sets with isolated extreme points, Proceedings of the Amer- ican Mathematical Society 137 (2009), no. 1, 287–295. ↑4

    2009

  13. [21]

    Valerdi, On minimal depth in neural networks , arXiv:2402.15315 (2024)

    Juan L. Valerdi, On minimal depth in neural networks , arXiv:2402.15315 (2024). ↑1, ↑2, ↑5

    2024

  14. [22]

    12, 4425–4431

    Shuning Wang and Xusheng Sun, Generalization of hinging hyperplanes , IEEE Transactions on Information Theory 51 (2005), no. 12, 4425–4431. ↑3 Department of Computer Science, the University of Copenhagen Department of Computer Science, the University of Copenhagen Department o...

    2005

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.