7 Additional Experimental Details↩︎

7.1 Datasets↩︎

7.1.0.1 Synthetic

For this dataset \(n=1000\) and \(x_i \overset{iid}{\sim} \mathrm{Unif}(\mathbb{S}^{d-1})\) with \(d=100\). Then, we sample \(w^\star\sim \mathrm{Unif}(\mathbb{S}^{d-1})\). We assume that the labels \(y_i \sim Ber(p^\star(x))\) where \(p^\star(x) = \frac{1}{1 + \exp(-\beta \cdot \langle w^\star,x\rangle)}\) with \(\beta = 4\). Here, the link function is sigmoid, which is \(L\)-smooth with \(L=0.272\). We use the fact that if \(g(a) = \frac{1}{1+\exp(-\beta a)}\), then \(g'(a) = \beta g(a)(1-g(a))\) and \(g''(a) = \beta^2 g(a)(1-g(a))(1-2g(a))\) with the value of \(a\in [-1,1]\) as \(a\) is the inner product of two unit vectors. To create \(w_{v,l}\) and \(w_{v,c}\), we sample two unit vectors, \(u_1, u_2\), from \(\mathbb{S}^{d-1}\) perpendicular to \(w^\star\) and set \(w_{v,l} = \sqrt{1-\epsilon^2} w^\star + \epsilon u_1\) and \(w_{v,c} = \sqrt{1-4\epsilon^2}w^\star + 2\epsilon u_2\), with \(\epsilon=0.1\). The value \(\epsilon\) allows us to directly control the values of \(\langle w^\star,w_{v,l}\rangle\) and \(\langle w^\star,w_{v,c}\rangle\) with \(\langle w^\star,w_{v,c}\rangle <\langle w^\star,w_{v,l}\rangle\). The last condition ensures that the confidence estimate from the linear model is not accurate. For pairwise queries on two features \(x_i\) and \(x_j\), we compute the the sign of \(p_{v,l}(x_i) - p_{v,l}(x_j) = g(\langle w_{v,l},x_i\rangle) - g(\langle w_{v,l},x_j\rangle)\). Further, the distance metric between any two features \(x_i\) and \(x_j\) is \(\lvert\lvert x_i - x_j\rvert\rvert_2^2 = 2 - 2\langle x_i,x_j\rangle\). This setting does not exactly match either of the two theoretical settings in Theorems 1 and  2, as we use Spherical features with Smooth Link. However, our theoretical results also hold for this setting.

7.1.0.2 Spider and Bird

To ensure that we test our baselines on sufficiently complicated SQL queries, we filter out the databases from each of these datasets such that they contain large number of tables, foreign keys and samples. For spider, the thresholds for number of tables, foreign keys and samples is \(15, 7\) and \(100\) respectively, which results in \(3\) databases with \(370\) samples in total. For Bird, the corresponding thresholds are \(20,20\) and \(150\) and we end up with \(3\) databases totaling \(919\) samples. Note that in each case, we only filter and label the training sets. For both these datasets, we use \(60\%\) of the samples as positive samples. For the remaining \(40\%\) of the samples, we need to pair a question with an SQL that does not answer the question. For this purpose, we shuffle the questions and their correct SQLs of these \(40\%\) samples to obtain a derangement, i.e., each question is paired with the correct SQL of a different question. As there are no duplicate questions in the dataset, each question in the negative label set is mapped to an incorrect SQL.

7.1.0.3 BoolQ and VisOnlyQA

For BoolQ dataset, to ensure that we have sufficiently complicated questions, we only consider those (Passage, Question) pairs where the Passage contains more than \(175\) words. After this filtering, we end up with \(631\) samples, of which \(61.2\%\) are positive labels. The VisOnlyQA dataset contains single answer and multiple answer questions, of which the single answer questions contain both True/False answers and multiple choice questions. We only keep the single answer True/False questions to obtain a binary classification task resulting in \(470\) samples of which \(50\%\) are positive labels. For both these datasets, we convert the True label to \(1\) and False to \(0\). For BoolQ, we use the training dataset, and for VisOnlyQA, we use the Real Eval dataset.

7.2 Baselines↩︎

Direct/Raw Baseline For each dataset, we remove an intial in-context example bank of \(20\) samples. We keep adding the classifier-labeled examples to this in-context example bank. For Spider and Bird, for each in-context query, we supply the database schema followed by \(4\) in-context examples of (NL, SQL, label) selected randomly from the in-context example bank. This random sampling assigns a weight of \(1\) to each initial in-context example and \(0.5\) to each example labeled by a classifier. See Fig 6 for an example. For BoolQ, we also use \(4\) in-context examples of the form (Passage, Question, Label) as shown in Fig 8. For VisQA, we use \(2\) in-context examples of the form (Image, Question, Label) for the prompt as shown in Fig 9.

Calibrated baseline [25] In this methods, a mixture of \(2\) gaussians, one for each label, is fit to the raw confidences. Then, the calibrated label and calibrated confidence correspond to the mixture component and the mixture weights for each datapoint.

Base model confidences In  [15], the expected calibration error of base models is better than their instruct counterparts. However, instruct models are better at following instructions and thus, in-context learning [59], [60]. When the classifier is an instruct model with a corresponding base model, we use a direct query on the classifier, like Fig 6, to obtain its label. To obtain its confidence, we pass the full query sent to the classifier along with its label to the classifier’s corresponding base model. Then, we perform a softmax on the logits for label tokens (\(0\) and \(1\)) from the base model to obtain base model confidences. Note that the two possible methods using only base model confidences are obtained by applying ConfSel(Algoithm 2) with the labels being either raw or calibrated with the confidence obtained from the base models. The "best base" method reports the best performing of these methods.

Pairwise Queries For each pairwise query, we supply \(4\) in-context examples of correct pairwise comparisons. These are created from the example bank by sampling an example labeled \(1\) and another labeled \(0\). Note that the example labeled \(1\) is more correct than the example labeled \(0\), which decides the label of the pairwise query. For the VisOnlyQA dataset, we use only \(2\) in-context examples for each pairwise comparisons. The prompts for pairwise query for BoolQ and VisOnlyQA dataset are shown in Fig 8 and  9. Note that for each pairwise method in PairSel(Algorithm 3) other than PairSel-kNN, we have \(2\) options for labels (raw or calibrated) and \(2-3\) options for confidences (raw, calibrated and base). For certain classifiers (SQLCoder) and datasets (VisOnlyQA), base models and their corresponding confidences are not available. The "best pairwise" method is obtained by computing the best performing method among all the combinations of pairwise algorithm, label and confidence for each \(\alpha\).

PairSel-kNN For each dataset, we set \(\lambda = 0.5\) as the relative weight of the NL/Image/Passage to the Question in Natural Language (NL). To compute \(\text{dist}_{\text{NL}}\), we compute embeddings for NL using ‘all-MiniLM-L6-V2’ from Sentence Transformers [61]. To compute \(\text{dist}_{\text{SQL}}\) in Spider and Bird dataset, we compute the SQL embeddings using SQL Graph Neural Networks proposed in Appendix 7.5, and compute the cosine distance between embeddings. We set \(k=10\) for k-Nearest Neighbors. Since we use the labels and confidences in PairSel, we again have \(2\) options for labels (raw or calibrated) and \(2-3\) options for confidences (raw, calibrated or base). The "best kNN" method computes the best performing method of PairSel-kNN among the different combinations of labels and confidences for each \(\alpha\).

Naive Classifier If \(\beta\in [0.5,1)\) is the fraction of the dataset with the majority label, then, if \(\alpha\) fraction of datapoints are sent for human labeling, the total accuracy of the naive classifier is \(\beta * (1 - \alpha) + \alpha\). Note that \(\beta =0.6\) for Spider and Bird datasets, while \(\beta= 0.5, 0.507\) and \(0.612\) for the Synthetic, VisOnlyQA and BoolQ datasets respectively.

7.3 Metrics↩︎

Assuming that a direct query costs \(1\) unit, a pairwise query costs \(2\) units, and a human query costs \(A\gg1\) units, we compute the cost for each algorithm in Table 2. By varying \(\alpha\) from \(0.01\) to \(0.9\), with estimated \(A=65\) we plot the total accuracy v/s cost for selective classification algorithms in Figures 10. In Table 2, we report the theoretical costs of all methods for any value of \(A\). If \(n\) is the total number of datapoints, then direct labeling costs \(n\) units. Further, if we use base model confidences, then each query needs to be passed through the base model resulting in additional cost of \(n\). For methods involving pairwise queries, we apply pairwise queries to only \(n\) datapoints. Since we use pairwise queries to obtain a sorting, this incurs \(n \log(n)\) cost. Combining base model confidences with pairwise queries incurs the highest cost. Note that using a distance metric in PairSel-kNN does not incur any additional cost apart from that due to sorting by pairwise queries and/or base model confidences.

To estimate \(A\), we find the ratio of the cost of a direct query to that of an expert. For the direct query, we consider the most expensive classifier as GPT-4o, which costs \(\$ 5 /1\text{M}\) tokens. In case there are additional instructions to the GPT-4o model, the total length of a direct query and its response is \(\approx 2K\) tokens. Therefore, the cost of one direct query is atmost \(\$0.02\). If the human is a product manager, with an average salary of \(\$39/\text{hr}\) [63] and spends around \(2\) minutes to verify a single datapoint, then the average human cost is \(\$1.3\). Therefore, the ratio \(A\approx 65\).

All our experiments except training SQL embeddings took around 2 weeks on one Nvidia A-10 GPU with \(12\) cores and \(20\) GB RAM. Training SQL embedding took 2 days for each seed on the same machine.

7.4 Additional Experimental Results↩︎

7.4.1 Total accuracy vs. Cost of Labeling↩︎

Note that the cost of base models or pairwise queries is negligible compared to human labeling cost due to the relatively large value of \(A\) and small value of \(n\) in Fig 10. Therefore, the performance is mostly affected by the value of \(\alpha\), due to which Fig 10 resembles Fig 7, and the conclusions drawn from Fig 7 carry forward to Fig 10. One key difference between cost and \(\alpha\), is when the cost of pairwise queries or base models becomes non-negligible. Note that this is for larger values of \(\alpha\). Conisder the cases of \(\alpha\) close to \(0.9\), the maximum value that we consider, we can see that raw and calibrated baselines end up at a smaller cost, while some additional and somewhat non-negligible cost is added to all other baselines due to pairwise queries or base model confidences.

7.4.2 Choice of confidence and labels↩︎

Note that for each of base, pairwise and kNN methods, we report only the best performing ones in Table [tab:tot95acc] and Fig 7. For base and kNN methods this choice is between different labels and different confidences. The performance of these different combinations can be inferred from that of the raw and calibrated baselines. For instance, calibrated performs better than raw for most \(\alpha\) values in Fig 7, for all datasets and classifiers except Synthetic, (BoolQ, Llama3.1), and VisOnlyQA with Gemma 3 and Qwen 2.5VL. The performance of the base model confidence and kNN methods with calibrated labels and(or) confidences is also better than that with raw labels for only these datasets and classifiers.

7.4.3 Parameter Sensitivity↩︎

Note that none of the algorithms in ConfSel or PairSel have any parameters except PairSel-kNN, where we have \(2\) parameters \(k\), the number of nearest neighbors and \(\lambda\), the relative importance of distance for question and passage/SQL/Image for BoolQ/Spider and Bird/VisOnlyQA datasets, respectively. We compare the total accuracy of for different values of \(k=5, 20\) and \(\lambda = 0.1, 1.0, 1.5\) in addition to the baseline of \(\lambda=0.5, k=10\) for various combinations of datasets and classifiers.

For each of these combinations, we report the performance of best kNN method in Table 3. Again, to measure the maximum sensitivity to parameters, we compute the best \(\alpha \leq 0.5\), where the absolute difference between total accuracy of any hyperparameter combination and the baseline hyperparameter of \(\lambda = 0.5, k=10\) is maximum. We also measure the difference of each hyperparameter combination to the actual baseline hyperparameter choice of \(\lambda = 0.5, k =10\). Note that we do not include the Synthetic dataset in Table 3 as there is no notion of \(\lambda\) defined for it.

2pt

From Table 3, we can see that PairSel-kNN is not sensitive to the choice of hyperparameters that we have taken, with either no difference in performance wrt baseline or very small difference. The only case where changing hyperparameters increases performance by a substantial amount compared to the boost in performance of the kNN method over the raw baseline in Table [tab:tot95acc] is for GLM 4.1V in the VisOnlyQA dataset, as their the kNN method itself does not improve performance by a lot. Further, the sensitivity to \(k\) is much lower than that of \(\lambda\). Additionally, the low sensitivity to hyperparameters of PairSel-kNN, as well as its comparable performance to other pairwise methods, indicates that it is indeed the use of pairwise queries that provides the largest boost in performance.

7.5 SQL Embeddings↩︎

7.5.0.1 Existing SQL Distance metrics

Measuring the distance between SQLs is a key requirement for PairSel-kNN. If we can access a database for each SQL, we can execute the SQL and match the outputs of two SQLs. This is termed as execution accuracy [11]. While being accurate, this requires access to sample data for the query which might not be available due to privacy considerations. Extracting high quality sample data that obtains different outputs for different queries is also non-trivial [64]. Treating SQLs as strings, we can compute metrics based on string matching [65] or sentence embeddings [61], however these fail to incorporate the syntactic structure of SQLs. SQLs, and in general, scripts in most programming languages, can be represented as an abstract syntax tree (AST) [66], which is used by the compiler to execute the script. CodeBLEU [67] is a string matching distance metric which incorporates the AST structure. Existing works incorporate information from the AST into neural architectures, but these are designed for different tasks :  [68] utilizes AST graph for schema linking,  [69] uses AST information in positional encodings to a transformer for NL2SQL with AST decoder and  [70] uses an AST-based decoder for NL2SQL.

7.5.0.2 Proposed SQL Embeddings

We propose an embedding for SQL statements which uses the SQL’s abstract syntax tree (AST). The AST of an SQL statement is a tree which mimics its execution by the compiler. Its nodes consist of SQL commands, table and column names and aliases. Its edges encode the logic and syntax of the SQL statement. In our case, we consider a directed AST with edges from the leaf nodes to parents. As this is a tree, it has a single root node with only incident edges, and a path from each leaf node to the root. Each SQL statement is parsed into its AST using sqlglot [71]. We further simplify this tree by resolving all ALIAS commands to their actual names. In Figure 12, we provide an example of a SQL command and its AST. Note that here the "SELECT" command is the root node. We treat this AST graph as a Message Passsing Graph Neural Network [72]. In our GNN, there are two types of nodes – a) SQL nodes, which contain SQL commands and operators and b) content nodes, which contain table and column names. Each node has a fixed node embedding vector obtained from a pre-trained model. For SQL nodes, we generate embeddings from a T5 [61] model fine-tuned on wikiSQL [73] dataset to encode SQL-specific information. Content nodes are arbitrary names, so we use a Sentence-T5 model [61] to encode them. Each node’s embedding vector has dimension \(768\). To compute a single embedding from each graph, we perform message passing with topological propagation. In our topological propagation [74], each node is visited only after all nodes incident to it have been visited. We now show the message passing for a given node. For leaf nodes, the message is simply its node embeddings. For any non-leaf node \(i\), the message \(m_i\) is obtained by an attention-based combination of its node embeddings \(v_i\) and the messages of its neighbors, \(\{m_j\}_{j\in \mathrm{nghbr}(i)}\). Here, \(\mathrm{nghbr}(i)\) is the set of neighbors of \(i\). If \(X_i\in \mathbb{R}^{(1 + \lvert \mathrm{nghbr}(i) \rvert)\times 768}\) is the stacked version of these vectors, i.e., \(X_i = [v_i^\intercal, m_1^\intercal, m_2^\intercal, \ldots,]\), then \(m_i = \mathrm{softmax}(\frac{Q X_i (K X_i )^\intercal}{\sqrt{768}}) V X_i\), where \(Q, K, V\in \mathbb{R}^{768 \times 768}\) are the query, key and value attention matrices to be learned. Note that this aggregation scheme resembles that of graph attention networks veličković2018graph?. Further, by topological propgation, we ensure that the message at root node has utilized combinations of all nodes in the tree. The message at root node \(m_{root}\) is defined as the embedding of the SQL statement.

