# Optimal Regularized Online Convex Allocation by Adaptive Re-Solving

Wanteng Ma1, Ying Cao2, Danny H.K. Tsang2, Dong Xia1111Ma and Cao are co-first
authors. Ma’s research was partially supported by Hong Kong PhD Fellowship No.
PF20-46281. Tsang’s research was partially supported by Hong Kong RGC GRF
16211220; Xia’s research was partially supported by Hong Kong RGC Grant GRF
16300121 and 16301622.

1Department of Mathematics, HKUST
2Department of Electronic and Computer Engineering, HKUST

(())

###### Abstract

This paper introduces a dual-based algorithm framework for solving the
regularized online resource allocation problems, which have cumulative convex
rewards, hard resource constraints, and a non-separable regularizer. Under a
strategy of adaptively updating the resource constraints, the proposed
framework only requests an approximate solution to the empirical dual problem
up to a certain accuracy, and yet delivers an optimal logarithmic regret under
a locally strongly convex assumption. Surprisingly, a delicate analysis of
dual objective function enables us to eliminate the notorious loglog factor in
regret bound. The flexible framework renders renowned and computationally fast
algorithms immediately applicable, e.g., dual gradient descent and stochastic
gradient descent. 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 and real data application
demonstrate the merits of proposed algorithm framework.

##  1 Introduction

Online resource allocation seeks to maximize the total rewards in an online
service system that is subject to resource constraints. As an exemplary model
for sequential decision making, online allocation has drawn considerable
attentions in recent decades. Meanwhile, it is strongly connected to other
online problems such as revenue management (Talluri et al.,, 2004), online
linear programming (Agrawal et al.,, 2014) and ads bidding problems (Lee et
al.,, 2013), to name but a few. Online allocation finds applications in
diverse fields, e.g., computer science and operation research. Oftentimes,
online allocation problems feature resource constraints that are either hard
(Mehta et al.,, 2007) or soft (Mahdavi et al.,, 2012), with different
constraint capacities. The goal of a decision maker is to maximize the total
rewards (revenue, utility) function by a real-time decision policy that
enforces each of the resource constraints.

So far, existing literature on online allocation mostly focused on additively
separable objectives, i.e., the objective function only involves the total
rewards that can be simply described as the cumulative rewards by time (e.g.,
Mehta et al., (2007); Devanur and Hayes, (2009); Balseiro and Gur, (2019)).
While a separable objective is favorable for tracking additive total rewards,
it falls short of describing globally non-separable quantities such as total
resource consumption or average actions. For instance, the average action
(Agrawal and Devanur,, 2014) in online advertising measures the amount of
under-delivery of impressions. Unfortunately, non-separable objectives are
considerably under-explored in the literature, and particularly, there is a
paucity of work investigating the impact of non-separable regularization on
separable cumulative reward functions. Here we are interested in regularized
online allocation problems, which add a non-separable regularizer to the
objective function as a penalty for various purposes such as resource-saving,
load balancing, diversity, and fairness (Ghosh et al.,, 2009; Balseiro et
al.,, 2021). Compared with non-regularized online resource allocation that
maximizes an additively separable objective, the non-separable regularization
poses new challenges to algorithm design and regret analysis.

In this paper, we study regularized online allocation problem with a concave
reward function and linear resource constraints under the so-called random
input model (Goel and Mehta,, 2008) where i.i.d. requests arrive sequentially
and follow an unknown distribution. Decisions must be made sequentially, that
is, once a request is received with a known reward function, the decision
maker shall instantly makes a decision based on current request, previous
history and remaining resources. Throughout the paper, we impose hard
constraints on the total resource consumption, which shall never be violated
so that the decision maker must wisely control the resource consumption at any
time. Clearly, the challenges of online allocation problems mainly stem from
the dilemma of fulfilling the current request or reserving the resources for,
possibly more rewardable, future ones. The task for a decision maker is to
design a strategy that maximizes the regularized total rewards subject to
resource constraints. The regularizer is a non-separable function of total
resource consumption. A typical application of the problem under study is
online advertising (Mehta et al.,, 2007; Agrawal et al.,, 2018) where a
publisher needs to assign each impression to some advertiser and maximize the
click-through rate with budget constraints on each advertiser. Oftentimes,
other aspects of resource consumptions, including fairness of advertisers or
load balancing, are put into consideration. Towards that end, a regularizer on
total click-through rates can be added, in which case the objective function
turns out to be the regularized cumulative total click-through rates.

Our main goal is to design computationally efficient algorithms for the
aforementioned regularized online allocation problems, which, simultaneously,
achieve theoretically optimal regrets. In the absence of non-separable
regularizer, it has been well recognized that the lower bound of regret of
online allocation problems grows at a logarithmic rate (Bray,, 2019; Li and
Ye,, 2021). The forgoing works also proposed adaptive policies that achieve
the logarithmic-order regrets up to an additional loglog factor. Moreover,
Arlotto and Gurvich, (2019) shows that adaptive policies are, generally,
necessary to make a low regret possible. In sharp contrast, to our best
knowledge, regrets achieved by prior algorithms (Balseiro et al.,, 2021) on
regularized online allocation problems are of a square-root order. A first
natural question is: can a logarithmic-order regret be achieved in the
existence of a non-separable regularizer? Actually, we seek an even more
ambitious goal: can we achieve a regret of exactly order $O(\log T)$ without
the loglog factor so that the lower bound is sharply met? The next question is
more crucial: is there any computationally efficient algorithm that attains
the desired regret? Surprisingly, we give affirmative answers to both
questions by designing an adaptive algorithm framework that is flexible,
computationally fast, and theoretically guaranteed to achieve the sharply
optimal regret. Extensive numerical simulations and real data experiments are
presented to corroborate the effectiveness of our algorithms.

###  1.1 Contributions

To summarize, we make the following contributions in this paper.

Sharp dual convergence in non-linear and regularized cases. We derive the
convergence rate of sample-version dual solution to its population counterpart
in the case of additive non-linear rewards function and in the existence of a
non-separable regularizer. The convergence rate is at $O(T^{-1})$, which
improves the known rate $O(T^{-1}\log\log T)$ that was established only for
non-regularized linear reward functions (Li and Ye,, 2021). The improvement is
made possible by, jointly, a local strongly convex assumption on reward
functions and a delicate analysis of the local behavior of sample-version
stochastic dual program near the population optimal solution. The observed
local behavior and derived convergence performance are also valid for linear
or non-regularized cases. This dual convergence crucially motivates our
approach to treat a non-separable objective, which converts the non-separable
primal problem into a dual one that consists of separable functions. Our
analysis establishes a connection between the approximation errors measured by
function values and the deviations of approximate solutions, which are
determined by both intrinsic randomness and approximation of solutions. It
suggests that any approximate solution, up to a certain accuracy, to the dual
optimization suffices to guarantee the overall convergence of a primal-dual
algorithm, which lays the theoretical foundation for our history-dependent
algorithm design. It is noteworthy that, as a stochastic optimization problem,
the derived dual convergence sheds new light on the open Sample Average
Approximation (SAA) problems and may be of independent interest.

Adaptive algorithm framework. We propose a flexible dual-based and history-
dependent, i.e., reliant on past data and actions, algorithm framework for
solving the regularized online allocation problem. As a primal-dual algorithm
framework, each iteration mainly consists of two routines: primal decision
making and dual optimization. At a high level, our adaptive algorithm
framework generalizes the history-dependent policy in online linear
programming (Li and Ye,, 2021), which evolves from the budget-ration policy
(Arlotto and Gurvich,, 2019; Balseiro and Gur,, 2019) and the re-solving
heuristic in network revenue management (Jasin and Kumar,, 2012; Wu et al.,,
2015). There are two key ingredients in dual optimization of our algorithm
framework. First, at each iteration, we adaptively update the average
remaining resources in the dual problem. Besides fulfilling the resource
constraints, this adaptive resource control plays a critical role in achieving
a $O(\log T)$ regret rather than the $O(T^{1/2})$ one attained by Balseiro et
al., (2021). Secondly, at each iteration, our algorithm framework only
requires an approximate solution, up to a certain accuracy, to the dual
optimization. This allows a flexible choice of computationally efficient
algorithms for dual optimization, be them deterministic or stochastic. Paired
with first-order methods, our algorithm enjoys an acceptable polynomial-time
cost comparable to prior algorithms. More specifically, for strongly convex
objectives, it requires computing gradients for $O(t)$ times at time t; for
more general convex objectives, it requires $O(t^{3})$ times of gradient
computation. Note that our algorithm framework is also applicable to linear
reward functions or non-regularized online allocation problems.

Regret analysis. With its offline optimum as the benchmark, we investigate the
regret attained by the adaptive algorithm framework for regularized online
allocation problems. Since the regret is characterized by dual convergence,
the aforementioned new result of dual convergence allows us to derive a sharp
regret bound. More exactly, we show that our adaptive algorithm achieves an
$O(\log T)$ regret, which matches the best results in constraint-free and non-
regularized online convex optimization (Hazan et al.,, 2007) and multi-
secretary problem (Bray,, 2019). A matching lower bound is established under
our assumptions demonstrating the optimality of our adaptive algorithm
framework. To our best knowledge, this is the first theoretical guarantee of
an exact $O(\log T)$ regret bound for online non-linear allocation with hard
constraints and a non-separable regularizer. The best known regret even for
online learning programming (Li and Ye,, 2021) contains an additional
$\log\log T$ factor. By comparing with existing algorithms, we clarify the
critical role played by the adaptive resource control in controlling the
stopping time and achieving a logarithmic-order regret. In particular, we
establish a worst-case $O(T^{1/2})$ lower bound for dual-based algorithms if
the resource constraints are not adaptively updated. Basically, without
updating the resource constraints, dual-based algorithms suffer from early-
stopping.

We then elaborate the applications of our method and theory to online linear
programming, online convex optimization, online welfare maximization and
online convex packing. Simulation results are also presented.

###  1.2 Related Work

####  1.2.1 Online Linear Allocation

Many online problems with resource constraints can be formulated into online
allocation problems. A large proportion of early work mainly focused on linear
models. Vazirani et al., (2005); Mehta et al., (2007); Buchbinder et al.,
(2007) studied the AdWords problem, where a search engine tries to assign some
keywords to a set of competing bidders, each with a spending limit (i.e.,
constraint), and the goal is to maximize the revenue generated by these
keyword sales. The rewards in AdWords problem are proportional to consumed
resources and, thus, is a special case of online linear allocation. By viewing
AdWords as a generalization of online bipartite matching problem, Mehta et
al., (2007) achieved an optimal $(1-e^{-1})$-competitive ratio, which is
defined as the ratio of the revenue of an online algorithm to the revenue of
the best offline algorithm. Under a so-called random permutation model,
Devanur and Hayes, (2009) proposed a two-phase dual training algorithm for
AdWords problem and achieved the regret $O(T^{2/3})$. The random permutation
model, which assumes that the arrivals are in random order and the order
itself is uniformly distributed over all permutations, is more general than
the random input model, which assumes i.i.d. arrivals. But random input model
can be treated as a special case of random permutation model (Mehta,, 2013).
More discussions on the online allocation problems under random permutation
model can be found in Babaioff et al., (2008); Goel and Mehta, (2008);
Molinaro and Ravi, (2014) and references therein.

Apart from AdWords, two major topics related to online linear allocation are
online revenue management problem and online multi-secretary problem. In
online revenue management, a decision maker aims to find a dynamic pricing
policy that maximizes a company’s linear total rewards when the number of
supplied products is finite, demands of these products arrive sequentially,
and the resources for manufacturing the products are limited. Online revenue
management finds diverse applications in industry such as rental services, air
travel, hospital services (Talluri et al.,, 2004), etc. The earliest regret
analysis of this problem dates back to Cooper, (2002), which proposed a static
LP-based algorithm and achieved an $O(T^{1/2})$ regret. Later works show that
better regret is achievable by a re-solving strategy, i.e., repeatedly solving
an optimization program but with updated information. By combining the re-
solving strategy and a trigger-and-threshold mechanism, Reiman and Wang,
(2008) reduced the regret significantly to $O(T^{1/4})$. Equipped with
sufficiently frequent re-solving’s, Jasin, (2015) proposed to re-estimate the
parametric distribution of arrivals and proved that an $O(\log^{2}T)$ regret
is attained. Jasin and Kumar, (2012); Wu et al., (2015) and Bumpensanti and
Wang, (2020) investigated the special case when the i.i.d. arrivals obey a
discrete distribution with finite support and established $O(1)$ regrets for
re-solving style algorithms when the resource constraints are constants.
Online multi-secretary problem (Kleinberg,, 2005; Babaioff et al.,, 2007) is
one of the simplest online allocation problems as it has only one integer
constraint. Assuming the arrivals obey a known finite-support discrete
distribution, Arlotto and Gurvich, (2019) proposed an online budget-ratio (BR)
policy where decisions to fulfil or ignore requests are made by comparing the
remaining average budget with some fixed thresholds. Their BR policy is
adaptive and achieved an $O(1)$ regret but is inapplicable to the case of
multiple resource constraints. They also established a regret lower bound
$\Omega(T^{1/2})$ for all non-adaptive policies. Conversely, if the arrival
distribution is continuous, e.g. a simple uniform distribution over $[0,1]$,
Bray, (2019) developed a regret lower bound $\Omega(\log T)$ even when the
distribution is known to a decision maker.

Other independent works of online linear programming also contribute greatly
to the understanding of online allocation problems. Agrawal et al., (2014)
proposed a history-dependent dual-based algorithm that dynamically update dual
variables and periodically solve linear programs. Their algorithm achieved an
$O(T^{1/2})$ regret under the random permutation model. When the arrivals
satisfy the random input model, Devanur et al., (2019) proved that a dual-
based algorithm that attained an $O(T^{1/2})$ regret. But their algorithm
relies on the knowledge of the optimal allocation, which is unrealistic for
most applications. Otherwise, their algorithm requires periodically computing
the optimal solution to an offline linear programming. More recently, Li and
Ye, (2021) introduced a history-dependent algorithm that adaptively updates
the resource constraints, which achieved a regret $O(\log T\log\log T)$ that
is almost optimal except the $\log\log$ factor. But their strategy also
requires exact solutions to an offline linear programs of growing sizes, which
may be computationally intractable for large $T$. An $\Omega(\log T)$ regret
lower bound was established, which is consistent with Bray, (2019).

####  1.2.2 Online Convex Allocation

Linear objective functions only find limited applications in practice. Online
convex allocation moves one step further by allowing convex objective
functions. In Agrawal and Devanur, (2014), the authors investigated online
convex programming that is equipped with a fixed and convex reward function.
The imposed stochastic constraints are soft meaning that a certain degree of
constraint violations is allowed. They proposed a flexible algorithm framework
based on online convex optimization, which, for general convex objectives,
achieved an $O(T^{1/2})$ regret with $O(T^{1/2})$ constraint violations.
Furthermore, if the objective function is smooth, their algorithm achieves an
$O(\log T)$ regret with $O(\log T)$ constraint violations. The computational
cost of their algorithm can be linear provided that the offline optimum is
partially known. Otherwise, their algorithm requires solving convex programs
for logarithmic times to estimate the benchmark information periodically,
which can be computationally expensive.

Recently, partly due to its computational efficiency, dual mirror descent is
extensively studied for online convex allocation problems. Balseiro et al.,
(2022, 2020) focused on a class of online allocation problems with separable
reward functions and resource constraints that is proportional to time horizon
$T$. They proposed a dual-based mirror descent algorithm that achieves
$O(\sqrt{T})$ regret and was said to be unimprovable under their assumptions.
Their algorithm updates dual variables by mirror descent and makes primal
decisions by the conjugate functions. Their approach of controlling regret put
less emphasis on stopping time but focused more on the complementary slackness
of dual variables within updates. The rationale behind dual mirror descent is
that it presents a self-correcting mechanism that naturally prevents resources
from depleting too fast. This self-correcting mechanism relies on dual
updates; that is, when a request consumes more resources, the corresponding
dual variables will move against the excessive consumptions, and thus leading
to a more conservative subsequent action. The problem we study in this paper
is closer to Balseiro et al., (2021), which is the first to study online
convex allocation problems with a non-separable regularizer and hard resource
constraints. Their approach is similar to the non-regularized cases (Balseiro
et al.,, 2022, 2020), except that they define a new separable dual problem and
update dual variables using regularized subgradients since they allow non-
smooth regularizers. They showed that, for regularized online convex
allocation, dual mirror descent can still perform well and attain an
$O(T^{1/2})$ regret. While this regret is optimal for general convex reward
functions under both stochastic and adversarial input model, it is sub-optimal
when the reward functions possess more favourable conditions like strong
convexity. More recently, Lobos et al., (2021) extended dual mirror descent to
an even more challenging online allocation problem where the separable
objective and non-linear constraints are not necessarily convex. They proposed
a novel benchmark to measure the regret and concluded that an $O(T^{1/2})$
regret is achievable by dual mirror (sub-gradient) descent.

