# Online Primal-Dual Algorithms with Predictions for Packing Problems

Nguyễn Kim Thắng
University Paris-Saclay, IBISC, France  Christoph Dürr
Sorbonne University, CNRS, LIP6, France

###### Abstract

The domain of online algorithms with predictions has been extensively studied
for different applications such as scheduling, caching (paging), clustering,
ski rental, etc. Recently, Bamas et al., aiming for an unified method, have
provided a primal-dual framework for linear covering problems. They extended
the online primal-dual method by incorporating predictions in order to achieve
a performance beyond the worst-case case analysis. In this paper, we consider
this research line and present a framework to design algorithms with
predictions for non-linear packing problems. We illustrate the applicability
of our framework in submodular maximization and in particular ad-auction
maximization in which the optimal bound is given and supporting experiments
are provided.

##  1 Introduction

Online computation [7] is a well-established field in theoretical computer
science. In online computation, inputs are released one-by-one in form of a
request sequence. Requests arrive over time and each request must be answered
by the algorithm with an irrevocable action, without any information about
future requests to come. These actions define a solution to the problem at
hand, and the algorithm wants to optimize its objective value. Usually this
value is normalized by the optimum, which could have been computed if all the
requests were known in beforehand. The resulting _competitive ratio_ measures
the price of not knowing the future requests.

Several models have been studied, which relax some of the assumptions in the
standard online computation model, see [31, 32] for a recent survey.

One of the models is motivated by spectacular advances in machine learning
(ML). In particular, the capability of ML methods in predicting patterns of
future requests would provide useful information to be exploited by online
algorithms. A general framework for incorporating ML predictions into
algorithm design in order to achieve a better performance than the worst-case
one is formally introduced by [23]. This is rapidly followed by work studying
online algorithms with predictions [28] in a large spectrum of problems such
as scheduling [21, 27], caching (paging) [23, 29, 2], ski rental [15, 20, 1],
etc. In contrast to online computation with advice (see [17] for a survey),
the aforementioned models handle predictions in a careful manner, guaranteeing
good performance even if the predictions is completely wrong. More precisely,
on the one hand, if the predictions are accurate, one expects to achieve a
good performance as in the offline setting where the input are completely
given in advance. On the other hand, if the predictions are misleading, one
still has to maintain a competitive solution as in the online setting where no
predictive information is available.

This issue has been addressed (for example the aforementioned work) by subtly
incorporating predictions and exploiting specific problems’ structures. The
primal-dual method is an elegant and powerful technique for the design of
algorithms [36], especially for online algorithms [8]. In the objective of
unifying previous ad-hoc approaches, [5] presented a primal-dual approach to
design online algorithms with predictions for covering problems with a linear
objective function. In this paper, we build on previous work and provide a
primal-dual method with predictions for packing problems with non-linear
objectives; following a research direction and answering some open questions
mentioned in [5].

###  1.1 Problem and Model

##### Packing problem

In the packing problem studied in this paper we are given of a sequence of $n$
elements ${\cal E}$, and $m$ unit capacity resources, numbered from $1$ to
$m$. Each element $e\in\cal E$ has a profit $w_{e}$ and a resource requirement
$b_{i,e}\geq 0$ for each resource $i$. The goal is to select a set of elements
of maximum total profit, such that no resource capacity is exceeded. Formally
the goal is to chose a vector $\bm{x}\in\\{0,1\\}^{|\cal E|}$ maximizing
$\sum_{e\in\cal E}w_{e}x_{e}$ such that for every resource
$i\in\\{1,\ldots,m\\}$ we have $\sum_{e\in\cal E}b_{i,e}x_{e}\leq 1$.

##### Fractional variant

In the fractional variant of this problem, the integrality constraint on $x$
is removed, and the goal is to optimize over vectors $x\in[0,1]^{|\cal E|}$.
By $I$ we denote the instance of a packing problem, which consists of
$\langle{\cal E},(w_{e})_{e\in\cal E},m,(b_{i,e})_{1\leq i\leq m,e\in\cal
E}\rangle$.

##### Non-linear variant

We consider a generalization of this problem, where the objective is not to
maximize the sum $\sum_{e\in\cal E}w_{e}x_{e}$, but $f(\bm{x})$ for a given
function $f:\\{0,1\\}^{|\cal E|}\rightarrow{\mathbb{R}}^{+}$. It is assumed
that $f$ is monotone, in the sense that $f(\textbf{x})\leq f(\textbf{y})$,
whenever y equals x except for a single element $e$ with $x_{e}=0$ and
$y_{e}=1$. Describing $f$ explicitly needs space $O(2^{|{\cal E}|})$, hence it
is assumed that $f$ is given as a black-box oracle. For the fractional
variant, the multilinear extension $F:[0,1]^{|\cal
E|}\rightarrow{\mathbb{R}}^{+}$ is used instead of $f$, which is defined as

$F(\bm{x})=\sum_{S\subseteq\cal E}\prod_{e\in S}x_{e}\prod_{e\not\in
S}(1-x_{e})f(\bm{1}_{S}),$

where $\bm{1}_{S}$ is the characteristic vector of the set $S$. Alternatively,
$F(\bm{x})=\mathbb{E}\bigl{[}f(\bm{1}_{T})\bigr{]}$ where $T$ is a random set
such that every element $e$ appears independently in $T$ with probability
$x_{e}$. Note that $F(\bm{1}_{S})=f(\bm{1}_{S})$ for every
$S\subseteq\mathcal{E}$ — $F$ is truly an extension of $f$ — and if $f$ is
monotone then so is $F$, in the sense that $F(\bm{x})\leq F(\bm{y})$ for all
vectors $\bm{x},\bm{y}\in[0,1]^{|\cal E|}$ such that $x_{e}\leq y_{e}$ for all
elements $e$.

##### Online packing problem.

In the paper, we consider the model presented in [5] (with several definitions
rooted in [23, 20]). In the online packing problem, elements $e\in\cal E$
arrive online. When element $e\in\cal E$ arrives, the algorithm learns its
resource requirements $b_{i,e}$. At the arrival of $e$ only $x_{e}$ can be set
by the algorithm, and cannot be changed later on. Only $m$, the number of
resources, are initially known to the algorithm. The algorithm does not know
$\cal E$ initially, not even its cardinality. Formally an online algorithm
$\cal A$ receives the elements of $\cal E$ in arbitrary order, and upon
reception of element $e\in\cal E$ needs to choose a value for $x_{e}$. At any
moment, the vector $\bm{x}$ must satisfy all $m$ resource capacity constraints
of the packing problem.

We denote by ${\cal A}(I)$ the objective value of the solution produced by $A$
on an instance $I$. A prediction is an integral value
$x^{\texttt{pred}}_{e}\in\\{0,1\\}$, which is given to the algorithm with
every element $e$. Confidence in the prediction is described by a parameter
$\eta\in(0,1]$. For convenience we choose larger $\eta$ value to represent
smaller confidence. Similarly to ${\cal A}(I)$, we denote by ${\cal P}(I)$ the
objective value of the vector $\bm{x}^{\texttt{pred}}$ produced by the
prediction, and set ${\cal P}(I)=0$ whenever $\bm{x}^{\texttt{pred}}$ does not
satisfy all constraints. Finally we denote by ${\cal O}(I)$ the optimal
fractional solution to the packing problem, which could have been computed if
the whole instance $I$ were available from the beginning.

Algorithm $\mathcal{A}$ is $c(\eta)$-_consistent_ and $r(\eta)$-_robust_ if
for every instance $I$,

$\displaystyle\mathcal{A}(I)\geq\max\\{c(\eta)\cdot\mathcal{P}(I),r(\eta)\cdot\mathcal{O}(I)\\}.$

Ideally we would like that $c(\eta)$ tends to $1$, when $\eta$ approaches $0$,
meaning that with high confidence, the algorithm performs at least as good as
the prediction. Additionally we would like that $r(\eta)$ tends to the same
competitive ratio as in the standard online setting (without provided
predictions), when $\eta$ approaches $1$.

##### Objective function

At any moment in time, the algorithm maintains a vector $\bm{x}$ over the
arrived elements. Conceptually this vector is padded with zeros to create a
vector belonging to $[0,1]^{|\cal E|}$, which for convenience we also denote
by $\bm{x}$.

###  1.2 Approach and Contribution