Using this SQL embedding allows us to define a distance metric between different SQL statements and thus a distance metric for PairSel-kNN. We compare with a naive baseline of treating SQL as vanilla sentences and using sentence T5 model [61] to obtain embeddings. A concurrent work, FuncGMNEval  [75], also utilizes SQL’s syntactical structure for a GNN. Their input is a pair of SQL statements which are converted to their ROTs (Relational Operational Trees), which represents SQL’s execution plan based on relational algebra and are in general more representative of actual SQL execution than ASTs. Then, treating the ROTs of the two SQL statements as two different GNNs,  [75] train a GMN(Graph Matching Network) [76]. A GMN performs message passing on each node of the graph learning the node embeddings, edge embeddings and cross-graph attention weights to obtain a similarity score from their GMN.

7.5.0.3 Comparison to baselines for distance between SQLs.

We train our method and funcGMNEval on Spider-Pair dataset provided by  [75], which has pairs of SQL’s which are labeled \(0\) if they are similar and \(1\) if they’re dissimilar. We set the training time for both methods to be same, around  1.5 days. To train our method on Spider-Pair dataset, we adapt the training procedure of FuncGMNEval, but obtain the embeddings for the two SQLs separately using our AST GNNs and use cosine similarity between these vectors as the similarity metric instead of FuncGMNEval’s similarity score.

