A Complexity Measure for Active Learning in Multi-group Mean Estimation

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

A Complexity Measure for Active Learning in Multi-group Mean Estimation

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

A Complexity Measure for Active Learning in Multi-group Mean Estimation Abdellah Aznag

Rachel Cummings

Adam N. Elmachtoub

Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University Emails: {aa4693, rc2239, ae2516}@columbia.edu

arXiv:2606.14690v1 [cs.LG] 12 Jun 2026

We study a max-risk objective for active learning in a multi-group mean estimation d-armed bandits: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case uncertainty index maxk∈[d] σk2 /nk , where σk is the standard deviation of the distribution of arm d, and nk is the number of times arm d is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a budget term, a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the Variance Local Curvature (VLC), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the VLC is a reparametrization of a variance–Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound (Aznag et al. 2025) shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced ℓ1 geometry on the decision space, and a representationbased instance generator that reduces hard-instance construction to an explicit random matrix calculation. Key words : Active learning, multi-armed bandits, information-theoretic lower bounds, non-additive regrets.

Introduction

Active learning studies sequential sampling rules that choose where to collect the next observation under budget constraints. This differs from classical estimation, where data are often treated as given. In this paper, we are concerned with settings where the key decision is where to sample from next. This setting appears in online experimentation, clinical trials, and any application where we estimate group-level quantities under a shared budget and want a controlled, balanced estimation noise. While a substantial literature designs high-performing adaptive policies for these problems, far less is known about the fundamental performance limits they face. Model. We consider a multi-armed bandit setting where the goal is to actively learn the means of the arms’ distributions, and where accuracy is measured by the uncertainty index per-arm σ 2 /n. Fix a hypothesis class H of distributions on R with finite variance. An instance is a d-tuple of distributions D = (D1 , . . . , Dd ) ∈ Hd , where each Dk has mean µk and standard deviation σ(Dk ) > 0. We write σ(D) := (σ1 (D), . . . , σd (D)) ∈ Rd+ , where σk (D) := σ(Dk ). 1

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

The class H is known, but the instance D (and hence σ(D)) is unknown. For a fixed, known horizon T , a (possibly adaptive) policy π sequentially chooses arms A1 , . . . , AT ∈ [d] and observes the corresponding samples. Let nk :=

T X

1{At = k }

(k ∈ [d])

t=1

be the terminal number of pulls of arm k, and write n := (n1 , . . . , nd ). The terminal risk is σk2 , k∈[d] nk

R(n; σ) := max and the corresponding optimal benchmark risk is R⋆ (σ) :=

min R(n; σ) =

n∈Rd +: P k nk =T

∥σ ∥22 . T

(1.1)

Remark 1.1 (Confidence-interval representation). Each per-arm index σk2 /nk is (up to a constant) the squared width of a confidence interval for the mean µk built from the nk samples of arm k. The risk R(n; σ) = maxk∈[d] σk2 /nk is therefore the widest such interval across arms, and minimizing it amounts to controlling the worst-estimated mean rather than the best one. We measure performance by normalized regret, defined for a policy π and instance D ∈ Hd as R(n; σ(D)) Regret(π, D) := En∼(π,D) −1 , (1.2) R⋆ (σ(D)) where the randomness is induced by the policy π and the samples drawn from D through the random counts n. We study information-theoretic lower bounds on the normalized regret defined in (1.2). Remark 1.2 (Effect of normalizing). We use normalized rather than standard regret because it is scale-free and captures the right asymptotics: any policy pulling every arm ∼ T times already drives the unnormalized excess risk to zero, so standard regret cannot isolate the difficulty of learning the variances. Dividing by R⋆ (σ) makes the quantity vanish only as the optimal allocation is approached. One recovers a bound on standard regret simply by multiplying the bound of Theorem 2.1 through by R⋆ (σ). Local neighborhood. Fix a base standard-deviation vector σ ∈ Rd+ and define its normalized variance profile

σ ⊙2 ∈ ∆d . ∥σ ∥22 N (σ) is scale-free and encodes the optimal normalized allocation that yields R∗ (σ). For ρ ∈ (0, 1), N (σ) :=

define the local instance class Hρ (σ) :=

n D ∈ Hd :

o N (σ(D))/N (σ) − 1 2 ≤ ρ .

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Local minimax lower bound. Since the arms are unlabeled, we restrict attention to permutationinvariant policies (i.e., policies invariant to permutations of arm labels). This is possible because any policy can be symmetrized by a random permutation of labels at time 0 without worsening worst-case regret over a permutation-closed instance class; let Πsym denote this class. Fix a radius ρ ∈ (0, 1) and a tolerance τ > 0. Define the τ -tolerant symmetric policies by n o sym sym Πρ,τ (σ) := π ∈ Π : sup Regret(π, D) ≤ τ . D∈Hρ (σ)

The tolerance τ restricts attention to policies whose worst-case normalized regret over the local class is controlled, and is primarily a proof-technical device: our lower-bound argument requires prior control on how a policy allocates its budget on Hρ (σ), and without such control the informationtheoretic reduction does not yield a non-vacuous bound. We make the precise role of τ explicit in Remark 1.3 below. In the learnable asymptotic setting, one is naturally interested in regimes where τ ↓ 0. The corresponding local minimax value is defined by Vρ,τ (σ) :=

inf sym

sup

Regret(π, D),

π∈Πρ,τ (σ) D∈Hρ (σ)

with the convention Vρ,τ (σ) = +∞ if Πsym ρ,τ = ∅. Remark 1.3 (On the role of the tolerance τ ). The tolerance does not change the local minimax value in the learnable regime. Writing τ ⋆ := inf π∈Πsym supD∈Hρ (σ) Regret(π, D) for the unconstrained value, one indeed has Vρ,τ (σ) = τ ⋆ for every τ ≥ τ ⋆ and Vρ,τ (σ) = +∞ for τ < τ ⋆ . The parameter τ instead enters through analysis: the lower bound we prove (Theorem 2.1) holds for τ -tolerant policies and carries a multiplicative penalty 1 − ϵ(ρ, τ ). Restricting to small τ (the learnable regime) sends ϵ(ρ, τ ) → 0 and makes the bound sharp, whereas imposing no restriction at all (τ = +∞) only yields the weaker penalty ϵ(ρ, +∞), which can be vacuous. Since Vρ,τ = τ ⋆ throughout the learnable regime, the resulting bound also lower bounds the unconstrained local minimax value. Benchmark and notion of sharpness. Our goal is to lower bound Vρ,τ (σ). To interpret such a lower bound, suppose that (by separate algorithmic work) one constructs a permutation-invariant policy π ⋆ with a uniform local worst-case guarantee sup

Regret(π ⋆ , D) ≤ V̄ρ (σ),

D∈Hρ (σ)

where V̄ρ (σ) is an explicit function of (T, d, σ, ρ). Then, we have by construction, V̄ρ (σ) ≥

sup

Regret(π ⋆ , D) ≥ Vρ,V̄ρ (σ) (σ).

D∈Hρ (σ)

A meaningful lower bound therefore does two things. First, it must apply at a tolerance level V̄ρ (σ) for which an admissible policy exists, i.e., Πsym (σ) ̸= ∅. Second, it should satisfy a small ρ,V̄ρ (σ)

gap between the achievable guarantee and the minimax value V

V̄ρ (σ)

ρ,V̄ρ (σ) (σ)

guarantee on this ratio implies local minimax near-optimality.

. In particular, a Õ(1)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

1.1.

Our Contributions

Conceptually, our central novelty is an information-theoretic approach of the non-additive, max-type objective defined in (1.2). Specifically, we show that its local minimax difficulty is governed by a single curvature functional, the Variance Local Curvature (VLC), rather than by tail conditions on H. Our main contributions are threefold:

1. A general local minimax lower bound framework. We introduce a local minimax formulation parameterized by a locality radius ρ and a tolerance τ , and prove a lower bound on Vρ,τ (σ) that cleanly separates budget, heteroscedasticity, and model curvature. The bound is expressed through a one-arm curvature functional VLCρ (· | H), and applies to general hypothesis classes H with finite variance (see Section 2). 2. Sharp characterization for smooth classes and a principled benchmark. For smooth classes, we relate VLCρ to a variance–Fisher information quantity via a quadratic KL expansion, yielding explicit expressions for many standard families. We then benchmark our lower bound against the strongest available general upper bound, showing that it is close in broad regimes (up to logarithmic factors) and pinpointing a systematic gap in highly heterogeneous instances. This comparison provides both a refined understanding of when current algorithms are provably near-optimal and concrete guidance on how future upper-bound analyses might be sharpened (see Section 3). 3. A principled method for generating hard instances. We develop an instance generation viewpoint for lower bounds: rather than guessing an adversarial family directly in Hd , we parameterize local hard families through a representation map. Concretely, we encode nearby decisions by a hypercube code and a linear map A, and view the adversary as choosing the full representation x 7→ Ax. The construction reduces the core lower bound problem to an explicit matrix optimization problem, which can be handled with sharp random matrix theory machinery. To the best of our knowledge, this “instance generator” viewpoint is new in this setting and may be useful on its own for other non-additive objectives (see Section 4). 1.2.

Related Work

Our setting is closely related to stochastic multi-armed bandits (MAB) (Lattimore and Szepesvári 2020) in that data are acquired by pulling arms. The lower-bound literature for classical MAB is extensive (Magureanu et al. 2014, He et al. 2022, Combes and Proutiere 2014, Cai and Scarlett 2021), and many proofs ultimately reduce to controlling the probability of confusing nearby instances via information-theoretic inequalities (e.g., Pinsker-type arguments (Yu 1997)). A key difference is that these techniques are typically tailored to bandit objectives whose regret is additive over time (cumulative regret) or has a canonical discrete structure (best-arm identification). Our objective

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

is neither: the normalized regret in (1.2) is a non-additive, max-type functional of the terminal allocation. As a result, standard MAB lower-bound templates do not apply directly and must be adapted to the loss-induced geometry of our decision problem. Early work introduced this problem for bounded feedback models, motivated in part by fairness constraints (Sarkies et al. 2015, Acemoglu et al. 2019, De Leeuw 2008). Antos et al. (2008) studied the case where H consists of bounded distributions with known support and provided an algorithm with 3 √2 , leaving open the corresponding lower bounds. Carpentier et al. (2011) proposed regret Õ σd ∥σ∥ T min

a different algorithm and analyzed additional settings for H, including sub-Gaussian distributions with a known sub-Gaussian parameter bound and Gaussian distributions; the lower-bound question remained unresolved. More recently, Aznag et al. (2023) obtained the near-optimal worst-case upper bound Õ

p d/T

for this objective and provided the first lower-bound results in the Gaussian case. In particular, they showed that a suitably normalized isotropic Gaussian instance attains regret on the order p of Ω̃ d/T , matching the worst-case upper bound up to logarithmic factors. To the best of our knowledge, these are the only existing lower bounds for the problem we are studying. Our main theorem provides a local minimax lower bound for any hypothesis class H with finite variance, expressed in terms of a one-arm information curvature VLCρ (· | H) and the variance’s heteroscedasticity. This yields a unified lower-bound framework for this problem. From a technical point of view, our work can be embedded within the information geometry literature (Nielsen 2020). Recently, information geometry (Atz et al. 2021, Boguna et al. 2021, Isert et al. 2023, Fei et al. 2025) has provided promising tools for tackling non-linearity aspects in learning problems. Our core idea, instance generation, essentially assumes that H can be embedded in a statistical manifold. This establishes a natural correspondence between the set of instances H, and a (locally) Euclidean space where calculations are more interpretable. In turn, this reduces the problem of finding a lower bound to optimizing over a (locally) Euclidean space. 1.3.

Paper Structure and Notation

Paper structure. Section 2 defines the Variance Local Curvature (VLC) and states our main local minimax lower bound (Theorem 2.1), together with its various implications. Section 3 studies the particular case when the hypothesis class H represents smooth classes. Section 4 provides a proof outline, highlighting the two core ideas (loss-induced geometry and representation-based instance generation). Proofs are deferred to the appendix. Notation. For an integer n ≥ 1, we write [n] := {1, . . . , n}. Vectors are denoted in bold, and 1 = (1, . . . , 1) ∈ Rd is the all-ones vector. For x, y ∈ Rd , ⟨x, y ⟩ denotes the Euclidean inner product and ∥x∥p the ℓp norm. We write x⊙2 for the element-wise square of x. For a vector u ∈ Rd , we write

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