We use the primal-dual method in our approach. At a high level, it formulates
a given problem as a (primal) linear program. There is a corresponding dual
linear program, which plays an important role in the method. By weak duality,
a solution to the dual bounds the optimal solution to the primal. Every
arrival of an element in the online problem, translates in the arrival of a
variable in the primal linear program, and a corresponding constraint in the
dual linear program. The algorithm updates the fractional solutions to both
the primal and dual in order to maintain their feasibility. Then, the
competitive ratio of the algorithm is established by showing that every time
an update of primal and dual solutions is made, the increase of the primal can
be bounded by that of the dual up to some desired factor.

Note that, similar to [5], we focus on constructing fractional solution which
is the main step in the primal-dual method. In order to derive algorithms for
specific problems, online rounding schemes are needed and in many problems,
such schemes already exist. We will provide references for the rounding
schemes tailor designed for different applications, but do not develop them in
this paper.

We follow the primal-dual framework presented in [34] to design competitive
algorithms for fractional non-linear packing problems. Given a function
$f:\\{0,1\\}^{n}\rightarrow\mathbb{R}^{+}$, its _multilinear extension_
$F:[0,1]^{n}\rightarrow\mathbb{R}^{+}$ is defined as
$F(\bm{x}):=\sum_{S\subseteq\mathcal{E}}\prod_{e\in S}x_{e}\prod_{e\notin
S}(1-x_{e})\cdot f(\bm{1}_{S})$ where $\bm{1}_{S}$ is the characteristic
vector of $S$ (i.e., the $e^{\textnormal{th}}$-component of $\bm{1}_{S}$
equals $1$ if $e\in S$ and equals 0 otherwise).

The performance of an algorithm will depend on the following measures on the
objective function.

######  Definition 1 ([34])

A differentiable function $F:[0,1]^{|\cal E|}\rightarrow\mathbb{R}^{+}$ is
_$(\lambda,\mu)$ -locally-smooth_ for some parameters $\lambda,\mu\geq 0$ if
for any set $S\subseteq\mathcal{E}$, and for every vector
$\bm{x}\in[0,1]^{|\cal E|}$, the following inequality holds:

$\langle\nabla F(\bm{x}),\bm{1}_{S}\rangle=\sum_{e\in
S}\nabla_{e}F(\bm{x})\geq\lambda F\bigl{(}\bm{1}_{S}\bigr{)}-\mu
F\bigl{(}\bm{x}\bigr{)}.$

where $\nabla_{e}F(\bm{x})$ denotes $\partial F(\bm{x})/\partial x_{e}$.

Note that the $(\lambda,\mu)$-smoothness notion here differs from the usual
notion of smoothness of functions in convex optimization. The former,
introduced in [34], is related to the definition of smooth games [30] in the
context of algorithmic game theory. The parameters $(\lambda,\mu)$ somehow
describe how far the function is from being linear. For example a non-
decreasing linear function is $(1,1)$-locally-smooth. Another example is the
multilinear extension of monotone submodular functions, which is
$(1,2)$-locally-smooth [34].

The dual of a linear packing problem is a linear covering problem and vice-
versa. However this breaks when considering non-linear objective functions.
The usual trick is to linearize the model, by introducing auxiliary variables
and work with what is called a configuration linear program. Now, how are we
going to exploit the prediction? In our approach, we incorporate the
predictive information in the primal-dual approach by modifying the
coefficients of the constraints. This in turn influences the increase of the
primal variables and hence the solution produced by the algorithm.

This approach guarantees that: (i) if the confidence on the prediction is high
($\eta$ is close to 0) then value of variables corresponding to the elements
selected by the prediction would get a large value; (ii) and inversely, if the
confidence on the prediction is low ($\eta$ is close to 1) then the variables
would be constructed as in the standard online primal-dual method. The
construction follows the multiplicative weights update based on the gradient
of the multilinear extension [34], which generalizes the multiplicative update
in [9, 3]. Using the concept of local-smoothness, we show the feasibility of
our primal/dual solutions (even when the prediction provides an infeasible
one) and also analyze the performance of the algorithm, as a function of
locally-smoothness and confidence parameters.

###### Theorem 1

Let $F$ be the multilinear extension of the non-decreasing objective function
$f$. Denote the _row sparsity_ $d:=\max_{i}|\\{b_{ie}:b_{ie}>0\\}|$ and the
_divergence_
$\rho:=\max_{i}\max_{e,e^{\prime}:b_{ie^{\prime}>0}}b_{ie}/b_{ie^{\prime}}$.
Assume that $F$ is $(\lambda,\mu)$-locally-smooth for some parameters
$\lambda>0$ and $\mu$. Then, for every $0<\eta\leq 1$, there exists a
$r(\eta)$-consistent and
$r(\eta)\cdot\bigl{(}\frac{\lambda}{2\ln(1+d\rho/\eta)+\mu}\bigr{)}$-robust
algorithm for the fractional packing problem where
$r(\eta)=\min_{\bm{0}\leq\bm{u}\leq\bm{1}}F(\frac{\bm{u}}{1+\eta})/F(\bm{u})$.

In the following, we describe the applications of our framework to different
classes of problems.

  * •

Linear objectives. Numerous combinatorial problems can be formalized by linear
programs with packing constraints to which our framework applies. When $f$ is
a monotone linear function, the smooth parameters of $F$ are $\lambda=1$ and
$\mu=1$. In this case, our algorithm guarantees the consistency
$C(\eta)=\frac{1}{1+\eta}$ and the robustness
$R(\eta)=\frac{\Omega(1)}{2(1+\eta)\ln(1+d\rho/\eta)}$. Note that in this
case, the multilinear extension $F$ is rather easy to compute, as it satisfies
$F(\bm{x})=\sum_{e\in\cal E}x_{e}f(\bm{1}_{\\{e\\}})$.

  * •

Submodular objectives. Submodular maximization constitutes a major research
agenda and has been widely studied in optimization, machine learning [4, 19,
6] and algorithm design [13, 10]. Using our framework, we derive an algorithm
that yields a $(1-\eta)$-consistent and
$\Omega\bigl{(}\frac{1}{2\ln(1+d\rho/\eta)}\bigr{)}$-robust fractional
solution for online submodular maximization with packing constraints. This
performance is similar to that of linear functions up to constant factors.
Note that using the online contention resolution rounding schemes [14],
generalizing the offline counterpart [11], one can obtain randomized
algorithms for several specific constraint polytopes such as knapsack
polytopes, matching polytopes and matroid polytopes.

##### Ad-auctions problem.

An interesting particular packing problem is the ad-auctions revenue
maximization. Informally, one needs to allocate ads in an online manner to
advertisers with their budget constraints in order to maximize the total
revenue from allocated ads. Any algorithm improving the ad allocation even by
a small fraction would have a non-negligible impact. Building on the salient
ideas of our framework, we give a $(1-\eta)$-consistent and $(1-\eta
e^{-\eta})$-robust algorithm for this problem.

###  1.3 Related work

The primal-dual method is a powerful tool for online computation.

A primal-dual framework for linear programs with packing/covering constraints
was given in [9]. Their method unifies several previous potential-function-
based analyses and give a principled approach to design and analyze algorithms
for problems with linear relaxations. A framework for covering/packing
problems with convex/concave objectives whose gradients are monotone was
provided by [3]. Subsequently, [34] presented algorithms dealing with non-
convex functions and established the competitive ratio as a function of the
smoothness parameters of the objective function. The smoothness notion
introduced in [34] has rooted in smooth games defined by [30] in the context
of algorithmic game theory.

The domain of algorithms with predictions [28], or learning augmented
algorithms, has recently emerged and rapidly grown at the intersection of
(discrete) algorithm design and machine learning (ML). The idea is to
incorporate learning predictions, together with ML techniques into algorithm
design, in order to achieve performance guarantees beyond the worst-case
analysis and provide specifically adapted solutions to different problems.
Interesting results have been shown over a large spectrum of problems such as
scheduling [21, 27], caching (paging) [23, 29, 2], ski rental [15, 20, 1],
counting sketches [16], bloom filters [18, 26], etc. Recently, Bamas et al.
[5] have proposed a primal-dual approach to design online algorithms with
predictions for linear problems with covering constraints. In this paper, by
combining their ideas and the ideas from [9, 3, 34], we present a primal-dual
framework for more general problems with non-linear objectives and
packing/covering constraints (motivated by a question mentioned in [5]).

