Efficient Algorithms for Global Inference in Internet Marketplaces

Sathiya Keerthi Selvaraj, Rohan Ramanath, S. Sathiya Keerthi, Yao Pan, Konstantin Salomatin, Kinjal Basu

Introduction

In modern internet marketplaces, such as LinkedIn or Uber, global inference problems often manifest as massive Linear Programs (LPs) with billions or even trillions of variables. These problems involve matching jobs to members or drivers to riders under complex global constraints. To handle this scale, engineers typically employ dual decomposition methods that break the primary problem into many smaller sub-problems. However, a significant computational hurdle remains: the Euclidean projection step.

The Projection Bottleneck

Each iteration of a dual decomposition solver requires finding the point on a complex geometric shape (a polytope) closest to a target point. In existing state-of-the-art solvers like LinkedIn's ECLIPSE, this projection step is the primary performance killer.

Profiling of computational costs in existing solvers, highlighting that the projection step consumes 74% of total time.

As shown in the profiling data above, the projection operation $\hat{x}_i(\lambda)$ accounts for a staggering 74% of the total computation time. Standard general-purpose algorithms fail to exploit the specific structure of marketplace problems, leading to significant inefficiencies when scaled across distributed clusters. The authors found that while the optimizer's logic was fast, the "inner loop" of projection was the true enemy of performance.

The DuaLip Framework

To address this, the authors introduce DuaLip, a framework utilizing "vertex-oriented" projection algorithms. The core insight is the "corral" intuition: in marketplace LPs, the optimal projection almost always resides on a vertex (a corner) or a very low-dimensional face of the polytope. By adding a small smoothing term ($\gamma$), the probability of landing exactly on a vertex increases to over 99% in practice.

DuaLip employs a "Vertex-First Projection" strategy. Instead of a general search, it first evaluates the nearest vertex. If optimality conditions are met, the algorithm terminates immediately. If not, it incrementally expands the search space by adding vertices—a process that remains highly efficient because the "corral dimension" (the number of vertices needed) is typically very small.

Furthermore, the framework adapts the classic Wolfe’s algorithm for general polytopes, optimizing it specifically for vertex-first initialization to avoid costly coordinate transformations. For more complex constraints common in recommendation engines—such as "Slate" or "Assignment" constraints—the authors developed specialized versions of the algorithm using dynamic programming to maintain efficiency.

Scalability and Results

The researchers evaluated DuaLip against proprietary LinkedIn datasets (featuring up to 100 trillion variables) and public benchmarks like Movie-Lens. The results demonstrate a step-function improvement in both speed and scalability.

Comparison of execution times (in hours) between DuaLip, ECLIPSE (Ecl), and SCS across different problem scales.

Compared to the previous state-of-the-art (ECLIPSE), DuaLip achieved speedups between 6x and 8x. More impressively, it successfully solved problems with 1 trillion variables in approximately 2.6 hours, whereas commercial-grade solvers like SCS failed to complete within 24 hours or could not scale to such dimensions. Empirical tests confirmed that over 96% of projections were resolved at the very first vertex-check step, validating the theoretical intuition behind vertex dominance.

Conclusion

By shifting the focus from general-purpose optimization to vertex-oriented search, DuaLip removes the primary bottleneck in web-scale marketplace inference. While future work remains to bridge theoretical gaps regarding smoothing parameters when $\gamma > 0$, the current framework provides a robust, highly scalable solution for the world's largest optimization challenges, with potential applications extending to natural language processing and semi-supervised learning.

Summary updated

BibTeX
@inproceedings{selvaraj2022efficient,
  author = {Sathiya Keerthi Selvaraj and Rohan Ramanath and S. Sathiya Keerthi and Yao Pan and Konstantin Salomatin and Kinjal Basu},
  title = {{Efficient Algorithms for Global Inference in Internet Marketplaces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20297},
}
Figure