G.2, display after (G.16), p. 50 (corrected: the claim that f is decreasing is omitted) — f(x) < 2 for large x, and m ≥ 2x(log x)² ⇒ m/(log m)² ≥ x
ProvedOfflineCMC.Minimax.log_sq_stepp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1real-analysissample-complexity
Let
Then:
- there is a constant such that for every ;
- there is a constant such that for every and every real ,
In the proof of Theorem 2 this is applied with and . It turns a sample size of order into the inequality that the Bernstein bound of Proposition 3 needs.
Differences from the source:
- correction: "This is obviously decreasing in " → not stated; reason: false. With , the derivative of is , which is positive for , i.e. for . The claim is not used.
- generalization: → every , for every ; reason: at this is the page's display with . It extends to larger because is increasing for .
Preamble
import Mathlib
Formal statement
namespace OfflineCMC.Minimax
theorem log_sq_step :
(∃ c : ℝ, ∀ x : ℝ, c < x →
(1 + Real.log 2 / Real.log x + 2 * (Real.log (Real.log x) / Real.log x)) ^ 2 < 2) ∧
∃ c : ℝ, 1 < c ∧ ∀ x : ℝ, c < x → ∀ m : ℝ, 2 * x * Real.log x ^ 2 ≤ m →
x ≤ m / Real.log m ^ 2 := by sorry
end OfflineCMC.Minimax
Source
Banerjee, Honnappa & Rao, Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity, arXiv:2211.07092v5, p. 50, App. G.2, display after (G.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.