To compare different methods to compute distance metrics, we plot the AUC for the test dataset of Spider-Pair and the time taken to compute similarity of all pairs for the Bird dataset in Table 4. We compare our method, FuncGMNEval [75], and vanilla Sentence Embeddings. Further, we compute the time taken for computing all distances for all pairs of Bird, as it is the largest dataset we use (\(>900\) samples), and for PairSel-kNN, we need to compute distances between all pairs.

From Table 4, we can see that after similar training time, the performance of our method in terms of test AUC on the Spider-Pair dataset is slightly worse than the baseline FuncGMNEval. However, to compute the similarity between any two SQL statements, FuncGMNEval needs to perform a forward pass over the pair of SQL statements. In contrast, our method computes the embedding only once for each SQL statement separately, resulting in one forward pass per SQL statement. This makes our method much faster, by approximately an order of magnitude, when computing all pairs distance on the bird dataset Further, the sentence embedding baseline is faster than our method and FuncGMNEval, but its test AUC is extremely low as it considers SQL statements as sentences. Overall, our method achieves a balance between relative speed and performance. Thus, it can be utilized even in online settings, where the NL-SQL pair arrive one-by-one and we need to compute the distance between every new SQL statement and all existing SQL statements.

8 Additional Theoretical Details↩︎

We first compute \(F_{\mathrm{clf}}\). \[\begin{align} f_{\mathrm{clf}}(n) &= \frac{1}{\lvert S \rvert}\sum_{x_i \in S} \mathbf{1}\{\hat{y}_i \neq y_i^\star\}\\ \mathbb{E}_{\hat{y}_i, y^\star_i}[f_{\mathrm{clf}}(n)] &= \frac{1}{\lvert S \rvert} \sum_{x_i \in S} \mathbb{E}_{\hat{y}_i, y^\star}[\mathbf{1}\{\hat{y}_i \neq y_i^\star\}]\\ &= \frac{1}{\lvert S \rvert}\sum_{x_i \in S}(p_{\mathrm{clf},l}(x_i)(1 - p^\star(x_i))+ p^\star(x_i)(1 - p_{\mathrm{clf},l}(x_i)))\\ &=\frac{1}{\lvert S \rvert}\sum_{x_i \in S}(p_{\mathrm{clf},l}(x_i) + p^\star(x_i) - 2 p_{\mathrm{clf},l}(x_i)p^\star(x_i))\\ F_{\mathrm{clf}} &= \mathbb{E}_{x\sim {\mathcal{D}}_x}[\mathbb{E}_{\hat{y}_i, y_i^\star}[f_{\mathrm{clf}}(n)]] = \mathbb{E}_{x\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x) + p^\star(x) - 2 p_{\mathrm{clf},l}(x)p^\star(x)] \end{align}\] Similarly, we can compute \(F_h\). \[\begin{align} f_h(n) \triangleq& \frac{1}{\lvert S \rvert}\sum_{x_i\in S} \mathbf{1}\{\tilde{y}_i \neq y_i^\star\}\\ \mathbb{E}_{\tilde{y}_i^\star, y_i^\star}(f_h(n)) =& \frac{1}{\lvert S \rvert}\sum_{x\in S}(p_h(x) + p^\star(x) - p_h(x)p^\star(x))\\ F_h =& \mathbb{E}_{x\sim {\mathcal{D}}_x}[p_h(x) + p^\star(x) - 2p_h(x)p^\star(x)] \end{align}\] Further, by Chernoff bound based on iid sampled datapoints \(x_i\sim {\mathcal{D}}_x\), with probability \(1-\delta\), we have, \[\begin{align} \label{eq:chernoff95f} \max\{\lvert f_{\mathrm{clf}}(n) - F_{\mathrm{clf}} \rvert,\,\, \lvert f_h(n) - F_h \rvert\} = \mathcal{O}\left(\sqrt{\frac{2\log(2/\delta)}{n}}\right) \end{align}\tag{1}\]

8.1 Sufficient Conditions for Pairwise Queries to be Beneficial↩︎

We need to show \(F_{\mathrm{clf}, c}(\alpha) \geq F_{\mathrm{clf}, p}(\alpha)\) to show that pairwise queries are advantageous. Here, we establish certain sufficient conditions independent of the actual models for \(p_{\mathrm{clf},c}, p^\star, p_{\mathrm{clf},l}\) and \(p_h\) and the data distribution \({\mathcal{D}}_x\).

We define \(h_{c}, h_{p}:{\mathcal{X}}\to [0,1]\) as the following. \[\begin{align} h_{c}(x) &\triangleq \Pr_{x'\sim {\mathcal{D}}_x}[\lvert 2p_{\mathrm{clf},c}(x') - 1 \rvert \geq \lvert 2p_{\mathrm{clf},c}(x) - 1 \rvert]\\ h_{p}(x)& \triangleq \sqrt{\Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\leq p_{\mathrm{clf},l}(x)]\cdot \Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\geq p_{\mathrm{clf},l}(x)]} \end{align}\]

The first condition implies that at each datapoint, the human is a better labeler than the classifier, and the second relates the accuracy of \(p_{\mathrm{clf},c}\) to the actual prediction of the labeler. Note that if \(p_{\mathrm{clf},c}(x) = p_{\mathrm{clf},l}(x), \forall x\in {\mathcal{X}}\), then the second condition can never be satisfied. The consequence of this assumption is that \((2p^\star(x) - 1)(p_h(x) - p_{\mathrm{clf},l}(x))\geq 0\) and \((h_{p}(x))^{(1-\alpha)n} - (h_{c}(x))^{(1-\alpha)n}\geq 0\) for all \(x\in {\mathcal{X}}\), therefore, their product is always positive. Note that these conditions are very strict and are not satisfied by the models used in Assumption 1 and Theorems 1 and 2.

9 Proofs↩︎

9.1 Proofs of Lemmas 1 and 2↩︎

9.1.0.1 Proof of Lemma 1