Online matching and ad-auctions have been widely studied (see [25] and
references therein). Motivated by Internet advertising applications, several
works have considered the ad-auctions problem in various settings where
forecast/prediction is available/learnable. Esfandiari et al. [12] considered
a model in which the input is stochastic and a forecast for the future items
is given. The accuracy of the forecast is intuitively measured by the fraction
of the value of an optimal solution that can be obtained from the stochastic
input. They provide algorithms with provable bounds in this setting. Schild et
al. [33] introduced the semi-online model in which unknown future has a
predicted part and an adversarial part. They gave algorithms with competitive
ratios depending on the fraction of the adversarial part (in the input).
Closely related to our work is the model by Mahdian et al. [24] in which given
two algorithms, one needs to design a (new) algorithm which is robust to both
given algorithms. They derived an algorithm for ad-auctions problems that
achieves a fraction of the maximum revenue of the given algorithms. The main
difference to ours model is that their algorithm is _not_ robust in case a
given algorithm provides infeasible solutions (which would happen for the
prediction) whereas our algorithm is.

##  2 Primal-Dual Framework for Packing Problems

##### Formulation.

First, we model the packing problem as a configuration linear program. For the
integral variant of the packing problem, the decision variable
$x_{e}\in\\{0,1\\}$ indicates whether element $e$ is selected in the solution.
A configuration is a set of elements $S\subseteq\mathcal{E}$ and could be
feasible or not. In addition to $\bm{x}$ the linear program contains variables
$z_{S}\in\\{0,1\\}$ for every configuration $S$. The idea is that $z_{S}=1$
solely for the set $S$ containing all selected elements $e$, i.e. for which
$x_{e}=1$. In this case $S$ is feasible by the constraints imposed on
$\bm{x}$.

The fractional variant of the packing problem is modeled with the same
variables and constraints, but without the integrality constraints. Now
$x_{e}$ specifies the fraction with which $e$ is selected. The $\bm{z}$
variables represent now a distribution on configurations $S$ and have to be
consistent with $\bm{x}$ in the following sense. When $S$ is selected with
probability $z_{S}$, then $e$ belongs to the selected set $S$ with probability
$x_{e}$. Unlike for the integral linear program, $\bm{z}$ is not unique for
given $\bm{x}$. In our algorithm we chose a particular vector $\bm{z}$. Note
that the support of $\bm{z}$ might contain non-feasible configurations.

We consider the following linear program and its dual.

$\displaystyle b\max\sum_{S}$ $\displaystyle f(\bm{1}_{S})z_{S}$
$\displaystyle\sum_{e}b_{i,e}\cdot x_{e}$ $\displaystyle\leq 1$
$\displaystyle\forall i$ $\displaystyle(\alpha_{i})$
$\displaystyle\sum_{S:e\in S}z_{S}$ $\displaystyle=x_{e}$
$\displaystyle\forall e$ $\displaystyle(\beta_{e})$
$\displaystyle\sum_{S}z_{S}$ $\displaystyle=1$ $\displaystyle(\gamma)$
$\displaystyle x_{e},z_{S}$ $\displaystyle\geq 0$ $\displaystyle\forall e,S$

$\displaystyle\min\sum_{i}\alpha_{i}$ $\displaystyle+\gamma$
$\displaystyle\sum_{i}b_{i,e}\cdot\alpha_{i}$ $\displaystyle\geq\beta_{e}$
$\displaystyle\forall e$ $\displaystyle(x_{e})$
$\displaystyle\gamma+\sum_{e\in S}\beta_{e}$ $\displaystyle\geq f(\bm{1}_{S})$
$\displaystyle\forall S$ $\displaystyle(z_{S})$ $\displaystyle\alpha_{i}$
$\displaystyle\geq 0$ $\displaystyle\forall i$

In the primal, $(\alpha_{i})$ are the packing constraints of the given
problem. Constraints $(\beta_{e})$ force the aforementioned relation between
$\bm{x}$ and $\bm{z}$. Constraint $(\gamma)$ ensures that $\bm{z}$ represents
a distribution. Note that the primal constraints $(\gamma)$ and $(\beta_{e})$,
imply the box constraints $x_{e}\leq 1~{}\forall e$.

##### Algorithm.

Assume that function $F(\cdot)$ is $(\lambda,\mu)$-locally smooth. Let $d$ be
the maximal number of positive entries in a row, i.e.,
$d=\max_{i}|\\{b_{ie}:b_{ie}>0\\}|$. Let $\rho$ the maximum divergence between
positive row coefficients, i.e.
$\rho=\max_{i}\max_{e,e^{\prime}:b_{ie^{\prime}>0}}b_{ie}/b_{ie^{\prime}}$.
The algorithm is given a prediction $\bm{x}^{\texttt{pred}}$, i.e. with every
arriving element $e$, it receives the values $x^{\texttt{pred}}_{ie}$ for each
resource $i$. It uses this prediction to specify coefficients
$\overline{\bm{b}}$, which are scaled from $\bm{b}$ in a specific manner. The
maximum divergence $\overline{\rho}$ is defined similarly as $\rho$ with
$\overline{\bm{b}}$ replacing $\bm{b}$, i.e.,
$\overline{\rho}=\max_{i}\max_{e,e^{\prime}:\overline{b}_{ie^{\prime}>0}}\overline{b}_{i,e}/\overline{b}_{ie^{\prime}}$.

The algorithm maintains a primal solution $\bm{y}\in[0,1]^{\cal E}$, computed
with the primal-dual method with respect to the coefficients
$\overline{\bm{b}}$. Its decision for element $e$ either follows the predicted
solution $x^{\texttt{pred}}_{e}$, or it follows $y_{e}$ in case infeasibility
of the predicted solution $\bm{x}^{\texttt{pred}}$ has been detected.

The value of $\overline{b}_{i,e}$ depends on coefficient $b_{i,e}$ and the
prediction $x^{\texttt{pred}}_{e}$. Specifically, $\overline{b}_{i,e}=b_{i,e}$
if $x^{\texttt{pred}}_{e}=1$ and the predictive solution is _not_ feasible;
$\overline{b}_{i,e}=\frac{1}{\eta}b_{i,e}$ otherwise. In both cases, packing
constraints using $\overline{\bm{b}}$ are stronger than they would be with
coefficients $\bm{b}$.

Intuitively, if we do not trust the prediction at all, i.e. $\eta=1$, then
$\overline{b}_{i,e}=b_{i,e}$ and therefore $x_{e},y_{e}$ would get a value
proportional to the one returned by a primal-dual algorithm in the classic
setting. Inversely, if we trust the prediction (i.e., $\eta$ is close to 0)
and the prediction is feasible, then $\overline{b}_{i,e}=b_{i,e}$ when
$x^{\texttt{pred}}_{e}=1$ and $\overline{b}_{i,e}=b_{i,e}/\eta$ when
$x^{\texttt{pred}}_{e}=0$. Therefore, the modified constraint
$\sum_{e^{\prime}}\overline{b}_{i,e^{\prime}}y_{e^{\prime}}\leq 1$ will likely
prevent $y_{e}$, for $e$ such that $x^{\texttt{pred}}_{e}=0$, from getting a
large value. Hence, $y_{e}$ for $e$ such that $x^{\texttt{pred}}_{e}=1$ could
get a large value. In the end of each iteration, we set the output solution
$x_{e}$ roughly by scaling a factor $\frac{1}{1+\eta}$ to $y_{e}$ or
$x^{\texttt{pred}}_{e}$ (depending on cases) in order to maintain the
feasibility and the consistency to the prediction.

The construction of $\bm{y}$ follows the scheme in [34]. We recall the
definition of the divergence factor
$\overline{\rho}=\max_{i}\max_{e,e^{\prime}:\overline{b}_{ie^{\prime}>0}}\overline{b}_{i,e}/\overline{b}_{ie^{\prime}}$.
So in particular, $\overline{\rho}\leq\rho/\eta$. Recall that the gradient in
direction $e$ is $\nabla_{e}F(\bm{y})=\partial F(\bm{y})/\partial y_{e}$. By
convention, when an element $e$ is not released, $\nabla_{e}F(\bm{y})=0$.
While $\nabla_{e}F(\bm{y})>0$ — i.e., increasing $y_{e}$ improves the
objective value — and
$\sum_{i}\overline{b}_{i,e}\alpha_{e}\leq\frac{1}{\lambda}\nabla_{e}F(\bm{y})$,
the primal variable $y_{e}$ and dual variables $\alpha_{i}$’s are increased by
appropriate rates. We will argue in the analysis that the primal and dual
solutions returned by the algorithm are feasible.

Recall that by definition of the multilinear extension,

$\nabla_{e}F(\bm{y})=F((\bm{y}_{-e},1))-F((\bm{y}_{-e},0))=\mathbb{E}_{R}\bigl{[}f\bigl{(}\bm{1}_{R\cup\\{e\\}}\bigr{)}-f\bigl{(}\bm{1}_{R}\bigr{)}\bigr{]}$