Besides deterministic and hard constraints, a large body of literature on
online convex programming focus on stochastic constraints and allow constrain
violations. For instance, Yu et al., (2017) investigated online convex
optimization with stochastic constraints and adversarial rewards. An
$O(T^{1/2})$ bound is achieved for both the regret and constraint violations.
A closely related problem is the long-term constraint problem, which aims to
solve an online convex optimization problem by permitting a small number of
cumulative constraint violations. Mahdavi et al., (2012); Jenatton et al.,
(2016) designed algorithms achieving $O(T^{1/2})$ regrets and $O(T^{3/4})$
constraint violations. When the objective function is strongly convex, Yuan
and Lamperski, (2018) proposed an algorithm that achieves an $O(\log T)$
regret at the cost of $O\big{(}(T\log T)^{1/2}\big{)}$ constraint violations.

It is worth briefly mentioning the literature on general online convex
optimization, which laid the early foundations of online convex allocation
problems. For strongly convex objectives, classical literature on online
convex optimization have revealed an optimal logarithmic regret. See
Zinkevich, (2003); Hazan et al., (2007) and references therein. It is
reasonable to expect a logarithmic-order regret for other online problems in
the existence of strong convexity. Nevertheless, achieving a logarithmic-order
regret is challenging if an additional non-separable regularizer is posed. In
literature, regularized online convex programming is commonly solved by the
follow-the-regularized-leader style algorithms. For instance, Xiao, (2010)
introduced regularized dual averaging (RDA), which is an extension of the
simple dual averaging algorithm originally proposed by Nesterov, (2009),
showing that an $O(T^{1/2})$ regret is achieved for general convex regularizer
and $O(\log T)$ regret for strongly convex regularizer. However, their
regularizer is separable, and hence their RDA scheme is inapplicable for our
problem. A generalized follow-the-regularized-leader framework is summarized
in McMahan, (2011, 2017), which includes many online-mirror-descent style
algorithms as special cases. Our dual-based adaptive algorithm differs from
the follow-the-regularized-leader algorithms as it exploits more historical
information rather than just the gradients and past actions, and it does not
follow the leader. More introduction for general online convex optimization
can be found in Hazan et al., (2016).

###  1.3 Notations

Some notations will be used throughout the paper. Define $a\wedge
b:=\min\\{a,b\\}$ and $a\vee b:=\max\\{a,b\\}$. Write $[n]$ as the shorthand
of $\\{1,\ldots,n\\}$. Define the non-negative region
$\mathbb{R}_{+}:=\left\\{x\middle|x\geq 0\right\\}$. We will always use $i$ to
denote dimensions and use $d_{i}$ for the $i$-th dimension of vector $d$, and
for vector sequence $\left\\{d_{t}\right\\}_{t=1}^{T}$, i.e., $d_{it}$ stands
for the $i$-th entry of vector $d_{t}$. Denote
$(x)^{+}:=\max\left\\{x,0\right\\}$, $\|\cdot\|_{2}$ and $\|\cdot\|_{\infty}$
for the vector $\ell_{2}$-norm and $\ell_{\infty}$-norm, respectively.

##  2 Regularized Online Allocation Problem

We describe the convex regularized online allocation problem with finite time
period $T$ as following:

$\displaystyle\max_{\\{x_{t},t\in[T]\\}}\quad$
$\displaystyle\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})$ (2.1) s.t.
$\displaystyle\sum_{t=1}^{T}b_{t}x_{t}\preceq dT,\ d\in\mathbb{R}_{+}^{m}$
$\displaystyle x_{t}\in\mathcal{X},\forall t\in[T].$

where $f_{t}:\mathbb{R}^{n}\to\mathbb{R}$ is the concave reward function,
$r:\mathbb{R}^{m}\to\mathbb{R}$ is a concave regularizer to penalize the
average resource consumption, $\ b_{t}\in\mathbb{R}^{m\times n}$ is the cost
matrix and its entry could be both positive or negative (i.e., we can
replenish the resource). We assume our inputs are stochastic, meaning that the
i.i.d. requests $\\{(f_{t},b_{t})\\}_{t=1}^{T}$ are sampled from an unknown
distribution $\mathcal{P}$: $(f_{t},b_{t})\sim\mathcal{P}$. The decision
region $\mathcal{X}\subseteq\mathbb{R}^{n}_{+}$ is closed and convex with void
action $0\in\mathcal{X}$ .

Following the online sequential learning setting, we assume that at each time
$1\leq t\leq T$, we first receive a request with known reward function and
cost $(f_{t},b_{t})$ and then make the decision $x_{t}$ based on the
observation of $t$-th request and history
$\mathcal{H}_{t-1}:=\left\\{f_{j},b_{j},x_{j}\right\\}_{j=1}^{t-1}$:

$x_{t}:=A(f_{t},b_{t},\mathcal{H}_{t-1}),$

by taking the total resource constraints $\sum_{j=1}^{t}b_{j}x_{j}\preceq dT$
into consideration. Here $A$ denotes a history-dependent algorithm. Our goal
is to design such an online algorithm $A$ that can maximize the regularized
total reward $\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(T^{-1}\cdot\sum_{t=1}^{T}b_{t}x_{t})$. Define the algorithm expected reward
over a given distribution $\mathcal{P}$ as

$R\left(A\middle|\mathcal{P}\right):=\mathbb{E}_{A,\mathcal{P}}\left[\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})\right].$ (2.2)

Here we take expectation with respect to both the inputs and the algorithm $A$
if $A$ is a stochastic algorithm. To measure the performance of an online
algorithm, we compare the algorithm reward with the expected offline optimum
(or hindsight optimum) defined by

$R^{*}(\mathcal{P}):=\mathbb{E}_{\mathcal{P}}\left[\max_{x_{t}\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}),\ s.t.\ \sum_{t=1}^{T}b_{t}x_{t}\preceq
dT\right],$ (2.3)

which serves as the benchmark performance. For a given $\mathcal{P}$, define
the regret as
$\operatorname{Regret}\left(A\middle|\mathcal{P}\right):=R^{*}(\mathcal{P})-R\left(A\middle|\mathcal{P}\right)$.
We then define the worst-case regret of an algorithm $A$ as the worst
difference between the expected online reward and offline optimum over all the
possible distributions in a certain probability family $\Xi$:

$\operatorname{Regret}(A):=\sup_{\mathcal{P}\in\Xi}\left\\{R^{*}(\mathcal{P})-R\left(A\middle|\mathcal{P}\right)\right\\},$
(2.4)

where the distribution family $\Xi$ will be identified later.

Compared with unconstrained online optimization, the key obstacle to designing
algorithms for the online allocation problem is to enforce the total resource
constraints, which shall not be violated at any time. However, we can
transform the primal problem into a dual one with fewer constraints by the
duality theory. This motivates us to investigate the problem (2.1) from the
dual perspective.

###  2.1 The dual problem

We consider the dual problem of online allocation (2.1). The Lagrangian of
this problem is

$L(x,a,\lambda,\mu):=\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(a)+\mu^{\top}(aT-\sum_{t=1}^{T}b_{t}x_{t})+\lambda^{\top}(dT-\sum_{t=1}^{T}b_{t}x_{t}).$
(2.5)

Here we introduce the equality constraint $a=(\sum_{t=1}^{T}b_{t}x_{t})/T$ in
order to separate $r(T^{-1}\cdot\sum_{i=1}^{T}b_{t}x_{t})$ into additive
terms. Denote the domain of $r(a)$ as $\mathcal{Z}$ with
$b\circ\mathcal{X}:=\textsf{span}\left\\{b\cdot x\middle|\text{ for all
possible }b\text{ and }x\in\mathcal{X}\right\\}\subseteq\mathcal{Z}$. Define
the conjugate function

$\displaystyle f^{*}_{t}(\lambda):=$
$\displaystyle\max\limits_{x\in\mathcal{X}}\left\\{f_{t}(x)-x^{\top}\lambda\right\\}$
(2.6) $\displaystyle r^{*}(\mu):=$
$\displaystyle\max\limits_{a\in\mathcal{Z}}\left\\{r(a)-a^{\top}\mu\right\\}.$

Then, the dual problem of 2.1 can be written as

$\displaystyle\min_{\mu,\lambda}\quad$
$\displaystyle\bar{D}_{T}(\lambda,\mu,d):=\frac{1}{T}\sum_{t=1}^{T}f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d^{\top}\lambda$
(2.7) $\displaystyle s.t.$ $\displaystyle\lambda\succeq 0.$

Under our stochastic input assumption, (2.7) can be viewed as a sample average
approximation (SAA) (Shapiro et al.,, 2009) of the following stochastic
program:

$\displaystyle\min_{\mu,\lambda}\quad$ $\displaystyle
D(\lambda,\mu,d):=\mathbb{E}f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d^{\top}\lambda$
(2.8) $\displaystyle s.t.$ $\displaystyle\lambda\succeq 0.$

In the following discussion, we will sometimes write the dual variable
uniformly as $\boldsymbol{\lambda}:=[\lambda^{\top},\mu^{\top}]^{\top}$ in
shorthand. If we have known the exact offline solution to (2.7), denoted by
$\boldsymbol{\lambda}_{T}^{*}$, then by choosing the corresponding primal
variables we can optimize the primal problem (2.1). However, in online setting
it is impossible to find such exact dual solution before time $T$. Thus at
time $t$ we turn to solve the $t$-sample average approximation of
$D(\lambda,\mu,d)$, i.e.,

