ectral gap is larger, as evidenced in previous learning to rank results in simpler settings [@NOS14; @SBB15; @HOX14]. This is made precise in , and in the main result of Theorem \[thm:main2\], we appropriately rescale the spectral gap and use $\alpha\in[0,1]$ defined as $$\begin{aligned}
    \label{eq:lambda2_L1}
    \alpha &\equiv& \frac{\lambda_2(L)(d-1)}{\Tr(L)}  \;\;=\;\; \frac{\lambda_2(L)(d-1)}{\sum_{j = 1}^n \ell_j } \;. \end{aligned}$$ The accuracy also depends on the topology via the maximum weighted degree defined as $D_{\max} \equiv \max_{i \in [d]} D_{ii} = \max_{i \in [d]} \{ \sum_{j: i \in S_j} \ell_j/\kappa_j\}$. Note that the average weighted degree is $\sum_i D_{ii}/ d = \Tr(L)/d$, and we rescale it by $D_{\rm max}$ such that $$\begin{aligned}
    \label{eq:lambda2_L1beta}
    \beta &\equiv& \frac{\Tr(L)}{d D_{\max}}  \;\;=\;\; \frac{\sum_{j = 1}^n \ell_j }{d D_{\max}} \;. \end{aligned}$$ We will show that the performance of rank breaking estimator depends on the topology of the graph through these two parameters. The larger the spectral gap $\alpha$ the smaller error we get with the same effective sample size. The degree imbalance $\beta\in[0,1]$ determines how many samples are required for the analysis to hold. We need smaller number of samples if the weighted degrees are balanced, which happens if $\beta$ is large (close to one).

The following quantity also determines the convexity of the objective function. $$\begin{aligned}
    \label{eq:gamma_def}
     \gamma \;\equiv\; \min_{j \in [n]} \Bigg\{ \Bigg(1 - \frac{p_{j,\ell_j}}{\kappa_j} \Bigg)^{{\left \lceil{2e^{2b}} \right \rceil}-2}\Bigg\}  \;.\; 
    \end{aligned}$$ Note that $\gamma$ is between zero and one, and a larger value is desired as the objective function becomes more concave and a better accuracy follows. When we are collecting data where the size of the offerings $\kappa_j$’s are increasing with $d$ but the position of the separators are close to the top, such that $\kappa_j = \omega(d)$ and $p_{j,\ell_j} = O(1)$, then for $b=