Simultaneous deterministic selection of error and cost budgets
ProvedNarrowDNF.Weighted.select_two_budgetscombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Let be nonempty and finite with strictly positive normalized weights . Let , and assume and , where . For every ,
The conclusion includes . It chooses one realization controlling both the approximation error and the active-set cost, instead of selecting these two quantities separately.
Preamble
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Real.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
import Theorems.Thm_NarrowDNF_Weighted_exists_le_mean
namespace NarrowDNF
end NarrowDNF
namespace NarrowDNF.Weighted
end NarrowDNF.Weighted
open NarrowDNF
open NarrowDNF
open NarrowDNF.Weighted
open scoped BigOperators
variable {α : Type*} [Fintype α]
Formal statement
theorem NarrowDNF.Weighted.select_two_budgets [Nonempty α] (weights : α → ℝ)
(hw : ∀ x, 0 < weights x) (hs : ∑ x, weights x = 1)
(err cost : α → ℝ) (herr : ∀ x, 0 ≤ err x) (hcost : ∀ x, 0 ≤ cost x)
(e B τ : ℝ) (hB : 0 ≤ B) (hτ : 0 < τ)
(he : (∑ x, weights x * err x) ≤ e)
(hM : (∑ x, weights x * cost x) ≤ B) :
∃ x, err x ≤ e + τ ∧ cost x ≤ B * (1 + e / τ) := by sorrySource