More Like this

1. Accelerated Spectral Ranking

   Agarwal, Arpit; Patil, Prathamesh; Agarwal, Shivani (January 2018, Proceedings of the 35th International Conference on Machine Learning)

   The problem of rank aggregation from pairwise and multiway comparisons has a wide range of implications, ranging from recommendation systems to sports rankings to social choice. Some of the most popular algorithms for this problem come from the class of spectral ranking algorithms; these include the rank centrality (RC) algorithm for pairwise comparisons, which returns consistent estimates under the Bradley-Terry-Luce (BTL) model for pairwise comparisons (Negahban et al., 2017), and its generalization, the Luce spectral ranking (LSR) algorithm, which returns consistent estimates under the more general multinomial logit (MNL) model for multiway comparisons (Maystre & Grossglauser, 2015). In this paper, we design a provably faster spectral ranking algorithm, which we call accelerated spectral ranking (ASR), that is also consistent under the MNL/BTL models. Our accelerated algorithm is achieved by designing a random walk that has a faster mixing time than the random walks associated with previous algorithms. In addition to a faster algorithm, our results yield improved sample complexity bounds for recovery of the MNL/BTL parameters: to the best of our knowledge, we give the first general sample complexity bounds for recovering the parameters of the MNL model from multiway comparisons under any (connected) comparison graph (and improve significantly over previous bounds for the BTL model for pairwise comparisons). We also give a message-passing interpretation of our algorithm, which suggests a decentralized distributed implementation. Our experiments on several real-world and synthetic datasets confirm that our new ASR algorithm is indeed orders of magnitude faster than existing algorithms. 

   more » « less
2. Accelerated Spectral Ranking

   Agarwal, Arpit; Patil, Prathamesh; Agarwal, Shivani (July 2018, Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research)

   The problem of rank aggregation from pairwise and multiway comparisons has a wide range of implications, ranging from recommendation systems to sports rankings to social choice. Some of the most popular algorithms for this problem come from the class of spectral ranking algorithms; these include the rank centrality (RC) algorithm for pairwise comparisons, which returns consistent estimates under the Bradley-Terry-Luce (BTL) model for pairwise comparisons (Negahban et al., 2017), and its generalization, the Luce spectral ranking (LSR) algorithm, which returns consistent estimates under the more general multinomial logit (MNL) model for multiway comparisons (Maystre & Grossglauser, 2015). In this paper, we design a provably faster spectral ranking algorithm, which we call accelerated spectral ranking (ASR), that is also consistent under the MNL/BTL models. Our accelerated algorithm is achieved by designing a random walk that has a faster mixing time than the random walks associated with previous algorithms. In addition to a faster algorithm, our results yield improved sample complexity bounds for recovery of the MNL/BTL parameters: to the best of our knowledge, we give the first general sample complexity bounds for recovering the parameters of the MNL model from multiway comparisons under any (connected) comparison graph (and improve significantly over previous bounds for the BTL model for pairwise comparisons). We also give a message-passing interpretation of our algorithm, which suggests a decentralized distributed implementation. Our experiments on several real-world and synthetic datasets confirm that our new ASR algorithm is indeed orders of magnitude faster than existing algorithms. 

   more » « less
3. Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization

   Wei, Jingrong; Chen, Long (January 2025, International Conference on Learning Representations (ICLR))

   The heavy-ball momentum method accelerates gradient descent with a momentum term but lacks accelerated convergence for general smooth strongly convex problems. This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, the first variant with provable global and accelerated convergence for such problems. AOR-HB closes a long-standing theoretical gap, extends to composite convex optimization and min-max problems, and achieves optimal complexity bounds. It offers three key advantages: (1) broad generalization ability, (2) potential to reshape acceleration techniques, and (3) conceptual clarity and elegance compared to existing methods. 

   more » « less
4. Machine learning accelerated photodynamics simulations

   https://doi.org/10.1063/5.0159247  

   Li, Jingbai; Lopez, Steven A (September 2023, Chemical Physics Reviews)

   Machine learning (ML) continues to revolutionize computational chemistry for accelerating predictions and simulations by training on experimental or accurate but expensive quantum mechanical (QM) calculations. Photodynamics simulations require hundreds of trajectories coupled with multiconfigurational QM calculations of excited-state potential energies surfaces that contribute to the prohibitive computational cost at long timescales and complex organic molecules. ML accelerates photodynamics simulations by combining nonadiabatic photodynamics simulations with an ML model trained with high-fidelity QM calculations of energies, forces, and non-adiabatic couplings. This approach has provided time-dependent molecular structural information for understanding photochemical reaction mechanisms of organic reactions in vacuum and complex environments (i.e., explicit solvation). This review focuses on the fundamentals of QM calculations and ML techniques. We, then, discuss the strategies to balance adequate training data and the computational cost of generating these training data. Finally, we demonstrate the power of applying these ML-photodynamics simulations to understand the origin of reactivities and selectivities of organic photochemical reactions, such as cis–trans isomerization, [2 + 2]-cycloaddition, 4π-electrostatic ring-closing, and hydrogen roaming mechanism. 

   more » « less
5. Xenic: SmartNIC-Accelerated Distributed Transactions

   https://doi.org/10.1145/3477132.3483555  

   Schuh, Henry N.; Liang, Weihao; Liu, Ming; Nelson, Jacob; Krishnamurthy, Arvind (October 2021, The ACM SIGOPS 28th Symposium on Operating Systems Principles)