Note that if a datapoint \(x_i\in S_{\alpha, c}, i\in [n]\), for all datapoints \(j\in S\setminus S_{\alpha, c}\), we should have \(\lvert 2p_{\mathrm{clf},c}(x_j) - 1 \rvert \geq \lvert 2 p_{\mathrm{clf},c}(x_i) - 1 \rvert\). Note that if \(x_i \in S_{\alpha,c}\), then we use the label \(\hat{y}_i\sim p_{\mathrm{clf},l}(x_i)\), otherwise, we use the label \(\tilde{y}_i \sim p_{h}(x_i)\). Therefore, \[\begin{align} F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)&= \frac{1}{n}\sum_{i=1}^n \mathbb{E}_{x_i \sim {\mathcal{D}}_x}\bigg[{\boldsymbol{1}}\{x_i\in S_{\alpha, c}\} \cdot (2p^\star(x_i) - 1)(p_h(x_i) - p_{\mathrm{clf},l}(x_i)\bigg] \end{align}\] Note that each term of the expectation is equal as \(x_i\) are iid. Further, \(\Pr[x_i\in S_{\alpha, c}] = (\Pr_{x}[\lvert 2p_{\mathrm{clf},c}(x) - 1 \rvert \geq \lvert 2p_{\mathrm{clf},c}(x_i) - 1 \rvert])^{(1-\alpha)n}\), as the other \((1-\alpha)n\) points are sampled independently from \({\mathcal{D}}_x\).

9.1.0.2 Proof of Lemma 2

The proof follows that of Lemma 1 with \(S_{\alpha, c}\) replaced by \(S_{\alpha, p}\). Note that an element \(x_i\in S_{\alpha, p}\) if and only if there are two sets of points \(S_1, S_2\), where \(S_1 \cap S_2 = \phi, S_1 \cup S_2 = S \setminus S_{\alpha, p}\) and \(\lvert S_1 \rvert = \lvert S_2 \rvert = \frac{(1-\alpha)n}{2}\), such that for each point \(x_j\in S_1\) \(p_{\mathrm{clf},l}(x_j) \geq p_{\mathrm{clf},l}(x_i)\) and for each point \(x_j\in S_2, p_{\mathrm{clf},l}(x_j) \leq p_{\mathrm{clf},l}(x_i)\). \(S_1\) and \(S_2\) correspond to the sets \(\{x_{(i)}, i \in [0, \frac{(1-\alpha)n}{2}]\}\) and \(\{x_{(i)}, i \in [\frac{n(1+\alpha)}{2}, n]\}\), the two parts of the sorted values on either side of the selected "middle" portion. Therefore, \[\Pr[x_i\in S_{\alpha, p}] = \left(\sqrt{\Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\leq p_{\mathrm{clf},l}(x)]\cdot \Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\geq p_{\mathrm{clf},l}(x)]}\right)^{(1-\alpha)n},\] as each datapoint is sampled iid from \({\mathcal{D}}_x\).

9.2 Proofs of Theorems 1 and 2↩︎

9.2.1 Preliminaries↩︎

In this section, we simplify the computation of \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\) and \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\) by computing the terms \(\Pr_{x'\sim {\mathcal{D}}_x}[\lvert 2p_{\mathrm{clf},c}(x')-1 \rvert \geq \lvert 2p_{\mathrm{clf},c}(x)-1 \rvert]\) and \(\\\sqrt{\Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\leq p_{\mathrm{clf},l}(x)]\cdot \Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\geq p_{\mathrm{clf},l}(x)]}\) in Lemmas 1 and  2 respectively.

9.2.2 Proof of Theorem 1↩︎

Let \(u=\varphi(x), \forall x\in {\mathcal{X}}\), then \(u\sim \mathrm{Unif}(\mathbb{S}^{d-1})\).

Let \(u = \rho w_{\mathrm{clf},c} + \sqrt{1-\rho^2}u_{\perp} = \lambda w_{\mathrm{clf},l} + \sqrt{1-\lambda^2}v_{\perp}\), where \(\langle u_{\perp}, w_{\mathrm{clf},c},=\rangle 0\) and \(\langle v_{\perp},w_{\mathrm{clf},l}\rangle = 0\). For \(x\sim \mathrm{Unif}(\mathbb{S}^{d-1})\), we need to find the distibutions on \(\rho,\lambda, u_{\perp}\) and \(v_{\perp}\) respectively.

Note that \(u_{\perp}\) is sampled uniformly from the \(d-1\)-dimensional unit sphere of \(d\)-dimensional unit vectors that are perpendicular to \(w_{\mathrm{clf},c}\), while \(v_{\perp}\) is sampled from a similar distribution of vectors perpendicular to \(w_{\mathrm{clf},l}\).

As for \(\rho\) and \(\lambda\), note that these belong to the same distribution, as the projection of a vector uniformly sampled from the unit sphere on a fixed vector, which is \(w_{\mathrm{clf},c}\) and \(w_{\mathrm{clf},l}\) for \(\rho\) and \(\lambda\) respectively. Further, if \(A_{d}(r)\) is the surface area of the \(d\)-dimensional unit sphere of radius \(r\). Then, \(\forall a,b\in [-1,1]\) with \(a\leq b\), we have, \[\begin{align} \Pr[\rho \in [a, b]] = \Pr[\lambda \in [a, b]] = \int_{a}^b\frac{A_{d-1}(\sqrt{1-a^2})}{A_d(1)} da = \frac{A_{d-1}(1)}{A_{d}(1)} \int_{a}^b(\sqrt{1 - a^2})^{d-3} da \label{eq:prob95sphere} \end{align}\tag{2}\] Note that the surface area of sphere which has a projection \(a\) on a fixed vector is simply the surface area of the \(d-1\) dimensional sphere of radius \(\sqrt{1-a^2}\).

We obtain the following conditions. \[\label{eq:sphere95main} \begin{align} & \rho \perp u_{\perp} \text{ and } \lambda \perp v_{\perp},\quad\mathbb{E}[\lambda] = \mathbb{E}[\rho] = 0, \quad \mathbb{E}[\lambda^2] = \mathbb{E}[\rho^2] = \frac{1}{d},\quad \mathbb{E}[u_{\perp}] = \mathbb{E}[v_{\perp}] = 0\\ &\quad\mathbb{E}[u_{\perp} u_{\perp}^\top] = \frac{1}{d-1}(I_d - w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top),\quad \mathbb{E}[v_{\perp} v_{\perp}^\top] = \frac{1}{d-1}(I_d - w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top) \end{align}\tag{3}\] We decompose the difference term \((2p^\star(x)-1)(p_h(x) -p_{\mathrm{clf},l}(x))\) \[\begin{align} (2p^\star(x)-1)(p_h(x) -p_{\mathrm{clf},l}(x)) &= \langle w^\star,u\rangle\langle u,w_{h} - w_{\mathrm{clf},l}\rangle = (w^\star)^\top uu^\top (w_h - w_{\mathrm{clf},l})\label{eq:sphere95err} \end{align}\tag{4}\]

Now, we can compute \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\) and \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\). As we need a positive lower bound on \(F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha)\) to show that \(F_{\mathrm{clf},c}(\alpha) \geq F_{\mathrm{clf},p}(\alpha)\), we compute an upper bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\) and a lower bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\).

9.2.2.1 Upper bound on ConfSel.

Note that the distribution of \(p_{\mathrm{clf},l}(x)\) and \(p_{\mathrm{clf},c}(x)\) is symmetric around \(\frac{1}{2}\) for spherical features and linear link function. So, we use Lemma 3 and  equation 2 to bound \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\). \[\begin{align} &\Pr_{x'\sim {\mathcal{D}}_x}[\lvert 2p_{\mathrm{clf},c}(x')-1 \rvert\geq \lvert 2p_{\mathrm{clf},c}(x)-1 \rvert] \\ &= \Pr_{x'}[\lvert \langle w_{\mathrm{clf},c},\varphi(x')\rangle \rvert \geq \lvert \langle w_{\mathrm{clf},c},\varphi(x)\rangle \rvert]=C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da \end{align}\] where \(C_1 = \frac{2A_{d-1}(1)}{A_d(1)}\).

