Naculich 2020: Regge colour basis of the four-gluon amplitude and the all-loop coefficient B_ℓℓResearch Paper
Motivation
At high energies (s≫−t, the Regge limit) scattering amplitudes of gauge theories simplify and organise into towers of logarithms log∣s/t∣. For the four-gluon amplitude of N=4 super-Yang–Mills theory with gauge group SU(N), the colour structure is what makes the nonplanar (subleading in 1/N) amplitude hard to control. Naculich (2020) builds a basis of colour factors Cik adapted to the Regge limit at every loop order, writes the ℓ-loop amplitude in that basis, and uses one of its coefficients, Bℓℓ(ℓ), to motivate a conjectured all-loop relation with the Regge limit of the N=8 supergravity four-graviton amplitude. The physics conjecture itself is not a mathematical statement; what is exact and checkable is the colour algebra underlying it — finite-dimensional linear algebra over polynomials in N.
Setting
Trace basis. Four-gluon colour factors are expanded in six single and double traces c[1],…,c[6] of fundamental generators (eq. (2.1)). A colour vector is a column v=(v1,…,v6) of polynomials in N, with complex coefficients.
Colour operators. The t-channel Casimir Tt2 and the crossing-odd combination Ts−u2=21(Ts2−Tu2) act on colour vectors as the explicit 6×6 matrices of eq. (4.15) (entries in Z[21][N]). The tree-level t-channel colour factor is C00=c[1]−c[3]. Crossing (exchange of legs 2 and 3) is the permutation P: c[1]↔c[3], c[4]↔c[6].
each with exactly i operators. The admissible pairs are (0,0), (1,1), (2,1),(2,2) and (i,1),(i,i−1),(i,i) for i≥3.
Extended trace basis. At ℓ loops, tλ+6k(ℓ)=Nℓ−2kc[λ] for λ=1,2,3 and Nℓ−2k−1c[λ] for λ=4,5,6, giving 3ℓ+3 elements (eq. (2.3)). The colour-ordered amplitudesAλ(ℓ) of an amplitude are its coordinates in this basis (eq. (2.4)).
Regge-basis amplitude. Eq. (4.24):
A(ℓ)=A1(0)a~ℓi=0∑ℓk∑Bik(ℓ)Nℓ−iCik.
Null vectors. Four vectors per loop order ℓ≥2 (eqs. (2.10), (2.12), extended by prepending zeros) encode the SU(N) group-theory relations among the Aλ(ℓ).
Formalization targets
Goal: the all-loop coefficient Bℓℓ(ℓ) (eqs. (4.26)–(4.27))
For every even ℓ,
A1(0)a~ℓBℓℓ(ℓ)=2⋅3ℓ/21(A3ℓ+1(ℓ)−A3ℓ+3(ℓ)),
and for ℓ=1, A1(0)a~B11(1)=−(A1(1)+A3(1)). The paper obtains the even-ℓ formula by guessing from explicit results through ℓ=9; a proof for all ℓ is not given there.
The Regge colour factors satisfy the four null-vector constraints and have no t2(ℓ) component, for all ℓ≥2.
The Regge colour factors are linearly independent, and for ℓ≥2 span all constrained Regge-limit amplitudes (the "basis" claim of Sec. 4).
Significance
The result. Eq. (4.26) is the input to the paper's analysis of the infrared behaviour of Bℓℓ(ℓ) (at most 1/ϵℓ, manifest for even ℓ because only most-subleading-colour amplitudes appear), and hence to the conjectured all-orders relation between Bℓℓ(ℓ) and the Regge limit of N=8 supergravity (Sec. 6). An all-ℓ proof replaces an extrapolation from nine loop orders by a theorem.
Formalizing it. The low-loop tables (4.16), (4.20), (4.18), (4.22) are finite computations; the goal and milestones 3, 4, 7, 8 are statements for every loop order and need genuine arguments (induction on ℓ, structure of the operators on the extended basis).
Difficulty
The coefficient Bℓℓ(ℓ) is defined through the whole (3ℓ−2)-element basis: a formula for it must vanish on every other Nℓ−iCik, including the nested commutators Ci1 and Ci,i−1 whose components grow in complexity with i. Checking the formula loop order by loop order does not give a proof; one needs to control how Tt2 and Ts−u2 act on the two most-subleading slots of the extended basis uniformly in ℓ.
Formalization scope
Colour vectors are Fin 6 → ℂ[X], with N the polynomial variable X; operators are Matrix (Fin 6) (Fin 6) ℂ[X] acting by Matrix.mulVec. Coefficients Bik and the prefactor κ=A1(0)a~ℓ are arbitrary complex numbers; B is a function ℕ × ℕ → ℂ of which only the admissible pairs matter.
Extended-basis indices λ are 1-based natural numbers, 1≤λ≤3ℓ+3; the coordinate function returns 0 outside this range. The colour-ordered amplitudes are defined as the coordinates of κ∑BikNℓ−iCik, so the goal says: whatever the coefficients, the stated combination of coordinates returns κBℓℓ. This is equivalent to the paper's reading for amplitudes lying in the span of the Regge basis (milestone 8).
The odd-ℓ formula (4.28) for ℓ>1 is not included. It agrees with the model at ℓ=3 (it is the B33 line of eq. (4.22)), but an exploratory exact-rational computation (not machine-checked) found that at ℓ=5 no linear combination of the six amplitudes A3ℓ−8,A3ℓ−6,A3ℓ−5,A3ℓ−3,A3ℓ−2,A3ℓ reproduces B55(5) in this model. Including it would risk a false milestone.
Local checks of the statements used Lean v4.28.0 with Mathlib; only standard Mathlib API (polynomials, matrices, LinearIndependent, finite sums) is used.
Welcome contributions: lemmas describing Tt2 and Ts−u2 as operators on extended-basis coordinates (shift of N-degree), and general tools for iterated commutators.
Selected references
S. G. Naculich, All-loop-orders relation between Regge limits of N=4 SYM and N=8 supergravity four-point amplitudes, arXiv:2012.00030 (2020), https://arxiv.org/abs/2012.00030.
Gubser-Klebanov-Polyakov 1998: dimensions of operators dual to massive string statesResearch Paper
Motivation
In 1997 Maldacena conjectured that N=4 super-Yang–Mills theory with gauge group U(N) is equivalent to type IIB string theory on AdS5×S5 (hep-th/9711200). The paper of Gubser, Klebanov and Polyakov (hep-th/9802109), together with Witten's paper of the same year (hep-th/9802150), turned the conjecture into a computational rule: the generating functional of connected gauge theory correlators equals the minimum of the supergravity action subject to boundary conditions at the edge of anti-de Sitter space. The concrete outputs of the paper are two-point functions and operator dimensions, read off from the small-momentum, non-analytic behaviour of solutions of a radial ordinary differential equation.
The mathematical core is classical analysis of modified Bessel functions: which solution is regular in the throat, how Kν splits into I±ν, and what the leading non-analytic term of a logarithmic derivative is as the momentum tends to zero. The physical headline, Eq. (46), is that operators dual to massive string states at level n acquire dimensions growing like 2(ngYM2N)1/2 at large 't Hooft coupling.
Setting
Let R>0 be the AdS radius and z>0 the radial coordinate, with the boundary at z=R and the horizon at z=∞. For a bulk field ϕ(x,z)=eik⋅xf~k(z) with Euclidean momentum k>0, the radial equation is
(Dk,μf)(z)=z3∂z(z−3∂zf)−k2f−z2μf=0,
with μ=0 for the massless s-wave (Eq. (20)), μ=l(l+4) for the l-th partial wave (Eq. (34)), and μ=(mR)2 for a scalar string state of mass m (Eq. (40)).
The modified Bessel functions are defined for x>0 and real ν by
The normalised radial profile is f~k(z)=z2Kν(kz)/(R2Kν(kR)), the flux factor is F(k)=[z−3∂zlogf~k(z)]z=R, and the two-point function is ⟨O(k)O(q)⟩=(2π)4δ4(k+q)16π2N2F(k) (Eq. (26)). For a level-n string state m2=4n/α′, R4=2NgYM2α′2, the Bessel order is ν=4+(mR)2 (Eq. (41)) and the dimension of the dual operator is Δ=2+ν (Eq. (45)).
Formalization targets
Goal (Eqs. (41)–(46))
For n≥1, N,gYM,α′,m,R>0 with m2=4n/α′, R4=2NgYM2α′2 and ν=4+(mR)2∈/Z: there is a function A real-analytic at 0 with
Δ=2+ν=2+4+4ngYM2N, and Δ/(2(ng2N)1/2)→1 as g→∞.
Milestones
Solutions of the radial equation (Eqs. (22), (35), (39)–(41)), regularity selecting Kν (text after (23)), the connection formula Kν=2sinπνπ(I−ν−Iν) (Eq. (42)), the flux factor for integer order (Eqs. (36)–(37)) and non-integer order (Eqs. (43)–(44)), the relation (mR)2=4ngYM2N (Eq. (41)) and the asymptotics (45)–(46).
Significance
The computation is the prototype of the AdS/CFT dictionary between bulk masses and boundary dimensions, Δ(Δ−4)=(mR)2 in five bulk dimensions. The massless case reproduces the non-renormalisation of dimensions of operators dual to supergravity fields; the massive case is the first prediction that unprotected operators acquire dimensions growing without bound at strong coupling.
The mathematical statements are classical, but their formalisation needs modified Bessel functions of real order, their connection formula, and asymptotic expansions near 0 with logarithmic terms — material not currently present in Mathlib as far as the drafter checked. None of the statements below has a machine-checked proof yet.
Corrections to the source. Numerical exploration by the drafter (not machine-checked) indicates that the sign of the logarithmic coefficient printed in Eqs. (36)–(37) is reversed (the standard expansion has (−1)n+1log(x/2)In(x) in Kn(x)), and that Eq. (27) is inconsistent with Eq. (37) at l=0: the correct leading term for l=0 is −41k4log(kR)=−81k4log(k2R2). The partial-wave milestone is stated with the corrected coefficient. Eq. (44) (non-integer order), which carries the paper's main prediction, agrees with the standard expansions.
Difficulty
The flux factor is a logarithmic derivative of Kν evaluated at the boundary. The leading term of Kν near 0 is a pure power, which contributes only an analytic part; the physical information sits in a subleading term of relative size k2ν (or k2l+4logk for integer order). Extracting it requires the full series structure of Kν near 0, not only its leading asymptotics, together with control of the remainder uniformly enough to pass through a logarithm and a derivative.
Formalization scope
All functions are real-valued; Kν is defined by its integral representation and Iν by its power series, both used only for x>0. The convention 1/Γ(pole)=0 is realised by Lean's 1/0=0. "An analytic function of k2 plus a term plus o(⋅)" is encoded as: there exists A with AnalyticAt ℝ A 0 such that the difference is little-o of the given power as k→0+. Because 2ν is not an even integer when ν∈/Z (and because of the logarithm in the integer case), the coefficient of the leading non-analytic term is uniquely determined, so the statements are not vacuous. The physics steps (the identification of generating functionals, Eq. (12), and the Fourier transform to position space) are not formalised: the two-point function is defined through the flux factor, Eq. (26). Welcome contributions: general facts about Kν and Iν (differential equation, positivity, asymptotics, series near 0), reusable beyond this mission.
Selected references
S.S. Gubser, I.R. Klebanov, A.M. Polyakov, Gauge theory correlators from non-critical string theory, Phys. Lett. B 428 (1998) 105–114. https://arxiv.org/abs/hep-th/9802109
J. Maldacena, The large N limit of superconformal field theories and supergravity, Adv. Theor. Math. Phys. 2 (1998) 231. https://arxiv.org/abs/hep-th/9711200
Witten 1998: Anti de Sitter Space and Holography — the massive scalar boundary-value problemResearch Paper
Motivation
In February 1998 Witten's paper Anti de Sitter Space and Holography made precise Maldacena's proposal that large-N conformal field theories in d dimensions are described by gravity on (d+1)-dimensional anti de Sitter spaceAdSd+1. The dictionary it proposes identifies boundary values of bulk fields with sources of boundary operators, and reads correlation functions off the dependence of the bulk action on those boundary values. Its most quoted quantitative consequence is the mass–dimension relation: a scalar of mass m on AdSd+1 corresponds to a boundary operator of conformal dimension
Δ=21(d+d2+4m2),Δ(Δ−d)=m2.
Behind this physics statement sits a piece of classical analysis on hyperbolic space: the Dirichlet-type problem for the operator Δg−m2 with prescribed boundary asymptotics, solved by an explicit Poisson-type integral (Section 2 of the paper, eqs. (2.15)–(2.44)). This mission formalizes that analytic core.
Timeline. Maldacena 1997 (hep-th/9711200) conjectured the correspondence; Gubser–Klebanov–Polyakov (hep-th/9802109) and Witten (hep-th/9802150, both February 1998) proposed the precise dictionary; the Euclidean black-hole thermodynamics used in Section 3 goes back to Hawking–Page 1983.
Setting
Euclidean AdSd+1 is modelled as the upper half space{(x0,x):x0>0,x∈Rd} with the hyperbolic metric
A massive scalar of squared mass m2∈R solves Δgu=m2u (eqs. (2.34), (2.37)). The conformal dimension is Δ=21(d+d2+4m2) (eq. (2.44)), the bulk-to-boundary kernel is
and the Poisson-type integral of a boundary datum φ0 is ∫RdKΔ(x0,x−x′)φ0(x′)dx′ (eqs. (2.20), (2.41)).
Formalization targets
Goal (eq. (2.41) with (2.43)–(2.44))
For m2>−d2/4 there is a constant c>0 such that for every bounded continuous φ0 on Rd,
φ(x0,x)=c∫Rd(x02+∣x−x′∣2)Δx0Δφ0(x′)dx′
is a C2 solution of Δgφ=m2φ on the upper half space and x0Δ−dφ(x0,x)→φ0(x) as x0→0+, i.e. φ∼x0d−Δφ0 at the boundary (eq. (2.36) with f=x0).
Milestones
x0Δ solves the massive equation when Δ(Δ−d)=m2 (eqs. (2.16)–(2.17), (2.37)).
The inverted kernel KΔ solves it too (eqs. (2.18)–(2.19), (2.38)).
Scaling: ∫x02Δ−d(x02+∣x∣2)−Δdx is independent of x0 (eq. (2.40)).
Approximate identity: these kernels tend to a multiple of δ(x) (eq. (2.39)).
The massless case Δ=d with φ→φ0 (eq. (2.20)).
Δ=21(d+d2+4m2) is the larger root of Δ(Δ−d)=m2 (eqs. (2.43)–(2.44)).
The gauge-field profile x0d−2 solves the reduced Maxwell equation (eqs. (2.24)–(2.25)).
Hawking–Page, d=3: β(r+)=12πr+/(1+3r+2) has a maximum and I(r+)=πr+2(1−r+2)/(1+3r+2) is negative for large r+ (eqs. (3.15)–(3.16)).
Significance
The goal is the analytic statement underlying the mass–dimension relation Δ(Δ−d)=m2 of the AdS/CFT dictionary: it shows that the boundary datum φ0 of a massive field is naturally a density of weight d−Δ, which is how the paper identifies the dimension of the dual operator. The same kernel is the starting point for the two-point function (2.42). The result is classical mathematics (scattering theory on hyperbolic space), proved informally in the paper; this mission produces a machine-checked version together with reusable infrastructure for the hyperbolic Laplacian in half-space coordinates.
Difficulty
The pointwise identities (milestones 1, 2, 6, 7, 8) are calculus. The substance is analytic: differentiating the Poisson-type integral twice under the integral sign with only boundedness of φ0, and proving the approximate-identity limit with the right normalisation; the scaling integral requires Δ>d/2, and the endpoint m2=−d2/4 (where Δ=d/2 and the kernel is not integrable) must be excluded.
Formalization scope
Points are pairs (x0,x)∈R×EuclideanSpaceR(Find); partial derivatives are one-variable derivs, so the solution predicate also demands C2 regularity on {x0>0}, which rules out junk values of deriv. Real powers are Real.rpow; integrals are Bochner integrals for Lebesgue measure. Boundary data are bounded continuous functions. All declarations live in the namespace WittenAdSHolography, with the shared definitions in one definition file.
J. Maldacena, The Large N Limit of Superconformal Field Theories and Supergravity, Adv. Theor. Math. Phys. 2 (1998) 231–252. https://arxiv.org/abs/hep-th/9711200
S. S. Gubser, I. R. Klebanov, A. M. Polyakov, Gauge Theory Correlators from Non-Critical String Theory, Phys. Lett. B 428 (1998) 105–114. https://arxiv.org/abs/hep-th/9802109
S. W. Hawking, D. N. Page, Thermodynamics of Black Holes in Anti-de Sitter Space, Commun. Math. Phys. 87 (1983) 577–588. https://doi.org/10.1007/BF01208266
Coupling Constant II: The Beta Function in the Energy Scale and the Running DichotomyTextbook
Motivation
A coupling constant is the number that fixes the strength of an interaction: in the
modern formulation it is the parameter weighting the interaction part of a Lagrangian
against its kinetic part. In a quantum field theory such a parameter is not constant.
Probing a process at a higher energy resolves more of the virtual activity that dresses
the interaction, and the value one measures depends on the energy scale μ at which
the measurement is made. This scale dependence is called the running of the coupling,
and it is the organising phenomenon behind two of the best-known qualitative facts about
the Standard Model: the electromagnetic coupling grows with energy (α≈1/137
at low energy, α≈1/127 at the Z mass, about 90 GeV) and apparently
diverges at a finite energy — the Landau pole — while the strong coupling decreases
logarithmically at high energy, the asymptotic freedom found by Gross, Politzer and
Wilczek and recognised by the 2004 Nobel Prize.
The source treats the running through the beta function, defined there by
β(g)=μ∂μ∂g=∂lnμ∂g,
and through the one-loop strong coupling
αs(k2)≈β0ln(k2/Λ2)1.
Everything in this mission is the mathematics of those two formulas: an autonomous scalar
ordinary differential equation in the logarithm of the energy, and the behaviour of its
solutions according to the sign of the one-loop coefficient.
Setting
Write μ>0 for the energy scale of a process and g, or α, for a real-valued
coupling as a function of that scale. The beta function in the energy scale is the
logarithmic derivative used by the source,
β(g)(μ)=μ⋅dμdg(μ),
a function of μ built from g; a theory whose beta function vanishes identically is
scale-invariant, since its coupling then takes the same value at every scale.
A coupling is said to be one-loop running with coefficient b on a set S of scales
when it satisfies, at every μ∈S,
μdμdα(μ)=bα(μ)2,
equivalently dα/dμ=bα2/μ. Here b<0 is the asymptotically free sign
(QCD) and b>0 the sign the source attributes to QED. The equation is the one-loop
truncation written in μ rather than in t=lnμ: both forms appear in the source,
and the first milestone is precisely their agreement.
The one-loop strong coupling with one-loop coefficient β0>0 and QCD scaleΛ>0 is the explicit function
α(Q)=β0ln(Q2/Λ2)1,Q>Λ,
the formula the source quotes for αs(k2). It is defined by an existing platform
definition, which this mission reuses rather than restates.
Formalization targets
Goal — the running dichotomy in the energy scale
For every reference scale μ0>0 and every positive reference value α0 of the
coupling at that scale:
b<0:α(μ)=1−bα0ln(μ/μ0)α0(μ≥μ0),α(μ)μ→∞0;b>0:no coupling obeys μdμdα=bα2 on all of [μ0,μ0e1/(bα0)] with α(μ0)=α0.
The negative-coefficient half is asymptotic freedom together with the uniqueness of the
solution; the positive-coefficient half is the Landau pole, stated as the non-existence of
any solution up to the pole scale rather than as a divergence of one chosen formula. The
pole scale μ0e1/(bα0) is the one the one-loop equation itself predicts.
Supporting levels
The milestones below range from the definitional identity
μ∂μg=∂lnμg, through the three qualitative readings of the
sign of β that the source states in words (vanishing beta function means scale
invariance; positive beta function means the coupling grows with energy; negative means it
falls), to the identification of the quoted QCD formula as an exact solution of the
one-loop equation and the determination of Λ from a single measured value.
Significance
The dichotomy is the mathematical content of two physical statements that the source
presents side by side. Asymptotic freedom is what makes perturbative QCD predictive at high
energy; the Landau pole is the reason the source warns that the perturbative beta function
cannot be trusted at strong coupling, since the one-loop equation has no solution reaching
the pole scale at all. Formalizing the uniqueness half also pins down what "the" running
coupling means: the explicit formula is not merely one solution of the renormalization-group
equation but the only one through a given data point.
An earlier public mission on the same source
("Coupling Constant: One-Loop Running, Asymptotic Freedom and the Landau Pole") formalized
the one-loop flow in the logarithmic variable t=lnμ with a cubic beta function
β(g)=bg3, and its statements are proved. This mission is stated in the other
variable the source uses — the energy scale μ itself, with the quadratic one-loop
equation for α — and adds the parts of the source that the earlier mission does not
cover: the defining identity between the two forms of the beta function, the sign-to-monotonicity
statements for an arbitrary (not necessarily one-loop) coupling, the explicit pole scale, and
the determination of the QCD scale Λ from a measurement. Where the earlier mission
already settles a statement in the quoted formula's variables, this proposal references the
published theorem instead of restating it.
Difficulty
The equation is elementary, and the difficulty is entirely in what the statements quantify
over. The negative-coefficient half asserts that every function satisfying the equation on
[μ0,∞) is the explicit one, so it needs a uniqueness argument for a nonlinear
scalar ordinary differential equation rather than a verification that a formula works; the
substitution u=1/α that makes the equation linear is legitimate only while α
is known not to vanish, which is part of what has to be proved. The positive-coefficient half
is a non-existence statement on a closed interval reaching the pole, so no local solution can
be extended to it; the naive attempt — differentiate the explicit formula and observe that it
blows up — proves nothing about the other candidate solutions.
Formalization scope
Couplings are total functions R→R, and every statement restricts to
the scales it is about: the positive half-line for the beta-function statements, (Λ,∞)
for the explicit QCD formula, [μ0,∞) or a closed interval for the one-loop flow.
Outside those ranges nothing is claimed — in particular at Q≤Λ, where the logarithm
in the quoted formula vanishes or is negative and the reciprocal returns a junk value.
Differentiability is a hypothesis where it is needed, written as a two-sided derivative at each
scale of the set, so that a statement cannot be satisfied by a one-sided artefact at an endpoint.
The one-loop property is phrased as an exact differential equation, never as an asymptotic
approximation, and the Landau-pole milestone is a non-existence claim rather than a divergence
claim, so it cannot be discharged by exhibiting a formula with a singularity.
A complete development needs the mean value theorem, Gronwall- or uniqueness-type arguments for
scalar ordinary differential equations, and the standard logarithm and exponential API; the
uniqueness lemma for u˙=bu2 and the reciprocal substitution are reusable beyond this
mission. Contributions of a general scalar-ODE uniqueness lemma, usable by both this mission
and the earlier one, are especially welcome.
A. Deur, S. J. Brodsky, G. F. de Téramond, The QCD running coupling, Progress in Particle and Nuclear Physics 90 (2016) 1-74. https://arxiv.org/abs/1604.08082
ATLAS Collaboration, A precise determination of the strong-coupling constant from the recoil of Z bosons with the ATLAS experiment at s=8 TeV, 2023. https://arxiv.org/abs/2309.12986
P. A. Zyla et al. (Particle Data Group), Review of Particle Physics - Chapter 9, Quantum Chromodynamics, PTEP 2020 (8). https://doi.org/10.1093/ptep/ptaa104
Polyakov Action: Symmetries and Classical Equivalence with Nambu–GotoTextbook
Motivation
The Polyakov action is the standard action for the worldsheet of a bosonic string. It was introduced by Deser and Zumino and independently by Brink, Di Vecchia and Howe in 1976, and is associated with Polyakov after he used it to quantize the string in 1981. Its value over the Nambu–Goto (area) action is that it is quadratic in the embedding fields, which makes quantization tractable, while being classically equivalent to the area action. This mission formalizes the classical facts collected in the Wikipedia article Polyakov action.
Setting
A string sweeps out a two-dimensional worldsheet with coordinates σ=(τ,σ). Its embedding in a D-dimensional target is Xμ(σ); the target carries a metric gμν(X), and the worldsheet carries an independent (auxiliary) metric hab(σ) with inverse hab and determinant h. With the induced metric Gab=gμν(X)∂aXμ∂bXν and string tension T, the Polyakov and Nambu–Goto actions are
SP=2T∫d2σ−hhabGab,SNG=T∫d2σ−detGab.
The stress–energy tensor is Tab=T(Gab−21habhcdGcd). Signature convention: timelike +, spacelike −.
Formalization targets
Goal: on-shell equivalence with Nambu–Goto
If the auxiliary metric satisfies its equation of motion Tab=0 (with hcdGcd≥0), then
SP=SNG.
Milestones
Poincaré invariance of the target: translations X→X+b (exact) and infinitesimal Lorentz transformations X→X+εωX (to O(ε2)), for a constant target metric.
Worldsheet diffeomorphism invariance and Weyl invariance h→Λh.
Tracelessness of the stress–energy tensor, Taa=0.
The variations δ−h=−21−hhabδhab and δS/δhab=2T−h(Gab−21habhcdGcd).
On shell, detG=41h(hcdGcd)2.
Conformal gauge: S=2T∫(X˙2−X′2), the constraints X˙⋅X′=0, X˙2+X′2=0, the wave equation □Xμ=0, and its light-cone solution X=X+(τ+σ)+X−(τ−σ).
Significance
These are the classical foundations of bosonic string theory: the symmetries (Poincaré, diffeomorphism, Weyl) are what make the conformal gauge reachable, and the equivalence with Nambu–Goto justifies using the quadratic action. All statements are textbook results; the work here is to formalize them with explicit hypotheses (differentiability, integrability, positivity of hcdGcd) that the physics presentation leaves implicit.
Difficulty
The algebraic statements are 2×2 matrix identities. The diffeomorphism invariance needs the change-of-variables formula; the infinitesimal Lorentz statement needs care with integrability; the wave-equation milestone needs the fundamental lemma of the calculus of variations; and the light-cone solution is d'Alembert's theorem.
Formalization scope
Worldsheet =R2 (coordinates Fin 2 → ℝ, index 0=τ), target =RD. Actions are Bochner integrals over a region U⊆R2. The inverse metric is Mathlib's matrix inverse. Quantization, Virasoro operators, the Liouville action and string boundary conditions are out of scope.
Selected references
Wikipedia, Polyakov action, revision 1292212311.
S. Deser, B. Zumino, A complete action for the spinning string, Phys. Lett. B 65 (1976) 369–373.
L. Brink, P. Di Vecchia, P. Howe, A locally supersymmetric and reparametrization invariant action for the spinning string, Phys. Lett. B 65 (1976) 471–474.
A. M. Polyakov, Quantum geometry of bosonic strings, Phys. Lett. B 103 (1981) 207–210.
Drezet 2023: GHZ Bell-Nonlocality in the Everett MultiverseResearch Paper
Motivation
Whether the many-worlds (Everett) interpretation of quantum mechanics is local in the sense of Bell is a recurring question in the foundations of physics. A number of authors have argued that Everett's theory escapes Bell-type nonlocality theorems because it drops the assumption that each measurement has a single outcome. A. Drezet's paper arXiv:2306.07794 (2023) argues against this claim by revisiting the Greenberger–Horne–Zeilinger (GHZ) nonlocality theorem, which, unlike Bell's inequality, uses only probability-one (perfect) correlations. Its central mathematical step, stated in Section II, is that no locally causal beable model can reproduce the quantum predictions for the GHZ state. The paper's argument is that this step makes no assumption about completeness or hidden variables, and so applies to Everett's theory as well.
Timeline:
1964–1976: J. S. Bell introduces Bell inequalities and, in "The theory of local beables" (1976), the notion of local causality phrased with beables λ (collected in Speakable and Unspeakable in Quantum Mechanics, 2004).
1989: Greenberger, Horne and Zeilinger give a nonlocality proof for three spin-½ particles that uses no inequality ("Going beyond Bell's theorem").
2015: L. Vaidman discusses the GHZ argument in the many-worlds setting ("Bell inequality and Many-Worlds interpretation").
2023: Drezet's paper, the source of this mission.
Setting
Three spin-½ particles are sent to three distant observers, Alice, Bob and Charlie. Each one measures the spin of their particle along a direction n^j∈{x^,y^} and records an outcome α,β,γ∈{+1,−1}. The particles are prepared in the GHZ state
∣ψ⟩=21(∣+z⟩1∣+z⟩2∣+z⟩3−∣−z⟩1∣−z⟩2∣−z⟩3),
and quantum mechanics predicts the joint outcome probabilities through the Born rule, P(α,β,γ∣n^1,n^2,n^3,ψ)=∣⟨αn^1,βn^2,γn^3∣ψ⟩∣2. Here ∣an^⟩ denotes the eigenvector of σn^ with eigenvalue a. In Lean this is bornProb n₁ n₂ n₃ α β γ.
A locally causal (Bell-local) model consists of
a space Λ of beables with a probability distribution ρ(λ) that does not depend on the settings (Eq. (18), statistical independence), and
local response probabilities Pj(α∣λ,n^j), where party j's outcome depends only on λ and its own setting (Eq. (17)).
In Lean the model is a LocalCausalModel Λ and its prediction is M.predict. The beables are arbitrary: λ may be a hidden variable, or the quantum state itself as in the Beltrametti–Bugajski representation, Eq. (15).
Formalization targets
Goal (Section II, Eqs. (10)–(27))
No locally causal model reproduces the quantum predictions on the four GHZ settings (x^,x^,x^), (x^,y^,y^), (y^,x^,y^), (y^,y^,x^):
Eqs. (2)–(5).σx(1)σx(2)σx(3)∣ψ⟩=−∣ψ⟩, and the three σxσyσy-type operators fix ∣ψ⟩.
Born probabilities (Section III, Eqs. (30)–(32)). For (x^,x^,x^) each outcome triple has probability 1/4 if αβγ=−1 and 0 otherwise. For the other three GHZ settings the same holds with αβγ=+1.
Eqs. (10)–(13). No assignment Aj,Bj∈{±1} satisfies all four GHZ constraints.
Eqs. (19)–(27). If a product of three probability distributions on {±1} vanishes off the set {αβγ=s}, then each factor is a point mass, and the three atoms multiply to s.
Section II, summary (ii). A locally causal model that reproduces the GHZ predictions is, for ρ-almost every λ, deterministic, with values satisfying (10)–(13).
Section III (B). Local causality implies non-signalling.
Eq. (29). Quantum non-signalling for the GHZ state, with Alice's marginal P1(±1∣x^,ψ)=21.
Appendix 3, Eqs. (39)–(45). Keeping Eq. (17) but letting the beable density depend on the settings (a "superdeterministic" model) does reproduce the GHZ predictions.
Significance
The goal theorem is the mathematical core of the paper's conclusion that any beable account of the GHZ correlations, including one where λ is just the quantum state, violates Bell's local causality. Milestones 6–8 formalize the paper's separation of notions of locality: non-signalling holds both in quantum mechanics and in every locally causal model, so it cannot tell them apart; and dropping statistical independence (Eq. (18)) is enough to reproduce the correlations. The GHZ theorem itself has been known since 1989. As far as the drafter is aware it has no machine-checked formalization on this platform, and this mission provides one, stated for general measurable beable spaces.
Difficulty
The combinatorial core (milestone 3) is a parity argument. The substance lies in the steps that connect it to probability: showing that perfect correlations force determinism almost surely when ρ is an arbitrary probability measure (null sets, measurability, integrals of nonnegative functions), and computing the Born probabilities exactly in Lean from explicit matrices and eigenvectors.
Formalization scope
Outcomes are elements of ℤˣ (exactly {+1,−1}). Settings form a two-element type Setting with values x and y. Qubit index 0 is ∣+z⟩ and index 1 is ∣−z⟩. Three-qubit operators are Kronecker products.
A LocalCausalModel Λ has a probability measure ρ on a measurable space Λ and measurable response functions P j λ n α with values in [0,1] that sum to one over α. The fixed state ψ is left implicit. Predictions are Bochner integrals, and all integrands are bounded and measurable.
The goal quantifies over all such models on all measurable spaces. Its hypothesis is the equality of all 4×8 predicted and Born probabilities. Because it uses the actual Born probabilities rather than an arbitrary list of constraints, it cannot hold vacuously.
Needed infrastructure: finite-dimensional matrix computations over C with 2, and basic measure theory (a.e. vanishing of nonnegative integrands).
Selected references
A. Drezet, An Elementary Proof That Everett's Quantum Multiverse Is Nonlocal: Bell-Locality and Branch-Symmetry in the Many-Worlds Interpretation, arXiv:2306.07794, 2023. https://arxiv.org/abs/2306.07794
D. M. Greenberger, M. A. Horne, A. Zeilinger, Going beyond Bell's theorem, in Bell's Theorem, Quantum Theory and Conceptions of the Universe, Kluwer, 1989, pp. 69–72. https://arxiv.org/abs/0712.0921
Verlinde 2016: Apparent Dark Matter and the Baryonic Tully-Fisher RelationResearch Paper
Motivation
In emergent gravity proposals, spacetime and gravity are macroscopic descriptions of an underlying quantum system. In Verlinde (2016) it is argued that in de Sitter space (a universe with positive dark energy) the entanglement entropy has, besides the usual area-law part, a thermal volume-law part, and that matter displaces this volume-law entropy. The elastic response of the medium to this displacement produces an extra gravitational pull, which the paper proposes as the origin of the effects usually ascribed to dark matter in galaxies and clusters.
The physical derivation is heuristic, but it ends in explicit mathematical relations between the baryonic (visible) mass profile MB(r) and the apparent dark matter mass profile MD(r) of a spherically symmetric, isolated system. The central one is the integral relation (7.40),
∫0rr′2GMD(r′)2dr′=6MB(r)a0r,
where G is Newton's constant and a0=cH0 is the Hubble acceleration scale. For a point mass it reproduces Milgrom's empirical acceleration relation and the baryonic Tully-Fisher relationvf4=aMGMB with aM=a0/6.
Setting
All quantities are real numbers or real functions of the radius r>0. G>0 and a0>0 are constants. MB(r) and MD(r) are the baryonic and apparent dark masses inside radius r. The Newtonian accelerations are gB(r)=GMB(r)/r2 and gD(r)=GMD(r)/r2 (7.42). The averaged density inside radius r is ρˉ(r)=3M(r)/(4πr3) (7.45), and the slope parameter is β(r)=−dlogρˉ/dlogr=−rρˉ′(r)/ρˉ(r) (7.46). A local density ρ gives M(r)=∫0rρ(r′)4πr′2dr′ (7.39).
The paper also uses two purely mathematical facts about elastic strain in d−1 spatial dimensions: a bound (7.30) on the largest principal strain of a traceless symmetric strain tensor, and the integration-by-parts identity (7.31) between the squared Hessian and the squared Laplacian.
Formalization targets
Goal: Milgrom relation for a central point mass (7.43)
If MB>0 is constant and (7.40) holds for every r>0, then for every r>0
gD(r)=aMgB(r),aM=6a0.
Milestones
(4.44) the strain-squared integral outside a spherical inclusion: ∫c∞(c/V)2dV=c.
(7.30) ε2≤d−1d−2∑ijεij′2 for a traceless symmetric ε′ with eigenvalue ε.
(7.31) ∫(∇i∇jχ)2dV=∫(∇2χ)2dV.
(7.47) ρˉD(r)2=(4−βB(r))8πGra0ρˉB(r) for a general baryonic profile.
(7.48) ρD(r)=(1−31βD(r))ρˉD(r).
(7.51) ΩD2=34ΩB when (7.47) is applied at the Hubble radius with βB=0.
Significance
The point-mass relation (7.43) is what connects the paper to the observed flat rotation curves and the baryonic Tully-Fisher law; (7.47) is its extension to extended mass profiles, which the paper uses to discuss galaxy clusters. The formal content checked here is the mathematics that turns the stated relation (7.40) into these observable consequences, plus the two elasticity lemmas used on the way to (7.40). The physical steps that lead to (7.40) (the entropy-displacement picture, the elastic interpretation, the identification (7.35)) are not mathematical statements and are outside the scope of this mission. None of these relations is known to have been machine-checked before.
Difficulty
The algebra is short once one may differentiate; the work is in the analysis. (7.40) is an integral identity with a singular weight 1/r′2 at the origin, so recovering pointwise information requires the fundamental theorem of calculus on (0,∞) with only continuity there, and care with integrability at 0. (7.31) is a double integration by parts in Rn that must be justified for the chosen decay class. (7.30) needs the spectral theorem for symmetric matrices, or an equivalent argument.
Formalization scope
All statements live in the namespace Verlinde2016. Radial profiles are functions R→R, with hypotheses only on (0,∞). The integral in (7.40) is Lean's interval integral over [0,r]; since it would be 0 for a non-integrable integrand, the positivity of the right-hand side forces integrability. Continuity of MD (and of densities) on (0,∞) is taken as a standing physical convention. In (7.31) the paper's condition that "χ falls off rapidly enough" is formalized as χ smooth with compact support. Spatial dimension is d−1 in (7.30); (7.40)–(7.51) use d=4 as in Section 7.2. Definitions: avgDensity, slopeParam, partialDeriv.
M. Milgrom, A modification of the Newtonian dynamics as a possible alternative to the hidden mass hypothesis, Astrophys. J. 270 (1983) 365. https://doi.org/10.1086/161130
Liouville Field Theory I: Spectrum and Kinematic SymmetriesTextbook
Motivation
Liouville field theory is a two-dimensional conformal field theory whose classical equation of motion generalizes Liouville's equation. It is one of the few interacting conformal field theories with a continuous spectrum that has been solved: its three-point function on the sphere is given by the DOZZ formula (Dorn–Otto 1994; Zamolodchikov–Zamolodchikov 1996), proved rigorously from a probabilistic construction of the path integral by Kupiainen–Rhodes–Vargas (2017), with the conformal bootstrap established by Guillarmou–Kupiainen–Rhodes–Vargas (2020). It appears in two-dimensional quantum gravity, non-critical string theory, and log-correlated random energy models.
This mission is the first in a series following the Wikipedia article on Liouville field theory. It formalizes the kinematic layer of the theory: the algebraic relations between the coupling constant, the background charge, the central charge, the conformal dimensions and the reflection coefficient, on which every later statement (the spectrum, the DOZZ formula, the bootstrap) is phrased.
Setting
Fix a complex number b, the coupling constant. Define
the background chargeQ=b+b1;
the central chargec=1+6Q2;
the conformal dimension of the primary field with momentumα∈C, Δ(α)=α(Q−α);
the reflection coefficient with normalization parameter λ,
RP=±λ−2iPΓ(−2ibP)Γ(−2ib−1P)Γ(2ibP)Γ(2ib−1P),
with sign +1 if c∈(−∞,1) and −1 otherwise.
Two symmetries act on these data: the reflectionα→Q−α and the dualityb→1/b. The spectrum of the theory is the set of dimensions Δ∈24c−1+R+, parametrized by momenta α=2Q+iP, P∈R+.
Formalization targets
Goal: the spectrum parametrization
For every b∈C, the map P↦Δ(2Q+iP) is a bijection
[0,∞)∼24c−1+[0,∞)⊂C.
Milestones
Reflection invariance: Δ(Q−α)=Δ(α).
Duality: c and Δ are invariant under b→1/b.
Marginality: for b=0, b(Q−b)=1⟺Q=b+1/b.
Dimension in terms of momentum: Δ(2Q+iP)=24c−1+P2.
Imaginary coupling: real nonzero β=ib produce exactly the real central charges c≤1.
Reflection relation consistency: RPR−P=1 for λ=0 and 2ibP,2ib−1P∈/Z.
Significance
These identities are the dictionary between the parameters used in the physics literature (b, Q, c, α, P, Δ) and fix the conventions for later missions in the series: the DOZZ formula, the pole structure of correlation functions, and the reflection and duality covariance of structure constants are all stated in these variables. None of these statements is open; the value of the mission is a vetted, reusable definition layer with machine-checked consistency of the conventions.
Difficulty
The individual statements are elementary algebra over C, together with the non-vanishing of the Gamma function away from its poles. The care needed is in conventions: total functions in Lean (0−1=0, principal-branch complex powers, Gamma at its poles) must be handled by explicit hypotheses exactly where the source implicitly excludes degenerate values.
Formalization scope
All quantities are complex-valued functions of b∈C, defined in the namespace LiouvilleFieldTheory. 1/b is Lean's inverse (so b=0 gives junk values Q=0, c=1; statements that need b=0 assume it). R+ is taken to be [0,∞). The condition c∈(−∞,1) is encoded as Imc=0∧Rec<1. λ−2iP is the principal-branch complex power. The analytic content of the article (Virasoro representations, conformal blocks, the special function Υb, the path integral, the DOZZ formula) is out of scope for this mission.
Computational Optimal Transport XII: The Entropic Barycenter Scalings Are (e^{f_s/ε}, e^{g_s/ε}) for the Solutions of a Dual Program with Σ_s λ_s f_s = 0Textbook
Why barycenters of histograms matter
A barycenter summarizes several objects by minimizing a weighted sum of distances to them. For probability histograms, ordinary coordinatewise averages depend strongly on how the bins are labeled. Optimal transport instead lets mass move between bins and charges for those moves through a cost matrix. The resulting Wasserstein barycenter can reflect the geometry of the bins: nearby bins can exchange mass at a lower cost than distant ones. Peyré and Cuturi use this construction in their treatment of variational transport problems, including shape interpolation and the representation of a measure as a barycenter of other measures. The finite histogram problem in this mission is the entropically regularized version developed in §9.2 of their textbook.
The computational question is how to connect three ways of describing the same solution: a histogram that is the barycenter, transport matrices coupling it to the inputs, and vectors of dual potentials. Proposition 9.1 on p. 530 identifies the dual potentials behind the scaling factors of the optimal transport matrices. This is the second proposition numbered 9.1 in the chapter; the one on p. 519 concerns derivatives with respect to histograms.
Finite histogram setting
There are S input histograms. Source s has ns bins and a probability vector bs, while the barycenter has n bins. The real matrix Cs∈Rn×ns gives the cost of transporting a unit of mass from barycenter bin i to input bin j. A weight vector λ∈ΣS has nonnegative entries summing to one; Σk denotes the probability simplex on k bins. The unregularized barycenter problem (9.10) minimizes ∑sλsLCs(a,bs) over a∈Σn, where LCs is the minimum transport cost with marginals a and bs.
For a regularization parameter ε>0, the entropic transport costLCsε(a,bs) minimizes ⟨Cs,Ps⟩−εH(Ps) over nonnegative coupling matrices Ps with row marginal a and column marginal bs. Here ⟨Cs,Ps⟩=∑i,jCs,ijPs,ij and H(Ps)=∑i,j(−Ps,ijlogPs,ij+Ps,ij), with 0log0=0. The Gibbs kernel is Ks,ij=e−Cs,ij/ε.
The book also writes the regularized barycenter as a weighted KL projection. Its variables are the matrices (Ps)s; each matrix has column marginal bs, and every matrix has the same row marginal. That shared row marginal is a, so the optimization can be expressed without carrying a as a separate variable. The generalized matrix divergence is KL(Ps∣Ks)=∑i,j[Ps,ijlog(Ps,ij/Ks,ij)−Ps,ij+Ks,ij], using the continuous value at Ps,ij=0. See (9.15)–(9.17) in Peyré and Cuturi.
Formalization targets
The goal is Proposition 9.1 on p. 530. The dual variables are row potentials fs∈Rn and column potentials gs∈Rns. They maximize
The theorem asserts that the primal and dual optima are attained, that every optimal primal family and every optimal dual family satisfy
Ps,ij=efs,i/εKs,ijegs,j/ε,
and that the dual maximum is the minimum value of the entropic barycenter objective (9.15). The milestone targets are the scalar and matrix versions of the KL conjugate (9.22), followed by the closed form maximizer of one gs block, corresponding to the update (9.18). These statements retain the source's finite matrix setting and are listed in the order in which their concepts enter the dual formulation.
What the result supplies
The scaling formula turns the optimal couplings into a product of a row factor, a fixed positive kernel, and a column factor. It identifies those factors with exponentials of dual potentials and gives a constrained maximization problem whose value is the entropic barycenter cost. Thus a solver can reason about the couplings, the barycenter marginal, or the potentials while referring to one theorem that connects them. The book uses the same variables to describe the iterative scaling updates on pp. 529–531 and later illustrates barycenters of shapes and surface measures; those applications depend on interpreting the matrix factors correctly. Peyré and Cuturi give the mathematical proposition and its argument. A complete Lean proof of the proposition and its supporting KL identities is the work this mission calls for; the statements here are draft targets rather than machine-checked solutions.
Where the difficulty lies
The potential program is a constrained optimization problem, while the transport problem constrains nonnegative matrices by two kinds of marginals. Equality of their optimum values must preserve the normalization constants in generalized KL. The exponential form alone does not establish that a proposed matrix has the required marginals, nor does a feasible matrix alone identify dual potentials. In addition, the assertion concerns every optimizer: a choice of zero source weight would leave that source's coupling unconstrained by the objective, and a zero target entry would put a logarithmic column update on the boundary. These are substantive edge cases of the formulas, not merely notation.
Formalization scope
Lean uses Fin S, Fin n, and Fin (n_s) for the finite index sets; these are zero based versions of the book's one based indices. Histograms and potentials are real vectors, costs and couplings are real matrices, and the Gibbs kernel is defined entrywise. The theorem requires S,n,ns>0, ε>0, strictly positive weights λs that sum to one, and strictly positive input histograms bs that each sum to one. The strict positivity of weights and input entries is an explicit restriction beyond (9.15)–(9.21), needed for a statement about every optimizer and finite logarithmic potentials. Entropy uses 0log0=0 on nonnegative couplings. The shared row marginal is constructed by the constraints on the Ps; it is not a free histogram unrelated to them.
The definition layer includes finite matrix pairing, entropy, generalized KL, the Gibbs kernel, feasibility, and primal and dual objective functions. The KL conjugate identities and the block optimizer are separate theorem targets so they can be reused in other entropic transport developments. The main theorem asserts primal and dual attainment as well as their relationship; it does not assume strong duality or an optimal scaling as an input. The page has slips in the dimensions of the marginal equations and a missing subscript on K in (9.17); the Lean statements use the dimensions specified by Ps∈Rn×ns. The optional cost-gradient Proposition 9.2 on pp. 519–520 and the fs block update (9.19)–(9.20) lie outside this proposal.
Selected references
Gabriel Peyré and Marco Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5–6):355–607, 2019. DOI: 10.1561/2200000073.
Computational Optimal Transport IX: The Entropic Cost L^ε_C(a, b) Equals max ⟨f, a⟩ + ⟨g, b⟩ − ε⟨e^{f/ε}, K e^{g/ε}⟩, with Optimal Scalings (e^{f/ε}, e^{g/ε})Textbook
Motivation
Optimal transport compares two distributions by finding the least expensive way to move mass between them. For finite histograms, the resulting linear program is precise but its optimal coupling can be sparse. In applications where the coupling represents traffic, matching, or a differentiable loss, a sparse plan may be undesirable or expensive to compute repeatedly. Peyré and Cuturi describe how adding an entropy term selects a diffuse coupling and leads to matrix scaling algorithms that can be used on large finite problems (Peyré and Cuturi, 2019, Chapter 4).
The entropic dual gives a second view of the same regularized problem. Its variables are real vectors attached to the two marginal constraints. Unlike the ordinary Kantorovich dual, the objective has no explicit feasibility constraints and is smooth. This permits calculations in the log domain, which the book introduces because direct scaling with exponentials can suffer from numerical overflow or underflow when the regularization parameter is small relative to the costs (Peyré and Cuturi, 2019, §4.4). This mission targets the exact relationship between the regularized minimum, the smooth dual maximum, and the scaling factors.
Setting
Fix positive integers n,m. A histograma∈Σn is a vector with nonnegative entries summing to one; b∈Σm is defined similarly. Strict positivity is required for the attained dual maximum and log-domain updates; the primal scaling and Kantorovich-feasibility statements also cover zero-entry histograms. A couplingP∈U(a,b) is an n×m matrix with nonnegative entries, row sums a, and column sums b. A real matrix C assigns cost Cij to each transfer from row i to column j, and ⟨C,P⟩=∑i,jCijPij is its transport cost.
The book uses the entropyH(P)=−∑i,jPij(logPij−1), with 0log0=0. For ε>0, the regularized cost is LCε(a,b)=minP∈U(a,b){⟨C,P⟩−εH(P)}. The Gibbs kernel has entries Kij=exp(−Cij/ε). Given potentials f∈Rn and g∈Rm, the smooth dual objective is Q(f,g)=⟨f,a⟩+⟨g,b⟩−ε∑i,jefi/εKijegj/ε. These are the finite-dimensional objects of (4.1), (4.2), and (4.30) in the source (Peyré and Cuturi, 2019, pp. 425, 428, 448).
Formalization targets
Attained entropic duality
The goal is Proposition 4.4. There are an optimal coupling P and potentials (f,g) at which the dual reaches its maximum, with the common value
LCε(a,b)=⟨C,P⟩−εH(P)=f′,g′maxQ(f′,g′).
For every maximizing pair (f′,g′), the same optimal coupling satisfies
Pij=efi′/εKijegj′/ε.
Thus the dual potentials determine the scaling vectors u=ef′/ε and v=eg′/ε in (4.12). The maximum is an attained maximum of a real function, as stated in the book, rather than an unrestricted real infimum or supremum that might take a default value on a bad input (Peyré and Cuturi, 2019, Proposition 4.4).
Supporting results
The milestones follow the source's statements. Proposition 4.3 gives existence, uniqueness, and the Gibbs scaling of the primal optimizer. Remark 4.21 gives the two partial-gradient formulas and the closed log-domain block updates. Proposition 4.5 states that an entropic dual maximizer is a feasible pair of ordinary Kantorovich potentials, so its linear objective is bounded above by the unregularized cost LC(a,b) (Peyré and Cuturi, 2019, pp. 432, 449, 452–453).
Significance
The equality establishes that the matrix scaling variables and the dual potentials describe the same optimal coupling. It lets a computation based on scaling be interpreted as maximizing a smooth objective, and it gives exact marginal-error expressions through the dual gradients. Feasible Kantorovich potentials obtained at the optimum also provide a lower bound on the ordinary transport cost. These statements explain why log-domain updates represent the same mathematical problem as entropic transport, even when direct exponentiation is numerically fragile (Peyré and Cuturi, 2019, §§4.4–4.5).
The results are established in the textbook; the open work here is their Lean formalization. A completed development would provide reusable finite coupling, entropy, Gibbs-kernel, and smooth-dual interfaces, together with the existence and differentiability results needed to connect them. It would also distinguish a primal optimum, a dual maximum, and a feasible potential without relying on informal convention. The mission does not assert that these textbook results are new, and no machine-checked proof of these exact statements is claimed here.
Difficulty
The unconstrained dual objective has a symmetry: shifting every coordinate of f by one constant and every coordinate of g by its negative leaves the value unchanged. Consequently, the set of maximizers is not bounded in the ordinary product space. Positivity of the marginals matters for attaining a maximum with finite real potentials; if a marginal entry is zero, the corresponding potential can escape toward negative infinity. On the primal side, the entropy formula must be valid at zero entries even though optimality links it to strictly positive exponential scalings. The formal argument must connect these boundary conventions and the finite-dimensional optimization statements without turning the maximum into a junk real supremum (Peyré and Cuturi, 2019, Proposition 4.4 and Remark 4.21).
Formalization scope
The Lean development represents indices by Fin n and Fin m, matrices by Matrix (Fin n) (Fin m) ℝ, and histograms by Mathlib's stdSimplex. Positive dimensions and ε>0 appear throughout. Strictly positive marginal entries are required for the attained dual maximum and log-domain updates; the other statements permit zero entries. The book assumes positive weights for discrete measures in Remark 2.1; the marginal positivity is also required for the attained dual maximum and the logarithmic updates. The cost matrix itself may have arbitrary real entries. Entropy uses Real.negMulLog, which implements 0log0=0 on the nonnegative couplings where it is applied.
The primal optimum is a predicate on a coupling and its objective, rather than a chosen matrix. The unregularized LC is a real infimum used only when simplex marginals make its feasible set nonempty and bounded. The dual objective is a finite sum. Its gradients are stated as one-variable derivatives in each coordinate, and each block update is characterized as the unique maximizer with the other block fixed. The complete development needs Mathlib's finite sums, real exponential and logarithm, calculus, finite-dimensional topology, and optimization facts. Contributions that establish these shared interfaces or the four milestone statements are in scope.
Propositions 4.7 and 4.8 are excluded from this proposal because their printed bounds compare a dual linear objective with LCε where the accompanying arguments instead support a comparison with the unregularized LC; (4.47) also has a sign discrepancy. The milestone list therefore avoids encoding a false inequality (Peyré and Cuturi, 2019, pp. 453–454).
Selected references
Gabriel Peyré and Marco Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5–6), 2019, pp. 355–607. DOI: 10.1561/2200000073.
Generalising the Scattered Property of Subspaces 2: If h + 1 Divides r and n ≥ h + 1, Maximum h-Scattered 𝔽_q-Subspaces of V(r, qⁿ) of Dimension rn/(h + 1) ExistResearch Paper
Motivation
A scattered subspace is an Fq-subspace U of an Fqn-vector space V that meets every one-dimensional Fqn-subspace of V in an Fq-subspace of dimension at most one. Scattered subspaces produce scattered linear sets in projective spaces over finite fields, and through them two-intersection sets, two-weight codes, translation caps and maximum rank distance (MRD) codes. Blokhuis and Lavrauw (Geom. Dedicata 2000) proved that a scattered subspace of V(r,qn) has dimension at most rn/2, and constructions of that dimension are known whenever rn is even (see Bartoli, Giulietti, Marino, Polverino 2018 and the references there).
Csajbók, Marino, Polverino and Zullo (arXiv:1906.10590v2, Combinatorica 41, 2021) replace "one-dimensional" by "h-dimensional". The resulting h-scattered subspaces interpolate between scattered subspaces (h=1) and subspaces meeting every hyperplane in small dimension (h=r−1), which Sheekey and Van de Voorde (Des. Codes Cryptogr. 2020) showed to be equivalent to MRD codes with an idealiser isomorphic to Fqn. For the new notion the paper proves an upper bound on the dimension (Theorem 2.3) and shows that the bound is attained when h+1 divides r (Theorem 2.6). This mission is the attainment half.
Setting
Let Fq⊆Fqn be finite fields, so n=[Fqn:Fq], and let V=V(r,qn) be an r-dimensional Fqn-vector space with r≥1. Every Fqn-space is also an Fq-space of dimension rn. For an integer h with 0<h≤r−1, an Fq-subspace U≤V is h-scattered (Definition 1.1) if
U spans V over Fqn, ⟨U⟩Fqn=V, and
dimFq(S∩U)≤h for every h-dimensional Fqn-subspace S of V.
An h-scattered subspace of largest possible Fq-dimension is maximum h-scattered. Theorem 2.3 of the paper says that an h-scattered U either has dimension r and defines a subgeometry (an Fq-basis of U is an Fqn-basis of V), or satisfies
dimFqU≤h+1rn.(1)
Two building blocks appear in the statements. If V=V1⊕⋯⊕Vt with Vi=V(ri,qn) and Ui≤Vi are Fq-subspaces, then U=U1⊕⋯⊕Ut is the direct sum of the Ui. For r≤n the Gabidulin-type subspace of Fqnr is
Gr={(x,xq,xq2,…,xqr−1):x∈Fqn},
the image of an Fq-linear map, since x↦xqj fixes Fq.
Formalization targets
Goal: Theorem 2.6 (p. 7)
If h≥1, h+1 divides r and n≥h+1, then V(r,qn) contains an Fq-subspace U that is maximum h-scattered and satisfies
dimFqU=h+1rn.
Milestones, in the order the paper uses them
Proposition 2.1 (p. 3): for h>1, every h-scattered subspace is i-scattered for all 0<i<h.
Theorem 2.3 (p. 4): the dichotomy above, subgeometry or bound (1).
Theorem 2.4 (p. 6): if Ui is hi-scattered in Vi, then U1⊕⋯⊕Ut is minihi-scattered in V1⊕⋯⊕Vt.
Theorem 2.4, second sentence (p. 6): if every Ui is h-scattered with dimFqUi=rin/(h+1), then the direct sum is h-scattered of dimension rn/(h+1).
Example 2.5 (p. 7): for 2≤r≤n, Gr is maximum (r−1)-scattered of dimension n.
Significance
Together with Theorem 2.3, the goal settles the largest dimension of an h-scattered subspace of V(r,qn) whenever h+1∣r and n≥h+1: it is exactly rn/(h+1). The subspaces it produces are the input of the paper's Delsarte duality (Theorem 3.3), which turns maximum h-scattered subspaces of V(r,qn) reaching bound (1) into maximum (n−h−2)-scattered subspaces of V(rn/(h+1)−r,qn) and so gives constructions also when h+1∤r. The direct-sum theorem is also of independent use: it extends the direct-sum construction for scattered linear sets of Bartoli, Giulietti, Marino and Polverino to every h, and Example 2.5 gives the subspace counterpart of Gabidulin codes.
All results in this mission are proved in the paper. To our knowledge none of them has a machine-checked proof; no formal library contains scattered subspaces, linear sets or Gabidulin-type subspaces. The remaining work is formalizing the paper's arguments: the counting of roots of linearized polynomials behind Example 2.5, the Grassmann-formula and quotient-space argument of Theorem 2.4, and the bound (1) of Theorem 2.3, which the companion mission on the dimension bound states as its goal.
Difficulty
The construction itself is short; the work lies in the three ingredients. The obvious approach to Theorem 2.4 fails: an h-dimensional Fqn-subspace W of V1⊕V2 need not be the sum of its intersections with V1 and V2, so the intersection W∩U cannot be bounded summand by summand. Example 2.5 needs that a nonzero q-polynomial ∑j<rajxqj has at most qr−1 roots in Fqn, and the root set is an Fq-subspace. Maximality is not a property of a single subspace: it quantifies over every h-scattered subspace of V and so needs the full upper bound of Theorem 2.3, including the case n<h+1 handled there by Proposition 2.1.
Formalization scope
Fq is a finite field F, Fqn a finite field K with Algebra F K, so q=Fintype.card F and n=Module.finrank F K. V is a finite-dimensional K-module with a compatible F-module structure (IsScalarTower F K V), and r=Module.finrank K V. An Fq-subspace is a Submodule F V; its intersection with an Fqn-subspace S is S.restrictScalars F ⊓ U.
Conventions the statements commit to:
The range 0<h<r and the spanning condition are part of IsHScattered; without the range every spanning subspace would be h-scattered for h≥r.
Every quotient rn/(h+1) is multiplied out, as (h+1)dimFqU=rn or ≤rn; no natural-number division is used.
The direct sum in Theorem 2.4 is external: V=∏i<tVi ((i : Fin t) → V i) and U=Submodule.pi Set.univ U. The minimum h=minihi is given by h≤hi for all i and h=hi for some i. The second part of Theorem 2.4 assumes t≥1.
Example 2.5 is stated on Fin r → K, with Gr the range of the F-linear map x↦(xqj)j<r, and assumes r≥2 so that (r−1)-scattered is within Definition 1.1's range.
The goal assumes r≥1: h+1 divides 0, but the zero space has no h-scattered subspace. The upper end h<r follows from h+1∣r.
"Defines a subgeometry" in Theorem 2.3 is: some subset of U spans U over Fq and is an Fqn-basis of V.
The goal is not satisfied by a small subspace: both the dimension equality (h+1)dimFqU=rn and maximality among all h-scattered subspaces of V are part of its conclusion.
Results the paper cites without a number (the Blokhuis–Lavrauw bound for h=1, the direct-sum theorem for scattered linear sets) are not items. Theorem 2.3 is restated here because the maximality in Theorem 2.6 rests on it; it duplicates the goal of the companion mission. Useful infrastructure beyond this mission: roots of linearized polynomials over finite fields, dimension formulas for subspaces under restriction of scalars, and direct sums of h-scattered subspaces. Contributions on any milestone are welcome, and the goal can be closed from the milestones alone.
D. Bartoli, M. Giulietti, G. Marino, O. Polverino, Maximum scattered linear sets and complete caps in Galois spaces, Combinatorica 38 (2018), 255–278. https://doi.org/10.1007/s00493-016-3531-6
Computational Optimal Transport VII: The Entropic Optimal Coupling P_ε Tends to the Maximum-Entropy Optimal Plan as ε → 0 and to a ⊗ b as ε → ∞Textbook
Motivation
The discrete optimal transport problem of Kantorovich asks for the cheapest way to move a probability histogram a onto a histogram b when moving a unit of mass from i to j costs Ci,j. Its optimal couplings are vertices of a polytope and are typically sparse: they rely on a few routes. Two communities have reasons to blur them. In transportation planning, observed traffic is more diffuse than linear-programming predictions, which led to the "gravity" model of Wilson (1969) and Erlander (1980), as recounted in Peyré and Cuturi, §4.1. In machine learning and statistics, adding an entropy term to the objective turns the linear program into a strictly convex problem that Sinkhorn's matrix-scaling algorithm solves at scale (Cuturi, 2013).
Every use of the entropic problem raises the same question: what does the regularized solution approximate? Chapter 4 of Peyré and Cuturi's Computational Optimal Transport answers it in Proposition 4.1 for the two extreme regimes of the regularization strength ε.
Timeline.Cominetti and San Martín (1994) studied the convergence of entropic penalties for linear programs, including first-order expansions near ε=0 and ε=+∞. Peyré and Cuturi (2019) record the transport case as Proposition 4.1, with a short compactness proof.
Setting
Fix sizes n,m≥1. A histogram is a vector of the probability simplexΣn={a∈R+n:∑iai=1}. Given a∈Σn, b∈Σm, the set of couplings is
U(a,b)={P∈R+n×m:P1m=a,P⊤1n=b},
nonnegative matrices with row sums a and column sums b. For a cost matrix C∈Rn×m write ⟨C,P⟩=∑i,jCi,jPi,j. The Kantorovich problem is LC(a,b)=minP∈U(a,b)⟨C,P⟩.
The discrete entropy of a coupling is
H(P)=−i,j∑Pi,j(logPi,j−1),
with 0log0=0. For ε>0 the entropic problem is
LCε(a,b)=P∈U(a,b)min⟨P,C⟩−εH(P),
whose unique minimizer is Pε. The maximum-entropy optimal couplingP0⋆ is the optimal coupling of the Kantorovich problem with the largest entropy. The Gibbs kernel is Ki,j=e−Ci,j/ε and the Kullback–Leibler divergence between matrices is KL(P∣K)=∑i,jPi,jlog(Pi,j/Ki,j)−Pi,j+Ki,j.
In Lean these are couplings, frob and IsOptimalCoupling in CompOT.Assignment, and entropy, entObjective, IsEntropicOptimal, IsMaxEntropyOptimal, gibbs and klMat in CompOT.EntropicLimit.
For ε>0, problem (4.2) has a unique optimal solution (§4.1, p. 425).
The maximum-entropy optimal coupling (4.3) exists and is unique (proof of Proposition 4.1, p. 426).
The sandwich (4.5): for an optimal P and ε>0, 0≤⟨C,Pε⟩−⟨C,P⟩≤ε(H(Pε)−H(P)).
a⊗b is the unique maximizer of H on U(a,b) (p. 426).
(4.7): Pε is the KL projection of the Gibbs kernel onto U(a,b) (p. 428).
Significance
The result. Proposition 4.1 justifies the entropic regularization as an approximation scheme: for small ε the regularized plan converges to an exact optimal plan, and specifically to a canonical one, the most diffuse among all optimal couplings, so the limit does not depend on any tie-breaking. The value LCε converges to the transport cost, which is what makes Sinkhorn-based estimates of transport distances meaningful. For large ε the plan becomes the independent coupling a⊗b, which explains the interpolation between optimal transport and maximum mean discrepancy studied later in the book. The KL projection identity (4.7) is the starting point of Sinkhorn's algorithm, so this mission also supplies the bridge to the next missions of the series.
Formalizing it. The proposition is a known result with a complete proof in the source; the work is formalizing it in Lean 4 with Mathlib. To our knowledge none of these statements, nor the discrete entropic transport problem itself, has a machine-checked proof in Mathlib or on the platform. A formal proof also pins down the convention for zero entries, on which the statement silently depends.
Difficulty
The obvious argument passes to the limit in the optimality of Pε, but this only shows that limit points are optimal for the Kantorovich problem; it does not identify which optimal coupling is the limit when the optimal set is a face of the polytope rather than a vertex. Identifying it requires a second-order argument at the level of the entropy, and the convergence of the whole family (not just a subsequence) rests on the uniqueness of the maximum-entropy optimal coupling, which in turn needs strict concavity of H on a set that may contain matrices with zero entries, where the logarithm is singular. Existence and uniqueness of Pε face the same boundary issue: the minimizer may a priori sit on the boundary of the polytope.
Formalization scope
Indices are 0-based (Fin n, Fin m); histograms are functions Fin n → ℝ in Mathlib's stdSimplex; matrices are Matrix (Fin n) (Fin m) ℝ with the product topology, so convergence is entrywise. Entropy uses 0log0=0 (Real.negMulLog); the book's remark that H=−∞ at a zero entry is not used, since it would contradict the continuity of H invoked in the book's proof and make (4.3) degenerate. Optimality is expressed by predicates (a minimizer over U(a,b)), never by a real infimum, so no junk value of an empty infimum appears. The limit ε→0 is taken from the right. The values LCε and LC appear as the objectives at Pε and P0⋆.
In the goal, Pε and P0⋆ are given by hypotheses (any family solving (4.2) for every ε>0, any solution of (4.3)). This is not a vacuous formalization: milestones 1 and 2 assert that such objects exist and are unique, so the hypotheses are satisfiable and determine them. Standing assumptions are exactly those of the book: a∈Σn, b∈Σm, ε>0; no positivity of a, b or C is assumed.
A complete development needs: compactness of the transport polytope, continuity and strict concavity of x↦−xlogx on [0,∞), and the Gibbs inequality on finite sums. These are reusable for the Sinkhorn and entropic-duality missions of this series. Proofs of any milestone are welcome independently.
Selected references
G. Peyré and M. Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5–6):355–607, 2019. https://doi.org/10.1561/2200000073 (§4.1, pp. 425–430)
R. Cominetti and J. San Martín, Asymptotic analysis of the exponential penalty trajectory in linear programming, Mathematical Programming 67(1–3):169–187, 1994. https://doi.org/10.1007/BF01582220
A. G. Wilson, The use of entropy maximizing models, in the theory of trip distribution, mode split and route split, Journal of Transport Economics and Policy, 108–126, 1969 (bibliography of Peyré and Cuturi). https://doi.org/10.1561/2200000073
S. Erlander, Optimal Spatial Interaction and the Gravity Model, Vol. 173, Springer-Verlag, 1980 (bibliography of Peyré and Cuturi). https://doi.org/10.1561/2200000073
Information-Theoretic Analysis of Generalization Capability of Learning Algorithms III: The Gibbs Algorithm Has Excess Risk at Most (1/β)log(1/Q(wₒ)) + β/(2n) (Corollary 2)Research Paper
Motivation
Statistical learning algorithms fit hypotheses to data that are available during training, while their performance is judged on new data. A rule that minimizes training loss can fit peculiarities of the sample, so its training loss and population loss need not agree. Xu and Raginsky study this difference through information quantities associated with the sample and the algorithm's output. Their Gibbs example shows how a probability distribution chosen before seeing the data can guide a randomized learner and yield a population-risk guarantee with explicit dependence on the sample size and the prior's mass at a good hypothesis. This mission formalizes their countable-hypothesis result, Corollary 2, and the steps of Section 4.3 and Appendix D that support it. Xu and Raginsky, 2017
Setting
Let Z be an instance space and W a hypothesis space, each with a measurable structure. A probability measure μ on Z generates a sample S=(Z1,…,Zn) of n independent observations. A lossℓ(w,z) measures the cost of hypothesis w on instance z. Its population risk is Lμ(w)=EZ∼μℓ(w,Z); its empirical risk on a realized sample s is Ls(w)=n−1∑i=1nℓ(w,zi). These definitions match equations (1)–(3) of the paper. Xu and Raginsky, 2017, p. 2
A randomized learning rule is a Markov kernelPW∣S: for each observed sample s, it gives a probability distribution for an output hypothesis W. Together with the sample law μ⊗n, it determines the joint law of (S,W). The expected generalization error is gen(μ,PW∣S)=E[Lμ(W)−LS(W)], as in equation (4). A probability distribution Q on W serves as a prior. The Gibbs rule at inverse temperature β>0 weights a hypothesis by its prior mass times e−βLs(w), then normalizes across the hypothesis space. Thus it favors low empirical risk without discarding the prior. Xu and Raginsky, 2017, pp. 2, 6
The associated optimization problem balances expected empirical risk against the conditional Kullback–Leibler divergence from the learning kernel to Q: D(PW∣S∥Q∣PS)=∫D(PW∣S=s∥Q)μ⊗n(ds). This penalty measures how much the output distribution changes from the prior after observing the sample. The paper's Theorem 5 identifies the Gibbs kernel as an optimizer of this relaxed problem. Xu and Raginsky, 2017, p. 6
Formalization targets
Gibbs optimization
For nonnegative loss, Theorem 5 asserts that the Gibbs kernel is a Markov learning rule, has the normalized exponential distribution at each sample, and minimizes the relaxed objective over learning kernels:
PW∣S=s∗(dw)=EQ[e−βLs(W)]e−βLs(w)Q(dw).
The milestone list also records the Appendix D empirical-risk comparison with a fixed hypothesis, its identity D(δw∥Q)=−logQ({w}) when the prior has positive mass at w, and the Gibbs generalization bound quoted in equation (28). Xu and Raginsky, 2017, pp. 6–7, 13
Expected population risk
The goal is Corollary 2. If W is countable, 0≤ℓ≤1, wo achieves the minimum population risk, and Q({wo})>0, then
E[Lμ(W)]≤w∈WinfLμ(w)+β1logQ({wo})1+2nβ.
The first excess term reflects the prior mass on a population-risk minimizer; the second is controlled by sample size and inverse temperature. The target keeps the infimum over the whole hypothesis space and the constants of equation (29). Xu and Raginsky, 2017, p. 7
Significance
Corollary 2 gives a quantitative way to choose a prior and temperature: a prior that puts more mass on a good hypothesis reduces the logarithmic term, while changing β changes both terms in opposite directions. It also connects the optimization characterization of a randomized algorithm to the population risk that matters for learning. Without the empirical-risk comparison and the separate generalization estimate, optimizing the training objective alone would not give this population statement. Xu and Raginsky, 2017, pp. 6–7, 13
The cited paper proves Corollary 2 and Theorem 5; the present task is to supply machine-checked proofs of their faithful Lean statements. The Donsker–Varadhan inequality and a tilted-measure identity are already published and proved on the platform, and the basic sample-law and risk definitions are already published. The Gibbs optimization, the Appendix D comparisons, and the quoted bound (28) are posed here as new targets. This work would leave reusable definitions for randomized learning kernels, their Gibbs specialization, and objectives with potentially infinite divergence.
Difficulty
The Gibbs rule is defined separately at every sample, but a learning algorithm must be a measurable kernel on the entire sample space. Establishing the normalized density pointwise does not by itself establish this kernel property. The relaxed objective also combines an integral of empirical risk with a conditional divergence, either of which can be infinite before bounded-loss assumptions are imposed. Equation (28), which the paper attributes to earlier work, needs a sharp β/(2n) constant; the looser information bound discussed immediately before it has a different dependence on β. These are separate mathematical obligations even though the final displayed inequality is short. Xu and Raginsky, 2017, pp. 6–7, 13
Formalization scope
The Lean development represents a sample as Fin n → Z, its law as Measure.pi, and a randomized learner as Kernel (Fin n → Z) W. Population and empirical risks come from the published LearnStability.Characterization.Setting definition. The Gibbs kernel is built by a normalized density over the probability prior Q; Theorem 5 explicitly asserts it is a Markov kernel. The relaxed objective takes values in R≥0∪{∞}, so an infinite KL cost is not lost through real conversion. Generalization error remains the real expectation of the population-risk minus empirical-risk difference. The stated loss bounds ensure those real expectations are meaningful in the bounded-loss results.
The paper assumes a nonnegative loss in its general setting and requires ℓ∈[0,1] for the later bounds. The Lean statements add joint measurability of ℓ and n>0 explicitly. Corollary 2 also makes the named minimizer's defining property and positive prior mass explicit: countability alone does not ensure an attained infimum, and a zero prior mass makes the printed logarithmic bound infinite. Theorem 5 retains its general measurable hypothesis space and nonnegative loss; countability appears only where the paper invokes it. Theorem 5 states optimality over all Markov kernels, the displayed Gibbs formula, and, for each sample, uniqueness of the Gibbs distribution as the minimizer of the samplewise problem (C.12) of Appendix C. The goal concerns the Gibbs kernel's actual population risk, rather than only the existence of a minimizer of the relaxed objective.
Useful contributions include probability-kernel measurability, control of conditional divergence and its finite conversions, the fixed-hypothesis comparison, and the sharp bounded-loss generalization estimate. The point-mass KL identity and the extended objective can be reused in other Gibbs and PAC-Bayesian formalizations. Xu and Raginsky, 2017, pp. 2, 6–7, 13
Selected references
A. Xu and M. Raginsky, Information-Theoretic Analysis of Generalization Capability of Learning Algorithms, Advances in Neural Information Processing Systems 30, 2017. arXiv:1705.07809v2
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization III: Every Limit Point of BSCA with Armijo Steps Is a Stationary PointResearch Paper
Motivation
Large optimization models often split their variables into blocks that can be handled separately. A method can then solve one smaller approximation problem per iteration instead of the full problem. The block successive convex approximation (BSCA) method of Razaviyayn, Hong and Luo allows the block approximation to guide the search without requiring it to be a global upper bound on the original objective. This matters when an upper bound is awkward to construct but a locally accurate convex model is available. The question is what such a run can approach: a small objective value by itself does not certify first-order optimality.
The paper develops this result after its successive upper-bound minimization methods. Theorem 4 of the pinned preprint gives the limit-point guarantee for BSCA with an Armijo step search. The mission records that result and the numbered relations (31)–(34) and (39) that organize the argument, using the 2012 preprint as the sole source for statement indices and page numbers.
Setting
The decision vector is a block vectorx=(x1,…,xN), with block xi in a nonempty, closed, convex set Xi⊆Rmi. The feasible set is X=∏i=1NXi. A continuously differentiable objective f assigns each feasible vector a real value. A point z∈X is stationary when f′(z;d)≥0 for every direction d whose full step z+d lies in X. For a smooth objective, f′(z;d) is the derivative of f in direction d.
For block i, the function hi(yi,x) approximates the objective as the trial block yi varies around a current point x. Its directional derivative at yi=xi agrees with the objective derivative in the corresponding one-block direction, as in equation (30). Each hi(⋅,x) is strictly convex on Xi, and hi varies continuously with its trial block and feasible base point. Strict convexity is a condition in the trial block for each fixed x; it does not say that hi is jointly convex in both arguments.
At iteration r, a cyclic schedule chooses one block i. A minimizer yir of hi(⋅,xr) over Xi replaces that block in yr; all other blocks of yr equal those of xr. The search direction is dr=yr−xr. With σ,β∈(0,1) and an initial trial length αinit>0, the Armijo rule chooses the largest member αr of {αinitβj:j=0,1,…} satisfying
f(xr)−f(xr+αrdr)≥−σαrf′(xr;dr),
then sets xr+1=xr+αrdr. The selected minimizer can be any one of the block minimizers; the definition does not prescribe a hidden tie-breaking rule.
Formalization targets
The first targets identify descent and line-search existence. Equation (31) says the chosen block direction has a nonpositive derivative. Equation (32) says a strict descent direction admits a trial index. The later milestones state the vanishing scaled derivative (33), a subsequence with vanishing search directions (34), and limiting block optimality following (39).
The goal is Theorem 4: for every limit point z of the sequence generated by cyclic BSCA,
z∈X,f′(z;d)≥0for every d with z+d∈X.
This is a limit-point assertion. It does not assert convergence of the entire iterate sequence, a convergence rate, or global optimality of a stationary point.
Significance
Theorem 4 identifies what an accumulation point of BSCA must satisfy even though its block models need only local first-order agreement rather than global upper bounds. In a nonconvex problem, stationarity is a meaningful first-order conclusion but need not be a global minimum. The exact role of the step search is important: accepting some Armijo step gives decrease, whereas the theorem's limit-point claim uses the largest acceptable member of the geometric trial sequence.
This mission asks solvers to supply machine-checked proofs for a known paper theorem and its stated supporting relations. The draft statements compile as open theorems; they are not proofs. The reusable output includes a block run predicate, an explicit first-order agreement predicate, and a bridge between feasible-direction stationarity and an extended-real objective on the full block space. These objects also make subsequent variants of cyclic block methods easier to state precisely.
Difficulty
A simple decrease argument shows that objective values do not increase, but the accepted step sizes may approach zero. Therefore decrease alone does not imply dr→0 or that a limit point minimizes every block model. The paper's key limit statement singles out a convergent subsequence on which a fixed block is updated and finds a further subsequence with vanishing directions. Passing block optimality to the limit then requires continuity of the approximation and feasible limit points. The cyclic schedule is needed to cover all blocks, while first-order agreement turns block optimality into stationarity for the original smooth objective.
Formalization scope
Lean uses the published TsengBCD.Stationary.X for the finite product of Euclidean block spaces, its extended-real lower directional derivative, and its stationary-point predicate. The product has the sup norm rather than the paper's Euclidean product norm; in finite dimension the notions of convergence used here agree. Blocks and iterations are indexed from zero. The paper's cyclic choice i=(rmodN)+1 is reindexed so the step from xr to xr+1 updates block rmodN. The existence of the schedule already rules out zero blocks.
The objective is a real function on the full block space, with ContDiff ℝ 1 expressing the paper's continuous differentiability. This makes the Fréchet derivative used in the Armijo test equal to the paper's lower directional derivative at the points in question. For stationarity, the objective is extended by +∞ outside X, so infeasible directions cannot silently become admissible. The approximation derivative remains extended-real because the paper assumes only convexity for that function. ContinuousOn is taken on the product of a feasible trial block and a feasible base point.
Two points are explicit in the formalization. First, 0<αinit≤1 ensures that a convex combination of xr and yr stays in X; the paper prints only positivity. Whether Theorem 4 holds without this restriction under a different global interpretation of f and hi remains a separate question. Second, Figure 4 mixes r and r−1 in the approximation, direction, and update lines. The run follows the adjacent prose and proof, all of which construct the direction at the current iterate. For (33), the existence of a limit point makes explicit the proof's standing situation and gives the decreasing objective a finite limit. An arbitrary unrelated sequence, an Armijo step that is not the largest accepted trial, or an objective extension that gives a default zero derivative off X is outside this scope.
The remaining proof work includes feasibility of every iterate, first-order agreement along the selected block, the Armijo existence statement, the subsequence claim, passage of block minimization to the limit, and the final stationary-point equivalence. The finite-dimensional convex analysis and topology involved are reusable beyond this one algorithm.
Selected references
M. Razaviyayn, M. Hong and Z.-Q. Luo, A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization, SIAM Journal on Optimization 23(2), 2013, 1126–1153. arXiv:1209.2385v1; DOI:10.1137/120891009.
P. Tseng, Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization, Journal of Optimization Theory and Applications 109(3), 2001, 475–494. DOI:10.1023/A:1017501703105.
Generalising the Scattered Property of Subspaces 1: An h-Scattered 𝔽_q-Subspace of V(r, qⁿ) Either Defines a Subgeometry or Has Dimension at Most rn/(h + 1)Research Paper
Motivation
Let V be an r-dimensional vector space over the finite field Fqn. Viewed over the subfield Fq, V has dimension rn, and its one-dimensional Fqn-subspaces form the Desarguesian spread. An Fq-subspace U of V is scattered if it meets every element of this spread in an Fq-subspace of dimension at most one. Scattered subspaces define scattered Fq-linear sets in PG(r−1,qn). Through these linear sets they are connected to projective two-weight codes, strongly regular graphs and maximum rank distance (MRD) codes. In 2000 Blokhuis and Lavrauw proved that a scattered subspace has dimension at most rn/2, and a sequence of papers showed that this bound is attained whenever 2∣rn.
Csajbók, Marino, Polverino and Zullo (arXiv:1906.10590v2; Combinatorica 41, 2021) replace the one-dimensional spread elements by all h-dimensional Fqn-subspaces. This gives a hierarchy of conditions, the h-scattered subspaces, that refines the scattered case. For h=r−1 and dimension n these subspaces had already been identified with Fqn-linear MRD codes by Sheekey and Van de Voorde. This mission formalizes the paper's main theorem, the dimension bound for h-scattered subspaces.
Timeline.
2000: Blokhuis and Lavrauw, Scattered spaces with respect to a spread in PG(n, q), prove dimFqU≤rn/2 for scattered U (the case h=1).
2000–2018: Ball–Blokhuis–Lavrauw (2000), Blokhuis–Lavrauw (2000), Csajbók–Marino–Polverino–Zullo (2017) and Bartoli–Giulietti–Marino–Polverino (2018) together show that scattered subspaces of dimension rn/2 exist whenever rn is even.
2020: Sheekey and Van de Voorde study subspaces scattered with respect to hyperplanes (h=r−1) and relate them to MRD codes.
2019–2021: Csajbók, Marino, Polverino and Zullo introduce h-scattered subspaces and prove the bound rn/(h+1) for every h (Theorem 2.3).
Setting
Let Fq⊆Fqn be finite fields, so n=dimFqFqn, and let V be a vector space over Fqn of dimension r. Every Fqn-subspace of V is also an Fq-subspace. For an Fq-subspace U of V, ⟨U⟩Fqn denotes its Fqn-span.
Definition 1.1. Let 0<h≤r−1. An Fq-subspace U of V is h-scattered if ⟨U⟩Fqn=V and every h-dimensional Fqn-subspace S of V satisfies dimFq(S∩U)≤h. In Lean this is HScattered.Bound.IsHScattered F K h U, with F=Fq, K=Fqn, and r = Module.finrank K V.
An Fq-subspace Udefines a subgeometry of PG(V,Fqn) if some Fq-basis of U is also an Fqn-basis of V (HScattered.Construction.DefinesSubgeometry F K U, a definition shared with the other missions of this series). In coordinates, U is then Fqr inside Fqnr.
A rank distance code of Fqn×m, n≤m, is a set C of Fq-linear maps from an m-dimensional to an n-dimensional Fq-space, with distance d(f,g)=rk(f−g).
Formalization targets
Goal: Theorem 2.3
If U is an h-scattered Fq-subspace of V, then either dimFqU=r, U defines a subgeometry and U is (r−1)-scattered, or
dimFqU≤h+1rn.
The disjunction is inclusive. The statement holds for every h in the range 0<h≤r−1, including h=1.
Milestones
Proposition 2.1. For h>1, an h-scattered subspace is i-scattered for every 0<i<h.
Lemma 2.2. If r≥2 and r≤i≤n, then V contains an (r−1)-scattered Fq-subspace of dimension i.
Result 4.6 (Delsarte). A rank distance code of Fqn×m, n≤m, with minimum distance d has ∣C∣≤qm(n−d+1).
Significance
The result. Theorem 2.3 is the upper end of the theory of h-scattered subspaces. It shows that the bound rn/(h+1) decreases with h: a stronger intersection condition forces a smaller subspace. Every subspace reaching the bound is a maximum h-scattered subspace. The rest of the paper builds on such subspaces. Its constructions show the bound is sharp when h+1∣r. Its intersection numbers with hyperplanes lie in [rn/(h+1)−n,rn/(h+1)−n+h]. Its Delsarte-type duality sends maximum h-scattered subspaces to maximum (n−h−2)-scattered ones. Each of these statements presupposes the bound. For h=r−1, the bound dimU≤n is the geometric counterpart of the Singleton bound for MRD codes.
Formalizing it. The theorem is proved in the paper; it has no machine-checked proof. A formalization would provide a Lean model of h-scattered subspaces over a field tower and a rank-metric Singleton bound, and the bound itself as a reusable lemma for the companion missions on constructions, hyperplane intersections and duality. The case h=1 is attributed in the paper to Blokhuis–Lavrauw and is not reproved there, so a complete formal proof must also supply that case.
Difficulty
The obvious approach is to count. Every h-dimensional Fqn-subspace meets U in at most qh vectors. But these subspaces overlap heavily, and a double count of incidences between vectors of U and h-dimensional subspaces does not produce a bound of the form rn/(h+1). The h-scattered condition must be used on subspaces of every dimension t<h at once, which is the content of Proposition 2.1. The argument for h=1 does not carry over directly either: the paper treats h=r−1, 1<h<r−1 with n≥h+1, and n<h+1 as separate cases. The case h=r−1 rests on a coding-theoretic input (Result 4.6), and the middle case needs auxiliary subspaces whose existence (Lemma 2.2) holds only when n≥h+1.
Formalization scope
Field tower.Fq and Fqn are finite fields F, K with [Algebra F K]. V is a finite-dimensional K-module with a compatible F-module structure ([IsScalarTower F K V]). The parameters are q = Fintype.card F, n = Module.finrank F K and r = Module.finrank K V.
Subspaces.Fq-subspaces are Submodule F V and Fqn-subspaces are Submodule K V. The intersection S∩U is S.restrictScalars F ⊓ U.
The definition. The range 0<h<r and the spanning condition ⟨U⟩Fqn=V are clauses of IsHScattered.
No division.rn/(h+1) never appears with division: "dimU≤rn/(h+1)" is (h+1)dimU≤rn in N.
Result 4.6. The code is a Finset of linear maps. The minimum distance d enters as a lower bound on all pairwise rank distances, with 1≤d≤n.
Lemma 2.2. It carries r≥2, which Definition 1.1 forces for (r−1)-scattered subspaces.
Ruling out trivial readings. Without the range h<r, every spanning subspace would be "h-scattered" for h≥r, and U=V of dimension rn would refute the goal. Without the spanning condition, U=0 would satisfy the bound vacuously. Both conditions are part of the definition, and the goal is the inclusive disjunction for every h-scattered U.
Cited inputs. Result 4.6 is Delsarte's theorem [13], numbered in this paper and posed here with sorry. The case h=1 of the goal is the Blokhuis–Lavrauw bound [4], which the paper cites without proof and says can be obtained by adapting its argument (Zullo's thesis [30]). It is not an item: a complete proof of the goal must cover it.
Infrastructure. A proof needs: dimension arithmetic for restriction of scalars in a tower; the rank–nullity theorem for Fq-linear maps; the count of roots of a q-polynomial ∑jajxqj, for Lemma 2.2; and a rank-metric Singleton bound. The Singleton bound and Lemma 2.2 are reusable beyond this mission. Contributions are welcome on any milestone, on the h=1 case, and on the reduction for n<h+1.
Selected references
B. Csajbók, G. Marino, O. Polverino, F. Zullo, Generalising the scattered property of subspaces, arXiv:1906.10590v2 (2020); Combinatorica 41 (2021). https://arxiv.org/abs/1906.10590v2
A. Blokhuis, M. Lavrauw, Scattered spaces with respect to a spread in PG(n, q), Geometriae Dedicata 81 (2000) 231–243. https://doi.org/10.1023/A:1005283806897
J. Sheekey, G. Van de Voorde, Rank-metric codes, linear sets, and their duality, Designs, Codes and Cryptography 88 (2020) 655–675. https://doi.org/10.1007/s10623-019-00703-z
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization II: Limit Points of Cyclic BSUM with Unique Block Minimizers Are Coordinatewise StationaryResearch Paper
Motivation
Many large optimization problems in signal processing, statistics and machine learning have a variable that splits naturally into blocks, and are solved by updating one block at a time. The classical method of this kind, block coordinate descent (BCD), minimises the objective exactly in one block while the others are held fixed. In practice the exact block subproblem is often too expensive, and one minimises instead a simpler function that upper-bounds the objective and touches it at the current point. The EM algorithm, DC (difference of convex) programming, proximal and linearised block updates and several alternating schemes for matrix factorisation and transceiver design are all of this form.
Razaviyayn, Hong and Luo (arXiv:1209.2385, SIAM J. Optim. 23 (2013)) gave one convergence analysis for this whole family, the block successive upper-bound minimization (BSUM) method, without convexity or smoothness of the objective. This mission formalizes the block part of that analysis: the cyclic BSUM method (Theorem 2) and its maximum-improvement variant MISUM (Theorem 3).
Timeline. Bertsekas (Nonlinear Programming, 1999, Prop. 2.7.1) proved that limit points of cyclic BCD are stationary for continuously differentiable objectives over a product of closed convex sets when each block minimiser is unique. Tseng (J. Optim. Theory Appl. 109, 2001) treated nondifferentiable objectives using regularity and coordinatewise minima. Chen, He, Li and Zhang (SIAM J. Optim. 22, 2012) introduced maximum block improvement, which drops the uniqueness assumption. The 2013 paper extends these results from exact block minimisation of f to minimisation of block upper bounds.
Setting
The problem is
xminf(x)s.t.x∈X=X1×⋯×Xn,(12)
where each Xi⊆Rmi is a closed convex set and f is a continuous real function on X. A point is x=(x1,…,xn) with xi∈Rmi. The directional derivative is f′(x;d)=liminfλ↓0(f(x+λd)−f(x))/λ, a value in [−∞,+∞]. A point z∈X is stationary for (12) if f′(z;d)≥0 for every d with z+d∈X. The function f is regular at z if f′(z;d)≥0 holds for every d=(d1,…,dn) such that f′(z;(0,…,dk,…,0))≥0 for every block k. A point z∈X is coordinatewise stationary if f′(z;d)≥0 for every d=(0,…,dk,…,0) with zk+dk∈Xk, for every k.
For each block i an approximation functionui(xi,y) is given, with xi∈Rmi and y∈X. Assumption 2 requires:
(B1) ui(yi,y)=f(y) for y∈X;
(B2) ui(xi,y)≥f(y1,…,yi−1,xi,yi+1,…,yn) for xi∈Xi, y∈X;
(B3) ui′(xi,y;di)xi=yi=f′(y;(0,…,di,…,0)) whenever yi+di∈Xi, the left side being the derivative in xi only;
(B4) ui is continuous in (xi,y).
The BSUM algorithm (Fig. 2) starts at x0∈X and, at each iteration, picks a block i by the cyclic rule, replaces xi by any minimiser of ui(⋅,xr−1) over Xi, and keeps the other blocks. The MISUM algorithm (Fig. 3) instead updates a block k attaining miniminxi∈Xiui(xi,xr−1).
Formalization targets
Goal: Theorem 2(a)
If each ui(xi,y) is quasi-convex in xi, Assumption 2 holds and every block subproblem minxi∈Xiui(xi,y), y∈X, has a unique solution, then every limit point z of the cyclic BSUM iterates satisfies
f′(z;d)≥0∀d=(0,…,dk,…,0),zk+dk∈Xk,k=1,…,n,
and z is a stationary point of (12) if f is regular at z.
Milestones
The proof passes through the monotonicity f(x0)≥f(x1)≥⋯ (14); the limit limrf(xr)=f(z) at a limit point z (15); the claim that xrj→z forces xrj+1→z; block minimality uk(zk,z)≤uk(xk,z) for all xk∈Xk and every k; and the first-order condition uk′(xk,z;dk)∣xk=zk≥0 for feasible dk (22).
Companions
Theorem 2(b): if the level set X0={x∈X:f(x)≤f(x0)} is compact, block minimisers are unique in at least n−1 blocks and f is regular on X0, then d(xr,X∗)→0, where X∗ is the set of stationary points. Theorem 3: under Assumption 2 alone, every limit point of the MISUM iterates is coordinatewise stationary, and stationary where f is regular.
Significance
Theorem 2 is the stationarity guarantee for every method that can be written as cyclic block minimisation of tight upper bounds: block EM, alternating DC iterations, proximal block updates, and the matrix-factorisation and beamforming schemes of Section VIII of the paper. Each such method needs only a check of (B1)–(B4) to inherit it. Theorem 3 shows that the uniqueness assumption, which part (a) needs and BCD needs too, can be traded for a greedy block choice.
The results are proved in the paper. As far as the platform's catalogue shows, none of them has been formalized; the related published work is the formalization of Tseng's 2001 setting (directional derivative, stationarity, regularity, cyclic rule), which this mission reuses. Formalizing the analysis checks the "without loss of generality" and "by further restricting to a subsequence" steps, which carry most of the argument, and gives reusable statements about limit points of block methods.
Difficulty
The obvious argument shows that f(xr) decreases and that a limit point z satisfies the block optimality condition for the block updated along the convergent subsequence. It does not say anything about the other blocks: consecutive iterates may stay a fixed distance apart, so the next iterate need not converge to z, and then nothing is known about z in the next block. Showing that xrj+1→z is the central step, and it is exactly where quasi-convexity and uniqueness of the block minimisers are used. Without uniqueness, limit points of even exact cyclic BCD need not be stationary (Powell's examples, which the paper cites), which is why Theorem 2(b) needs compactness and Theorem 3 needs a different update rule.
The step from block minimality to stationarity is a second gap: (B3) only matches derivatives in coordinate directions, and passing to all directions requires regularity of f.
Formalization scope
The space Rm1×⋯×Rmn is the dependent product X n of the referenced Tseng setting, with blocks indexed 0,…,N−1 (paper block k is index k−1). It carries the sup norm over blocks, which matters only for distances; convergence statements do not depend on the norm. The block sets are closed and convex, f is a real function continuous on X, and x0∈X; these standing hypotheses of Section IV appear in every statement.
The paper assumes domf=X. Accordingly f is extended by +∞ off X, and stationarity and regularity are those of the extension. Directional derivatives are extended-real liminfs, never real-valued limits with a junk value. A run is a predicate on a sequence: each new block is a minimiser of the block subproblem, but existence of minimisers is not assumed. The cyclic rule updates block rmodN on the step xr→xr+1, a relabelling of Fig. 2's i=(rmodn)+1. Limit points are cluster points of the sequence.
Deviations from the printed statements, each disclosed in the items:
Theorems 2(a) and 3 say "coordinatewise minimum". Their proofs establish coordinatewise stationarity and call it that, and the literal minimum claim is false (one block, X=[−1,1], f(x)=−x2, a quadratic upper bound tight at the iterate; the run stays at 0 while f(1)<f(0)). The statements assert coordinatewise stationarity.
Theorem 2(b) assumes regularity "at every point in the set of stationary points"; the proof applies it at a limit point not yet known to be stationary. The statement assumes regularity on the level set X0, as Tseng's Theorem 4.1 does.
d(xr,X∗)→0 is stated as "for every ε>0, eventually xr is within ε of a stationary point", so an empty X∗ cannot make it true.
Trivializing formalizations are ruled out: hypotheses on ui are required on all of X, not just along the run; uniqueness is required at every y∈X; and a sorry-free check shows that all hypotheses of Theorem 2(a) hold together for a one-block instance.
Not formalized: Proposition 2 (a sufficient condition for (B3)), Corollaries 2 and 3 (essentially cyclic and overlapping rules) and the applications of Section VIII. Contributions of reusable lemmas about cluster points of block methods and first-order conditions for constrained minimisers in a single block are welcome.
Selected references
M. Razaviyayn, M. Hong, Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, arXiv:1209.2385v1, 2012; SIAM J. Optim. 23(2) (2013) 1126–1153. https://arxiv.org/abs/1209.2385
P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001) 475–494. https://doi.org/10.1023/A:1017501703105
D. P. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, 1999.
B. Chen, S. He, Z. Li, S. Zhang, Maximum block improvement and polynomial optimization, SIAM J. Optim. 22(1) (2012) 87–107. https://doi.org/10.1137/110834858
Quality in Supply Chain Encroachment I: With Endogenous Uniform Quality, an Encroaching Manufacturer Gains and the Retailer Always LosesResearch Paper
Motivation
Manufacturers increasingly sell directly to consumers through their own stores and websites, alongside the independent retailers that carry their products. This practice is called supply chain encroachment. Retailers routinely resent it, and examples range from beer brewers to personal computers. Arya, Mittendorf and Sappington (Marketing Science, 2007) showed that, when product quality is fixed, encroachment can benefit the retailer too: the manufacturer lowers the wholesale price to keep the retailer channel competitive, and this wholesale price effect can outweigh the lost sales.
Ha, Long and Nasiry (Manufacturing & Service Operations Management, 2016; authors' manuscript SSRN 3970373) ask what changes when the manufacturer also chooses product quality. Their first result, formalized in this mission, is that the win–win outcome disappears: with endogenous quality and a single product sold in both channels, encroachment always helps the manufacturer and always hurts the retailer.
Setting
Consumers have a quality sensitivity θ uniformly distributed on [0,1], and a consumer who buys a product of quality u>0 at price p obtains surplus θu−p. When one product of quality u is sold in total quantity q, the market-clearing price is p=u(1−q). The manufacturer's unit production cost for quality u is ku2, with k>0 the cost of quality. Selling one unit through her own direct channel costs her an additional c≥0; the retailer's selling cost is 0.
Benchmark (no direct channel). The manufacturer chooses a wholesale price w and a quality u; after observing them the retailer orders qR≥0. The profits are
ΠRN=(u(1−qR)−w)qR,ΠMN=(w−ku2)qR.
Encroachment with uniform quality. The game has three stages and perfect information:
the manufacturer chooses w and u;
the retailer, having observed them, orders qR≥0;
the manufacturer, having observed qR, sells qM≥0 directly.
Both channels sell the same product at the price u(1−qR−qM), so
The solution concept is subgame perfect equilibrium: at every decision node, on or off the equilibrium path, the mover's rule picks a feasible action that no feasible alternative beats. The manufacturer encroaches when qMU>0 on the equilibrium path.
In the Lean development these are the structures Outcome and Profile, the payoffs retailerPayoff and mfrPayoff k c, and the predicate IsSPE k c σ of the definition QualityEncroach.Uniform.Game, with the benchmark counterparts BenchProfile and IsBenchSPE k τ.
Formalization targets
Goal: Proposition 1(iii)
In the benchmark, every equilibrium has uN=3k1 and profits ΠMN=54k1, ΠRN=108k1. The goal states that, for every k>0, c≥0 and every subgame perfect equilibrium of the encroachment game in which the manufacturer encroaches,
ΠMU>54k1=ΠMNandΠRU<108k1=ΠRN.
The statement fixes no threshold value, and it holds for every equilibrium.
Milestones
The milestones follow the paper's backward induction:
the benchmark subgame, equations (1)–(2), and the benchmark equilibrium (§3.2);
the manufacturer's stage-3 best response qMU(qR,w,u)=(21−2qR−2uc−2ku)+;
the quantity subgame (3) and the optimal wholesale price and profits (4)–(5) for a given quality;
the three-case optimal profit ΠM(u) of the Appendix, covering three regimes: the manufacturer sells directly, the retailer deters direct sales exactly, or the direct channel is idle;
Proposition 1(i): there is a threshold c~>0 such that
c<c~⇒qMU>0,c>c~⇒qMU=0.
Further statements
The mission also contains:
condition (6) for a fixed quality, together with the identity wN(u)−wU(u)=c/6;
Proposition 1(ii): the equilibrium quality first rises and then falls in c, and it is distorted upward exactly below a threshold cu;
Corollary 1: c~ is decreasing in k, and for c>0 the retailer's profit under encroachment is increasing in k;
existence of a subgame perfect equilibrium.
Significance
The result separates two regimes that look alike. With quality fixed, a retailer facing an encroaching manufacturer is better off exactly when condition (6) holds. With quality chosen by the manufacturer, that region disappears. The manufacturer distorts quality, upward when c is small and downward when it is large, and so relies less on the wholesale price to steer the retailer's order. The retailer then loses in every equilibrium in which encroachment occurs. The paper's later sections (quality differentiation, a fixed cost of quality, no quality commitment, a general cost function) all measure against this base case.
The result is proved on paper, by backward induction with closed-form profits, an envelope-theorem convexity argument in c, and a numerically located threshold c~≈0.1019/k. None of it is formalized. A machine-checked proof would certify:
the closed-form reduced profits;
the case analysis of the Appendix, whose boundaries are given by roots of polynomial equations in u;
the claim, stated in the paper only for the reduced problem, that it holds for every subgame perfect equilibrium of the game.
Difficulty
Each step of the backward induction is a one-variable concave problem, but the steps do not compose into a single smooth problem. The retailer's best order depends on whether his order leaves room for direct sales. As a result the manufacturer's profit given u is the piecewise function ΠM(u). Its middle piece describes a retailer who orders exactly enough to keep the manufacturer out, and that piece is not a stationary point of anything. The global optimum over u switches between the first piece and the other two at a threshold c~ that the paper locates only numerically.
The goal compares the optimum of this piecewise problem with a constant, for every equilibrium. The natural first idea, comparing the reduced profits with the benchmark ones pointwise in u, does not work for the retailer: for a fixed quality his encroachment profit 2c2/(9u) exceeds the benchmark profit u(1−ku)2/16 on part of the range, which is exactly condition (6). The comparison has to use the quality the manufacturer actually chooses, and that quality is known only through the case analysis above.
Formalization scope
All quantities are real numbers. The following conventions are fixed:
the wholesale price ranges over all of R, since the paper states no sign restriction;
qualities are u>0 and quantities qR,qM≥0;
the inverse demand u(1−qR−qM) is used for all nonnegative quantities, as in the paper.
Subgame perfection is written in one-shot-deviation form at every history, which in this three-stage game with perfect information is subgame perfection. It constrains the retailer's rule at every (w,u) and the manufacturer's stage-3 rule at every (w,u,qR), not only on the path.
The benchmark profits in the goal are the paper's constants 1/(54k) and 1/(108k). The milestone benchmark_equilibrium proves that a benchmark equilibrium exists and that these are its profits.
Two formalizations would trivialize the goal, and both are ruled out:
stating the goal about the reduced form ΠMU at a maximizer of ΠM(u) instead of about the game would assume the backward induction;
dropping the off-path optimality conditions would let the goal range over non-equilibria.
The encroachment threshold of Proposition 1(i) is stated in both directions, with c~>0 chosen before c. The boundary point c=c~ is left open, because the paper's statements disagree there.
The closed forms qRN, wN, ΠMN, ΠRN, qMU, qRU, wU, ΠMU, ΠRU, ΠMUZ and ΠM are definitions that cite their page. Every statement that uses one with u in a denominator assumes u>0.
A complete development needs:
concave quadratic maximization;
a piecewise-concave best-response lemma;
the envelope argument of the Appendix, or a direct polynomial comparison;
some way to certify the numerically located thresholds, for which interval arithmetic or explicit polynomial sign certificates are both acceptable.
The game definitions are reusable for the other missions of this series, which keep this cost structure. Proofs of any milestone are welcome, as are alternative arguments for the goal that bypass the threshold computation.
A. Arya, B. Mittendorf, D. E. M. Sappington, The Bright Side of Supplier Encroachment, Marketing Science 26(5): 651–659, 2007. https://doi.org/10.1287/mksc.1070.0280
Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 4: Lagrangian Duals of the Reduced Relaxation and Their Closed-Form Optimal Dual VariablesResearch Paper
Motivation
Best subset selection with ridge shrinkage, the ℓ0ℓ2-regularized least squares problem
β∈Rpmin21∥y−Xβ∥22+λ0∥β∥0+λ2∥β∥22,
is a mixed integer program. Exact solvers for it rely on branch-and-bound: at every node of the search tree a convex relaxation is solved, and the node is discarded if a lower bound on that relaxation already exceeds the best objective value found so far. Hazimeh, Mazumder and Saab (arXiv:2004.06152v2, Mathematical Programming 2022) build such a solver, L0BnB, for instances with p in the millions. Its relaxations are solved only approximately, by first-order methods, and an approximate primal solution does not by itself certify a lower bound. The bound has to come from a dual feasible point. Theorem 2 of the paper supplies the duals of the node relaxation in closed form, together with explicit formulas for the optimal dual variables as functions of the primal optimum. Everything the paper later proves about the quality of its dual bounds (Section 3.2, Theorem 3) starts from these formulas.
Setting
Data are a matrix X∈Rn×p with columns X1,…,Xp, a response y∈Rn, and parameters λ0,λ2,M>0, where M bounds the coefficients. Write [p]={1,…,p} and [a]+=max{a,0}. The reverse Huber penalty is B(t)=∣t∣ for ∣t∣≤1 and B(t)=(t2+1)/2 for ∣t∣≥1. Define
ψ1(b)=2λ0B(bλ2/λ0),ψ2(b)=(Mλ0+λ2M)∣b∣,
and let ψ=ψ1 if λ0/λ2≤M and ψ=ψ2 if λ0/λ2>M. The reduced relaxation (5) is
where h1 is maximized over all of Rn×Rp (problem (20)) and h2 subject to ∣ρTXi∣−μi≤λ0/M+λ2M for i∈[p] (problem (22)). For an optimal β∗ of (5), with residual r∗=y−Xβ∗, the candidate dual variables are
In the Lean development these objects are F, box, h1, v, h2, Feas22, alphaStar, gammaStar, rhoStar, muStar in the namespace L0BnB.Duality.
Formalization targets
Goal: Theorem 2 (pp. 13–14)
Let β∗ minimize F over ∥β∥∞≤M.
If λ0/λ2≤M: h1(α,γ)≤F(β) for all α,γ and all feasible β, and h1(α∗,γ∗)=F(β∗).
If λ0/λ2>M: h2(ρ,μ)≤F(β) for all (ρ,μ) feasible for (22) and all feasible β; (ρ∗,μ∗) is feasible for (22) and h2(ρ∗,μ∗)=F(β∗).
This is "(20), respectively (22), is a dual of (5), and (23), respectively (24), are optimal dual variables", with the paper's remark that strong duality holds.
Milestones
(45) For a∈R, η≥0 and D(b)=ψ1(b)+ab+η∣b∣, the point 0 (if 2λ0λ2+η−∣a∣≥0) or −λ0/λ2sign(a) (otherwise) minimizes D on ∣b∣≤λ0/λ2.
(47) If ∣a∣−η≥2λ0λ2, then minb∈RD(b)=−4λ21(∣a∣−η)2+λ0.
Weak duality, the first halves of both bullets of the goal.
(23)h1(α∗,γ∗)=F(β∗) when λ0/λ2≤M.
(24)(ρ∗,μ∗) feasible for (22) and h2(ρ∗,μ∗)=F(β∗) when λ0/λ2>M.
Significance
The result. Theorem 2 turns the node relaxation of L0BnB into a pair of explicit concave maximization problems, one per regime of λ0/λ2 versus M. The dual (20) is unconstrained, so any (α,γ) gives a valid lower bound; the paper's dual bounds (25)–(28) evaluate h1 or h2 at α^=−r^ built from an inexact primal solution β^, with the remaining variable chosen in closed form. The formulas (23)–(24) explain why this choice is right: at the exact optimum it recovers the primal value. Theorem 3 of the paper, which bounds the loss of this dual bound by a quantity depending on the support size rather than on p, compares v(α^,γ^i) to v(α∗,γi∗) term by term and therefore depends on (23).
Formalizing it. The paper proves the case λ0/λ2≤M in Appendix A and omits the proof of the case λ0/λ2>M ("follows along the lines similar to what was shown above"). The appendix also contains an intermediate formula for the coordinate minimum, −[(∣αTXi∣−ηi)2/(4λ2)−λ0]+, that is incorrect when ηi is large; the final dual (49) = (20) is nevertheless correct. A machine-checked proof supplies the omitted case and settles the correct statement. To our knowledge neither half has been formalized.
Difficulty
The dual objective (20) hides the box constraint inside the term M∣γi∣ and the penalty inside [⋅]+, and the reverse Huber penalty is piecewise, so even the weak-duality half has to handle both pieces of ψ1 and the junction ∣b∣=λ0/λ2. The attainment half is where the work lies: it needs the optimality conditions of a nonsmooth convex problem over a box, at coordinates where βi∗=0 (where ψ is not differentiable), where ∣βi∗∣=M (where the box is active), and where both may interact with the regime boundary λ0/λ2=M. The natural first idea, to read (23) off the Lagrangian derivation in the paper, does not yield a proof: that derivation assumes a dual optimum (α∗,η∗) exists and relates it to β∗ by complementary slackness, whereas the theorem asserts an identity for the explicit (α∗,γ∗) built from β∗ alone.
Formalization scope
Data are X : Matrix (Fin n) (Fin p) ℝ, y : Fin n → ℝ and reals lam0 lam2 M with 0 < lam0, 0 < lam2, 0 < M as hypotheses; [p] is Fin p. Norms and inner products are explicit sums: αTXi=∑rαrXri, ∥α∥22=∑rαr2, ∥μ∥1=∑i∣μi∣, [a]+=max{a,0}, and ∥β∥∞≤M is ∣βi∣≤M for every i. The regime split is written λ0/λ2≤M versus M<λ0/λ2. sign is Real.sign, with sign(0)=0; where it is evaluated in (23) the argument is nonzero at an optimum. The optimal solution β∗ is a hypothesis (feasible and minimizing F over the box); its existence is not part of the statements. The coordinate milestones (45) and (47) are stated for a scalar a standing for αTXi and a multiplier η≥0. No normalization of X or y is assumed: the unit-norm convention that opens Section 3 is not used by Theorem 2. The paper writes no O(⋅) in these results, so no constants are instantiated.
"A dual is given by" is formalized as weak duality over all dual-feasible points together with equality at the explicit dual variables. Weak duality alone would not be Theorem 2, and neither would the equality alone; the goal requires both in both regimes. Uniqueness of the dual optimum is not claimed.
A complete development needs elementary convex analysis of the scalar penalty ψ1 (its conjugate and subdifferential), first-order optimality conditions for a convex function over a box in Rp, and finite-sum bookkeeping. The scalar facts about the reverse Huber penalty are reusable in the companion missions on the reduced relaxation and on dual-bound quality. Contributions to any milestone, or a direct proof of the goal, are welcome.
Selected references
H. Hazimeh, R. Mazumder, A. Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2 (2021); Mathematical Programming (2022). https://arxiv.org/abs/2004.06152v2
D. Bertsimas, A. King, R. Mazumder, Best subset selection via a modern optimization lens, Annals of Statistics 44(2), 813–852, 2016. https://doi.org/10.1214/15-AOS1388
H. Hazimeh, R. Mazumder, Fast best subset selection: coordinate descent and local combinatorial optimization algorithms, Operations Research 68(5), 1517–1537, 2020. https://arxiv.org/abs/1803.01454
Approximation Algorithms for Product Framing and Pricing 3: Under MNL Pricing, Optimal Framing Fills Pages in Descending Quality Order with One Price per PageResearch Paper
Motivation
Online retailers show their catalogue on a sequence of pages, and most visitors never reach the last one. Which products appear on the first page, and at what prices, therefore decides what a typical consumer can buy at all. Gallego, Li, Truong and Wang (Operations Research, 2020) model this as the product framing problem: the consideration set of a consumer is the set of products on the pages that consumer is willing to view, and the number of pages viewed is random. Their Section 7 adds prices to the problem and asks how a retailer should frame and price jointly when consumers choose by the multinomial logit (MNL) model.
The question connects two literatures. In assortment pricing under MNL with a common price sensitivity, the optimal prices of all offered products are known to be equal (Anderson, de Palma and Thisse 1992; Gallego and Stefanescu, as cited on p. 16 of the paper), and the nested-logit extension of Gallego and Wang (Operations Research, 2014) keeps an adjusted markup constant across nests. In search and ranking models, the order in which products are shown changes which ones are bought. The paper's structural results say what survives of the equal-price rule once consideration sets are nested by page, and which products belong on the early pages.
Setting
There are n products, i∈[n]={1,…,n}, and mpages, each holding at most p products. A framing places each product on one page x(i)∈[m] or leaves it undisplayed. A consumer views the first X pages, where X∈[m] is random with law λ(x)=P[X=x], independent of the framing. A consumer who views x pages considers S(x), the products on pages 1,…,x, so S(1)⊆S(2)⊆⋯⊆S(m).
Product i has a qualityai∈R and a priceri∈R, and the price sensitivity is β>0. The mean utility of product i is ui=ai−βri, and the outside option has utility u0=0. Under the MNL model a consumer with consideration set S buys i∈S with probability
P(i,S)=1+∑k∈Seukeui,
and P(i,S)=0 for i∈/S. The expected revenue from that consumer is R(r∣S)=∑i∈SriP(i,S), and the total expected revenue of a framing and a price vector is
E[R(r∣S(X))]=x=1∑mλ(x)R(r∣S(x)).
For a fixed framing, R(a) denotes the optimal value of this quantity over all price vectors, as a function of the quality vector a.
Formalization targets
Goal: Theorem 6 (p. 17)
The goal is the existence of an optimal joint solution with the paper's structure: there are a feasible framing and prices r∈Rn such that no feasible framing with any prices earns more, and
∣S(x)∣=min(n,xp)for all x∈[m],ak≤ai whenever i is displayed and k is undisplayed or on a later page.
Pages are filled in order until all products are displayed, and the products appear in descending order of quality.
Milestones
(15), p. 43. The partial derivative of the total expected revenue in the price of a displayed product:
(17), p. 43. At every optimal price vector, each displayed price is 1/β plus a weighted average of the revenues R(r∣S(l)), l≥x(i).
Theorem 5, p. 16. For a fixed framing, every optimal price vector is constant on each page, ri=θx(i), with θ1≤θ2≤⋯≤θm.
(19), p. 44. The optimal value R(a) is nondecreasing in the quality of any displayed product.
Significance
Theorem 5 reduces the pricing problem of a fixed framing from n prices to m page prices and says that later pages carry higher prices; this is the page-level analogue of the constant-markup property of MNL pricing, and it runs opposite to the ordering found in oligopoly search models (Arbatskaya 2007). Theorem 6 removes the framing decision almost entirely: a joint optimum is obtained by sorting the products by quality and filling pages in that order, leaving only page prices to choose. The paper's approximation algorithm for joint pricing and framing (Theorem 7, NEST-P, with guarantee 6/π2) starts from this structure.
None of these statements has a machine-checked proof. A complete development would give the first formal treatment of MNL price optimization with nested consideration sets, including the existence of optimal prices, which the paper takes for granted. The paper's argument for the monotonicity θ1≤⋯≤θm and its envelope-theorem step (19) are informal; a formal proof has to supply both.
Difficulty
The expected revenue is not concave in the prices, even with two products on two pages (Example 1, p. 17), so the first-order condition alone does not identify the optimum, and existence of an optimal price vector has to be argued from the behaviour of the revenue as prices tend to ±∞. The within-page equality of prices follows from the first-order condition, but the ordering of page prices needs a global comparison of revenues across consideration sets. In Theorem 6, the obvious exchange argument (swap a higher-quality product forward) does not obviously keep revenue from decreasing when the swapped products have different prices; the paper splits into two cases, and in one of them the improvement comes from continuously moving qualities, which requires control of the optimal value as a function of a rather than of a fixed price vector.
Formalization scope
Products are Fin n, pages are the natural numbers 1,…,m with m≥1, and capacities satisfy p≥1. A framing is f : Fin n → ℕ with page f i ∈ [m] for displayed products and f i = 0 for undisplayed ones (the paper's x(i)=m+1); feasibility means at most p products per page. The law of X is a nonnegative function on [m] summing to one. Prices are finite reals: the paper's priced-out products (ri=+∞) coincide with undisplayed ones, which the framing already allows. "Descending order" and "increases" are read weakly.
Theorem 5 and (17) are stated for every maximizing price vector and only for products on pages that some consumer reaches (Λ(x)=P[X≥x]>0), a restriction the paper never discusses: a product on a page no consumer reaches can carry any price at an optimum. They do not assert that a maximizer exists. Theorem 6 is read existentially ("some optimal solution has this structure"); the universal reading is false when some λ(x)=0, because exchanging products between pages x and x+1 then changes no revenue. (19) is formalized as its stated consequence, the monotonicity of the optimal value R(a)=suprE[R(r∣S(X))], together with the boundedness of the revenues; the envelope identity itself would need a differentiable selection of optimal prices that the paper does not establish.
A trivializing formalization of the goal would take the optimum over framings that are already sorted, over a single fixed framing, or over prices fixed in advance; the goal's optimality clause ranges over all feasible framings and all real price vectors. The development needs elementary calculus of the MNL revenue (HasDerivAt, Real.exp), finite sums over pages, and a compactness or limiting argument for the existence of optimal prices. Pages are those of the authors' accepted manuscript, which differ from the journal typesetting. Proofs of any milestone, and lemmas on MNL pricing reusable beyond this paper (boundedness of R(r∣S), existence of optimal MNL prices, the constant-price property for a single assortment), are welcome.
Selected references
G. Gallego, A. Li, V.-A. Truong, X. Wang, Approximation Algorithms for Product Framing and Pricing, Operations Research 68(1), 2020. https://doi.org/10.1287/opre.2019.1875
S. P. Anderson, A. de Palma, J.-F. Thisse, Discrete Choice Theory of Product Differentiation, MIT Press, 1992 (book; cited by the paper for the equal-price property of MNL pricing).
G. Gallego, R. Wang, Multiproduct Price Optimization and Competition under the Nested Logit Model with Product-Differentiated Price Sensitivities, Operations Research 62(2), 2014. https://doi.org/10.1287/opre.2013.1249
Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 1: For α > 3 and ∫ tε(t) dt < +∞ the Trajectory Converges Weakly to a Minimizer of gResearch Paper
Motivation
Minimizing a convex function g on a real Hilbert space H by first-order methods has a continuous-time counterpart: second-order differential equations whose trajectories descend g. Su, Boyd and Candès (20) showed that Nesterov's accelerated gradient method is a discretization of x¨+tαx˙+∇g(x)=0 with α=3, along which g(x(t))−ming=O(1/t2). Two modifications of this equation have been studied separately because each adds a property the plain system lacks.
A Hessian-driven damping term β∇2g(x(t))x˙(t) (Attouch, Peypouquet, Redont, J. Differential Equations 2016) damps oscillations and, for β>0, makes t2∥∇g(x(t))∥2 integrable, while keeping fast values and weak convergence of trajectories.
A Tikhonov regularization term ϵ(t)x(t) with ϵ(t)↓0 (Attouch, Chbani, Riahi, J. Math. Anal. Appl. 2018) can steer trajectories to the minimum-norm minimizer.
Boţ, Csetnek and László (arXiv:1911.12845v2, 2020) combine both terms and ask which properties of the two parent systems survive. This mission covers the first of their answers: when ϵ decays fast enough, the fast rates and the weak convergence of trajectories are preserved.
Timeline. 2016 (published 2018): weak convergence of trajectories of x¨+tαx˙+∇g(x)=0 for α>3 (Attouch, Chbani, Peypouquet, Redont, Math. Program. 168). 2016: the same with Hessian-driven damping, β>0 (Attouch, Peypouquet, Redont). 2018: Tikhonov regularization of that system, with the O(1/t2) rate kept and strong convergence to the minimum-norm minimizer under slow decay of ϵ (Attouch, Chbani, Riahi). 2020: both terms together (Boţ, Csetnek, László, this paper).
Setting
Fix a real Hilbert space H, a starting time t0>0, parameters α≥3 and β≥0, and initial data u0,v0∈H. The General assumption of the paper is:
g:H→R is convex and twice Fréchet differentiable, ∇g is Lipschitz continuous on bounded sets, and argming=∅; ming denotes its minimal value;
ϵ:[t0,+∞)→[0,+∞) is nonincreasing, of class C1, and ϵ(t)→0 as t→+∞.
A global C2-solution is a twice continuously differentiable x:[t0,+∞)→H satisfying (5) for every t≥t0. The decay of ϵ is controlled by ∫t0+∞tϵ(t)dt<+∞ together with one of two conditions:
(a) there exist a>1 and t1≥t0 with ϵ˙(t)≤−2aβϵ2(t) for all t≥t1;
(b) there exist a>0 and t1≥t0 with ϵ(t)≤ta for all t≥t1.
A curve x(t)converges weakly to xˉ if ⟨x(t),v⟩→⟨xˉ,v⟩ for every v∈H. The Lean development lives in the namespace TikhonovHDD.Weak, with IsSolution, GenAssumptionG, GenAssumptionEps, CondA, CondB, argmin, minVal and WeakTendstoAtTop for these objects.
Formalization targets
Goal: Theorem 3.5 (p. 15)
Under the General assumption, ∫t0+∞tϵ(t)dt<+∞ and (a) or (b), if α>3 then every global C2-solution of (5) satisfies
∃xˉ∈argming:x(t)⇀xˉ(t→+∞).
Milestones
In the order the argument uses them:
Theorem 2.1 (p. 4): existence and uniqueness of a global C2-solution of (5).
Lemma A.2 (p. 29): a bounded-below, locally absolutely continuous F with F˙≤G∈L1 a.e. has a finite limit.
Theorem 3.3 (p. 11), split three ways: for α≥3, g(x(t))−ming=O(1/t2); for α>3, x is bounded and t(g(x(t))−ming), t∥x˙∥2, tϵ∥x−x∗∥2, tϵ∥x∥2∈L1; and separately t2∥∇g(x(t))∥2∈L1.
Lemma A.3 (p. 30): u(t)+αtu˙(t)→uˉ with α>0 implies u(t)→uˉ.
Theorem 3.4 (p. 12): for α>3 and every x∗∈argming, t⟨∇g(x),x−x∗⟩∈L1, lim∥x(t)−x∗∥ and limt⟨x˙+β∇g(x),x−x∗⟩ exist, g(x(t))−ming=o(1/t2), ∥x˙+β∇g(x)∥=o(1/t), and t2ϵ(t)∥x(t)∥2→0.
Significance
The result. Theorem 3.5 shows that the Tikhonov term, when it decays at least as fast as ∫tϵ<∞ requires, does not disturb the asymptotics of the Hessian-damped system: values converge at rate o(1/t2) and trajectories converge weakly to a minimizer. With β=0 it recovers the corresponding results for the regularized system without Hessian damping, and with ϵ≡0 those for the Hessian-damped system. It is also the boundary case of the paper's second half, where slower decay of ϵ is shown to give strong convergence to the minimum-norm minimizer instead.
Formalizing it. The results are proved in the paper; none of them is machine-checked. A formal development would produce reusable pieces: a Lyapunov-energy analysis of second-order systems with time-dependent coefficients, the asymptotic Lemmas A.2 and A.3, and the bridge from "the distance to every minimizer converges and weak cluster points are minimizers" to weak convergence of a curve (the continuous Opial lemma).
Difficulty
The obvious approach, a single Lyapunov function that decreases along trajectories, fails here: the Tikhonov term makes the natural energy Eb only almost nonincreasing, with an error ∝tϵ(t)∥x∗∥2 that must be integrated, and the Hessian term produces a cross term −βϵ(t)t2⟨∇g(x),x⟩ that is controlled only by condition (a) or (b). The step from O(1/t2) to o(1/t2) and to the existence of lim∥x(t)−x∗∥ cannot be read off a single bounded energy: boundedness of Eb gives rates in O, not in o, and says nothing directly about ∥x(t)−x∗∥. Weak convergence then requires Opial's lemma, which is not in Mathlib in continuous form. Existence of solutions is itself nontrivial in infinite dimension: the right-hand side involves ∇2g, so the system has to be rewritten as a first-order system before the Cauchy–Lipschitz theorem applies.
Formalization scope
H is any real Hilbert space (InnerProductSpace ℝ H, CompleteSpace H); nothing is finite-dimensional, so weak convergence is genuinely weaker than norm convergence. It is stated through inner products with every v∈H; stating it as norm convergence, or testing only some v, would change the theorem.
Trajectories are maps R→H with velocity and acceleration maps; derivatives are one-sided at t0 and values before t0 play no role. Every theorem is stated for everyC2-solution; Theorem 2.1 shows this class is a singleton, so the hypothesis is not vacuous. A sorry-free check that the hypotheses of the goal can be met (g=0, ϵ=0, x=0) accompanies the drafts.
∇2g(x)v is the derivative of ∇g at x applied to v; ϵ˙ is a derivative map tied to ϵ on [t0,+∞); ming=infg, attained since argming=∅; L1 membership is Lebesgue integrability on [t0,+∞) (never a comparison of a Bochner integral with a number); O, o are Asymptotics relations at +∞.
Repair. Theorem 2.1 carries the extra hypothesis "β=0 or g∈C2". As printed (only twice differentiable g) it is false for β>0: on R, g′(x)=2x+x2sin(1/x) gives a strongly convex g with bounded but discontinuous g′′, and the solution from u0=0, v0=1 is not C2. The paper's own proof uses continuity of ∇2g.
Flagged, not repaired. The last claim of Theorem 3.3, t2∥∇g(x(t))∥2∈L1, is its own item: the paper's argument for it uses a term proportional to β, so for β=0 the paper gives no proof. No counterexample is known, and the statement is drafted as printed.
Referenced, not re-posed. Lemma A.4 (continuous Opial lemma, p. 30), the last step of the goal's proof, is the published InertialAVD.Traj.lemma_A_2 (same hypotheses: S nonempty, lim∥x(t)−z∥ exists for every z∈S, every weak sequential limit point lies in S; same conclusion). It is a reference milestone of this mission; its weak convergence InertialAVD.Traj.WeakTendstoAtTop has the same body as TikhonovHDD.Weak.WeakTendstoAtTop.
The model is defined from scratch: the published HessianDamping.DINAVD.Setting concerns a different equation (no ϵx term) and is not reused.
Welcome contributions: a general Cauchy–Lipschitz existence theorem for locally Lipschitz first-order systems in Banach spaces on [t0,+∞) with a blow-up alternative, the continuous Opial lemma, and Lemma A.2 for absolutely continuous functions.
H. Attouch, J. Peypouquet, P. Redont, Fast convex optimization via inertial dynamics with Hessian driven damping, J. Differential Equations 261(10), 5734–5783, 2016. https://doi.org/10.1016/j.jde.2016.08.020
H. Attouch, Z. Chbani, H. Riahi, Combining fast inertial dynamics for convex optimization with Tikhonov regularization, J. Math. Anal. Appl. 457(2), 1065–1094, 2018. https://doi.org/10.1016/j.jmaa.2016.12.017
H. Attouch, Z. Chbani, J. Peypouquet, P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program. 168, 123–175, 2018. https://doi.org/10.1007/s10107-016-0992-8
W. Su, S. Boyd, E.J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: theory and insights, J. Mach. Learn. Res. 17(153), 1–43, 2016. https://jmlr.org/papers/v17/15-084.html
A Tutorial on Thompson Sampling I: Any Algorithm Whose Information Ratio Is at Most Γ̄ Has Expected Regret at Most √(Γ̄·H(x*)·T)Research Paper
Motivation
Thompson sampling (TS) chooses each action with the posterior probability that it is optimal. Its practical success in online advertising, recommendation and experimentation raised the question of why it works and when it does not. The tutorial of Russo, Van Roy, Kazerouni, Osband and Wen (Found. Trends Mach. Learn. 11(1), 2018) answers part of that question in §8.1 with an information-theoretic regret bound due to Russo and Van Roy (JMLR 17, 2016). The bound applies to every algorithm, not only TS. It reduces the analysis of a particular algorithm to one quantity, the information ratio: the squared expected regret of a period divided by the information the period yields about the optimal action.
Timeline:
2016: Russo and Van Roy, An information-theoretic analysis of Thompson sampling (JMLR 17), introduce the information ratio with the regret and the mutual information both conditioned on a realised history, and prove the regret bound and bounds on the ratio for TS (for example ∣X∣/2 for ∣X∣-armed bandits and d/2 for linear bandits).
2018: Russo and Van Roy, Learning to optimize via information-directed sampling (Oper. Res. 66), design algorithms that minimise the information ratio directly.
2018: Russo and Van Roy, Satisficing in time-sensitive bandit learning (arXiv:1803.02855), observe that the same bounds hold with the information ratio averaged over histories. This is the form (8.7) the tutorial uses (footnote 1, p. 75).
2018: the tutorial gives the bound as (8.8), with a three-line proof on p. 76 whose last step is cited from the 2016 paper.
Setting
An agent acts in periods t=1,2,…. In each period it selects an action xt from a finite set X and observes an outcome yt from a finite set Y. An unknown parameter θ, taking values in a measurable space Θ, has a prior distribution P. Given θ and the action x, the outcome is drawn from a probability vector qθ(⋅∣x) that depends measurably on θ. The agent receives the reward r(yt) for a known function r. The mean reward of action x is
μ(x,θ)=y∑qθ(y∣x)r(y),
and the optimal actionx∗=x∗(θ) is a measurable selector of argmaxxμ(x,θ). Ties may be broken in any measurable way, and every result holds for every selector.
The historyHt is the list (x1,y1),…,(xt,yt). An algorithmπ assigns to every history a probability vector over X, from which the next action is drawn. The joint law of (θ,Ht) is P(dθ)∏s≤tπ(xs∣Hs−1)qθ(ys∣xs), and every expectation below is taken under it. The expected cumulative regret, or Bayesian regret, is
E[Regret(T)]=E[t=1∑T(μ(x∗,θ)−μ(xt,θ))].
The entropy of the prior distribution of x∗ is H(x∗)=−∑aP(x∗=a)logP(x∗=a). The conditional mutual informationI(x∗;(xt,yt)∣Ht−1) is the expected information that the period-t observation carries about x∗ given the past, averaged over the past. The information ratio of period t is (8.7):
Γt=I(x∗;(xt,yt)∣Ht−1)(E[μ(x∗,θ)−μ(xt,θ)])2.
Formalization targets
Goal: (8.8)
For every model and every algorithm, every horizon T and every Γˉ≥0 with (E[μ(x∗,θ)−μ(xt,θ)])2≤ΓˉI(x∗;(xt,yt)∣Ht−1) for t=1,…,T,
E[Regret(T)]≤ΓˉH(x∗)T.
When every mutual information is positive, the least such Γˉ is maxt≤TΓt, which is the tutorial's Γˉ. A companion theorem states that literal form under the positivity hypothesis.
Milestones, in the order of the p. 76 proof
Regret is additive over periods:
E[Regret(T)]=t=1∑TE[μ(x∗,θ)−μ(xt,θ)].
The Jensen (Cauchy–Schwarz) step: if δt2≤ΓˉIt for every t and ∑tIt≤H, then ∑tδt≤TΓˉH. This milestone is the published, proved theorem BanditAlgorithm.information_ratio_cumulative_bound_signed. It states the step in the form the proof uses, with the entropy budget as a hypothesis.
The entropy budget:
t=1∑TI(x∗;(xt,yt)∣Ht−1)≤H(x∗).
Significance
The result. (8.8) separates the regret analysis of an algorithm into two independent problems. One is a per-period bound on the information ratio, which depends on the structure of the problem and the algorithm. The other is the entropy of the optimal action, which depends only on the prior. Combined with the bound Γˉ≤∣X∣/2 that Russo and Van Roy (2016) prove for TS on ∣X∣-armed bandits, and with H(x∗)≤log∣X∣, it gives ∣X∣Tlog∣X∣/2. On the shortest-path problem of p. 76, Γˉ≤d/2 makes the regret depend on the number d of edges and on H(x∗), not on the exponentially large number of paths. The same inequality is the design criterion of information-directed sampling, which chooses actions to minimise the ratio.
Formalizing it. The bound and its proof are known. The work here is to make the probabilistic model explicit, with a general parameter space, an outcome kernel and randomized algorithms; to formalize the per-period decomposition of the regret and the chain-rule argument behind the entropy budget, which the tutorial cites rather than proves; and to obtain (8.8) for every algorithm in one statement. The Proved platform results for Lattimore and Szepesvári's Bayesian adversarial bandit (Theorem 36.5 and its chain-rule lemmas) are about a different model: one algorithm (TS), the best arm in hindsight of a reward matrix, and the budget logk. To our knowledge, (8.8) itself has not been formalized.
Difficulty
The Cauchy–Schwarz step is elementary and already proved on the platform. Milestone 1 is bookkeeping: the cumulative regret integrates over histories of length T, while the period-t term integrates over histories of length t, and later periods must be integrated out.
The substance is the entropy budget. The obvious attempt bounds each period's information by H(x∗), which loses a factor T. The bound is uniform in T only because the per-period informations telescope: their sum is the information that the whole history carries about x∗, which is at most the entropy of x∗. Each step requires conditional distributions of x∗ given histories, where θ lives in a general measurable space and is integrated against the prior. Zero-probability histories must also be handled consistently with the convention 0log0=0.
Formalization scope
X and Y are finite types; Θ is an arbitrary measurable space with a probability measure P. The tutorial allows infinite action sets and general outcomes. The finite specialization makes H(x∗) and every mutual information a finite sum. The kernel qθ(⋅∣x) of §4 replaces the noise representation yt=g(xt,θ,wt) of p. 70; both describe the same laws.
Standing hypotheses: qθ(y∣x)≥0, ∑yqθ(y∣x)=1, measurability of θ↦qθ(y∣x), measurability of the level sets of x∗, and μ(x,θ)≤μ(x∗(θ),θ). They make every integrand bounded and measurable, so no integrability hypothesis is added.
An algorithm is a behavioural policy, giving a probability vector over actions for each history. Under perfect recall this is equivalent to an algorithm with internal randomization. Periods are 0-based in Lean: Lean period s is tutorial period t=s+1.
Logarithms are natural in both I and H. The conditional mutual information is defined directly as an average of Kullback–Leibler divergences, with joint probabilities. It is not defined as a difference of unconditional mutual informations: that would make the chain rule true by definition and empty milestone 3. Γt is never written as a quotient in the goal, so a period with zero information cannot turn the bound into one with Γˉ=0.
Needed infrastructure: marginalisation over later periods of the history law, the chain rule of conditional mutual information for finite variables averaged against a general prior, and I(x∗;HT)≤H(x∗). The Proved platform results InformationTheory.kernel_average_categorical_kl_le_marginal_entropy and its _general variant (average KL to the mixture is at most the mixture's entropy), and the adversarial-bandit lemmas BanditAlgorithm.bayesian_ts_conditional_information_gain_chain_rule and bayesian_history_mutualInformation_endpoint_bound, are related tools. A chain-rule library for this history model would be reusable beyond this mission, for example for information-directed sampling. Proofs of auxiliary lemmas are welcome.
The tutorial's argument is on pp. 75–76. The tutorial cites Russo and Van Roy (2016) for the original results, including the entropy budget.
Selected references
D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, A Tutorial on Thompson Sampling, Foundations and Trends in Machine Learning 11(1):1–96, 2018. https://doi.org/10.1561/2200000070
D. Russo, B. Van Roy, Learning to Optimize via Information-Directed Sampling, Operations Research 66(1):230–252, 2018. https://doi.org/10.1287/opre.2017.1663
Computational Optimal Transport VIII: Sinkhorn's Scalings Contract by λ(K)² per Iteration in Hilbert's Projective MetricTextbook
Why Sinkhorn's algorithm needs a convergence rate
Sinkhorn's algorithm is the standard method for computing entropically regularized optimal transport between two histograms. It is used throughout machine learning, statistics, imaging and graphics because each iteration is two matrix–vector products followed by entrywise divisions, which parallelize on GPUs and differentiate easily. The same iteration, under the names matrix scaling, RAS or iterative proportional fitting, has been used since the 1930s in transportation planning, economics and contingency-table analysis. Whether the iteration converges, and how fast, determines how many iterations a practitioner must run and which stopping criteria are reliable.
This mission formalizes the global convergence analysis of Sinkhorn's algorithm as presented in Chapter 4 (§4.2, Remarks 4.12–4.14) of G. Peyré and M. Cuturi, Computational Optimal Transport (2019).
Timeline. Sinkhorn (1964) proved that a positive matrix can be scaled to be doubly stochastic, and Sinkhorn and Knopp (1967) extended this to prescribed marginals. Birkhoff (1957) and Samelson (1957) independently showed that a positive linear map is a strict contraction of the positive cone for Hilbert's projective metric, with an explicit ratio. Franklin and Lorenz (1989) combined the two to prove that Sinkhorn's scalings converge linearly in Hilbert's metric at rate λ(K)2. Linial, Samorodnitsky and Wigderson (1998) related the iteration to the permanent.
Setting
Fix n,m≥1, a matrix K∈Rn×m with positive entries (in the book, the Gibbs kernelKi,j=e−Ci,j/ε), and vectors a∈Rn, b∈Rm with positive entries. Products ⊙ and quotients of vectors are entrywise. The regularized transport plan has the form P=diag(u)Kdiag(v), where the scalingsu,v solve
u⊙(Kv)=a,v⊙(K⊤u)=b.(4.14)
Sinkhorn's algorithm alternately enforces each equation:
v(0)=1m,u(ℓ+1)=Kv(ℓ)a,v(ℓ+1)=K⊤u(ℓ+1)b.(4.15)
For vectors with positive entries, Hilbert's projective metric is
dH(u,u′)=logi,jmaxujui′uiuj′,
which vanishes exactly when u and u′ are proportional, and equals the variation seminorm∥logu−logu′∥var with ∥f∥var=maxifi−minifi. Birkhoff's constants of K are
and for ℓ≥0 the mirrored bound for v(ℓ) with the half-step coupling diag(u(ℓ+1))Kdiag(v(ℓ)). The book writes the rate as O(λ(K)2ℓ); the constants stated are those its proof yields.
Milestones, in attack order
(4.21): dH(u,u′)=∥logu−logu′∥var.
Remark 4.12: dH is a distance on rays (triangle inequality; zero exactly on proportional vectors).
Invariances: dH(v,v′)=dH(v/v′,1)=dH(1/v,1/v′) and invariance under positive diagonal scaling.
Theorem 4.1 (Birkhoff–Hopf): dH(Kv,Kv′)≤λ(K)dH(v,v′) and λ(K)<1.
One half-step contracts by λ(K): dH(u(ℓ+1),u⋆)≤λ(K)dH(v(ℓ),v⋆), and the v-analogue.
The display behind (4.23): dH(u(ℓ),u⋆)≤dH(a,u(ℓ)⊙Kv(ℓ))+λ(K)2dH(u(ℓ),u⋆), and its mirror.
Significance
The result. Theorem 4.2 gives a global linear rate that holds from the first iteration, independent of the starting point, with a ratio computable from K alone. Through (4.21) the rate transfers to the dual potentials εlogu(ℓ), and the bounds (4.23) turn the marginal violations P(ℓ)1m versus a — which are computed anyway — into certified stopping criteria. Theorem 4.1 alone also yields a quantitative Perron–Frobenius theorem (Remark 4.13).
Formalizing it. All results here are classical and proved in the literature (Birkhoff 1957; Franklin–Lorenz 1989); Theorem 4.1 is quoted by the book without proof. To our knowledge neither Hilbert's projective metric on the positive cone, the Birkhoff–Hopf theorem, nor the convergence rate of Sinkhorn's algorithm has a machine-checked proof in Mathlib. The mission produces a reusable development of dH and Birkhoff's contraction theorem, and a certified rate and stopping rule for the most widely used optimal-transport solver.
Difficulty
Milestones 1–3 and 5–6 are finite manipulations of maxima of ratios. The central difficulty is Theorem 4.1. The obvious argument — bound (Kv)i/(Kv′)i entrywise by maxkvk/vk′ — only shows that K is non-expansive (λ≤1); it loses the strict contraction entirely. The sharp ratio (η−1)/(η+1) depends on how K acts on the two vectors jointly, which the entrywise argument does not see. The book quotes the theorem without proof, so the argument has to be supplied from Birkhoff's original paper or later expositions.
Formalization scope
Lean namespace CompOT.Sinkhorn. Indices are 0-based (Fin n, Fin m); vectors are functions Fin n → ℝ, matrices Matrix (Fin n) (Fin m) ℝ, and ⊙ and / are the pointwise operations on functions. dH, η and ∥⋅∥var use real iSup/iInf over the finite index sets. Every theorem assumes 0<n, 0<m and positive entries for K, a, b and every vector passed to dH, which excludes Lean's junk values for division by zero and logarithms of non-positive numbers. Sinkhorn's algorithm is a run predicate (IsSinkhornRun) stating the recursion (4.15) with v(0)=1m; u(0) is not an iterate and is unconstrained. The solution (u⋆,v⋆) is any positive solution of (4.14), taken as a hypothesis (it exists iff ∑iai=∑jbj); the book's histograms are probability vectors, but only positivity is used. P⋆ in (4.24) is diag(u⋆)Kdiag(v⋆), the solution of the regularized problem (4.2) by Proposition 4.3.
Deviations from the print, all disclosed in the items: the O(⋅) of (4.22) is replaced by the proof's explicit constants; the limit (u(ℓ),v(ℓ))→(u⋆,v⋆) is stated as dH→0, since scalings are determined only up to (ru,v/r); the second inequality of (4.23) is false as printed (its right side is 0 for ℓ≥1) and is stated with the half-step coupling the mirrored proof gives.
A definition of dH without the logarithm, or as a maximum of single-entry ratios, would make the statements different theorems; the definition here is the book's, and (4.21) is a milestone checking it against the variation seminorm. A run predicate not tied to K, a, b, or an unsatisfiable one, is ruled out: the predicate is the recursion itself and is inhabited for every K, a, b.
Contributions welcome: the metric properties of dH (reusable for Perron–Frobenius and nonlinear consensus), a proof of the Birkhoff–Hopf theorem, and positivity lemmas for Sinkhorn iterates.
Selected references
G. Peyré, M. Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5–6):355–607, 2019. https://doi.org/10.1561/2200000073 (§4.2, pp. 431–443)
R. Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices, Annals of Mathematical Statistics 35(2):876–879, 1964. https://doi.org/10.1214/aoms/1177703591
N. Linial, A. Samorodnitsky, A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, STOC 1998. https://doi.org/10.1145/276698.276880
Wasserstein Distributionally Robust Kalman Filtering 1: Minimax MMSE Estimation over a Gaussian Wasserstein Ball Is a Finite Convex SDP with an Affine Robust EstimatorResearch Paper
Motivation
The Kalman filter estimates the hidden state of a linear system from noisy observations. At every step it solves a minimum mean square error (MMSE) estimation problem: given a joint normal distribution of a signal x and an observation y, find the estimator ψ(y) minimizing E[∥x−ψ(y)∥2]. The answer, the conditional mean, is optimal only if the model distribution is correct, and in practice the system matrices and noise covariances are estimated and misspecified.
Shafieezadeh-Abadeh, Nguyen, Kuhn and Mohajerin Esfahani (arXiv:1809.08830, NeurIPS 2018) replace the single model by a set of plausible models: all normal distributions within type-2 Wasserstein distance ρ of a nominal normal distribution. The estimator is then chosen to minimize the worst-case mean square error over this set. Their Theorem 2.5 shows that this robust estimation problem, although posed over an infinite-dimensional space of estimators and a nonconvex set of distributions, has the same value as a finite convex program over covariance matrices, and that the robust estimator is affine. Applied at every time step, this yields the Wasserstein distributionally robust Kalman filter of the paper's §4.
This mission formalizes Theorem 2.5 together with the minimax theorem (Theorem 2.3) and the lemmas of its proof.
Setting
Let n,m≥0 and d=n+m. A point of Rd is z=[x;y] with signal x∈Rn and observation y∈Rm. A symmetric matrix S∈Rd×d is partitioned as S=[SxxSyxSxySyy]. S+d (S++d) denotes the positive semidefinite (definite) matrices, A⪰B means A−B∈S+d, ⟨A,B⟩=Tr[A⊤B], and A1/2 is the positive semidefinite square root of A⪰0.
Normal distributions.Nd(c,S) is the normal distribution on Rd with mean c and covariance S∈S+d; singular S is allowed. Nd is the set of all of them.
Wasserstein distance. For distributions Q1,Q2 on Rd,
W2(Q1,Q2)=πinf(∫∥z1−z2∥2π(dz1,dz2))1/2,
the infimum ranging over all distributions π on Rd×Rd with marginals Q1 and Q2.
Ambiguity set. Fix μ=[μx;μy]∈Rd, Σ∈S++d, the nominal distribution P=Nd(μ,Σ) and a radius ρ≥0. The Wasserstein ambiguity set is
P={Q∈Nd:W2(Q,P)≤ρ}.
Robust estimation. Let L be the set of all measurable functions ψ:Rm→Rn. The distributionally robust MMSE problem is
ψ∈LinfQ∈PsupEQ[∥x−ψ(y)∥2],(2)
and a distributionally robust MMSE estimator is a ψ attaining the outer infimum. Nature's problem exchanges the two optimizations; a Q⋆∈P attaining its outer supremum is a least favorable prior.
The finite program. With σ=λmin(Σ), program (5) maximizes f(S)=Tr[Sxx−SxySyy−1Syx] over S∈S+d (with Sxx∈S+n, Syy∈S+m) subject to
Tr[S+Σ−2(Σ1/2SΣ1/2)1/2]≤ρ2,S⪰σId.
Formalization targets
Goal: Theorem 2.5 (p. 3)
The optimal value of (2) equals the optimal value of (5).
If S⋆ is optimal in (5), then
ψ⋆(y)=Sxy⋆(Syy⋆)−1(y−μy)+μx
is a distributionally robust MMSE estimator.
3. For the same S⋆, Q⋆=Nd(μ,S⋆) lies in P and is a least favorable prior.
Existence and uniqueness of an optimal S⋆ are not part of the statement.
Milestones, in the order of the proof
Proposition 2.2 (Gelbrich formula): for Σ1,Σ2⪰0,
Lemma A.2: the maximizer of ⟨S,D⟩ under the Wasserstein-type trace constraint, and S⋆⪰σId.
(A.6): for S≻0, minG⟨[In−G⊤−GG⊤G],S⟩=f(S), uniquely at G⋆=SxySyy−1.
Significance
The result. Theorem 2.5 gives the robust estimator in closed form from one optimal covariance matrix, and identifies the least favorable distribution as a normal distribution with the nominal mean. Together with Theorem 2.3 it shows that the pair (ψ⋆,Q⋆) is a saddle point: the robust estimator is the Bayesian estimator for the least favorable prior. For ρ=0 the program has the single feasible point Σ and the estimator reduces to the classical conditional mean, so the theorem contains the Kalman update as a special case. The finite program is what makes the robust filter of §4 computable; the paper's §3 (formalized in the companion mission of this series) solves it with a Frank–Wolfe method.
Formalizing it. The result is proved in the paper; nothing here is open. No part of it is machine-checked yet. The Gelbrich formula for normal distributions (Proposition 2.2) is cited from the literature and has no formal proof in Mathlib; neither does Lemma A.1, cited from earlier work of the same authors. A closely related statement for a Wasserstein ball over all distributions around an elliptical nominal (Kuhn et al. 2019, Theorem 25) is posed on the platform as WassersteinDRO.Shrinkage.distributionally_robust_mmse_estimator; it is a different theorem, since the ambiguity set there is convex and contains non-normal distributions.
Difficulty
The ambiguity set P is not convex, because a mixture of normal distributions is generally not normal. The standard route to a minimax equality, Sion's theorem, needs convexity on nature's side and therefore does not apply to (2) directly; the obvious attempt to interchange the infimum and the supremum fails at this step. The space L of measurable estimators is infinite-dimensional, and the Wasserstein constraint is an infimum over couplings, so a proof must pass to finite-dimensional descriptions on both sides (means and covariances for Q, affine maps for ψ) and justify each passage. The matrix-analytic parts involve the nonlinear map S↦(Σ1/2SΣ1/2)1/2, for which Mathlib has square roots but little calculus.
Formalization scope
Rd is EuclideanSpace ℝ (Fin n ⊕ Fin m); the Sum.inl coordinates are x, the Sum.inr coordinates are y, and the blocks of a matrix are toBlocks₁₁, toBlocks₁₂, toBlocks₂₁, toBlocks₂₂.
Nd(c,S) is Mathlib's multivariateGaussian c S with S.PosSemidef; only the nominal Σ is required to be positive definite.
W2 is the published coupling-based WassersteinDRO.Shrinkage.wassersteinDistance 2 in [0,∞]. The ambiguity set is defined through it, not through the Gelbrich formula; the formula is Proposition 2.2, a milestone.
Expectations are lower Lebesgue integrals in [0,∞], with no integrability guard. A non-integrable estimator therefore has infinite risk and cannot lower the infimum through a junk value.
The values of (2) and of nature's problem are in [0,∞]; the value of (5) is the published sdpValue in EReal, and the two are compared through the coercion.
σ is passed as a real number that is the least eigenvalue of Σ.
"Equivalent" in Theorem 2.5 is read as the three claims above. A version that asserts only equality of values, or optimality of ψ⋆ among affine estimators only, is weaker than the theorem and is not the goal.
Lemma A.2 carries the added hypothesis ρ>0, without which its algebraic equation has no admissible root.
A complete development needs the Gelbrich formula for (possibly degenerate) normal distributions, conditional means of jointly normal vectors, a minimax theorem for convex–concave functions on compact sets, Lagrangian duality for a convex semidefinite program, and calculus of the positive semidefinite square root. The first three are reusable well beyond this mission, and contributions of any of them as separate results are welcome.
Selected references
S. Shafieezadeh-Abadeh, V. A. Nguyen, D. Kuhn, P. Mohajerin Esfahani, Wasserstein Distributionally Robust Kalman Filtering, NeurIPS 2018; arXiv:1809.08830v3. https://arxiv.org/abs/1809.08830
M. Gelbrich, On a formula for the L² Wasserstein metric between measures on Euclidean and Hilbert spaces, Mathematische Nachrichten 147, 1990. https://doi.org/10.1002/mana.19901470121
V. A. Nguyen, D. Kuhn, P. Mohajerin Esfahani, Distributionally robust inverse covariance estimation, arXiv:1802.01981, 2018. https://arxiv.org/abs/1802.01981
D. Kuhn, P. Mohajerin Esfahani, V. A. Nguyen, S. Shafieezadeh-Abadeh, Wasserstein distributionally robust optimization: theory and applications in machine learning, INFORMS TutORials, 2019; arXiv:1908.08729. https://arxiv.org/abs/1908.08729
D. P. Bertsekas, Convex Optimization Theory, Athena Scientific, 2009.
Wasserstein Distributionally Robust Kalman Filtering 2: The Bisection Algorithm Returns a Feasible, ε-Suboptimal Solution of the Frank–Wolfe Direction-Finding SubproblemResearch Paper
Motivation
A Kalman filter estimates the hidden state x of a linear system from observations y, assuming the joint law of z=(x,y) is a known Gaussian. When that law is only approximately known, Shafieezadeh-Abadeh, Nguyen, Kuhn and Mohajerin Esfahani (arXiv:1809.08830v3, NeurIPS 2018) replace it by the worst Gaussian within a 2-Wasserstein ball of radius ρ around a nominal Gaussian with covariance Σ. Their Theorem 2.5 shows that the resulting minimax estimation problem is equivalent to a finite nonlinear semidefinite program, program (5), whose objective is f(S)=Tr[Sxx−SxySyy−1Syx].
Each step of the robust filter solves program (5), so the filter is only practical if (5) can be solved quickly. The paper solves it with a Frank–Wolfe method (Algorithm 2), which avoids projections by replacing the objective with its linearization at the current iterate and maximizing that linear function over the original feasible set. That inner problem, the direction-finding subproblem, is again a nonlinear SDP. The paper's Algorithm 1 solves it by a one-dimensional bisection, and Theorem 3.2 states that this bisection returns a feasible solution whose objective value is within a prescribed tolerance ε of the optimum. This mission formalizes that guarantee.
Setting
Fix dimensions n≥1 (state) and m (observation), d=n+m, and index coordinates so that the first n belong to x. Let S+d and S++d denote the positive semidefinite and positive definite d×d matrices, and ⟨A,B⟩=Tr[A⊤B] the trace inner product. The data are a nominal covariance Σ∈S++d with smallest eigenvalue σ=λmin(Σ), a radius ρ>0, a tolerance ε>0, and the current Frank–Wolfe iterate S∈S+d, written in blocks Sxx,Sxy,Syx,Syy.
The gradient matrix is
D=∇f(S)=[In,−G]⊤[In,−G],G=SxySyy−1,
which is positive semidefinite and nonzero. The direction-finding subproblem (7b) is
L⪰σIdmax⟨L,D⟩s.t.Tr[L+Σ−2(Σ1/2LΣ1/2)1/2]≤ρ2;
its constraint says that the Gaussian with covariance L lies within Wasserstein distance ρ of the nominal Gaussian, and F denotes its feasible set. For γ with γId≻D the paper defines
Algorithm 1 takes the largest eigenvalue λ1 of D and a unit eigenvector v1, and starts from the bracket [LB,UB]=[γmin,γmax] with
γmin=λ1(1+v1⊤Σv1/ρ),γmax=λ1(1+Tr[Σ]/ρ).
Each pass sets γ=(UB+LB)/2 and L=L(γ), replaces LB by γ if h(γ)<0 and UB by γ otherwise, and the loop exits with output L as soon as h(γ)>0 and Δ(γ)<ε.
Formalization targets
Goal: Theorem 3.2
For all inputs as above:
Soundness. At every pass k whose exit test holds, with trial point γk,
L(γk)∈Fand⟨L′,D⟩≤⟨L(γk),D⟩+ε for all L′∈F.
Termination. If h has no zero at a dyadic point γmin+j(γmax−γmin)/2k, 0<j≤2k, then some pass satisfies the exit test.
The termination hypothesis is a correction: the printed theorem asserts that the algorithm outputs a solution, but if a trial point (or γmax) coincides exactly with the root of h, the upper end of the bracket becomes that root, all later trial points have h<0, and the loop never exits. Soundness holds unconditionally. The normalization ∥v1∥=1 is also added; the page says only "an eigenvector", and γmin is not a lower bound for a rescaled one.
Milestones (App. A.3, p. 13, in the order the proof uses them)
L(γ)∈F whenever γId≻D and h(γ)>0.
Weak duality: ⟨L′,D⟩≤γ(ρ2−Tr[Σ])+γ2⟨(γId−D)−1,Σ⟩ for all L′∈F and γ≥0 with γId≻D.
The suboptimality display: if h(γ⋆)=0 then ⟨L(γ⋆)−L(γ),D⟩≤γ(ρ2−Tr[Σ])+γ2⟨(γId−D)−1,Σ⟩−⟨L(γ),D⟩.
Lemma A.3: every root γ⋆ of h with γ⋆Id≻D lies in [γmin,γmax].
Significance
Theorem 3.2 is what makes Algorithm 1 a valid linear-maximization oracle for the Frank–Wolfe method on program (5): the convergence analysis of Frank–Wolfe with inexact oracles requires exactly a feasible point whose linearized objective is within a known tolerance of the optimum. It also shows that the inner problem, a semidefinite program with a matrix square root in the constraint, reduces to a scalar root-finding problem once D is diagonalized, which is why the robust filter runs at a cost comparable to an eigendecomposition per step.
The result is proved in the paper; no machine-checked version exists. The formal version adds what the paper leaves implicit: the termination edge case, the normalization of v1, and the requirement D=0 (here n≥1). The milestone statements on Lagrangian weak duality for the Wasserstein–Gaussian trust region and on the location of the multiplier are reusable for other covariance-robust programs of the same shape, such as Wasserstein shrinkage estimation.
Difficulty
The algorithm is elementary; the analysis is not. Feasibility of L(γ) requires computing the matrix square root (Σ1/2L(γ)Σ1/2)1/2 in closed form and comparing eigenvalues of non-commuting products to obtain L(γ)⪰σId. The dual bound is a semidefinite Lagrangian duality statement over a constraint involving a matrix square root, whose inner supremum (Lemma A.1, cited from earlier work) must be evaluated in closed form. Termination needs monotonicity and continuity of h on (λ1,∞) and a careful account of which side of the root each bisection update lands on; the obvious invariant "the root stays strictly inside the bracket" fails precisely in the excluded dyadic case.
Formalization scope
Matrices are indexed by Fin n ⊕ Fin m with blocks toBlocks₁₁ (xx), toBlocks₁₂ (xy), toBlocks₂₂ (yy). The feasible set F is the published definition WassersteinDRO.Shrinkage.sdpFeasibleSet ρ Σ σ, which uses the published positive semidefinite square root psdSqrt. Mathlib's matrix inverse returns 0 on singular matrices; every statement involving h, L or Δ assumes γId≻D or works at trial points that lie above λ1, and Syy−1 is allowed to be this junk value because the theorem admits any S∈S+d (then D=diag(In,0)). The constants σ and λ1 are passed as reals together with hypotheses that pin them to the smallest eigenvalue of Σ and the largest eigenvalue of D. The algorithm is modelled as its sequence of passes, not as a function returning an output, so a non-terminating run cannot silently produce a value.
A formalization that defines the output with a fuel bound or a default value, that states only optimality of L(γ⋆) at the exact root, or that assumes termination as a hypothesis would not be Theorem 3.2; ε-suboptimality is stated against every feasible point, not against a supremum that could be a junk value.
A complete development needs the spectral theorem for symmetric matrices, uniqueness of the positive semidefinite square root, and semidefinite Lagrangian duality; Mathlib supplies the first two. Proofs of the milestones are welcome contributions.
Selected references
S. Shafieezadeh-Abadeh, V. A. Nguyen, D. Kuhn, P. Mohajerin Esfahani, Wasserstein Distributionally Robust Kalman Filtering, NeurIPS 2018; arXiv:1809.08830v3. https://arxiv.org/abs/1809.08830
V. A. Nguyen, D. Kuhn, P. Mohajerin Esfahani, Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator, Optimization Online, 2018; arXiv:1805.07194 (reference [18] of the paper; source of Lemma A.1). https://arxiv.org/abs/1805.07194
M. Jaggi, Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization, ICML 2013 (reference [13]; Frank–Wolfe with approximate oracles). https://proceedings.mlr.press/v28/jaggi13.html
Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 1: For α > 3 Every Trajectory of ẍ + (α/t)ẋ + ∇Φ(x) = 0 Converges Weakly to a Minimizer of ΦResearch Paper
Motivation
Nesterov's accelerated gradient method and its proximal variant FISTA minimize a smooth convex function with a value gap of order O(1/k2) after k iterations, against O(1/k) for plain gradient descent. They are among the most widely used first-order methods in large-scale optimization, signal processing and machine learning. Su, Boyd and Candès (JMLR 2016) observed that, for α=3, the second-order differential equation
x¨(t)+tαx˙(t)+∇Φ(x(t))=0(1)
is a continuous-time limit of Nesterov's scheme, and proved Φ(x(t))−minΦ=O(1/t2) for α≥3. A rate on the values says nothing about the trajectory itself: whether x(t) (or the iterates xk) converges at all was a long-standing question. The paper of Attouch, Chbani, Peypouquet and Redont answers it for α>3: every trajectory of (1) converges weakly to a minimizer of Φ.
Timeline:
1983 — Nesterov introduces the accelerated gradient method with an O(1/k2) rate on the values.
2000 — Alvarez proves weak convergence of the trajectories of the heavy ball with friction, x¨+γx˙+∇Φ(x)=0, whose damping is constant (SIAM J. Control Optim. 38).
2009 — Beck and Teboulle extend it to composite problems (FISTA), still with a rate on the values only.
2014–2016 — Su, Boyd, Candès identify (1) as the continuous model of Nesterov's method and prove the O(1/t2) rate for α≥3.
2015 — Attouch, Chbani, Peypouquet, Redont prove weak convergence of the trajectories of (1) for α>3 (this mission), and of the iterates of the corresponding algorithms; Chambolle and Dossal obtain the discrete result independently. The case α=3 remains open.
Setting
Let H be a real Hilbert space with inner product ⟨⋅,⋅⟩ and norm ∥⋅∥, and let Φ:H→R be a continuously differentiable convex function with gradient ∇Φ. Fix a damping parameter α>0 and an initial time t0>0. A solution of (1) on [t0,+∞[ is a pair of maps x,v from the time axis to H such that, at every t≥t0, x has derivative v(t) and v has derivative −tαv(t)−∇Φ(x(t)). So v=x˙, and x¨ satisfies (1). The damping coefficient α/t is singular at 0 and vanishes as t→+∞; this is why the time origin is positive.
Three functions of time measure the progress of a solution:
the global energyW(t)=21∥x˙(t)∥2+Φ(x(t));
the anchored distancehz(t)=21∥x(t)−z∥2 to a point z∈H;
when Φ has a minimizer x∗, the anchored energies, for λ,ξ≥0,
x(t)converges weakly to xˉ as t→+∞ if ⟨x(t),y⟩→⟨xˉ,y⟩ for every y∈H. A weak limit point of x(t) is the weak limit of a sequence x(sn) with sn→+∞. argminΦ is the set of minimizers of Φ.
Formalization targets
Goal: Theorem 2.16
If argminΦ=∅ and α>3, then for every solution x of (1) there is xˉ∈argminΦ with
x(t)⇀xˉ(t→+∞).
The goal asserts only the qualitative conclusion; no rate or constant enters it.
Milestones
Lemma 2.1 (energy dissipation): W˙(t)=−tα∥x˙(t)∥2 for t>t0; W is nonincreasing with a limit in R∪{−∞}, finite when Φ is bounded below.
(7): h¨z(t)+tαh˙z(t)+Φ(x(t))−Φ(z)≤∥x˙(t)∥2.
Lemma 2.2: ∫t0ts1(W(s)−Φ(z))ds≤C−t1h˙z(t)−2α3W(t) with an explicit constant C.
Theorem 2.3 i), ii) (minimizing property, every α>0): limW(t)=limΦ(x(t))=infΦ∈R∪{−∞}, and every weak limit point of x(t) is a minimizer.
Remark 2.6: the Lyapunov inequality for dtdEλ,ξ, and monotonicity of Eλ,λ(α−λ−1) for α≥3, 2≤λ≤α−1.
Theorem 2.14 ii) with (13), (15): for α>3, ∥x(t)−x∗∥2≤E2,2(α−3)(t0)/(α−3) and ∫t0∞t∥x˙(t)∥2dt≤E2,2(α−3)(t0)/(α−3).
Lemma A.4: if tw¨+αw˙≤g a.e. with α>1, g≥0 integrable and w bounded below, then [w˙]+ is integrable and limw(t) exists.
Lemma A.2 (Opial's lemma, continuous form).
Significance
The result. Theorem 2.16 is the first proof that the trajectories of the continuous Nesterov model converge, not only their values. The paper's discrete analysis parallels the continuous one and yields weak convergence of the iterates of Nesterov-type forward–backward algorithms for α>3 (Theorem 5.3, a companion mission). The minimizing property (Theorem 2.3) holds for every α>0, with no minimizer assumed, and shows that a bounded trajectory exists only if Φ has a minimizer. Strong convergence results under further geometric assumptions (Theorems 3.1–3.3) build directly on Theorem 2.16.
Formalizing it. All statements are proved on paper. None of them, nor the differential equation (1), is formalized on Prove2Me or in Mathlib; the discrete analogue (weak convergence of the unperturbed accelerated forward–backward iterates) exists on the platform as a separate result. A formal development provides: a reusable encoding of solutions of a non-autonomous second-order ODE in a Hilbert space; Lyapunov arguments with one-sided derivatives on a half-line; a continuous-time Opial lemma, which is the standard tool for weak convergence of evolution equations and of semigroups; and the scalar differential-inequality lemma A.4.
Difficulty
Lyapunov functions such as W or Eα−1,0 give rates on the values but not convergence of x(t): a decreasing energy says nothing about where the trajectory goes, and the minimizer set may be a continuum. The natural first idea, showing that ∥x(t)−x∗∥ is eventually monotone as for the gradient flow, fails: the inertial term makes hx∗ oscillate, and (7) controls only th¨+αh˙, a second-order quantity. Making it usable requires integrability of t∥x˙(t)∥2 on [t0,+∞[, which is not available from the Su–Boyd–Candès energy and holds only for α>3; the borderline α=3 is open. In infinite dimension, convergence is genuinely weak: bounded sets are not compact, so the argument must identify weak limit points through weak lower semicontinuity of Φ and conclude through Opial's lemma.
Formalization scope
Space.H is a real inner product space that is complete (InnerProductSpace ℝ H, CompleteSpace H); no finite dimension is assumed, since in finite dimension weak and norm convergence coincide.
Potential.Φ:H→R with ConvexOn ℝ Set.univ Φ and ContDiff ℝ 1 Φ; ∇Φ is Mathlib's gradient. Minimizers are points z with Φ(z)≤Φ(y) for all y; minΦ is written Φ(x∗) for such a point.
Solutions. (1) is the first-order system x˙=v, v˙=−tαv−∇Φ(x), with derivatives within [t0,+∞[ at every t≥t0 and t0>0. Existence of solutions is not assumed or proved: every statement concerns a given solution, as in the paper.
Limits and integrals. Limits in R∪{−∞} are taken in EReal, infΦ as an EReal infimum. Improper integrals ∫t0+∞ carry an explicit integrability conjunct; integrals over [t0,t] are interval integrals of continuous functions.
Explicit constants. The constant C of Lemma 2.2 and the bounds E2,2(α−3)(t0)/(α−3) of (13), (15) are stated exactly as the paper computes them.
Trivializations ruled out. Weak convergence is not replaced by norm convergence, the derivative relations between x, v and their energies are part of the hypotheses or conclusions (never a free deriv), and the solution predicate is non-vacuous: the constant trajectory for Φ=0 and the explicit solution x(t)=t2 of Example 2.5 satisfy it.
Citation. Theorem numbers and pages refer to the Optimization Online preprint 5179 (October 2015), titled "…asymptotic vanishing damping", not to the Mathematical Programming typesetting.
Contributions of reusable infrastructure are welcome, in particular a continuous-time Opial lemma, weak lower semicontinuity of continuous convex functions on a Hilbert space along weakly convergent sequences, and integration-by-parts lemmas for one-sided derivatives on a half-line.
W. Su, S. Boyd, E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: theory and insights, Journal of Machine Learning Research 17 (2016) 1–43. https://jmlr.org/papers/v17/15-084.html
F. Alvarez, On the minimizing property of a second order dissipative system in Hilbert spaces, SIAM Journal on Control and Optimization 38 (2000) 1102–1119. https://doi.org/10.1137/S0363012998335802
A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences 2 (2009) 183–202. https://doi.org/10.1137/080716542
A. Chambolle, Ch. Dossal, On the convergence of the iterates of the "fast iterative shrinkage/thresholding algorithm", Journal of Optimization Theory and Applications 166 (2015) 968–982. https://doi.org/10.1007/s10957-015-0746-4