publications

preprints

1. PoLoRA: A Preconditioned Orthogonalized LoRA Optimizer

   Nikhil Ghosh, Tetiana Parshakova, and Robert M. Gower

   arXiv preprint, 2026

   Abs arXiv Bib Blog Code

   Low-rank adaptation (LoRA) makes finetuning large language models cheaper by adding to each weight matrix a trainable low-rank update parameterized as the product of two matrices. These matrices are usually trained with Adam, which treats them as a single flat vector of parameters and ignores both the matrix and product structure of LoRA. Applying a matrix-aware optimizer such as Muon to each factor does not consistently improve over Adam, and neither do the product-aware Muon variants proposed in concurrent works. To realize consistent gains, we introduce PoLoRA, a Preconditioned Orthogonalized LoRA optimizer built from three ingredients: a product-aware spectral update direction, curvature preconditioning derived from controlling the per-sample loss change, and a magnitude rule that controls the sizes of both the factor and merged updates. We evaluate PoLoRA on instruction-tuning datasets for code and math across models from 1B to 8B parameters, and find that it reaches the final held-out loss achieved by tuned Adam in 1.2-1.7 times fewer steps, while adding at most 3% per-step overhead. Compared to Adam, PoLoRA is also less sensitive to the learning rate, and its optimal learning rate is stable across ranks.

   @article{ghosh2026polora,
     title = {PoLoRA: A Preconditioned Orthogonalized LoRA Optimizer},
     author = {Ghosh, Nikhil and Parshakova, Tetiana and Gower, Robert M.},
     journal = {arXiv preprint},
     preprint = {true},
     year = {2026},
   }

