Efficient Vertex-Oriented Polytopic Projection for Web-Scale Applications
Authors: Rohan Ramanath, S. Sathiya Keerthi, Yao Pan, Konstantin Salomatin, Kinjal Basu3821-3829
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We develop an intuition guided by theoretical and empirical analysis to show that when these instances follow certain structures, a large majority of the projections lie on vertices of the polytopes. To do these projections efficiently we derive a vertex-oriented incremental algorithm to project a point onto any arbitrary polytope, as well as give specific algorithms to cater to simplex projection and polytopes where the unit box is cut by planes. To show the efficacy of these special purpose projection algorithms, we switch out the projection step of Ecl , and run an ablation study over various internet marketplace problems. We call this new solver Dua Lip, a Dual decomposition-based Linear Programming framework which shows drastic speedups over the existing state-of-the-art. We demonstrate the value of the above algorithms empirically using dataset D. |
| Researcher Affiliation | Industry | Rohan Ramanath, S. Sathiya Keerthi, Yao Pan, Konstantin Salomatin, Kinjal Basu Linked In Corportation Mountain View, CA, USA rohan@ramanath.me, {keselvaraj, yopan, ksalomatin, kbasu}@linkedin.com |
| Pseudocode | Yes | Algorithm 1: Dua Lip vertex-first projection and Algorithm 2: Modified Duchi et al. algorithm for Simplex-Eq |
| Open Source Code | Yes | To promote reproducible research we open source (with Free BSD License)1 the solver with all the efficient projection operators discussed in the paper.1https://github.com/linkedin/Dua Lip |
| Open Datasets | Yes | To promote reproducible research we open source (with Free BSD License)1 the solver with all the efficient projection operators discussed in the paper. There, we report the solver s performance on the open-source movie-lens dataset (Harper and Konstan 2015), which contains user rating of movies to formulate an optimization problem (taking a similar approach to (Manshadi et al. 2013)). |
| Dataset Splits | No | The paper does not explicitly provide specific dataset split information (percentages, sample counts, or detailed methodology) for training, validation, or testing. |
| Hardware Specification | No | The paper mentions 'all runs are on Spark 2.3 clusters with up to 800 processors.' This provides some details about the computing environment, but lacks specific hardware models like CPU or GPU types, or memory specifications. |
| Software Dependencies | No | The paper mentions 'Spark 2.3 clusters' but does not list other software dependencies with specific version numbers (e.g., Python, PyTorch, TensorFlow, specific libraries). |
| Experiment Setup | No | The paper does not contain specific experimental setup details such as concrete hyperparameter values, training configurations, or system-level settings in the main text. It focuses more on the algorithmic details and overall performance. |