u⊥ := {x ∈ Rd : ⟨x, u⟩ = 0}. For a finite set S, |S | denotes its cardinality. We use R>0 := (0, +∞) and R+ := [0, ∞). For a random variable X, we write E[X] for its expectation and Var(X) for its variance. For two distributions P, Q, KL(P ∥Q) denotes the Kullback–Leibler divergence. When we write Õ(·) (instead of O(·)), polylogarithmic factors in T are suppressed.

Variance Local Curvature and Main Theorem

Definition 1 (Variance Local Curvature). Fix (σ, ρ) ∈ R>0 × (0, 1) and define n o v2 − σ2 Bρ (σ) := v ∈ R>0 : ≤ ρ . σ2 Let Sρ (σ) denote the set of measurable selectors n o Sρ (σ) := D : Bρ (σ) → H measurable : Var(D(v)) = v 2 ∀v ∈ Bρ (σ) . √ √ Equivalently, Bρ (σ) = σ 1 − ρ, σ 1 + ρ ∩ R>0 is an interval of admissible standard deviations around σ. The ρ-Variance Local Curvature is VLCρ (σ | H) :=

inf

sup

D∈Sρ (σ) va ,v ∈Bρ (σ) b

KL(D(va ) ∥ D(vb )) ∈ R+ ∪ {+∞}, 2 2 2 va −vb σ2

(2.1)

with the convention VLCρ (σ | H) = +∞ if Sρ (σ) = ∅. Moreover, the Variance Local Curvature is defined as VLC(σ | H) := VLC0+ (σ | H) = lim sup VLCρ (σ | H). ρ→0+

Although Definition 1 optimizes over all measurable selectors, the resulting curvature is usually easy to evaluate, as it admits simple closed forms in many standard settings (see Table 1). Remark 2.1 (Examples). To build intuition for VLC, we look at the following two extremes. (i) A rich class with vanishing curvature. Let H = {(1 − ε)δ0 + εδC : ε ∈ (0, 1)} with C ≫ 0. A distribution here has variance ε(1 − ε)C 2 , so the variance can be moved by an arbitrarily small change in ε once C is large, while KL between two such distributions depends only on (ε, ε′ ) and stays bounded. Variance is thus “cheap” to change in KL, and VLC(σ | H) → 0 as C → ∞. (ii) A rigid class with curvature bounded below. Let H = {Normal(0, σ 2 ) : σ > 0} be the centered Gaussian family. By Lemma 3.1 (see the Normal row of Table 1), VLC(σ | H) = 14 for every σ > 0. 2.1.

Main Result

Our main theorem lower bounds the local minimax value Vρ,τ (σ) in terms of the one-arm complexities VLCρ (σk | H) and the heteroscedasticity of the standard deviations σ. We introduce the heteroscedasticity index, which describes how uneven the randomness is between arms. σk2 σk4 Hetk (σ) := 1− 2 2 . ∥σ ∥22 ∥σ ∥2 We are now ready to state our main theorem.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Theorem 2.1 (Local minimax lower bound). There exist universal constants C > 0 such q that for any σ ∈ Rd+ , there exists a minimal resolution ρ∗ ∝ Td such that for any τ > 0, and any ρ ≥ ρ⋆ , the local minimax value satisfies

Vρ,τ (σ) ≥ C 1 − ϵ(ρ, τ )

v u d X Hetk (σ) ∥σ ∥0 u t , T VLCρ (σk | H) k=1

where ϵ(ρ, τ ) vanishes when (ρ, τ ) → (0, 0). Our lower bound decomposes the difficulty of mean estimation into three orthogonal ingredients: a budget term, a heteroscedasticity term, and a structural term. v r u d X 1 ∥σ ∥0 u u . 1 − ϵ(ρ, τ ) · Hetk (σ) u VLCρ (σk | H) | {z } | {zT } t k=1 | {z } {z } Heteroscedasticity | Error term Budget

Model curvature

The budget contribution is standard and almost ubiquitously present in learning theory. The term ∥σ ∥0 represents the effective dimentionality of the problem. Moreover, the multiplicative correction

1 − ϵ(ρ, τ ) captures two sources of approximation: ρ controls the locality scale (finer perturbations as ρ ↓ 0), and τ restricts attention to relevant policies. In the vanishing regime ρ ↓ 0 and τ ↓ 0, this correction tends to 1. We discuss these regime conditions and their interpretation in Section 2.2. The heteroscedasticity weights Hetk (σ) describe how unevenly the randomness is spread across arms. They are scale invariant: multiplying σ by a constant does not change these weights, but redistributing mass across coordinates does. When the variances are equal (more homogeneous uncertainty), the learner must hedge broadly, since many arms can potentially dominate the max-risk objective. This is analogous to worst-case rates in learning where difficulty scales with the number of coordinates that can be simultaneously active: a diffuse signal forces exploration across many directions. By contrast, when uncertainty is concentrated on a few arms, the problem becomes effectively lower-dimensional: only a small subset can plausibly determine the maximum, and a policy can focus its budget there. In this sense, concentrated uncertainty is easier because it reduces the number of arms that must be balanced at comparable precision to control the max-risk objective; P equivalently, ∥σ ∥0 · k Hetk (σ) acts as an effective number of relevant arms. The structural term VLCρ (σk | H) measures how much information is created by a local change in variance within the model class. It is a curvature: larger VLCρ means that nearby variance levels are strongly separated in KL, so variance is easier to learn and allocation mistakes become less persistent; smaller VLCρ means the class is richer in ways that allow variance to change while producing little KL signal, making it intrinsically harder to discriminate nearby variance profiles. This mirrors familiar phenomena in statistical learning and nonparametrics: in rigid, well-specified

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

models, local parameters are easily identifiable, while in richer classes the same functional can have weaker effective curvature and require substantially more data. Here this manifests directly in the p factor 1/ VLCρ : weaker curvature enlarges the “local indistinguishability” region, forcing larger regret even when the budget and heteroscedasticity are held fixed. A more detailed discussion on the VLC for smooth classes H is deferred to Section 3. The bound in Theorem 2.1 separates the effect of the class H from the effect of the instance D. The class H enters through the operator VLC( · | H), which assigns to each variance level σ a local information curvature. The instance D influences the bound in two local ways: first through the heteroscedasticity profile Hetk (σ(D)), which quantifies how much arm k contributes to the directional uncertainty relevant for the allocation decision, and second through the evaluation of the curvature operator at the realized variance levels, VLC(σk (D) | H). Concretely, the contribution of arm k takes the form

p Hetk (σ(D)) p , VLC(σk (D) | H)

so H determines the curvature profile σ 7→ VLC(σ | H), while D determines where this profile is evaluated and how the heteroscedasticity (and thus the effective difficulty) is distributed across arms. 2.2.

Discussions

Worst-case bounds and interpolation over subclasses. For ρ ∈ (0, 1), call a distribution D ∈ H p ρ-interior if its standard deviation σ(D) = Var(D) admits a nonempty local selector set, i.e., D ∈ Hρ◦

⇐⇒

Sρ σ(D) ̸= ∅.

Given any subclass G ⊆ Hρ◦ , define its worst-case ρ−VLC by VLC⋆ρ (G | H) := inf VLCρ σ(D) | H ∈ R+ ∪ {+∞}. D∈G

Then, for each (D, . . . , D) ∈ G d , we have d X

p k=1

1 − d1 Hetk (σ · 1) ∥Het(1)∥1 =p =p . VLCρ (σ(D) | H) VLCρ (σ(D) | H) VLCρ (σ(D) | H)

Applying Theorem 2.1 and the equality above yields the worst case lower bound over the ρ−interior subclass G d ! s 1 d sup Vρ,τ σ(D) ≥ Ω (1 − ϵ(ρ, τ )) 1 − . d VLC⋆ρ (G | H)T D∈G d In particular, the bound in Theorem 2.1 is modular in the instance class, as any restriction to a subclass G ⊆ Hρ◦ simply replaces the global curvature constant by its worst-case value over G ,

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

