b(\theta^*),\Delta\rangle \; =\; \frac{1}{2}\Delta^\top H(\theta)\Delta \leq -\frac{1}{2}\lambda_2(-H(\theta)){\|\Delta\|}_2^2,\end{aligned}$$ where the last inequality holds because the Hessian matrix $-H(\theta)$ is positive semi-definite with $H(\theta){\boldsymbol{1}} = {\boldsymbol{0}}$ and $\Delta^\top{\boldsymbol{1}} = 0$. Combining and , $$\begin{aligned}
 \label{eq:thm_ml_3}
{\|\Delta\|}_2 \;\;\leq\;\; \frac{2{\|\nabla\Lrb(\theta^*)\|}_2}{\lambda_2(-H(\theta))}.\end{aligned}$$ Note that $\theta \in \Omega_b$ by definition. Theorem \[thm:main\] follows by combining Equation with Lemma \[lem:gradient\_topl\] and Lemma \[lem:hessian\_positionl\].

### Proof of Lemma \[lem:gradient\_topl\]

The idea of the proof is to view $\nabla\Lrb(\theta^*)$ as the final value of a discrete time vector-valued martingale with values in $\reals^d$. Define $\nabla\L_{G_{j,a}}(\theta^*)$ as the gradient vector arising out of each rank-breaking graph $\{G_{j,a}\}_{j\in [n], a \in [\ell_j]}$ that is $$\begin{aligned}
    \label{eq:rev1}
    \nabla_i\L_{G_{j,a}}(\theta^*) \equiv \sum_{\substack{\i \in S_j \\ \i \neq i}} \,\lambda_{j,a}\,\I_ {\big\{(i,\i) \in G_{j,a}\big\}}  \,\Bigg(\I_{\big\{\sigma_j^{-1}(i) < \sigma_j^{-1}(\i)\big\}}  - \frac{\exp(\theta_i^*)}{\exp(\theta_i^*) + \exp(\theta_{\i}^*)} \Bigg)\;.\end{aligned}$$ Consider $\nabla\L_{G_{j,a}}(\theta^*)$ as the incremental random vector in a martingale of $\sum_{j=1} \ell_j$ time steps. Lemma \[lem:consistency\] shows that the expectation of each incremental vector is zero. Observe that the conditioning event $\{i'' \in S \,:\,\sigma^{-1}(i'')<p_{j,a} \}$ given in is equivalent to conditioning on the history $\{G_{j,a'}\}_{a'<a}$. Therefore, using the assumption that the rankings $\{\sigma_j\}_{j \in [n]}$ are mutually independent, we have that the conditional expectation of $\nabla\L_{G_{j,a}}(\theta^*)$ conditioned on $\{G_{j',a''}\}_{j' < j, a'' \in [\ell_{j'}]}$ is zero. Further, the conditional expectation of $\nabla\L_{G_{j,a}}(\theta^*)$ is zero even when condi