Efficient Algorithms for Global Inference in Internet Marketplaces

• URL: http://arxiv.org/abs/2103.05277v2
• Date: Wed, 10 Mar 2021 16:48:54 GMT
• Title: Efficient Algorithms for Global Inference in Internet Marketplaces
• Authors: Rohan Ramanath, Sathiya Keerthi, Yao Pan, Konstantin Salomatin, Kinjal Basu
• Abstract summary: Matching demand to supply in internet marketplaces is a global inference problem. Until recently, solving such problems on web-scale data with an LP formulation was intractable. Recent work developed a dual decomposition-based approach to solve such problems when the polytope constraints are simple. In this work, we motivate the need to go beyond these simple polytopes and show real-world internet marketplaces that require more complex structured polytope constraints.
• Score: 6.2122699483618
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matching demand to supply in internet marketplaces (e-commerce, ride-sharing, food delivery, professional services, advertising) is a global inference problem that can be formulated as a Linear Program (LP) with (millions of) coupling constraints and (up to a billion) non-coupling polytope constraints. Until recently, solving such problems on web-scale data with an LP formulation was intractable. Recent work (Basu et al., 2020) developed a dual decomposition-based approach to solve such problems when the polytope constraints are simple. In this work, we motivate the need to go beyond these simple polytopes and show real-world internet marketplaces that require more complex structured polytope constraints. We expand on the recent literature with novel algorithms that are more broadly applicable to global inference problems. We derive an efficient incremental algorithm using a theoretical insight on the nature of solutions on the polytopes to project onto any arbitrary polytope, that shows massive improvements in performance. Using better optimization routines along with an adaptive algorithm to control the smoothness of the objective, improves the speed of the solution even further. We showcase the efficacy of our approach via experimental results on web-scale marketplace data.

Related papers

• Efficient Imitation Learning with Conservative World Models [54.52140201148341]
  We tackle the problem of policy learning from expert demonstrations without a reward function. We re-frame imitation learning as a fine-tuning problem, rather than a pure reinforcement learning one.
  arXiv  Detail & Related papers  (2024-05-21T20:53:18Z)
• An Improved Artificial Fish Swarm Algorithm for Solving the Problem of Investigation Path Planning [8.725702964289479]
  We propose a chaotic artificial fish swarm algorithm based on multiple population differential evolution (DE-CAFSA) We incorporate adaptive field of view and step size adjustments, replace random behavior with the 2-opt operation, and introduce chaos theory and sub-optimal solutions. Experimental results demonstrate that DE-CAFSA outperforms other algorithms on various public datasets of different sizes.
  arXiv  Detail & Related papers  (2023-10-20T09:35:51Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  We consider the problem of network parameter cancellation optimization for networks. We show that deploying an algorithm in the real world for exploration and learning can be achieved with the data without exploring.
  arXiv  Detail & Related papers  (2023-10-12T18:36:36Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  We address the solution of the popular Wordle puzzle, using new reinforcement learning methods. For the Wordle puzzle, they yield on-line solution strategies that are very close to optimal at relatively modest computational cost.
  arXiv  Detail & Related papers  (2022-11-15T03:46:41Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Computation Resource Allocation Solution in Recommender Systems [19.456109814747048]
  We propose a computation resource allocation solution (CRAS) that maximizes the business goal with limited computation resources and response time. The effectiveness of our method is verified by extensive experiments based on the real dataset from Taobao.com.
  arXiv  Detail & Related papers  (2021-03-03T08:41:43Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  Some problems have many objectives which lead to a large number of non-dominated solutions. This paper presents a new algorithm that has been designed to obtain the most significant solutions. This new algorithm has been applied to the real world application in Unmanned Air Vehicle (UAV) Mission Planning Problem.
  arXiv  Detail & Related papers  (2020-02-20T17:07:08Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.