Unnumbered closeness of optimal empirical and population losses
OpenQAlgorithms.Papers.Independent.Support50.P30.optimalLoss_generalizationUse the bounded measurable loss and i.i.d. sampling assumptions of Theorem 4 with . Fix the same nonempty class of commuting unitaries for both risks, and define and . There is a universal such that for , and a positive integer sample budget with ,
Both risk sets are nonempty and bounded by the weight and observable bounds. This compares infima and does not require that an optimizer exists.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30
noncomputable section
open MeasureTheory
open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal
namespace QAlgorithms.Papers.Independent.Support50.P30
/-- PDF p.7: infima over the same nonempty class. The explicit weight and
observable bounds keep both sets of risk values bounded. -/
theorem optimalLoss_generalization :
∃ C : ℝ, 0 < C ∧ ∀ (n M : ℕ), 2 ≤ n → 1 ≤ M →
∀ (epsilon deltaConf : ℝ), 0 < epsilon → epsilon < 1 →
0 < deltaConf → deltaConf < 1 →
C * (((n + 3).choose 3 : ℝ) + Real.log (1 / deltaConf)) / epsilon ^ 2 ≤ (M : ℝ) →
∀ (P : Measure (QnnDensity n)), IsProbabilityMeasure P →
∀ (a : QnnDensity n → ℝ), Measurable a → (∀ rho, |a rho| ≤ 1) →
∀ (O : QnnOperator n), O.IsHermitian → PermutationEquivariant O → specNorm O ≤ 1 →
∀ V : Set (QnnOperator n), V.Nonempty → V ⊆ unitaryFamily n →
(Measure.pi (fun _ : Fin M => P))
{xs | |sInf (Set.range (fun U : V => empiricalRisk a O U.val xs)) -
sInf (Set.range (fun U : V => qnnPopulationRisk P a O U.val))| ≤ epsilon} ≥
ENNReal.ofReal (1 - deltaConf) := by sorry
end QAlgorithms.Papers.Independent.Support50.P30
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a real constant with the following property. For every pair of natural numbers and , and every satisfying
let be the space of positive semidefinite complex matrices of trace indexed by the -bit strings, equipped with its Borel measurable structure. For every probability measure on , every measurable function satisfying for every , every Hermitian matrix with Euclidean operator norm at most that commutes with every permutation of the qubits, and every nonempty set of unitary matrices that also commute with every qubit permutation, define
Here a permutation of acts on basis vectors by . Under the product measure , the set of samples satisfying
has measure at least . The two optimization quantities are infima; their attainment is not assumed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.