Optimal Regularized Online Allocation by Adaptive Re-Solving

Wanteng Ma (), Ying Cao (), Danny H. K. Tsang () and Dong Xia ()
Additional contact information
Wanteng Ma: Department of Mathematics, The Hong Kong University of Science and Technology, Clearwater Bay, Kowloon, Hong Kong
Ying Cao: Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Clearwater Bay, Kowloon, Hong Kong
Danny H. K. Tsang: Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Clearwater Bay, Kowloon, Hong Kong
Dong Xia: Department of Mathematics, The Hong Kong University of Science and Technology, Clearwater Bay, Kowloon, Hong Kong

Operations Research, 2025, vol. 73, issue 4, 2079-2096

Abstract: This paper introduces a dual-based algorithm framework for solving the regularized online resource allocation problems, which have potentially nonconcave cumulative rewards, hard resource constraints, and a nonseparable regularizer. Under a strategy of adaptively updating the resource constraints, the proposed framework only requests approximate solutions to the empirical dual problems up to a certain accuracy and yet delivers an optimal logarithmic regret under a locally second-order growth condition. Surprisingly, a delicate analysis of the dual objective function enables us to eliminate the notorious log-log factor in regret bound. The flexible framework renders renowned and computationally fast algorithms immediately applicable, for example, dual stochastic gradient descent. Additionally, an infrequent re-solving scheme is proposed, which significantly reduces computational demands without compromising the optimal regret performance. A worst-case square-root regret lower bound is established if the resource constraints are not adaptively updated during dual optimization, which underscores the critical role of adaptive dual variable update. Comprehensive numerical experiments demonstrate the merits of the proposed algorithm framework.

Keywords: Optimization; online allocation problems; regret; re-solving strategy (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0486 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:2079-2096

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().