Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (123): sum-over-paths formula for a ReLU network

Proved
LesHouchesWidth.output_eq_sum_over_paths

by LG · Sep 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

machine-learningneural-networksprobability

For every configuration of weights, every input x∈Rn0x\in\mathbb R^{n_0}x∈Rn0​ and every output neuron qqq,

zq(L+1)(x)=∑p=1n0xp∑γ∈Γp,q(∏ℓ=1L+1Wγ(ℓ)γ(ℓ−1)(ℓ))(∏ℓ=1Lξγ;x(ℓ)),ξγ;x(ℓ)=1{zγ(ℓ)(ℓ)(x)>0},z^{(L+1)}_q(x)=\sum_{p=1}^{n_0}x_p\sum_{\gamma\in\Gamma_{p,q}}\Big(\prod_{\ell=1}^{L+1}W^{(\ell)}_{\gamma(\ell)\gamma(\ell-1)}\Big)\Big(\prod_{\ell=1}^{L}\xi^{(\ell)}_{\gamma;x}\Big),\qquad \xi^{(\ell)}_{\gamma;x}=\mathbf 1\{z^{(\ell)}_{\gamma(\ell)}(x)>0\},zq(L+1)​(x)=p=1∑n0​​xp​γ∈Γp,q​∑​(ℓ=1∏L+1​Wγ(ℓ)γ(ℓ−1)(ℓ)​)(ℓ=1∏L​ξγ;x(ℓ)​),ξγ;x(ℓ)​=1{zγ(ℓ)(ℓ)​(x)>0},

where Γp,q\Gamma_{p,q}Γp,q​ is the set of paths γ=(γ(0),…,γ(L+1))\gamma=(\gamma(0),\dots,\gamma(L+1))γ=(γ(0),…,γ(L+1)) through the network with γ(0)=p\gamma(0)=pγ(0)=p and γ(L+1)=q\gamma(L+1)=qγ(L+1)=q.

This identity expresses a ReLU network with zero biases as a polynomial in its weights whose coefficients are the activation indicators. All the moment computations of Lecture 5 start from it.

Formalization Note The statement is deterministic, with no probability involved. The notes index weights along a path as Wγ(ℓ−1)γ(ℓ)(ℓ)W^{(\ell)}_{\gamma(\ell-1)\gamma(\ell)}Wγ(ℓ−1)γ(ℓ)(ℓ)​; here the row/column orientation of the network recursion is used.

Preamble
import Mathlib
import Definitions.Def_LesHouchesWidth_ReLUNet
Formal statement
namespace LesHouchesWidth

open MeasureTheory ProbabilityTheory

theorem output_eq_sum_over_paths {n : ℕ → ℕ} {L : ℕ} (ω : Weights n L)
    (x : Fin (n 0) → ℝ) (q : Fin (n (L + 1))) :
    output ω x q =
      ∑ p : Fin (n 0), x p *
        ∑ γ ∈ pathsFromTo n L p q, pathWeight ω γ * pathActivation ω x γ := by sorry

end LesHouchesWidth
Source
Bahri, Hanin, Brossollet, Erba, Keup, Pacelli, Simon, *Les Houches Lectures on Deep Learning at Large & Infinite Width*, arXiv:2309.01592v3 (https://arxiv.org/abs/2309.01592), p. 40, eq. (123) (Section 5.3, Definition 2 and the exercise following it).
Read-back

What the Lean code literally says, in plain math · Aristotle (Harmonic) - non-blind, same agent as drafter

Non-blind read-back. This read-back was written by the same agent (Aristotle, by Harmonic) that drafted the Lean statement, with full knowledge of the source and of the intended meaning. It is not independent testimony and should not be treated as a blind audit; an independent read-back is still recommended before launch.

Let n:N→Nn:\mathbb N\to\mathbb Nn:N→N be any width sequence and L∈NL\in\mathbb NL∈N any depth (L=0L=0L=0 is allowed). Let ω\omegaω be any real weight configuration (no probability is involved), let x∈Rn0x\in\mathbb R^{n_0}x∈Rn0​ be any input, and let q<nL+1q<n_{L+1}q<nL+1​. The theorem asserts the exact identity

zq(L+1)(x)=∑p<n0xp∑γ∈Γp,q(∏ℓ=0Lwℓ(γ(ℓ+1),γ(ℓ)))(∏ℓ=0L−11{zγ(ℓ+1)(ℓ+1)(x)>0}).z^{(L+1)}_q(x)=\sum_{p<n_0}x_p\sum_{\gamma\in\Gamma_{p,q}}\Big(\prod_{\ell=0}^{L}w_\ell\big(\gamma(\ell+1),\gamma(\ell)\big)\Big)\Big(\prod_{\ell=0}^{L-1}\mathbf 1\{z^{(\ell+1)}_{\gamma(\ell+1)}(x)>0\}\Big).zq(L+1)​(x)=p<n0​∑​xp​γ∈Γp,q​∑​(ℓ=0∏L​wℓ​(γ(ℓ+1),γ(ℓ)))(ℓ=0∏L−1​1{zγ(ℓ+1)(ℓ+1)​(x)>0}).

Here z(⋅)z^{(\cdot)}z(⋅) is the zero-bias ReLU recursion z(1)=w0xz^{(1)}=w_0xz(1)=w0​x, z(ℓ+1)=wℓmax⁡(z(ℓ),0)z^{(\ell+1)}=w_\ell\max(z^{(\ell)},0)z(ℓ+1)=wℓ​max(z(ℓ),0). The weight is wℓ(i,j)=2/nℓ ωℓ,i,jw_\ell(i,j)=\sqrt{2/n_\ell}\,\omega_{\ell,i,j}wℓ​(i,j)=2/nℓ​​ωℓ,i,j​, and Γp,q\Gamma_{p,q}Γp,q​ is the set of all index sequences γ(0),…,γ(L+1)\gamma(0),\dots,\gamma(L+1)γ(0),…,γ(L+1) with γ(ℓ)<nℓ\gamma(\ell)<n_\ellγ(ℓ)<nℓ​, γ(0)=p\gamma(0)=pγ(0)=p, γ(L+1)=q\gamma(L+1)=qγ(L+1)=q. There are no hypotheses. If some width is 000, both sides are empty sums equal to 000. The indicator uses the strict inequality >0>0>0, so a neuron whose preactivation is exactly 000 contributes 000.

Human review
  • Endorsed by Shuze Chen · Sep 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Sep 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me