$\displaystyle\min_{\mu,\lambda}\quad$
$\displaystyle\bar{D}_{t}(\lambda,\mu,d):=\frac{1}{t}\sum^{t}_{j=1}f_{j}^{*}(b_{j}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d^{\top}\lambda$
(2.9) $\displaystyle s.t.$ $\displaystyle\lambda\succeq 0.$

and then use the dual approximate solution $\boldsymbol{\lambda}_{t}$ to
decide the primal solution $x_{t}$. Such a re-solving idea can also be found
in other contexts (Jasin,, 2015; Ferreira et al.,, 2018; Li and Ye,, 2021) and
has shown its merit in controlling the regret both in theory and in practice.
Hence we expect that this idea also works in convex online allocation
problems. Nevertheless, to discuss how practical this re-solving idea is in
our setting, we still have three crucial questions to answer:

  1. 1.

What is the behavior of $\boldsymbol{\lambda}_{T}^{*}$ when $T$ is large? We
know that $\boldsymbol{\lambda}_{T}^{*}$ varies depending on the data we
collected. But from the stochastic programming perspective, as $T$ goes large,
the optimal solution to the SAA (2.7), $\boldsymbol{\lambda}_{T}^{*}$, will
converge to the solution to its stochastic program (2.8), denoted by
$\boldsymbol{\lambda}^{*}$. If we want to establish the theory of dual-based
algorithms that rely on the approximation of $\boldsymbol{\lambda}_{T}^{*}$,
we need to explore the convergence behavior of $\boldsymbol{\lambda}_{T}^{*}$
toward $\boldsymbol{\lambda}^{*}$ before we proceed with the study of
algorithms.

  2. 2.

How will the dual approximate solutions affect our reward and, consequently,
the regret? This question is the key for the algorithm design. For online
allocation problems, a good approximation of $\boldsymbol{\lambda}^{*}$ or
$\boldsymbol{\lambda}_{T}^{*}$ does not necessarily mean a good reward because
of the restriction imposed by resource depletion and stopping time. As we will
show later, simply solving the convex programming (2.9) is not enough to
achieve the optimal regret. We attempt to explain the influence of dual
approximate solutions on regret in two phases: before and after stopping time,
and show that the adaptive strategy of updating constraints is necessary for
optimal regret.

  3. 3.

How to control the regret as well as make the algorithm computationally
efficient? Most of the re-solving techniques require periodically solving
potentially large-scale convex programming, which is computationally
demanding. Interestingly, we will show that a proper approximation of dual
optimal solutions up to certain precisions can significantly reduce the
computational costs, while maintaining the optimal order of regret. The
influence of our approximation scheme on the regret is, in general, negligible
when compared to the exact optimal solutions.

We propose an online adaptive algorithm for solving program (2.1), which
achieves logarithmic regret based on the following assumptions.

###  2.2 Assumptions

######  Assumption 1 (Basic assumptions on arrivals).

The arrival sequences $\\{(f_{t},b_{t})\\}$ satisfy:

  1. 1.1

$\\{(f_{t},b_{t})\\}_{t=1}^{T}$ are generated i.i.d. from distribution
$\mathcal{P}$.

  2. 1.2

$f_{t}$ is strictly concave in the closed convex decision region
$\mathcal{X}\subseteq\mathbb{R}^{n}_{+}$ with $\left\lVert
x\right\rVert_{\infty}\leq D$ for any $x\in\mathcal{X}$.

  3. 1.3

There exists $\bar{f}\in R_{+}$ such that $\forall x\in\mathcal{X}$,
$|f_{t}(x)|\leq\bar{f}$.

  4. 1.4

There exists $\bar{b}\in R_{+}$ such that $\left\lVert
b_{t}\right\rVert_{2}\leq\bar{b}$ for any $t$.

  5. 1.5

We assume there exists $\underline{d}>0$, and a large $\bar{d}>0$ such that
for any $i\in[m]$, $d_{i}\in(\underline{d},\bar{d})$. Denote
$\Omega_{d}=\bigotimes_{i=1}^{n}(\underline{d},\bar{d})$.

The assumptions on the upper bound $\bar{f}$ and $\bar{b}$ are common and
practical in online allocation problems. It helps us control the size of the
problem and ease our analysis. Assumption 1.5 follows from Li and Ye, (2021).
We assume that the average resource constraints $d$ is of a reasonable size,
i.e., $d_{i}$ is neither too large nor too small. If $d_{i}$ is too large,
then the constraint itself will be of no interest because the restriction it
imposed on the primal variables is negligible. This assumption is crucial for
the subsequent discussion of regret, especially for bounding the stopping
time.

Under Assumption 1, we can define the general feasible region of our
regularizer $r(a)$ as $\mathcal{Z}:=\left\\{a\middle|\left\lVert
a\right\rVert_{2}\leq\sqrt{n}D\bar{b}\right\\}$, which satisfies
$b\circ\mathcal{X}\subseteq\mathcal{Z}$. We then describe the necessary
assumptions on the regularizer $r$.

In order to study the influence of the average constraint $d$ on adaptive
algorithms and how the variation of it affects the solution, we need the
following assumptions.

######  Assumption 2 (Assumptions on the regularizer).

Suppose $(\lambda^{*},\mu^{*})$ is the optimal solution to the problem (2.8)
when $d\in\Omega_{d}$. Then for any $d\in\Omega_{d}$, the concave regularizer
$r$ is either $0$ or satisfies:

  1. 2.1

$r$ is strictly concave and bounded in $\mathcal{Z}$: $|r|\leq\bar{r}$ with
bounded (sub)gradient $\left\lVert\nabla r(a)\right\rVert_{\infty}\leq G$ for
any $a\in\mathcal{Z}$.

  2. 2.2

The conjugate $r^{*}$ satisfies $\langle\nabla r^{*}(-\mu)-\nabla
r^{*}(-\mu^{*}),\mu^{*}-\mu\rangle\geq\underline{\mathcal{L}}_{r}\left\lVert\mu-\mu^{*}\right\rVert^{2}_{2}$
for any $\mu$ satisfying $\left\lVert\mu\right\rVert_{\infty}\leq G$ and some
constant $\underline{\mathcal{L}}_{r}>0$.

  3. 2.3

The conjugate $r^{*}$ satisfies $\left\lVert\nabla r^{*}(-\mu)-\nabla
r^{*}(-\mu^{*})\right\rVert_{2}\leq\bar{\mathcal{L}}_{r}\left\lVert\mu-\mu^{*}\right\rVert_{2}$
for any $\mu$ satisfying $\left\lVert\mu\right\rVert_{\infty}\leq G$ and some
constant $\bar{\mathcal{L}}_{r}>0$.

Together with Assumption 1, we can show that both the population-version and
sample-version optimal solutions, $\boldsymbol{\lambda}^{*}$ and
$\lambda_{T}^{\ast}$, respectively, are uniformly bounded.

######  Lemma 1.

Under Assumption 1, 2, the optimal solutions to problem (2.7) and (2.8) are
bounded by:

$\begin{gathered}\left\lVert\lambda^{*}_{T}\right\rVert_{\infty}\leq\frac{2(\bar{f}+\bar{r})}{\underline{d}},\left\lVert\lambda^{*}\right\rVert_{\infty}\leq\frac{2(\bar{f}+\bar{r})}{\underline{d}}\\\
\left\lVert\mu^{*}_{T}\right\rVert_{\infty}\leq
G,\left\lVert\mu^{*}\right\rVert_{\infty}\leq G\end{gathered}$ (2.10)

By Lemma 1, we define the regions that contain all the possible optimal dual
variable as $\Omega_{\lambda}:=\left\\{\lambda\middle|\ \lambda\succeq 0\text{
and
}\left\lVert\lambda\right\rVert_{\infty}\leq\frac{2(\bar{f}+\bar{r})}{\underline{d}}\right\\}$,
and $\Omega_{\mu}:=\left\\{\mu\middle|\
\left\lVert\mu\right\rVert_{\infty}\leq G\right\\}$. These regions will be the
feasible sets of our dual variables since we do not want them to move far from
the optimal solution $\boldsymbol{\lambda}^{*}$. Assumption 2.2 and 2.3
require the conjugate of regularizer to be smooth and have quadratic growth.
This can be achieved if the regularizer $r$ is locally strongly convex and
smooth (see, Kakade et al., (2009) or Agrawal and Devanur, (2014) for the
conjugate of strongly convex/smooth functions). But our assumption is a bit
weaker than directly assuming strong convexity and smoothness on $r$ itself.

Here are several possible regularizers that satisfy our assumptions:

  1. 1.

$\ell_{2}$-loss: $r(a):=-\kappa\left\lVert a\right\rVert_{2}^{2}$. This
regularizer serves as a tool to directly penalize resource consumption and
achieve the goal of resource saving.

  2. 2.

Smooth minima:
$r(a):=-\kappa\log(\sum_{i=1}^{m}\exp{(-a_{i})}+\exp(-\sqrt{n}D\bar{b}))$.
This LogSumExp regularizer is the smooth approximation of max-min fairness
regularizer $r(a):=\kappa\min_{i}\\{a_{i}\\}\wedge\sqrt{n}D\bar{b}$, which
forces us to maximize the minimum resource consumption. Resources after max-
min fairness regularization tend to be distributed fairly so that all
resources are utilized adequately. See, e.g., Nash, (1950); Bertsimas et al.,
(2011); Balseiro et al., (2021).

  3. 3.

Smooth maxima: $r(a):=-\kappa\log(\sum_{i=1}^{m}\exp{(a_{i})}+1)$. This
regularizer is the smooth approximation of negative maximum consumption
$r(a):=-\kappa\max_{i}\\{a_{i}\\}\vee 0$. This represents the load-balancing
task: we minimize the maximum resource consumption so that all the resources
are evenly distributed and no resource is over-exploited (or balanced load for
every computer server in the load-balancing task).

  4. 4.

Entropy loss:
$r(a):=-\kappa\left[\sum_{i=1}^{m}a_{i}\log\left(a_{i}\right)+\left(1-\sum_{i=1}^{m}a_{i}\right)\log\left(1-\sum_{i=1}^{m}a_{i}\right)\right]$
with the corresponding feasible region:
$\mathcal{Z}:=\left\\{a\in\mathbb{R}_{+}^{m}\mid\sum_{i=1}^{m}a_{i}\leq
1\right\\}$. We use this entropy loss when our problem is related to random
strategies and probabilistic assignment, e.g., in the online advertising, we
randomly assign each impression to different advertisers with selected
probabilities. This entropy loss regularizer seeks to find online allocation
strategies with high entropy, which may share appealing properities like
diversity, fairness, or robustness (Agrawal et al.,, 2018).

  5. 5.

Huber loss (Huber,, 1964):
$r(a):=-\kappa\left[\sum_{i=1}^{m}\frac{1}{2}a_{i}^{2}\mathbb{I}(|a_{i}|\leq\delta)+\delta(|a_{i}|-\frac{\delta}{2})\mathbb{I}(|a_{i}|>\delta)\right]$
for some $\delta>0$. Then conjugate of a Huber loss is also in the form
$r^{*}(\mu):=\sum_{i=1}^{m}\frac{1}{2\kappa}\mu_{i}^{2}\mathbb{I}(|\mu_{i}|\leq\kappa\delta)+(\sqrt{n}D\bar{b}|\mu_{i}|-\kappa\delta(\sqrt{n}D\bar{b}-\frac{\delta}{2})\mathbb{I}(|a_{i}|>\kappa\delta)$.
Huber loss satisfies our assumption if the optimal solution sits in the center
of $\Omega_{\mu}:\left\lVert\mu^{*}\right\rVert_{\infty}<\kappa\delta$. This
depends on actual problems since $\mu^{*}$ is determined by both $f$ and $r$.
But Huber loss entails that our regularizer may not necessarily be (globally)
strongly convex and smooth. Compared with the $\ell_{2}$-loss, Huber loss
penalizes more mildly to extreme resource consumptions.

  6. 6.

No regularizer: $r(a):=0$. In this case, our problem is reduced to the non-
regularized online convex allocation problem. Therefore, the theory developed
in this paper is immediately applicable to the non-regularized cases.

In addition, we need the following non-degeneracy assumptions.

######  Assumption 3 (Non-degeneracy).

We assume that our problem is non-degenerate: suppose $(\lambda^{*},\mu^{*})$
is the optimal solution to the problem (2.8) when $d\in\Omega_{d}$. For ease
of notations, we write $\lambda^{\ast}$ and $\mu^{\ast}$ instead of
$\lambda^{\ast}(d)$ and $\mu^{\ast}(d)$, respectively. Then for any
$d\in\Omega_{d}$,

  1. 3.1

Let $\nu:=\lambda+\mu$ and $\nu^{*}:=\lambda^{*}+\mu^{*}$. The conjugate
function $f^{*}_{t}$ satisfies

$\begin{gathered}\left\lVert\mathbb{E}\left[\nabla{f^{*}_{t}}(b_{t}^{\top}\nu)-\nabla{f^{*}_{t}}(b_{t}^{\top}\nu^{*})\;\middle|\;b_{t}\right]\right\rVert_{2}\leq\bar{\mathcal{L}}_{f}\left\lVert
b_{t}^{\top}\nu-b_{t}^{\top}\nu^{*}\right\rVert_{2},\\\
\mathbb{E}\left[\langle\nabla{f^{*}_{t}}(b_{t}^{\top}\nu)-\nabla{f^{*}_{t}}(b_{t}^{\top}\nu^{*}),b_{t}^{\top}\nu-
b_{t}^{\top}\nu^{*}\rangle\middle|b_{t}\right]\geq\underline{\mathcal{L}}_{f}\left\lVert
b_{t}^{\top}\nu-b_{t}^{\top}\nu^{*}\right\rVert^{2}_{2}\end{gathered}$

for any $\lambda\in\Omega_{\lambda}$, $\mu\in\Omega_{\mu}$ and constants
$\bar{\mathcal{L}}_{f},\underline{\mathcal{L}}_{f}>0$, conditioning on
$b_{t}$.

  2. 3.2

The matrix $M:=\mathbb{E}\left[b_{t}b_{t}^{\top}\right]$ is positive definite
with minimum eigenvalue $\sigma_{\min}>0$.

  3. 3.3

Define the primal variable given $(\lambda^{*},\mu^{*})$ as
$\tilde{x}_{t}(\boldsymbol{\lambda}^{*}):=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda^{*}+\mu^{*})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda^{*}+\mu^{*}))$. Then the optimal solution
$(\lambda^{*},\mu^{*})$ satisfies $\lambda^{*}_{i}=0$ if and only if
$d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}>0$.

Assumption 3.1 requires the expected conjugate of reward function to exhibit a
local quadratic growth and smoothness, conditioning on any given $b_{t}$.
Combined with Assumption 2.2, 2.3, Assumption 3.1 ensures that the stochastic
program (2.8) is locally smooth and locally strongly convex. Assumption 3.1
controls the growth rate of the reward function (and its conjugate) so that it
will neither grow too fast nor degenerate to a line, which plays a critical
role in characterizing dual solutions. Assumption 3.2 is easily satisfied
since, oftentimes, the constraints are linearly independent. Assumption 3.3
imposes strong complementary slackness on the resource constraints
$d\in\Omega_{d}$ uniformly. This suggests that when $d$ changes within a
certain region of $\Omega_{d}$, the binding or non-binding dimensions (defined
below) of resource constraints of the optimal solution will not change. This
brings convenience for analyzing adaptive algorithms with frequently updated
constraints. Assumption 3 states the non-degeneracy condition for both primal
and dual problems with nonlinear objectives, which is generalized from the
non-degeneracy condition of linear programs (Jasin and Kumar,, 2012; Jasin,,
2015; Wu et al.,, 2015; Li and Ye,, 2021). Note that Assumption 3 only
concerns the deterministic problem (2.8), but the empirical problem not
necessarily share these local properties.

In this sequel, all the dimensions that satisfy
$d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}=0$
with respect to the original $d$ in (2.1) are referred to as binding
dimensions. Denote
$I_{\textsf{B}}=\left\\{i\middle|d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}=0\right\\}$
the collection of binding dimensions. Similarly, non-binding dimensions are
written as
$I_{\textsf{NB}}=\left\\{i\middle|d_{i}-d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}>0\right\\}$.
Here for ease of notations, we omit the dependence of $I_{\textsf{B}}$ and
$I_{\textsf{NB}}$ on the resource constraint $d$. Assumption 3.3 ensures that
binding and non-binding dimensions can be uniquely determined by the dual
solution $\lambda^{*}$.

Note that $-\nabla f_{t}^{\ast}(b_{t}^{\top}\nu)$ represents the primal
solution given dual variable $\nu$. Its randomness stems from the stochastic
reward function $f_{t}$. From this perspective, Assumption 3 concerns the
affect of dual variables to their corresponding expected primal solutions. It
turns out that merely the perturbation behavior of expected primal solutions
is not sufficient for our analysis, and we also need the perturbation behavior
of the intrinsically random primal solutions, which can be controlled by the
second moment. The following assumption serves for this purpose. Equivalently,
it depicts the variation behavior of the random award function $f_{t}$. This
second-order moment establishes the connection between dual variables and
primal performances.

######  Assumption 4 (Smoothness of the second moment).

Let $\nu:=\lambda+\mu$ and $\nu^{*}:=\lambda^{*}+\mu^{*}$ when we choose
$d\in\Omega_{d}$ in (2.8). The second moment of the gradient $\nabla
f_{t}^{*}$ satisfies the following smoothness

$\mathbb{E}\left[\left\lVert\nabla f_{t}^{*}(b_{t}^{\top}\nu)-\nabla
f_{t}^{*}(b_{t}^{\top}\nu^{*})\right\rVert^{2}_{2}\middle|b_{t}\right]\leq
L_{2}\left\lVert b_{t}^{\top}(\nu-\nu^{*})\right\rVert^{2}_{2}$

for any $d\in\Omega_{d}$, $\lambda\in\Omega_{\lambda}$, $\mu\in\Omega_{\mu}$
and given $b_{t}$, where $L_{2}>0$ is a constant.

Assumption 4 requires the variation of reward function given $b_{t}$:
$f_{t}\sim\mathcal{P}|b_{t}$ to be mild so that the primal solution
$\tilde{x}_{t}(\boldsymbol{\lambda}):=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda+\mu))$ has a second order moment smoothness.
Note that this doesn’t mean that $\nabla f^{*}_{t}$ must be globally smooth. A
similar description of smoothness can be found in Gorbunov et al., (2020).
Compared with Assumption 3.1, Assumption 4 actually states the smoothness in a
different perspective. Assumption 3.1 only requires the smoothness of the
expected reward, but here Assumption 4 focuses more on the variation of the
random reward function itself. Basically, Assumption 4 claims that no matter
how the reward $f_{t}$ varies, the difference of primal variables can be
bounded by the difference of dual variables in expectation. Assumption 4 is
not necessary for the study of dual convergence in section 3, but it is
indispensable for the theoretical study of adaptive algorithms and regret
analysis. We note that Assumptions 2-4 assume the corresponding conditions
holds for all the $d\in\Omega_{d}$.

##  3 Dual Convergence

For all dual-based online algorithms, the finite-sample convergence rate of
dual variables is of great value since it reveals the best performance dual-
based algorithms can achieve compared to the deterministic optimum. Recall the
optimal solution $\boldsymbol{\lambda}_{T}^{\ast}$ to the sample average
approximation (SSA) in eq. (2.7). The Law of Large Numbers dictates that
$\boldsymbol{\lambda}_{T}^{\ast}$ converges to $\lambda^{\ast}$ in probability
as $T\to\infty$. While the asymptotic behaviors of optimal solutions to SAA
have been intensively studied in the literature (Kleywegt et al.,, 2002;
Shapiro et al.,, 2009; Kim et al.,, 2015), they are not enough for us to
develop the non-asymptotical dual convergence in the case of regularized
online convex programming. In this section, we establish the dual convergence
bounds under locally strong convexity, i.e., Assumptions 1-3, for regularized
online problem (2.1). We emphasize that our assumptions hold uniformly for all
$d^{\prime}\in\Omega_{d}$. Consequently, the dual convergence performance we
will derive in this section also holds for all $d^{\prime}\in\Omega_{d}$.

Define
$D_{t}(\boldsymbol{\lambda},d):=f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d^{\top}\lambda$,
and the corresponding gradient

$\phi_{t}(\boldsymbol{\lambda},d):=\nabla_{\boldsymbol{\lambda}}D_{t}(\boldsymbol{\lambda},d)=\left[\begin{array}[]{c}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+d\\\ b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu+\lambda)-\nabla r^{*}(-\mu)\end{array}\right].$

Then we have $\nabla
D(\boldsymbol{\lambda},d):=\nabla_{\boldsymbol{\lambda}}D(\boldsymbol{\lambda},d)=\mathbb{E}\phi_{t}(\boldsymbol{\lambda},d)$.
Denote
$\bar{\phi}_{T}(\boldsymbol{\lambda},d):=T^{-1}\sum_{t=1}^{T}\phi_{t}(\boldsymbol{\lambda},d)$.
One crucial idea to bounding the dual convergence is that the confined growth
rate of $D(\boldsymbol{\lambda},d)$ indicates that, with high probability, its
sample version $\bar{D}_{T}(\boldsymbol{\lambda},d)$ is lower bounded by a
quadratic function (Li and Ye,, 2021). The confined growth speed of
$D(\boldsymbol{\lambda},d)$ is guaranteed by the following proposition.

######  Proposition 1.

Under Assumptions 1-3, the objective function $D(\boldsymbol{\lambda},d)$ in
stochastic program (2.8) satisfies the following growth condition:

$\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\leq
D(\boldsymbol{\lambda},d)-D(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})\leq\bar{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2},$
(3.1)

where the constant
$\underline{\mathcal{L}}_{D}:=\frac{\underline{\mathcal{L}}_{r}}{4}\wedge\frac{1}{2}\frac{\underline{\mathcal{L}}_{r}}{\underline{\mathcal{L}}_{r}+2\underline{\mathcal{L}}_{f}\sigma_{\min}}$,
$\bar{\mathcal{L}}_{D}:=\bar{b}^{2}\bar{\mathcal{L}}_{f}+\bar{\mathcal{L}}_{r}/2$.

By Proposition 1, we now derive an upper bound for dual convergence
$\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
by capturing the shape of dual objective
$\bar{D}_{T}(\boldsymbol{\lambda},d)$. While this idea is typical in
literature (Li and Ye,, 2021), we seek a more delicate analysis, which enables
us to reach a sharper result. Basically, we focus on the local behavior of
$\bar{D}_{T}(\boldsymbol{\lambda},d)$ around $\boldsymbol{\lambda}^{*}$. The
rationale is obvious. Since $\bar{D}_{T}(\boldsymbol{\lambda},d)$ is always
convex and converges to a deterministic convex function, the shape of
$\bar{D}_{T}(\boldsymbol{\lambda},d)$ in a small neighborhood of
$\boldsymbol{\lambda}^{*}$ will mimic that of $D(\boldsymbol{\lambda},d)$ as
long as $T$ is large enough. Consequently, its optimal solution
$\boldsymbol{\lambda}^{*}_{T}$ will lie in a small neighbourhood of
$\boldsymbol{\lambda}^{*}$.

