  This paper introduces a dual-based algorithm framework for solving the
regularized online resource allocation problems, which have potentially
non-concave cumulative rewards, hard resource constraints, and a non-separable
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, e.g., 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.