To compute \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\), we can further simplify  equation 4 . \[\begin{align} uu^\top = \rho^2 w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top + (1-\rho^2) u_{\perp}u_{\perp}^\top + \rho\sqrt{1-\rho^2}(w_{\mathrm{clf},c} u_{\perp}^\top + u_{\perp}w_{\mathrm{clf},c}^\top) \end{align}\] Using  equation 3 and equation 4 , we obtain \[\begin{align} F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha) &= \mathbb{E}_x\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}(w^\star)^\top uu^\top (w_h - w_{\mathrm{clf},l})\right]\\ &=(w^\star)^\top\mathbb{E}_x\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n} uu^\top\right](w_h - w_{\mathrm{clf},l}) \end{align}\] Therefore, we only need to compute \(\mathbb{E}_x\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n} uu^\top\right]\). \[\begin{align} &\mathbb{E}_x\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n} uu^\top\right]\\ &= \mathbb{E}_x\Bigg[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}\\ &\quad \cdot(\rho^2 w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top + (1-\rho^2) u_{\perp}u_{\perp}^\top + \rho\sqrt{1-\rho^2}(w_{\mathrm{clf},c} u_{\perp}^\top + u_{\perp}w_{\mathrm{clf},c}^\top)) \Bigg]\\ & = \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {1};}}{\underbrace{\mathbb{E}_{\rho}\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}\rho^2\right] w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top}} \\ &\quad+ \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {2};}}{\underbrace{\mathbb{E}_{\rho}\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}(1-\rho^2)\right]\mathbb{E}_{u_{\perp}}[u_{\perp}u_{\perp}^\top]}} \\ &\quad+ \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {3};}}{\underbrace{\mathbb{E}_{\rho}\left[\left(C_1\int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}\rho\sqrt{1-\rho^2}\right](w_{\mathrm{clf},c}\mathbb{E}_{u_{\perp}}[u_{\perp}^\top] + \mathbb{E}_{u_{\perp}}[u_{\perp}]w_{\mathrm{clf},c}^\top)}} \end{align}\]

In the last step, we use the independence of \(\rho\) and \(u_{\perp}\). From  equation 3 , the term \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {3};}\) is \(0\). Further, \(\mathbb{E}_{u_{\perp}}[u_{\perp} u_{\perp}^\top] = \frac{1}{d-1}(I_d - w_{\mathrm{clf},c} w_{\mathrm{clf},c}^\top)\).

We use \(E_0 \triangleq \mathbb{E}_{\rho}[ (h(\rho))^{(1-\alpha)n}]\) and \(E_2 \triangleq = \mathbb{E}_{\rho}[ (h(\rho))^{(1-\alpha)n}\rho^2]\) where \(h(\rho) = \int_{\lvert \rho \rvert}^1 (\sqrt{1-a^2})^{d-3} da\). Further, we set \(W_{\mathrm{clf},c} = w_{\mathrm{clf},c} w_{\mathrm{clf},c}^\top\) Then, we can compute the required non-zero terms in above expression.

\[\begin{align} \label{eq:sphere95conf95final} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {1};} &= C_1^{(1-\alpha)n} E_2 W_{\mathrm{clf},c}, \quad \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {2};} = \frac{C_1^{(1-\alpha)n}(E_0 - E_2)}{d-1}(I_d - W_{\mathrm{clf},c}) \end{align}\tag{5}\]

9.2.2.2 Lower bound for PairSel-Middle.

The lower bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\) proceeds in a similar fashion to the upper bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\). Note that \(p_{\mathrm{clf},l}(x)\) is also symmetric around \(\frac{1}{2}\) under spherical features and linear link function. We use Lemma 3 and  equation 2 to bound the probability term. \[\begin{align} \sqrt{\Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\leq p_{\mathrm{clf},l}(x)]\cdot \Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\geq p_{\mathrm{clf},l}(x)]} &\geq \Pr_{x'\sim {\mathcal{D}}_x}[\langle w_{\mathrm{clf},l},\varphi(x')\rangle \geq \lvert \langle w_{\mathrm{clf},l},\varphi(x')\rangle \rvert]\\ &=C_2 \int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3}ds \end{align}\] where \(C_2 = \frac{A_{d-1}(1)}{A_d(1)} = \frac{C_1}{2}\). Note that this expression is exactly half that of the corresponding term for confidence queries. Further, we can use a similar decomposition of \(u u^\top\) in terms of \(\lambda\) and \(v_{\perp}\) to obtain, \[\begin{align} F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha) =(w^\star)^\top\mathbb{E}_x\left[\left(C_2\int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n} uu^\top\right](w_h - w_{\mathrm{clf},l}) \end{align}\] Now, following the decomposition of \(u u^\top\) in terms of \(\lambda\) and \(v_{\perp}\), we obtain, \[\begin{align} &\mathbb{E}_x\left[\left(C_2\int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n} uu^\top\right]\\ & = \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};}}{\underbrace{\mathbb{E}_{\lambda}\left[\left(C_2\int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}\lambda^2\right] w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top}} \\ &\quad + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};}}{\underbrace{\mathbb{E}_{\lambda}\left[\left(C_2\int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}(1-\lambda^2)\right]\mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}v_{\perp}^\top]}} \\ &\quad+ \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {6};}}{\underbrace{\mathbb{E}_{\lambda}\left[\left(C_2\int_{\lvert \lambda \rvert}^1 (\sqrt{1-a^2})^{d-3} da\right)^{(1-\alpha)n}\lambda \sqrt{1-\lambda ^2}\right](w_{\mathrm{clf},l}\mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}^\top] + \mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}]w_{\mathrm{clf},l}^\top)}} \end{align}\] The term \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {6};}\) is \(0\) from  equation 3 . Further, the terms \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};}\) and \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};}\) can be computed in terms of \(E_0\) and \(E_2\). We set \(W_{\mathrm{clf},l} = w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top\). \[\begin{align} \label{eq:sphere95pair95final} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};} = C_2^{(1-\alpha)n} E_2 W_{\mathrm{clf},l}, \quad \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};} = \frac{C_2^{(1-\alpha)n}(E_0 - E_2)}{d-1}(I_d - W_{\mathrm{clf},l}) \end{align}\tag{6}\]

9.2.2.3 Difference of errors

We can now compute the term \(F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha)\). \[\begin{align} F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha) &= (F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)) - (F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)) \\ &= (w^\star)^\top( \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {1};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {2};})(w_h - w_{\mathrm{clf},l})\\ \end{align}\] We first compute the difference \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {1};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {2};}\). \[\begin{align} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {4};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {5};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {1};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {2};} &= C_2^{(1-\alpha)n} E_2 W_{\mathrm{clf},l} + \frac{C_2^{(1-\alpha)n}(E_0 - E_2)}{d-1}(I_d - W_{\mathrm{clf},l}) \\ \quad &- C_1^{(1-\alpha)n} E_2 W_{\mathrm{clf},c} - \frac{C_1^{(1-\alpha)n}(E_0 - E_2)}{d-1}(I_d - W_{\mathrm{clf},c})\\ &= \frac{C_2^{(1-\alpha)n}}{d-1}\bigg((E_0 - dE_2) (2^{(1-\alpha)n - W_{\mathrm{clf},l}} W_{\mathrm{clf},c}) \\ &\quad - (2^{(1-\alpha)n} - 1) (E_0 - E_2) I_d\bigg) \end{align}\] Plugging this back, we obtain. \[\begin{align} &F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha) \\ &\geq \frac{C_2^{(1-\alpha)n}}{d-1}\bigg(( E_0 - d E_2) (2^{(1-\alpha)n} \langle w^\star,w_{\mathrm{clf},c}\rangle(\langle w_{\mathrm{clf},c},w_h\rangle - \langle w_{\mathrm{clf},c},w_{\mathrm{clf},l}\rangle) \\ &\quad-\langle w^\star,w_{\mathrm{clf},l}\rangle(\langle w_h,w_{\mathrm{clf},l}\rangle - 1)) - (2^{(1-\alpha)n} - 1)(E_0 - E_2)(\langle w^\star,w_h\rangle - \langle w^\star,w_{\mathrm{clf},l}\rangle)\bigg) \end{align}\] We require \(w_{\mathrm{clf},c}\) such that the RHS is \(\geq 0\). This implies, \[\begin{align} \label{eq:sphere95penul} &\langle w^\star,w_{\mathrm{clf},c}\rangle(\langle w_{\mathrm{clf},c},w_h\rangle - \langle w_{\mathrm{clf},c},w_{\mathrm{clf},l}\rangle)\nonumber\\ &\geq 2^{-(1-\alpha)n}(\langle w^\star,w_{\mathrm{clf},l}\rangle(\langle w_h,w_{\mathrm{clf},l}\rangle - 1)) \nonumber\\ &\quad + \frac{E_0 - E_2}{E_0 - d E_2}(1 - 2^{-(1-\alpha)n})(\langle w^\star,w_h\rangle - \langle w^\star,w_{\mathrm{clf},l}\rangle) \end{align}\tag{7}\] We now compute the terms \(E_0\) and an upper bound on \(E_2\) which satisfies our requirements.