Consider the first order and second order term of
$\bar{D}_{T}(\boldsymbol{\lambda},d)$ separately. Decompose the convex
function
$\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)$
into two parts:

$\displaystyle\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)=\underbrace{\left\langle\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle}_{\text{first
order
term}}+\underbrace{\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)-\left\langle\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle}_{\text{second
order term}}.$ (3.2)

It suffices to show that, with high probability, the first order term is lower
bounded by a linear function and the second order term is lower bounded by a
quadratic function, within a small neighborhood of $\boldsymbol{\lambda}^{*}$.
For the first order term, we need the concentration of gradients.

######  Lemma 2.

Under Assumptions 1-3, the concentration of the gradient in the first order
term $\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d)$ satisfies

$\displaystyle\mathop{{}\mathbb{P}}(\left\lVert\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right\rVert_{2}>\varepsilon)\leq
4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}}),$ (3.3)

for any $\varepsilon>0$, where the constant
$c_{1}:=\sqrt{n}\bar{b}D+\bar{d}\vee G$.

By Lemma 2, we conclude that, with high probability, the first order term in
(3.2) is lower bounded by
$\left\langle\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle\geq\left\langle\nabla
D(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle-\varepsilon\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq-\varepsilon\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$.
For the second order term, we focus on a small neighborhood of
$\boldsymbol{\lambda}^{*}$. For a constant $H>0$ (to be clarified soon),
define $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ as

$\Omega_{\boldsymbol{\lambda}}(\varepsilon):=\left\\{(\lambda^{\ast},\mu)\middle|\left\lVert\lambda-\lambda^{*}\right\rVert_{\infty}\leq
4H\varepsilon,\ \left\lVert\mu-\mu^{*}\right\rVert_{\infty}\leq
4H\varepsilon\right\\}.$ (3.4)

Actually, it suffices to control the second order term for all dual variables
in $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ since we shall show that
$\boldsymbol{\lambda}_{T}^{\ast}$ belong to
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ with a high probability depending
on the value of $\varepsilon$. In order to control the shape of second order
term for all dual variables in $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$,
we systematically split the region
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ to derive a uniform concentration
of the second order term. The motivation for choosing this small neighborhood
rather than a fixed region is that, for a convex function, the local behavior
near the deterministic optimal solution is enough to guarantee the global
properties of empirical optimal solutions. Consequently, for this small
neighborhood, the size of its covering according to our splitting scheme can
be bounded by a constant. The benefit of this local analysis is that we can
successfully eliminate the O($\log\log T$) factor and achieve a sharper dual
convergence bound. The uniform concentration of the second order term in
(3.2), together with Lemma 2, enable us to derive the following result.

######  Proposition 2.

Under Assumptions 1-3, given any $\varepsilon>0$, the dual problem satisfies
that for
$\forall\boldsymbol{\lambda}\in\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ and
$\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>2H\varepsilon$
, there exists a corresponding
$\boldsymbol{\lambda}^{\prime}\in\Omega_{\boldsymbol{\lambda}}(\varepsilon)$
such that
$\left\lVert{\boldsymbol{\lambda}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
and

$\displaystyle\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert\boldsymbol{\lambda}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-\underline{\mathcal{L}}_{D}H\varepsilon\left\lVert\boldsymbol{\lambda}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$

with probability at least
$1-4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}})-2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{T\varepsilon^{2}}{2})$,
where

$\begin{gathered}H:=\left(1+2\sqrt{2}(\sqrt{n}\bar{b}D+\sqrt{m}G)(1+\frac{\sqrt{m}(1-q)}{q})\right)/\underline{\mathcal{L}}_{D},\text{
and }\\\
q:=\frac{\sqrt{m}}{\sqrt{m}+1\wedge\frac{\underline{\mathcal{L}}_{D}}{8\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}}}\vee\frac{1}{2}.\end{gathered}$

The detailed proof is deferred to Appendix A.4. Proposition 2 delivers a
strong message that, under the event where the inequality holds, the dual
optimal solution $\boldsymbol{\lambda}_{T}^{\ast}$ must be close to
$\boldsymbol{\lambda}^{\ast}$ in the sense that
$\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
2H\varepsilon$. Otherwise:

  1. 1.

If $\boldsymbol{\lambda}^{*}_{T}$ has
$2H\varepsilon<\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
4H\varepsilon$, then there will be a ${\boldsymbol{\lambda}^{*}_{T}}^{\prime}$
such that
$\left\lVert{\boldsymbol{\lambda}^{*}_{T}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>2H\varepsilon$,
and

$\displaystyle\bar{D}_{T}(\boldsymbol{\lambda}^{*}_{T},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert{\boldsymbol{\lambda}^{*}_{T}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-\underline{\mathcal{L}}_{D}H\varepsilon\left\lVert{\boldsymbol{\lambda}^{*}_{T}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>0,$

which contradicts the optimality of $\boldsymbol{\lambda}^{*}_{T}$.

  2. 2.

If $\boldsymbol{\lambda}^{*}_{T}$ has
$\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>4H\varepsilon$,
since
$\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)=0$
and
$\bar{D}_{T}(\boldsymbol{\lambda}^{*}_{T},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\leq
0$, by the convexity of $\bar{D}_{T}$ we have
$\bar{D}_{T}(\tilde{\boldsymbol{\lambda}},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\leq
0$ for any
$\tilde{\boldsymbol{\lambda}}=\boldsymbol{\lambda}^{*}+\alpha(\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*})$
with $0\leq\alpha\leq 1$. Then we can always find an $\alpha$ such that
$2H\varepsilon<\left\lVert\tilde{\boldsymbol{\lambda}}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
4H\varepsilon$ and
$\bar{D}_{T}(\tilde{\boldsymbol{\lambda}},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\leq
0$. However, according to Proposition 2, we have

$\bar{D}_{T}(\tilde{\boldsymbol{\lambda}},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert{\tilde{\boldsymbol{\lambda}}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-\underline{\mathcal{L}}_{D}H\varepsilon\left\lVert{\tilde{\boldsymbol{\lambda}}}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>0,$

which also ends up with a contradiction.

Thus, under the event in Proposition 2, we get
$\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
2H\varepsilon$. Since $2H\varepsilon$ is smaller than the radius of
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$, we can safely conclude that the
optimal solution $\boldsymbol{\lambda}^{*}_{T}$ lies in the small neighborhood
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$. Consequently, we derive the
following $O(T^{-1})$ bound for dual convergence.

######  Theorem 1 (Dual convergence).

Under Assumptions 1-3, the dual optimal solution
$\boldsymbol{\lambda}^{*}_{T}$ satisfies

$\displaystyle\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\leq
C_{1}\cdot\frac{1}{T},$ (3.5)

where

$C_{1}:=4H^{2}\left(16m^{2}c_{1}+4(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\right)$

###### Proof.

By the tail expectation formula, for constant $H>0$, we have

$\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}=4H^{2}\int_{0}^{\infty}\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}>4H^{2}z)dz$

According to the probabilistic bound in Proposition 2, for any $z>0$,

$\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}>4H^{2}z)\leq
4m\exp(-\frac{Tz}{4mc_{1}})+2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{Tz}{2}).$

Then, calculating the integral, we get

$\displaystyle\mathbb{E}(\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2})$
$\displaystyle=4H^{2}\int_{0}^{\infty}\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{*}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\geq
4H^{2}z)dz$
$\displaystyle\leq\int_{0}^{\infty}\left[4m\exp(-\frac{Tz}{4mc_{1}})+2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{Tz}{2})\right]dz$
$\displaystyle=\frac{C_{1}}{T}$

∎

######  Remark 1.

Our dual convergence bound is sharper than that in Li and Ye, (2021). Under
our assumption, the $O(T^{-1})$ rate is unimprovable because we can find a
distribution $\mathcal{P}\in\Xi$ that incurs an $\Omega(T^{-1})$ dual
convergence rate. Let us consider a non-regularized case when $x\in[0,1]$ and
$f_{t}(x):=f(x,\xi_{t}):=-(x-2\xi_{t})^{2}/4+\xi_{t}^{2}$, with the single
constraint $d=1/2$ and cost $b_{t}=1$. The dual problem is

$D_{t}(\lambda)=\begin{cases}\frac{1}{2}\lambda&\text{ if }\lambda>\xi_{t}\\\
-\frac{1}{4}+\xi_{t}-\frac{1}{2}\lambda&\text{ if
}\lambda<\xi_{t}-\frac{1}{2}\\\
\lambda^{2}-2(\xi_{t}-\frac{1}{4})\lambda+\xi_{t}^{2}&\text{ if
}\xi_{t}-\frac{1}{2}\leq\lambda\leq\xi_{t}.\end{cases}$

Let $\xi_{t}$ be any distribution varies within $[1/2,\ 3/4]$ with variance
$\sigma^{2}_{\xi}>0$. Then, for any $t$, we have $\xi_{t}-1/4\in[1/4,\
1/2]\subseteq[\xi_{t}-1/2,\xi_{t}]$. Thus, for the sample average
$\bar{D}_{T}(\lambda):=T^{-1}\sum_{t=1}^{T}D_{t}(\lambda)$, when
$\lambda\in[1/4,\ 1/2]$,
$\bar{D}_{T}(\lambda):=\lambda^{2}-2(\bar{\xi_{T}}-1/4)\lambda+\bar{\xi^{2}_{T}}$
with the optimal solution being $\lambda^{*}_{T}:=\bar{\xi_{T}}-1/4$. We have
$\mathbb{E}(\lambda^{*}_{T}-\lambda^{*})^{2}\geq\operatorname{Var}(\bar{\xi_{T}})=\sigma^{2}_{\xi}/T$.
This shows that our $O(T^{-1})$ dual convergence rate is indeed optimal.

Note that our Proposition 2 holds uniformly for all $d^{\prime}\in\Omega_{d}$.
Denote the optimal solutions to problem (2.7) and (2.8), given a certain
$d^{\prime}$, by $\boldsymbol{\lambda}_{T}^{*}(d^{\prime})$ and
$\boldsymbol{\lambda}^{*}(d^{\prime})$, respectively. Then, we actually have

$\displaystyle\mathbb{E}\sup_{d^{\prime}\in\Omega_{d}}\left\lVert\boldsymbol{\lambda}^{*}_{T}(d^{\prime})-\boldsymbol{\lambda}^{*}(d^{\prime})\right\rVert^{2}_{2}\leq
C_{1}\cdot\frac{1}{T}$ (3.6)

Bound (3.6) plays a critical role in our regret analysis since the re-solving
strategy of our adaptive algorithm framework needs to frequently update the
resource constratins.

We then discuss $\epsilon$-optimal solutions of dual problem (2.7). Our
following finite-sample convergence result of $\epsilon$-optimal solution can
be viewed as a non-parametric version of SAA convergence developed by large
deviation theory (Ruszczyński and Shapiro,, 2003). Notably, we only make
assumptions on the deterministic problem $D(\boldsymbol{\lambda},d)$, and our
result does not rely on restricted tail conditions such as the moment
generating function in Ruszczyński and Shapiro, (2003); Shapiro et al.,
(2009). Therefore our result allows more flexible distributions.

######  Theorem 2 (Convergence of dual approximate solution).

Under Assumptions 1-3, suppose $\boldsymbol{\lambda}_{T}^{\epsilon}$ is an
$\epsilon$-optimal solution that satisfies
$\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{*},d)\leq\epsilon$.
Then we have the following convergence of $\epsilon$-optimal solution:

$\displaystyle\mathbb{E}\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\leq\frac{C_{1}}{T}+\frac{4\epsilon}{\underline{\mathcal{L}}_{D}}$

###### Proof.

Recall that, by Proposition 2, convex function $\bar{D}_{T}$ is larger that a
quadratic function in a neighborhood of $\boldsymbol{\lambda}^{*}$ with a high
probability claimed there. Then, for any $\varepsilon$ satisfying
$\epsilon<4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$, with the same
high probability, the $\epsilon$-optimal solution must belong to
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$, because, for all the points in
the border
$\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}=4H\varepsilon$,
we already have
$\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq
4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$. Then, with the same high
probability, it follows that

$\displaystyle\epsilon\geq\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert\boldsymbol{\lambda}_{T}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-\underline{\mathcal{L}}_{D}H\varepsilon\left\lVert\boldsymbol{\lambda}_{T}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2},$

which suggests that
$\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq\left\lVert\boldsymbol{\lambda}_{T}^{\prime}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
H\varepsilon+\big{(}H^{2}\varepsilon^{2}+2\epsilon/\underline{\mathcal{L}}_{D}\big{)}^{1/2}$.

Still, applying the tail expectation formula, we get

$\displaystyle\mathbb{E}(\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2})$
$\displaystyle=4H^{2}\int_{0}^{\frac{\epsilon}{H^{2}\underline{\mathcal{L}}_{D}}}\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq
2H\sqrt{z})dz+4H^{2}\int_{\frac{\epsilon}{H^{2}\underline{\mathcal{L}}_{D}}}^{\infty}\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq
2H\sqrt{z})dz$
$\displaystyle\leq\frac{4\epsilon}{\underline{\mathcal{L}}_{D}}+4H^{2}\int_{\frac{\epsilon}{H^{2}\underline{\mathcal{L}}_{D}}}^{\infty}\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq
2H\sqrt{z})dz.$

Let
$2H\sqrt{z}=H\varepsilon+\sqrt{H^{2}\varepsilon^{2}+\frac{2\epsilon}{\underline{\mathcal{L}}_{D}}}$.
When $z>\frac{\epsilon}{H^{2}\underline{\mathcal{L}}_{D}}$, we have
$\epsilon<4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$, thus
$\mathop{{}\mathbb{P}}(\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq
2H\sqrt{z})$ can be bounded by
$4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}})+2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{T\varepsilon^{2}}{2})$.
Also when
$2H\sqrt{z}=H\varepsilon+\sqrt{H^{2}\varepsilon^{2}+\frac{2\epsilon}{\underline{\mathcal{L}}_{D}}}$,
we have $\varepsilon^{2}\geq
z-\frac{\epsilon}{H^{2}\underline{\mathcal{L}}_{D}}$. By the integral of $z$,
we get the second part of the bound. ∎

Theorem 2 explains how the approximation of dual solutions affects the dual
convergence. The accuracy remains valid as we directly optimize the
deterministic dual function $D(\boldsymbol{\lambda},d)$. Moreover, this
theorem reveals that even if the empirical dual function
$\bar{D}_{T}(\boldsymbol{\lambda},d)$ is not strongly convex or smooth, the
dual convergence of approximate solution also holds as long as we choose an
appropriate accuracy. We can further show that this property is preserved with
a slightly different accuracy if we run stochastic optimization algorithms on
$\bar{D}_{T}$. We describe the convergence of stochastic approximate solution
in the following corollary:

######  Corollary 1 (Convergence of stochastic dual approximate solution).

Under Assumptions 1-3, suppose $\boldsymbol{\lambda}_{T}^{\epsilon}$ is a
stochastic $\epsilon$-optimal solution generated by stochastic optimization
algorithm $\mathcal{B}$ that satisfies

$\mathbb{E}_{\mathcal{B}}\left[\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{*},d)\middle|\bar{D}_{T}\right]\leq\epsilon$

for any given $\bar{D}_{T}$. Then we have the following convergence of the
stochastic $\epsilon$-optimal solution:

$\displaystyle\mathbb{E}\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\leq\frac{12C_{1}}{T}+3\cdot
2^{\frac{4}{3}}\left(m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)\right)^{\frac{1}{3}}/\underline{\mathcal{L}}_{D}^{\frac{2}{3}}\cdot\epsilon^{\frac{2}{3}},$

where the expectation is taken with respect to $\mathcal{B}$ and
$\mathcal{P}$.

