Timezone: »
Poster
Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences
Kinjal Basu · Ankan Saha · Shaunak Chatterjee
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by a sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability in practice.
Author Information
Kinjal Basu (LinkedIn)
Ankan Saha (Linkedin Corporation)
Shaunak Chatterjee (LinkedIn)
More from the Same Authors
-
2022 : A Light-speed Linear Program Solver for Personalized Recommendation with Diversity Constraints »
Miao Cheng · Haoyue Wang · Aman Gupta · Rahul Mazumder · Sathiya Selvaraj · Kinjal Basu -
2022 Poster: Pushing the limits of fairness impossibility: Who's the fairest of them all? »
Brian Hsu · Rahul Mazumder · Preetam Nandy · Kinjal Basu -
2021 Poster: A/B Testing for Recommender Systems in a Two-sided Marketplace »
Preetam Nandy · Divya Venugopalan · Chun Lo · Shaunak Chatterjee -
2020 Poster: A/B Testing in Dense Large-Scale Networks: Design and Inference »
Preetam Nandy · Kinjal Basu · Shaunak Chatterjee · Ye Tu -
2020 Spotlight: A/B Testing in Dense Large-Scale Networks: Design and Inference »
Preetam Nandy · Kinjal Basu · Shaunak Chatterjee · Ye Tu -
2010 Poster: Lower Bounds on Rate of Convergence of Cutting Plane Methods »
Xinhua Zhang · Ankan Saha · S.V.N. Vishwanathan