where $(\bm{y}_{-e},1)$ denotes a vector which is identical to $\bm{y}$ on
every coordinate different to $e$ and the value at coordinate $e$ is 1. The
vector $(\bm{y}_{-e},0)$ is defined similarly. The expectation is taken over
random subset $R\subseteq\mathcal{E}\setminus\\{e\\}$ such that $e^{\prime}$
is included with probability $y_{e^{\prime}}$. Therefore, during the iteration
of the while loop with respect to element $e$, only $y_{e}$ is modified and
$y_{e^{\prime}}$ remains fixed for all $e^{\prime}\neq e$, as a consequence
$\nabla_{e}F(\bm{y})$ is constant during the iteration. Moreover, for every
$e$, $F(\bm{y})$ and $\nabla_{e}F(\bm{y})$ can be efficiently approximated up
to any required precision [35].

One important aspect of the primal-dual algorithm presented below, is that it
works only with primal variables $\bm{x}$ and dual variables $\alpha$, and
uses the multilinear extension $F$ instead of $f$. However for the analysis,
we will later show how to extend these solutions with variables $\bm{z}$ and
$\bm{\beta}$, $\gamma$ both to show feasibility of the constructed solution
and to analyze consistency and robustness of the algorithm.

1: All primal and dual variables are initially set to 0.

2: Let $\bm{y}\in[0,1]^{\cal E}$ be such that $y_{e}=0~{}\forall e$.

3: At every step, always maintain $z_{S}=\prod_{e\in S}x_{e}\prod_{e\notin
S}(1-x_{e})$.

4: for each arrival of a new element $e$ do

5: if $x^{\texttt{pred}}_{e}=1$ or the predictive solution
$\bm{x}^{\texttt{pred}}$ is infeasible then

6: set $\overline{b}_{i,e}=b_{i,e}$

7: else

8: set $\overline{b}_{i,e}=b_{i,e}/\eta$

9: end if

10: while
$\sum_{i}\overline{b}_{i,e}\alpha_{i}\leq\frac{1}{\lambda}\nabla_{e}F(\bm{y})$
and $\nabla_{e}F(\bm{y})>0$ do

11: Some of the primal and dual variables are increased continuously as
follows, where $\tau$ is the time during this process.

12: Increase $y_{e}$ at a rate such that
$\frac{dy_{e}}{d\tau}\leftarrow\frac{1}{\nabla_{e}F(\bm{y})\cdot\ln(1+d\overline{\rho})}$.

13: end while

14: if $x^{\texttt{pred}}_{e}=1$ and the predictive solution is still feasible
then

15: set
$x_{e}\leftarrow\frac{1}{1+\eta}x^{\texttt{pred}}_{e}=\frac{1}{1+\eta}$

16: else

17: set $x_{e}\leftarrow\frac{1}{1+\eta}y_{e}$

18: end if

19: end for

Algorithm 1 Algorithm for Packing Problem.

Note that once the prediction becomes infeasible, the algorithm works with the
given $b$ coefficients and outputs the solution computed by $y_{e}$ scaled by
$1/(1+\eta)$.

##### Primal variables.

The vector $\bm{x}$ is completed by $\bm{z}$ to form a complete solution to
the primal linear program, by setting $z_{S}=\prod_{e\in S}x_{e}\prod_{e\notin
S}(1-x_{e})$.

##### Dual variables.

Variables $\alpha_{i}$’s are constructed in the algorithm. Define
$\gamma=\frac{\mu}{\lambda}F(\bm{y})$ and
$\beta_{e}=\frac{1}{\lambda}\cdot\nabla_{e}F(\bm{y})$.

The following lemma provides a lower bound on the $\alpha$ variables.

###### Lemma 1

At any moment during the iteration related to element $e$, for every
constraint $i$ it always holds that

$\displaystyle\alpha_{i}$
$\displaystyle\geq\frac{\nabla_{e}F(\bm{y})}{\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
d\lambda}\left[\exp\biggl{(}\ln\bigl{(}1+d\overline{\rho}\bigr{)}\cdot\sum_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
y_{e^{\prime}}\biggr{)}-1\right].$ (1)

_Proof_ Fix a constraint $i$. We prove the claimed inequality by induction. In
the very beginning of the algorithm, when no elements are released yet, the
inequality holds since both sides are 0. Consider any moment $\tau$ during the
loop corresponding to an arriving element $e$. Assume that the inequality
holds at the beginning of the iteration step. We will show that the inequality
still holds after the step.

As $F$ is a multilinear extension, by its very definition, $F$ is linear in
$y_{e}$. Hence $\nabla_{e}F(\bm{y})$ is independent of $y_{e}$. Moreover,
during the loop corresponding to resource $e$, only $y_{e}$ is modified,
leaving $y_{e^{\prime}}$ unchanged for all $e^{\prime}\neq e$. As as a result,
$d\nabla_{e}F(\bm{y})/d\tau=0$. Therefore, the rate at time $\tau$ of the the
right-hand-side of Inequality (1) is:

$\displaystyle\frac{\nabla_{e}F(\bm{y})}{\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
d\lambda}\cdot\ln\bigl{(}1+d\overline{\rho}\bigr{)}\cdot\overline{b}_{i,e}\cdot\frac{dy_{e}}{d\tau}\cdot\exp\biggl{(}\ln\bigl{(}1+d\overline{\rho}\bigr{)}\cdot\sum_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
y_{e^{\prime}}\biggr{)}$
$\displaystyle\leq\frac{\nabla_{e}F(\bm{y})}{\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
d\lambda}\cdot\ln\bigl{(}1+d\overline{\rho}\bigr{)}\cdot\overline{b}_{i,e}\cdot\frac{1}{\nabla_{e}F(\bm{y})\cdot\ln(1+d\overline{\rho})}\cdot\biggl{(}\frac{\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
d\lambda\cdot\alpha_{i}}{\nabla_{e}F(\bm{y})}+1\biggr{)}$
$\displaystyle\leq\frac{\overline{b}_{i,e}\cdot\alpha_{i}}{\nabla_{e}F(\bm{y})}+\frac{1}{d\lambda}=\frac{d\alpha_{i}}{d\tau},$

where in the first inequality we use the induction hypothesis and the
increasing rate of $y_{e}$. So at any time during the iteration related to
$e$, the increasing rate of the left-hand side is always larger than that of
the right-hand side. Hence, the lemma follows. $\Box$

###### Lemma 2

The primal variables constructed by the algorithm are feasible.

_Proof_ First observe that if during the execution of the algorithm in the
iteration related to some element $e$, we have
$\sum_{e^{\prime}}\overline{b}_{i,e^{\prime}}y_{e^{\prime}}>1$ for some
constraint $i$ then by Lemma 1,

$\alpha_{i}>\frac{\nabla_{e}F(\bm{y})}{\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}\cdot
d\lambda}\left[\exp\biggl{(}\ln\bigl{(}1+d\overline{\rho}\bigr{)}\biggr{)}-1\right]=\frac{\overline{\rho}\cdot\nabla_{e}F(\bm{y})}{\lambda\max_{e^{\prime}}\overline{b}_{i,e^{\prime}}}\geq\frac{\nabla_{e}F(\bm{y})}{\lambda\overline{b}_{i,e}}$

Therefore,
$\sum_{i}\overline{b}_{i,e}\alpha_{i}>\frac{1}{\lambda}\nabla_{e}F(\bm{y})$
and hence the algorithm would have stopped increasing $y_{e}$ at some earlier
point. Therefore, every constraint
$\sum_{e^{\prime}}\overline{b}_{i,e^{\prime}}y_{e^{\prime}}\leq 1$ is always
maintained during the execution of the algorithm.

Secondly, we show primal feasibility (even when the prediction oracle provides
an infeasible solution). If the prediction oracle provides a feasible
solution, we set $S_{1}=\\{e:x^{\texttt{pred}}_{e}=1\\}$ and
$S_{2}=\emptyset$. Otherwise, let $e^{*}$ be the the first element for which
the prediction oracle provides an infeasible solution. Let $S_{1}$ be the set
of all resources $e$ such that $x^{\texttt{pred}}_{e}=1$ and $e$ is released
before $e^{*}$. Further let $S_{2}=\\{e:x^{\texttt{pred}}_{e}=1\\}\setminus
S_{1}$. For every constraint $i$,