Corollary 1 points out that the impact of stochastic optimization on the dual
convergence is limited, and the order of dual convergence can still be
controlled by $\epsilon$. Compared to Theorem 2, the smaller order
$\epsilon^{\frac{2}{3}}$ could be viewed as the accuracy loss because of
randomness. Even if we do not assume $\bar{D}_{T}$ to be strongly convex, the
difference between stochastic solutions and the deterministic one
$\mathbb{E}\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}_{T}^{*}\right\rVert_{2}^{2}$
is still under control just as we optimize a strongly convex function. This
inspires us to apply the stochastic approximate solutions to the re-solving
heuristic because, in many contexts, the benefits of stochastic algorithms
greatly outweigh the lower order of convergence $\epsilon^{\frac{2}{3}}$. With
the theory of dual convergence, we are ready to describe our dual-based
algorithm framework for online allocation.

##  4 Algorithm Framework

Our algorithm extends the linear adaptive re-solving strategy in Li and Ye,
(2021) to convex objective functions. The key idea is similar to the frequent
re-solving strategy in network revenue management (e.g., Jasin and Kumar,
(2012); Bumpensanti and Wang, (2020)) in spirit. We keep re-solving dual
problems with updated average remaining capacity inspired by the budget-ratio
policy (Arlotto and Gurvich,, 2019). Compared to the re-solving strategy in
network revenue management, we also need to keep updating the constraints and
re-solving the associated optimization programs. But the difference is that
our strategy is dual-based, and the size of our optimization problems grows
with time. Fortunately, the optimization in our algorithm can be easier as we
only need approximate solutions. The resource control in our algorithm is
handled more carefully when compared with the simple dual mirror descent. We
show that, non-adaptive policies are too greedy and can’t wisely keep the
remaining budget balanced in the long run. It is noteworthy that the idea of
budget-ratio policy (Arlotto and Gurvich,, 2019) featuring average remaining
capacity update has actually been implicitly conceived in the frequent re-
solving heuristic (Jasin and Kumar,, 2012; Wu et al.,, 2015). If we rescale
the variables in the frequent re-solving heuristic in Jasin and Kumar, (2012)
by the remaining time, we get a very similar constraint update strategy in
Bumpensanti and Wang, (2020).

Our dual-based online allocation algorithm is in line with other dual-based
online algorithms in spirit: we keep maintaining a dual variable
$\boldsymbol{\lambda}_{t}$ and every time when a request comes, we instantly
give a response based on the dual variable and the request just received. We
choose the primal action $x_{t}$, given the dual variable
$\boldsymbol{\lambda}$, by:

$\displaystyle\tilde{x}_{t}(\boldsymbol{\lambda})$
$\displaystyle:=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda+\mu)^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda+\mu)),$

and the primal variable $a$ is set by

$\tilde{a}(\mu):=\mathop{\arg\max}_{a\in\mathcal{Z}}\\{r(a)+\mu^{\top}a\\}=-\nabla
r^{*}(-\mu).$

Note that the primal solution $a$ may not explicitly affect our action
$x_{t}$, but it is helpful for our theoretical analysis of dual-based policies
and for algorithm implementation.

We outline our dual-based and history-dependent algorithm framework in
Algorithm 1. The algorithm updates dual variables by solving a $t$-sample SAA
as shown in equation (4.1). Each $\boldsymbol{\lambda}_{t}$ is a
$\epsilon_{t}$-optimal solution of the $t$-sample SAA with adaptive resources
constraints $d_{t}$. We emphasize that two ingredients in our algorithm
framework are crucial to guarantee an $O(\log T)$ regret: (1) the adaptive
update of resource constraints $d_{t}$; (2) the careful choice of accuracy
$\epsilon_{t}$ for approximate dual solutions. Without the adaptive update of
$d_{t}$, the worst-case regret will never be optimal for some extreme cases
(see Section 5 for more discussion). The dual solution accuracy can be set as
either increasing $\epsilon_{t}=\Theta(t^{-1})$ or decreasing
$\epsilon_{t}=\Theta((T-t)^{-1})$ (or $\epsilon_{t}=\Theta(t^{-3/2})$,
$\epsilon_{t}=\Theta((T-t)^{-3/2})$ for stochastic optimization algorithms).
Approximate solutions help significantly alleviate the total computational
cost. Our algorithm is history-dependent, meaning that we exploit all the
information we have collected up to time $t$. This is the essence of our
adaptive strategy. This history-dependent policy makes our algorithm learn
more efficiently compared with other dual-based algorithms that do not learn
from history (Devanur et al.,, 2019; Balseiro et al.,, 2022), at the cost of
acceptable extra computation. As is common in the literature on dual-based
online algorithms, we assume that both the conjugate $f_{t}^{\ast}$ and
corresponding primal variable $\tilde{x}_{t}$ are easily attainable.

Algorithm 1 History-based resolving algorithm framework

0: regularizer $r$, iteration number $T$, start point
$\boldsymbol{\lambda}_{0}:={\bf 0}$, and initial resource $B_{0}:=dT$.

for all $t=1,T$ do

Receive $(f_{t},b_{t})\sim\mathcal{P}$.

Calculate
$\displaystyle\tilde{x}_{t}:=\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})$
$\displaystyle:=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda_{t-1}+\mu_{t-1})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda_{t-1}+\mu_{t-1})).$

Select $x_{t}:=\begin{cases}\tilde{x}_{t}&\text{ if }B_{t-1}\geq b_{t}x_{t}\\\
0&\text{ otherwise }\end{cases}$

Update remaining resources: $B_{t}:=B_{t-1}-b_{t}x_{t}$

Update average remaining resources: $d_{t}:=\frac{B_{t}}{T-t}$

Update dual variable $\boldsymbol{\lambda}_{t}$ via solving the following dual
problem by any approximation algorithm $\mathcal{B}_{t}$ with accuracy
$\epsilon_{t}$:
$\min_{\boldsymbol{\lambda}\in\Omega_{\lambda}\times\Omega_{\mu}}\left\\{\bar{D}_{t}(\boldsymbol{\lambda},d_{t}):=\frac{1}{t}\sum^{t}_{j=1}f_{j}^{*}(b_{j}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d_{t}^{\top}\lambda\right\\}$
(4.1)

end for

Our algorithm framework is free of optimizer, that is, we can select any
optimizer to get the $\epsilon_{t}$-optimal solution to dual program (4.1).
Since the dual problem $\bar{D}_{t}(\boldsymbol{\lambda},d_{t})$ is generally
convex with respect to $\boldsymbol{\lambda}$, one favourable choice is
stochastic gradient descent that is first order (recall that we assume the
gradient of the dual problem, i.e., the primal variable, is easily attainable)
and the computational complexity can be free of size $t$. This makes it
possible to deal with large scale dual optimization when the total running
time $T$ is large.

More specifically, if the dual optimizer is selected as stochastic gradient
descent where the accuracy is specified by $\epsilon_{t}:=ct^{-3/2}$, we end
up with the following Algorithm 2 by our algorithm framework. Basically, it
requires computing $O(t^{3})$ stochastic gradients at time $t$. Moreover, if
the dual problem $\bar{D}_{t}$ is further strongly convex or smooth, we can
reduce the computational cost to $O(t)$ for each time $t$. See Section 6.1 for
more discussions on the case of strongly convex objectives. In Section 5, we
demonstrate that any optimization algorithm $\mathcal{B}_{t}$ that achieves
the rate of dual convergence
$\mathbb{E}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert_{2}^{2}=O(t^{-1})$
or $O\big{(}(T-t)^{-1}\big{)}$ suffices to guarantee the optimal logarithmic
regret in the end.

Algorithm 2 Resolving with Stochastic Gradient Descent

0: regularizer $r$, iteration number $T$, start point
$\boldsymbol{\lambda}_{0}:={\bf 0}$, and initial resource $B_{0}:=dT$.

for all $t=1,\dots,T$ do

Receive $(f_{t},b_{t})\sim\mathcal{P}$.

Calculate
$\displaystyle\tilde{x}_{t}:=\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})$
$\displaystyle:=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda_{t-1}+\mu_{t-1})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda_{t-1}+\mu_{t-1})).$

Select $x_{t}:=\begin{cases}\tilde{x}_{t}&\text{ if }B_{t-1}\geq b_{t}x_{t}\\\
0&\text{ otherwise }\end{cases}$

Update remaining resources: $B_{t}:=B_{t-1}-b_{t}x_{t}$

Update average remaining resources: $d_{t}:=\frac{B_{t}}{T-t}$

Set $R:=\sqrt{m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)}$,
$L:=\sqrt{m\bar{d}^{2}+2n\bar{b}^{2}D^{2}+nG^{2}}$, $K:=t^{3}$, and
$\eta_{t}:=\frac{\sqrt{2}R}{L\sqrt{K}}$. Define
$\boldsymbol{\lambda}_{t}^{0}:=\boldsymbol{\lambda}_{t-1}$

for all $k=1,\dots,K$ do

Randomly pick $\zeta$ from $[t]:=\left\\{1,\dots,t\right\\}$ with uniform
distribution.

Calculate the stochastic gradient  $\nabla
D_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1}):=\left[\begin{array}[]{c}-b_{\zeta}\tilde{x}_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})+d_{t}\\\
-b_{\zeta}\tilde{x}_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})+\tilde{a}(\boldsymbol{\lambda}_{t}^{k-1})\end{array}\right]$
(4.2)

Update dual variable via stochastic gradient descent:
$\boldsymbol{\lambda}_{t}^{k}:=\mathop{\rm
arg\min}_{\boldsymbol{\lambda}\in\Omega_{\lambda}\times\Omega_{\mu}}\left\\{\langle\boldsymbol{\lambda},\nabla
D_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})\rangle+\frac{1}{2\eta_{t}}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}_{t}^{k-1}\right\rVert^{2}_{2}\right\\}$
(4.3)

end for

Update dual variable by averaging:
$\boldsymbol{\lambda}_{t}:=\frac{\sum_{k=1}^{K}\boldsymbol{\lambda}_{t}^{k}}{K}$

end for

##  5 Regret Analysis

###  5.1 Regret upper bound

In this section, we apply dual convergence established in Section 3 to derive
an upper bound of regret. The result is valid for our algorithm framework
Algorithm 1 with any dual optimizers. Without loss of generality, we focus on
stochastic optimizers $\mathcal{B}_{t}$, which are independent of future
arrivals $\left\\{(f_{j},b_{j})\right\\}_{j\geq t+1}$. As long as
$\mathcal{B}_{t}$ delivers reasonably accurate dual solutions
$\boldsymbol{\lambda}_{t}$, based on past history
$\mathcal{H}_{t-1}=\left\\{f_{j},b_{j},x_{j}\right\\}_{j=1}^{t-1}$, new
arrival $(f_{t},b_{t})$ and updated constraint $d_{t}\in\Omega_{d}$, our
adaptive framework Algorithm 1 achieves a logarithmic-order regret. Precisely,
the accuracy of dual solutions shall satisfy the following condition.

######  Condition 1.

(Accuracy of dual solutions). Suppose the updated constraints
$\left\\{d_{j}\middle|1\leq j\leq t\right\\}\subseteq\Omega_{d}$. We say the
algorithm $\\{\mathcal{B}_{t}\\}_{t\geq 1}$ satisfies dual convergence
condition 1 if

$\\\
\mathbb{E}_{\mathcal{B},\mathcal{P}}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert^{2}\leq
C_{2}\frac{1}{t+1},\text{ or }\ \
\mathbb{E}_{\mathcal{B},\mathcal{P}}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert^{2}\leq
C_{2}(\frac{1}{t+1}+\frac{1}{T-t})$ (5.1)

for some constant $C_{2}>0$. The expectation is taken with respect to all the
$\\{\mathcal{B}_{t}\\}_{t\geq 1}$ and $\mathcal{P}$.

Recall that the dual convergence established in Section 3 holds uniformly for
any $d\in\Omega_{d}$. Therefore, any dual optimizers ensuring corresponding
dual solution error $\epsilon_{t}=\Theta(t^{-1})$ or
$\epsilon_{t}=\Theta\big{(}(T-t)^{-1}\big{)}$ (
$\epsilon_{t}=\Theta(t^{-3/2})$ or $\epsilon_{t}=\Theta((T-t)^{-3/2}$ for
stochastic dual optimizers) satisfy Condition 1. If Condition 1 holds, our
adaptive framework Algorithm 1 achieves the following optimal regret.

######  Theorem 3.

Under Assumptions 1-4, if the algorithm $\\{\mathcal{B}_{t}\\}_{t\geq 1}$ we
choose satisfies Condition 1, then the regret of Algorithm 1 has the following
upper bound:

$\text{Regret}(A)\leq\mathring{C}\cdot\log T$

for some constant $\mathring{C}>0$ depending on the values in Assumptions 1-4.

Clearly, exact solutions to the SAA program (4.1) is a theoretically valid
candidate for $\\{\mathcal{B}_{t}\\}_{t\geq 1}$, which is actually the classic
idea of re-solving heuristic. However, the computational cost can be high if
we want to find an exact solution. Fortunately, by Theorem 3, it suffices to
approximately solve SAA program (4.1) as long as the accuracy meets conditions
(5.1). We shall show in Section 5.2 that the rate $O(\log T)$ is optimal.

We now briefly sketch the proof of Theorem 3. The proof begins with the
decomposition of regret, which shows that regret can be controlled by the
cumulative error of dual solutions
$\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})$ and by
$\mathbb{E}[T-\tau]$ for some stopping time $\tau$. Recall, given a certain
distribution $\mathcal{P}$, the definition of regret:

$\operatorname{Regret}\left(A\middle|\mathcal{P}\right)=R^{*}(\mathcal{P})-R\left(A\middle|\mathcal{P}\right),$

where $R^{*}(\mathcal{P})$ and $R\left(A\middle|\mathcal{P}\right)$ are
defined in (2.3) and (2.2), respectively. To upper bound the regret, we need
an upper bound of offline maximum reward. To that end, we define

$g(\boldsymbol{\lambda}):=\mathbb{E}\big{[}f_{t}(\tilde{x}_{t}(\boldsymbol{\lambda}))+r(\tilde{a}(\mu))+(\tilde{a}(\mu)-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))^{\top}\mu^{*}+(d-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))^{\top}\lambda^{*}\big{]}.$

Here $g(\boldsymbol{\lambda})$ serves as an upper bound for
$R^{*}(\mathcal{P})$, characterized by the following lemma.

######  Lemma 3.

The offline maximum reward $R^{*}(\mathcal{P})$ satisfies
$R^{*}(\mathcal{P})\leq T\cdot g(\boldsymbol{\lambda}^{*}).$

###### Proof.

Recall the Lagrangian of program (2.5). By duality, we have

$\displaystyle R^{*}(\mathcal{P})$
$\displaystyle:=\mathbb{E}_{\mathcal{P}}\left[\max_{x_{t}\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}),\ s.t.\ \sum_{t=1}^{T}b_{t}x_{t}\preceq
dT\right]$
$\displaystyle\leq\mathbb{E}\sum_{t=1}^{T}\left[f_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})+r(\tilde{a}(\mu^{*}))+(\tilde{a}(\mu^{*})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}))^{\top}\mu^{*}+(d-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}))^{\top}\lambda^{*}\right]$
$\displaystyle=T\cdot g(\boldsymbol{\lambda}^{*})$

∎

Since $f_{t}$ and $r(a)$ have trivial upper bounds, we get
$R^{*}(\mathcal{P})\leq T(\bar{f}+\bar{r})$. Thus, for a proper stopping time
$\tau$, we have

$R^{*}(\mathcal{P})\leq\mathbb{E}\left[\tau
g(\boldsymbol{\lambda}^{*})+(T-\tau)(\bar{f}+\bar{r})\right].$ (5.2)

Note that our strategy of dealing the non-separable regularizer is to
introduce an additional (i.e., variable split) primal variable $a$. While its
actual value does not directly affect our algorithm framework, it is vital for
our theoretical investigation. To this end, denote

$a_{t}:=\underset{a\in\mathcal{Z}}{\arg\max}\
\big{\\{}r(a)+\mu_{t}^{\top}a\big{\\}}$

the value of $a$ at $t$-th iteration. By Fenchel conjugate, we actually have
$a_{T}=-\nabla r^{\ast}(-\mu_{T})$. The second impact of variable splitting is
an equality constraint between $a_{T}$ and $T^{-1}\sum_{t=1}^{T}b_{t}x_{t}$.
It turns out that their difference can be measured by the difference between
$\mu_{T}$ and the following quantity

$\displaystyle\hat{\mu}_{T}:=\arg\max\limits_{\mu}\left\\{r^{*}(-\mu)-\mu^{\top}\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}\right\\}.$
(5.3)

