UDuo: Universal Dual Optimization Framework for Online Matching

• URL: http://arxiv.org/abs/2505.22243v1
• Date: Wed, 28 May 2025 11:25:50 GMT
• Title: UDuo: Universal Dual Optimization Framework for Online Matching
• Authors: Bin Li, Diwei Liu, Zehong Hu, Jia Jia,
• Abstract summary: We propose a novel paradigm that fundamentally rethinks online allocation through three key innovations.<n> temporal user arrival representation vector, resource pacing learner, and online time-series forecasting approach.<n> Experimental results show that UDuo achieves higher efficiency and faster convergence than the traditional arrival model in real-world pricing.
• Score: 9.092568268958425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online resource allocation under budget constraints critically depends on proper modeling of user arrival dynamics. Classical approaches employ stochastic user arrival models to derive near-optimal solutions through fractional matching formulations of exposed users for downstream allocation tasks. However, this is no longer a reasonable assumption when the environment changes dynamically. In this work, We propose the Universal Dual optimization framework UDuo, a novel paradigm that fundamentally rethinks online allocation through three key innovations: (i) a temporal user arrival representation vector that explicitly captures distribution shifts in user arrival patterns and resource consumption dynamics, (ii) a resource pacing learner with adaptive allocation policies that generalize to heterogeneous constraint scenarios, and (iii) an online time-series forecasting approach for future user arrival distributions that achieves asymptotically optimal solutions with constraint feasibility guarantees in dynamic environments. Experimental results show that UDuo achieves higher efficiency and faster convergence than the traditional stochastic arrival model in real-world pricing while maintaining rigorous theoretical validity for general online allocation problems.

Related papers

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• RCCDA: Adaptive Model Updates in the Presence of Concept Drift under a Constrained Resource Budget [19.391900930310253]
  Real-time machine learning algorithms are often faced with the challenge of adapting models to concept drift.<n>Existing solutions often depend on drift-detection methods that produce high computational overhead for resource-constrained environments.<n>We propose RCCDA: a dynamic model update policy that optimize ML training dynamics while ensuring strict compliance to predefined resource constraints.
  arXiv  Detail & Related papers  (2025-05-30T02:49:42Z)
• Large Language Model Empowered Recommendation Meets All-domain Continual Pre-Training [60.38082979765664]
  CPRec is an All-domain Continual Pre-Training framework for Recommendation.<n>It holistically align LLMs with universal user behaviors through the continual pre-training paradigm.<n>We conduct experiments on five real-world datasets from two distinct platforms.
  arXiv  Detail & Related papers  (2025-04-11T20:01:25Z)
• Global-Decision-Focused Neural ODEs for Proactive Grid Resilience Management [50.34345101758248]
  We propose predict-all-then-optimize-globally (PATOG), a framework that integrates outage prediction with globally optimized interventions.<n>Our approach ensures spatially and temporally coherent decision-making, improving both predictive accuracy and operational efficiency.<n>Experiments on synthetic and real-world datasets demonstrate significant improvements in outage prediction consistency and grid resilience.
  arXiv  Detail & Related papers  (2025-02-25T16:15:35Z)
• Exploring the Boundary of Diffusion-based Methods for Solving Constrained Optimization [46.75288477458697]
  We propose a novel diffusion-based framework for Continuous Constrained Optimization problems called DiOpt.<n>DiOpt operates in two distinct phases: an initial warm-start phase, implemented via supervised learning, followed by a bootstrapping phase.<n>It is designed to iteratively refine solutions, thereby improving the objective function while rigorously satisfying problem constraints.
  arXiv  Detail & Related papers  (2025-02-14T17:43:08Z)
• Client-Centric Federated Adaptive Optimization [78.30827455292827]
  Federated Learning (FL) is a distributed learning paradigm where clients collaboratively train a model while keeping their own data private.<n>We propose Federated-Centric Adaptive Optimization, which is a class of novel federated optimization approaches.
  arXiv  Detail & Related papers  (2025-01-17T04:00:50Z)
• DECODE: Domain-aware Continual Domain Expansion for Motion Prediction [10.479509360064219]
  We introduce DECODE, a novel continual learning framework for motion prediction.<n>It balances specialization with generalization, dynamically adjusting to real-time demands.<n>It achieves a notably low forgetting rate of 0.044 and an average minADE of 0.584 m.
  arXiv  Detail & Related papers  (2024-11-26T22:20:22Z)
• Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement [1.9689888982532262]
  Motivated by our collaboration with a major refugee resettlement agency in the U.S., we study a dynamic matching problem where each new arrival (a refugee case) must be matched immediately and irrevocably to one of the static resources (a location with a fixed annual quota) Given the time-consuming nature of service, a server may not be available at a given time, thus we refer to it as a dynamic resource. Upon matching, the case will wait to avail service in a first-come-first-serve manner.
  arXiv  Detail & Related papers  (2024-10-30T13:17:38Z)
• OPUS: Occupancy Prediction Using a Sparse Set [64.60854562502523]
  We present a framework to simultaneously predict occupied locations and classes using a set of learnable queries. OPUS incorporates a suite of non-trivial strategies to enhance model performance. Our lightest model achieves superior RayIoU on the Occ3D-nuScenes dataset at near 2x FPS, while our heaviest model surpasses previous best results by 6.1 RayIoU.
  arXiv  Detail & Related papers  (2024-09-14T07:44:22Z)
• Model-based Causal Bayesian Optimization [74.78486244786083]
  We introduce the first algorithm for Causal Bayesian Optimization with Multiplicative Weights (CBO-MW) We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. Our experiments include a realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system.
  arXiv  Detail & Related papers  (2023-07-31T13:02:36Z)
• Model-Free Learning of Optimal Deterministic Resource Allocations in Wireless Systems via Action-Space Exploration [4.721069729610892]
  We propose a technically grounded and scalable deterministic-dual gradient policy method for efficiently learning optimal parameterized resource allocation policies. Our method not only efficiently exploits gradient availability of popular universal representations such as deep networks, but is also truly model-free, as it relies on consistent zeroth-order gradient approximations of associated random network services constructed via low-dimensional perturbations in action space.
  arXiv  Detail & Related papers  (2021-08-23T18:26:16Z)

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.