$\displaystyle\sum_{e}b_{i,e}x_{e}$
$\displaystyle=\sum_{e:x^{\texttt{pred}}_{e}=1}b_{i,e}x_{e}+\sum_{e:x^{\texttt{pred}}_{e}=0}b_{i,e}x_{e}$
$\displaystyle=\sum_{e\in S_{1}}b_{i,e}x_{e}+\sum_{e\in
S_{2}}b_{i,e}x_{e}+\sum_{e:x^{\texttt{pred}}_{e}=0}b_{i,e}x_{e}$
$\displaystyle\leq\frac{1}{1+\eta}\cdot 1+\eta\cdot\sum_{e\in
S_{2}}\overline{b}_{i,e}x_{e}+\eta\cdot\sum_{e:x^{\texttt{pred}}_{e}=0}\overline{b}_{i,e}x_{e}$
$\displaystyle=\frac{1}{1+\eta}+\frac{\eta}{1+\eta}\sum_{e\in
S_{2}}\overline{b}_{i,e}y_{e}+\frac{\eta}{1+\eta}\sum_{e:x^{\texttt{pred}}_{e}=0}\overline{b}_{i,e}y_{e}$
$\displaystyle\leq\frac{1}{1+\eta}+\frac{\eta}{1+\eta}\sum_{e}\overline{b}_{i,e}y_{e}$
$\displaystyle\leq\frac{1}{1+\eta}+\frac{\eta}{1+\eta}\cdot 1=1.$

The first inequality is due to: (1) the feasibility of the prediction
restricted on $S_{1}$, i.e., $\sum_{e\in
S_{1}}b_{i,e}x^{\texttt{pred}}_{e}\leq 1$; and (2)
$x_{e}=\frac{1}{1+\eta}=\frac{1}{1+\eta}x^{\texttt{pred}}_{e}$ for $e\in
S_{1}$; and (3) the definitions of $\overline{b}_{i,e}$ in Algorithm 1. The
third equality follows by the algorithm: $x_{e}=\frac{1}{1+\eta}\cdot y_{e}$
for $e\notin S_{1}$. The last inequality holds since
$\sum_{e}\overline{b}_{i,e}y_{e}\leq 1$ by the observation made at the
beginning of the lemma. Hence, $\sum_{e}b_{i,e}x_{e}\leq 1$ for every
constraint $i$.

Besides, by definition of $z_{S}=\prod_{e\in S}x_{e}\prod_{e\notin
S}(1-x_{e})$ where $0\leq x_{e}\leq 1$ for all $e$, the identity
$\sum_{S}z_{S}=1$ always holds. In fact, if one chooses an element $e$ with
probability $x_{e}$ then $z_{S}$ is the probability that the set of selected
elements is $S$. So the total probability $\sum_{S}z_{S}$ must be 1.
Similarly, $\sum_{S:e\in S}z_{S}=x_{e}\sum_{S^{\prime}\subset
E\setminus\\{e\\}}\prod_{e^{\prime}\in
S^{\prime}}x_{e^{\prime}}\prod_{e^{\prime}\notin
S^{\prime}}(1-x_{e^{\prime}})=x_{e}$ since $\sum_{S^{\prime}\subset
E\setminus\\{e\\}}\prod_{e^{\prime}\in
S^{\prime}}x_{e^{\prime}}\prod_{e^{\prime}\notin
S^{\prime}}(1-x_{e^{\prime}})=1$ (by the same argument).

Therefore, the solution $(\bm{x},\bm{z})$ is primal feasible. $\Box$

###### Lemma 3

The dual variables defined as above are feasible.

_Proof_ The first dual constraint $\sum_{i}b_{i,e}\alpha_{i}\geq\beta_{e}$ is
satisfied by the while loop condition of the algorithm and the definition of
$\beta_{e}$. The second dual constraint $\gamma+\sum_{e\in S}\beta_{e}\geq
f(\bm{1}_{S})$ reads

$\displaystyle\frac{1}{\lambda}\sum_{e\in
S}\nabla_{e}F(\bm{y})+\frac{\mu}{\lambda}F(\bm{y})\geq F(\bm{1}_{S}),$

which is, by arranging terms, exactly the $(\lambda,\mu)$-max-local smoothness
of $F$. (Recall that $F(\bm{1}_{S})=f(\bm{1}_{S})$.) Hence, the lemma follows.
$\Box$

See 1 _Proof_

##### Robustness.

First, we bound the increases of $F(\bm{y})$ and of the dual objective value —
which we denote by $D$ — at any time $\tau$ in the execution of Algorithm 1.
The derivative of $F(\bm{y})$ with respect to $\tau$ is:

$\displaystyle\nabla_{e}F(\bm{y})\cdot\frac{dy_{e}}{d\tau}=\nabla_{e}F(\bm{y})\cdot\frac{1}{\nabla_{e}F(\bm{y})\cdot\ln(1+d\overline{\rho})}=\frac{1}{\ln(1+d\overline{\rho})}$

Besides, the rate of the dual at time $\tau$ is:

$\displaystyle\frac{dD}{d\tau}$
$\displaystyle=\sum_{i}\frac{d\alpha_{i}}{d\tau}+\frac{d\gamma}{d\tau}=\sum_{i:\overline{b}_{i,e}>0}\biggl{(}\frac{\overline{b}_{i,e}\cdot\alpha_{i}}{\nabla_{e}F(\bm{y})}+\frac{1}{d\lambda}\biggr{)}+\frac{\mu}{\lambda}\frac{dF(\bm{y})}{d\tau}$
$\displaystyle=\sum_{i:\overline{b}_{i,e}>0}\frac{\overline{b}_{i,e}\cdot\alpha_{i}}{\nabla_{e}F(\bm{y})}+\sum_{i:\overline{b}_{i,e}>0}\frac{1}{d\lambda}+\frac{\mu}{\lambda}\cdot\frac{1}{\ln(1+d\overline{\rho})}$
$\displaystyle\leq\frac{2}{\lambda}+\frac{\mu}{\lambda\cdot\ln(1+d\overline{\rho})}=\frac{2\ln(1+d\overline{\rho})+\mu}{\lambda\cdot\ln(1+d\overline{\rho})},$

where the inequality holds since during the algorithm
$\sum_{i}\overline{b}_{i,e}\cdot\alpha_{i}\leq\frac{1}{\lambda}\nabla_{e}F(\bm{y})$.
Hence, the ratio between $F(\bm{y})$ and the dual $D$ is at least
$\frac{\lambda}{2\ln(1+d\overline{\rho})+\mu}$.

Besides, $x_{e}=\frac{1}{1+\eta}\geq\frac{1}{1+\eta}y_{e}$ if
$x^{\texttt{pred}}_{e}=1$ and the predictive solution is still feasible; and
$x_{e}=\frac{1}{1+\eta}y_{e}$ otherwise. Therefore,
$\bm{x}\geq\frac{\bm{y}}{1+\eta}$ and so $F(\bm{x})\geq
F\bigl{(}\frac{\bm{y}}{1+\eta}\bigr{)}$ by monotonicity111Note that this is
the only step in the analysis we use the monotonicity of $f$, which implies
the monotonicity of $F$. of $F$. Hence the robustness is at least

$\frac{F(\bm{x})}{F(\bm{y})}\cdot\frac{\lambda}{2\ln(1+d\overline{\rho})+\mu}\geq\min_{\bm{0}\leq\bm{u}\leq\bm{1}}\frac{F(\frac{1}{1+\eta}\bm{u})}{F(\bm{u})}\cdot\frac{\lambda}{2\ln(1+d\rho/\eta)+\mu}$

where the latter is due to $\overline{\rho}\leq\rho/\eta$.

##### Consistency.

By our algorithm, for every element $e$, if $x^{\texttt{pred}}_{e}=1$ (and the
prediction oracle provides a feasible solution) then $x_{e}=\frac{1}{1+\eta}$.
Hence, the consistency of the algorithm
$F(\bm{x})/F(\bm{x}^{\texttt{pred}})\geq
F(\frac{\bm{x}^{\texttt{pred}}}{1+\eta})/F(\bm{x}^{\texttt{pred}})\geq
r(\eta)$. $\Box$

###  2.1 Applications

####  2.1.1 Applications to linear functions

When the objective $f$ can be expressed as a monotone linear functions, its
multilinear extension $F$ is $(1,1)$-locally-smooth. Moreover,
$r(\eta)=1/(1+\eta)$. Consequently, Algorithm 1 provides a
$1/(1+\eta)$-consistent and $O\bigl{(}1/\ln(1+d\rho/\eta)\bigr{)}$-robust
fractional solution for the online linear packing problem.

####  2.1.2 Applications to online submodular maximization

