How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The D-equivalence violation bounds the finite-budget design's log-determinant gap
Statement
Let be a finite nonempty candidate set, let , and let be any returned nonsingular approximate design from Finite-budget multiplicative update for approximate D-optimal design. Put and Then , every nonsingular approximate competitor satisfies and if and only if is D-optimal among nonsingular approximate designs.
Facts & Assumptions
Given: A finite candidate set , feature vectors , , and a nonsingular approximate design returned by the stated algorithm.
Finite-budget multiplicative update for approximate D-optimal design: , the finite sensitivity is , and the returned violation is .
Approximate designs and linear-model optimality criteria: approximate design weights are nonnegative and sum to one; nonsingular means is positive definite; D-optimality maximizes over nonsingular designs.
The log determinant is concave on positive-definite matrices: is concave along every segment of positive-definite matrices.
The determinant differential is at every matrix, and Jacobi's formula holds on the invertible locus, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, and The chain rule for total derivatives: : along an invertible differentiable matrix path , .
The trace as the sum of the diagonal entries and Rectangular matrix multiplication and the identity matrix , including zero-sized shapes: trace is the sum of diagonal entries and matrix products are the finite coordinate products.
Equivalence criterion for D-optimal approximate designs: a nonsingular approximate design is D-optimal exactly when for every candidate .
Proof
By [F1] and [F5], The first rank-one trace identity follows by expanding the diagonal sum: . Since the are nonnegative and sum to one, their weighted average of the is at most their maximum. The displayed equality therefore gives and .
Let be any nonsingular approximate competitor and put and . The segment is positive definite because for each nonzero , . Define . By [F3], is concave, and [F4] gives . For , concavity gives , hence . Letting and using the right derivative proves .
Expand and . By the rank-one trace identity proved in step 1.1, and . Since is an approximate design, . Thus step 1.2 yields .
If , then for every , so [F6] makes D-optimal. Conversely, if is D-optimal, [F6] gives for every ; step 1.1 says their -weighted average equals , so their maximum is exactly and . This proves both directions.
Depends on
- Finite-budget multiplicative update for approximate D-optimal design
- Finite-budget multiplicative design updates preserve the simplex and nonsingularity
- Approximate designs and linear-model optimality criteria
- Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes
- The trace $\operatorname{tr}(A)$ as the sum of the diagonal entries
- The log determinant is concave on positive-definite matrices
- The determinant differential is $D\det(A)[H]=\operatorname{tr}(\operatorname{adj}(A)H)$ at every matrix, and Jacobi's formula holds on the invertible locus
- The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t
- The chain rule for total derivatives: $D(g\circ f)(a)=Dg(f(a))\circ Df(a)$
- Equivalence criterion for D-optimal approximate designs
Used by
Dependency tree · two levels
47 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization, §§3.1.5 and 7.5.2 (standard reference, not scraped)
- Holger Dette, Andrey Pepelyshev, and Anatoly Zhigljavsky, Improving Updating Rules in Multiplicative Algorithms for Computing D-optimal Designs, §§1–2 (standard reference, not scraped)