Rank-Induced PL Mirror Descent: A Rank-Faithful Second-Order Algorithm for Sleeping Experts
Tiantian Zhang [email protected] · 2025
Read Rank-Induced PL Mirror Descent: A Rank-Faithful Second-Order Algorithm for Sleeping Experts by Tiantian Zhang [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18138.txt.
Introduction
Tiantian Zhang presents a new learning rule for advice from experts who wake and sleep. Her 2025 paper deals with the sleeping experts task, where just some advisors are live each round. A learner must pick whom to trust while the live set shifts over time.
Her rule, RIPLM, works in a rank-based form drawn from the Plackett-Luce model. Past rules worked on expert names, not ranks. By staying in the rank form at each round, the rule keeps a known match with a rank bench mark. Zhang claims it is the first such rule that is both rank-true and adapts to variance.
Catalog record
| CREATOR | Tiantian Zhang [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18138
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rank-Induced PL Mirror Descent: A Rank-Faithful Second-Order Algorithm for Sleeping Experts Tiantian Zhang [email protected] Abstract We introduce a new algorithm, Rank-Induced Plackett–Luce Mirror Descent (RIPLM) , which leverages the structural equivalence between the rank benchmark and the distributional benchmark established in Bergam et al. 2022 . Unlike prior approaches that operate on expert identities, RIPLM updates directly in the rank-induced Plackett–Luce (PL) parameterization. This ensures that the algorithm’s played distributions remain within the class of rank-induced distributions at every round, preserving the equivalence with the rank benchmark. To our knowledge, RIPLM is the first algorithm that is both (i) rank-faithful and (ii) variance-adaptive in the sleeping experts setting. Tiantian ZHANG Tiantian Zhang † † heading: 23 2022 1- 1/21; Revised 5/22 9/22 21-0000 † † heading: 25 2025 1- 9/25 9/25 25-0000 † † shortheadings: Rank-Induced PL Mirror Descent / Zhang † † firstpage: 1 keywords sleeping experts, online learning, Plackett–Luce models, second-order bounds 1 From Second-Order Sleeping Experts The work of Bergam et al. 2022 introduced three insights that reshape algorithm design for sleeping experts: 1.1 Equivalence of Benchmarks via PL Models They prove that the rank benchmark L_{T}^{(\rank)}=\min_{\sigma\in S_{N}}\sum_{t=1}^{T}\ell_{t,\sigma(E_{t})} and the distributional benchmark L_{T}^{(dist)}=\inf_{u\in\Delta^{N-1}}\sum_{t=1}^{T}\frac{1}{u(E_{t})}\sum_{i\in E_{t}}u_{i}\ell_{t,i} are equivalent in expectation under stochastic loss or availability. The bridge is the Plackett–Luce (PL) model : the \varepsilon -rank-induced distribution u(\varepsilon)\propto(1,\varepsilon,\dots,\varepsilon^{N-1}) ordered by \sigma^{\star} satisfies \lim_{\varepsilon\to 0}L_{T}(u(\varepsilon))=L_{T}^{(\rank)} . They also show that minimizing L_{T}(u) is non-convex and the infimum may not be attained. Thus, algorithms must remain inside the PL manifold to be rank-faithful. 1.2 Second-Order Regret Bounds Classical algorithms achieve O(\sqrt{T\log N}) regret. Bergam et al. 2022 improve this by replacing T with a cumulative variance measure, deriving O(\sqrt{\VAR_{T}^{\max}\log N}) bounds under stochastic availability. However, in the fully adversarial setting their efficient method suffers an extra N factor, O(\sqrt{\VAR_{T}^{\max}N\log N}+N\log N) , exposing inefficiency in permutation-based methods. 1.3 NP-Hardness of Best Ordering They show that computing the optimal ranking \sigma^{\star} is NP-complete, ruling out exact ranking search in polynomial time. 1.4 Motivation for RIPLM Together, these insights form a blueprint: • To respect the rank benchmark, remain inside PL distributions. • To exploit variance adaptivity, use centered residuals with AdaGrad scaling. • To bypass NP-hardness, update in O(N) score space rather than over N! rankings. RIPLM is a direct instantiation of this blueprint. 2 Rank-Induced PL Mirror Descent (RIPLM) 2.1 Algorithm We maintain scores s_{i}\in\mathbb{R} . At round t , given awake set E_{t}\subseteq[N] , define the PL distribution p_{t}(i)=\frac{\exp(s_{i}/\tau_{t})\mathbf{1}\{i\in E_{t}\}}{\sum_{j\in E_{t}}\exp(s_{j}/\tau_{t})}, with temperature \tau_{t}>0 . After observing losses \ell_{t,i} , update g_{t,i}=\tfrac{p_{t}(i)}{\tau_{t}}\big(\ell_{t,i}-\langle p_{t},\ell_{t}\rangle\big),\quad G_{t,i}=\sum_{s=1}^{t}g_{s,i}^{2},\quad s_{t+1,i}=s_{t,i}-\eta\,g_{t,i}/\sqrt{G_{t,i}+\delta}. Algorithm 1 Rank-Induced PL Mirror Descent (RIPLM) Initialize s_{i}=0 , G_{i}=0 for all i\in[N] . for round t=1,\dots,T do Observe awake set E_{t}\subseteq[N] . Define PL distribution on E_{t} : p_{t}(i)=\frac{\exp(s_{i}/\tau_{t})\,\mathbf{1}\{i\in E_{t}\}}{\sum_{j\in E_{t}}\exp(s_{j}/\tau_{t})}. Sample i_{t}\sim p_{t} . Observe losses \ell_{t,i} for all i\in E_{t} . Compute mean loss \bar{\ell}_{t}=\sum_{j\in E_{t}}p_{t}(j)\,\ell_{t,j} . for each i\in E_{t} do Compute residual r_{t,i}=\ell_{t,i}-\bar{\ell}_{t} . Compute gradient g_{t,i}=\tfrac{p_{t}(i)}{\tau_{t}}r_{t,i} . Update accumulator G_{i}\leftarrow G_{i}+g_{t,i}^{2} . Update score s_{i}\leftarrow s_{i}-\eta\tfrac{g_{t,i}}{\sqrt{G_{i}+\delta}} . end for Update temperature: \tau_{t+1}\leftarrow\max\left(\tau_{\min},\,\frac{c}{\sqrt{\sum_{i\in E_{t}}p_{t}(i)r_{t,i}^{2}+\delta}}\right) \triangleright Optional cooling end for Implementation Notes The temperature schedule \tau_{t} is optional but recommended: decay it inversely with the empirical standard deviation of residuals to approach the \varepsilon -rank-induced limit. A small \delta>0 (e.g., 10^{-6} ) stabilizes divisions. Tune \eta or use a doubling trick if V_{T} is unknown. 2.2 Explicit Regret Bounds Theorem 1 (General second-order regret, fixed temperature) . Assume \ell_{t,i}\in[0,1] for all t,i . Fix a temperature \tau>0 and run RIPLM with \tau_{t}\equiv\tau . Initialize s_{1,i}=\tau\log\pi_{i} for a prior \pi\in\Delta([N]) . For any comparator u\in\Delta([N]) with u_{i}>0 , define its restriction \tilde{u}_{t}(i)=u_{i}\,\mathbf{1}\{i\in E_{t}\}/u(E_{t}) . Then \sum_{t=1}^{T}\langle p_{t}-\tilde{u}_{t},\ell_{t}\rangle\;\leq\;C\,\frac{\sqrt{N}}{\tau}\,\sqrt{\,V_{T}\big(\KL(u\|\pi)+\ln\ln(1+T)\big)}, where V_{T}=\sum_{t=1}^{T}\sum_{i\in E_{t}}p_{t}(i)\big(\ell_{t,i}-\langle p_{t},\ell_{t}\rangle\big)^{2} and C>0 is universal. Proof sketch. Run RIPLM with a fixed temperature \tau_{t}\equiv\tau>0 and potential \Psi_{\tau}(s)\;=\;\tau\log\!\sum_{j\in E_{t}}e^{s_{j}/\tau},\quad\text{so}\quad p_{t}=\nabla\Psi_{\tau}(s_{t}). For the surrogate \tilde{L}_{t}(s)=\langle\nabla\Psi_{\tau}(s),\ell_{t}\rangle , the exact gradient is \frac{\partial\tilde{L}_{t}}{\partial s_{i}}=\frac{p_{t}(i)}{\tau}\big(\ell_{t,i}-\langle p_{t},\ell_{t}\rangle\big)\;=:\;g_{t,i}. Diagonal AdaGrad mirror descent with fixed potential (and H_{t}=\mathrm{diag}(\sqrt{G_{t,i}+\delta}) , G_{t,i}=\sum_{s\leq t}g_{s,i}^{2} , s_{1,i}=\tau\log\pi_{i} ) yields, for any comparator q_{t}\in\Delta(E_{t}) , \sum_{t=1}^{T}\big(\langle p_{t},\ell_{t}\rangle-\langle q_{t},\ell_{t}\rangle\big)\;\leq\;\tau\,\KL(q_{1}\|\pi)\;+\;\eta\sum_{t=1}^{T}\|g_{t}\|_{H_{t}^{-1}}^{2}\;+\;\tfrac{c}{\eta}\ln\ln(1+T). Instantiate q_{t}=\tilde{u}_{t}:=u(\cdot)\mathbf{1}\{\cdot\in E_{t}\}/u(E_{t}) (restriction of arbitrary u\in\Delta([N]) with u_{i}>0 ). The AdaGrad telescoping plus Cauchy–Schwarz give \sum_{t=1}^{T}\|g_{t}\|_{H_{t}^{-1}}^{2}\;\leq\;2\sum_{i}\sqrt{G_{T,i}+\delta}\;\leq\;\frac{2\sqrt{N}}{\tau}\sqrt{V_{T}}, since g_{t,i}^{2}=\frac{p_{t}(i)^{2}}{\tau^{2}}r_{t,i}^{2}\leq\frac{p_{t}(i)}{\tau^{2}}r_{t,i}^{2} with r_{t,i}=\ell_{t,i}-\langle p_{t},\ell_{t}\rangle and \sum_{i}\sqrt{\sum_{t}p_{t}(i)r_{t,i}^{2}}\leq\sqrt{N}\sqrt{\sum_{t,i}p_{t}(i)r_{t,i}^{2}} . Optimizing \eta gives \sum_{t=1}^{T}\langle p_{t}-\tilde{u}_{t},\ell_{t}\rangle\;\leq\;C\,\frac{\sqrt{N}}{\tau}\,\sqrt{\,V_{T}\big(\KL(u\|\pi)+\ln\ln(1+T)\big)}. Finally, note \tilde{L}_{t}(s^{u})=\langle\tilde{u}_{t},\ell_{t}\rangle for any s^{u} with \nabla\Psi_{\tau}(s^{u})=\tilde{u}_{t} (surjectivity: s^{u}_{i}=\tau\log\tilde{u}_{t}(i)+c ). ∎ Corollary 2 (PL comparators) . If u=u^{\mathrm{PL}}_{\sigma} is any fixed-temperature Plackett–Luce distribution induced by \sigma , then \tilde{u}_{t} preserves the PL form on each E_{t} , so \sum_{t=1}^{T}\langle p_{t},\ell_{t}\rangle-\sum_{t=1}^{T}\langle u^{\mathrm{PL}}_{\sigma},\ell_{t}\rangle\;\leq\;O\!\left(\frac{\sqrt{N}}{\tau_{\min}}\,\sqrt{\,V_{T}\big(\KL(u^{\mathrm{PL}}_{\sigma}\|\pi)+\ln\ln(1+T)\big)}\right). Corollary 3 (Rank benchmark) . Let \sigma\in S_{N} and u^{\tau_{t}}_{\sigma} the PL distribution induced by \sigma at \tau_{t} . Then \sum_{t=1}^{T}\langle p_{t},\ell_{t}\rangle-L_{T}^{(\rank)}(\sigma)\;\leq\;O\!\left(\frac{\sqrt{N}}{\tau_{\min}}\,\sqrt{\,V_{T}(\KL(u^{\mathrm{PL}}_{\sigma}\|\pi)+\ln\ln T)}\right)+\sum_{t=1}^{T}O(e^{-1/\tau_{t}}). Lemma 4 (Surjectivity of restricted softmax) . Fix a round t , a temperature \tau_{t}>0 , and an awake set E_{t}\subseteq[N] . For any u\in\mathrm{ri}\,\Delta(E_{t}) (i.e., u_{i}>0 for all i\in E_{t} and \sum_{i\in E_{t}}u_{i}=1 ), there exists a score vector s^{u}_{t}\in\mathbb{R}^{E_{t}} such that \nabla\Psi_{\tau_{t}}(s^{u}_{t})\;=\;\mathrm{softmax}(s^{u}_{t}/\tau_{t})\;=\;u\quad\text{where}\quad\Psi_{\tau_{t}}(s)=\tau_{t}\log\!\sum_{j\in E_{t}}e^{s_{j}/\tau_{t}}. In particular, one may take s^{u}_{t,i}=\tau_{t}\log u_{i}+c_{t} for any constant c_{t}\in\mathbb{R} . Proof. For i\in E_{t} , define s^{u}_{t,i}=\tau_{t}\log u_{i} and choose any c_{t}\in\mathbb{R} ; adding c_{t} shifts all logits but leaves softmax unchanged. Then \frac{e^{s^{u}_{t,i}/\tau_{t}}}{\sum_{j\in E_{t}}e^{s^{u}_{t,j}/\tau_{t}}}=\frac{e^{\log u_{i}}}{\sum_{j\in E_{t}}e^{\log u_{j}}}=\frac{u_{i}}{\sum_{j\in E_{t}}u_{j}}=u_{i}, since u is supported on E_{t} and sums to 1 there. Hence \nabla\Psi_{\tau_{t}}(s^{u}_{t})=u . ∎ Remark 5 (Comparators with zeros) . If a target comparator u\in\Delta([N]) has some u_{i}=0 , work with its restriction \tilde{u}_{t} on E_{t} ; if \tilde{u}_{t} has zeros, define the smoothed comparator \tilde{u}_{t}^{(\epsilon)}=(1-\epsilon)\tilde{u}_{t}+\epsilon\,\Unif(E_{t}) . By Lemma 4 , there exists s^{(\epsilon)}_{t} with \nabla\Psi_{\tau_{t}}(s^{(\epsilon)}_{t})=\tilde{u}_{t}^{(\epsilon)} . Because \ell_{t,i}\in[0,1] , replacing \tilde{u}_{t} by \tilde{u}_{t}^{(\epsilon)} changes the benchmark by at most \|\tilde{u}_{t}-\tilde{u}_{t}^{(\epsilon)}\|_{1}\leq 2\epsilon per round, so the total bias is \leq 2\epsilon T and vanishes as \epsilon\downarrow 0 . Remark 6 (Comparators on sleeping rounds) . When E_{t}\subsetneq[N] , the natural comparator is the restriction of u to E_{t} , i.e. \tilde{u}_{t}(i)=\frac{u(i)\mathbf{1}\{i\in E_{t}\}}{u(E_{t})}. This ensures the benchmark \langle\tilde{u}_{t},\ell_{t}\rangle is well defined even when some experts are asleep. Such restrictions are standard in the analysis of sleeping experts; see Cesa-Bianchi and Lugosi 2006 for the analogous argument in the full-information experts setting. 3 Minimax Lower Bound Theorem 7 (Minimax lower bound at \sqrt{V\log N} ) . For any N\geq 2 and horizon T , there exists a distribution over losses with E_{t}=[N] such that for any algorithm A , \mathbb{E}\big[V_{T}\big]\asymp T\quad\text{and}\quad\mathbb{E}\!\left[\sum_{t=1}^{T}\langle p_{t},\ell_{t}\rangle-\min_{\sigma\in S_{N}}\sum_{t=1}^{T}\ell_{t,\sigma(E_{t})}\right]\;\geq\;c\sqrt{T\log N}. Consequently, writing V=\mathbb{E}[V_{T}] , one has \inf_{A}\sup\mathbb{E}[\mathrm{Regret}_{T}^{(\rank)}(A)]\geq c^{\prime}\sqrt{V\log N}. The proof adapts the standard experts lower bound ( Cesa-Bianchi and Lugosi 2006 , Thm. 3.7) ; see Appendix B. Proof sketch. We use the standard randomized experts construction ( Cesa-Bianchi and Lugosi 2006 , Thm. 3.7 ): one expert has mean loss 1/2-\varepsilon and the rest have mean 1/2+\varepsilon . Identifying the best expert requires \Omega(1/\varepsilon^{2}) exploration rounds, so \mathbb{E}[V_{T}]\asymp T when T=\Theta(1/\varepsilon^{2}) . Information-theoretic lower bounds then yield \Omega(\sqrt{T\log N}) regret, which translates directly to \Omega(\sqrt{V_{T}\log N}) . Full details are in Appendix B. ∎ 4 Conclusion RIPLM unifies three desiderata: rank-faithfulness, variance adaptivity, and efficiency. It achieves regret O(\sqrt{V_{T}(\ln N+\ln\ln T)}) against the rank benchmark, matching minimax lower bounds up to logarithmic factors. Future directions include: (i) bandit feedback via implicit exploration, (ii) instance-dependent complexity through rank-based priors, and (iii) empirical validation on recommendation and scheduling datasets. Appendix: Detailed Proofs Appendix A: Full Proof of Theorem 2 This appendix provides