Consider the online problem of maximizing a monotone submodular function
subject to packing constraints. A set-function
$f:2^{\mathcal{E}}\rightarrow\mathbb{R}+$ is _submodular_ if $f(S\cup
e)-f(S)\geq f(T\cup e)-f(T)$ for all $S\subset T\subseteq\mathcal{E}$. Let $F$
be the multilinear extension of a monotone submodular function $f$. Function
$F$ admits several useful properties: (i) if $f$ is monotone then so is $F$;
(ii) $F$ is concave in any positive direction, i.e., $\nabla
F(\bm{x})\geq\nabla F(\bm{y})$ for all $\bm{x}\leq\bm{y}$ ($\bm{x}\leq\bm{y}$
means $x_{e}\leq y_{e}~{}\forall e$).

###### Lemma 4

Let $f$ be an arbitrary monotone submodular function. Then, its multilinear
extension $F$ is (1,1)-locally-smooth.

_Proof_ As $F$ is the linear extension of a submodular function,
$\nabla_{e}F(\bm{x})=\mathbb{E}_{R}\bigl{[}f\bigl{(}\bm{1}_{R\cup\\{e\\}}\bigr{)}-f\bigl{(}\bm{1}_{R}\bigr{)}\bigr{]}$
where $R$ is a random subset of $\mathcal{E}\setminus\\{e\\}$ such that
$e^{\prime}$ is included with probability $x_{e^{\prime}}$. For any subset
$S=\\{e_{1},\ldots,e_{\ell}\\}$, we have

$\displaystyle F(\bm{x})+\sum_{e\in S}\nabla_{e}F(\bm{x})$
$\displaystyle=F(\bm{x})+\sum_{e\in
S}\mathbb{E}_{R}\bigl{[}f\bigl{(}\bm{1}_{R\cup\\{e\\}}\bigr{)}-f\bigl{(}\bm{1}_{R}\bigr{)}\bigr{]}$
$\displaystyle=\mathbb{E}_{R}\biggl{[}f(\bm{1}_{R})+\sum_{e\in
S}\bigl{[}f\bigl{(}\bm{1}_{R\cup\\{e\\}}\bigr{)}-f\bigl{(}\bm{1}_{R}\bigr{)}\bigr{]}\biggl{]}$
$\displaystyle\geq\mathbb{E}_{R}\biggl{[}f(\bm{1}_{R})+\sum_{i=1}^{\ell}\bigl{[}f(\bm{1}_{R\cup\\{e_{1},\ldots,e_{i}\\}})-f(\bm{1}_{R\cup\\{e_{1},\ldots,e_{i-1}\\}})\bigr{]}\biggr{]}$
$\displaystyle=\mathbb{E}_{R}\bigl{[}f(\bm{1}_{R\cup
S})\bigl{]}\geq\mathbb{E}_{R}\bigl{[}f(\bm{1}_{S})\bigl{]}$
$\displaystyle=F\bigl{(}\bm{1}_{S}\bigr{)}$

the first inequality is due to the submodularity $f$ and the second one due to
its monotonicity. The lemma follows. $\Box$

###### Proposition 1

For any $0<\eta\leq 1$, Algorithm 1 gives a $(1-\eta)$-consistent and
$O\bigl{(}1/\ln(1+d\rho/\eta)\bigr{)}$-robust fractional solution to the
problem of online submodular maximization under packing constraints.

_Proof_ We first bound
$r(\eta)=\min_{\bm{0}\leq\bm{u}\leq\bm{1}}F(\frac{1}{1+\eta}\bm{u})/F(\bm{u})$.
By the non-negativity and the concavity in positive direction of $F$, for any
set $S\subseteq\mathcal{E}$,

$\displaystyle F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)}$ $\displaystyle\geq
F(\bm{u})-\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\bm{u}-\frac{\bm{u}}{1+\eta}\biggr{\rangle}$
(2) $\displaystyle F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)}$
$\displaystyle\geq F(\bm{0})+\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\frac{\bm{u}}{1+\eta}\biggr{\rangle}\geq\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\frac{\bm{u}}{1+\eta}\biggr{\rangle}.$
(3)

Therefore,

$\displaystyle\frac{F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)}}{F(\bm{u})}$
$\displaystyle\geq 1-\frac{\eta}{1+\eta}\cdot\frac{\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\bm{u}\biggr{\rangle}}{F(\bm{u})}$
(by (2)) $\displaystyle\geq
1-\frac{\eta}{1+\eta}\cdot\frac{\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\bm{u}\biggr{\rangle}}{F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)}}$
(by monotonicity of $F$) $\displaystyle\geq
1-\frac{\eta}{1+\eta}\cdot\frac{\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\bm{u}\biggr{\rangle}}{\biggl{\langle}\nabla
F\biggl{(}\frac{\bm{u}}{1+\eta}\biggr{)},\frac{\bm{u}}{1+\eta}\biggr{\rangle}}$
(by (3)) $\displaystyle=1-\eta.$

So, $r(\eta)\geq 1-\eta$. Therefore, the proposition holds by Theorem 1 and by
the (1,1)-locally-smoothness of $F$ (Lemma 4). $\Box$

One can derive online randomized algorithms for the integral variants of these
problems by rounding the fractional solutions. For example, using the online
contention resolution rounding schemes [14], one can obtain randomized
algorithms for several specific constraint polytopes, for example, knapsack
polytopes, matching polytopes and matroid polytopes.

##  3 Ad-Auction Revenue Maximization

##### Problem.

In the problem, we are given $m$ buyers, each buyer $1\leq i\leq m$ has a
budget $B_{i}$. Items arrive online and at the arrival of item $e$, each buyer
$1\leq i\leq n$ provides a bid $b_{i,e}\ll B_{i}$ for buying $e$. In the
integral variant of the problem, one needs to allocate the item to at most one
of the buyers. For every buyer, the total bids of the allocated items should
not exceed the budget. Note that this forms a packing constraint, similar to
the ones studied in the previous section, except that we don’t normalize the
constraints by the factor $1/B_{i}$. In the fractional variant of the problem,
items can be allocated in fractions to buyers, not exceeding a total of $1$
among the fractions. In both variants, the objective is to maximize the total
revenue received from all buyers, which is the sum over all allocations of
corresponding bid, possibly multiplied with the fraction of the allocation.

In out setting, every item $e$ arrives with a prediction, suggesting a buyer
to whom to allocate that item, if any. For convenience we denote the items by
the integers from $1$ to $n$.

###  3.1 The algorithm

##### Formulation.

The fractional variant of problem can be expressed as the following linear
program, where $x_{i,e}$ indicates the fraction at which item $e$ is allocated
to buyer $i$.

$\displaystyle\max\sum_{e=1}^{n}$ $\displaystyle\sum_{i=1}^{m}b_{i,e}x_{i,e}$
$\displaystyle\sum_{i=1}^{m}x_{i,e}$ $\displaystyle\leq 1$
$\displaystyle\forall e$ $\displaystyle(\beta_{e})$
$\displaystyle\sum_{e=1}^{n}b_{i,e}x_{i,e}$ $\displaystyle\leq B_{i}$
$\displaystyle\forall i$ $\displaystyle(\alpha_{i})$ $\displaystyle x_{i,e}$
$\displaystyle\geq 0$ $\displaystyle\forall i,e$

$\displaystyle\min\sum_{i=1}^{n}B_{i}\alpha_{i}$
$\displaystyle+\sum_{e=1}^{m}\beta_{e}$ $\displaystyle
b_{i,e}\alpha_{i}+\beta_{e}$ $\displaystyle\geq b_{i,e}$ $\displaystyle\forall
i,e$ $\displaystyle(x_{i,e})$ $\displaystyle\alpha_{i},\beta_{e}$
$\displaystyle\geq 0$ $\displaystyle\forall i,e$

In the primal linear program, the first constraint ensures that an item can be
allocated to at most one buyer and the second constraint ensures that a buyer
$i$ does not spend more than the budget $B_{i}$. The dual of the relaxation is
presented in the right.

##### Algorithm.

For the sake of simplicity in the algorithm description, we introduce a
fictitious buyer, denoted as $0$, such that $b_{0,e}=0$ for all items $e$. The
non-assignment of an item $e$ to any buyer can be seen as being assigned to
the fictitious buyer $0$ with revenue 0. The purpose of buyer $0$ is to
simplify the description of the algorithm. We define the constant
$C=(1+R_{\max})^{\frac{\eta}{R_{\max}}}$ where
$R_{\max}=\max_{i,e}\frac{b_{i,e}}{B_{i}}$. Adapting the primal-dual algorithm
presented in the previous section, we obtain the following algorithm for the
fractional ad-auction problem.

