The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

# The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression
Source: [https://arxiv.org/html/2607.06642](https://arxiv.org/html/2607.06642)
###### Abstract

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to*myopic*Bayesian active learning for linear regression, the common framework where long\-term planning is replaced with the one\-step optimal choice\. In this work, we prove a first\-of\-its\-kind approximation ratio for the greedy algorithm’s risk that is tight up to an absolute constant\. The approximation ratio is linear in the*maximum initial leverage score*\(MILS\), a newly identified quantity fundamental to the greedy algorithm’s performance\. Finally, we illustrate the results with simple numerical simulations\.

## 1Introduction

Optimal experimental design and active learning are two closely\-related paradigms for selecting informative data under a budget constraint\. Both ask the same fundamental question: given the freedom to choose from a pool of candidate inputs, which should we observe in order to minimize model parameter estimation error or future prediction error? In experimental design the choices are typically made offline, while in active learning they are made adaptively as new labels are observed\. However, for Bayesian linear regression, the model under consideration in this work, the observation values don’t affect the estimation or prediction risk, and thus the offline and adaptive settings are equivalent\. The task is therefore a particular set optimization function \(A/VA/V\-optimal design\) with a large search space of size\(nk\)\\binom\{n\}\{k\}that precludes brute force in any realistic setting\.

While exact optimization is NP\-hard\(Li,[2025](https://arxiv.org/html/2607.06642#bib.bib9)\), approximation algorithms have been developed\. In this work, we focus on the greedy algorithm\. The greedy algorithm starts from the empty set and repeatedly adds the point that yields the largest immediate reduction in risk, untilkkpoints have been selected\. Not only is the greedy algorithm a practical choice in the offline setting, but more importantly, addresses a fundamental question in the adaptive setting\. In the adaptive setting, to avoid the intractability of planning, the most common Bayesian active learning algorithms\(MacKay,[1992](https://arxiv.org/html/2607.06642#bib.bib7); Galet al\.,[2017](https://arxiv.org/html/2607.06642#bib.bib14); Smithet al\.,[2023](https://arxiv.org/html/2607.06642#bib.bib15)\)rely on a myopic approach: choose the observation that optimally reduces the risk, as if it were the last step\. The connection between “one\-step optimal” and “multi\-step optimal” is a gap with little work in the literature\. We focus on that connection via analyzing the equivalent greedy algorithm\.

Surprisingly little is known about how the greedy algorithm compares to the optimal strategy for this problem\. Existing guarantees\(Bianet al\.,[2017](https://arxiv.org/html/2607.06642#bib.bib18); Chamon and Ribeiro,[2017](https://arxiv.org/html/2607.06642#bib.bib19)\)bound the the*reduction*in the estimation or prediction risk \(A/VA/V\-optimal design\)\. By showing the risk reduction is monotone and approximately submodular, these work show greedy attains a constant fraction of the optimal*reduction*\. However, a constant factor approximation factor for the*reduction*is often vacuous\. Whether greedy achieves a constant factor approximation for the risk itself has, to our knowledge, remained open\.

We close this gap with the following contributions:

- •Constant\-factor risk guarantee\.We prove that the reciprocal risk for Bayesian Linear Regression is approximately submodular in the sense ofDas and Kempe \([2018](https://arxiv.org/html/2607.06642#bib.bib20)\)\. Combining this with existing analyses of greedy under approximate submodularity yields the first constant\-factor approximation guarantee on the risk achieved by greedy\. The constant is the problem\-dependent quantity*maximum initial leverage score*\(MILS\)\.
- •Parametrized hard instance showing tightness\.We construct a family of problems on which greedy’s risk is provably a factor of the MILS larger than the optimal risk which matches our upper bound\. This shows that the problem\-dependent factor in our guarantee is necessary, not an artifact of the analysis\.
- •Numerical simulation\.We use numerical simulation to illustrate previously known bounds and our bound, as well as confirm greedy’s poor performance in our construction\.

We provide the precise problem statement in Section[2](https://arxiv.org/html/2607.06642#S2), cover necessary background and related work in Section[3](https://arxiv.org/html/2607.06642#S3), provide our upper bound and lower bounds in Sections[4](https://arxiv.org/html/2607.06642#S4)and[5](https://arxiv.org/html/2607.06642#S5), then show an illustrative example in Section[6](https://arxiv.org/html/2607.06642#S6)\.

## 2Problem Statement

Precisely, our problem statement is the following:

###### Problem Statement 1\.

Given a set ofnnvectorsV=\{vi\}i=1n⊂ℝdV=\\\{v\_\{i\}\\\}\_\{i=1\}^\{n\}\\subset\\mathbb\{R\}^\{d\}, a positive definite matrixΛ∈ℝd×d\\Lambda\\in\\mathbb\{R\}^\{d\\times d\}, and a budgetkk, choose a setS⊂\[n\]S\\subset\[n\]of size\|S\|=k\|S\|=kto minimize

f​\(S\):=tr​\(\(Λ\+∑i∈Svi​vi⊤\)−1\)\\displaystyle f\(S\):=\\mathrm\{tr\}\\left\(\\left\(\\Lambda\+\\sum\_\{i\\in S\}v\_\{i\}v\_\{i\}^\{\\top\}\\right\)^\{\-1\}\\right\)\(1\)

The problem parameters are integersnn,kk, anddd\. In our analysis, we show the importance of an additional problem\-dependent parameter which we refer to as the*maximum initial leverage score*\(MILS\),

hmax=maxi∈\[n\]⁡vi⊤​Λ−1​vi\.\\displaystyle h\_\{\\text\{max\}\}=\\max\_\{i\\in\[n\]\}v\_\{i\}^\{\\top\}\\Lambda^\{\-1\}v\_\{i\}\.\(2\)
For a given problem defined byVV,Λ\\Lambda, andkk, we denote an optimal solution as

S⋆=arg⁡maxS⊂\[n\]:\|S\|=k⁡f​\(S\)\\displaystyle S^\{\\star\}=\\arg\\max\_\{S\\subset\[n\]:\|S\|=k\}f\(S\)\(3\)
### 2\.1Greedy Algorithm

In this paper, we analyze the greedy algorithm, which, given a problem, returns a setSgreedyS\_\{\\text\{greedy\}\}\. The greedy algorithm starts with an initialS0=∅S\_\{0\}=\\emptyset, then forkkiterations, chooses the element that when added, would minimizeff\. See Algorithm[1](https://arxiv.org/html/2607.06642#alg1)\.

Algorithm 1Greedy Algorithm0:Vectors

V∈ℝn×dV\\in\\mathbb\{R\}^\{n\\times d\}, Matrix

Λ∈ℝd×d\\Lambda\\in\\mathbb\{R\}^\{d\\times d\}, budget

k∈ℕk\\in\\mathbb\{N\}
0:Selected set

S⊂\[n\]S\\subset\[n\]of size

kk
1:

S0=∅S\_\{0\}=\\emptyset
2:foriteration

t←1t\\leftarrow 1to

kkdo

3:Compute

it∈arg⁡mini∉St−1⁡f​\(St−1∪\{i\}\)i\_\{t\}\\in\\arg\\min\_\{i\\not\\in S\_\{t\-1\}\}f\(S\_\{t\-1\}\\cup\\\{i\\\}\)
4:Set

St=St−1∪\{it\}S\_\{t\}=S\_\{t\-1\}\\cup\\\{i\_\{t\}\\\}
5:endfor

6:return

Sgreedy=SkS\_\{\\text\{greedy\}\}=S\_\{k\}

Note that there is non\-determinacy in the case of ties\. When we prove a result for the greedy algorithm, we require that the theorem holds for any choice of tie\-breaking\.

For the offline problem, this algorithm is attractive due to its simplicity and computational efficiency\. The greedy algorithm runs in time𝒪​\(n​k\)\\mathcal\{O\}\(nk\)\. In active learning with linear regression, the greedy algorithm is equivalent to the myopic algorithm which is attractive due to removing the need for planning\.

## 3Background and Related Work

### 3\.1Active Learning

Active learning studies the setting where there is a large pool of unlabeled data and a limited labeling budget\. An active learning algorithm adaptively chooses which points to label next in order to achieve the best test performance\. Several recent approaches study the myopic Bayesian setting\(Galet al\.,[2017](https://arxiv.org/html/2607.06642#bib.bib14); Kirschet al\.,[2019](https://arxiv.org/html/2607.06642#bib.bib13); Mussmannet al\.,[2022](https://arxiv.org/html/2607.06642#bib.bib16); Smithet al\.,[2023](https://arxiv.org/html/2607.06642#bib.bib15)\), where the next point or batch of points is chosen by minimizing an expected cost \(e\.g\., loss, entropy\)\. Given the computational planning of planning, these methods only minimize the cost after a single step, similar to greedy algorithms\.

### 3\.2Bayesian Linear Regression

Our primary motivation for the setting is Bayesian linear regression\(Bishop,[2006](https://arxiv.org/html/2607.06642#bib.bib5); Murphy,[2023](https://arxiv.org/html/2607.06642#bib.bib3)\)\. This model is defined by a prior covarianceΣ0\\Sigma\_\{0\}, observation noiseσ2\\sigma^\{2\}, and a fixed set of pointsX=\{xi\}i=1n⊂ℝdX=\\\{x\_\{i\}\\\}\_\{i=1\}^\{n\}\\subset\\mathbb\{R\}^\{d\}\. Then, the model is

ϑ\\displaystyle\\char 106\\relax∼𝒩​\(0,Σ0\)\\displaystyle\\sim\\mathcal\{N\}\(0,\\Sigma\_\{0\}\)\(4\)ϵi\\displaystyle\\epsilon\_\{i\}∼𝒩​\(0,σ2\)\\displaystyle\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\)\(5\)yi\\displaystyle y\_\{i\}=xi⊤​θ\+ϵi\\displaystyle=x\_\{i\}^\{\\top\}\\theta\+\\epsilon\_\{i\}\(6\)
A standard result is that the parameter posterior isθ\|\{\(xi,yi\)\}i∈S∼𝒩​\(μS,ΣS\)\\theta\|\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i\\in S\}\\sim\\mathcal\{N\}\(\\mu\_\{S\},\\Sigma\_\{S\}\)where

ΣS\\displaystyle\\char 83\\relax\_\{S\}=\(Σ0−1\+σ−2​∑i∈Sxi​xi⊤\)−1\\displaystyle=\\left\(\\Sigma\_\{0\}^\{\-1\}\+\\sigma^\{\-2\}\\textstyle\\sum\_\{i\\in S\}x\_\{i\}x\_\{i\}^\{\\top\}\\right\)^\{\-1\}\(7\)µS\\displaystyle\\textmu\_\{S\}=σ−2​ΣS​∑i∈Syi​xi\\displaystyle=\\sigma^\{\-2\}\\Sigma\_\{S\}\\sum\_\{i\\in S\}y\_\{i\}x\_\{i\}\(8\)
Two natural criteria for chosingSSare to minimize the variance of the posteriorθ\\thetaor to minimize the average variance of predictions on test points\{x¯i\}i=1m\\\{\\overline\{x\}\_\{i\}\\\}\_\{i=1\}^\{m\}\(Chaloner and Verdinelli,[1995](https://arxiv.org/html/2607.06642#bib.bib1)\)\. In the first case,

𝔼θ\|S​\[‖θ−𝔼θ\|S​\[θ\]‖2\]=tr​\(ΣS\)\\displaystyle\\mathbb\{E\}\_\{\\theta\|S\}\\left\[\\\|\\theta\-\\mathbb\{E\}\_\{\\theta\|S\}\[\\theta\]\\\|^\{2\}\\right\]=\\mathrm\{tr\}\(\\Sigma\_\{S\}\)\(9\)
In the second case,

1m​∑i=1mVarθ\|S​\[θ⋅x¯i\]=tr​\(ΣS​1m​∑i=1mx¯i​x¯i⊤\)\\displaystyle\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\text\{Var\}\_\{\\theta\|S\}\\left\[\\theta\\cdot\\overline\{x\}\_\{i\}\\right\]=\\mathrm\{tr\}\\left\(\\Sigma\_\{S\}\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\overline\{x\}\_\{i\}\\overline\{x\}\_\{i\}^\{\\top\}\\right\)\(10\)
In both cases, we can write the optimization criteria in the form of Problem Statement[1](https://arxiv.org/html/2607.06642#Thmproblem1)\. For the first criteria, withΛ=Σ0\\Lambda=\\Sigma\_\{0\}andvi=σ−1​xiv\_\{i\}=\\sigma^\{\-1\}x\_\{i\},f​\(S\)=tr​\(σS\)f\(S\)=\\mathrm\{tr\}\(\\sigma\_\{S\}\)\. For the second criteria, ifΣX¯=1m​∑i=1mx¯i​x¯i⊤\\Sigma\_\{\\overline\{X\}\}=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\overline\{x\}\_\{i\}\\overline\{x\}\_\{i\}^\{\\top\}is full\-rank, then withΛ=ΣX¯−1/2​Σ0​ΣX¯−1/2\\Lambda=\\Sigma\_\{\\overline\{X\}\}^\{\-1/2\}\\Sigma\_\{0\}\\Sigma\_\{\\overline\{X\}\}^\{\-1/2\}andvi=σ−1​ΣX¯−1/2​xiv\_\{i\}=\\sigma^\{\-1\}\\Sigma\_\{\\overline\{X\}\}^\{\-1/2\}x\_\{i\},f​\(S\)=tr​\(ΣS​ΣX¯\)f\(S\)=\\mathrm\{tr\}\(\\Sigma\_\{S\}\\Sigma\_\{\\overline\{X\}\}\)\.

Notably, in this case, since the objective value doesn’t depend on the observation valueyiy\_\{i\}, only that it is observed, adaptivity serves no role\. Therefore, active learning in this setting is equivalent to set optimization, removing a source of complexity for algorithmic analysis\.

### 3\.3Optimal Experimental Design

Optimal experimental design is the classical statistical problem of choosing inputs at which to observe a response so as to most accurately estimate a parameter or prediction\(Kiefer,[1959](https://arxiv.org/html/2607.06642#bib.bib8); Fedorov,[2013](https://arxiv.org/html/2607.06642#bib.bib4); Atkinsonet al\.,[2007](https://arxiv.org/html/2607.06642#bib.bib6)\)\. Our goal is to select a setSSof design pointsxix\_\{i\}in a candidate poolX=\{x1,…,xn\}X=\\\{x\_\{1\},\\dots,x\_\{n\}\\\}\. The two design criteria we consider are*A\-optimality*, a frequentist version of minimizing the parameter variance, and*V\-optimality*, a frequentist version of minimizing the prediction variance on a set of points\. Withλ\\lambda\-strength L2 regularization, the A\-optimality criteria istr​\(\(λ​I\+∑i∈Sxi​xi⊤\)−1\)\\mathrm\{tr\}\(\(\\lambda I\+\\sum\_\{i\\in S\}x\_\{i\}x\_\{i\}^\{\\top\}\)^\{\-1\}\)and the V\-optimality criteria for points\{x¯i\}i=1m\\\{\\overline\{x\}\_\{i\}\\\}\_\{i=1\}^\{m\}withL=1m​∑i=1mx¯i​x¯i⊤L=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\overline\{x\}\_\{i\}\\overline\{x\}\_\{i\}^\{\\top\}istr​\(\(λ​I\+∑i∈Sxi​xi⊤\)−1​L\)\\mathrm\{tr\}\(\(\\lambda I\+\\sum\_\{i\\in S\}x\_\{i\}x\_\{i\}^\{\\top\}\)^\{\-1\}L\)\. The positive definite matrixLLencodes the importance of estimation in different parameter directions\.

In both cases, we can write them in our Problem Statement[1](https://arxiv.org/html/2607.06642#Thmproblem1)\. ForAA\-optimaliy,Λ=λ​Id\\Lambda=\\lambda I\_\{d\}andvi=xiv\_\{i\}=x\_\{i\}, and forVV\-optimalityΛ=λ​L−1\\Lambda=\\lambda L^\{\-1\}andvi=L−1/2​xiv\_\{i\}=L^\{\-1/2\}x\_\{i\}\. Solving either exactly under a cardinality constraint is NP\-hard\(Li,[2025](https://arxiv.org/html/2607.06642#bib.bib9)\), motivating both convex\-relaxation\(Allen\-Zhuet al\.,[2021](https://arxiv.org/html/2607.06642#bib.bib11); Nikolovet al\.,[2022](https://arxiv.org/html/2607.06642#bib.bib10)\)and combinatorial approaches\(Madanet al\.,[2019](https://arxiv.org/html/2607.06642#bib.bib12)\)\.

### 3\.4Submodularity, Approximate Submodularity, and Curvature

A set functiong:2\[n\]→ℝg:2^\{\[n\]\}\\to\\mathbb\{R\}is*submodular*if for allS⊆T⊆\[n\]S\\subseteq T\\subseteq\[n\]andi∉Ti\\notin T,

g​\(S∪\{i\}\)−g​\(S\)≥g​\(T∪\{i\}\)−g​\(T\),g\(S\\cup\\\{i\\\}\)\-g\(S\)\\;\\geq\\;g\(T\\cup\\\{i\\\}\)\-g\(T\),the diminishing\-returns property\. The classical theorem ofNemhauseret al\.\([1978](https://arxiv.org/html/2607.06642#bib.bib17)\)states that for monotone submodularggwithg​\(∅\)=0g\(\\emptyset\)=0, greedy achieves a\(1−1/e\)\(1\-1/e\)\-approximation to the cardinality\-constrained maximumS⋆∈arg⁡maxS⊂\[n\],\|S\|=k⁡g​\(S\)S^\{\\star\}\\in\\arg\\max\_\{S\\subset\[n\],\|S\|=k\}g\(S\),

g​\(Sgreedy\)g​\(S⋆\)≥1−1/e\\displaystyle\\frac\{g\(S\_\{\\text\{greedy\}\}\)\}\{g\(S^\{\\star\}\)\}\\geq 1\-1/e\(11\)
For set functions that are not submodular, two parameters quantify whether the set function is approximately submodular\.

Das and Kempe \([2018](https://arxiv.org/html/2607.06642#bib.bib20)\)introduces the*submodularity ratio*,

γ​\(g\)=minS,L⊂\[n\]:S∩L=∅⁡∑i∈S\(g​\(L∪\{i\}\)−g​\(L\)\)g​\(L∪S\)−g​\(L\),\\gamma\(g\)=\\min\_\{S,L\\subset\[n\]:S\\cap L=\\emptyset\}\\frac\{\\sum\_\{i\\in S\}\\big\(g\(L\\cup\\\{i\\\}\)\-g\(L\)\\big\)\}\{g\(L\\cup S\)\-g\(L\)\},\(12\)
A set function is submodular exactly whenγ=1\\gamma=1\.Bianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)defines a*curvature*that bounds the extent to which the marginal gain of an element shrinks as more elements are added

α=1−minS⊂T,i∉T⁡g​\(T∪\{i\}\)−g​\(T\)g​\(S∪\{i\}\)−g​\(S\)\\displaystyle\\alpha=1\-\\min\_\{S\\subset T,i\\not\\in T\}\\frac\{g\(T\\cup\\\{i\\\}\)\-g\(T\)\}\{g\(S\\cup\\\{i\\\}\)\-g\(S\)\}\(13\)
Note thatγ,α∈\[0,1\]\\gamma,\\alpha\\in\[0,1\]\.Bianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)shows that for monotone non\-negativeggwith submodularity ratioγ\\gammaand curvatureα\\alpha, greedy attains a1α​\(1−e−α​γ\)\\frac\{1\}\{\\alpha\}\\bigl\(1\-e^\{\-\\alpha\\gamma\}\\bigr\)\-approximation, recovering the\(1−1/e\)\(1\-1/e\)bound whenγ=α=1\\gamma=\\alpha=1\.

### 3\.5Submodularity and A/V\-Optimal Design

To the best of our knowledge, the only existing approximation guarantees for the greedy algorithm applied to A\-optimal design are found inBianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)andChamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)\. In both cases, the object of analysis is the reduction

Freduction​\(S\)=f​\(∅\)−f​\(S\),F\_\{\\text\{reduction\}\}\(S\)\\;=\\;f\(\\emptyset\)\-f\(S\),\(14\)which is monotone non\-decreasing, satisfiesFreduction​\(∅\)=0F\_\{\\text\{reduction\}\}\(\\emptyset\)=0\.Bianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)provides a bound on the submodularity ratio and curvature, which yields a multiplicative approximation factor forFreductionF\_\{\\text\{reduction\}\}\.Chamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)analysis−Freduction\-F\_\{\\text\{reduction\}\}by their definedα\\alpha\-supermodularity for monotone non\-increasing functions, which can be equivalently defined asα\\alpha\-submodularity\. Intuitively,Chamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)defines theα\\alpha\-submodularity as the minimal ratio of marginal gains as a function of the cardinalities ofSSandTT, and uses it to prove a multiplicative approximation ratio for the greedy algorithm\. They then provide specific values ofα\\alphafor−Freduction\-F\_\{\\text\{reduction\}\}\.

This style of guarantee has a basic limitation: it bounds how much risk has been removed, not how much remains\. Iff​\(∅\)f\(\\emptyset\)is sufficiently large,Freduction​\(Sgreedy\)F\_\{\\text\{reduction\}\}\(S\_\{\\text\{greedy\}\}\)could be within a constant factor ofFreduction​\(S⋆\)F\_\{\\text\{reduction\}\}\(S^\{\\star\}\), while the objective itselff​\(Sgreedy\)f\(S\_\{\\text\{greedy\}\}\)could be an arbitrarily large factor away fromf​\(S⋆\)f\(S^\{\\star\}\)\. For example, iff​\(∅\)=1f\(\\emptyset\)=1,f​\(S⋆\)=ϵf\(S^\{\\star\}\)=\\epsilon, andf​\(Sgreedy\)=12f\(S\_\{\\text\{greedy\}\}\)=\\frac\{1\}\{2\}, thenFreduction​\(Sgreedy\)/Freduction​\(S⋆\)≥1/2F\_\{\\text\{reduction\}\}\(S\_\{\\text\{greedy\}\}\)/F\_\{\\text\{reduction\}\}\(S^\{\\star\}\)\\geq 1/2butf​\(S⋆\)/f​\(Sgreedy\)=2​ϵf\(S^\{\\star\}\)/f\(S\_\{\\text\{greedy\}\}\)=2\\epsilon\. Consequently, prior to the present work, no approximation ratio guarantee on the achieved riskffitself was known for greedy A\- or V\-optimal design\.

## 4Upper Bound

Previous work analyzes the risk reduction functionFreduction​\(S\)=f​\(∅\)−f​\(S\)F\_\{\\text\{reduction\}\}\(S\)=f\(\\emptyset\)\-f\(S\)\. Instead, we focus on the reciprocal risk function,Freciprocal​\(S\)=1/f​\(S\)F\_\{\\text\{reciprocal\}\}\(S\)=1/f\(S\)\. Both these functions are monotonic decreasing functions offf, so the greedy algorithm remains unchanged\. Our main result hinges on a lower bound on the submodularity ratio,

###### Lemma 1\.

The submodularity ratio ofFreciprocalF\_\{\\text\{reciprocal\}\}is bounded asγ​\(Freciprocal\)≥\(1\+hmax\)−1\\gamma\(F\_\{\\text\{reciprocal\}\}\)\\geq\(1\+h\_\{\\text\{max\}\}\)^\{\-1\}

Combined with the result fromDas and Kempe \([2018](https://arxiv.org/html/2607.06642#bib.bib20)\)\(or fromBianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)withα=1\\alpha=1\), we find that,

###### Corollary 1\.

Freciprocal​\(Sgreedy\)Freciprocal​\(S⋆\)≥1−exp⁡\(−\(1\+hmax\)−1\)\\displaystyle\\frac\{F\_\{\\text\{reciprocal\}\}\(S\_\{\\text\{greedy\}\}\)\}\{F\_\{\\text\{reciprocal\}\}\(S^\{\\star\}\)\}\\geq 1\-\\exp\(\-\(1\+h\_\{\\text\{max\}\}\)^\{\-1\}\)\(15\)

The main result then follows from taking the reciprocal of the equation, which yields a complicated expression\. The following algebraic proposition creates a more interpretable bound,

###### Proposition 1\.

For anyh≥0h\\geq 0,

11−exp⁡\(−\(1\+h\)−1\)≤h\+11−1/e≤h\+1\.582\\displaystyle\\frac\{1\}\{1\-\\exp\(\-\(1\+h\)^\{\-1\}\)\}\\leq h\+\\frac\{1\}\{1\-1/e\}\\leq h\+1\.582\(16\)

The proof is in Appendix[A\.1](https://arxiv.org/html/2607.06642#A1.SS1)\. Our main result is then,

###### Theorem 1\.

f​\(Sgreedy\)f​\(S⋆\)≤hmax\+11−1/e\\displaystyle\\frac\{f\(S\_\{\\text\{greedy\}\}\)\}\{f\(S^\{\\star\}\)\}\\leq h\_\{\\text\{max\}\}\+\\frac\{1\}\{1\-1/e\}\(17\)

Thus, greedy acheives a risk approximation guarantee ofhmax\+1\.582h\_\{\\text\{max\}\}\+1\.582, which scales linearly in the Maximum Initial Leverage Score \(MILS\)\.

### 4\.1Tightness of Approximate Submodularity

In this section, we show that our bound onγ\\gammais tight and that the curvature is arbitrarily close to11\. Note that approximate submodularity and curvature don’t depend on the budgetkkso we drop these from the following statements\.

###### Proposition 2\.

For anyn∈ℕn\\in\\mathbb\{N\}andh\>0h\>0, there exists a problem withnnvectors,hmax=hh\_\{\\text\{max\}\}=handd=nd=ndimensions, such that the submodularity ratio isγ​\(Freciprocal\)≤1\(1\+h\)−hn\\gamma\(F\_\{\\text\{reciprocal\}\}\)\\leq\\frac\{1\}\{\(1\+h\)\-\\frac\{h\}\{n\}\}

The proof is in Appendix[A\.2](https://arxiv.org/html/2607.06642#A1.SS2)\. Note that asn→∞n\\rightarrow\\infty,γ→\(1\+hmax\)−1\\gamma\\rightarrow\(1\+h\_\{\\text\{max\}\}\)^\{\-1\}implying that Theorem[1](https://arxiv.org/html/2607.06642#Thmlemma1)is tight \(when examining all values ofnn\)\. Also, note that for allh\>0h\>0andd≥2d\\geq 2, the submodularity ratio is strictly less than11, soFreciprocalF\_\{\\text\{reciprocal\}\}is not submodular\(Das and Kempe,[2018](https://arxiv.org/html/2607.06642#bib.bib20)\)\. Furthermore, the curvatureα\\alphaforFreciprocalF\_\{\\text\{reciprocal\}\}is not in general bounded away from11, so the more refined analysis using curvature\(Bianet al\.,[2017](https://arxiv.org/html/2607.06642#bib.bib18)\)doesn’t provide an improvement\.

###### Proposition 3\.

For anyn∈ℕn\\in\\mathbb\{N\}andh\>0h\>0, there exists a problem withnnvectors,hmax=hh\_\{\\text\{max\}\}=h, andd=2d=2where the curvature ofFreciprocalF\_\{\\text\{reciprocal\}\}is greater than1−\(11\+\(n−1\)​h2\)21\-\\left\(\\frac\{1\}\{1\+\\frac\{\(n\-1\)h\}\{2\}\}\\right\)^\{2\}

The proof is in Appendix[A\.3](https://arxiv.org/html/2607.06642#A1.SS3)\. Note the curvature approaches11asn→∞n\\rightarrow\\infty\.

### 4\.2Proof of Lemma[1](https://arxiv.org/html/2607.06642#Thmlemma1)

In this section, we prove Lemma[1](https://arxiv.org/html/2607.06642#Thmlemma1)to by showingFreciprocalF\_\{\\text\{reciprocal\}\}is approximately submodular\. First, we prove a specific matrix identity\.

###### Lemma 2\.

For any symmetric positive definite matrixAAand symmetric positive semi\-definite matrixBB

tr\(A−1\)−tr\(\(A\+B\)\)−1\)≤tr​\(A−1​B​A−1\)​tr​\(\(A\+B\)−1\)tr​\(A−1\)\\displaystyle\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\-\\mathrm\{tr\}\\left\(\\left\(A\+B\)\\right\)^\{\-1\}\\right\)\\leq\\frac\{\\mathrm\{tr\}\\left\(A^\{\-1\}BA^\{\-1\}\\right\)\\mathrm\{tr\}\\left\(\\left\(A\+B\\right\)^\{\-1\}\\right\)\}\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\}\(18\)

###### Proof\.

From the matrix version of the Cauchy–Schwarz inequality,

tr​\(XT​Y\)2≤tr​\(XT​X\)​tr​\(YT​Y\)\\displaystyle\\mathrm\{tr\}\\left\(X^\{T\}Y\\right\)^\{2\}\\leq\\mathrm\{tr\}\\left\(X^\{T\}X\\right\)\\mathrm\{tr\}\\left\(Y^\{T\}Y\\right\)\(19\)
LetX=\(A\+B\)−1/2X=\(A\+B\)^\{\-1/2\}andY=\(A\+B\)1/2​A−1Y=\(A\+B\)^\{1/2\}A^\{\-1\}\.

tr​\(A−1\)2\\displaystyle\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)^\{2\}≤tr​\(\(A\+B\)−1\)​tr​\(A−1​\(A\+B\)​A−1\)\\displaystyle\\leq\\mathrm\{tr\}\\left\(\(A\+B\\right\)^\{\-1\}\)\\mathrm\{tr\}\\left\(A^\{\-1\}\(A\+B\)A^\{\-1\}\\right\)\(20\)=tr​\(\(A\+B\)−1\)​\[tr​\(A−1\)\+tr​\(A−1​B​A−1\)\]\\displaystyle=\\mathrm\{tr\}\\left\(\(A\+B\)^\{\-1\}\\right\)\\left\[\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\+\\mathrm\{tr\}\\left\(A^\{\-1\}BA^\{\-1\}\\right\)\\right\]\(21\)
Dividing both sides bytr​\(A−1\)\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)and subtractingtr​\(\(A\+B\)−1\)\\mathrm\{tr\}\\left\(\(A\+B\)^\{\-1\}\\right\)from both sides yields the result\. ∎

The following lemma is a restated version of Lemma[1](https://arxiv.org/html/2607.06642#Thmlemma1)in different notation withγ​\(Freciprocal\)\\gamma\(F\_\{\\text\{reciprocal\}\}\)written out\.

###### Lemma[1](https://arxiv.org/html/2607.06642#Thmlemma1)\(restated\)\.

For anyL,S⊂\[n\]L,S\\subset\[n\]withL∩S=∅L\\cap S=\\emptyset,

∑i∈SFreciprocal​\(L∪\{i\}\)−Freciprocal​\(L\)Freciprocal​\(L∪S\)−Freciprocal​\(L\)≥\(1\+hmax\)−1\\displaystyle\\frac\{\\sum\_\{i\\in S\}F\_\{\\text\{reciprocal\}\}\(L\\cup\\\{i\\\}\)\-F\_\{\\text\{reciprocal\}\}\(L\)\}\{F\_\{\\text\{reciprocal\}\}\(L\\cup S\)\-F\_\{\\text\{reciprocal\}\}\(L\)\}\\geq\(1\+h\_\{\\text\{max\}\}\)^\{\-1\}\\\(22\)

###### Proof\.

DefineA=Λ\+∑i∈Lvi​vi⊤A=\\Lambda\+\\sum\_\{i\\in L\}v\_\{i\}v\_\{i\}^\{\\top\}andB=∑i∈Svi​vi⊤B=\\sum\_\{i\\in S\}v\_\{i\}v\_\{i\}^\{\\top\}\.

Freciprocal​\(L∪S\)−Freciprocal​\(L\)\\displaystyle F\_\{\\text\{reciprocal\}\}\(L\\cup S\)\-F\_\{\\text\{reciprocal\}\}\(L\)=1f​\(L∪S\)−1f​\(L\)\\displaystyle=\\frac\{1\}\{f\(L\\cup S\)\}\-\\frac\{1\}\{f\(L\)\}\(23\)=Tr​\(A−1\)−Tr​\(\(A\+B\)−1\)Tr​\(A−1\)​Tr​\(\(A\+B\)−1\)\\displaystyle=\\frac\{\\text\{Tr\}\(A^\{\-1\}\)\-\\text\{Tr\}\(\(A\+B\)^\{\-1\}\)\}\{\\text\{Tr\}\(A^\{\-1\}\)\\text\{Tr\}\(\(A\+B\)^\{\-1\}\)\}\(24\)≤Tr​\(A−1​B​A−1\)Tr​\(A−1\)2\\displaystyle\\leq\\frac\{\\text\{Tr\}\(A^\{\-1\}BA^\{\-1\}\)\}\{\\text\{Tr\}\(A^\{\-1\}\)^\{2\}\}\(25\)=∑i∈Str​\(A−1​vi​vi⊤​A−1\)tr​\(A−1\)2\\displaystyle=\\sum\_\{i\\in S\}\\frac\{\\mathrm\{tr\}\\left\(A^\{\-1\}v\_\{i\}v\_\{i\}^\{\\top\}A^\{\-1\}\\right\)\}\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)^\{2\}\}\(26\)≤∑i∈S\(1\+hmax\)1\+vi⊤​A−1​vi​tr​\(A−1​vi​vi⊤​A−​1\)tr​\(A−1\)2\\displaystyle\\leq\\sum\_\{i\\in S\}\\frac\{\(1\+h\_\{\\text\{max\}\}\)\}\{1\+v\_\{i\}^\{\\top\}A^\{\-1\}v\_\{i\}\}\\frac\{\\mathrm\{tr\}\\left\(A^\{\-1\}v\_\{i\}v\_\{i\}^\{\\top\}A^\{\-\}1\\right\)\}\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)^\{2\}\}\(27\)=\(1\+hmax\)​∑i∈Str​\(A−1\)−tr​\(\(A\+vi​vi⊤\)−1\)tr​\(A−1\)2\\displaystyle=\(1\+h\_\{\\text\{max\}\}\)\\sum\_\{i\\in S\}\\frac\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\-\\mathrm\{tr\}\\left\(\(A\+v\_\{i\}v\_\{i\}^\{\\top\}\\right\)^\{\-1\}\)\}\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)^\{2\}\}\(28\)≤\(1\+hmax\)​∑i∈Str​\(A−1\)−tr​\(\(A\+vi​vi⊤\)−1\)tr​\(A−1\)​tr​\(\(A\+vi​vi⊤\)−1\)\\displaystyle\\leq\(1\+h\_\{\\text\{max\}\}\)\\sum\_\{i\\in S\}\\frac\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\-\\mathrm\{tr\}\\left\(\(A\+v\_\{i\}v\_\{i\}^\{\\top\}\\right\)^\{\-1\}\)\}\{\\mathrm\{tr\}\\left\(A^\{\-1\}\\right\)\\mathrm\{tr\}\\left\(\(A\+v\_\{i\}v\_\{i\}^\{\\top\}\)^\{\-1\}\\right\)\}\(29\)=\(1\+hmax\)​∑i∈S1f​\(L∪\{i\}\)−1f​\(L\)\\displaystyle=\(1\+h\_\{\\text\{max\}\}\)\\sum\_\{i\\in S\}\\frac\{1\}\{f\(L\\cup\\\{i\\\}\)\}\-\\frac\{1\}\{f\(L\)\}\(30\)=\(1\+hmax\)​∑i∈SFreciprocal​\(L∪\{i\}\)−Freciprocal​\(L\)\\displaystyle=\(1\+h\_\{\\text\{max\}\}\)\\sum\_\{i\\in S\}F\_\{\\text\{reciprocal\}\}\(L\\cup\\\{i\\\}\)\-F\_\{\\text\{reciprocal\}\}\(L\)\(31\)
The lines follow from: definition ofFreciprocalF\_\{\\text\{reciprocal\}\}, definition offfand finding a common denominator, Lemma[2](https://arxiv.org/html/2607.06642#Thmlemma2), linearity ofBBandtr\\mathrm\{tr\}, definition ofhmaxh\_\{\\text\{max\}\}and monotonicity ofX−1X^\{\-1\}for symmetric positive definite matrices, the Sherman\-Morrison formula, the monotonicity ofX−1X^\{\-1\}for symmetric positive definite matrices, simplifying fractions and definition offf, and definition ofFreciprocalF\_\{\\text\{reciprocal\}\}\. Finally, rearranging terms yields the result\. ∎

## 5Lower Bound

We now construct an explicit problem showing that the upper bound is tight up to constants\.

###### Theorem 2\.

For anyh\>0h\>0andd≥4d\\geq 4, if there exists an orderddHadamard matrix, then there exists add\-dimensional problem withn=2​dn=2dvectors such thathmax=max⁡\(h,4\)h\_\{\\text\{max\}\}=\\max\(h,4\)and for a cardinality constraint ofk=dk=d,

f​\(Sgreedy\)f​\(S⋆\)≥1\+h5\\displaystyle\\frac\{f\(S\_\{\\text\{greedy\}\}\)\}\{f\(S^\{\\star\}\)\}\\geq\\frac\{1\+h\}\{5\}\(32\)

The proof is in Appendix[B](https://arxiv.org/html/2607.06642#A2)\. Note that by using Sylvester’s construction, there are Hadamard matrices for any order that is a power of22\. To make it explicit, the example ford=4d=4is

Λ\\displaystyle\\char 76\\relax=\[exp⁡\(04\)0000exp⁡\(14\)0000exp⁡\(24\)0000exp⁡\(34\)\]\\displaystyle=\\begin\{bmatrix\}\\exp\\left\(\\frac\{0\}\{4\}\\right\)&0&0&0\\\\ 0&\\exp\\left\(\\frac\{1\}\{4\}\\right\)&0&0\\\\ 0&0&\\exp\\left\(\\frac\{2\}\{4\}\\right\)&0\\\\ 0&0&0&\\exp\\left\(\\frac\{3\}\{4\}\\right\)\\end\{bmatrix\}v1\\displaystyle v\_\{1\}=\[2​exp⁡\(08\)000\]\\displaystyle=\\begin\{bmatrix\}2\\exp\\left\(\\frac\{0\}\{8\}\\right\)&0&0&0\\end\{bmatrix\}v2\\displaystyle v\_\{2\}=\[02​exp⁡\(18\)00\]\\displaystyle=\\begin\{bmatrix\}0&2\\exp\\left\(\\frac\{1\}\{8\}\\right\)&0&0\\end\{bmatrix\}v3\\displaystyle v\_\{3\}=\[002​exp⁡\(28\)0\]\\displaystyle=\\begin\{bmatrix\}0&0&2\\exp\\left\(\\frac\{2\}\{8\}\\right\)&0\\end\{bmatrix\}v4\\displaystyle v\_\{4\}=\[0002​exp⁡\(38\)\]\\displaystyle=\\begin\{bmatrix\}0&0&0&2\\exp\\left\(\\frac\{3\}\{8\}\\right\)\\end\{bmatrix\}v5\\displaystyle v\_\{5\}=\[h​exp⁡\(08\)2h​exp⁡\(18\)2h​exp⁡\(28\)2h​exp⁡\(38\)2\]\\displaystyle=\\begin\{bmatrix\}\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{0\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{1\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{2\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{3\}\{8\}\\right\)\}\{2\}\\end\{bmatrix\}v6\\displaystyle v\_\{6\}=\[h​exp⁡\(08\)2−h​exp⁡\(18\)2h​exp⁡\(28\)2−h​exp⁡\(38\)2\]\\displaystyle=\\begin\{bmatrix\}\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{0\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{1\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{2\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{3\}\{8\}\\right\)\}\{2\}\\end\{bmatrix\}v7\\displaystyle v\_\{7\}=\[h​exp⁡\(08\)2h​exp⁡\(18\)2−h​exp⁡\(28\)2−h​exp⁡\(38\)2\]\\displaystyle=\\begin\{bmatrix\}\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{0\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{1\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{2\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{3\}\{8\}\\right\)\}\{2\}\\end\{bmatrix\}v8\\displaystyle v\_\{8\}=\[h​exp⁡\(08\)2−h​exp⁡\(18\)2−h​exp⁡\(28\)2h​exp⁡\(38\)2\]\\displaystyle=\\begin\{bmatrix\}\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{0\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{1\}\{8\}\\right\)\}\{2\}&\-\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{2\}\{8\}\\right\)\}\{2\}&\\frac\{\\sqrt\{h\}\\exp\\left\(\\frac\{3\}\{8\}\\right\)\}\{2\}\\end\{bmatrix\}
where the greedy algorithm will choose\{1,2,3,4\}\\\{1,2,3,4\\\}which is outperformed by choosing\{5,6,7,8\}\\\{5,6,7,8\\\}\.

We ran numerical experiments forh=10,100,1000h=10,100,1000confirming thathmax=10,100,1000h\_\{\\text\{max\}\}=10,100,1000andf​\(Sg\)f​\(S∗\)=115,1015,10015\\frac\{f\(S\_\{g\}\)\}\{f\(S^\{\*\}\)\}=\\frac\{11\}\{5\},\\frac\{101\}\{5\},\\frac\{1001\}\{5\}\. The code snippet and output is shown in Appendix[C](https://arxiv.org/html/2607.06642#A3)\.

While Theorem[2](https://arxiv.org/html/2607.06642#Thmtheorem2)is stated with simple constants, in Appendix[B](https://arxiv.org/html/2607.06642#A2), we prove a slightly more general result which yields slightly better constants for largedd\. From numerical results, it appears our construction cannot yield examples with approximation ratios lower than1\+h3\.23\\frac\{1\+h\}\{3\.23\}\.

## 6Illustrative Numerical Example

For illustration of our bounds, we consider a simple setting withΛ=Id\\Lambda=I\_\{d\}andxix\_\{i\}drawn uniformly from the unit sphereSd−1S^\{d\-1\}\. We then run greedy withd=20d=20,n=1000n=1000, andk∈\[100\]k\\in\[100\]\. For each iteration, we can compute a bound onf​\(S⋆\)f\(S^\{\\star\}\)\. For an approximation ratio lower bound ofcconFreciprocalF\_\{\\text\{reciprocal\}\}\(e\.g\., Theorem[1](https://arxiv.org/html/2607.06642#Thmlemma1)\),

f​\(S⋆\)≥c​f​\(Sgreedy\)\\displaystyle f\(S^\{\\star\}\)\\geq cf\(S\_\{\\text\{greedy\}\}\)\(33\)
For an approximation ratio lower bound ofcconFreductionF\_\{\\text\{reduction\}\}, \(e\.g\., as inBianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)orChamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)\),

f​\(S⋆\)≥f​\(∅\)−f​\(∅\)−f​\(Sgreedy\)c\\displaystyle f\(S^\{\\star\}\)\\geq f\(\\emptyset\)\-\\frac\{f\(\\emptyset\)\-f\(S\_\{\\text\{greedy\}\}\)\}\{c\}\(34\)
This experiment was implemented \(code and results in Appendix[D](https://arxiv.org/html/2607.06642#A4)\) and the results are shown in Figure[1](https://arxiv.org/html/2607.06642#S6.F1)\. We can see that the bound based onFreductionF\_\{\\text\{reduction\}\}fromChamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)becomes vacuous aroundk=10k=10\. The numerical results conclude that the bound fromBianet al\.\([2017](https://arxiv.org/html/2607.06642#bib.bib18)\)\(not shown in figure\) is vacuous even fork=1k=1due to theγ\\gammaandα\\alphabounds being very close to0and11, respectively\.

Figure 1:The objective value of the greedy algorithm and the lower bound on the optimal objective from Theorem[1](https://arxiv.org/html/2607.06642#Thmlemma1)andChamon and Ribeiro \([2017](https://arxiv.org/html/2607.06642#bib.bib19)\)\.
## 7Discussion

The results in this work not only provide the firstA/VA/V\-optimality criteria approximation ratio guarantee \(not on the reduction\) for the common greedy heuristic, but addresses a more fundamental question in active learning\. Nearly all active learning algorithms avoid planning over multiple data labeling iterations by focusing only on the current data labeling iteration\. To our knowledge, there is no existing guarantee on the test loss approximation ratio for myopic algorithms\. Here, for Bayesian Logistic Regression, that myopic data labeling nearly matches fully planned data labeling, at least when the MILS is small\. We hope this work serves as a foundation for future analyses of other models, especially those where adaptive selection is not equivalent to offline selection\.

## References

- Z\. Allen\-Zhu, Y\. Li, A\. Singh, and Y\. Wang \(2021\)Near\-optimal discrete optimization for experimental design: a regret minimization approach\.Mathematical Programming186\(1\),pp\. 439–478\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p2.6)\.
- A\. Atkinson, A\. Donev, and R\. Tobias \(2007\)Optimum experimental designs, with sas\.Vol\.34,OUP Oxford\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p1.9)\.
- A\. A\. Bian, J\. M\. Buhmann, A\. Krause, and S\. Tschiatschek \(2017\)Guarantees for greedy maximization of non\-submodular functions with applications\.InProceedings of the 34th International Conference on Machine Learning,D\. Precup and Y\. W\. Teh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.70,pp\. 498–507\.External Links:[Link](https://proceedings.mlr.press/v70/bian17a.html)Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p3.1),[§3\.4](https://arxiv.org/html/2607.06642#S3.SS4.p4.1),[§3\.4](https://arxiv.org/html/2607.06642#S3.SS4.p6.7),[§3\.5](https://arxiv.org/html/2607.06642#S3.SS5.p1.10),[§3\.5](https://arxiv.org/html/2607.06642#S3.SS5.p1.11),[§4\.1](https://arxiv.org/html/2607.06642#S4.SS1.p2.10),[§4](https://arxiv.org/html/2607.06642#S4.p2.1),[§6](https://arxiv.org/html/2607.06642#S6.p2.2),[§6](https://arxiv.org/html/2607.06642#S6.p3.7)\.
- C\. M\. Bishop \(2006\)Pattern recognition and machine learning\.Springer\.Cited by:[§3\.2](https://arxiv.org/html/2607.06642#S3.SS2.p1.3)\.
- K\. Chaloner and I\. Verdinelli \(1995\)Bayesian experimental design: a review\.Statistical science,pp\. 273–304\.Cited by:[§3\.2](https://arxiv.org/html/2607.06642#S3.SS2.p3.3)\.
- L\. Chamon and A\. Ribeiro \(2017\)Approximate supermodularity bounds for experimental design\.Advances in Neural Information Processing Systems30\.Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p3.1),[§3\.5](https://arxiv.org/html/2607.06642#S3.SS5.p1.10),[§3\.5](https://arxiv.org/html/2607.06642#S3.SS5.p1.11),[Figure 1](https://arxiv.org/html/2607.06642#S6.F1),[§6](https://arxiv.org/html/2607.06642#S6.p2.2),[§6](https://arxiv.org/html/2607.06642#S6.p3.7)\.
- A\. Das and D\. Kempe \(2018\)Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection\.Journal of Machine Learning Research19\(3\),pp\. 1–34\.Cited by:[1st item](https://arxiv.org/html/2607.06642#S1.I1.i1.p1.1),[§3\.4](https://arxiv.org/html/2607.06642#S3.SS4.p3.1),[§4\.1](https://arxiv.org/html/2607.06642#S4.SS1.p2.10),[§4](https://arxiv.org/html/2607.06642#S4.p2.1)\.
- V\. V\. Fedorov \(2013\)Theory of optimal experiments\.Elsevier\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p1.9)\.
- Y\. Gal, R\. Islam, and Z\. Ghahramani \(2017\)Deep bayesian active learning with image data\.InInternational conference on machine learning,pp\. 1183–1192\.Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p2.1),[§3\.1](https://arxiv.org/html/2607.06642#S3.SS1.p1.1)\.
- J\. Kiefer \(1959\)Optimum experimental designs\.Journal of the Royal Statistical Society: Series B \(Methodological\)21\(2\),pp\. 272–304\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p1.9)\.
- A\. Kirsch, J\. Van Amersfoort, and Y\. Gal \(2019\)Batchbald: efficient and diverse batch acquisition for deep bayesian active learning\.Advances in neural information processing systems32\.Cited by:[§3\.1](https://arxiv.org/html/2607.06642#S3.SS1.p1.1)\.
- Y\. Li \(2025\)Strong formulations and algorithms for regularized a\-optimal design\.arXiv preprint arXiv:2505\.14957\.Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p2.1),[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p2.6)\.
- D\. J\. MacKay \(1992\)Information\-based objective functions for active data selection\.Neural computation4\(4\),pp\. 590–604\.Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p2.1)\.
- V\. Madan, M\. Singh, U\. Tantipongpipat, and W\. Xie \(2019\)Combinatorial algorithms for optimal design\.InConference on Learning Theory,pp\. 2210–2258\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p2.6)\.
- K\. P\. Murphy \(2023\)Probabilistic machine learning: advanced topics\.MIT Press\.External Links:[Link](http://probml.github.io/book2)Cited by:[§3\.2](https://arxiv.org/html/2607.06642#S3.SS2.p1.3)\.
- S\. Mussmann, J\. Reisler, D\. Tsai, E\. Mousavi, S\. O’Brien, and M\. Goldszmidt \(2022\)Active learning with expected error reduction\.arXiv preprint arXiv:2211\.09283\.Cited by:[§3\.1](https://arxiv.org/html/2607.06642#S3.SS1.p1.1)\.
- G\. L\. Nemhauser, L\. A\. Wolsey, and M\. L\. Fisher \(1978\)An analysis of approximations for maximizing submodular set functions—i\.Mathematical programming14\(1\),pp\. 265–294\.Cited by:[§3\.4](https://arxiv.org/html/2607.06642#S3.SS4.p1.7)\.
- A\. Nikolov, M\. Singh, and U\. Tantipongpipat \(2022\)Proportional volume sampling and approximation algorithms for a\-optimal design\.Mathematics of Operations Research47\(2\),pp\. 847–877\.Cited by:[§3\.3](https://arxiv.org/html/2607.06642#S3.SS3.p2.6)\.
- F\. B\. Smith, A\. Kirsch, S\. Farquhar, Y\. Gal, A\. Foster, and T\. Rainforth \(2023\)Prediction\-oriented bayesian active learning\.InInternational conference on artificial intelligence and statistics,pp\. 7331–7348\.Cited by:[§1](https://arxiv.org/html/2607.06642#S1.p2.1),[§3\.1](https://arxiv.org/html/2607.06642#S3.SS1.p1.1)\.

## Appendix AUpper Bound Details

### A\.1Proof of Proposition[1](https://arxiv.org/html/2607.06642#Thmproposition1)

###### Proposition[1](https://arxiv.org/html/2607.06642#Thmproposition1)\.

For anyh≥0h\\geq 0,

11−exp⁡\(−\(1\+h\)−1\)≤h\+11−1/e≤h\+1\.582\\displaystyle\\frac\{1\}\{1\-\\exp\(\-\(1\+h\)^\{\-1\}\)\}\\leq h\+\\frac\{1\}\{1\-1/e\}\\leq h\+1\.582\(35\)

###### Proof\.

Letg​\(h\)=11−exp⁡\(−\(1\+h\)−1\)g\(h\)=\\frac\{1\}\{1\-\\exp\(\-\(1\+h\)^\{\-1\}\)\}forh≥0h\\geq 0\. Then,

g′​\(h\)\\displaystyle g^\{\\prime\}\(h\)=exp⁡\(−1/\(1\+h\)\)\(1−exp⁡\(−1/\(1\+h\)\)\)2​1\(1\+h\)2\\displaystyle=\\frac\{\\exp\(\-1/\(1\+h\)\)\}\{\(1\-\\exp\(\-1/\(1\+h\)\)\)^\{2\}\}\\frac\{1\}\{\(1\+h\)^\{2\}\}\(36\)=\(12​\(1\+h\)\)2sinh2⁡\(12​\(1\+h\)\)\\displaystyle=\\frac\{\\left\(\\frac\{1\}\{2\(1\+h\)\}\\right\)^\{2\}\}\{\\sinh^\{2\}\\left\(\\frac\{1\}\{2\(1\+h\)\}\\right\)\}\(37\)≤1\\displaystyle\\leq 1\(38\)
The last line follows since forx\>0x\>0,sinh⁡\(x\)≥x\\sinh\(x\)\\geq x111Note thatsinh⁡\(0\)=0\\sinh\(0\)=0andsinh′⁡\(x\)=cosh⁡\(x\)≥1\\sinh^\{\\prime\}\(x\)=\\cosh\(x\)\\geq 1\.

Thus,g​\(h\)−hg\(h\)\-his non\-increasing and so

g​\(h\)≤h\+g​\(0\)=h\+11−1/e\\displaystyle g\(h\)\\leq h\+g\(0\)=h\+\\frac\{1\}\{1\-1/e\}\(39\)∎

### A\.2Proof of Proposition[2](https://arxiv.org/html/2607.06642#Thmproposition2)

###### Proposition[2](https://arxiv.org/html/2607.06642#Thmproposition2)\.

For anyn∈ℕn\\in\\mathbb\{N\}andh\>0h\>0, there exists a problem withnnvectors,hmax=hh\_\{\\text\{max\}\}=handd=nd=ndimensions, such that the submodularity ratio isγ​\(Freciprocal\)≤1\(1\+h\)−hn\\gamma\(F\_\{\\text\{reciprocal\}\}\)\\leq\\frac\{1\}\{\(1\+h\)\-\\frac\{h\}\{n\}\}

###### Proof\.

LetΛ=1h​In\\Lambda=\\frac\{1\}\{h\}I\_\{n\}andvi=eiv\_\{i\}=e\_\{i\}for alli∈\[n\]i\\in\[n\]\.

Note that11h\+1=h1\+h\\frac\{1\}\{\\frac\{1\}\{h\}\+1\}=\\frac\{h\}\{1\+h\}

Freciprocal​\(∅\)\\displaystyle F\_\{\\text\{reciprocal\}\}\(\\emptyset\)=1n​h\\displaystyle=\\frac\{1\}\{nh\}\(40\)Freciprocal​\(\{i\}\)\\displaystyle F\_\{\\text\{reciprocal\}\}\(\\\{i\\\}\)=1\(n−1\)​h\+h1\+h\\displaystyle=\\frac\{1\}\{\(n\-1\)h\+\\frac\{h\}\{1\+h\}\}\(41\)Freciprocal​\(\[n\]\)\\displaystyle F\_\{\\text\{reciprocal\}\}\(\[n\]\)=1\+hn​h\\displaystyle=\\frac\{1\+h\}\{nh\}\(42\)
Taking the differences,

Freciprocal​\(\[n\]\)−Freciprocal​\(∅\)\\displaystyle F\_\{\\text\{reciprocal\}\}\(\[n\]\)\-F\_\{\\text\{reciprocal\}\}\(\\emptyset\)=1n\\displaystyle=\\frac\{1\}\{n\}\(44\)∑i=1nFreciprocal​\(\{i\}\)−Freciprocal​\(∅\)\\displaystyle\\sum\_\{i=1\}^\{n\}F\_\{\\text\{reciprocal\}\}\(\\\{i\\\}\)\-F\_\{\\text\{reciprocal\}\}\(\\emptyset\)=n​\(1\(n−1\)​h\+h1\+h−1n​h\)\\displaystyle=n\\left\(\\frac\{1\}\{\(n\-1\)h\+\\frac\{h\}\{1\+h\}\}\-\\frac\{1\}\{nh\}\\right\)\(45\)=1h−h2n​\(1\+h\)−1h\\displaystyle=\\frac\{1\}\{h\-\\frac\{h^\{2\}\}\{n\(1\+h\)\}\}\-\\frac\{1\}\{h\}\(46\)=h2n​\(1\+h\)h2−h3n​\(1\+h\)\\displaystyle=\\frac\{\\frac\{h^\{2\}\}\{n\(1\+h\)\}\}\{h^\{2\}\-\\frac\{h^\{3\}\}\{n\(1\+h\)\}\}\(47\)=1n​\(1\+h\)−h\\displaystyle=\\frac\{1\}\{n\(1\+h\)\-h\}\(48\)
Taking the ratio,

γ​\(Freciprocal\)\\displaystyle\\char 103\\relax\(F\_\{\\text\{reciprocal\}\}\)≤∑i=1nFreciprocal​\(\{i\}\)−Freciprocal​\(∅\)Freciprocal​\(\[n\]\)−Freciprocal​\(∅\)\\displaystyle\\leq\\frac\{\\sum\_\{i=1\}^\{n\}F\_\{\\text\{reciprocal\}\}\(\\\{i\\\}\)\-F\_\{\\text\{reciprocal\}\}\(\\emptyset\)\}\{F\_\{\\text\{reciprocal\}\}\(\[n\]\)\-F\_\{\\text\{reciprocal\}\}\(\\emptyset\)\}\(49\)=nn​\(1\+h\)−h\\displaystyle=\\frac\{n\}\{n\(1\+h\)\-h\}\(50\)=1\(1\+h\)−hn\\displaystyle=\\frac\{1\}\{\(1\+h\)\-\\frac\{h\}\{n\}\}\(51\)∎

### A\.3Proof of Proposition[3](https://arxiv.org/html/2607.06642#Thmproposition3)

###### Proposition[3](https://arxiv.org/html/2607.06642#Thmproposition3)\.

For anyn∈ℕn\\in\\mathbb\{N\}andh\>0h\>0, there exists a problem withnnvectors,hmax=hh\_\{\\text\{max\}\}=h, andd=2d=2where the curvature ofFreciprocalF\_\{\\text\{reciprocal\}\}is greater than1−\(11\+\(n−1\)​h2\)21\-\\left\(\\frac\{1\}\{1\+\\frac\{\(n\-1\)h\}\{2\}\}\\right\)^\{2\}

###### Proof\.

For convenience, definem=n−1m=n\-1\. LetΛ=1h​e1​e1⊤\+\(1h\+m\)​e2​e2⊤\\Lambda=\\frac\{1\}\{h\}e\_\{1\}e\_\{1\}^\{\\top\}\+\\left\(\\frac\{1\}\{h\}\+m\\right\)e\_\{2\}e\_\{2\}^\{\\top\}\. Definevi=e1v\_\{i\}=e\_\{1\}for1≤i≤m1\\leq i\\leq mandvm\+1=e2v\_\{m\+1\}=e\_\{2\}and \. Then,

f0:=f​\(∅\)\\displaystyle f\_\{0\}:=f\(\\emptyset\)=11h\+m\+11h=h1\+m​h​\(2\+m​h\)\\displaystyle=\\frac\{1\}\{\\frac\{1\}\{h\}\+m\}\+\\frac\{1\}\{\\frac\{1\}\{h\}\}=\\frac\{h\}\{1\+mh\}\(2\+mh\)\(52\)f1:=f​\(\{m\+1\}\)\\displaystyle f\_\{1\}:=f\(\\\{m\+1\\\}\)=11h\+m\+1\+11h=h1\+m​h\+h​\(2\+m​h\+h\)\\displaystyle=\\frac\{1\}\{\\frac\{1\}\{h\}\+m\+1\}\+\\frac\{1\}\{\\frac\{1\}\{h\}\}=\\frac\{h\}\{1\+mh\+h\}\(2\+mh\+h\)\(53\)fm:=f​\(\[m\]\)\\displaystyle f\_\{m\}:=f\(\[m\]\)=11h\+m\+11h\+m=h1\+m​h⋅2\\displaystyle=\\frac\{1\}\{\\frac\{1\}\{h\}\+m\}\+\\frac\{1\}\{\\frac\{1\}\{h\}\+m\}=\\frac\{h\}\{1\+mh\}\\cdot 2\(54\)fm\+1:=f​\(\[m\+1\]\)\\displaystyle f\_\{m\+1\}:=f\(\[m\+1\]\)=11h\+m\+1\+11h\+m=h1\+m​h\+h​\(2\+h1\+m​h\)\\displaystyle=\\frac\{1\}\{\\frac\{1\}\{h\}\+m\+1\}\+\\frac\{1\}\{\\frac\{1\}\{h\}\+m\}=\\frac\{h\}\{1\+mh\+h\}\\left\(2\+\\frac\{h\}\{1\+mh\}\\right\)\(55\)
The curvature is at least

α\\displaystyle\\alpha≥1−Freciprocal​\(\{m\+1\}\)−Freciprocal​\(∅\)Freciprocal​\(\[m\+1\]\)−Freciprocal​\(\[m\]\)\\displaystyle\\geq 1\-\\frac\{F\_\{\\text\{reciprocal\}\}\(\\\{m\+1\\\}\)\-F\_\{\\text\{reciprocal\}\}\(\\emptyset\)\}\{F\_\{\\text\{reciprocal\}\}\(\[m\+1\]\)\-F\_\{\\text\{reciprocal\}\}\(\[m\]\)\}\(57\)=1−1/f1−1/f01/fm\+1−1/fm\\displaystyle=1\-\\frac\{1/f\_\{1\}\-1/f\_\{0\}\}\{1/f\_\{m\+1\}\-1/f\_\{m\}\}\(58\)=1−f0−f1fm−fm\+1​fm​fm\+1f0​f1\\displaystyle=1\-\\frac\{f\_\{0\}\-f\_\{1\}\}\{f\_\{m\}\-f\_\{m\+1\}\}\\frac\{f\_\{m\}f\_\{m\+1\}\}\{f\_\{0\}f\_\{1\}\}\(59\)
Becausef0−f1=11h\+m−11h\+m\+1=fn−fn\+1f\_\{0\}\-f\_\{1\}=\\frac\{1\}\{\\frac\{1\}\{h\}\+m\}\-\\frac\{1\}\{\\frac\{1\}\{h\}\+m\+1\}=f\_\{n\}\-f\_\{n\+1\},

α\\displaystyle\\alpha≥1−fn​fn\+1f0​f1\\displaystyle\\geq 1\-\\frac\{f\_\{n\}f\_\{n\+1\}\}\{f\_\{0\}f\_\{1\}\}\(60\)=1−2​\(2\+h1\+m​h\)\(2\+m​h\)​\(2\+m​h\+h\)\\displaystyle=1\-\\frac\{2\\left\(2\+\\frac\{h\}\{1\+mh\}\\right\)\}\{\(2\+mh\)\(2\+mh\+h\)\}\(61\)=1−2​\(2\+2​m​h\+h\)\(1\+m​h\)​\(2\+m​h\)​\(2\+m​h\+h\)\\displaystyle=1\-\\frac\{2\(2\+2mh\+h\)\}\{\(1\+mh\)\(2\+mh\)\(2\+mh\+h\)\}\(62\)
Note that2\+2​m​h\+x2\+m​h\+x\\frac\{2\+2mh\+x\}\{2\+mh\+x\}is decreasing forx≥0x\\geq 0\. Thus,

α\\displaystyle\\alpha≥1−2​\(2\+2​m​h\)\(1\+m​h\)​\(2\+m​h\)​\(2\+m​h\)\\displaystyle\\geq 1\-\\frac\{2\(2\+2mh\)\}\{\(1\+mh\)\(2\+mh\)\(2\+mh\)\}\(63\)=1−22\(2\+m​h\)2\\displaystyle=1\-\\frac\{2^\{2\}\}\{\(2\+mh\)^\{2\}\}\(64\)=1−\(11\+\(n−1\)​h2\)2\\displaystyle=1\-\\left\(\\frac\{1\}\{1\+\\frac\{\(n\-1\)h\}\{2\}\}\\right\)^\{2\}\(65\)∎

## Appendix BLower Bound Details

For the lower bound, we prove a slightly more general result that yields Theorem[2](https://arxiv.org/html/2607.06642#Thmtheorem2)as a corollary\.

###### Lemma 3\.

For anyh\>0h\>0,α\>0\\alpha\>0,0<r<10<r<1, andd≥4d\\geq 4, if there exists an orderddHadamard matrix and

g​\(d,r,α\)=d​ln⁡\(1/r\)​\(1\+α\)−α​ln⁡\(\(1−r\)​α2\(rd​\(1\+α\)2−1\)​ln⁡\(1/r\)\)\+α−\(α\+2\)​ln⁡\(1/r\)1−r\>0,\\displaystyle g\(d,r,\\alpha\)=d\\ln\(1/r\)\(1\+\\alpha\)\-\\alpha\\ln\\left\(\\frac\{\(1\-r\)\\alpha^\{2\}\}\{\(r^\{d\}\(1\+\\alpha\)^\{2\}\-1\)\\ln\(1/r\)\}\\right\)\+\\alpha\-\(\\alpha\+2\)\\frac\{\\ln\(1/r\)\}\{1\-r\}\>0,\(66\)then there exists add\-dimensional problem withn=2​dn=2dvectors such thathmax=max⁡\(h,α\)h\_\{\\text\{max\}\}=\\max\(h,\\alpha\)and for a cardinality constraint ofk=dk=d,

f​\(Sgreedy\)f​\(S⋆\)≥1\+h1\+α\\displaystyle\\frac\{f\(S\_\{\\text\{greedy\}\}\)\}\{f\(S^\{\\star\}\)\}\\geq\\frac\{1\+h\}\{1\+\\alpha\}\(67\)

###### Proof\.

LetHHbe an orderddHadamard matrix, so all entries are±1\\pm 1andH​HT=d​IdHH^\{T\}=dI\_\{d\}\.

LetΛ∈ℝd×d\\Lambda\\in\\mathbb\{R\}^\{d\\times d\}be a diagonal matrix with diagonal entriesΛj,j=r−\(j−1\)\\Lambda\_\{j,j\}=r^\{\-\(j\-1\)\}\.

We define two sets of vectors,U=\{ui\}i=1d⊂ℝdU=\\\{u\_\{i\}\\\}\_\{i=1\}^\{d\}\\subset\\mathbb\{R\}^\{d\}andW=\{wi\}i=1d⊂ℝdW=\\\{w\_\{i\}\\\}\_\{i=1\}^\{d\}\\subset\\mathbb\{R\}^\{d\}as follows:

ui,j\\displaystyle u\_\{i,j\}=𝟏​\[i=j\]​α​r−\(j−1\)\\displaystyle=\\mathbf\{1\}\[i=j\]\\sqrt\{\\alpha r^\{\-\(j\-1\)\}\}\(68\)wi,j\\displaystyle w\_\{i,j\}=Hj,i​h​r−\(j−1\)d\\displaystyle=H\_\{j,i\}\\sqrt\{\\frac\{hr^\{\-\(j\-1\)\}\}\{d\}\}\(69\)Let the candidate vectorsV=\{vi\}i=12​dV=\\\{v\_\{i\}\\\}\_\{i=1\}^\{2d\}be such thatvi=uiv\_\{i\}=u\_\{i\}fori∈\[d\]i\\in\[d\]andvd\+i=wiv\_\{d\+i\}=w\_\{i\}fori∈\[d\]i\\in\[d\]\.

Note that,

ui⊤​Λ−1​ui\\displaystyle u\_\{i\}^\{\\top\}\\Lambda^\{\-1\}u\_\{i\}=∑j=1dvi,j2​Λj,j−1=∑j=1d𝟏​\[i=j\]​α​r−\(j−1\)r−\(j−1\)=α\\displaystyle=\\sum\_\{j=1\}^\{d\}v\_\{i,j\}^\{2\}\\Lambda\_\{j,j\}^\{\-1\}=\\sum\_\{j=1\}^\{d\}\\mathbf\{1\}\[i=j\]\\frac\{\\alpha r^\{\-\(j\-1\)\}\}\{r^\{\-\(j\-1\)\}\}=\\alpha\(71\)wi⊤​Λ−1​wi\\displaystyle w\_\{i\}^\{\\top\}\\Lambda^\{\-1\}w\_\{i\}=∑j=1d\(wi,j\)2​Λj,j−1=∑j=1dh​r−\(j−1\)d​r−\(j−1\)=h\\displaystyle=\\sum\_\{j=1\}^\{d\}\(w\_\{i,j\}\)^\{2\}\\Lambda\_\{j,j\}^\{\-1\}=\\sum\_\{j=1\}^\{d\}\\frac\{hr^\{\-\(j\-1\)\}\}\{dr^\{\-\(j\-1\)\}\}=h\(72\)
Thus,hmax=max⁡\(h,α\)h\_\{\\text\{max\}\}=\\max\(h,\\alpha\)\.

We will later show that the greedy algorithm selects the firstnnvectors\.

f​\(\[d\]\)\\displaystyle f\(\[d\]\)=Tr​\(\(Λ\+∑i=1dui​ui⊤\)−1\)\\displaystyle=\\text\{Tr\}\(\(\\Lambda\+\\sum\_\{i=1\}^\{d\}u\_\{i\}u\_\{i\}^\{\\top\}\)^\{\-1\}\)\(74\)=∑j=1d\(Λj,j\+α​Λj,j\)−1\\displaystyle=\\sum\_\{j=1\}^\{d\}\(\\Lambda\_\{j,j\}\+\\alpha\\Lambda\_\{j,j\}\)^\{\-1\}\(75\)=\(1\+α\)−1​∑j=1drj−1\\displaystyle=\(1\+\\alpha\)^\{\-1\}\\sum\_\{j=1\}^\{d\}r^\{j\-1\}\(76\)
The optimal set ofk=dk=dvectors will haveffvalue no larger thanf​\(\{i\}i=d\+12​d\)f\(\\\{i\\\}\_\{i=d\+1\}^\{2d\}\)\. First, note that

\[∑i=1dwi​wi⊤\]j,k\\displaystyle\\left\[\\sum\_\{i=1\}^\{d\}w\_\{i\}w\_\{i\}^\{\\top\}\\right\]\_\{j,k\}=∑i=1dwi,j​wi,k\\displaystyle=\\sum\_\{i=1\}^\{d\}w\_\{i,j\}w\_\{i,k\}\(77\)=hd​r−\(j−1\)​r−\(k−1\)​∑i=1dHj,i​Hk,i\\displaystyle=\\frac\{h\}\{d\}\\sqrt\{r^\{\-\(j\-1\)\}\}\\sqrt\{r^\{\-\(k\-1\)\}\}\\sum\_\{i=1\}^\{d\}H\_\{j,i\}H\_\{k,i\}\(78\)=hd​r−\(j−1\)​r−\(k−1\)​\[H​H⊤\]j,k\\displaystyle=\\frac\{h\}\{d\}\\sqrt\{r^\{\-\(j\-1\)\}\}\\sqrt\{r^\{\-\(k\-1\)\}\}\\left\[HH^\{\\top\}\\right\]\_\{j,k\}\(79\)=hd​r−\(j−1\)​r−\(k−1\)​\[d​Id\]j,k\\displaystyle=\\frac\{h\}\{d\}\\sqrt\{r^\{\-\(j\-1\)\}\}\\sqrt\{r^\{\-\(k\-1\)\}\}\\left\[dI\_\{d\}\\right\]\_\{j,k\}\(80\)=𝟏​\[j=k\]​h​r−\(j−1\)\\displaystyle=\\mathbf\{1\}\[j=k\]hr^\{\-\(j\-1\)\}\(81\)
Thus,∑i=1dwi​wi⊤=h​Λ\\sum\_\{i=1\}^\{d\}w\_\{i\}w\_\{i\}^\{\\top\}=h\\Lambda

f​\(\{i\}i=d\+12​d\)\\displaystyle f\(\\\{i\\\}\_\{i=d\+1\}^\{2d\}\)=Tr​\(\(Λ\+∑i=1dwi​wi⊤\)−1\)\\displaystyle=\\text\{Tr\}\(\(\\Lambda\+\\sum\_\{i=1\}^\{d\}w\_\{i\}w\_\{i\}^\{\\top\}\)^\{\-1\}\)\(82\)=Tr​\(\(Λ\+h​Λ\)−1\)\\displaystyle=\\text\{Tr\}\(\(\\Lambda\+h\\Lambda\)^\{\-1\}\)\(83\)=\(1\+h\)−1​∑j=1drj−1\\displaystyle=\(1\+h\)^\{\-1\}\\sum\_\{j=1\}^\{d\}r^\{j\-1\}\(84\)
Thus,

f​\(\[d\]\)f​\(\{i\}i=d\+12​d\)=1\+h1\+α\\displaystyle\\frac\{f\(\[d\]\)\}\{f\(\\\{i\\\}\_\{i=d\+1\}^\{2d\}\)\}=\\frac\{1\+h\}\{1\+\\alpha\}\(85\)
If we can show that the greedy algorithm chooses\[d\]\[d\]\(the firstk=dk=dvectors\), then it suffices to prove the result\.

Note that minimizingf​\(St−1∪\{it\}\)f\(S\_\{t\-1\}\\cup\\\{i\_\{t\}\\\}\)is the same as maximizingf​\(St−1\)−f​\(St−1∪\{it\}\)f\(S\_\{t\-1\}\)\-f\(S\_\{t\-1\}\\cup\\\{i\_\{t\}\\\}\)

Note that for anykk, ifk<j≤dk<j\\leq d, then from the Sherman\-Morrison formula,

f​\(\[k\]\)−f​\(\[k\]∪\{j\}\)\\displaystyle f\(\[k\]\)\-f\(\[k\]\\cup\\\{j\\\}\)=uj⊤​\(Λ\+∑i=1kui​ui⊤\)−2​uj1\+uj⊤​\(Λ\+∑i=1kui​ui⊤\)−1​uj\\displaystyle=\\frac\{u\_\{j\}^\{\\top\}\\left\(\\Lambda\+\\sum\_\{i=1\}^\{k\}u\_\{i\}u\_\{i\}^\{\\top\}\\right\)^\{\-2\}u\_\{j\}\}\{1\+u\_\{j\}^\{\\top\}\\left\(\\Lambda\+\\sum\_\{i=1\}^\{k\}u\_\{i\}u\_\{i\}^\{\\top\}\\right\)^\{\-1\}u\_\{j\}\}\(86\)=α​r−\(j−1\)​\(r−\(j−1\)\)−2​α​r−\(j−1\)1\+α​r−\(j−1\)​\(r−\(j−1\)\)−1​α​r−\(j−1\)\\displaystyle=\\frac\{\\sqrt\{\\alpha r^\{\-\(j\-1\)\}\}\(r^\{\-\(j\-1\)\}\)^\{\-2\}\\sqrt\{\\alpha r^\{\-\(j\-1\)\}\}\}\{1\+\\sqrt\{\\alpha r^\{\-\(j\-1\)\}\}\(r^\{\-\(j\-1\)\}\)^\{\-1\}\\sqrt\{\\alpha r^\{\-\(j\-1\)\}\}\}\(87\)=α​rj−1\(1\+α\)\\displaystyle=\\frac\{\\alpha r^\{j\-1\}\}\{\(1\+\\alpha\)\}\(88\)
which are strictly decreasing injjsincer<1r<1\.

Thus, as long asf​\(\[k\]\)−f​\(\[k\+1\]\)\>f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)f\(\[k\]\)\-f\(\[k\+1\]\)\>f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)for all0≤k<d0\\leq k<dandi∈\[d\]i\\in\[d\], then the greedy algorithm will iteratively select sets\[1\],\[2\],\[3\],…,\[d\]\[1\],\[2\],\[3\],\\dots,\[d\]and the theorem is proven\.

Note that for0≤k<d0\\leq k<dandi∈\[d\]i\\in\[d\],

f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)\\displaystyle f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)=wi⊤​\[Λ\+∑j=1kuj​uj⊤\]−2​wi1\+wi⊤​\[Λ\+∑j=1kuj​uj⊤\]−1​wi\\displaystyle=\\frac\{w\_\{i\}^\{\\top\}\\left\[\\Lambda\+\\sum\_\{j=1\}^\{k\}u\_\{j\}u\_\{j\}^\{\\top\}\\right\]^\{\-2\}w\_\{i\}\}\{1\+w\_\{i\}^\{\\top\}\\left\[\\Lambda\+\\sum\_\{j=1\}^\{k\}u\_\{j\}u\_\{j\}^\{\\top\}\\right\]^\{\-1\}w\_\{i\}\}\(89\)≤wi⊤​\[Λ\+∑j=1kuj​uj⊤\]−2​wiwi⊤​\[Λ\+∑j=1kuj​uj⊤\]−1​wi\\displaystyle\\leq\\frac\{w\_\{i\}^\{\\top\}\\left\[\\Lambda\+\\sum\_\{j=1\}^\{k\}u\_\{j\}u\_\{j\}^\{\\top\}\\right\]^\{\-2\}w\_\{i\}\}\{w\_\{i\}^\{\\top\}\\left\[\\Lambda\+\\sum\_\{j=1\}^\{k\}u\_\{j\}u\_\{j\}^\{\\top\}\\right\]^\{\-1\}w\_\{i\}\}\(90\)=∑j=1k\(1\+α\)−2​\(r−\(j−1\)\)−2​wi,j2\+∑j=k\+1d\(r−\(j−1\)\)−2​wi,j2∑j=1k\(1\+α\)−1​\(r−\(j−1\)\)−1​wi,j2\+∑j=k\+1d\(r−\(j−1\)\)−1​wi,j2\\displaystyle=\\frac\{\\sum\_\{j=1\}^\{k\}\(1\+\\alpha\)^\{\-2\}\(r^\{\-\(j\-1\)\}\)^\{\-2\}w\_\{i,j\}^\{2\}\+\\sum\_\{j=k\+1\}^\{d\}\(r^\{\-\(j\-1\)\}\)^\{\-2\}w\_\{i,j\}^\{2\}\}\{\\sum\_\{j=1\}^\{k\}\(1\+\\alpha\)^\{\-1\}\(r^\{\-\(j\-1\)\}\)^\{\-1\}w\_\{i,j\}^\{2\}\+\\sum\_\{j=k\+1\}^\{d\}\(r^\{\-\(j\-1\)\}\)^\{\-1\}w\_\{i,j\}^\{2\}\}\(91\)=∑j=1k\(1\+α\)−2​rj−1​hd\+∑j=k\+1drj−1​hd∑j=1k\(1\+α\)−1​hd\+∑j=k\+1dhd\\displaystyle=\\frac\{\\sum\_\{j=1\}^\{k\}\(1\+\\alpha\)^\{\-2\}r^\{j\-1\}\\frac\{h\}\{d\}\+\\sum\_\{j=k\+1\}^\{d\}r^\{j\-1\}\\frac\{h\}\{d\}\}\{\\sum\_\{j=1\}^\{k\}\(1\+\\alpha\)^\{\-1\}\\frac\{h\}\{d\}\+\\sum\_\{j=k\+1\}^\{d\}\\frac\{h\}\{d\}\}\(92\)=11\+α​∑j=1krj−1\+\(1\+α\)2​∑j=k\+1drj−1∑j=1k1\+∑j=k\+1d\(1\+α\)\\displaystyle=\\frac\{1\}\{1\+\\alpha\}\\frac\{\\sum\_\{j=1\}^\{k\}r^\{j\-1\}\+\(1\+\\alpha\)^\{2\}\\sum\_\{j=k\+1\}^\{d\}r^\{j\-1\}\}\{\\sum\_\{j=1\}^\{k\}1\+\\sum\_\{j=k\+1\}^\{d\}\(1\+\\alpha\)\}\(93\)=11\+α​1−rk1−r\+\(1\+α\)2​rk−rd1−rk\+\(d−k\)​\(1\+α\)\\displaystyle=\\frac\{1\}\{1\+\\alpha\}\\frac\{\\frac\{1\-r^\{k\}\}\{1\-r\}\+\(1\+\\alpha\)^\{2\}\\frac\{r^\{k\}\-r^\{d\}\}\{1\-r\}\}\{k\+\(d\-k\)\(1\+\\alpha\)\}\(94\)=11\+α​11−r​1−rd​\(1\+α\)2\+rk​\(α2\+2​α\)d​\(1\+α\)−k​α\\displaystyle=\\frac\{1\}\{1\+\\alpha\}\\frac\{1\}\{1\-r\}\\frac\{1\-r^\{d\}\(1\+\\alpha\)^\{2\}\+r^\{k\}\(\\alpha^\{2\}\+2\\alpha\)\}\{d\(1\+\\alpha\)\-k\\alpha\}\(95\)
The condition thatf​\(\[k\]\)−f​\(\[k\+1\]\)\>f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)f\(\[k\]\)\-f\(\[k\+1\]\)\>f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)is equivalent to\[f​\(\[k\]\)−f​\(\[k\+1\]\)\]−\[f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)\]\\left\[f\(\[k\]\)\-f\(\[k\+1\]\)\\right\]\-\\left\[f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)\\right\]being positive\. We multiply this quantity by positive constants to getG​\(k,d,r,α\)G\(k,d,r,\\alpha\)which is positive if and only iff​\(\[k\]\)−f​\(\[k\+1\]\)\>f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)f\(\[k\]\)\-f\(\[k\+1\]\)\>f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)\.

G​\(d,α,r,k\)\\displaystyle G\(d,\\alpha,r,k\)\(96\):=1\+αα​ln⁡\(1/r\)​\(d​\(1\+α\)−k​α\)​r−k​\[f​\(\[k\]\)−f​\(\[k\+1\]\)\]−\[f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)\]\\displaystyle:=\\frac\{1\+\\alpha\}\{\\alpha\}\\ln\(1/r\)\(d\(1\+\\alpha\)\-k\\alpha\)r^\{\-k\}\\left\[f\(\[k\]\)\-f\(\[k\+1\]\)\\right\]\-\\left\[f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)\\right\]\(97\)=ln⁡\(1/r\)​\(d​\(1\+α\)−k​α\)\+1α​ln⁡\(1/r\)1−r​\(rd​\(1\+α\)2−1\)​r−k−\(α\+2\)​ln⁡\(1/r\)1−r\\displaystyle=\\ln\(1/r\)\(d\(1\+\\alpha\)\-k\\alpha\)\+\\frac\{1\}\{\\alpha\}\\frac\{\\ln\(1/r\)\}\{1\-r\}\\left\(r^\{d\}\(1\+\\alpha\)^\{2\}\-1\\right\)r^\{\-k\}\-\(\\alpha\+2\)\\frac\{\\ln\(1/r\)\}\{1\-r\}\(98\)
Forrd​\(1\+α\)2≥1r^\{d\}\(1\+\\alpha\)^\{2\}\\geq 1, this function is convex inkk\. Thus, it will be positive for allkkif its positive for the minimizerk∗k^\{\*\}\. Taking the derivative and setting it to0, we getk∗=1ln⁡\(1/r\)​ln⁡\(\(1−r\)​α2\(rd​\(1\+α\)2−1\)​ln⁡\(1/r\)\)k^\{\*\}=\\frac\{1\}\{\\ln\(1/r\)\}\\ln\\left\(\\frac\{\(1\-r\)\\alpha^\{2\}\}\{\(r^\{d\}\(1\+\\alpha\)^\{2\}\-1\)\\ln\(1/r\)\}\\right\)\. Thus the minimal value is at least,

g​\(d,α,r\)\\displaystyle g\(d,\\alpha,r\):=mink⁡G​\(d,α,r,k\)\\displaystyle:=\\min\_\{k\}G\(d,\\alpha,r,k\)\(99\)=d​ln⁡\(1/r\)​\(1\+α\)−α​ln⁡\(\(1−r\)​α2\(rd​\(1\+α\)2−1\)​ln⁡\(1/r\)\)\+α−\(α\+2\)​ln⁡\(1/r\)1−r\\displaystyle=d\\ln\(1/r\)\(1\+\\alpha\)\-\\alpha\\ln\\left\(\\frac\{\(1\-r\)\\alpha^\{2\}\}\{\(r^\{d\}\(1\+\\alpha\)^\{2\}\-1\)\\ln\(1/r\)\}\\right\)\+\\alpha\-\(\\alpha\+2\)\\frac\{\\ln\(1/r\)\}\{1\-r\}\(100\)
Putting it all together, ifg​\(d,α,r\)g\(d,\\alpha,r\)is positive, thenG​\(d,α,r,k\)G\(d,\\alpha,r,k\)is positive for allkk, so\[f​\(\[k\]\)−f​\(\[k\+1\]\)\]−\[f​\(\[k\]\)−f​\(\[k\]∪\{d\+i\}\)\]\\left\[f\(\[k\]\)\-f\(\[k\+1\]\)\\right\]\-\\left\[f\(\[k\]\)\-f\(\[k\]\\cup\\\{d\+i\\\}\)\\right\]is positive for allkk, and thus the greedy algorithm will sequentially select the elements\. ∎

We ran a Python Notebook to get some numerical results onggusing some example values ofdd,α\\alpha, andrr:

\[1\]:importmathdefg\(d,alpha,r\):subexpression=\(1\-r\)\*alpha\*\*2/\(r\*\*d\*\(1\+alpha\)\*\*2\-1\)/math\.log\(1/r\)returnd\*math\.log\(1/r\)\*\(1\+alpha\)\-alpha\*math\.log\(subexpression\)\+alpha\-\(alpha\+2\)\*math\.log\(1/r\)/\(1\-r\)ford,alpha,rin\[\(4,4,math\.exp\(\-1/4\)\),\(4,3\.7,0\.75\),\(8,2\.8,0\.85\),\(16,2\.5,0\.93\),\(256,2\.25,0\.9955\)\]:print\(f"d=\{d\},\\talpha=\{alpha\},\\tr=\{round\(r,6\)\},\\tg=\{round\(g\(d,alpha,r\),6\)\}"\)

d=4,alpha=4,r=0\.778801,g=0\.033082d=4,alpha=3\.7,r=0\.75,g=0\.010047d=8,alpha=2\.8,r=0\.85,g=0\.013102d=16,alpha=2\.5,r=0\.93,g=0\.013278d=256,alpha=2\.25,r=0\.9955,g=0\.001105

The first setting of values is used to prove Theorem[2](https://arxiv.org/html/2607.06642#Thmtheorem2)below\. The other settings show that we can get tighter approximations \(i\.e\. smallerα\\alpha\) for largerdd\. Separately, we found that even for arbitrarily largeddand optimally chosenrr, the expression can only be positive ifα≥2\.23\\alpha\\geq 2\.23, sod=256d=256nearly achieves the lowest value ofα\\alpha\(and thus approximation ratio\)\. We now prove the main result,

###### Theorem[2](https://arxiv.org/html/2607.06642#Thmtheorem2)\.

For anyh\>0h\>0andd≥4d\\geq 4, if there exists an orderddHadamard matrix, then there exists add\-dimensional problem withn=2​dn=2dvectors such thathmax=max⁡\(h,4\)h\_\{\\text\{max\}\}=\\max\(h,4\)and for a cardinality constraint ofk=dk=d,

f​\(Sgreedy\)f​\(S⋆\)≥1\+h5\\displaystyle\\frac\{f\(S\_\{\\text\{greedy\}\}\)\}\{f\(S^\{\\star\}\)\}\\geq\\frac\{1\+h\}\{5\}\(102\)

###### Proof\.

Settingα=4\\alpha=4andr=exp⁡\(−1/d\)r=\\exp\(\-1/d\), it suffices to prove thatg​\(d,4,exp⁡\(−1/d\)\)\>0g\(d,4,\\exp\(\-1/d\)\)\>0for alld≥4d\\geq 4\.

g​\(d,exp⁡\(−1/d\),4\)=5\+4​ln⁡\(25​exp⁡\(−1\)−1\)−4​ln⁡\(42\)\\displaystyle g\(d,\\exp\(\-1/d\),4\)=5\+4\\ln\\left\(25\\exp\(\-1\)\-1\\right\)\-4\\ln\(4^\{2\}\)\(103\)−4ln\(d\(1−exp\(−1/d\)\)\+4−61d​\(1−exp⁡\(−1/d\)\)\\displaystyle\-4\\ln\(d\(1\-\\exp\(\-1/d\)\)\+4\-6\\frac\{1\}\{d\(1\-\\exp\(\-1/d\)\)\}\(104\)
We now show thatggis increasing indd\.

Letu​\(d\)=d​\(1−exp⁡\(−1/d\)\)u\(d\)=d\(1\-\\exp\(\-1/d\)\)\. Noting thatexp⁡\(x\)≤1\+x\+x22\\exp\(x\)\\leq 1\+x\+\\frac\{x^\{2\}\}\{2\}forx≤0x\\leq 0,

u′​\(d\)\\displaystyle u^\{\\prime\}\(d\)=\(1−exp⁡\(−1/d\)\)−d​exp⁡\(−1/d\)​1d\\displaystyle=\(1\-\\exp\(\-1/d\)\)\-d\\exp\(\-1/d\)\\frac\{1\}\{d\}\(105\)=1−\(1\+1d\)​exp⁡\(−1/d\)\\displaystyle=1\-\\left\(1\+\\frac\{1\}\{d\}\\right\)\\exp\(\-1/d\)\(106\)≥1−\(1\+1d\)​\(1−1d\+12​d2\)\\displaystyle\\geq 1\-\\left\(1\+\\frac\{1\}\{d\}\\right\)\\left\(1\-\\frac\{1\}\{d\}\+\\frac\{1\}\{2d^\{2\}\}\\right\)\(107\)=12​d2​\(1−1d\)\>0\\displaystyle=\\frac\{1\}\{2d^\{2\}\}\\left\(1\-\\frac\{1\}\{d\}\\right\)\>0\(108\)
Souuis increasing indd\. Furthermore, noting thatexp⁡\(x\)≥1\+x\\exp\(x\)\\geq 1\+xfor allxx, we can showu​\(d\)≤1u\(d\)\\leq 1,

u​\(d\)\\displaystyle u\(d\)=d​\(1−exp⁡\(−1/d\)\)\\displaystyle=d\(1\-\\exp\(\-1/d\)\)\(109\)≤d​\(1−\(1−1/d\)\)\\displaystyle\\leq d\(1\-\(1\-1/d\)\)\(110\)=1\\displaystyle=1\(111\)
Since4​ln⁡\(1/u\)−6/u4\\ln\(1/u\)\-6/uis increasing inuuforu∈\(0,1\)u\\in\(0,1\),g​\(d,exp⁡\(−1/d\),4\)g\(d,\\exp\(\-1/d\),4\)is increasing indd\.

Thus

g​\(d,exp⁡\(−1/d\),4\)\\displaystyle g\(d,\\exp\(\-1/d\),4\)≥g​\(4,exp⁡\(−1/4\),4\)\\displaystyle\\geq g\(4,\\exp\(\-1/4\),4\)\(112\)\>0\.03\\displaystyle\>0\.03\(113\)
The last equation is from the numerical result\. ∎

## Appendix CLower Bound Example Code

Below is the code to numerically check the explicit example withd=4d=4\.

\[2\]:importnumpyasnpimportmatplotlib\.pyplotaspltH=np\.array\(\[\[1,1,1,1\],\[1,\-1,1,\-1\],\[1,1,\-1,\-1\],\[1,\-1,\-1,1\]\]\)classProblem:defmils\(self\):returnmax\(\[v@np\.linalg\.inv\(self\.Lam\)@vforvinself\.vectors\]\)deff\(self,S\):cov=np\.array\(self\.Lam\)foriinS:cov\+=np\.outer\(self\.vectors\[i\],self\.vectors\[i\]\)returnnp\.trace\(np\.linalg\.inv\(cov\)\)classConstructedProblem\(Problem\):def\_\_init\_\_\(self,h\):self\.d=4self\.n=4self\.Lam=np\.diag\(\[math\.exp\(i/4\)foriinrange\(4\)\]\)self\.vectors=\[\]scaling=np\.diag\(\[math\.exp\(i/8\)foriinrange\(4\)\]\)foriinrange\(4\):self\.vectors\.append\(2\*scaling@np\.eye\(4\)\[i\]\)foriinrange\(4\):self\.vectors\.append\(math\.sqrt\(h\)/2\*scaling@H\[i\]\)defGreedy\(problem,k\):S=\[\]fortinrange\(k\):greedy\_next=np\.argmin\(\[problem\.f\(S\+\[i\]\)ifinotinSelsenp\.infforiinrange\(problem\.n\)\]\)S\.append\(greedy\_next\)returnS

\[3\]:forhin\[10,100,1000\]:prob=ConstructedProblem\(h\)S=Greedy\(prob,4\)greedy\_value=prob\.f\(S\)better\_value=prob\.f\(\[4,5,6,7\]\)print\(32\*"\-"\)print\(f"h=\{h\}"\)print\(f"MILS=\{prob\.mils\(\)\}"\)print\(f"Greedy Set:\{S\}"\)print\(f"Greedy Value:\{greedy\_value\}"\)print\(f"Better Value:\{better\_value\}"\)print\(f"Approx Ratio:\{greedy\_value/better\_value\}"\)print\(\)

\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-h=10MILS=10\.0Greedy Set:\[0,1,2,3\]Greedy Value:0\.5715395991050106Better Value:0\.25979072686591387Approx Ratio:2\.2000000000000006\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-h=100MILS=100\.0Greedy Set:\[0,1,2,3\]Greedy Value:0\.5715395991050106Better Value:0\.028294039559653993Approx Ratio:20\.2\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-h=1000MILS=1000\.0Greedy Set:\[0,1,2,3\]Greedy Value:0\.5715395991050106Better Value:0\.0028548431523726806Approx Ratio:200\.2

## Appendix DIllustrative Example Code

\[4\]:classRandomProblem\(Problem\):def\_\_init\_\_\(self,d,n\):self\.d=dself\.n=nself\.Lam=np\.eye\(d\)self\.vectors=\[\]rng=np\.random\.default\_rng\(seed=0\)foriinrange\(n\):v=rng\.normal\(size=\(d,\)\)v/=np\.linalg\.norm\(v\)self\.vectors\.append\(v\)defChamon\_alpha\(a,b\):return1/\(1\+a\)defChamon\_reduction\_approx\_ratio\(k\):ifk==0:return1product\_terms=\[1\-1/np\.sum\(\[1/Chamon\_alpha\(h,h\+s\)forsinrange\(k\)\]\)forhinrange\(k\)\]return1\-np\.product\(product\_terms\)defBian\_gamma\_alpha\(vectors\):X\_norm\_squared=np\.linalg\.norm\(np\.array\(vectors\),ord=2\)\*\*2return\{"gamma":1/X\_norm\_squared/\(1\+X\_norm\_squared\),"alpha":1\-1/X\_norm\_squared/\(1\+X\_norm\_squared\)\}defBian\_reduction\_approx\_ratio\(alpha,gamma\):return1/alpha\*\(1\-\(\(k\-alpha\*gamma\)/k\)\*\*k\)defreduction\_approx\_ratio\_lb\(greedy\_value,f\_0,reduction\_approx\_ratio\):returnf\_0\-\(f\_0\-greedy\_value\)/reduction\_approx\_ratio

\[5\]:d,n,k=20,1000,100prob=RandomProblem\(d,n\)f\_0=prob\.f\(\[\]\)our\_approx\_ratio=\(prob\.mils\(\)\+1/\(1\-1/math\.e\)\)S=Greedy\(prob,k\)greedy\_values=np\.array\(\[prob\.f\(S\[:t\]\)fortinrange\(k\+1\)\]\)print\(32\*"\-"\)print\("Bian Analysis at k=1"\)print\(Bian\_gamma\_alpha\(prob\.vectors\)\)print\("Bian Reduction Approximation Ratio:\{\}"\.format\(round\(Bian\_reduction\_approx\_ratio\(\*\*Bian\_gamma\_alpha\(prob\.vectors\)\),6\)\)\)print\("Bian Optimal Lower Bound:\{\}"\.format\(round\(reduction\_approx\_ratio\_lb\(greedy\_values\[1\],f\_0,Bian\_reduction\_approx\_ratio\(\*\*Bian\_gamma\_alpha\(prob\.vectors\)\)\),6\)\)\)print\(32\*"\-"\)our\_lb\_values=greedy\_values/our\_approx\_ratioChamon\_lb\_values=np\.array\(\[reduction\_approx\_ratio\_lb\(greedy\_values\[t\],f\_0,Chamon\_reduction\_approx\_ratio\(t\)\)fortinrange\(k\+1\)\]\)plt\.subplots\(figsize=\(8,6\)\)plt\.plot\(range\(k\+1\),greedy\_values,color=’blue’,linewidth=2,label=’Greedy Algorithm’\)plt\.plot\(range\(k\+1\),our\_lb\_values,color=’green’,linewidth=2,label=’Our Lower Bound on Optimal’,linestyle=’dashed’\)plt\.plot\(range\(k\+1\),Chamon\_lb\_values,color=’red’,linewidth=2,label=’Chamon\\’s Lower Bound on Optimal’,linestyle=’dotted’\)plt\.xlabel\(’k’,fontsize=13\)plt\.ylabel\(’f value’,fontsize=13\)plt\.xlim\(0,k\)plt\.ylim\(0,d\)plt\.grid\(True,linestyle=’\-\-’,alpha=0\.7\)plt\.legend\(\)plt\.tight\_layout\(\)plt\.show\(\)

\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-Bian Analysis at k=1\{’gamma’:0\.0002594098407928644,’alpha’:0\.9997405901592071\}Bian Reduction Approximation Ratio:0\.000259Bian Optimal Lower Bound:\-1907\.699383\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-