The above maximization is taken without constraints, implying that
$T^{-1}\sum_{t=1}^{T}b_{t}x_{t}=-\nabla r^{\ast}(-\hat{\mu}_{T})$. Due to the
property of $\nabla r^{\ast}$ (Assumption 2.3), we have

$\Big{\|}a_{T}-T^{-1}\sum_{t=1}^{T}b_{t}x_{t}\Big{\|}_{2}\leq\bar{\mathcal{L}}_{r}\|\mu_{T}-\hat{\mu}_{T}\|_{2}.$

We are in position to describe the following regret decomposition for a
general stopping time.

######  Proposition 3.

Under Assumptions 1-3, for a proper stopping time $\tau$ ensuring that the
resource is not depleted before $t\leq\tau$, the regret of our dual-based
adaptive framework Algorithm 1 admits the following upper bound:

$\displaystyle\operatorname{Regret}\left(A\middle|\mathcal{P}\right)\leq$
$\displaystyle\underbrace{\mathbb{E}\left[\sum_{t=1}^{\tau}g(\boldsymbol{\lambda}^{*})-g(\boldsymbol{\lambda}_{t})\right]}_{\textsf{R.1}}+\underbrace{\mathbb{E}\left[2(\bar{f}+\bar{r}+C_{3})(T-\tau)+\left\langle\lambda^{*},\sum_{t=1}^{\tau}(d-b_{t}x_{t})\right\rangle\right]}_{\textsf{R.2}}$
(5.4)
$\displaystyle+\underbrace{\mathbb{E}\left[\left\langle\mu^{*}-\hat{\mu}_{T},\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rangle\right]}_{\textsf{R.3}},$

where $C_{3}:=\sqrt{mn}GD\bar{b}$.

It remains to bound the three parts in Proposition 3, respectively. The key
point is to carefully choose a stopping time that (1) avoids early stopping;
(2) enforces the total resource constraints. The first term R.1 is contributed
by the algorithm before stopping time, which can be controlled by the
cumulative dual error
$\mathbb{E}\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}$.
The second term R.2 concerns the lost rewards due to resource depletion, which
can be controlled by $\mathbb{E}(T-\tau)$. To achieve an $O(\log T)$ regret,
the stopping time shall be carefully designed so that
$\mathbb{E}(T-\tau)=O(\log T)$. The term R.3 is contributed mainly by the
variable splitting, which can be controlled jointly by the cumulative dual
error and $\mathbb{E}(T-\tau)$. The three terms capture different sources of
regret induced by our adaptive framework Algorithm 1. It turns out that we
shall bound
$\mathbb{E}\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}$
and $\mathbb{E}(T-\tau)$, for which a smart design of stopping time becomes
crucial.

Our design of stopping time is inspired by the budget-ratio stopping time
introduced and investigated by Arlotto and Gurvich, (2019) and Li and Ye,
(2021) for online linear allocation problems. At the core of this design is a
smart strategy that ensures, as the updated constraint $d_{t}$ varies within a
region $\mathcal{D}\subset\Omega_{d}$, the binding and non-binding dimensions
of the problem $D(\boldsymbol{\lambda},d_{t})$ remain unchanged. The region
$\mathcal{D}$ is usually a small neighbour of the original budget $d$. The
following lemma dictates that such a region $\mathcal{D}$ exists for our
regularized online convex allocation problem. Recall that
$\boldsymbol{\lambda}^{\ast}(d^{\prime})$ denotes the optimal dual solution to
$D(\boldsymbol{\lambda},d^{\prime})$, and $I_{\textsf{B}}$ and
$I_{\textsf{NB}}$ stand for the binding and non-binding dimension of
$D(\boldsymbol{\lambda},d)$.

######  Lemma 4.

Under Assumptions 1-3, there exists a constant $\delta_{d}>0$ such that for
any $d^{\prime}\in\Omega_{d}$, if

$-\delta_{d}\leq d_{i}^{\prime}-d_{i}\leq\delta_{d}\text{ if }i\in
I_{\textsf{B}}\text{, and }d^{\prime}_{i}-d_{i}\geq-\delta_{d}\text{ if }i\in
I_{\textsf{NB}},$

the dual problems $D(\boldsymbol{\lambda},d^{\prime})$ and
$D(\boldsymbol{\lambda},d)$ share the same binding and non-binding dimensions.

For technical convenience, we assume that, for each non-binding dimensions
$i\in I_{\textsf{NB}}$, the updated constraint $d_{it}$ never exceeds the
threshold $\bar{d}$ (the uniform bound defined in Assumption 1) at all
iterations. This is a mid assumption both for theory and in practice. Indeed,
if $d_{it}$ is larger than the $\bar{d}$, this means that the constraint
$d_{it}$ is very loose so that its impact to the optimization problem is
negligible. In this case, such a constraint can essentially be discarded.

With Lemma 4, we define the required region where binding and non-binding
dimensions remain unchanged during iterations by

$\mathcal{D}:=\left\\{d^{\prime}\in\Omega_{d}\middle|-\delta_{d}\leq
d_{i}^{\prime}-d_{i}\leq\delta_{d}\text{ if }i\in I_{\textsf{B}}\text{, and
}d^{\prime}_{i}-d_{i}\geq-\delta_{d}\text{ if }i\in I_{\textsf{NB}}\right\\}.$

We thereby design the following stopping time.

$\tau:=\min\limits_{t\in[T]}\left\\{T-\left\lceil\frac{\sqrt{n}D\bar{b}}{\underline{d}}\right\rceil\right\\}\bigcup\big{\\{}t|d_{t}\notin\mathcal{D}\big{\\}}.$
(5.5)

Additionally, this stopping time also guarantees that resource depletion will
not happen before $\tau$. We show that $\tau$ rules out early-stopping so that
$\mathbb{E}[T-\tau]=O(\log T)$. The following lemmas bound the cumulative dual
error and $\mathbb{E}[T-\tau]$.

######  Lemma 5.

Under Assumptions 1-4, Algorithm 1 with selected dual optimizer
$\\{\mathcal{B}_{t}\\}_{t\geq 1}$ satisfying Condition 1 achieves

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}\right]\leq
O(\log T)$ (5.6)

######  Lemma 6.

Under Assumptions 1-4, the stopping time (5.5) of Algorithm 1 with selected
dual optimizer $\\{\mathcal{B}_{t}\\}_{t\geq 1}$ satisfying Condition 1 has

$\displaystyle\mathbb{E}\left(T-\tau\right)\leq O(\log T)$ (5.7)

These two lemmas play a key role in our regret analysis. They are proved by
investigating the dynamic behavior of constraints $d_{it}$ for binding and
non-binding dimensions, respectively. For binding dimensions, we investigate
the recurrence relation of $d_{it}$ by leveraging the binding relations. For
the non-binding dimensions, we exploit the $\delta_{d}$ gap between $d_{it}$
and average resource consumption. Equipped with Lemma 5 and 6, we now continue
sketching the proof of Theorem 3. By Proposition 3, it suffices to bound the
three terms there.

###### Proof of Theorem 3.

The proof continues from Proposition 3.

Step 1: bounding R.1. By Fenchel conjugate, we re-write the bridging function
$g(\boldsymbol{\lambda})$ by

$\displaystyle g(\boldsymbol{\lambda})=$
$\displaystyle\mathbb{E}\left[f_{t}(\tilde{x}_{t}(\boldsymbol{\lambda}))+r(\tilde{a}(\mu))+(\tilde{a}(\mu)-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))^{\top}\mu^{*}+(d-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))^{\top}\lambda^{*}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[f^{*}_{t}(b_{t}^{\top}(\lambda+\mu))+r^{*}(-\mu)\right]+\mathbb{E}(\mu^{*}-\mu)^{\top}(\tilde{a}(\mu)-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))+\mathbb{E}(\lambda^{*}-\lambda)^{\top}(d-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}))$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[f^{*}_{t}(b_{t}^{\top}(\lambda+\mu))+r^{*}(-\mu)\right]-\mathbb{E}\left[\nabla
f_{t}^{*}(b_{t}^{\top}(\lambda+\mu))^{\top}b_{t}^{\top}(\lambda+\mu-\lambda^{*}-\mu^{*})\right.$
$\displaystyle\left.-\nabla
r^{*}(-\mu)^{\top}(\mu-\mu^{*})+d^{\top}(\lambda-\lambda^{*})\right]$
$\displaystyle=$ $\displaystyle D(\boldsymbol{\lambda},d)-\nabla
D(\boldsymbol{\lambda},d)^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})$

By Assumption 2 and 3, we get

$\displaystyle g(\boldsymbol{\lambda}^{*})-g(\boldsymbol{\lambda})=$
$\displaystyle
D(\boldsymbol{\lambda}^{*},d)-D(\boldsymbol{\lambda},d)+\left\langle\nabla
D(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle$
$\displaystyle+\left\langle\nabla D(\boldsymbol{\lambda},d)-\nabla
D(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle\leq\left(2\bar{\mathcal{L}}_{D}-\underline{\mathcal{L}}_{D}\right)\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}.$

Then Lemma 5 gives rise to the following bound.

$\mathbb{E}\left[\sum_{t=1}^{\tau}g(\boldsymbol{\lambda}^{*})-g(\boldsymbol{\lambda}_{t-1})\right]\leq
O(\log T).$

Step 2: bounding R.2. This term can be controlled by the definition of
stopping time and Lemma 6.

$\displaystyle\mathbb{E}$
$\displaystyle\left[2(\bar{f}+\bar{r}+C_{3})(T-\tau)+\left\langle\lambda^{*},\sum_{t=1}^{\tau}(d-b_{t}x_{t})\right\rangle\right]$
$\displaystyle=\mathbb{E}\left[2(\bar{f}+\bar{r}+C_{3})(T-\tau)+\left\langle\lambda^{*},d_{\tau}(T-\tau)-d(T-\tau)\right\rangle\right]$
$\displaystyle\leq\mathbb{E}\left[2(\bar{f}+2\bar{r}+C_{3})(T-\tau)+\sum_{i\in
I_{\textsf{B}}}\lambda^{*}_{i}(d_{i}+\delta_{d})(T-\tau)\right]$
$\displaystyle\leq(2\bar{f}+2\bar{r}+2C_{3}+(\left\lVert
d\right\rVert+\sqrt{m}\delta_{d})\frac{2(\bar{f}+\bar{r})}{\underline{d}})\mathbb{E}(T-\tau)=O(\log
T)$

Step 3: bounding R.3. This term requires the most effort. It concerns the
combined effects of variable splitting and complementary slackness. The
following lemma is important for bounding this term.

######  Lemma 7.

Under Assumptions 1-4, Algorithm 1 with selected dual optimizer
$\\{\mathcal{B}_{t}\\}_{t\geq 1}$ satisfying Condition 1 and stopping time
(5.5) ensures

$\displaystyle\mathbb{E}$
$\displaystyle\left\lVert\hat{\mu}_{T}-\mu^{*}\right\rVert^{2}_{2}\leq
O(\frac{\log T}{T}),\text{ and }\
\mathbb{E}\left\lVert\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rVert^{2}_{2}\leq
O(T\log T).$

The proof Lemma 7 exploits the local smoothness of $r$ and $\tilde{x}_{t}$
with the help of the optimality of $\mu^{*}$, i.e.,
$\tilde{a}(\mu^{*})=\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}))$ .
By Cauchy–Schwarz inequality, we get

$\displaystyle\mathbb{E}\left[\left\langle\mu^{*}-\hat{\mu}_{T},\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rangle\right]\leq$
$\displaystyle\bigg{(}\mathbb{E}\left\lVert\hat{\mu}_{T}-\mu^{*}\right\rVert^{2}_{2}\mathbb{E}\left\lVert\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rVert^{2}_{2}\bigg{)}^{1/2}.$
(5.8)

Thus R.3 can be controlled by $\log T$. The proof is concluded.

∎

###  5.2 Lower bound and algorithms without constraint update

Bray, (2019) and Li and Ye, (2021) have established the logarithmic regret
lower bound for online multi-secretary problems and online linear programming,
respectively. To show the optimality of Theorem 3, we establish a matching
lower bound in this section. We note that there always exists a regularizer
function that makes our regularized online allocation problem more challenging
than the non-regularized one. For example, consider that $f_{t}(x)$ and $r$
are both monotonic increasing and the hindsight optimal strategy
$\\{x_{t}^{\prime}\\}_{t=1}^{T}$ that optimizes
$\max_{x_{t}\in\mathcal{X}}\big{\\{}\sum_{t=1}^{T}f_{t}(x_{t})\text{ s.t.
}\sum_{t=1}^{T}b_{t}x_{t}\leq dT\big{\\}}$, it holds that
$\sum_{t=1}^{T}b_{t}x_{t}^{\prime}=dT$ and thus
$r(T^{-1}\sum_{t=1}^{T}b_{t}x_{t}^{\prime})\geq
r(T^{-1}\cdot\sum_{t=1}^{T}b_{t}x_{t})$ for any other $\\{x_{t}\\}_{t=1}^{T}$.
This renders the regret lower bound of regularized problem larger than that of
non-regularized one. Therefore, for the regret lower bound, we only focus on
the non-regularized problems.

######  Theorem 4 (Regret lower bound).

For any dual-based algorithm $A$, we have the worst-case regret lower bound:

$\displaystyle\operatorname{Regret}(A)\geq\Omega(\log T).$

Theorem 4 justifies the optimality of our algorithm in terms of worst-case
regret. The logarithmic regret also matches that of classic unrestricted
online convex optimization (Hazan et al.,, 2007). Nevertheless, one may wonder
how important the adaptive constraint update is in our adaptive framework
Algorithm 1 and whether it is possible to achieve an optimal regret without
adaptive constraints update. Here we only present a negative answer partially
for two specific but renowned algorithms. For concreteness, we investigate two
similar algorithms (Algorithms 3 and 4) without constraints update that have
been discussed in the literature for online dual gradient (mirror descent
(Balseiro et al.,, 2021, 2022) and dual SAA (Li and Ye,, 2021).

Algorithm 3 Online dual gradient (mirror) descent without constraint update

0: regularizer $r$, iteration number $T$, step size
$\eta_{t}:=\Theta(\frac{1}{t})$ for $t\in[T]$, start point
$\boldsymbol{\lambda}_{0}:={\bf 0}$, and initial resource $B_{0}:=dT$.

for all $t=1,T$ do

Receive $(f_{t},b_{t})\sim\mathcal{P}$.

Calculate  $\displaystyle\tilde{x}_{t}$
$\displaystyle:=\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1}):=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda_{t-1}+\mu_{t-1})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda_{t-1}+\mu_{t-1}))$ $\displaystyle\tilde{a}_{t}$
$\displaystyle:=\mathop{\arg\max}_{a\in\mathcal{Z}}\\{r(a)+\mu_{t-1}^{\top}a\\}=-\nabla
r^{*}(-\mu_{t-1}).$

Select $x_{t}:=\begin{cases}\tilde{x}_{t}&\text{ if }B_{t-1}\geq b_{t}x_{t}\\\
0&\text{ otherwise }\end{cases}$

Update remaining resources: $B_{t}:=B_{t-1}-b_{t}x_{t}$

Calculate the stochastic gradient $\nabla
D_{t}(\boldsymbol{\lambda}_{t-1}):=\left[\begin{array}[]{c}-b_{t}\tilde{x}_{t}+d\\\
-b_{t}\tilde{x}_{t}+\tilde{a}_{t}\end{array}\right]$

Update dual variable via online gradient descent:
$\boldsymbol{\lambda}_{t}:=\mathop{\rm
arg\min}_{\boldsymbol{\lambda}\in\Omega_{\lambda}\times\Omega_{\mu}}\left\\{\langle\boldsymbol{\lambda},\nabla
D_{t}(\boldsymbol{\lambda}_{t-1})\rangle+\frac{1}{2\eta_{t}}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}_{t-1}\right\rVert^{2}_{2}\right\\}$

end for

Algorithm 4 Dual SAA without constraint update

0: regularizer $r$, iteration number $T$, start point
$\boldsymbol{\lambda}_{0}:={\bf 0}$, and initial resource $B_{0}:=dT$.

for all $t=1,T$ do

Receive $(f_{t},b_{t})\sim\mathcal{P}$.

Calculate
$\displaystyle\tilde{x}_{t}:=\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})$
$\displaystyle:=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda_{t-1}+\mu_{t-1})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda_{t-1}+\mu_{t-1})).$