1: All primal and dual variables are initially set to 0.

2: For the analysis, we maintain for every buyer $i$ two sets $N(i),M(i)$,
both initially empty.

3: for each arrival of a new item $e$ do

4: Let $i^{*}$ be the buyer such that $x^{\texttt{pred}}_{i^{*},e}=1$. If
either the prediction is not feasible or there is no such $i^{*}$ (i.e.,
$x^{\texttt{pred}}_{i^{\prime},e}=0~{}\forall i^{\prime}$) then set $i^{*}=0$.

5: Let $i$ be the buyer that maximizes
$b_{i^{\prime},e}(1-\alpha_{i^{\prime}})$. If $b_{i,e}(1-\alpha_{i})\leq 0$
then set $i=0$.

6: Set $\beta_{e}\leftarrow\max\bigl{\\{}0,b_{i,e}(1-\alpha_{i})\bigr{\\}}$ #
for the purpose of analysis

7: if $b_{i,e}<b_{i^{*},e}$ then

8: Set $x_{i,e}\leftarrow\eta$ and $x_{i^{*},e}\leftarrow 1-\eta$.

9: Define $\overline{b}_{i,e}=b_{i,e}/\eta$

10: $N(i^{*})\leftarrow N(i^{*})\cup\\{e\\}$. # for the purpose of analysis

11: else

12: Set $x_{i,e}\leftarrow 1$ and define $\overline{b}_{i,e}=b_{i,e}$ #
includes case $\bm{x}^{\texttt{pred}}$ is infeasible

13: end if

14: Update $M(i)\leftarrow M(i)\cup\\{e\\}$. # for the purpose of analysis

15: Update
$\alpha_{i}\leftarrow\alpha_{i}\left(1+\frac{b_{i,e}}{B_{i}}\right)+\frac{b_{i,e}}{B_{i}}\cdot\frac{1}{C-1}$.

16: end for

Algorithm 2 Algorithm for Ad-Auctions Revenue Maximization.

###### Lemma 5

For every $i$, it always holds that

$\alpha_{i}\geq\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e\in M(i)}b_{i,e}}{\eta
B_{i}}}-1\biggr{)}.$

_Proof_ We adapt the proof in [9] with a slight modification. The primal
inequality $\alpha_{i}$ is proved by induction on the number of released
items. Initially, when no item is released, the inequality is trivially true.
Assume that the inequality holds right before the arrival of an item $e$. The
inequality remains unchanged for all but the buyer $i$ selected in line 5 of
the algorithm, i.e. $i$ maximizes $b_{i,e}(1-\alpha_{i})$. We denote by
$\alpha_{i}$ the value before the update triggered by the arrival of $e$ and
$\alpha^{\prime}_{i}$ its value after the update. We have

$\displaystyle\alpha^{\prime}_{i}$
$\displaystyle=\alpha_{i}\cdot\left(1+\frac{b_{i,e}}{B_{i}}\right)+\frac{b_{i,e}}{B_{i}}\cdot\frac{1}{C-1}$
$\displaystyle\geq\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e^{\prime}\in
M(i)\setminus e}b_{i,e}}{\eta
B_{i}}}-1\biggr{)}\cdot\left(1+\frac{b_{i,e}}{B_{i}}\right)+\frac{b_{i,e}}{B_{i}}\cdot\frac{1}{C-1}$
$\displaystyle=\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e^{\prime}\in
M(i)\setminus e}b_{i,e}}{\eta
B_{i}}}\cdot\left(1+\frac{b_{i,e}}{B_{i}}\right)-1\biggr{)}$
$\displaystyle\geq\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e^{\prime}\in
M(i)\setminus e}b_{i,e}}{\eta B_{i}}}\cdot C^{\frac{b_{i,e}}{\eta
B_{i}}}-1\biggr{)}$ $\displaystyle=\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e\in
M(i)}b_{i,e}}{\eta B_{i}}}-1\biggr{)}.$

The first inequality is due to the induction hypothesis. The second inequality
is due to this sequence of transformations. For any $0<y\leq z\leq 1$ we have

$\displaystyle\frac{\ln(1+y)}{y}$ $\displaystyle\geq\frac{\ln(1+z)}{z}$
$\displaystyle\Leftrightarrow\quad\ln(1+y)$ $\displaystyle\geq\ln(1+z)y/z$
$\displaystyle\Leftrightarrow\quad 1+y$ $\displaystyle\geq(1+z)^{y/z},$

which we apply with $y=b_{i,e}/{B_{i}}$ and $z=R_{\max}$. By the definition of
$C$ we obtain

$\biggl{(}1+R_{\max}\biggr{)}^{\frac{1}{R_{\max}}\cdot\frac{b_{i,e}}{B_{i}}}=C^{\frac{b_{i,e}}{\eta
B_{i}}}.$

This completes the induction step. $\Box$

###### Lemma 6

The primal solution is feasible up to a factor $(1+R_{\max})$.

_Proof_ The first primal constraint $\sum_{e}x_{i,e}\leq 1$ follows the values
of $x_{i,e}$ and $x_{i^{*},e}$ in Algorithm 2. For the second primal
constraint, we first prove that $\sum_{e=1}^{m}b_{i,e}\leq B_{i}$ for every
$i$. By Lemma 5, for every $i$,

$\alpha_{i}\geq\frac{1}{C-1}\biggl{(}C^{\frac{\sum_{e\in M(i)}b_{i,e}}{\eta
B_{i}}}-1\biggr{)}$

So whenever $\sum_{e\in M(i)}b_{i,e}\geq\eta B_{i}$, we have $\alpha_{i}\geq
1$; so the algorithm stops allocating items to buyer $i$. Hence, the buyer $i$
can be allocated at most one additional item once her budget is already
saturated. Hence, $\sum_{e\in M(i)}b_{i,e}<\eta B_{i}+\max_{e}b_{i,e}$.
Therefore,

$\displaystyle\sum_{e=1}^{m}b_{i,e}x_{i,e}=\sum_{e\in
M(i)}b_{i,e}x_{i,e}+\sum_{e\in N(i)}b_{i,e}x_{i,e}<B_{i}+\max_{e}b_{i,e}$

where the latter is due to the feasibility of $N(i)$, the set of items
assigned by the prediction to buyer $i$, i.e., $\sum_{e\in
N(i)}b_{i,e}x_{i,e}\leq(1-\eta)\sum_{e}b_{i,e}x^{\texttt{pred}}_{i,e}\leq(1-\eta)B_{i}$.
So, $\sum_{e=1}^{m}b_{i,e}x_{i,e}\leq B_{i}(1+R_{\max})$. $\Box$

###### Theorem 2

The algorithm is $(1-\eta)$-consistent and $\frac{1-1/C}{1+R_{\max}}$-robust.
The robustness tends to $1-e^{-\eta}$ when $R_{\max}$ tends to 0.

_Proof_ First, we establish robustness. At the arrival of item $e$, the
increase in the primal is

$\begin{cases}(1-\eta)\cdot b_{i^{*},e}+\eta\cdot b_{i,e}&\text{ if
}b_{i,e}<b_{i^{*},e},\\\ b_{i,e}&\text{ if }b_{i,e}\geq
b_{i^{*},e}\end{cases}$

which is always larger than $b_{i,e}$. Besides, the increase in the dual is

$\displaystyle B_{i}\Delta\alpha_{i}+\beta_{e}$
$\displaystyle=b_{i,e}\alpha_{i}+\frac{b_{i,e}}{C-1}+b_{i,e}(1-\alpha_{i})=\biggl{(}1+\frac{1}{C-1}\biggr{)}b_{i,e}=\frac{C}{C-1}.$

Hence, by Lemma 6, the robustness is $\frac{C-1}{C}\cdot\frac{1}{1+R_{\max}}$.

Secondly we establish consistency quite easily. At every time the prediction
solution gets a profit $b_{i^{*},e}$, the algorithm achieves a profit at least
$(1-\eta)b_{i^{*},e}$. $\Box$

###  3.2 Experiments

We run an experimental evaluation of Algorithm 2. Source code is publicly
available222http://www.lip6.fr/christoph.durr/packing. For this purpose we
constructed a random instance on 100 buyers and 10,000 items, adapting the
model described in [22]. Every item $e$ receives a bid from exactly 6 random
buyers. This means that in average every bidder makes 600 bids. The value of
the bid follows a lognormal distribution with mean $1/2$ and deviation $1/2$
as well. By choosing the budget of the bidders we can tune the hardness of the
instance, under the constraint that $R_{\max}$ remains reasonably small. We
choose the budget as a $1/10$ fraction of the total bids, leading to a value
$R_{\max}\approx 0.19$.