yielding a graded family of guarantees. Finally, taking G = Hρ◦ yields a worst-case lower bound over all ρ-interior instances, i.e., ! s 1 d sup Vρ,τ σ(D) ≥ Ω (1 − ϵ(ρ, τ )) 1 − . ⋆ ◦ | H)T d VLC ( H d D∈(H◦ ) ρ ρ ρ Resolution limit and vanishing-regime. When ρ ≪

d/T , the perturbations are below the statis-

tical resolution of a horizon-T experiment with d arms, and the information-theoretic reduction used in the proof of Theorem 2.1 becomes insensitive to such fine differences. In this sense, q ⋆ d ρ =Θ T marks the natural resolution limit of our proof technique. More broadly, while the theorem statement is valid for any tolerance τ and any locality radius ρ (above feasibility), it becomes non-vacuous only in regimes where both ρ → 0 and τ → 0. Sending ρ → 0 corresponds to sending the granularity of the local discrimination problem to zero: we seek a bound that remains nontrivial even under arbitrarily fine perturbations. The tolerance τ → 0 may appear unusual, but it is conceptually natural: it restricts attention to learnable regimes in which there exists at least one policy whose worst-case normalized regret over the local class vanishes. If τ is not small, the local minimax formulation allows policies that perform poorly even on the local class, and the value Vρ,τ becomes less connected to the asymptotic learning question the lower bound is meant to capture. If D ∈ Hρ◦ , then D ∈ Hρ◦′ for every ρ′ ∈ (0, ρ), since any selector on Bρ (σ(D)) restricts to a selector on the smaller neighborhood Bρ′ (σ(D)). Motivated by this “nested balls” property, define the interior of H by H◦ :=

Hρ◦ .

ρ∈(0,1)

In the regime

d ↓ 0, τ ↓ 0, Theorem 2.1 yields a non-vacuous asymptotic lower bound for every T

interior instance. Formally, for any Dn ∈ (H◦ )dn and any sequence of (ρn , τn , Tn , dn ) satisfying ρn ≥ ρ⋆n and τn + ρn → 0, we have p

Tn /dn Vρn ,τn σ(Dn ) lim sup qP ≥ C > 0, dn Hetk (σ(Dn )) n k=1 VLCρn (σk (Dn )|H)

where C is the universal constant from Theorem 2.1. This is the sense in which the theorem provides a “true” local minimax lower bound. We emphasize that the locality radius and tolerance vanish at a rate tied to the horizon: the p bound is informative along schedules with ρT ≳ d/T and τT → 0, rather than at a single fixed

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

(ρ, τ, T ). Corollary 2.1 below specializes this to one fixed instance as T → ∞. We first record the simplest instantiation, for a fixed instance and a fixed dimension as T → ∞, before the general worst-case version. Corollary 2.1 (Fixed instance, T → ∞). Fix the dimension d and an interior instance D ∈ p (H◦ )d . For any schedule (ρT , τT ) with ρT ≥ ρ⋆T = Θ( d/T ) and τT → 0, p

T /d VρT ,τT σ(D) lim inf qP ≥ C > 0, T →∞ d Het (σ(D)) VLC(σ (D) | H ) k k k=1 where C is the universal constant of Theorem 2.1. Equivalently, for a fixed instance the local minimax p value obeys VρT ,τT (σ(D)) = Ω d/T , with the implied constant set by the heteroscedasticity and curvature of D. Corollary 2.2 (Informal). Assume the problem is learnable at rate v̄ → 0 in an asymptotic regime with d/T → 0. Then Theorem 2.1 implies the worst-case interior lower bound sup D∈(H◦ )d

VΘ√ d ,v̄ σ(D) ≥ Ω T

d 1 p T VLC(H◦ | H)

! .

VLC for Smooth Classes

This section characterizes the VLC in a smooth regime where the KL divergence admits a quadratic expansion along variance perturbations. Concretely, we show that the VLC is a reparametrization of a Fisher information type quantity. 3.1.

VLC and Fisher Information

We show that VLC can be written as a re-parametrization of the Fisher information. Our Fisher quantity is defined as the best (i.e., most favorable for minimizing KL at fixed variance level) local curvature over all realizations in H with the prescribed variance. Definition 2 (Variance-Fisher information). For a variance level θ ∈ R+ , define the variance-Fisher information at θ by IVar (θ) := 2 lim inf ∆→0

inf

P ∈H: Q∈H: Var(P )=θ Var(Q)=θ+∆

KL(Q ∥ P ) ∈ [0, +∞]. ∆2

Equivalently, IVar (θ) is the smallest quadratic KL curvature (in the variance coordinate) that can occur among all distributions in H with variance θ, allowing any nuisance features of the distribution (e.g., mean or higher moments) to vary as θ is perturbed.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Class of distributions H

Variance σ 2 IVar (σ 2 )

{Normal(µ, θ) : µ ∈ R, θ > 0}

{Laplace(µ, b) : µ ∈ R, b > 0}

2b2

1 λ2 α {Gamma(α, β) : β > 0} (fixed α > 0) 2 β {Bernoulli(p) : p ∈ (0, 1)}

VLC(σ | H)

1 2σ 4 1 4σ 4 1 4σ 4 α 4σ 4

{Exponential(λ) : λ > 0}

p(1 − p)

1 4 1 8 1 8 α 8

σ2 1 σ 2 (1 − 4σ 2 ) 2(1 − 4σ 2 )

Table 1. Examples of variance-Fisher information (minimized over H at a fixed variance level σ 2 ) and the corresponding VLC via Lemma 3.1.

Assumption 3.1 (Local quadratic KL expansion in the variance coordinate). Fix an instance D ∈ H and its variance level θ = Var(D) with 0 < IVar (θ) < ∞. Assume that for every ε > 0 there exists δε > 0 such that for all |∆| ≤ δε , I

Var (θ)

− ε ∆2 ≤

inf

Q∈H: P ∈H: Var(P )=θ Var(Q)=θ+∆

KL(Q ∥ P ) ≤

Var (θ)

+ ε ∆2 .

(3.1)

Moreover, assume the upper bound is attained (up to o(∆2 )) by a C 2 curve {Pϑ : ϑ ∈ (θ − η, θ +η)} ⊂ H with Var(Pϑ ) = ϑ. Assumption 3.1 is a standard smoothness condition: locally, the KL divergence between two nearby variance levels is quadratic in the variance increment, with curvature IVar (θ)/2 after optimizing over nuisance directions within H. Lemma 3.1 below shows that VLCρ is the corresponding scale-free curvature that appears in our minimax regret bounds. Its proof is deferred to Appendix B. Lemma 3.1 (VLC and variance-Fisher information). Under Assumption 3.1, there exists ρ0 ∈ (0, 1) such that for all ρ ∈ (0, ρ0 ), VLCρ (σ | H) =

σ4 IVar (σ 2 ) 1 + oρ (1) , 2 4

where oρ (1) → 0 as ρ ↓ 0. In particular, VLC(σ | H) = σ2 IVar (σ 2 ). In summary, in the smooth regime the difficulty of learning local variance profiles is controlled by the scalar curvature IVar (σ 2 ), and VLC provides a scale-free normalization that is directly comparable across models. In particular, whenever IVar (σ 2 ) is available in closed form, one immediately obtains an explicit formula for VLC(σ | H). Table 1 records several standard examples.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

3.2.

Distance to Optimality Under The Smoothness Assumption

Under Assumption 3.1, we benchmark Theorem 2.1 against the strongest available general upper bound, namely Theorem 4.1 of Aznag et al. (2025). This comparison shows that our guarantee is √ near-optimal (up to an O( log T ) factor) in a broad class of structured regimes, and we exhibit the discrepancies in the general case. Moreover, a side-by-side reading of the proof of Theorem 4.1 and our argument highlights the main sources of slack in the current upper-bound technique, and suggests concrete, high-level directions for sharpening it. Their bound relies on a general UCB framework, which we instantiate by constructing an explicit UCB for the variance and then invoke their regret guarantee directly. A computable UCB for the variance. Assume each arm belongs to a smooth one-parameter subfamily {Pϑ : ϑ ∈ Θ} ⊂ H. Write Var(Pϑ ) for the variance under parameter ϑ. For an arm with n samples, let ϑbn be an estimator of ϑ (e.g., the MLE) and set βt := log(T ). Define the (data-driven) upper confidence bound on the variance by likelihood-ratio inversion: n o (σn+ )2 := sup Var(Pϑ′ ) : ϑ′ ∈ Θ, n KL Pϑbn ∥ Pϑ′ ≤ βt .

(3.2)

Allocation rule (Variance-UCB). Initialize by pulling each arm once. For t > d, let nk,t be the + number of pulls of arm k up to time t, and let σk,t be the bound (3.2) computed from the samples

of arm k. At time t + 1, pull an arm maximizing + 2 (σk,t ) . k∈[d] nk,t

kt+1 ∈ arg max

Upper bound under smoothness. Under Assumption 3.1, the confidence radius induced by (3.2) has a Fisher scaling, hence a VLC scaling. Consequently, applying Theorem 4.1 in Aznag et al. (2025) implies the following upper bound ! √ d log T X σk (D) 1 √ ·p . Regret(π, D) = O T k=1 ∥σ(D)∥2 VLC(σk (D) | H) Discrepancies between the upper and lower bounds. To make the gap between the best known upper bound and our lower bound transparent, we rewrite the leading term in Theorem 4.1 of Aznag et al. (2025) in our notation. Applying Cauchy–Schwarz to the right-hand side and introducing the normalized variance weights Het+ k (σ) := we obtain

σk2 , ∥σ ∥22

v r  u d + u X log T ∥ σ ∥ Het (σ(D)) 0 t k . Regret(π, D) = O T VLC(σ k (D) | H) k=1

(3.3)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Up to polylogarithmic factors, the only mismatch between (3.3) and the lower bound in Theorem 2.1 is the appearance of Het+ in place of Het. By construction, Hetk (σ) ≤ Het+ k (σ) for every coordinate k, so the bound (3.3) may be loose precisely in regimes where this inequality is far from 2 2 tight. The key distinction is that Het+ k (σ) := σk /∥σ ∥2 is only the oracle Neyman weight: it measures

the share of total variance carried by arm k, but it does not encode how this share interacts with the rest of the instance. In contrast, our heteroscedasticity term Hetk (σ) = Het+ (σ) 1− k

σk4 ∥σ 2 ∥22

penalizes directions in which the variance profile is nearly one-dimensional: it is large only when arm k carries non-negligible variance and there remains substantial “variance-squared mass” outside coordinate k. Consequently, when the variance is reasonably spread across the active arms (no single σk4 dominates ∥σ 2 ∥22 ), the correction factor is Θ(1) and Het and Het+ are comparable (indeed they coincide up to constants in the homogeneous-on-support regime). By contrast, in spiky regimes where many arms have vanishing variance and one (or a few) arms dominate ∥σ 2 ∥2 , the factor 1 − σk4 /∥σ 2 ∥22 collapses for the dominant coordinates, driving Het (and thus the intrinsic difficulty) to 0 in the extreme case of a single nonzero variance, whereas Het+ remains order-one. This is exactly the phenomenon Het captures that Het+ misses: the directional uncertainty relevant for identifying the optimal allocation vanishes as the instance approaches the boundary of the simplex, even though the largest variance weight itself does not. This behavior is also algorithmically natural: if all but one arm are (nearly) deterministic, then after a handful of samples one can certify their variance is (close to) zero and essentially stop allocating budget to them. The remaining uncertainty is concentrated on the single noisy arm, so an optimal procedure should quickly focus its pulls there, yielding vanishing “allocation identification” regret in that boundary regime. Guidelines for sharpening future upper bounds. This comparison suggests concrete guidelines for sharpening future upper-bound analyses. First, rather than controlling each σk independently and then union-bounding over k, one should analyze the normalized variance profile (equivalently, the Neyman weight vector) and its fluctuations in directions tangent to the simplex. Moreover, one should allow confidence budgets and error metrics that are instance-weighted (e.g., weighted by λ⋆ ) rather than uniform across arms, so that arms with vanishing variance can be eliminated quickly. Currently, such refinements are not captured by the current upper bound strategies.

Proof Outline

Overview. Lower bounds are obtained by randomizing over instances that are close enough to generate nearly indistinguishable data, yet far enough that their optimal allocations differ

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

substantially, forcing any policy to make costly mistakes. While we follow this template here as well, we introduce two key ingredients that will be crucial in overcoming two separate obstacles. (i) Identifying the geometry: the first obstacle is to identify the right geometry on the set of decisions: we need a notion of distance that is compatible with the regret. In the classic multi-armed bandit setting with additive regret, one typically has RegretT =

d X

E[nk ] · ∆k = E [⟨n, ∆⟩] ,

k=1

where ∆ is the suboptimality gap vector. In particular, regret is linear in the sampling counts n, which makes separation essentially linear. In other words, the right geometry that measures between two different decisions is the euclidean geometry. In our setting, the normalized excess risk takes the max form

maxk∈[d] σk2 /nk R(n; σ) − 1 = − 1, R⋆ (σ) ∥σ ∥22 /T which is non-additive and non-linear in n, and therefore the right geometry is not euclidean. We show that the right geometry for our problem is the ℓ1 geometry: separation between decisions is measured (up to a universal constant) by ∥ · ∥1 . (ii) Identifying the adversarial instance: the second obstacle is to construct the adversarial family in a way that is both local and analyzable. In an additive objective one can often propose a simple perturbation family and check that it is hard. Here this is much less clear: the hardness depends on anisotropy coming from the instance and from the class H (through VLCρ ), so there is no single “obvious” hard direction. Our approach is therefore not to guess a hard family, but to parameterize all local hard families we care about through a representation map. Concretely, we encode nearby decisions by a hypercube code x ∈ X and a linear map A, and view the adversary as choosing the representation x 7→ Ax. This renders the lower bound calculable: the same representation controls both distinguishability (via average KL) and decision separation (via the ℓ1 geometry), and the problem reduces to a tractable matrix optimization. This viewpoint is what makes the construction interpretable and what allows us to use sharp first-order calculations to handle anisotropy in closed form. In particular, it is this viewpoint that will allow us to capture the refined heteroscedasticity that we believe is relevant to the problem. From the two ideas to the bound. Combining these ingredients gives the following pipeline, carried out in full in Appendix A. (1) We fix the decision-relevant level set (the scale-free variance profile). (2) Over this slice we select maximally indistinguishable distributions, quantified by VLCρ (· | H). (3) We re-index the resulting hard instances by nearby decisions, turning the problem into a testing problem on the decision set. (4) We embed a hypercube code X through a linear map A and lower bound the regret by a decision-mismatch (classification) cost measured in the ℓ1 geometry.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

1⊥

(σ 2 )⊥

X ⊂ {±1}d

σ2

A(X )

Figure 1. Illustration of the instance-generation process: a subset of the hypercube X ⊂ {±1}d , lying in the hyperplane 1⊥ , is transformed through a linear map A into a new set A(X ) in the hyperplane (σ 2 )⊥ . Each A(x) is identified with a generated instance D(A, x).

Conclusions

Our results characterize the local minimax difficulty of adaptive allocation in the non-degenerate regime where VLCρ (σ | H) ∈ (0, ∞) at the relevant locality scales. Two natural extensions go beyond this setting. First, the curvature VLCρ is defined through a quadratic normalization in the variance coordinate. For extremely rich classes, KL separation under local variance perturbations can be smaller than √ quadratic, in which case the quadratic curvature collapses and the canonical T scaling may no longer be the right resolution. Conversely, for classes that are too constrained, local variance neighborhoods may be infeasible or induce singular KL behavior. A refined local complexity notion that captures the correct power-law (or more general) modulus of KL with respect to variance perturbations would provide a principled way to treat both degeneracies within a single framework. Second, the proof strategy we introduce (namely, an adapted geometry for decision separation, and a representation-based instance generation for constructing hard families) should extend to other non-additive objectives on allocations, where standard bandit lower-bound templates do not apply directly. Understanding the corresponding geometries and deriving sharp performance limits in these settings is, in its own right, an interesting direction for future work.

Acknowledgments A.A. and A.E. supported in part by NSF grant IIS-2147361. R.C. supported in part by NSF grants CNS2138834 (CAREER) and IIS-2147361.

References Acemoglu D, Makhdoumi A, Malekian A, Ozdaglar A (2019) Too much data: Prices and inefficiencies in data markets. Working Paper 26296, National Bureau of Economic Research, URL http://dx.doi.org/10. 3386/w26296.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Antos A, Grover V, Szepesvári C (2008) Active learning in multi-armed bandits. 287–302, ISBN 978-3-54087986-2, URL http://dx.doi.org/10.1007/978-3-540-87987-9_25. Atz K, Grisoni F, Schneider G (2021) Geometric deep learning on molecular representations. Nature Machine Intelligence 3(12):1023–1032. Aznag A, Cummings R, Elmachtoub AN (2023) An active learning framework for multi-group mean estimation. Thirty-seventh Conference on Neural Information Processing Systems, URL https://openreview.net/ forum?id=pLcSrn8NpJ. Aznag A, Cummings R, Elmachtoub AN (2025) An active learning framework for multi-group mean estimation. URL https://arxiv.org/abs/2505.14882. Boguna M, Bonamassa I, De Domenico M, Havlin S, Krioukov D, Serrano MÁ (2021) Network geometry. Nature Reviews Physics 3(2):114–135. Cai X, Scarlett J (2021) On lower bounds for standard and robust gaussian process bandit optimization. International Conference on Machine Learning, 1216–1226 (PMLR). Carpentier A, Lazaric A, Ghavamzadeh M, Munos R, Auer P (2011) Upper-confidence-bound algorithms for active learning in multi-armed bandits. Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings 22, 189–203 (Springer). Combes R, Proutiere A (2014) Unimodal bandits: Regret lower bounds and optimal algorithms. International Conference on Machine Learning, 521–529 (PMLR). De Leeuw ED (2008) Choosing the method of data collection. . Fei Y, Liu Y, Jia C, Li Z, Wei X, Chen M (2025) A survey of geometric optimization for deep learning: From euclidean space to riemannian manifold. ACM Comput. Surv. 57(5), ISSN 0360-0300, URL http://dx.doi.org/10.1145/3708498. He J, Zhang J, Zhang RQ (2022) A reduction from linear contextual bandits lower bounds to estimations lower bounds. International Conference on Machine Learning, 8660–8677 (PMLR). Isert C, Atz K, Schneider G (2023) Structure-based drug design with geometric deep learning. Current Opinion in Structural Biology 79:102548. Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press), URL http://dx.doi. org/10.1017/9781108571401. Magureanu S, Combes R, Proutiere A (2014) Lipschitz bandits: Regret lower bound and optimal algorithms. Conference on Learning Theory, 975–999 (PMLR). Nielsen F (2020) An elementary introduction to information geometry. Entropy 22(10):1100. Sarkies MN, Bowles KA, Skinner E, Mitchell D, Haas R, Ho M, Salter K, May K, Markham D, O’Brien L, et al. (2015) Data collection methods in health services research. Applied clinical informatics 6(01):96–109. Yu B (1997) Assouad, Fano, and Le Cam, 423–435 (New York, NY: Springer New York), ISBN 978-1-46121880-7, URL http://dx.doi.org/10.1007/978-1-4612-1880-7_29.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Appendix A:

Proof Overview of Theorem 2.1

In this section, we provide the road map to derive Theorem 2.1, and defer the technical proofs for the intermediary lemmas to Appendix B. The proof builds a lower bound by designing a collection of nearby instances that strategically confuse any learning policy. The idea is to make these instances close enough to be statistically indistinguishable but not so close that misidentifying them yields negligible regret. Achieving this balance requires controlling both their scale (how far they are) and their orientation (how they are arranged). We face mainly two obstacles: Obstacle (i): geometry. The first challenge, that of scale, is addressed by introducing a problem-specific notion of distance that measures how costly it is to allocate resources incorrectly. Obstacle (ii): representation. The second challenge, that of orientation, recognizes that even when instances are at the right distance, their relative positioning still matters: rotating or reshaping them can make the problem significantly harder. To systematically optimize these two aspects, we lift the search for hard instances into a structured space of configurations and reduce the lower bound construction to an explicit optimization tradeoff over this space. This yields a principled framework that identifies the most confusing yet consequential perturbations of the original problem, establishing the desired lower bound. A.1.

Constructing the Lower Bound Framework

To establish a lower bound on the local minimax value Vρ,τ (σ), our strategy is to restrict the full, complex local class Hρ (σ) to a smaller, more tractable, and maximally challenging subset, that will be bijective to a ball inside the d−simplex ∆d . This construction proceeds in three main steps. First, we restrict attention to a decision-relevant level set to isolate the regret due to learning (rather than changes in the benchmark risk) This is Step 1. Second, over this restricted set, we select distributions that are as statistically indistinguishable as possible, a notion quantified by VLCρ (· | H). This is Step 2. Finally, we show that the resulting class of hard instances can be re-parameterized by a simple geometric set of nearby decisions, which forms the basis of the subsequent reduction to testing. This is Step 3.

Step 1: fixing the decision-relevant level set. The benchmark risk R⋆ (σ) = ∥σ∥22 /T depends only on the overall scale of σ. To separate regret due to learning from changes in the benchmark, we work on a fixed-scale slice by passing to the scale-free variance profile N (σ) :=

σ ⊙2 ∈ ∆d . ∥σ∥22

Fixing N (σ) fixes the decision-relevant profile while quotienting out global scale. For a radius ρ ∈ (0, 1), we consider instances whose normalized profile lies in a ρ-neighborhood of N (σ): H̃ρ (σ) :=

n D ∈ Hd :

N (σ(D))/N (σ) − 1 2 ≤ ρ,

o R⋆ (σ(D)) = R⋆ (σ) .

Step 2: selecting maximally indistinguishable distributions (VLC selectors). To construct a hard family over H̃ρ (σ), we must specify, for each arm k and each nearby standard deviation level vk , a distribution in H with variance vk2 . To make learning maximally difficult, we choose these distributions to be as statistically

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

similar as possible across nearby variances. This is exactly what VLCρ (σk | H) captures: it is the smallest achievable KL curvature under local variance perturbations at scale ρ. (i)

Concretely, for each arm k, let {Dk }i≥1 be a sequence of measurable selectors on Bρ (σk ) such that (i) (i) KL Dk (va ) ∥ Dk (vb ) −→ VLCρ (σk | H), i → ∞. (A.1) sup 2 2 2 va −vb

va ,vb ∈Bρ (σk )

2 σk

Given v ∈ Rd+ , define the induced d-arm instance (i) (i) D(i) (v) := D1 (v1 ), . . . , Dd (vd ) ∈ Hd .

Step 3: re-parameterizing hard instances by nearby decisions. Rather than working directly with variance vectors, we parameterize local alternatives by decisions in the simplex. Let λ⋆ := N (σ). Define the local set of decisions ∆ρ (λ⋆ ) :=

n λ ∈ ∆d :

o λ/λ⋆ − 1 2 ≤ ρ .

For each λ ∈ ∆ρ (λ⋆ ), we define a canonical representative on the same scale as σ by σ(λ) := ∥σ∥2

√ λ,

so that N (σ(λ)) = λ. For each i ≥ 1, we then define the corresponding hard instance Di (λ) := D(i) σ(λ) ∈ Hd . The next lemma formalizes the resulting correspondence: decisions in ∆ρ (λ⋆ ) index a local family of hard instances, and restricting to this family can only strengthen a lower bound. Lemma A.1 (Decision-indexed hard instances). For each i ≥ 1 and each λ ∈ ∆ρ (λ⋆ ), N σ(Di (λ)) = λ. Moreover, for any policy π, sup

Regret(π, D) ≥ lim sup i→∞

D∈Hρ (σ )

Regret π, Di (λ) ,

sup λ∈∆ρ (λ⋆ )

and the same inequality holds after taking inf π . In particular, Vρ,τ (σ) ≥

inf sym

π∈Πρ,τ (σ )

lim sup

sup

i→∞

λ∈∆ρ (λ⋆ )

Regret π, Di (λ) .

Lemma A.1 shows that the search for a worst-case instance reduces to a search over a local set of decisions ∆ρ (λ⋆ ), with statistical indistinguishability controlled armwise by VLCρ (· | H) through the selectors (A.1). A.2.

Decision Mismatch

Next, we rewrite the normalized regret into a form that highlights the discrepancy between a policy’s terminal decision and the target decision induced by the instance. Fix i ≥ 1 and a decision λ ∈ ∆ρ (λ⋆ ). By construction, the decision-indexed instance Di (λ) has decision-relevant profile N (σ(Di (λ))) = λ. When a policy π is run on this instance, it produces terminal counts n = (n1 , . . . , nd ) and hence a random terminal decision λ̄ :=

n ∈ ∆d . T

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

The regret can therefore be viewed as the expected cost of implementing λ̄ when the target decision is λ. We formalize this by introducing the decision mismatch function r(·∥·), which quantifies the penalty for acting according to one decision when another is the target. In our setting, r(λ̄∥λ) :=

λ λk − 1 = max − 1, k∈[d] λ̄k λ̄ ∞

(A.2)

with the convention r(λ̄∥λ) = +∞ if λ̄k = 0 for some k. A direct calculation from the definition of normalized regret shows that, for each i and λ, Regret π, Di (λ) = E r(λ̄∥λ) ,

(A.3)

where the expectation is over the randomness of the policy and the samples through the random terminal decision λ̄. The advantage of (A.3) is that it decouples analytic and statistical components. The non-additive structure of the objective is entirely encapsulated by the deterministic function r(·∥·), while the behavior of any policy π is reduced to the distributional properties of a single random vector, the terminal decision λ̄. This highlights a fundamental departure from classic bandit frameworks: in those settings, regret is typically a cumulative sum of separable per-round losses, whereas here the objective is evaluated holistically on the terminal allocation. Consequently, the relevant geometry is induced by r on the decision set, rather than by additive per-arm contributions. Finally, while the notation r(·∥·) is suggestive of a divergence, it is simply a problem-specific cost function derived from the regret definition. It satisfies the basic separation property r(λ∥λ) = 0 =⇒ λ = λ̄ and r(λ̄∥λ) > 0 for λ̄ ̸= λ, and increases as λ̄ deviates from the target λ. A.3.

Structured Adversarial Construction

The analysis now requires simplifying the supremum over the local decision set ∆ρ (λ⋆ ) to make the lower bound tractable. The core strategy is to replace this continuous set with a finite, structured collection of hardest-to-distinguish alternatives. This reduction is principled: shrinking the set of possible instances into a finite set makes the problem easier for the policy (in fact, it makes the problem as easy as classification on a specific loss function), hence any lower bound derived on the restricted family remains valid for the original problem. The resulting task is a discrete multi-class testing problem.

A finite “sign-cube” of directions. The central step is to replace the continuum of deviation directions by a finite set that preserves the essential combinatorial difficulty. We restrict to a finite design X ⊂ {−1, +1}d ∩ 1⊥ , so that instead of estimating a continuous decision, the policy must identify which label x ∈ X was chosen by the adversary.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Embedding the code into the local decision set. With the combinatorial structure fixed by X , we embed these discrete directions into the local geometry around the base decision λ⋆ ∈ ∆d . A raw direction x ∈ X must be mapped to a valid nearby decision. We do so by choosing a linear map A ∈ Rd×d and defining ρ λx := λ⋆ ⊙ 1 + √ Ax , d

x ∈ X,

(A.4)

where ⊙ denotes the Hadamard product. This parameterization cleanly separates (i) the discrete directions x ∈ X from (ii) the orientation/anisotropy encoded by A. For (A.4) to be valid, we must ensure λx ∈ ∆ρ (λ⋆ ). This is equivalent to AX ⊥ (λ⋆ ), and

≤

√ d.

(A.5)

∞

Lemma A.2 (Exact feasibility conditions for the local simplex). Fix λ⋆ ∈ ∆d and ρ ∈ (0, 1). For each x ∈ X , define ρ λx := λ⋆ ⊙ 1 + √ Ax . d Then the following are equivalent: (i) λx ∈ ∆ρ (λ⋆ ), i.e. λx /λ⋆ − 1 2 ≤ ρ and λx ∈ ∆d . (ii) The vector ux := Ax satisfies the two constraints ⟨λ⋆ , ux ⟩ = 0 In particular, if AX ⊂ (λ⋆ )⊥ and supx∈X ∥Ax∥2 ≤

and √

∥ux ∥2 ≤

√ d.

d, then {λx }x∈X ⊂ ∆ρ (λ⋆ ).

From decisions to hard instances. Using the decision-indexed generator from Section A.1, each candidate decision λx induces a hard instance Di (x) := Di (λx ) ∈ Hd ,

x ∈ X.

Thus, the adversary randomizes over the finite family {Di (x) : x ∈ X }.

Separation: regret reduces to decision mismatch on the constructed family. The key point is that, on this family, normalized regret is exactly the expected mismatch between the random terminal decision λ̄ = n/T and the target decision λx . Lemma A.3 (Separation on the constructed family). For every policy π, every i ≥ 1, and every x ∈ X, h Regret(π, Di (x)) = Eλ̄∼(π,Di (x)) r λ̄

λx

where r(·∥·) is the decision mismatch defined in (A.2). Together, Lemmas A.8–A.3 reduce the lower bound problem to analyzing a finite multi-class testing problem over x ∈ X , with statistical indistinguishability controlled by VLCρ through the instance generator A and decision separation controlled by the loss-induced geometry r.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

A.4.

Reduction to a classification problem

A direct lower-bound analysis of the expected mismatch cost E r(λ̄∥λ) is difficult, since it requires characterizing the distribution of the policy’s random terminal decision λ̄ = n/T for an arbitrary adaptive policy. To bridge this continuous–discrete gap, we follow a standard information-theoretic template: we discretize the local decision set by a finite packing and reduce the problem to a multi-class testing task. The novelty in our setting is that, because the loss is non-additive and non-Euclidean, we must first identify a loss-compatible geometry that turns misclassification into a quantitative regret penalty. The minimum-mismatch decoder Fix a finite set of candidate decisions {λx }x∈X ⊂ ∆ρ (λ⋆ ) (as constructed in Section A.3). Given an output λ̄ ∈ ∆ρ (λ⋆ ), we decode a label by nearest-neighbor in the mismatch loss r: Definition 3 (Minimum-mismatch decoder). Given λ̄ ∈ ∆ρ (λ⋆ ), define x̄ ∈ argmin r λ̄ λx′ .

(A.6)

x′ ∈X

This decoder is canonical for our objective: it projects the continuous terminal decision onto the discrete packing using exactly the loss that defines regret. A loss-induced geometry on decisions To lower bound regret by a term that depends only on the discrete event {x̄ ̸= x}, we need a function that quantifies the intrinsic cost of confusing two labels. We define this cost through a minimax ambiguity principle. Definition 4 (Symmetric ambiguity cost). For λa , λb ∈ ∆d , define r̃(λa , λb ) := inf max{r(λ∥λa ), r(λ∥λb )} . λ∈∆d

By construction, r̃(λa , λb ) is the smallest worst-case mismatch incurred by a single decision when the target is either λa or λb . This is the loss-induced notion of separation we use throughout the lower bound. Lemma A.4 (Projection reduces regret). Fix {λx }x∈X ⊂ ∆ρ (λ⋆ ) and let x ∈ X be the true label. For any policy and the decoder x̄ from Definition 3, E r λ̄ λx ≥ E[r̃(λx , λx̄ )] ≥ Pr(x̄ ̸= x) · min r̃(λx , λb ). b̸=x

The first inequality converts regret into an ambiguity penalty, and the second isolates the misclassification probability. Thus, the lower bound reduces to controlling two factors: a statistical classification error and a geometric separation term. A tractable ℓ1 separation A key simplification in our setting is that the geometry induced by r̃ is equivalent to the ℓ1 geometry on ∆d . Lemma A.5 (ℓ1 lower bound for r̃). For all λa , λb ∈ ∆d , 1 r̃(λa , λb ) = ∥λa − λb ∥1 . 2 In particular, if the finite family {λx } is well separated in ℓ1 , then any misclassification event {x̄ = ̸ x} forces a nontrivial regret penalty. In the next subsections, we bound the classification error via Fano (using structured KL control from VLCρ ) and bound the decision separation via the explicit parameterization of λx .

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

22 A.5.

Bounding the classification error

The reduction in Lemma A.4 shows that the regret lower bound factors through the misclassification probability Pr(x̄ ̸= x). This is a multi-class testing problem: the adversary draws a label x ∼ U(X ), the policy observes the bandit transcript FT , and outputs a decoded label x̄ = x̄(FT ). The ability of any policy to succeed is limited by the amount of information the transcript carries about x. A standard information-theoretic tool is Fano’s inequality, which lower bounds Pr(x̄ ̸= x) when the mutual information I(x; FT ) is small. For bandit models, I(x; FT ) can be upper bounded by average pairwise transcript KL, and transcript KL decomposes into a sum over arms of expected pulls times arm-level KL. Our local construction provides control of both terms. First, by construction of the VLC selectors (Step 2 in Section A.1), the arm-level KL between two labels is proportional to the squared decision perturbation, with proportionality constant VLCρ (σk | H) (up to a vanishing o(1) term along i → ∞). Second, for policies in the local minimax class, the tolerance condition forces sampling proportions to remain in the local regime, yielding the pull-count control E[nk ] ≈ T λ⋆k (up to a vanishing error as (ρ, τ ) → (0, 0)). Combining these two controls yields a geometric upper bound on mutual information in terms of a Frobenius norm, stated next. Lemma A.6 (Fano bound with structured KL). Let X ⊂ {±1}d ∩ 1⊥ be nonempty and let x ∼ U(X ). Let {λx }x∈X be defined by (A.4) for some A ∈ Rd×d , and set Σ := Cov U(X ) ,

d Γ := diag λ⋆k VLCρ (σk | H)

k=1

where λ⋆ = N (σ) is the base decision. There exists a function ε(ρ, τ ) with ε(ρ, τ ) → 0 as (ρ, τ ) → (0, 0) such that for any policy π ∈ Πsym ρ,τ (σ), 2T ρ2

lim sup Pr(x̄ ̸= x) ≥ 1 −

i→∞

√

√ 2 Γ A Σ F 1 + ε(ρ, τ ) + log 2 . log |X |

In particular, the error term does not depend on the choice of the policy π ∈ Πsym ρ,τ (σ). √ √ Lemma A.6 isolates the statistical difficulty in a single geometric quantity: ∥ Γ A Σ∥2F , where ∥ · ∥F is the Frobenius norm. The diagonal matrix Γ encodes armwise information curvatures through VLCρ (σk | H), while Σ encodes the geometry of the design X . The embedding map A transports the design into the decision neighborhood, and the Frobenius term captures their interaction at the level of mutual information. A.6.

Bounding the decision cost

Having bounded the classification error, we now lower bound the second component in the regret reduction: the conditional decision cost E[r̃(λx , λx̄ ) | x̄ = ̸ x]. The key point is that our hard family is indexed by hypercube labels x ∈ X ⊂ {±1}d , so the disagreement structure of x − x̄ has a simple combinatorial form. Define the disagreement projector P̸= := diag 1{xk ̸= x̄k } ,

so that

x − x̄ = 2 P̸= x.

This representation allows us to connect decision separation directly to the ℓ1 geometry of the loss.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Lemma A.7 (Lower bound on conditional decision cost). Assume the candidates are parameterized as ρ λx = λ⋆ ⊙ 1 + √ Ax , d

x ∈ X ⊂ {±1}d ,

and define Λ := diag(λ⋆ ). Then on the event {x̄ ̸= x}, ρ r̃(λx , λx̄ ) = √ Λ A (P̸= x) 1 , d and hence ρ h E[r̃(λx , λx̄ ) | x̄ ̸= x] = √ E Λ A (P̸= x) 1 d

i x̄ ̸= x .

√ The equality in Lemma A.7 consists of a conventional scale factor ρ/ d and a core structural term ∥Λ A P̸= x∥1 . This term quantifies the magnitude of the decision penalty by composing the policy-dependent disagreement vector P̸= x with the embedding A and the baseline scaling Λ. It is precisely this interaction that creates the adversary’s tradeoff: the same embedding A that controls statistical indistinguishability through the Frobenius term in Lemma A.6 also controls the magnitude of the penalty incurred when the policy makes an error. A.7.

Tuning the design

The structured construction reduces the lower bound to a discrete testing problem indexed by (X , A). We now explain how these objects are chosen so as to (i) make the classification problem hard and (ii) ensure that any error is costly, while maintaining feasibility of the local parameterization.

Design of X . The set X plays a purely combinatorial role: it defines the discrete set of candidate directions and hence the number of labels the policy must distinguish. To make the testing problem intrinsically hard, we want |X | to be exponentially large in d. At the same time, to amplify the cost of any error, we want X to be well-separated in Hamming distance so that any misclassification produces a large disagreement pattern (and hence a large projector P̸= ). These two requirements are met by a standard Gilbert–Varshamov construction. Such a design only exists in even dimensions d ∈ 2 · N. For simplicity, we assume that d is even. Proving the lower bound on odd dimensions can be easily extended by dropping one arm or padding with a dummy coordinate. Lemma A.8 (Hypercube design). There exists a universal constant κ > 0 and a set X ⊂ {−1, 1}d ∩ 1⊥ such that minx̸=x′ dH (x, x′ ) ≥ d/4 and log |X | ≥ κd. For the remainder of the analysis we fix such a design X .

Design of the representation map A. Once X is fixed, the remaining degree of freedom is the embedding A, which controls the orientation of the packing inside the local decision neighborhood through λx = λ⋆ ⊙ (1 + √ρd Ax). The key point is that the same A governs both sides of the lower bound: • Distinguishability (classification). The mutual information bound from Fano yields a term of the form √ √ ∥ Γ A Σ∥2F , where Σ = Cov(U(X )) and Γ = diag(λ⋆k VLCρ (σk | H)). ̸ x}, the ℓ1 geometry yields a term of the form ∥Λ A(P̸= x)∥1 , where • Decision cost. On the event {x̄ = Λ = diag(λ⋆ ).

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Thus, choosing A amounts to choosing an embedding that is simultaneously hard to distinguish and costly to confuse. We select A by a deterministic derandomization argument; let us explain the motivation. At this point the lower bound depends on A through two competing geometric quantities (one governing distinguishability, one governing the cost of confusion), and optimizing this tradeoff directly over all matrices is analytically hard. Random matrix theory provides a mature calculus for computing expectations of spectral and norm functionals under rotations, so averaging over a symmetric matrix ensemble often yields clean first-order expressions for the quantities we need. We separate anisotropy from orientation by writing a right polar-type decomposition A = SO, where S is a deterministic positive semi-definite matrix that encodes the anisotropy we wish to impose, and O is an orthogonal matrix that randomizes orientation. The anisotropy matrix S fixes the local shape of the construction and prepares the problem for a uniform orthogonal randomization: since S is supposed to deal with any anisotropies, averaging uniformly over O is the natural way to remove orientation effects. Concretely, we do not average over the whole orthogonal group: to maintain feasibility we restrict the orientation to orthogonal matrices that send the (normalized) base direction λ to the all-ones direction 1. Since orthogonal maps preserve Euclidean norms, we impose this constraint at the level of unit vectors and sample O from the compact set n λ 1 o O(λ→1) := O ∈ O(d) : O =√ . ∥λ∥2 d We take O to be uniform over O(λ→1) in the canonical way induced by Haar measure: fix any deterministic λ Q ∈ O(d) such that Q ∥λ∥ = √1d , draw U Haar-uniform from the stabilizer subgroup Stab(1) := {U ∈ O(d) : 2

U 1 = 1}, and set O = U Q. This law is supported on O(λ→1), is invariant under the natural symmetries of the constraint, and does not depend on the particular choice of Q. Since O(λ→1) is compact, the resulting distribution is a bona fide probability measure and the expectations we use are well-defined; we therefore omit the standard measure-theoretic formalities. After this symmetrization step, the analysis depends on S only through rotation-invariant quantities. We then derandomize: once we compute the average tradeoff over O, there must exist a fixed orthogonal O (and hence a fixed A = SO) that achieves at least the same tradeoff. This reduces the hard instance design to choosing the deterministic anisotropy S (optimized later), while the orthogonal factor O serves as the analytic device that makes the calculation tractable. Lemma A.9 (Representation Design). Let Σ = Cov(U(X )), Λ = diag(λ⋆ ), and d Γ := diag λ⋆k VLCρ (σk | H) . k=1

There exist A⋆ ∈ R

d×d

such that Ex∼U (X ),x̄

ΛA⋆ (P̸= x) 1 √ √ ΓA⋆ Σ F

x̄ ̸= x

v u d uX ≳t

Hetk (λ⋆ ) , VLCρ (σk | H) k=1

where ≳ hides universal constants and a possible error term that is only a function of d. Moreover, the inequality above is scale invariant for A⋆ , i.e., it remains valid for any t · A⋆ for t > 0.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Feasibility and resolution. Finally, the packing must remain inside the local neighborhood. Feasibility requires that the multiplicative perturbations in λx = λ⋆ ⊙ (1 + √ρd Ax) preserve positivity and normalization. This imposes a resolution constraint relating ρ and (d, T ). Lemma A.10 (Feasibility and resolution). Setting ρ∗ = Θ √ and ∥A⋆ X ∥2 ≤ d.

q d T

implies that for all ρ ≳ ρ∗ A⋆ X ⊥ λ⋆

Together, Lemmas A.8–A.10 complete the tuning of the adversarial construction: X provides a large, well-separated label set; A provides a favorable embedding capturing both orientation and anisotropy; and ρ p must exceed the budget-imposed resolution ρ⋆ = 12 d/T . A.8.

Putting everything together: Proof of Theorem 2.1

We now synthesize the preceding components into a proof of Theorem 2.1. Throughout, fix a base profile σ ∈ Rd+ , a radius ρ ∈ (0, 1), and a tolerance τ > 0 such that the local minimax class Πsym ρ,τ (σ) is nonempty. Let λ⋆ := N (σ) and Λ := diag(λ⋆ ). p Fix ρ ≥ ρ⋆ := 12 d/T . Let X ⊂ {−1, 1}d ∩ 1⊥ be a design with log |X | ≥ κd and minx̸=x′ dH (x, x′ ) ≥ d/4 (which existence is guaranteed via Lemma A.8). For a linear map A ∈ Rd×d (chosen below), define candidate decisions ρ λx = λ⋆ ⊙ 1 + √ Ax , d

x ∈ X,

and let Di (x) := Di (λx ) be the corresponding decision-indexed instances constructed from the VLCρ selectors. For any policy π ∈ Πsym ρ,τ (σ), let λ̄ = n/T be its terminal decision and let x̄ be the minimum-mismatch decoder (see Definition 3).

Step 1: reduce regret to classification error and decision cost. By Lemma A.3, for each x ∈ X , Regret(π, Di (x)) = E r(λ̄∥λx ) . Applying Lemma A.4 yields Regret(π, Di (x)) = E r(λ̄∥λx ) ≥ Pr(x̄ ̸= x) · E[r̃(λx , λx̄ ) | x̄ ̸= x] .

(A.7)

Step 2: bound the classification error by Fano. Let x⋆ ∼ U (X ) be uniform on X . Lemma A.6 gives √ 2 Γ A Σ F (1 + ε(ρ, τ )) + log 2 lim sup Pr(x̄ ̸= x⋆ ) ≥ 1 − , (A.8) log |X | i→∞ d where Σ = Cov(U(X )) and Γ := diag λ⋆k VLCρ (σk | H) . Since log |X | ≥ κd, it suffices to choose the 2T ρ2

√

k=1

resolution ρ > 0 so that the fraction in (A.8) is bounded away from 1. This is possible if we choose s √ √ 2 d log |X | 2T ρ2 1 1 Γ A Σ F ≥ ⇐⇒ ρ ≥ √ √ 2. d log |X | 2 2 T ΓA Σ F

Then, we have Pr(x̄ ̸= x⋆ ) ≥ 1 −

1 + ϵ(ρ, τ ) log 2/κ − = Ω(1 − ϵ(ρ, τ )). 2 d

(A.9)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Step 3: bound the conditional decision cost. On {x̄ ̸= x}, Lemma A.7 yields ρ h E[r̃(λx , λx̄ ) | x̄ ̸= x] = √ E Λ A (P̸= x) 1 d

x̄ ̸= x =

1 2

i h x̄ = ̸ x E Λ A (P x) = ̸ log |X | 1 √ √ , T ΓA Σ F

(A.10)

where P̸= = diag(1{xk ̸= x̄k }).

Step 4: choose a good orientation and conclude. The remaining task is to choose an embedding A that makes the ratio between the decision-cost term in (A.10) and the distinguishability term in (A.9) large. This is achieved by the representation lemma (Lemma A.9), which provides a choice of A such that, up to universal constants and vanishing terms, v v u u d u d λ⋆ 1 − (λ⋆ /∥λ⋆ ∥ )2 uX Hetk (λ⋆ ) X 2 u k k E ΛA⋆ (P̸= x) 1 x̄ ̸= x t √ √ ≳ =t , VLCρ (σk | H) VLCρ (σk | H) ΓA⋆ Σ F k=1 k=1

(A.11)

Combining (A.7), (A.10), (A.11), the constant lower bound on Pr(x̄ ̸= x), as well as log |X | ≥ κd yields v r u d X Hetk (λ⋆ ) du t , lim sup sup Regret(π, Di (x)) ≳ (1 − ϵ(ρ, τ )) T k=1 VLCρ (σk | H) i→∞ x∈X where we implicitly used that the constructed instance is feasible by Lemma A.2. By recalling that λ⋆ ∝ σ and that Het is scale-invariant, and taking inf π∈Πsym (which is possible since the error term ϵ does not ρ,τ (σ ) depend on the choice of π, by Lemma A.6) and using Lemma A.1, we complete the proof for Theorem 2.1.

Appendix B:

Proof of Technical Lemmas

Proof of Lemma 3.1. Fix σ ∈ R>0 and write θ := σ 2 . Recall VLCρ (σ | H) =

inf

sup

D∈Sρ (σ ) va ,v ∈Bρ (σ ) b

o n v2 − σ2 ≤ ρ . Bρ (σ) = v ∈ R>0 : σ2

KL(D(va ) ∥ D(vb )) , 2 2 2 va −vb σ2

Let θa := va2 and θb := vb2 . Then va , vb ∈ Bρ (σ) implies θa , θb ∈ [ θ(1 − ρ), θ(1 + ρ) ]. Moreover, the denominator becomes v 2 − v 2 2 a

σ2

θ − θ 2 a

Step 1: lower bound. Fix any selector D ∈ Sρ (σ). For any va , vb ∈ Bρ (σ), D(va ) ∈ H has variance θa and D(vb ) ∈ H has variance θb . Therefore KL(D(va ) ∥ D(vb )) ≥

inf

Q∈H: P ∈H: Var(Q)=θa Var(P )=θb

KL(Q ∥ P ).

Take ∆ := θa − θb . By Assumption 3.1, for every ε > 0 there exists δε > 0 such that if |∆| ≤ δε then I (θ ) Var b inf inf KL(Q∥P ) ≥ − ε ∆2 . Var(P )=θb Var(Q)=θa 2 Since θb ∈ [θ(1 − ρ), θ(1 + ρ)] and IVar (·) is finite at θ under the assumption, we may choose ρ small enough so that IVar (θb ) = IVar (θ) (1 + oρ (1)) uniformly over θb in this interval. Hence, uniformly for all va , vb ∈ Bρ (σ) with |θa − θb | ≤ δε , KL(D(va ) ∥ D(vb )) ≥

Var (θ)

− ε (θa − θb )2 · (1 + oρ (1)).

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Dividing by (θa − θb )/θ

gives I (θ) KL(D(va ) ∥ D(vb )) Var ≥ θ2 − ε · (1 + oρ (1)). 2 2 (θa − θb )/θ

Taking the supremum over va , vb ∈ Bρ (σ) (restricting to pairs with sufficiently small |θa − θb | is allowed since the supremum is over a larger set), then taking the infimum over selectors D, yields VLCρ (σ | H) ≥ θ2

Var (θ)

− ε · (1 + oρ (1)).

Finally, send first ρ ↓ 0 (so oρ (1) → 0) and then ε ↓ 0 to obtain σ4 θ2 IVar (θ) = IVar (σ 2 ). 2 2

lim inf VLCρ (σ | H) ≥ ρ↓0

(B.1)

Step 2: upper bound. We show the matching upper bound by constructing a selector whose KL matches the quadratic upper expansion. Fix ε > 0. By Assumption 3.1, there exists δε > 0 such that for all |∆| ≤ δε , inf

inf

P ∈H: Q∈H: Var(P )=θ Var(Q)=θ+∆

KL(Q∥P ) ≤

Var (θ)

+ ε ∆2 .

Moreover, the assumption provides a C 2 curve {Pϑ : ϑ ∈ (θ − η, θ + η)} ⊂ H with Var(Pϑ ) = ϑ that attains this upper bound up to o(∆2 ). Choose ρ0 > 0 such that θ(1 + ρ0 ) < θ + η and θ(1 − ρ0 ) > θ − η. For any ρ ∈ (0, ρ0 ), define a selector D ∈ Sρ (σ) by v ∈ Bρ (σ).

D(v) := Pv2 ,

Then for any va , vb ∈ Bρ (σ), writing ∆ = θa − θb , the C 2 curve property yields KL(D(va )∥D(vb )) = KL(Pθa ∥Pθb ) ≤ uniformly over va , vb ∈ Bρ (σ) as ρ ↓ 0. Dividing by ∆/θ

Var (θ)

+ ε ∆2 · (1 + oρ (1)),

gives

KL(D(va )∥D(vb )) 2 IVar (θ) + ε · (1 + oρ (1)). ≤ θ 2 2 va ,vb ∈Bρ (σ ) (va2 − vb2 )/σ 2 sup

Taking the infimum over selectors yields VLCρ (σ | H) ≤ θ2

Var (θ)

+ ε · (1 + oρ (1)).

Sending ρ ↓ 0 and then ε ↓ 0 gives lim sup VLCρ (σ | H) ≤ ρ↓0

θ2 σ4 IVar (θ) = IVar (σ 2 ). 2 2

Step 3: conclude. Combining (B.1) and (B.2) yields VLCρ (σ | H) =

σ4 IVar (σ 2 ) 1 + oρ (1) , 2

for ρ small enough, where oρ (1) → 0 as ρ ↓ 0. This proves the lemma.

(B.2)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Proof of Lemma A.1. Fix i ≥ 1 and λ ∈ ∆ρ (λ⋆ ), and set v := σ(λ) = ∥σ∥2

√ λ.

Since λ⋆ = N (σ), we have σk2 = ∥σ∥22 λ⋆k for each k, hence λk vk2 − σk2 = ⋆ − 1 ≤ ρ, 2 σk λk

k ∈ [d],

(i)

so vk ∈ Bρ (σk ) and the selector Dk (vk ) is well-defined. By construction, (i) (i) Di (λ) = D(i) (v) = D1 (v1 ), . . . , Dd (vd ) , (i) and each selector satisfies Var(Dk (vk )) = vk2 . Therefore σ Di (λ) = v, and hence v ⊙2 ∥σ∥22 λ N σ(Di (λ)) = N (v) = = = λ, ∥v∥22 ∥σ∥22 Pd where we used ∥v∥22 = ∥σ∥22 k=1 λk = ∥σ∥22 . Next, since λ ∈ ∆ρ (λ⋆ ) and N (σ(Di (λ))) = λ, we have Di (λ) ∈ Hρ (σ) (and in fact also R⋆ (σ(Di (λ))) = ∥σ∥22 /T = R⋆ (σ) by the identity above). Hence, for any policy π and any i ≥ 1, Regret(π, D) ≥

sup

Regret π, Di (λ) .

sup λ∈∆ρ (λ⋆ )

D∈Hρ (σ )

Taking lim supi→∞ yields the second display in the lemma. Applying inf π to both sides preserves the inequality, and restricting the infimum to Πsym ρ,τ (σ) gives the final displayed bound for Vρ,τ (σ). Proof of Lemma A.2. Fix λ⋆ ∈ ∆d and ρ ∈ (0, 1), and let x ∈ X . Write ρ ux := Ax, so that λx = λ⋆ ⊙ 1 + √ ux . d Since λ⋆ ∈ ∆d has strictly positive coordinates (here λ⋆ = N (σ) with σ ∈ Rd+ ), the componentwise ratio is well-defined and satisfies ρ λx = 1 + √ ux . ⋆ λ d

(B.3)

(i)⇒(ii). Assume λx ∈ ∆ρ (λ⋆ ). By definition, λx − 1 ≤ ρ. λ⋆ 2 Using (B.3), this is equivalent to ρ √ ∥ux ∥2 ≤ ρ, d

i.e.

∥ux ∥2 ≤

√ d.

Moreover, λx ∈ ∆d implies ⟨1, λx ⟩ = 1. Expanding the sum constraint, D E ρ ρ ρ ⟨1, λx ⟩ = 1, λ⋆ ⊙ 1 + √ ux = ⟨1, λ⋆ ⟩ + √ ⟨λ⋆ , ux ⟩ = 1 + √ ⟨λ⋆ , ux ⟩, d d d so ⟨1, λx ⟩ = 1 is equivalent to ⟨λ⋆ , ux ⟩ = 0. (ii)⇒(i). Assume ⟨λ⋆ , ux ⟩ = 0 and ∥ux ∥2 ≤

√

d. Then (B.3) gives

ρ λx − 1 = √ ∥ux ∥2 ≤ ρ, ⋆ λ 2 d

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

so the ℓ∞ neighborhood constraint holds. Next, the same expansion as above yields ρ ⟨1, λx ⟩ = 1 + √ ⟨λ⋆ , ux ⟩ = 1, d so λx has unit sum. Finally, for each coordinate k, ρ 1 + √ ux,k ≥ 1 − ρ ≥ 0 d

√ (since ρ ∈ (0, 1) and ux,k ≥ −∥ux ∥2 ≥ − d),

and since λ⋆k ≥ 0, this implies (λx )k ≥ 0 for all k. Therefore λx ∈ ∆d . Combining λx ∈ ∆d with the neighborhood bound proves λx ∈ ∆ρ (λ⋆ ). √

The final statement follows immediately: if AX ⊂ (λ⋆ )⊥ , i.e. ⟨λ⋆ , Ax⟩ = 0 for all x ∈ X , and supx∈X ∥Ax∥2 ≤ d, then condition (ii) holds for all x ∈ X , hence {λx }x∈X ⊂ ∆ρ (λ⋆ ). Proof of Lemma A.3. Fix a policy π, an index i ≥ 1, and a label x ∈ X . Let σx := σ(λx ) denote the

standard-deviation vector associated with λx , so that by construction of the instance generator, σ Di (x) = σx ,

N (σx ) = λx .

and

Run π on Di (x) and let n = (n1 , . . . , nd ) be the terminal pull counts, with terminal decision λ̄ := n/T . For this realized n, the risk is 2 σx,k , k∈[d] nk

R(n; σx ) = max

with the convention R(n; σx ) = +∞ if nk = 0 for some k with σx,k > 0. Since λx = N (σx ), we can write 2 σx,k = ∥σx ∥22 λx,k for each k, hence

R(n; σx ) = ∥σx ∥22 · max k∈[d]

λx,k . nk

Moreover, R⋆ (σx ) =

∥σx ∥22 , T

so for every realized n, T λx,k R(n; σx ) λx,k − 1 = max − 1 = max − 1 = r(λ̄ ∥ λx ), k∈[d] k∈[d] λ̄k R⋆ (σx ) nk where in the last step we used the definition of r in (A.2) (with the convention r(λ̄ ∥ λx ) = +∞ if λ̄k = 0 for some k). Taking expectation over the randomness of the policy and the samples (equivalently, over the induced random terminal decision λ̄) yields R(n; σx ) Regret(π, Di (x)) = E − 1 = E r(λ̄ ∥ λx ) , R⋆ (σx ) which is the claimed separation identity. Proof of Lemma A.4. Fix the true label x ∈ X and a realization of the terminal decision λ̄ ∈ ∆d . Let x̄ ∈ argminx′ ∈X r(λ̄∥λx′ ) be the minimum-mismatch decoder (Definition 3). By definition of r̃ (Definition 4), for any λ ∈ ∆d , n o max r(λ∥λx ), r(λ∥λx̄ ) ≥ r̃(λx , λx̄ ).

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Applying this inequality with λ = λ̄ yields n o max r(λ̄∥λx ), r(λ̄∥λx̄ ) ≥ r̃(λx , λx̄ ). Moreover, since x̄ minimizes r(λ̄∥λx′ ) over x′ ∈ X , we have r(λ̄∥λx̄ ) ≤ r(λ̄∥λx ), hence the maximum on the left-hand side equals r(λ̄∥λx ). Therefore, r(λ̄∥λx ) ≥ r̃(λx , λx̄ ). Taking expectation over the randomness of λ̄ (induced by the policy and samples) gives the first inequality in the lemma: E r(λ̄∥λx ) ≥ E[r̃(λx , λx̄ )] . For the second inequality, decompose according to the event {x̄ = x}: E[r̃(λx , λx̄ )] = E[r̃(λx , λx̄ ) 1{x̄ = x}] + E[r̃(λx , λx̄ ) 1{x̄ ̸= x}] . Since r̃(λx , λx ) = 0 (take λ = λx in the defining infimum), the first term is 0. On the event {x̄ ̸= x} we have r̃(λx , λx̄ ) ≥ minb̸=x r̃(λx , λb ), hence E[r̃(λx , λx̄ )] ≥ Pr(x̄ ̸= x) · min r̃(λx , λb ), b̸=x

which is the desired bound. Proof of Lemma A.5. Fix λa , λb ∈ ∆d . Recall that λa λ

r(λ∥λa ) =

− 1 = max ∞

k∈[d]

λk,a − 1, λk

with the convention r(λ∥λa ) = +∞ if λk = 0 for some k with λk,a > 0. We start with the following elementary fact: d >0

∀u ∈ R

∆d ∩ (u, +∞) ̸= ∅

⇐⇒

d X

uk < 1,

k=1

where (u, +∞) := {λ ∈ Rd : λk > uk ∀k}. Let t ≥ 0. Then r̃(λa , λb ) < t ⇐⇒ inf max r(λ∥λa ), r(λ∥λb ) < t λ∈∆

d ⇐⇒ ∃ λ ∈ ∆d : max r(λ∥λa ), r(λ∥λb ) < t λk,u ⇐⇒ ∃ λ ∈ ∆d : max <1+t k∈[d], u∈{a,b} λk 1 ⇐⇒ ∃ λ ∈ ∆d : ∀k ∈ [d], max(λk,a , λk,b ) < λk 1+t d 1 X ⇐⇒ max(λk,a , λk,b ) < 1 (by (B.4)) 1 + t k=1

⇐⇒

d X

max(λk,a , λk,b ) − 1 < t.

k=1

Since this equivalence holds for all t ≥ 0, it follows that r̃(λa , λb ) =

d X k=1

max(λk,a , λk,b ) − 1.

(B.4)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Finally, using max(x, y) = x+y+2|x−y| and

d X

k=1

max(λk,a , λk,b ) =

λk,a =

P k

λk,b = 1, we obtain

1X 1 λk,a + λk,b + |λk,a − λk,b | = 1 + ∥λa − λb ∥1 . 2 k=1 2

Therefore, 1 r̃(λa , λb ) = ∥λa − λb ∥1 , 2 as claimed. Proof of Lemma A.6. Fix a nonempty X ⊂ {±1}d ∩ 1⊥ , a matrix A ∈ Rd×d , and a policy π ∈ Πsym ρ,τ (σ). Let x ∼ U(X ) and let FT denote the bandit transcript generated by running π on the instance Di (x). For any decoder x̄ = x̄(FT ), Fano’s inequality gives Pr(x̄ ̸= x) ≥ 1 −

log 2 + I(x; FT ) . log |X |

Moreover, since x is uniform, the mutual information admits the standard upper bound 1 X KL (π, Di (x)) (π, Di (y)) , I(x; FT ) ≤ 2 |X | x,y∈X

(B.5)

(B.6)

where (π, Di (x)) denotes the law of the transcript under policy π and instance Di (x).

Step 1: bandit KL decomposition. For fixed x, y ∈ X , the canonical KL decomposition for bandit transcripts yields d X (i) (i) KL (π, Di (x)) (π, Di (y)) = En∼(π,Di (x)) [nk ] KL Dk (λx ) Dk (λy ) ,

(B.7)

k=1

(i)

where Dk (λx ) denotes the k-th arm distribution in Di (λx ).

Step 2: controlling pull counts via tolerance. Let λ̄ := n/T be the terminal decision under (π, Di (x)). By Lemma A.3, Regret(π, Di (x)) = E r(λ̄ ∥ λx ) ≤ τ. Since r(·∥λx ) is convex in its first argument, Jensen’s inequality implies r E[λ̄] λx ≤ E r(λ̄ ∥ λx ) ≤ τ. Unpacking the definition r(u∥v) = ∥v/u∥∞ − 1, this gives, for every k ∈ [d], (λx )k −1 ≤ τ E[λ̄k ] Using

P k

=⇒

E[λ̄k ] ≥

(λx )k . 1+τ

E[λ̄k ] = 1, we obtain the complementary upper bound X 1 X (λx )k + τ E[λ̄k ] = 1 − E[λ̄j ] ≤ 1 − (λx )j = ≤ (λx )k + τ. 1 + τ 1+τ j̸=k j̸=k

Since λx ∈ ∆ρ (λ⋆ ), we have (λx )k ≤ (1 + ρ)λ⋆k , hence E[λ̄k ] ≤ (1 + ρ)λ⋆k + τ ≤ (1 + ε(ρ, τ )) λ⋆k ,

(B.8)

where one may take, e.g., ε(ρ, τ ) := ρ + τ / minj∈[d] λ⋆j , which satisfies ε(ρ, τ ) → 0 as (ρ, τ ) → (0, 0) for fixed λ⋆ ∈ ∆ d . Combining (B.8) with E[nk ] = T E[λ̄k ] yields En∼(π,Di (x)) [nk ] ≤ T λ⋆k (1 + ε(ρ, τ )).

(B.9)

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Step 3: controlling arm-level KL via VLCρ . By construction of the instance generator, the variance of arm k under Di (λ) is σk (λ)2 = ∥σ∥22 λk . Using the selectors in (A.1) and the definition of VLCρ (σk | H), we have σ (λ )2 − σ (λ )2 2 k x k y (i) (i) lim sup KL Dk (λx ) Dk (λy ) ≤ VLCρ (σk | H) . σk2 i→∞ Since σk2 = ∥σ∥22 λ⋆k and σk (λ)2 = ∥σ∥22 λk , we get σk (λx )2 − σk (λy )2 (λx )k − (λy )k = . σk2 λ⋆k Under the parametrization λx = λ⋆ ⊙ (1 + √ρd Ax), ρ (λx )k − (λy )k = λ⋆k · √ [A(x − y)]k , d so the ratio equals √ρd [A(x − y)]k , and therefore ρ2 (i) (i) VLCρ (σk | H) [A(x − y)]2k . lim sup KL Dk (λx ) Dk (λy ) ≤ d i→∞

(B.10)

Step 4: averaging and Frobenius form. Plugging (B.9) and (B.10) into (B.7) gives d X T ρ2 lim sup KL (π, Di (x)) (π, Di (y)) ≤ (1 + ε(ρ, τ )) λ⋆k VLCρ (σk | H) [A(x − y)]2k . d i→∞ k=1

With Γ := diag(λ⋆k VLCρ (σk | H))dk=1 , the sum equals (x − y)⊤ A⊤ ΓA(x − y). Averaging over x, y ∼ U(X ) i.i.d., and using E[(x − y)(x − y)⊤ ] = 2 Cov(U(X )) = 2Σ, we obtain T ρ2 1 X lim sup KL (π, D (x)) (π, D (y)) ≤ (1 + ε(ρ, τ )) · 2 Tr(Γ A Σ A⊤ ) i i |X |2 x,y∈X d i→∞ =

√ √ 2 2T ρ2 (1 + ε(ρ, τ )) ΓA Σ F. d

Combining this bound with (B.5)–(B.6) yields the stated inequality. Proof of Lemma A.7. Fix i ≥ 1 and x ∈ X . On the constructed family we have ρ ρ λx = λ⋆ ⊙ 1 + √ Ax , λx̄ = λ⋆ ⊙ 1 + √ Ax̄ . d d Therefore ρ ρ λx − λx̄ = √ λ⋆ ⊙ A(x − x̄) = √ Λ A (x − x̄), d d ⋆ where Λ = diag(λ ). By Lemma A.5, 1 ρ r̃(λx , λx̄ ) = ∥λx − λx̄ ∥1 = √ Λ A (x − x̄) 1 . 2 2 d Next, recall P̸= := diag(1{xk ̸= x̄k }). For each coordinate k, if xk = x̄k then (x − x̄)k = 0, and if xk ̸= x̄k then necessarily x̄k = −xk and (x − x̄)k = 2xk . Hence x − x̄ = 2 P̸= x, and plugging this into the previous display yields, on the event {x̄ ̸= x} (and in fact always), ρ ρ r̃(λx , λx̄ ) = √ Λ A (2 P̸= x) 1 = √ Λ A (P̸= x) 1 . 2 d d Taking conditional expectation given {x̄ ̸= x} gives the second display.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Proof of Lemma A.8. Let E be the set of subsets of {−1, 1}d satisfying both orthogonality and separation, i.e., n E := X ⊂ {−1, 1}d : X ⊂ 1⊥ ,

min dH (x, x′ ) ≥ ′

x̸=x ∈X

do . 4

Let m be the largest size in E, i.e., m := max |X |. X ∈E

Proving the lemma boils down to proving log m = Ω(d). First, notice that E is non-empty, since the singleton n o (1, . . . , 1, −1, . . . , −1) (consisting of d/2 ones and d/2 minus ones) lies in E. Let S ∈ E be a set of maximal size. We introduce the Pd balls associated with the 0-norm ∥x∥0 = k=1 1{xk ̸= 0}: for x ∈ {−1, 1}d and r > 0, n o B0 (x, r) := y ∈ {−1, 1}d : ∥x − y∥0 < r . We claim that {−1, 1}d ∩ 1⊥ =

[

B0 (y, d/4) ∩ 1⊥ .

(B.11)

y∈S

The inclusion ⊆ is immediate. Assume for the sake of contradiction that it is strict, i.e., there exists x ∈ {−1, 1}d with x ⊥ 1 such that

d X

d 1{xk ̸= yk } ≥ , 4 k=1

∀y ∈ S,

or equivalently miny∈S dH (x, y) ≥ d/4. In particular x ∈ / S, and the new set S ′ := S ∪ {x} still satisfies orthogonality and separation, hence S ′ ∈ E, contradicting the maximality of S. Therefore (B.11) holds. Next, using (B.11) and a union bound, |{−1, 1}d ∩ 1⊥ | =

[

B0 (y, d/4) ∩ 1⊥

y∈S

≤

B0 (y, d/4) ∩ 1⊥ .

y∈S ⊥

By symmetry of {−1, 1} , the sets B0 (y, d/4) ∩ 1 have constant size over {−1, 1}d ∩ 1⊥ . In particular, they d

have the same size as B0 (y0 , d/4) ∩ 1⊥ , where y0 = (1, . . . , 1, −1, . . . , −1) consists of d/2 ones and d/2 minus ones. Therefore, |{−1, 1}d ∩ 1⊥ | ≤ |S| · |B0 (y0 , d/4) ∩ 1⊥ | = m · |B0 (y0 , d/4) ∩ 1⊥ |, or equivalently m ≥

|{−1, 1}d ∩ 1⊥ | . |B0 (y0 , d/4) ∩ 1⊥ |

It remains to prove that this log-ratio grows linearly in d. The numerator can be calculated easily: choosing an element from {−1, 1}d ∩ 1⊥ is equivalent to choosing d/2 placements for +1 and setting the remaining d/2 placements to −1, hence d |{−1, 1} ∩ 1 | = . d/2 d

⊥

We now upper bound the denominator. Let x ∈ B0 (y0 , d/4) ∩ 1⊥ and let u := ∥x − y0 ∥0 ∈ {0, 1, . . . , ⌊d/4⌋}. We claim that u must be even. Indeed, for each k ∈ [d], 1 xk − y0,k 1{xk ̸= y0,k } = |xk − y0,k | ≡ 2 2

(mod 2),

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

34 so

d X

1{xk ̸= y0,k } ≡

k=1

1X 1 (xk − y0,k ) = (⟨1, x⟩ − ⟨1, y0 ⟩) ≡ 0 2 k=1 2

(mod 2),

where we used x ⊥ 1 and y0 ⊥ 1. Hence 2 | u, and we write u = 2u′ . For u = 2u′ , choosing x such that ∥x − y0 ∥0 = 2u′ amounts to choosing exactly u′ coordinates among the 2 2 +1 entries of y0 and u′ coordinates among the −1 entries of y0 to flip, hence there are d/ such vectors. u′ Therefore, ⊥

|B0 (y0 , d/4) ∩ 1 | =

X d/42 u<d/4 2|u

u/2

X d/42 u′

u′ <d/8

⌊d/4⌋

1 X ≤ 2 u=0

2 d/4 d/4 ≤ , d/8 u

where the last inequality follows from Vandermonde’s inequality. Consequently, d 2 d! [(d/8)!]2 d/2 m ≥ 2 · d/4 = . [(d/2)!]2 (d/4)! d/8 We show that the lower bound above grows exponentially in d. By Stirling’s formula, n! =

√

n n 1 2πn 1+O , e n

so a direct substitution yields 1 2 d! [(d/8)!]2 = 16 1 + O · 23d/4 . [(d/2)!]2 (d/4)! d Therefore, there exists X ∈ E such that log |X | = Ω(d), completing the proof. Proof of Lemma A.9. Fix a policy (and hence a decoder x̄ ∈ X ) and write Σ := Cov(U(X )),

Λ := diag(λ⋆ ),

d Γ := diag λ⋆k VLCρ (σk | H)

k=1

Let λ̂ := λ⋆ /∥λ⋆ ∥2 and define the constrained orthogonal class O(1 7→ λ̂) :=

n o 1 O ∈ O(d) : O √ = λ̂ . d

Let x ∼ U(X ) and O ∼ U(O(1 7→ λ̂)) be independent, and set A := SO, where S = diag(s) is a diagonal matrix with positive entries. For a realization (O, x) define U (O, x) := E ΛS O(P̸= x) 1

x̄ ̸= x ,

√ V (O) :=

√ ΓS O

Σ F.

Step 1: averaging the distinguishability term. Since X ⊂ 1⊥ , we have E[x] ∈ 1⊥ and Σ 1 = 0, hence

√ √ range(Σ) ⊂ 1⊥ . Using ∥ ΓS O Σ∥2F = Tr(S ⊤ ΓS O Σ O ⊤ ) and invariance of the uniform law on O(1 7→ λ̂) on the orthogonal complement 1⊥ , we obtain Tr(S ⊤ ΓS)Tr(Σ) EO,x V (O)2 = EO,x Tr(S ⊤ ΓS O Σ O ⊤ ) = . d−1

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Step 2: averaging the decision-cost term. On the event {x̄ ̸= x}, since x̄ ∈ X and minx̸=x′ dH (x, x′ ) ≥ d/4, we have dH (x, x̄) ≥ d/4. Moreover, x − x̄ = 2P̸= x and x − x̄ ∈ 1⊥ , so P̸= x ∈ 1⊥ and p p ∥P̸= x∥2 = dH (x, x̄) ≥ d/4. Fix any v ∈ 1⊥ and write r := ∥v∥2 . Under O ∼ U(O(1 7→ λ̂)), the random vector Ov is uniformly distributed on the sphere of radius r in λ̂⊥ . Let U ∼ Unif(Sd−2 ) and set Γ(d/2) αd := E|U1 | = √ = π Γ((d + 1)/2)

2 (1 + o(1)). πd

By rotational symmetry in λ̂⊥ , q q ⊤ 2 2 EO,x |ek Ov| = r αd Projλ̂⊥ ek 2 = r αd 1 − λ̂k = r αd 1 − (λ⋆k /∥λ⋆ ∥2 ) . Therefore, q d d X X 2 ⋆ EO,x ∥ΛS Ov∥1 = 1 − (λ⋆k /∥λ⋆ ∥2 ) . λ⋆k sk EO,x |e⊤ Ov| = r α λ s d k k k k=1

k=1

Applying this with v = P̸= x and using r = ∥v∥2 ≥ EO,x [U (O, x)] = EO,x E Λ SO(P̸= x) 1

d/4 on {x̄ ̸= x} (by definition of X ) yields √ q d d X ⋆ 2 x̄ ̸= x ≥ αd λk sk 1 − (λ⋆k /∥λ⋆ ∥2 ) . 2 k=1

Averaging over x ∼ U (X ) preserves this lower bound, hence √ q q d d d X ⋆ 1 + o(1) X ⋆ 2 2 αd λk sk 1 − (λ⋆k /∥λ⋆ ∥2 ) = √ EO,x [U (O, x)] ≥ λk sk 1 − (λ⋆k /∥λ⋆ ∥2 ) . 2 2π k=1 k=1

Step 3: existence of a good A. Let EO,x [U (O, x)] c := p . EO,x [V (O)2 ] Since U (O, x) ≥ 0 and V (O) ≥ 0, we have E[U (O, x)2 ] ≥ E[U (O, x)]2 , and therefore EO,x U (O, x)2 − c2 V (O)2 ≥ EO,x [U (O, x)]2 − c2 EO,x [V (O)2 ] = 0. Hence there exists a realization O⋆ ∈ O(1 7→ λ̂) such that U (O⋆ , x) ≥ c V (O⋆ ), i.e. q 2 1+o(1) Pd ⋆ √ λ s 1 − (λ⋆k /∥λ⋆ ∥2 ) Ex ΛS O⋆ (P̸= x) 1 x̄ ̸= x k k=1 k 2π √ √ q ≥ c≥ . Tr(S ⊤ ΓS )Tr(Σ) ΓS O⋆ Σ F d−1

⊤

Using Tr(S ΓS) =

k=1

⋆ k

λ VLCρ (σk | H)sk and Tr(Σ) ≤ d, we obtain

q 2 o(1) Pd d−1 1+ ⋆ √ λ s 1 − (λ⋆k /∥λ⋆ ∥2 ) E ΛS O⋆ (P̸= x) 1 x̄ ̸= x k k k=1 d 2π √ √ q ≥ . Pd ΓS O⋆ Σ F λ⋆ VLC (σ | H)s2 k=1

Taking the argmax of the RHS above over s > 0d with ∥s∥2 = 1 and setting S⋆ = diag(s1 , . . . , sd ), we obtain v v u u d u d λ⋆ 1 − (λ⋆ /∥λ⋆ ∥ )2 uX Hetk (λ⋆ ) 2 uX k k E ΛS⋆ O⋆ (P̸= x) 1 x̄ ̸= x t √ √ =t , ≳ VLCρ (σk | H) VLCρ (σk | H) ΓS⋆ O⋆ Σ k=1 k=1 F

where ≳ ignores numerical constants and error terms. This yields the desired inequality. Thus the lemma is proved for A⋆ = S⋆ O⋆ . Finally, the ratio in the LHS is scale-invariant in A: replacing A by tA multiplies both numerator and denominator by t.

Aznag, Cummings, and Elmachtoub: A Complexity Measure for Active Learning in Multi-group Mean Estimation

Proof of Lemma A.10. Recall the parametrization ρ λx = λ⋆ ⊙ 1 + √ Ax , d

x ∈ X.

By Lemma A.2, it suffices to ensure the two conditions ⟨λ⋆ , Ax⟩ = 0

and

∥Ax∥2 ≤

√ d

∀x ∈ X ,

because they imply {λx }x∈X ⊂ ∆ρ (λ⋆ ). Let A⋆ be the matrix provided by Lemma A.9. As ensured in the construction, we have A⋆ X ⊂ (λ⋆ )⊥ , i.e., the first condition is satisfied. Moreover, we have ∥A⋆ x∥2 = ∥S⋆ O⋆ x∥2 Moreover, once again from Lemma A.9, the matrix Ã can be rescaled without loss of generality. Thus we choose sup ∥A⋆ x∥2 =

√ d.

x∈X

We now need to determine a sufficient resolution ρ∗ > 0 under which the proof is valid. The only restriction that remains to be verified is the Inequality (A.9): s 1 d log |X | ρ≥ √ √ 2. 2 T ΓA Σ F

However, we have log |X | ≤ d. Moreover, by the choice of A⋆ , we have suffices to choose

r ρ≳

Hence ρ∗ = Θ

q d T

, which completes the proof

d . T

√

Γ A⋆

√

Σ F = Θ(d). Therefore, it

Record · ID 271819 · SHA-256 9a10976672640408
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.