Using these bounds on \(E_0\) and \(E_2\), we can make obtain an interpretable upper bound for the second term in  equation 7 . \[\begin{align} \frac{E_0 - E_2}{E_0 - d E_2} = 1 + \frac{(d-1)E_2}{E_0 - d E_2} = 1 +(1-1/d)(E_0/d E_2 - 1)^{-1} \end{align}\] If we plug in the value of \(E_0\) and the upper bound on \(E_2\), we obtain, \[\begin{align} \frac{E_0 - E_2}{E_0 - d E_2} \leq 1 + \Theta\left(d^{-((1-\alpha)n + 1)/2}((1-\alpha)n)^{-1}\right) \end{align}\] Plugging this into  equation 7 proves Theorem 1

9.2.3 Proof of Theorem 2↩︎

The proof for Gaussian features and \(L\)-smooth \(g\) follows that of Theorem 1 in Appendix 9.2.2. We set \(u = \varphi(x), \forall x\in {\mathcal{X}}\). Then, \(u\sim {\mathcal{N}}(0, I_d)\). Let \(u = \rho w_{\mathrm{clf},c} + u_{\perp} = \lambda w_{\mathrm{clf},l} + v_{\perp}\) where \(\langle w_{\mathrm{clf},c},u_{\perp}\rangle = \langle w_{\mathrm{clf},l},v_{\perp}\rangle=0\). As \(u\) is gaussian, \(\rho, \lambda, u_{\perp}\) and \(v_{\perp}\) are also gaussian.

These random variables have the following distribution. \[\label{eq:gauss95main} \begin{align} &\rho \perp u_{\perp} \quad \text{and} \quad \lambda \perp v_{\perp},\\ &\rho = \langle w_{\mathrm{clf},c},u\rangle\sim {\mathcal{N}}(0, 1), \quad \lambda = \langle w_{\mathrm{clf},l},u\rangle \sim {\mathcal{N}}(0,1),\\ & \mathbb{E}[u_{\perp} u_{\perp}^\top] + \mathbb{E}[\rho^2]w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top = \mathbb{E}[v_{\perp} v_{\perp}^\top] + \mathbb{E}[\lambda^2]w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top = I_d\\ & u_{\perp} = u - \rho w_{\mathrm{clf},c} \sim {\mathcal{N}}(0, I_d - w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top), \\ & v_{\perp} = u - \lambda w_{\mathrm{clf},l} \sim {\mathcal{N}}(0, I_d - w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top), \end{align}\tag{8}\]

For a \(L\)-smooth differentiable \(g\), we need to use Taylor’s expansion for the difference term \((2p^\star(x) - 1)(p_h(x) - p_{\mathrm{clf},l}(x))\). We use \(g'(0)=1\) and \(g(0) = \frac{1}{2}\) to write down the Taylor’s expansion for \(p^\star(x), p_h(x)\) and \(p_{\mathrm{clf},l}(x)\) around \(0\).

\[\label{eq:taylor} \begin{align} p^\star(x) &=g(0) + g'(0)\langle w^\star,u\rangle + r^\star(\langle w^\star,u\rangle)) = \frac{1}{2} + \langle w^\star,u\rangle + r^\star(\langle w^\star,u\rangle))\\ p_h(x) &=g(0) + g'(0)\langle w_h,u\rangle + r_h(\langle w_h,u\rangle))= \frac{1}{2} + \langle w_h,u\rangle + r_h(\langle w_h,u\rangle))\\ p_{\mathrm{clf},l}(x) &=g(0) + g'(0)\langle w_{\mathrm{clf},l},u\rangle + r_{\mathrm{clf},l}(\langle w_{\mathrm{clf},l},u\rangle) = \frac{1}{2} + \langle w_{\mathrm{clf},l},u\rangle + r_{\mathrm{clf},l}(\langle w_{\mathrm{clf},l},u\rangle) \end{align}\tag{9}\] By \(L\)-smoothness of \(g\), we have, \[\begin{align} \label{eq:l95smooth} \forall a\in \mathbb{R}, \quad \lvert r^\star(a) \rvert,\lvert r_h(a) \rvert, \lvert r_{\mathrm{clf},l}(a) \rvert \leq \frac{L}{2}\lvert a \rvert^2 \end{align}\tag{10}\] Therefore, \[\label{eq:gauss95err95main} \begin{align} &(2p^\star(x) - 1)(p_{h}(x) - p_{\mathrm{clf},l}(x)) \\ &= (\langle w^\star,u\rangle + r^\star(\langle w^\star,u\rangle))(\langle w_{h} - w_{\mathrm{clf},l},u\rangle + r_h(\langle w_{h},u\rangle) - r_{\mathrm{clf},l}(\langle w_{\mathrm{clf},l},u\rangle))\\ &= (w^\star) uu^\top (w_h - w_{\mathrm{clf},l}) + r(u)\\ \text{where}\quad r(u) &= \langle w^\star,u\rangle(r_h(\langle w_{h},u\rangle) - r_{\mathrm{clf},l}(\langle w_{\mathrm{clf},l},u\rangle)) + \langle w_{h} - w_{\mathrm{clf},l},u\rangle r^\star(\langle w^\star,u\rangle) \end{align}\tag{11}\]

We compute a bound on \(r(u)\). \[\begin{align} \lvert r(u) \rvert \leq& \lvert \langle w^\star,u\rangle \rvert(\lvert r_h(\langle w_{h},u\rangle) \rvert + \lvert r_{\mathrm{clf},l}(\langle w_{\mathrm{clf},l},u\rangle) \rvert) + (\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)\lvert r^\star(\langle w^\star,u\rangle) \rvert\nonumber\\ \leq& \frac{L}{2}\lvert \langle w^\star,u\rangle \rvert(\lvert \langle w_{h},u\rangle \rvert^2 + \lvert \langle w_{\mathrm{clf},l},u\rangle \rvert^2) + \frac{L}{2}(\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)\lvert \langle w^\star,u\rangle \rvert^2 \nonumber\\ \leq& \frac{L}{2}\lvert \langle w^\star,u\rangle \rvert\left((\lvert \langle w_{h},u\rangle \rvert^2 + \lvert \langle w_{\mathrm{clf},l},u\rangle \rvert^2) + (\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)\lvert \langle w^\star,u\rangle \rvert\right) \nonumber\\ \leq&\frac{L}{2}\lvert \langle w^\star,u\rangle \rvert\left((\lvert \langle w_{h},u\rangle \rvert + \lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)^2 + (\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)\lvert \langle w^\star,u\rangle \rvert\right) \nonumber\\ =& \frac{L}{2}\lvert \langle w^\star,u\rangle \rvert(\lvert \langle w_{h},u\rangle \rvert + \lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)(\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert+\lvert \langle w^\star,u\rangle \rvert)\label{eq:g95final} \end{align}\tag{12}\] We use triangle inequality in the first step and \(L\)-smoothness of \(g\) in the second step. In the fourth step, we use \(a^2 + b^2 \leq (a+b)^2\) for \(a,b\geq 0\).