The competitive ratio is determined using the fractional offline solution. The
integrality gap of our instance is very close to $1$, roughly $1.0001$ in
fact. For the prediction, we computed first the optimal integral solution,
which is a partial mapping from items to buyers. This solution was perturbed
as suggested by [5]: Every item was mapped, with probability $\epsilon$, to a
uniformly chose random buyer, among the buyers who bid on the item.

The experiments are shown in Figure 1, and indicate clearly the benefit of the
prediction when its perturbation is small. Note that the ratio is not close to
$1$ in that case for $\eta$ close to zero, because the algorithm does not
follow blindly the prediction. Infeasibility of the prediction was detected at
82% of the input sequence for $\epsilon=0.01$ and at 64% for $\epsilon=0.1$.
As expected, with the performance degrades with the perturbation of the
prediction. Note that the observed robustness is not monotone in $\eta$,
unlike the bound shown in this paper. We think that this performance
degradation for $\eta$ around $1/2$ is due to the rather simplistic mixture
between the primal-dual solution and the predicted solution.

$0$$0.2$$0.4$$0.6$$0.8$$1$$0.7$$0.8$$0.9$$\eta$robustness$\epsilon=0$$\epsilon=0.01$$\epsilon=0.1$
Figure 1: Experimental evaluation

##  4 Conclusion

In the paper, we have presented primal-dual frameworks to design algorithms
with predictions for non-linear problems with packing constraints. Through
applications, we show the potential of our approach and provide useful
ideas/guarantees in incorporating predictions into solutions to problems with
high impact such as submodular optimization and ad-auctions. An interesting
direction is to prove lower bounds for non-linear packing problems in terms of
smoothness and confidence parameters.

## References

  * Angelopoulos et al. [2020] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault.  Online Computation with Untrusted Advice.  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_ , volume 151, pages 52:1–52:15, 2020.
  * Antoniadis et al. [2020] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In _International Conference on Machine Learning_ , pages 345–355, 2020.
  * Azar et al. [2016] Yossi Azar, Niv Buchbinder, TH Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Seffi Naor, and Debmalya Panigrahi.  Online algorithms for covering and packing problems with convex objectives.  In _Proc. Symposium on Foundations of Computer Science (FOCS)_ , 2016\.
  * Bach et al. [2013] Francis Bach et al.  Learning with submodular functions: A convex optimization perspective.  _Foundations and Trends® in Machine Learning_ , 6(2-3):145–373, 2013.
  * Bamas et al. [2020] Etienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In _Proc. 34th Conference on Neural Information Processing Systems_ , 2020.
  * Bian et al. [2017] Andrew An Bian, Kfir Levy, Andreas Krause, and Joachim M. Buhmann.  Continuous DR-submodular maximization: Structure and algorithms.  In _Neural Information Processing Systems (NIPS)_ , 2017.
  * Borodin and El-Yaniv [2005] Allan Borodin and Ran El-Yaniv.  _Online computation and competitive analysis_.  Cambridge University Press, 2005.
  * Buchbinder and Naor [2009a] Niv Buchbinder and Joseph Naor.  Online primal-dual algorithms for covering and packing.  _Mathematics of Operations Research_ , 34(2):270–286, 2009a.
  * Buchbinder and Naor [2009b] Niv Buchbinder and Joseph Naor.  The design of competitive online algorithms via a primal-dual approach.  _Foundations and Trends in Theoretical Computer Science_ , 3(2-3):93–263, 2009b.
  * Buchbinder et al. [2015] Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz.  A tight linear time (1/2)-approximation for unconstrained submodular maximization.  _SIAM Computing_ , 44(5):1384–1402, 2015.
  * Chekuri et al. [2014] Chandra Chekuri, Jan Vondrak, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  _SIAM Journal on Computing_ , 43(6):1831–1879, 2014.
  * Esfandiari et al. [2018] Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni.  Allocation with traffic spikes: Mixing adversarial and stochastic models.  _ACM Trans. Econ. Comput._ , 6(3–4), 2018.
  * Feldman et al. [2011] Moran Feldman, Joseph Naor, and Roy Schwartz.  A unified continuous greedy algorithm for submodular maximization.  In _Symposium on Foundations of Computer Science (FOCS)_ , pages 570–579, 2011.
  * Feldman et al. [2016] Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes.  In _Proc. 27th Symposium on Discrete Algorithms_ , pages 1014–1033, 2016.
  * Gollapudi and Panigrahi [2019] Sreenivas Gollapudi and Debmalya Panigrahi.  Online algorithms for rent-or-buy with expert advice.  In _International Conference on Machine Learning_ , pages 2319–2327, 2019.
  * Hsu et al. [2019] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian.  Learning-based frequency estimation algorithms.  In _Proc. Conference on Learning Representations_ , 2019.
  * Komm [2016] Dennis Komm.  _Introduction to Online Computation_.  Springer, 2016.
  * Kraska et al. [2018] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In _Proc. Conference on Management of Data_ , pages 489–504, 2018\.
  * Krause and Golovin [2014] Andreas Krause and Daniel Golovin.  Submodular function maximization.  In _Tractability: Practical Approaches to Hard Problems_ , pages 71–104. Cambridge University Press, 2014.
  * Kumar et al. [2018] Ravi Kumar, Manish Purohit, and Zoya Svitkina.  Improving online algorithms via ML predictions.  In _Proc. 32nd Conference on Neural Information Processing Systems_ , pages 9684–9693, 2018.
  * Lattanzi et al. [2020] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In _Proc. Symposium on Discrete Algorithms_ , pages 1859–1877, 2020\.
  * Lavastida et al. [2020] Thomas Lavastida, Benjamin Moseley, R Ravi, and Chenyang Xu.  Learnable and instance-robust predictions for online matching, flows and load balancing, 2020.
  * Lykouris and Vassilvtiskii [2018] Thodoris Lykouris and Sergei Vassilvtiskii.  Competitive caching with machine learned advice.  In _International Conference on Machine Learning_ , pages 3296–3305, 2018.
  * Mahdian et al. [2012] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi.  Online optimization with uncertain information.  _ACM Trans. Algorithms_ , 8(1), 2012.
  * Mehta [2013] Aranyak Mehta.  Online matching and ad allocation.  _Foundations and Trends® in Theoretical Computer Science_ , 8(4):265–368, 2013.
  * Mitzenmacher [2018] Michael Mitzenmacher.  A model for learned bloom filters, and optimizing by sandwiching.  In _Proc. Conference on Neural Information Processing Systems_ , pages 464–473, 2018.
  * Mitzenmacher [2020] Michael Mitzenmacher.  Scheduling with predictions and the price of misprediction.  In _Proc. 11th Innovations in Theoretical Computer Science Conference_ , 2020.
  * Mitzenmacher and Vassilvitskii [2020] Michael Mitzenmacher and Sergei Vassilvitskii.  _Beyond the Worst-Case Analysis of Algorithms_ , chapter Algorithms with Predictions.  Cambridge University Press, 2020.
  * Rohatgi [2020] Dhruv Rohatgi.  Near-optimal bounds for online caching with machine learned advice.  In _Proc. Symposium on Discrete Algorithms_ , pages 1834–1845, 2020\.
  * Roughgarden [2015] Tim Roughgarden.  Intrinsic robustness of the price of anarchy.  _Journal of the ACM_ , 62(5):32, 2015.
  * Roughgarden [2019] Tim Roughgarden.  Beyond worst-case analysis.  _Communications of the ACM_ , 62(3):88–96, 2019\.
  * Roughgarden [2020] Tim Roughgarden.  _Beyond the Worst-Case Analysis of Algorithms_.  Cambridge University Press, 2020.
  * Schild et al. [2019] Aaron Schild, Erik Vee, Manish Purohit, Ravi Kumar Ravikumar, and Zoya Svitkina.  Semi-online bipartite matching.  In _Proc. 10th Innovations in Theoretical Computer Science Conference_ , 2019.
  * Thang [2020] Nguyen Kim Thang.  Online primal-dual algorithms with configuration linear programs.  In _Proc. 31st International Symposium on Algorithms and Computation_ , 2020.
  * Vondrák [2010] Jan Vondrák.  Polyhedral techniques in combinatorial optimization.  Lecture notes, Nov 18 2010.
  * Williamson and Shmoys [2011] David P Williamson and David B Shmoys.  _The design of approximation algorithms_.  Cambridge University Press, 2011.