2. There Will Be a Scientific Theory of Deep Learning

   Jamie Simon, Daniel Kunin, Alexander Atanasov, Enric Boix-Adserà, Blake Bordelon, Jeremy Cohen, Nikhil Ghosh, Florentin Guth, Arthur Jacot, Mason Kamb, Dhruva Karkada, Eric J. Michaud, Berkan Ottlik, and Joseph Turnbull

   arXiv preprint, 2026

   Abs arXiv Bib HTML

   In this paper, we make the case that a scientific theory of deep learning is emerging. By this we mean a theory which characterizes important properties and statistics of the training process, hidden representations, final weights, and performance of neural networks. We pull together major strands of ongoing research in deep learning theory and identify five growing bodies of work that point toward such a theory: (a) solvable idealized settings that provide intuition for learning dynamics in realistic systems; (b) tractable limits that reveal insights into fundamental learning phenomena; (c) simple mathematical laws that capture important macroscopic observables; (d) theories of hyperparameters that disentangle them from the rest of the training process, leaving simpler systems behind; and (e) universal behaviors shared across systems and settings which clarify which phenomena call for explanation. Taken together, these bodies of work share certain broad traits: they are concerned with the dynamics of the training process; they primarily seek to describe coarse aggregate statistics; and they emphasize falsifiable quantitative predictions. We argue that the emerging theory is best thought of as a mechanics of the learning process, and suggest the name learning mechanics. We discuss the relationship between this mechanics perspective and other approaches for building a theory of deep learning, including the statistical and information-theoretic perspectives. In particular, we anticipate a symbiotic relationship between learning mechanics and mechanistic interpretability. We also review and address common arguments that fundamental theory will not be possible or is not important. We conclude with a portrait of important open directions in learning mechanics and advice for beginners.

   @article{simon2026theory,
     title = {There Will Be a Scientific Theory of Deep Learning},
     author = {Simon, Jamie and Kunin, Daniel and Atanasov, Alexander and Boix-Adser{\`a}, Enric and Bordelon, Blake and Cohen, Jeremy and Ghosh, Nikhil and Guth, Florentin and Jacot, Arthur and Kamb, Mason and Karkada, Dhruva and Michaud, Eric J. and Ottlik, Berkan and Turnbull, Joseph},
     journal = {arXiv preprint},
     preprint = {true},
     year = {2026},
   }

3. Does a Global Perspective Help Prune Sparse MoEs Elegantly?

   Zeliang Zhang, Nikhil Ghosh, Jiani Liu, Bin Yu, and Xiaodong Liu

   arXiv preprint, 2026

   Abs arXiv Bib

   Empirical scaling laws for language models have encouraged the development of ever-larger LLMs, despite their growing computational and memory costs. Sparse Mixture-of-Experts (MoEs) offer a promising alternative by activating only a subset of experts per forward pass, improving efficiency without sacrificing performance. However, the large number of expert parameters still leads to substantial memory consumption. Existing pruning methods typically allocate budgets uniformly across layers, overlooking the heterogeneous redundancy that arises in sparse MoEs. We propose GRAPE (Global Redundancy-Aware Pruning of Experts), a global pruning strategy that dynamically allocates pruning budgets based on cross-layer redundancy. Experiments on Mixtral-8x7B, Mixtral-8x22B, DeepSeek-MoE, Qwen-MoE, and GPT-OSS show that, under the same pruning budget, GRAPE consistently achieves the best average performance. On the three main models reported in the paper, it improves average accuracy over the strongest local baseline by 1.40% on average across pruning settings, with gains of up to 2.45%.

   @article{zhang2026grape,
     title = {Does a Global Perspective Help Prune Sparse MoEs Elegantly?},
     author = {Zhang, Zeliang and Ghosh, Nikhil and Liu, Jiani and Yu, Bin and Liu, Xiaodong},
     journal = {arXiv preprint},
     preprint = {true},
     year = {2026},
   }

4. GSM-Agent: Understanding Agentic Reasoning Using Controllable Environments

   Hanlin Zhu, Tianyu Guo, Song Mei, Stuart Russell, Nikhil Ghosh, Alberto Bietti, and Jiantao Jiao

   arXiv preprint, 2025

   Abs arXiv Bib

   As LLMs are increasingly deployed as agents, agentic reasoning - the ability to combine tool use, especially search, and reasoning - becomes a critical skill. However, it is hard to disentangle agentic reasoning when evaluated in complex environments and tasks. Current agent benchmarks often mix agentic reasoning with challenging math reasoning, expert-level knowledge, and other advanced capabilities. To fill this gap, we build a novel benchmark, GSM-Agent, where an LLM agent is required to solve grade-school-level reasoning problems, but is only presented with the question in the prompt without the premises that contain the necessary information to solve the task, and needs to proactively collect that information using tools. Although the original tasks are grade-school math problems, we observe that even frontier models like GPT-5 only achieve 67% accuracy. To understand and analyze the agentic reasoning patterns, we propose the concept of agentic reasoning graph: cluster the environment’s document embeddings into nodes, and map each tool call to its nearest node to build a reasoning path. Surprisingly, we identify that the ability to revisit a previously visited node, widely taken as a crucial pattern in static reasoning, is often missing for agentic reasoning for many models. Based on the insight, we propose a tool-augmented test-time scaling method to improve LLM’s agentic reasoning performance by adding tools to encourage models to revisit. We expect our benchmark and the agentic reasoning framework to aid future studies of understanding and pushing the boundaries of agentic reasoning.

   @article{zhu2025gsmagent,
     title = {GSM-Agent: Understanding Agentic Reasoning Using Controllable Environments},
     author = {Zhu, Hanlin and Guo, Tianyu and Mei, Song and Russell, Stuart and Ghosh, Nikhil and Bietti, Alberto and Jiao, Jiantao},
     journal = {arXiv preprint},
     preprint = {true},
     year = {2025},
   }

conference & journal articles

2026

1. ICLR

   Understanding the Mechanisms of Fast Hyperparameter Transfer

   Nikhil Ghosh, Denny Wu, and Alberto Bietti

   In International Conference on Learning Representations (ICLR), 2026

   Abs arXiv Bib

   The growing scale of deep learning models has rendered standard hyperparameter (HP) optimization prohibitively expensive. A promising solution is the use of scale-aware hyperparameters, which can enable direct transfer of optimal HPs from small-scale grid searches to large models with minimal performance loss. To understand the principles governing such transfer strategy, we develop a general conceptual framework for reasoning about HP transfer across scale, characterizing transfer as fast when the suboptimality it induces vanishes asymptotically faster than the finite-scale performance gap. We show formally that fast transfer is equivalent to useful transfer for compute-optimal grid search, meaning that transfer is asymptotically more compute-efficient than direct tuning. While empirical work has found that the Maximal Update Parameterization (μP) exhibits fast transfer when scaling model width, the mechanisms remain poorly understood. We show that this property depends critically on problem structure by presenting synthetic settings where transfer either offers provable computational advantage or fails to outperform direct tuning even under μP. To explain the fast transfer observed in practice, we conjecture that decomposing the optimization trajectory reveals two contributions to loss reduction: (1) a width-stable component that determines the optimal HPs, and (2) a width-sensitive component that improves with width but weakly perturbs the HP optimum. We present empirical evidence for this hypothesis across various settings, including large language model pretraining.

   @inproceedings{ghosh2026understanding,
     title = {Understanding the Mechanisms of Fast Hyperparameter Transfer},
     author = {Ghosh, Nikhil and Wu, Denny and Bietti, Alberto},
     booktitle = {International Conference on Learning Representations (ICLR)},
     preprint = {false},
     year = {2026},
   }

2. ICLR

   PLoP: Precise LoRA Placement for Efficient Finetuning of Large Models

   Soufiane Hayou, Nikhil Ghosh, and Bin Yu

   In International Conference on Learning Representations (ICLR), 2026

   Abs arXiv Bib

   Low-Rank Adaptation (LoRA) is a widely used finetuning method for large models. Its small memory footprint allows practitioners to adapt large models to specific tasks at a fraction of the cost of full finetuning. Different modifications have been proposed to enhance its efficiency by, for example, setting the learning rate, the rank, and the initialization. Another improvement axis is adapter placement strategy: when using LoRA, practitioners usually pick module types to adapt with LoRA, such as Query and Key modules. Few works have studied the problem of adapter placement, with nonconclusive results: original LoRA paper suggested placing adapters in attention modules, while other works suggested placing them in the MLP modules. Through an intuitive theoretical analysis, we introduce PLoP (Precise LoRA Placement), a lightweight method that allows automatic identification of module types where LoRA adapters should be placed, given a pretrained model and a finetuning task. We demonstrate that PLoP consistently outperforms, and in the worst case competes, with commonly used placement strategies through comprehensive experiments on supervised finetuning and reinforcement learning for reasoning.

   @inproceedings{hayou2026plop,
     title = {PLoP: Precise LoRA Placement for Efficient Finetuning of Large Models},
     author = {Hayou, Soufiane and Ghosh, Nikhil and Yu, Bin},
     booktitle = {International Conference on Learning Representations (ICLR)},
     preprint = {false},
     year = {2026},
   }

2025

1. JMLR

   The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning

   Nikhil Ghosh, Spencer Frei, Wooseok Ha, and Bin Yu

   Journal of Machine Learning Research, 2025

   Abs arXiv Bib

   In this work, we investigate the dynamics of stochastic gradient descent (SGD) when training a single-neuron autoencoder with linear or ReLU activation on orthogonal data. We show that for this non-convex problem, randomly initialized SGD with a constant step size successfully finds a global minimum for any batch size choice. However, the particular global minimum found depends upon the batch size. In the full-batch setting, we show that the solution is dense (i.e., not sparse) and is highly aligned with its initialized direction, showing that relatively little feature learning occurs. On the other hand, for any batch size strictly smaller than the number of samples, SGD finds a global minimum which is sparse and nearly orthogonal to its initialization, showing that the randomness of stochastic gradients induces a qualitatively different type of "feature selection" in this setting. Moreover, if we measure the sharpness of the minimum by the trace of the Hessian, the minima found with full batch gradient descent are flatter than those found with strictly smaller batch sizes, in contrast to previous works which suggest that large batches lead to sharper minima. To prove convergence of SGD with a constant step size, we introduce a powerful tool from the theory of non-homogeneous random walks which may be of independent interest.

   @article{ghosh2025effect,
     title = {The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning},
     author = {Ghosh, Nikhil and Frei, Spencer and Ha, Wooseok and Yu, Bin},
     year = {2025},
     preprint = {false},
     volume = {26},
     number = {49},
     pages = {1--61},
     journal = {Journal of Machine Learning Research}
   }

2024

1. ICML

   LoRA+: Efficient Low Rank Adaptation of Large Models

   Soufiane Hayou, Nikhil Ghosh, and Bin Yu

   In International Conference on Machine Learning (ICML), 2024

   Abs arXiv Bib HTML Code

   In this paper, we show that Low Rank Adaptation (LoRA) as originally introduced in Hu et al. (2021) leads to suboptimal finetuning of models with large width (embedding dimension). This is due to the fact that adapter matrices A and B in LoRA are updated with the same learning rate. Using scaling arguments for large width networks, we demonstrate that using the same learning rate for A and B does not allow efficient feature learning. We then show that this suboptimality of LoRA can be corrected simply by setting different learning rates for the LoRA adapter matrices A and B with a well-chosen ratio. We call this proposed algorithm LoRA+. In our extensive experiments, LoRA+ improves performance (1-2 % improvements) and finetuning speed (up to   2X SpeedUp), at the same computational cost as LoRA.

   @inproceedings{hayou2024loraplus,
     title = {LoRA+: Efficient Low Rank Adaptation of Large Models},
     author = {Hayou, Soufiane and Ghosh, Nikhil and Yu, Bin},
     booktitle = {International Conference on Machine Learning (ICML)},
     preprint = {false},
     year = {2024},
   }

2. NeurIPS

   The Impact of Initialization on LoRA Finetuning Dynamics

   Soufiane Hayou, Nikhil Ghosh, and Bin Yu

   2024

   Abs arXiv Bib

   In this paper, we study the role of initialization in Low Rank Adaptation (LoRA) as originally introduced in Hu et al. (2021). Essentially, to start from the pretrained model as initialization for finetuning, one can either initialize B to zero and A to random (default initialization in PEFT package), or vice-versa. In both cases, the product BA is equal to zero at initialization, which makes finetuning starts from the pretrained model. These two initialization schemes are seemingly similar. They should in-principle yield the same performance and share the same optimal learning rate. We demonstrate that this is an incorrect intuition and that the first scheme (initializing B to zero and A to random) on average yields better performance compared to the other scheme. Our theoretical analysis shows that the reason behind this might be that the first initialization allows the use of larger learning rates (without causing output instability) compared to the second initialization, resulting in more efficient learning of the first scheme. We validate our results with extensive experiments on LLMs.

   @article{hayou2024impact,
     title = {The Impact of Initialization on LoRA Finetuning Dynamics},
     author = {Hayou, Soufiane and Ghosh, Nikhil and Yu, Bin},
     booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
     preprint = {false},
     year = {2024},
   }

3. ICLR

   More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory

   James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin

   In International Conference on Learning Representations (ICLR), 2024

   Abs arXiv Bib

   In our era of enormous neural networks, empirical progress has been driven by the philosophy that more is better. Recent deep learning practice has found repeatedly that larger model size, more data, and more computation (resulting in lower training loss) improves performance. In this paper, we give theoretical backing to these empirical observations by showing that these three properties hold in random feature (RF) regression, a class of models equivalent to shallow networks with only the last layer trained. Concretely, we first show that the test risk of RF regression decreases monotonically with both the number of features and the number of samples, provided the ridge penalty is tuned optimally. In particular, this implies that infinite width RF architectures are preferable to those of any finite width. We then proceed to demonstrate that, for a large class of tasks characterized by powerlaw eigenstructure, training to near-zero training loss is obligatory: near-optimal performance can only be achieved when the training error is much smaller than the test error. Grounding our theory in real-world data, we find empirically that standard computer vision tasks with convolutional neural tangent kernels clearly fall into this class. Taken together, our results tell a simple, testable story of the benefits of overparameterization, overfitting, and more data in random feature models.

   @inproceedings{simon2023better,
     title = {More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory},
     author = {Simon, James B. and Karkada, Dhruva and Ghosh, Nikhil and Belkin, Mikhail},
     booktitle = {International Conference on Learning Representations (ICLR)},
     year = {2024},
     preprint = {false},
   }

2023

1. NeurIPS

   Alternating Updates for Efficient Transformers

   Cenk Baykal, Dylan Cutler, Nishanth Dikkala, Nikhil Ghosh, Rina Panigrahy, and Xin Wang

   In Advances in Neural Information Processing Systems (NeurIPS), 2023

   Awarded Abs arXiv Bib Blog

   spotlight

   It has been well established that increasing scale in deep transformer networks leads to improved quality and performance. However, this increase in scale often comes with prohibitive increases in compute cost and inference latency. We introduce Alternating Updates (AltUp), a simple-to-implement method to increase a model’s capacity without the computational burden. AltUp enables the widening of the learned representation, i.e., the token embedding, while only incurring a negligible increase in latency. AltUp achieves this by working on a subblock of the widened representation at each layer and using a predict-and-correct mechanism to update the inactivated blocks. We present extensions of AltUp, such as its applicability to the sequence dimension, and demonstrate how AltUp can be synergistically combined with existing approaches, such as Sparse Mixture-of-Experts models, to obtain efficient models with even higher capacity. Our experiments on benchmark transformer models and language tasks demonstrate the consistent effectiveness of AltUp on a diverse set of scenarios. Notably, on SuperGLUE and SQuAD benchmarks, AltUp enables up to 87% speedup relative to the dense baselines at the same accuracy.

   @inproceedings{baykal2023alternating,
     title = {Alternating Updates for Efficient Transformers},
     author = {Baykal, Cenk and Cutler, Dylan and Dikkala, Nishanth and Ghosh, Nikhil and Panigrahy, Rina and Wang, Xin},
     booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
     preprint = {false},
     year = {2023},
   }

2. EMNLP

   On the Benefits of Learning to Route in Mixture-of-Experts Models

   Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigrahy, Nikhil Vyas, and Xin Wang

   In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2023

   Abs Bib HTML

   Mixture-of-Expert (MoE) Transformer models, such as the Switch Transformer, allow us to successfully scale up model sizes while keeping the amount of compute time fixed. Prior work has established the computational efficiency benefits of using these models. A core component of these models is a router that routes input tokens to different experts in a layer. We show theoretical and empirical evidence that the router’s ability to route tokens intelligently confers a significant advantage to MoE models. We study synthetic settings where the input data is distributed in clusters and show theoretically and empirically that the router learns to route the inputs according to these clusters. Then we perform experiments on real data using the T5X library, where we observe that a trainable router confers a non-trivial benefit instead of a non-trainable router.

   @inproceedings{dikkala2023routing,
     title = {On the Benefits of Learning to Route in Mixture-of-Experts Models},
     author = {Dikkala, Nishanth and Ghosh, Nikhil and Meka, Raghu and Panigrahy, Rina and Vyas, Nikhil and Wang, Xin},
     booktitle = {Conference on Empirical Methods in Natural Language Processing (EMNLP)},
     pages = {9376--9396},
     preprint = {false},
     year = {2023},
   }

3. SIMODS

   A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors

   Nikhil Ghosh and Mikhail Belkin

   SIAM Journal on Mathematics of Data Science (SIMODS), 2023

   Abs arXiv Bib

   In this work we establish an algorithm and distribution independent non-asymptotic trade-off between the model size, excess test loss, and training loss of linear predictors. Specifically, we show that models that perform well on the test data (have low excess loss) are either "classical" – have training loss close to the noise level, or are "modern" – have a much larger number of parameters compared to the minimum needed to fit the training data exactly. We also provide a more precise asymptotic analysis when the limiting spectral distribution of the whitened features is Marchenko-Pastur. Remarkably, while the Marchenko-Pastur analysis is far more precise near the interpolation peak, where the number of parameters is just enough to fit the training data, it coincides exactly with the distribution independent bound as the level of overparametrization increases.

   @article{ghosh2023universal,
     title = {A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors},
     author = {Ghosh, Nikhil and Belkin, Mikhail},
     journal = {SIAM Journal on Mathematics of Data Science (SIMODS)},
     volume = {5},
     number = {4},
     pages = {977--1004},
     year = {2023},
     preprint = {false},
     publisher = {SIAM},
   }

4. ICLR

   Deconstructing Distributions: A Pointwise Framework of Learning

   Gal Kaplun^*, Nikhil Ghosh^*, Saurabh Garg, Boaz Barak, and Preetum Nakkiran

   In International Conference on Learning Representations (ICLR), 2023

   Abs arXiv Bib

   In machine learning, we traditionally evaluate the performance of a single model, averaged over a collection of test inputs. In this work, we propose a new approach: we measure the performance of a collection of models when evaluated on a single input point. Specifically, we study a point’s profile: the relationship between models’ average performance on the test distribution and their pointwise performance on this individual point. We find that profiles can yield new insights into the structure of both models and data – in and out-of-distribution. For example, we empirically show that real data distributions consist of points with qualitatively different profiles. On one hand, there are "compatible" points with strong correlation between the pointwise and average performance. On the other hand, there are points with weak and even negative correlation: cases where improving overall model accuracy actually hurts performance on these inputs. We prove that these experimental observations are inconsistent with the predictions of several simplified models of learning proposed in prior work. As an application, we use profiles to construct a dataset we call CIFAR-10-NEG: a subset of CINIC-10 such that for standard models, accuracy on CIFAR-10-NEG is negatively correlated with accuracy on CIFAR-10 test. This illustrates, for the first time, an OOD dataset that completely inverts "accuracy-on-the-line" (Miller, Taori, Raghunathan, Sagawa, Koh, Shankar, Liang, Carmon, and Schmidt 2021)

   @inproceedings{kaplun2023deconstructing,
     title = {Deconstructing Distributions: A Pointwise Framework of Learning},
     author = {Kaplun, Gal and Ghosh, Nikhil and Garg, Saurabh and Barak, Boaz and Nakkiran, Preetum},
     booktitle = {International Conference on Learning Representations (ICLR)},
     year = {2023},
     preprint = {false},
   }

2022

1. ICLR

   The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods

   Nikhil Ghosh, Song Mei, and Bin Yu

   In International Conference on Learning Representations (ICLR), 2022

   Abs arXiv Bib

   To understand how deep learning works, it is crucial to understand the training dynamics of neural networks. Several interesting hypotheses about these dynamics have been made based on empirically observed phenomena, but there exists a limited theoretical understanding of when and why such phenomena occur. In this paper, we consider the training dynamics of gradient flow on kernel least-squares objectives, which is a limiting dynamics of SGD trained neural networks. Using precise high-dimensional asymptotics, we characterize the dynamics of the fitted model in two "worlds": in the Oracle World the model is trained on the population distribution and in the Empirical World the model is trained on a sampled dataset. We show that under mild conditions on the kernel and L2 target regression function the training dynamics undergo three stages characterized by the behaviors of the models in the two worlds. Our theoretical results also mathematically formalize some interesting deep learning phenomena. Specifically, in our setting we show that SGD progressively learns more complex functions and that there is a "deep bootstrap" phenomenon: during the second stage, the test error of both worlds remain close despite the empirical training error being much smaller. Finally, we give a concrete example comparing the dynamics of two different kernels which shows that faster training is not necessary for better generalization.

   @inproceedings{ghosh2022stages,
     title = {The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods},
     author = {Ghosh, Nikhil and Mei, Song and Yu, Bin},
     booktitle = {International Conference on Learning Representations (ICLR)},
     year = {2022},
     preprint = {false},
   }

2019

1. NeurIPS

   Landmark Ordinal Embedding

   Nikhil Ghosh, Yuxin Chen, and Yisong Yue

   In Advances in Neural Information Processing Systems (NeurIPS), 2019

   Abs arXiv Bib

   In this paper, we aim to learn a low-dimensional Euclidean representation from a set of constraints of the form "item j is closer to item i than item k". Existing approaches for this "ordinal embedding" problem require expensive optimization procedures, which cannot scale to handle increasingly larger datasets. To address this issue, we propose a landmark-based strategy, which we call Landmark Ordinal Embedding (LOE). Our approach trades off statistical efficiency for computational efficiency by exploiting the low-dimensionality of the latent embedding. We derive bounds establishing the statistical consistency of LOE under the popular Bradley-Terry-Luce noise model. Through a rigorous analysis of the computational complexity, we show that LOE is significantly more efficient than conventional ordinal embedding approaches as the number of items grows. We validate these characterizations empirically on both synthetic and real datasets. We also present a practical approach that achieves the "best of both worlds", by using LOE to warm-start existing methods that are more statistically efficient but computationally expensive.

   @inproceedings{ghosh2019landmark,
     title = {Landmark Ordinal Embedding},
     author = {Ghosh, Nikhil and Chen, Yuxin and Yue, Yisong},
     booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
     year = {2019},
     preprint = {false},
   }