We compute lower bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\) and upper bound on \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\) to compute a lower bound on the difference \(F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha)\).

Upper bound on ConfSel. The distributions of \(p_{\mathrm{clf},l}(x)\) is symmetric around \(\frac{1}{2}\) from Assumption 1 for gaussian features. From Lemma 1, we obtain, \[\begin{align} &\Pr_{x'\sim {\mathcal{D}}_x}[\lvert 2p_{\mathrm{clf},c}(x')-1 \rvert\geq \lvert 2p_{\mathrm{clf},c}(x)-1 \rvert] \\ &= \Pr_{x'}[\lvert \langle w_{\mathrm{clf},c},\varphi(x')\rangle \rvert \geq \lvert \langle w_{\mathrm{clf},c},\varphi(x)\rangle \rvert]=\Pr_{\rho'\sim {\mathcal{N}}(0,1)}[\lvert \rho' \rvert\geq \lvert \rho \rvert] = 2(1 - \Phi(\lvert \rho \rvert)) \end{align}\] We substitute \(u' = \varphi(x') = \rho' w_{\mathrm{clf},c} + u_{\perp}'\), where \(\langle w_{\mathrm{clf},c},u_{\perp}'\rangle=0\) which matches the decomposition of \(u\). Additionally, \(\Phi:\mathbb{R}\to [0,1]\) the cdf of unit normal distribution.

We set \(\widetilde{h}(\rho) \triangleq 1 - \Phi(\lvert \rho \rvert), W_{\mathrm{clf},c} = w_{\mathrm{clf},c}w_{\mathrm{clf},c}^\top\). From Eq equation 11 , we bound \(F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)\). \[\begin{align} &F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha) = \mathbb{E}_u[ (2\widetilde{h}(\rho))^{(1-\alpha)n} ((w^\star)^\top(uu^\top)(w_{h} - w_{\mathrm{clf},l}) + r(u))]\\ &= (w^\star)^\top\left(\underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {7};}}{\underbrace{\mathbb{E}_{\rho}[(2\widetilde{h}(\rho))^{(1-\alpha)n}\rho^2]W_{\mathrm{clf},c}}} + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {8};}}{\underbrace{\mathbb{E}_{\rho}[(2\widetilde{h}(\rho))^{(1-\alpha)n}]\mathbb{E}_{u_{\perp}}[u_{\perp}u_{\perp}^\top]}} \right)(w_{h} - w_{\mathrm{clf},l})\\ &\quad + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {9};}}{\underbrace{\mathbb{E}_{\rho}[(2\widetilde{h}(\rho))^{(1-\alpha)n}\rho](w^\star)^\top(w_{\mathrm{clf},c}\mathbb{E}_{u_{\perp}}[u_{\perp}^\top] + \mathbb{E}_{u_{\perp}}[u_{\perp}] w_{\mathrm{clf},c}^\top )(w_h - w_{\mathrm{clf},l})}} \\ &\quad + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}}{\underbrace{\mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n}r(u)]}} \end{align}\] Note that \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {9};}=0\) by symmetry of \(u_{\perp}\). Let \(E_{a,b} \triangleq \mathbb{E}_{\rho\sim {\mathcal{N}}(0,1)}[(\widetilde{h}(\rho))^{b}\lvert \rho \rvert^a]\) for all \(a\in \mathbb{N}\cup\{0\}\).

\[\begin{align} \label{eq:gauss95conf95final} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {7};} = 2^{(1-\alpha)n} E_{2,(1-\alpha)n} W_{\mathrm{clf},c},\quad \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {8};} = 2^{(1-\alpha)n} E_{0,(1-\alpha)n}(I_d - W_{\mathrm{clf},c}) \end{align}\tag{13}\]

We compute \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\) separately using  equation 12 .

\[\begin{align} &\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};} = \mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n}r(u)] \leq \mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n}\lvert r(u) \rvert]\\ &\leq\frac{L}{2}\mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n} \sqrt{\lvert \langle w^\star,u\rangle \rvert^2(\lvert \langle w_{h},u\rangle \rvert + \lvert \langle w_{\mathrm{clf},l},u\rangle \rvert)^2(\lvert \langle w_{h},u\rangle \rvert +\lvert \langle w_{\mathrm{clf},l},u\rangle \rvert+\lvert \langle w^\star,u\rangle \rvert)^2}]\\ &\leq\frac{\sqrt{6}L}{2}\mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n} \sqrt{\langle w^\star,u\rangle^2(\langle w_{h},u\rangle^2 + \langle w_{\mathrm{clf},l},u\rangle^2)(\langle w_{h},u\rangle^2 +\langle w_{\mathrm{clf},l},u\rangle^2+\langle w^\star,u\rangle^2)}]\\ &\leq\frac{\sqrt{6}L}{2}\mathbb{E}_{u}[(2\widetilde{h}(\rho))^{(1-\alpha)n} \sqrt{\langle w^\star,u\rangle^2 \langle w_{h},u\rangle^4} + \sqrt{\langle w^\star,u\rangle^4\langle w_{h},u\rangle^2} + \sqrt{\langle w^\star,u\rangle^2 \langle w_{\mathrm{clf},l},u\rangle^4} \\ &+ \sqrt{\langle w^\star,u\rangle^4 \langle w_{\mathrm{clf},l},u\rangle^2} +\sqrt{2\langle w_{h},u\rangle^2 \langle w^\star,u\rangle^2 \langle w_{\mathrm{clf},l},u\rangle^2}]\\ \end{align}\] For the second inequality, we use \(L\)-smoothness. We use \((\sum_{i=1}^l a_i)^2 \leq l \sum_{i=1}^l a_i^2\) to obtain the third inequality. In the fifth inequality, we use \(\sum_{i=1}^l \sqrt{a_i} \leq \sum_{i=1}^l \sqrt{a_i}, \forall a_i\geq 0, i\in [l]\).

Note that all the terms in this expression are of the form \(\langle w_1,u\rangle^2\langle w_2,u\rangle^2\) or \(2\langle w_1,u\rangle^2\langle w_2,u\rangle^2\langle w_3,u\rangle^2\), where \(w_1, w_2\) and \(w_3\) take values in \(\{w^\star, w_{\mathrm{clf},l}, w_h\}\). We use these simplified expressions to compute \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\).

Using the above lemma, for some constant \(C_5>0\), we can bound \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\) as, \[\begin{align} \label{eq:gauss95term9510} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};} \leq 2^{(1-\alpha)n}C_5 L \sum_{k=0}^3 E_{k,(1-\alpha)n}d^{(3-k)/2} \end{align}\tag{14}\]

9.2.3.1 Lower bound for PairSel-Middle.

By symmetry of \(p_{\mathrm{clf},l}(x)\) around \(\frac{1}{2}\) from Assumption 1 for gaussian features, and we apply Lemma 3. \[\begin{align} \sqrt{\Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\leq p_{\mathrm{clf},l}(x)]\cdot \Pr_{x'\sim {\mathcal{D}}_x}[p_{\mathrm{clf},l}(x')\geq p_{\mathrm{clf},l}(x)]} &\geq \Pr_{x'}[\langle w_{\mathrm{clf},l},\varphi(x')\rangle \geq \lvert \langle w_{\mathrm{clf},l},\varphi(x')\rangle \rvert]\\ &= \Pr_{\lambda \sim {\mathcal{N}}(0,1)}[\lambda' \geq \lvert \lambda \rvert] = 1 - \Phi(\lvert \lambda \rvert) \end{align}\] We use a similar parametrization of \(x'\) into \(\lambda' w_{\mathrm{clf},l} + v_{\perp}'\) where \(\langle v_{\perp}',w_{\mathrm{clf},l}\rangle=0\). We now find a lower bound for \(F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)\) using the \(\lambda, v_{\perp}\) parametrization and  equation 11 . Further, \(W_{\mathrm{clf},l} = w_{\mathrm{clf},l}w_{\mathrm{clf},l}^\top\)

