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.
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.
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