Select $x_{t}:=\begin{cases}\tilde{x}_{t}&\text{ if }B_{t-1}\geq b_{t}x_{t}\\\
0&\text{ otherwise }\end{cases}$

Update remaining resources: $B_{t}:=B_{t-1}-b_{t}x_{t}$

Update dual variable via solving t-sample SAA:
$\boldsymbol{\lambda}_{t}:=\mathop{\rm
arg\min}_{\boldsymbol{\lambda}\in\Omega_{\lambda}\times\Omega_{\mu}}\left\\{\frac{1}{t}\sum^{t}_{j=1}f_{j}^{*}(b_{j}^{\top}(\mu+\lambda))+r^{*}(-\mu)+d^{\top}\lambda\right\\}$

end for

Algorithms 3 and 4 both feature the idea of approximating dual solutions,
i.e., iteratively updating $\boldsymbol{\lambda}_{t}$ to approach
$\boldsymbol{\lambda}^{*}$ by Stochastic Approximation (SA) or SAA. But the
implementation shows two different approaches. Algorithm 3 is not history-
dependent because it updates the dual variable using only the $t$-th sample,
while Algorithm 4 is history-dependent because it gathers all the information
up to time $t$ to update the dual variable. The following lemma establishes an
$\Omega(T^{1/2})$ regret lower bound for these two algorithms equipped with a
typical stopping time.

######  Theorem 5.

Under Assumptions 1-3, there exists a constant $c_{2}>0$ such that any dual-
based algorithm $A$ attempting to approximate $\boldsymbol{\lambda}^{*}$ with
$\mathbb{E}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
c_{2}D(t+1)^{-1/2}$ incurs a worst-case regret lower bound:

$\operatorname{Regret}(A)\geq\Omega(T^{1/2})$

We prove this theorem by constructing a one-dimensional strongly convex reward
and bound the regret by leveraging the probability estimation of a Binomial
distribution. Note that the lower bound can also be controlled by both dual
approximate error
$\mathbb{E}\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}$
and early stopping effect $\mathbb{E}(T-\tau)$. Here
$\boldsymbol{\lambda}^{\ast}$ is the deterministic dual solution when the
resource constraint is fixed at $d$. In sharp contrast, the dual solution
$\boldsymbol{\lambda}_{t}$ in our adaptive framework Algorithm 1 aims to
approximate $\boldsymbol{\lambda}^{\ast}(d_{t})$ where $d_{t}$ is the updated
constraint at time $t$. Intuitively, the rationale behind constraint update is
that, at time $t$, the decision should be made in consideration of the
remaining resources $d_{t}$ at hand instead of the initial resource $d$.

######  Remark 2.

Theorem 5 suggests that Algorithms 3 and 4 fail to reach the optimal regret
under our assumptions because they all seek to approximate a deterministic
$\boldsymbol{\lambda}^{*}$. In fact, even if we know the exact distribution
$\mathcal{P}$ and its optimal solution $\boldsymbol{\lambda}^{*}$, we are
still unable to make our dual-based algorithm optimal by just choosing
$\boldsymbol{\lambda}_{t}=\boldsymbol{\lambda}^{*}$. Theorem 5 gives a
rigorous evidence that our constraint-update algorithm outperforms other prior
ones without constraint update such as the online gradient decent studied by
Balseiro et al., (2021, 2022).

Finally, we remark that our theorem pushes forward the understanding of
adaptiveness for online algorithms to the dual-based ones. In Arlotto and
Gurvich, (2019), the authors established an $\Omega(\sqrt{T})$ regret lower
bound only for non-adaptive strategies (without adaptively updating the dual
solutions). However, our proof demonstrates that, even when the strategy is
adaptive, it might still not be sufficient to deliver an optimal regret if the
algorithm only focuses on dual updates but neglects the constraint update.
Actually, focusing on fixed constraints leads to a sub-optimal early stopping.

##  6 Applications

###  6.1 Strongly convex dual problems

We consider a special but practical setting, in which our empirical dual
problem $\bar{D}_{t}(\boldsymbol{\lambda},d_{t})$ in (4.1) is always
$\underline{\mathcal{L}}_{D}$-strongly convex. This assumption can be met if
$f_{t}^{*}$ and $r$ are almost-surely strongly convex. In this case, we only
need to do stochastic gradient descent for $O(t)$ times at time $t$ to make
our algorithm theoretically optimal. The detailed implementations are in
Algorithm 5.

Algorithm 5 Resolving with SGD for strongly convex dual objective

0: regularizer $r$, iteration number $T$, start point
$\boldsymbol{\lambda}_{0}:={\bf 0}$, and initial resource $B_{0}:=dT$.

for all $t=1,\dots,T$ do

Receive $(f_{t},b_{t})\sim\mathcal{P}$.

Calculate
$\displaystyle\tilde{x}_{t}:=\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})$
$\displaystyle:=\mathop{\arg\max}_{x\in\mathcal{X}}\\{f_{t}(x)-(\lambda_{t-1}+\mu_{t-1})^{\top}b_{t}x\\}=-\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda_{t-1}+\mu_{t-1})).$

Select $x_{t}:=\begin{cases}\tilde{x}_{t}&\text{ if }B_{t-1}\geq b_{t}x_{t}\\\
0&\text{ otherwise }\end{cases}$

Update remaining resources: $B_{t}:=B_{t-1}-b_{t}x_{t}$

Update average remaining resources: $d_{t}:=\frac{B_{t}}{T-t}$

Set $K:=t$, and $\eta_{k}:=\frac{\underline{\mathcal{L}}_{D}}{k}$. Define
$\boldsymbol{\lambda}_{t}^{0}:=\boldsymbol{\lambda}_{t-1}$

for all $k=1,\dots,K$ do

Randomly pick $\zeta$ from $[t]:=\left\\{1,\dots,t\right\\}$ with uniform
distribution.

Calculate the stochastic gradient $\nabla
D_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1}):=\left[\begin{array}[]{c}-b_{\zeta}\tilde{x}_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})+d_{t}\\\
-b_{\zeta}\tilde{x}_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})+\tilde{a}(\boldsymbol{\lambda}_{t}^{k-1})\end{array}\right]$

Update dual variable via stochastic gradient descent:
$\boldsymbol{\lambda}_{t}^{k}:=\mathop{\rm
arg\min}_{\boldsymbol{\lambda}\in\Omega_{\lambda}\times\Omega_{\mu}}\left\\{\langle\boldsymbol{\lambda},\nabla
D_{\zeta}(\boldsymbol{\lambda}_{t}^{k-1})\rangle+\frac{1}{2\eta_{k}}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}_{t}^{k-1}\right\rVert^{2}_{2}\right\\}$

end for

Update the dual variable by
$\boldsymbol{\lambda}_{t}:=\boldsymbol{\lambda}_{t}^{K}$

end for

Algorithm 5 satisfies Condition 1 but it does not rely on Corollary 1. Notice
that
$\mathbb{E}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert_{2}^{2}\leq
2\mathbb{E}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}_{t}(d_{t})\right\rVert_{2}^{2}+2\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}_{t}(d_{t})-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert_{2}^{2}$
where $\boldsymbol{\lambda}^{*}_{t}(d_{t})$ is the optimal solution to the
empirical dual problem $\bar{D}_{t}(\boldsymbol{\lambda},d_{t})$. The second
term
$\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}_{t}(d_{t})-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert_{2}^{2}$
represents the dual convergence and can be bounded by $O(t^{-1})$ by Theorem
1, while the first term accounts for the optimization error and can also be
bounded by $O(t^{-1})$ (see, Rakhlin et al., (2012)). If
$\bar{D}_{t}(\boldsymbol{\lambda},d_{t})$ is further smooth, we can also
ensure Condition 1 by running batch gradient descent for constant steps at
each time $t$ to get an $O\big{(}t^{-1}+(T-t)^{-1}\big{)}$ approximate
solution, which still requires computing gradients for $O(t)$ times at $t$-th
time.

###  6.2 Online linear programming

Our algorithm framework and theoretical results are also applicable to the
classical non-regularized online linear allocation problems, which finds
applications in online ad-auction (Buchbinder et al.,, 2007), network revenue
management (Jasin and Kumar,, 2012), multi-secretary problem (Kleinberg,,
2005) , etc. At time $t$, we make a decision
$x_{t}\in\mathcal{X}=\left[0,D\right]^{n}$ that returns a linear reward
$v_{t}$ and bears a random cost $b_{t}\in\mathbb{R}^{m\times n}$ per unit.
Online linear programming can be formalized as:

$\displaystyle\max_{x_{t}}\quad$
$\displaystyle\sum_{t=1}^{T}v_{t}^{\top}x_{t}$ s.t.
$\displaystyle\sum_{t=1}^{T}b_{t}x_{t}\preceq dT,\ d\in\mathbb{R}_{+}^{m}$
$\displaystyle x_{t}\in\left[0,D\right]^{n},\forall t\in[T].$

The empirical dual problem and its population version can be explicitly
written as

$\bar{D}_{T}(\lambda,d):=\frac{\sum_{t=1}^{T}\sum_{t=i}^{n}\left(v_{it}-b_{it}^{\top}\lambda\right)^{+}}{T}+d^{\top}\lambda,\text{
and }\
D(\lambda,d):=\mathbb{E}\sum_{t=i}^{n}\left(v_{it}-b_{it}^{\top}\lambda\right)^{+}+d^{\top}\lambda,$

which is in line with Li and Ye, (2021). Here the index $b_{it}$ means the
$i$-column of $b_{t}$. For a given dual variable $\lambda$, we make the primal
decision by $x_{it}:=D\mathbb{I}(v_{it}-b_{it}^{\top}\lambda>0)$ if the
resource constraints are not violated. Then, under the same locally strongly
convex and non-degeneracy assumptions, we can make optimal decisions by
choosing $\lambda_{t}$ as the $O(t^{-1})$-optimal solution (or
$O(t^{-3/2})$-optimal solution for stochastic optimizer) of
$\bar{D}_{t}(\lambda,d_{t})$. Towards that end, an $O(\log T)$ regret is
attainable, which improves prior result (Li and Ye,, 2021) .

###  6.3 Online welfare maximization with costs

Our algorithm framework is also applicable to combinatorial auctions in the
existence of production costs and resource constraints. (Blum et al.,, 2011;
Huang and Kim,, 2014; Tan et al.,, 2020). Imagine that we run an online
service system where customers arrive with a request of getting a bundle of
$n$ resources. Each customer arriving at time $t$ has a private valuation
function $v_{t}=\left[v_{1t},v_{2t},\cdots,v_{nt}\right]^{\top}$ on different
bundle $i$, and each bundle $i$ includes $m$ types of resources
$b_{i}\in\mathbb{R}^{m}$. Denote $b=\left[b_{1},b_{2},\cdots,b_{n}\right]$. At
every time $t$, we make our decision $x_{t}$ by choosing which bundle we would
like to provide. Here the decision variable is
$x_{t}\in\left\\{0,1\right\\}^{n}$ and $\sum_{i=1}^{n}x_{it}\leq 1$. The cost
of consuming resources is given by a convex function $h_{T}(x)$. Our goal is
to optimize the total social welfare by the following mixed-integer program:

$\displaystyle\max_{x_{t}}\quad$
$\displaystyle\sum_{t=1}^{T}v_{t}^{\top}x_{t}-h_{T}(\sum_{t=1}^{T}bx_{t})$
s.t. $\displaystyle\sum_{t=1}^{T}bx_{t}\preceq dT,\ d\in\mathbb{R}_{+}^{m}$
$\displaystyle\left\lVert x_{t}\right\rVert_{1}\leq 1$ $\displaystyle
x_{t}\in\left\\{0,1\right\\}^{n},\forall t\in[T].$

This online program usually formulates practical problems involved in
networking and cloud computing, e.g., cloud resource allocation (Dayarathna et
al.,, 2015) and 5G network slicing (Rost et al.,, 2017). If the convex cost is
in the form $h_{T}(x):=-T\cdot r(x/T)$ for some strongly convex function $r$,
we can write the corresponding empirical dual problem and its population
version as

$\displaystyle\bar{D}_{T}(\boldsymbol{\lambda},d)$
$\displaystyle:=\frac{\sum_{t=1}^{T}\sup_{i\in[n]}\left(v_{it}-b_{i}^{\top}(\lambda+\mu)\right)^{+}}{T}+r^{*}(-\mu)+d^{\top}\lambda$
$\displaystyle\ D_{T}(\boldsymbol{\lambda},d)$
$\displaystyle:=\mathbb{E}\sup_{i\in[n]}\left(r_{it}-b_{i}^{\top}\lambda\right)^{+}+r^{*}(-\mu)+d^{\top}\lambda.$

For a given $\boldsymbol{\lambda}$, our decision is made by
$x_{it}:=\mathbb{I}\big{(}i=\mathop{\rm
arg\max}_{i\in[n]}\left\\{v_{it}-b_{i}^{\top}(\lambda+\mu)\right\\}\big{)}$.
Under the similar locally strongly convex and non-degeneracy assumptions, our
algorithm framework achieves an $O(\log T)$ regret. The size of our problem is
different from Tan et al., (2020) because our algorithm focuses more on the
regret given linear resources rather than the competitive ratio with highly
restricted resources constraints. Here the regularizer can be interpreted as
the cost function of resources, which shares an increasing marginal cost.

###  6.4 Online convex covering and packing problem

We apply our algorithm framework to online covering and packing problems with
convex objective functions, which have been discussed in Azar et al., (2013,
2016). Consider an online context that $T$ groups of clients arrive with fixed
size and, at each time $t$, we serve the $t$-th group by assigning clients to
$n$ different facilities with increasing convex assignment cost $f_{it}$ and a
demand $b_{it}>0$ for each facility $i\in[n]$. Define $x_{it}$ as the number
of clients that are assigned to facility $i$ at time $t$, and then
$f_{it}(x_{it})$ is the corresponding assignment cost, $b_{it}x_{it}$ is the
demand for facility $i$. At each time, the total service must be larger than
the group size $1$, i.e., $\sum_{i=1}^{n}x_{it}\geq 1$. The average
maintenance cost of each facility $h_{i}$ is an increasing convex function to
its congestion, which is the ratio of the total demands of clients assigned to
the facility to the total capacity. Our goal is to minimize the sum of
assignment costs and maintenance costs:

$\displaystyle\min_{x_{t}}\quad$
$\displaystyle\sum_{t=1}^{T}\sum_{i=1}^{n}f_{it}(x_{it})+T\cdot\sum_{i=1}^{n}h_{i}(y_{i})$
s.t. $\displaystyle\sum_{t=1}^{T}b_{it}x_{it}\leq Ty_{i},\ \forall i\in[n]$
$\displaystyle\sum_{i=1}^{n}x_{it}\geq 1,\forall t\in[T]$ $\displaystyle
x_{it}\in\left[0,1\right]^{n},\forall t\in[T],i\in[n]$ $\displaystyle 0\leq
y_{i}\leq 1,\forall i\in[n].$

This is a convex and continuous variant of Capacity Constrained Facility
Location (CCFL) problem (Azar et al.,, 2013, 2016) featuring non-negative
covering and packing constraints. Here the covering constraint
$\sum_{i=1}^{n}x_{it}\geq 1$ represents the minimum service requirement, and
thus we can not take void actions; the packing constraints
$\sum_{t=1}^{T}b_{it}x_{it}\leq Ty_{i}$ represents that the congestion of each
facility $i$ is bounded by 1. Denote
$x_{t}:=\left[x_{1t},x_{2t},\cdots,x_{nt}\right]^{\top}$ and
$\mathcal{X}:=\left\\{x\in\mathbb{R}^{n}_{+}\middle|\left\lVert
x\right\rVert=1\right\\}$, we can write our convex covering and packing
problem as:

$\displaystyle\max_{x_{t}\in\mathcal{X}}\quad$
$\displaystyle\sum_{t=1}^{T}f_{t}(x_{t})+Tr(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})$
s.t. $\displaystyle\sum_{t=1}^{T}b_{t}x_{t}\preceq T\cdot\mathbf{1},$

where $f_{t}(x_{t}):=-\sum_{i=1}^{n}f_{it}(x_{it})$,
$r(y):=-\sum_{i=1}^{n}h_{i}(y_{i})$, and
$b_{t}:=\operatorname{diag}(b_{1t},b_{2t},\cdots,b_{nt})$. Thus, we can
similarly apply our Algorithm 1 to the CCFL problem and achieve optimal regret
control.

