ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let f(cdot)f(cdot) be a monotone test function, let h(f)h(f) denote the corresponding function appearing in the sample-complexity bounds, and let Γ(q)\Gamma(q) denote the corresponding quantity optimized over q∈(0,1)q\in(0,1). In the sparse regime with d=nθd=n^\theta and 0≤θ<10\leq\theta<1, the sample-complexity bounds are expressed in terms of these quantities.

Sample-complexity conjecture. For any monotone test function f(⋅)f(\cdot),

min⁡q∈(0,1)Γ(q)h(f)dlog⁡n∈Θ(1).\frac{\min_{q\in(0,1)}\Gamma(q)}{h(f)d\log n}\in\Theta(1).

A positive resolution would tightly characterize the order-wise sample complexity for every monotone test function, extending the order-wise tightness already established for noisy test functions. The supplied text does not indicate whether this conjecture has been resolved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.