\[\begin{align} &F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha) = \mathbb{E}_u[ (\widetilde{h}(\lambda))^{(1-\alpha)n} ((w^\star)^\top(uu^\top)(w_{h} - w_{\mathrm{clf},l}) + r(u))]\\ &= (w^\star)^\top\left(\underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {11};}}{\underbrace{\mathbb{E}_{\lambda}[(\widetilde{h}(\lambda))^{(1-\alpha)n}\lambda^2]W_{\mathrm{clf},l}}} + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {12};}}{\underbrace{\mathbb{E}_{\lambda}[(\widetilde{h}(\lambda))^{(1-\alpha)n}]\mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}v_{\perp}^\top]}} \right)(w_{h} - w_{\mathrm{clf},l})\\ &\quad + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {13};}}{\underbrace{\mathbb{E}_{\lambda}[(\widetilde{h}(\lambda))^{(1-\alpha)n}\lambda](w^\star)^\top(w_{\mathrm{clf},c}\mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}^\top] + \mathbb{E}_{\mathrm{clf}_{\perp}}[v_{\perp}] w_{\mathrm{clf},c}^\top )(w_h - w_{\mathrm{clf},l})}} \\ &\quad + \underset{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};}}{\underbrace{\mathbb{E}_{u}[(\widetilde{h}(\lambda))^{(1-\alpha)n}r(u)]}} \end{align}\] Note that \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {13};}=0\) by symmetry of \(v_{\perp}\). From  equation 8 , \(\lambda\) and \(\rho\) have the same distribution. Then,

\[\begin{align} \label{eq:gauss95pair95final} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {11};} = E_{2,(1-\alpha)n} W_{\mathrm{clf},l},\quad \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {12};} = E_{0,(1-\alpha)n}(I_d - W_{\mathrm{clf},l}) \end{align}\tag{15}\] To compute \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};}\), we use the same technique as \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\).

\[\begin{align} &\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};} = \mathbb{E}_{u}[(\widetilde{h}(\lambda))^{(1-\alpha)n}r(u)] \geq -\mathbb{E}_{u}[(\widetilde{h}(\lambda))^{(1-\alpha)n}\lvert r(u) \rvert]\\ \end{align}\] Since the bounds in Lemma 5 are independent of \(w_0, w_1,w_2,w_3\), we can use them here as well. This gives us the bound \[\begin{align} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};} \geq - C_5 L\sum_{k=0}^3 E_{k,(1-\alpha)n}d^{(3-k)/2} \label{eq:gauss95term9514} \end{align}\tag{16}\]

9.2.3.2 Difference of errors

We can now compute the term \(F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha)\). \[\begin{align} & F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha) = (F_{\mathrm{clf}} - F_{\mathrm{clf},p}(\alpha)) - (F_{\mathrm{clf}} - F_{\mathrm{clf},c}(\alpha)) \\ &= (w^\star)^\top( \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {11};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {12};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {7};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {8};})(w_h - w_{\mathrm{clf},l}) + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\\ \end{align}\] We first compute the difference \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {11};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {12};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {7};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {8};}\). \[\begin{align} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {11};} + \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {12};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {7};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {8};} &= E_{2,(1-\alpha)n} W_{\mathrm{clf},l} + E_{0,(1-\alpha)n}(I_d - W_{\mathrm{clf},l})\\ &\quad - 2^{(1-\alpha)n}(E_{2,(1-\alpha)n} W_{\mathrm{clf},c} + E_{0,(1-\alpha)n}(I_d - W_{\mathrm{clf},c})) \\ &= (E_{0,(1-\alpha)n} - E_{2,(1-\alpha)n})(2^{(1-\alpha)n} W_{\mathrm{clf},c} - W_{\mathrm{clf},l}) \\ &\quad+E_{0,(1-\alpha)n} I_d(1 - 2^{(1-\alpha)n}) \end{align}\]

We now compute the difference \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};}\) using  equation 14 and  equation 16 .

\[\begin{align} \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {14};} - \tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1.2pt] (char) {10};} \geq -(1 + 2^{(1-\alpha)n}) C_5 L\sum_{k=0}^3 E_{k,(1-\alpha)n}d^{(3-k)/2} \end{align}\]

Plugging this back, we obtain. \[\begin{align} F_{\mathrm{clf},c}(\alpha) - F_{\mathrm{clf},p}(\alpha) \geq & (E_{0,(1-\alpha)n} - E_{2,(1-\alpha)n})(2^{(1-\alpha)n} \langle w^\star,w_{\mathrm{clf},c}\rangle\\ &\quad \cdot(\langle w_{\mathrm{clf},c},w_h\rangle - \langle w_{\mathrm{clf},c},w_{\mathrm{clf},l}\rangle) -\langle w^\star,w_{\mathrm{clf},l}\rangle(\langle w_h,w_{\mathrm{clf},l}\rangle - 1))\\ &\quad - (2^{(1-\alpha)n} - 1)E_{0,(1-\alpha)n}(\langle w^\star,w_h\rangle - \langle w^\star,w_{\mathrm{clf},l}\rangle)\\ &\quad -(1 + 2^{(1-\alpha)n})C_5 L\sum_{k=0}^3 E_{k,(1-\alpha)n}d^{(3-k)/2} \end{align}\]

We require \(w_{\mathrm{clf},c}\) such that the RHS is \(\geq 0\). This implies, \[\begin{align} \label{eq:gauss95penul} &\langle w^\star,w_{\mathrm{clf},c}\rangle(\langle w_{\mathrm{clf},c},w_h\rangle - \langle w_{\mathrm{clf},c},w_{\mathrm{clf},l}\rangle) \\ &\geq\, 2^{-(1-\alpha)n}(\langle w^\star,w_{\mathrm{clf},l}\rangle(\langle w_h,w_{\mathrm{clf},l}\rangle - 1)) \nonumber\\ &\quad + \frac{(1 - 2^{-(1-\alpha)n})E_{0,(1-\alpha)n}}{E_{0,(1-\alpha)n}-E_{2,(1-\alpha)n}}(\langle w^\star,w_h\rangle - \langle w^\star,w_{\mathrm{clf},l}\rangle)\nonumber\\ &\quad + \frac{(1 + 2^{-(1-\alpha)n})C_5 L}{E_{0,(1-\alpha)n} - E_{2,(1-\alpha)n}}C_5 L\sum_{k=0}^3 E_{k,(1-\alpha)n}d^{(3-k)/2} \end{align}\tag{17}\]

We compute the term \(E_{0,b}\) and find upper bounds on \(E_{a,b}\) for \(a,b\in \mathbb{N}\) with \(a\) being even to obtain a tight and interpretable upper bound on the RHS.

From this Lemma, we can simplify the terms of \(\frac{E_{0,(1-\alpha)n}}{E_{0,(\alpha)n} - E_{2,(\alpha)n}} \leq 1 + o(1)\) and the coefficients of terms of \(L\) are bounded by \(\mathcal{O}(1)\). Plugging this into  equation 17 proves Theorem 2 with \(g'(0)=1\). To work with \(g'(0)\neq 1\), we replace \(g\) by \(\tilde{g}(a) = \frac{g(a)}{g'(0)},\forall a\in \mathbb{R}\) in the above proof. The smoothness constant for \(\tilde{g}\) is now \(\frac{L}{g'(0)}\), which gives us the correct statement of Theorem 2.