##  7 Numerical Experiments

In this section, we implement Resolving with SGD as a showcase for our
proposed algorithmic framework. The performance is assessed under 4 different
input models. The implementation details on multiple input models are as
follows: the dual update is calculated by closed-form solutions to Equation
(4.3) under input I-III and by cvxpy (Diamond and Boyd, (2016)) under input
IV. See Table 1 for more information. For each $T$, we randomly sample $T$
observations from datasets, implement our algorithm, and calculate the regret.
Only the average regret over 10 repetitions is reported. Note that we use the
dual objective evaluated at the average gradient
$D_{T}(\frac{1}{T}\sum_{t=1}^{T}\mathbf{\lambda}_{t})$ as the benchmark to
compute the regret.

Input | $f_{t}(x)$ | $r(x)$ | $b_{it}$ | $d_{i}$
---|---|---|---|---
I | $a_{t}^{\top}x$ | $-\kappa\left\lVert x-d/2\right\rVert_{2}^{2}$ | U$(0,1)$ | 0.1
II | $a_{t}^{\top}x$ | $-\kappa\left\lVert x-d/2\right\rVert_{2}^{2}$ | Bernoulli($p_{i}$) | U$(0.25,0.75)$
III | $-\frac{1}{4}x^{2}+\xi_{t}x$ | 0 | 1 | 0.5
IV | $a_{t}^{\top}x$ | $-\kappa\sum_{i=1}^{m}\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}\log\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}$ | 1 | From dataset
Table 1: Parameter Settings of Inputs

Input model I: Online welfare maximization with costs, independent reward and
resource consumption. The reward functions are linear as
$f_{t}(x)=a_{t}^{\top}x$. The regularization function is the $\ell_{2}$ loss
$r(x)=-\kappa\left\lVert x-d/2\right\rVert_{2}^{2}$, which corresponds to the
application of online welfare maximization with square costs. The reward
coefficients $a_{t}$’s and the constraint coefficients $b_{t}$’s are i.i.d.
random variables. More exactly, $a_{it}$ is generated from the uniform
distribution $U(0,10)$, and $b_{it}$ is generated from the uniform
distribution $U(0,1)$.

Figure 1: Regret versus horizon (T) under Input I. OGD stands for online
gradient descent in Balseiro et al., (2020); resolving with SGD is our
Algorithm 2; nonadaptive resolving with SGD is the nonadaptive version (i.e.,
without updating the constraints) of Algorithm 2.

(a) Online gradient descent

(b) Nonadaptive version of Algorithm 2

(c) Algorithm 2

Figure 2: Remaining resource of one binding dimension versus time under input
model I with $T=512$. Ten curves are displayed, each of which corresponds to
one simulation.

To illustrate how the regret scales with the time horizon $T$, we evaluate the
algorithms with different $T$ chosen from $\\{256,512,1024,1536,2048,2560\\}$.
Here $m=6$. We find that Resolving with SGD (Algorithm 2) shows logarithmic
regret, while its counterpart without constraint update ($d_{t}\equiv d$ in
Equation 4.2) shows a much worse regret. We name the latter algorithm as the
“Nonadaptive resolving with SGD”. The online gradient descent (OGD) method in
Balseiro et al., (2020) exhibits a $O(\sqrt{T})$ regret as indicated in their
theoretical findings. The regret comparison between the algorithms can be
found in Figure 1. In Figure 2, we plot the dynamic of resource consumption
for one binding dimension of the aforementioned algorithms. Ten curves are
displayed, each of which corresponds to one simulation. Being adaptive to the
level of remaining resources, Algorithm 2 controls carefully the constraint
consumption to ensure that the resources are consumed at a steady rate till
they are used up. In comparison, both the OGD and the nonadaptive version of
Algorithm 2 stop allocating resources too early, demonstrating the benefits of
the constraint updates, which exploit the history of past actions.

Input model II: Online welfare maximization with costs, dependent reward and
resource consumption. The parameter setting below is based on Balseiro et al.,
(2022). The reward functions and the regularization function are the same as
in input I, whereas input II considers the case when the reward coefficients
$a_{t}$’s are random variables conditional of the constraint coefficients
$b_{t}$’s. We set
$a_{t}=\text{Proj}_{[0,10]}\\{\theta_{t}^{\top}b_{t}+\delta_{t}\mathbf{1}\\}$,
where $\theta_{t}$ is generated from a multi-variate Gaussian distribution
$N(0,\text{diag}(1))$, and $\delta_{t}$ is generated from the standard
Gaussian distribution $N(0,1)$. The constraint coefficients $b_{it}$’s are
generated from Bernoulli distribution with probability parameter $p_{i}$ with
$p_{i}=(1+\alpha)/2$, and $\alpha$ is generated from the beta distribution
Beta$(1,3)$. The average resource constraints $d_{i}$’s are generated from the
uniform distribution U$(0.25,0.75)$.

Figure 3: Regret versus horizon (T) under Input II. OGD stands for online
gradient descent in Balseiro et al., (2020); resolving with SGD is Algorithm
2; nonadaptive resolving with SGD is the nonadaptive version of Algorithm 2.

Similar to the setting of input I, we evaluate the algorithms under input II
with different $T$’s and fix $m=6$. The regret performances and resource
consumption are displayed in Figure 3 and Figure 4, respectively. Among the
three algorithms (Algorithm 2, the nonadaptive Alg 2 and the OGD method in
Balseiro et al., (2020)), Algorithm 2 achieves a logarithmic regret, the
nonadaptive Alg 2 suffers from a higher regret while the regret of OGD grows
in a much faster speed.

(a) Online gradient descent

(b) Nonadaptive version of Algorithm 2

(c) Algorithm 2

Figure 4: Remaining resource of one binding dimension versus time under input
model II with $T=512$. Ten curves are displayed, each of which corresponds to
one simulation.

Input model III: Non-regularized online convex resource allocation with one
resource. In this model, we assess the algorithms’ performance under a non-
regularized special case, where there is only one resource, the reward
function$f_{t}(x)=f_{t}(x,\xi_{t})=-\frac{1}{4}x^{2}+\xi_{t}x$, the constraint
$d=\frac{1}{2}$ and cost $b_{t}=1$. The random variable $\xi_{t}$ follows a
two-point distribution that takes value in $\\{\frac{1}{2},\frac{3}{4}\\}$
with equal probability, i.e.,
$\mathop{{}\mathbb{P}}[\xi_{t}=\frac{1}{2}]=\mathop{{}\mathbb{P}}[\xi_{t}=\frac{3}{4}]=0.5$.
This special case is used in the proof of Theorem 5.

For input model III, the optimal solution to Problem (2.8) admits a closed-
form due to the simple distribution. We compare further with two algorithms:
one is “No learning” and the other is “SAA”, which are the convex versions of
Algorithm 1 and 2 in Li and Ye, (2021), respectively. Both of them require the
computation of optimal dual solutions, while neither Resolving with SGD
(Algorithm 2) nor OGD needs this step. The regret comparison is shown in
Figure 5(a). All benchmark algorithms show a regret increasing in $T$ while
Resolving with SGD exhibits a regret gradually stable with respect to $T$ as
$T$ increases. This corroborates the theoretical results that our proposed
algorithmic framework can achieve $O(\log T)$ regret and that any algorithm
without constraint updates will incur $\Omega(\sqrt{T})$ regret. We further
explain the reason for the performance advantage by plotting the remaining
time before stopping in Figure 5(b). All benchmark algorithms stop allocating
resource $O(\sqrt{T})$ steps earlier than Resolving with SGD (Algorithm 2),
which leads to the terrible regret performance.

(a) Regret versus horizon ($T$) under input III.

(b) Remaining time ($T-\tau$) versus horizon ($T$) under input III

Figure 5: Performance evaluation under input III. No learning and SAA are
convex versions of Algorithm 1 and 2 in Li and Ye, (2021); OGD is online
gradient descent in Balseiro et al., (2020); resolving with SGD is Algorithm
2; nonadaptive resolving with SGD is the nonadaptive version of Algorithm 2.

Input model IV: Display advertisement allocation with entropy regularization.
We use the display advertisement dataset in Balseiro et al., (2021) as the
last input model. Consider $m$ advertisers. In this model,
$f_{t}(x)=q_{t}^{\top}x$, where $q_{t}=\\{q_{1t},...,q_{mt}\\}$ and $q_{it}$
is the expected click through rate from impression $t$ of the $i$th
advertiser. The regularization function is
$r(x)=-\kappa\sum_{i=1}^{m}\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}\log\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}$,
imposing requirements of diversity and fairness on the allocation. The per-
time-slot budget of the $i$th advertiser denoted by $d_{i}$ is also given in
the dataset. The consumption cost is $b_{t}=1$. At time $t$, only one
advertiser can be assigned to the impression, i.e., $x_{t}\in\\{0,1\\}^{m}$
and $\sum_{i=1}^{m}x_{it}\leq 1$.

(a) Regret versus horizon ($T$) under Input IV with different regularization
levels ($\kappa=$ 0, 0.001, 0.005).

(b) Per step reward ($(\sum_{t}q_{t}x_{t})/T$) versus entropic regularization
($-\sum_{i=1}^{m}\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}\log\frac{x_{i}}{\sum_{i=1}^{m}d_{i}}$)
under input IV. From left to right dots represent $\kappa=0,0.001,0.005$,
respectively.

Figure 6: Performance evaluation under input IV. OGD is online gradient
descent in Balseiro et al., (2020); resolving with SGD is Algorithm 2

In Figure 6(a), regret curves of Algorithm 2 and OGD algorithm under different
$\kappa$s are plotted. The regret of Algorithm 2 grows slower than OGD, which
shows the advantage of the proposed algorithm under this setting. It is also
observed that the regret is very close for different regularization levels
($\kappa=0,0.001,0.005$) and $\kappa=0.001$ incurs the lowest regret. Trade-
off between the reward (average click through rate) and the regularization
term is plotted in Figure 6(b)

##  8 Discussion

In this paper, we investigated regularized online convex allocation problems
with a non-separable regularizer. While a polynomial-time adaptive algorithm
framework is proved optimal in controlling regret, several interesting yet
challenging questions are still open to us. One is the necessity of non-
degeneracy assumption. Recently, Bumpensanti and Wang, (2020) showed that the
non-degeneracy assumption is not necessary for re-solving heuristic to reach a
low regret under linear settings. Can a similar optimal result be achieved
without the non-degeneracy assumption on constraints in the online convex
allocation? Another question is on algorithm implementation. Although our
algorithms are of polynomial complexity, we still wonder whether there exists
any other adaptive strategy with a linear computational cost that can achieve
the (sub)optimal logarithmic regret. We note that in our adaptive strategy,
most of our computational complexity comes from the frequent updating of dual
solutions. To reduce the computational cost, one possible approach is to
reduce the updating frequency. Lastly, throughout this paper, we only
discussed online convex allocation problems under the stochastic input model.
The behavior of re-solving algorithms for other input models like random
permutation inputs or adversarial inputs still remains largely unknown.

## References

  * Agrawal and Devanur, (2014) Agrawal, S. and Devanur, N. R. (2014).  Fast algorithms for online stochastic convex programming.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1405–1424. SIAM.
  * Agrawal et al., (2014) Agrawal, S., Wang, Z., and Ye, Y. (2014).  A dynamic near-optimal algorithm for online linear programming.  Operations Research, 62(4):876–890.
  * Agrawal et al., (2018) Agrawal, S., Zadimoghaddam, M., and Mirrokni, V. (2018).  Proportional allocation: Simple, distributed, and diverse matching with high entropy.  In International Conference on Machine Learning, pages 99–108. PMLR.
  * Arlotto and Gurvich, (2019) Arlotto, A. and Gurvich, I. (2019).  Uniformly bounded regret in the multisecretary problem.  Stochastic Systems, 9(3):231–260.
  * Azar et al., (2013) Azar, Y., Bhaskar, U., Fleischer, L., and Panigrahi, D. (2013).  Online mixed packing and covering.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 85–100. SIAM.
  * Azar et al., (2016) Azar, Y., Buchbinder, N., Chan, T. H., Chen, S., Cohen, I. R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J., et al. (2016).  Online algorithms for covering and packing problems with convex objectives.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 148–157. IEEE.
  * Babaioff et al., (2007) Babaioff, M., Immorlica, N., Kempe, D., and Kleinberg, R. (2007).  A knapsack secretary problem with applications.  In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, pages 16–28. Springer.
  * Babaioff et al., (2008) Babaioff, M., Immorlica, N., Kempe, D., and Kleinberg, R. (2008).  Online auctions and generalized secretary problems.  ACM SIGecom Exchanges, 7(2):1–11.
  * Balseiro et al., (2020) Balseiro, S., Lu, H., and Mirrokni, V. (2020).  Dual mirror descent for online allocation problems.  In International Conference on Machine Learning, pages 613–628. PMLR.
  * Balseiro et al., (2021) Balseiro, S., Lu, H., and Mirrokni, V. (2021).  Regularized online allocation problems: Fairness and beyond.  In International Conference on Machine Learning, pages 630–639. PMLR.
  * Balseiro and Gur, (2019) Balseiro, S. R. and Gur, Y. (2019).  Learning in repeated auctions with budgets: Regret minimization and equilibrium.  Management Science, 65(9):3952–3968.
  * Balseiro et al., (2022) Balseiro, S. R., Lu, H., and Mirrokni, V. (2022).  The best of many worlds: Dual mirror descent for online allocation problems.  Operations Research.
  * Bertsimas et al., (2011) Bertsimas, D., Farias, V. F., and Trichakis, N. (2011).  The price of fairness.  Operations research, 59(1):17–31.
  * Blum et al., (2011) Blum, A., Gupta, A., Mansour, Y., and Sharma, A. (2011).  Welfare and profit maximization with production costs.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 77–86. IEEE.
  * Bray, (2019) Bray, R. (2019).  Does the multisecretary problem always have bounded regret?  Available at SSRN 3497056.
  * Buchbinder et al., (2007) Buchbinder, N., Jain, K., and Naor, J. S. (2007).  Online primal-dual algorithms for maximizing ad-auctions revenue.  In European Symposium on Algorithms, pages 253–264. Springer.
  * Bumpensanti and Wang, (2020) Bumpensanti, P. and Wang, H. (2020).  A re-solving heuristic with uniformly bounded loss for network revenue management.  Management Science, 66(7):2993–3009.
  * Cooper, (2002) Cooper, W. L. (2002).  Asymptotic behavior of an allocation policy for revenue management.  Operations Research, 50(4):720–727.
  * Dayarathna et al., (2015) Dayarathna, M., Wen, Y., and Fan, R. (2015).  Data center energy consumption modeling: A survey.  IEEE Communications Surveys & Tutorials, 18(1):732–794.
  * Devanur and Hayes, (2009) Devanur, N. R. and Hayes, T. P. (2009).  The adwords problem: online keyword matching with budgeted bidders under random permutations.  In Proceedings of the 10th ACM conference on Electronic commerce, pages 71–78.
  * Devanur et al., (2019) Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. (2019).  Near optimal online algorithms and fast approximation algorithms for resource allocation problems.  Journal of the ACM (JACM), 66(1):1–41.
  * Diamond and Boyd, (2016) Diamond, S. and Boyd, S. (2016).  Cvxpy: A python-embedded modeling language for convex optimization.  The Journal of Machine Learning Research, 17(1):2909–2913.
  * Ferreira et al., (2018) Ferreira, K. J., Simchi-Levi, D., and Wang, H. (2018).  Online network revenue management using thompson sampling.  Operations research, 66(6):1586–1602.
  * Ghosh et al., (2009) Ghosh, A., McAfee, P., Papineni, K., and Vassilvitskii, S. (2009).  Bidding for representative allocations for display advertising.  In International workshop on internet and network economics, pages 208–219. Springer.
  * Goel and Mehta, (2008) Goel, G. and Mehta, A. (2008).  Online budgeted matching in random input models with applications to adwords.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 982–991.
  * Gorbunov et al., (2020) Gorbunov, E., Hanzely, F., and Richtárik, P. (2020).  A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent.  In International Conference on Artificial Intelligence and Statistics, pages 680–690. PMLR.
  * Hazan et al., (2007) Hazan, E., Agarwal, A., and Kale, S. (2007).  Logarithmic regret algorithms for online convex optimization.  Machine Learning, 69(2):169–192.
  * Hazan et al., (2016) Hazan, E. et al. (2016).  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2(3-4):157–325.