Mathias Staudigl
email: m.staudigl@maastrichtuniversity.nl

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

Convergent Noisy forward-backward-forward algorithms in non-monotone variational inequalities

Keywords: Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction Variational inequalites, Forward-Backward-Forward Algorithm, Stochastic Approximation, Variance Reduction

We develop a new stochastic algorithm with variance reduction for solving pseudomonotone stochastic variational inequalities. Our method builds on Tseng's forward-backwardforward algorithm, which is known in the deterministic literature to be a valuable alternative to Korpelevich's extragradient method when solving variational inequalities over a convex and closed set governed with pseudo-monotone and Lipschitz continuous operators. The main computational advantage of Tseng's algorithm is that it relies only on a single projection step, and two independent queries of a stochastic oracle. Our algorithm incorporates a variance reduction mechanism, and leads to a.s. convergence to solutions of a merely pseudo-monotone stochastic variational inequality problem. To the best of our knowledge, this is the first stochastic algorithm achieving this by using only a single projection at each iteration.

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T : R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.

(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define (z).

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF]. We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T :

R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.
(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).

probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP(z).
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF].

We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T : R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.

(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).

probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP(z).
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF]. We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T : R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.

(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).

probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP(z).
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF].

We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T :

R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.
(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).

probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP(z).
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF].

We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna

INTRODUCTION

Several applications in engineering, science, finance and economics lead to a broad range of optimization and equilibrium problems. Under suitable convexity assumptions, the equilibrium conditions of such problems can be compactly formulated as variational inequalities [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The standard deterministic variational inequality problem, denoted as VI(T, X ) ( or simply VI), is defined as follows: given a closed convex set X ⊂ R d and a single valued map T :

R d → R d , find x * ∈ X such that T (x * ), x -x * ≥ 0.
(VI) Call X * the set of solutions of VI(T, X ). The variational inequality problem includes many important applications in economics, game theory and engineering (see e.g. [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF]; [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic nash games[END_REF]; [START_REF] Kannan | Distributed computation of equilibria in monotone nash games via iterative regularization techniques[END_REF]; [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; [START_REF] Mertikopoulos | Stochastic mirror descent dynamics and their convergence in monotone variational inequalities[END_REF]). If X is unbounded it also can be used to model complementarity problems, systems of equations and saddle point problems.

In practice the evaluation of the map T (x) is corrupted by (numerical or random) noise, or it is derived from some other stochastic model, calling for a stochastic analysis of (VI). In the stochastic VI, we start with a measurable set (Ξ, A), a measurable function F : R d × Ω → R d , and a random variable ξ : (Ω, F) → (Ξ, A), defined on a

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).

probability space (Ω, F, P), such that F (x, ξ) ∈ L 1 (Ω; R d ). We let P P • ξ -1 be the law of the random variable ξ, and define

T (x) E ξ [F (x, ξ)] = Ξ F (x, z) dP(z).
(1)

The expected value formulation (EV) of the stochastic variational inequality problem, is to

find x * ∈ X s.t T (x * ), x -x * ≥ 0 ∀x ∈ X . (EV)
Since computing the expected value T (x) is rarely possible in practice, advanced stochastic methods for solving EV are formulated without recourse to the mean operator T , but rather directly involve the random variable F (x, ξ). Stochastic approximation (SA) theory is the mathematical tool to use in such settings. Recent advances have been made in deriving low complexity schemes for solving stochastic VIs using SA with variance reduction to solve EV even under weak pseudo-monotonicity assumptions on the operator T . These advances have been made via stochastic versions of Korpelevich's extragradient method [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF], which read as

Y n = Π X [X n -α n A n+1 ], X n+1 = Π X [X n -α n B n+1 ],
where A n+1 and B n+1 are random estimators of T (X n ) and T (Y n ), respectively. Convergence and computational complexity of this scheme has been thoroughly studied in [START_REF] Yousefian | Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems[END_REF]; [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. In this paper we present another competitive scheme, based on the forward-backward-forward (FBF) scheme of [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF].

We illustrate the practical advantage of our FBF scheme by tackling an energy efficiency problem in multi-antenna communication networks. A more detailed analysis is provided in [START_REF] Bot | On the convergence of stochastic forwardbackward-forward methods with variance reduction for stochastic variational inequalities[END_REF].

THE STOCHASTIC FORWARD-BACKWARD-FORWARD ALGORITHM

The standing hypothesis used in our analysis are summarized as follows. Hypothesis 1. (Consistency). X * = ∅. Hypothesis 2. (Stochastic Model). X ⊂ R d is closed convex, (Ξ, A) is a measurable space, with Borel σ-algebra A, and F : X × Ξ → R d is a Carathéodory map (i.e. continuous in x, measurable in ξ). ξ is a random variable with values in Ξ, defined on a probability space (Ω, F, P). Hypothesis 3. (Lipschitz continuity). The averaged map

T : X → R d is Lipschitz continuous with modulus L > 0. Hypothesis 4. (Pseudo-Monotonicity). The map T (x) E ξ [F (x, ξ)] is pseudo-monotone on R d : T (x), y -x ≥ 0 ⇒ T (y), y -x ≥ 0.
At each iteration, the decision maker has access to a stochastic oracle (SO), reporting an approximation of T (x) of the form

A n+1 (x) 1 m n+1 mn+1 i=1 F (x, ξ (i) n+1 ) x ∈ R d , ( 2
)
where

ξ n = (ξ (1) n , . . . , ξ (mn) n
) is an i.i.d draw from P. The sequence (m n ) n≥1 ⊂ N determines the sample rate, or batch size, of the SO. Hypothesis 5. (Batch Size). The batch size sequence (m n ) n≥1 satisfies

∞ n=1 1 mn < ∞.
A sufficient condition on the sequence (m n ) n≥1 to cope with Assumption 5 is that for some constant c > 0 and integer n 0 > 0, we have m n = c • (n + n 0 ) 1+a ln(n + n 0 ) 1+b , for a > 0 and b ≥ -1, or a = 0 and b > 0. Approximations of the form (2) have received considerable interest in machine learning and computational statistics (see e.g. [START_REF] Atchadé | On perturbed proximal gradient algorithms[END_REF]). Hypothesis 6. (Stepsize choice). The stepsize (α n ) n≥0 in Algorithm 1 satisfies

0 < inf n≥0 α n ≤ ᾱ = sup n≥1 α n < 1 √ 2L . ( 5
)
For n ≥ 0, we introduce the approximation error , W n+1 A n+1 -T (X n ), and

Z n+1 B n+1 -T (Y n ). (6)
The next hypothesis imposes a control on the SO's variance.

Hypothesis 7. (Variance Control

). There exists p ≥ 2, x * ∈ X * and σ(x * ) > 0 such that for all ). Define the filtration (F n ) n≥0 , by F 0 = σ(X 0 ), and

x ∈ R d E[ F (x, ξ) -T (x) p ] 1/p ≤ σ(x * ) + σ 0 x -x * . ( 7
F n = σ(X 0 , ξ 1 , ξ 2 , . . . , ξ n , η 1 , . . . , η n ).
Algorithm 1 Stochastic Tseng-Forward-Backward-Forward method (SFBF) Require: step-size sequence (α n ) n≥0 ; batch size sequence (m n ) n≥1 ; probability measure µ

1: initialize X 0 ∼ µ # initialization 2: for n ≥ 0 do 3: Given X n , draw ξ n+1 = (ξ (i) n+1 ) 1≤i≤mn+1 and η n+1 = (η (i) n+1 ) 1≤i≤mn+1 ∼ P 4: Oracle returns A n+1 = 1 mn+1 mn+1 i=1 F (X n , ξ (i) n+1 ). (3) # First Oracle query 5: Compute Y n = Π X (X n -α n A n+1 ) # Forward step 6: Oracle returns B n+1 = 1 mn+1 mn+1 i=1 F (Y n , η (i) n+1 ). ( 4
)
# Second Oracle query 7:

Compute

X n+1 = Y n + α n (A n+1 -B n+1 ) # Backward step 8: n ← n + 1
# next stage 9: end for Hypothesis (7), coupled with eqs. ( 3) and ( 4), imply an online variance reduction scheme, as illustrated in the following Lemma. Lemma 8. Let p ≥ 2 be as in Hypothesis 7. For all n ≥ 0, p ∈ [2, p] we have

E[ W n+1 p |F n ] 1 p ≤ C p (σ(x * ) + σ 0 X n -x * ) √ m n+1
and

E[ Z n+1 p |F n ] 1 p ≤ C p √ m n+1 σ(x * ) + C p σ 0 √ m n+1 E[ Y n -x * p |F n ] 1 p .
for universal constants C p > 0.

Proof. We proof both statements via the verification of a general result. Let N ∈ N and ξ (1) , . . . , ξ (N ) be an i.i.d sample from the measure P. Define the process

M N i (x)
N i=0 by M 0 (x) 0, and for 1

≤ i ≤ N M N i (x) 1 N i n=1 F (x, ξ (n) ) -T (x) .
We claim that, for all 1 ≤ q ≤ p, N ∈ N, and x ∈ R d , we have

E M N N (x) q 1 q ≤ C q √ N (σ(x * ) + σ 0 x -x * ).
For i ∈ {1, 2, . . . , N}, the monotonicity of L p (Ω, P) and (7) implies that

E ∆M N i-1 (x) q 1 q = 1 N E F (x, ξ (i) ) -T (x) q 1 q ≤ 1 N E F (x, ξ (i) ) -T (x) p 1 p ≤ σ(x * ) + σ 0 x -x * N .
Using this, together with the Burkholder-Davis-Gundy inequality [START_REF] Stroock | Probability Theory: An Analytic View[END_REF], there exists constants C q > 0 such that 2019 IFAC LSS Delft, The Netherlands, May 26-28, 2019

121 E M N N (x) q 1/q ≤ C q N k=1 E F (x, ξ (k) ) -T (x) N q 2/q ≤ C q (σ(x * ) + σ 0 x -x * ) √ N .

CONVERGENCE ANALYSIS

We can give a full convergence proof of the stochastic process {(X k , Y k ); k ∈ N} generated by SFBF (Algorithm 1). To measure the progress of the algorithm, we need to introduce a merit function. For our purposes, the most convenient choice for a merit function is the residual function r α (x) :

x -Π X (x -αT (x)) ∀x ∈ R d . ( 8
)
Define ρ n 1-2L 2 α 2 n for all n ≥ 0. Our analysis starts by verifying a stochastic quasi Fejér property of the sequence X n -x * 2 k≥0 . Lemma 9. For all x * ∈ X * , we have

E[ X n+1 -x * 2 |F n ] ≤ X n -x * 2 - ρ n 2 r αn (X n ) 2 + κ n m n+1 σ 2 0 X n -x * 2 + σ(x * ) 2 ,
where

κ n = α 2 n C 2 2 [2(4 + ρ n ) + 16(1 + α n L + σ 0 α n C 2 2 / √ m n+1 ) 2 ],
and C 2 > 0 is a constant.

Proof. Since the proof is quite long and tedious, we only outline the main steps. The full proof can be found in Bot ȩt al. (2019). We start with verifying the recursion

X n+1 -x * 2 ≤ X n -x * 2 - ρ n 2 r αn (X n ) 2 +∆U n (x * )+∆V n , where ∆V n V n+1 -V n = (4 + ρ n )α 2 n W n+1 2 + 4α 2 n Z n+1 2 ,
and ∆U n (x) 2α n Z n+1 , x -Y n . The proof of this recursive relation proceeds via several algebraic steps.

Step 1: By definition of a point x * ∈ X * , we have T (x * ), y -x * ≥ 0 ∀y ∈ X . Set y = Y n , and using α n > 0 as well as pseudomonotonicity (Hypothesis 4), we see

α n T (Y n ), Y n -x * ≥ 0 ∀n ≥ 0.
Using the Doob decomposition eq. ( 6), we can rewrite this inequality as

α n B n+1 , Y n -x * ≥ α n Z n+1 , Y n -x * . (9) Since Y n = Π X (X n -α n A n+1 ), properties of the euclidean projection tell us that x * -Y n , Y n -X n + α n A n+1 ≥ 0.
(10) Adding equations ( 9) and ( 10) and using the definition of the iterate X n+1 , gives

x * -Y n , X n+1 -X n ≥ α n Z n+1 , Y n -x * . ( 11
)
Step 2: For all n ≥ 0, using (11) and the definition of X n+1 in the last equality, we get

X n+1 -X n , X n+1 -x * = X n+1 -X n , Y n -x * + X n+1 -X n , X n+1 -Y n = α n Z n+1 , x * -Y n + X n+1 -X n 2 -X n -Y n 2 + α n A n+1 -B n+1 , X n -Y n This gives X n+1 -x * 2 = X n -x * 2 -X n+1 -X n 2 + 2 X n+1 -X n , X n+1 -x * ≤ X n -x * 2 + X n+1 -X n 2 -2 X n -Y n 2 + 2 α n Z n+1 , x * -Y n + 2α n A n+1 -B n+1 , X n -Y n .
Step 3: Using again the definition of X n+1 , we see

X n+1 -X n 2 = X n -Y n 2 + α 2 n A n+1 -B n+1 2 + 2α n A n+1 -B n+1 , Y n -X n ≤ X n -Y n 2 + 2α 2 n T (X n ) -T (Y n ) 2 + 2α 2 n W n+1 -Z n+1 2 + 2α n A n+1 -B n+1 , Y n -X n ≤ X n -Y n 2 + 2L 2 α 2 n X n -Y n 2 + 4α 2 n W n+1 2 + 4α 2 n Z n+1 2 + 2α n A n+1 -B n+1 , Y n -X n .
The first inequality is the Cauchy-Schwarz inequality.

The second inequality uses the L-Lipschitz continuity of the operator T (Hypothesis 3), as well as the fact that a -b 2 ≤ 2 a 2 + 2 b 2 . Combining this with the last inequality obtained in Step 2, we see that

X n+1 -x * 2 ≤ X n -x * 2 -(1 -2L 2 α 2 n ) X n -Y n 2 + 4α 2 n W n+1 2 + 4α 2 n Z n+1 2 + 2 α n Z n+1 , x * -Y n .
Step 4: By definition of the squared residual function, the definition of Y n , and the non-expansiveness of the euclidean projection, we have

r αn (X n ) 2 = X n -Π X (X n -α n T (X n )) 2 ≤ 2 X n -Y n 2 + 2 Y n -Π X (X n -α n T (X n )) 2 ≤ 2 X n -Y n 2 + 2 α n W n+1 2 . Hence, -2 X n -Y n 2 ≤ 2α 2 n W n+1 2 -r αn (X n ) 2 .
Step 5: Combining the last inequality from Step 4 with the last inequality from Step 3 (recalling the Step-size condition Hypothesis 6), we conclude

X n+1 -x * 2 ≤ X n -x * 2 - 1 2 (1 -2L 2 α 2 n )r αn (X n ) 2 + (1 -2L 2 α 2 n )α 2 n W n+1 2 + 4α 2 n W n+1 2 + 4α n Z n+1 2 + 2 α n Z n+1 , x * -Y n = X n -x * 2 - ρ n 2 r αn (X n ) 2 + (4 + ρ n )α 2 n W n+1 2 + 4α 2 n Z n+1 2 + 2 α n Z n+1 , x * -Y n = X n -x * 2 - ρ n 2 r αn (X n ) 2 + ∆V n + ∆U n (x * ).
Now take conditional expectations on both sides, taking into account that E[∆U n (x)|F n ] = 0, as well as the bound

E[∆V n |F n ] ≤ κ n m n+1 [σ 2 0 X n -x * 2 + σ(x *
) 2 ] which can be verified using Lemma 8.

Lemma 9 allows us to proof that the process (X n ) n≥0 converges a.s. to a random variable X with values in X * as a consequence of the Robbins-Siegmund Lemma, and general facts due to [START_REF] Combettes | Stochastic quasi-fejér block-coordinate fixed point iterations with random sweeping[END_REF].

The next proposition provides explicit norm bounds on the iterates (X n ) n≥0 in L 2 (P). These bounds are going to be crucial to assess the convergence rate and the per-iteration complexity of the method. Proposition 10. Consider Hypothesis 1-7. For all

x * ∈ X * let σ(x * ) := max{σ(x * ), σ 0 }, a(x * ) := σ2 (x * )ᾱ 2 C 2 2 c 1 . (12) Choose n 0 ∈ N and γ > 0 such that n≥n0 1 mn+1 ≤ γ, and β(x * ) γa(x * ) + γ 2 a(x * ) 2 ∈ (0, 1). (13) Then sup n≥n0 E[ X n -x * 2 ] ≤ E[ X n0 -x * 2 ] + 1 1 -β(x * ) . ( 14
)
Proof. We first remark that for every γ > 0 we can find an index n 0 ∈ N as required, thanks to Hypothesis 5. Call

ψ n (x * ) = E[ X n -x * 2 ].
From Proposition 9, we obtain

ψ n+1 (x * ) ≤ ψ n (x * ) - ρ n 2 E[r αn (X n ) 2 ] + κ n m n+1 [σ 2 0 ψ n (x * ) + σ(x * ) 2 ].
It is easy to see that there exists a constant c 1 > 1 such that

κ n ≤ ᾱ2 C 2 2 c 1 1 + ᾱ2 σ 2 0 C 2 2 m n+1 ≤ ᾱ2 C 2 2 c 1 (1 + a(x * ) c 1 m n+1
).

Using this bound, the previous display telescopes to

ψ n (x * ) ≤ ψ n0 (x * ) + n-1 i=n0 (1 + ψ i (x * )) a(x * ) m i+1 + n-1 i=n0 (1 + ψ i (x * )) a(x * ) 2 c 1 m 2 i+1 .
For p > ψ n0 (x * ), define τ p (x * ) inf{n ≥ n 0 |ψ n (x * ) ≥ p}.

We claim that there exists p > ψ n0 (x * ) such that τ p(x * ) = ∞. Suppose not. Then τ p (x * ) < ∞ for all p > ψ n0 (x * ). Therefore, by definition of τ p (x * ), and the definition of n 0 , we get

p ≤ ψ τp(x * ) (x * ) ≤ ψ n0 (x * ) + τp(x * )-1 k=n0 (1 + ψ k (x * )) a(x * ) m k+1 + τp(x * )-1 k=n0 (1 + ψ k (x * )) 1 c 1 a(x * ) m k+1 2 ≤ ψ n0 (x * ) + (1 + p)γa(x * ) + (1 + p) a(x * ) 2 γ 2 c 1 .
Rearranging, and using c 1 > 1 as well as (13), gives

p ≤ ψ n0 (x * ) + 1 1 -γa(x * ) -γ 2 c1 a(x * ) 2 ≤ ψ n0 (x * ) + 1 1 -γa(x * ) -γ 2 a(x * ) 2 .
Since p > ψ n0 (x * ) has been chosen arbitrarily, we can let p → ∞, to arrive at a contradiction. Therefore, there exits p > ψ n0 (x * ) such that p sup n≥n0 ψ n (x * ) ≤ p < ∞. Therefore, for all n ≥ n 0 we get

ψ n (x * ) ≤ ψ n0 (x * ) + n-1 k=n0 (1 + ψ k (x * )) a(x * ) m k+1 + n-1 k=n0 (1 + ψ k (x * )) 1 c 1 a(x * ) m k+1 2 ≤ ψ n0 (x * ) + (1 + p)γa(x * ) + (1 + p) a(x * ) 2 γ 2 c 1 .
Taking the supremum over n ≥ n 0 , and shifting back to the original expressions of the involved data, we get

p = sup n≥n0 E[ X n -x * 2 ] ≤ E[ X n0 -x * 2 ] + 1 1 -β(x * ) .
We now give explicit estimates on the convergence rate, exhibiting an optimal O(1/K) convergence rate in the mean-square residual function. This result is in line with the stochastic extragradient method (SEG) of [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]. Without loss of generality, we can assume a constant step size α

∈ (0, 1/ √ 2L). For n ∈ N, φ ∈ R, x * ∈ X * , define ρ = 1 -2L 2 α 2 , Γ n n i=0 1 m i+1 , Γ 2 n n i=0 1 m 2 i+1 , δ n (x * ) X n -x * 2
, and

H(x * , n, φ) 1 + max 0≤i≤n E[δ i (x * )] 1 -φ -φ 2 .
Theorem 11. Consider Assumptions 1-7. Let x * ∈ X * be arbitrarily. Choose φ ∈ (0,

√ 5-1
2 ) and n 0 = n 0 (x * ) to be the first integer such that i≥n0 1 mi+1 ≤ φ a(x * ) . Then, for all ε > 0, there exists

N ε ∈ N such that E[r α (X Nε ) 2 ] ≤ Λ ∞ (x * , φ) N ε , (15)
where, for all n ≥ 1,

Λ n (x * , φ) := 2 ρ E[δ 0 (x * )] + 2 ρ (1 + H(x * , n 0 (x * ), φ)) a(x * )Γ n + a(x * ) 2 Γ 2 n .
Proof. Choosing γ = φ a(x * ) and n 0 = n 0 (x * ) as required in the statement of the Theorem. We use Proposition 10, to get

sup n≥n0 E[δ n (x * )] ≤ 1 + E[δ n0 (x * )] 1 -φ -φ 2 ≤ H(x * , n 0 (x * ), φ). Calling H(x * , n 0 (x * ), φ) ≡ H(x * , φ), it follows sup n≥0 E[δ n (x * )] ≤ H(x * , φ). ( 16
)
Taking expectation and summing we get from Proposition 9 ρ 2

n i=0 E[r α (X i ) 2 ] ≤ E[δ 0 (x * )] + n i=0 κ i m i+1 σ(x * ) 2 + σ 2 0 E[δ i (x * )] .
First, using the variance bound σ(x * ) = max{σ(x * ), σ 0 }, we get

κ i ≤ α 2 C 2 2 c 1 1 + α 2 C 2 2 σ(x * ) 2 mi+1
. Second, calling

a(x * ) = α 2 σ(x * ) 2 C 2 2 c 1 , we get ρ 2 n i=0 E[r α (X i ) 2 ] ≤ E[δ 0 (x * )] + n i=0 a(x * ) m i+1 (1 + E[δ i (x * )]) + n i=0 1 c 1 a(x * ) m i+1 2 (1 + E[δ i (x * )]) ≤ 1 + max 0≤i≤n E[δ i (x * )] a(x * )Γ n + a(x * ) 2 Γ 2 n ,
2019 IFAC LSS Delft, The Netherlands, May 26-28, 2019

From ( 16), and c 1 > 1, we conclude

ρ 2 n i=0 E[r α (X i ) 2 ] ≤ E[δ 0 (x * )] + (1 + H(x * , φ)) a(x * )Γ n + a(x * ) 2 Γ 2 n = ρ 2 Λ n (x * , φ).
Hence,

n i=0 E[r α (X i ) 2 ] ≤ Λ n (x * , φ
) for all n ≥ 1, x * ∈ X * . For all ε > 0, we define the stopping time

N ε inf{n ≥ 0|E[r α (X n ) 2 ] ≤ ε}. (17) Choose n = min{N ε , k} -1 for k ∈ N, we know that min{Nε,k}-1 i=0 E[r α (X i ) 2 ] > ε min{N ε , k}. Since k ∈ N is chosen arbitrarily, we can let k ↑ ∞, so that εN ε ≤ Nε-1 i=0 E[r α (X i ) 2 ] ≤ Λ Nε-1 (x * , φ) ≤ Λ ∞ (x * , φ).
Since this bound holds for all x * ∈ X * , we conclude

N ε ≤ 1 ε inf x * ∈X * Λ Nε (x * , φ) ≤ inf x * ∈X * Λ ∞ (x * , φ). ( 18
)
Using the definition of the stopping time N ε in the above gives the desired result.

ENERGY EFFICIENCY IN MULTI-ANTENNA COMMUNICATIONS

Energy efficiency is one of the most important requirements for mobile systems, and it plays a crucial role in preserving battery life and reducing the carbon footprint of multi-antenna devices (i.e., wireless devices equipped with several antennas to multiplex and demultiplex received or transmitted signals). Following [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF]; [START_REF] Feng | A survey of energy-efficient wireless communications[END_REF]; [START_REF] Mertikopoulos | Learning to be green: Robust energy efficiency maximization in dynamic MIMO-OFDM systems[END_REF], we consider K wireless devices (e.g., mobile phones), each equipped with M transmit antennas and seeking to connect to a common base-station with N receiver antennas.

In this case, the users' achievable throughput (received bits/sec) is given by the familiar Shannon-Telatar capacity formula Telatar (1999):

R(X; H)

= log det Id + K k=1 H k X k H † k ( 19
)
where:

(1) X k ∈ C M is the input signal covariance matrix of user k and X = (X 1 , . . . , X K ) denotes their aggregate covariance profile (hence Hermitian positive semidefinite).

(2) H k ∈ C M ×N is the channel matrix of user k, representing the quality of the wireless medium between user k and the receiver.

(3) Id is the N × N identity matrix.

In practice, because of fading and other signal attenuation factors, the channel matrices H k are random variables, so the users' achievable throughput is given by R

(X) = E H [R(X; H)] ( 20
) where the expectation is taken over the law of H. The system's energy efficiency (EE) is then defined as the ratio of the users' achievable throughput per the unit of power consumed to achieved, i.e.,

EE(X) = R(X) K k=1 [P c k + P t k ] (21)
where

(1) P t k is the transmit power of the k-th device; by elementary signal processing considerations, it is given by P t k = tr(X k ). (2) P c k > 0 is a constant representing the total power dissipated in all circuit components of the k-th device (mixer, frequency synthesizer, digital-to-analog converter, etc.), except for transmission. For concision, we will also write P c = k P c k for the total circuit power dissipated by the system. The users' transmit power is further constrained by the maximum output of the transmitting device, corresponding to a trace constraint of the form tr(X k ) ≤ P max for all k = 1, . . . , K.

(22) Hence, putting all this together, we obtain the stochastic fractional problem: maximize EE(X) = R(X)

P c + K k=1 tr(X k ) subject to X k 0, tr(X K ) ≤ P max . ( 23
)
The EE objective of this problem (which, formally, has units of bits/Joule) has been widely studied in the literature [START_REF] Cui | Energyefficiency of MIMO and cooperative MIMO techniques in sensor networks[END_REF]; [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF] and it captures the fundamental trade-off between higher spectral efficiency and increased battery life. Importantly, switching from maximization to minimization, we also see that ( 23) is a fractional programming program of the form quadratic over linear, and hence quasi-convex. Therefore, it can be solved by applying SFBF: in fact, given the costly projection step to the problem's feasible region, SFBF seems ideally suited to the task.

We do so in a series of numerical experiments illustrated in Figure 1. Specifically, we consider a network consisting of K = 16 users, each with M = 4 transmit antennas, and a common receiver with N = 128 receive antennas. To simulate realistic network conditions, the users' channel matrices are drawn at each update cycle from a COST Hata radio propagation model with Rayleigh fading [START_REF] Hata | Empirical formula for propagation loss in land mobile radio services[END_REF]; to establish a baseline, we also ran an experiment with static, deterministic channels. For comparison purposes, we ran both SFBF and the SEG of [START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF] with the same variance reduction schedule, the same number of iterations, and step-sizes for both methods as α EG = α F BF / √ 3, and α F BF = 10/N . Also, to reduce statistical error, we performed S = 100 sample runs for each algorithm. We observe that SFBF performs consistently better than SEG, converging to a given target value between 1.5 and 3 times faster.

CONCLUSION

In a forthcoming publication [START_REF] Bot | On the convergence of stochastic forwardbackward-forward methods with variance reduction for stochastic variational inequalities[END_REF] we derive many more characteristics of the algorithm, including explicit bounds on the iterates, and error bounds. We also plan to extend the analysis to settings involving setvaluled operators, to capture applications to Generalized Nash equilibrium problems, as illustrated in [START_REF] Grammatico | Proximal dynamics in multiagent network games[END_REF].

Fig. 1 .

 1 Fig. 1. Comparison of the extra-gradient and FBF methods in problem (23). The top plot, considers static channels, and we ran SFBF and SEG with the same initialization. The plot below, illustrates ergodic channels following a Rayleigh fading model and we performed 100 sample runs for each algorithm; we then plotted a sample run, the sample mean, and the best and worst values at each iteration for each algorithm.

The authors acknowledge financial support from the COST Action CA16228 "European Network for Game Theory". P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR16CE33000401).


Nikolaos Liakopoulos
email: nikolaosliakopoulos<liakopoulosnp@gmail.com>.

Apostolos S Destounis

Georgios Paschos

Thrasyvoulos Spyropoulos

Panayotis Mertikopoulos

Cautious regret minimization: Online optimization with long-term budget constraints

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Consider the following bare-bones model of an online portfolio management problem: At each stage t = 1, 2, . . . , an investor places an investment over d diverse goods. This investment is modeled as a vector of unit bid prices x t = (x 1 t , . . . , x d t ), with each x i t representing the amount of money the investor is willing to pay for a unit of the i-th good -for instance, for an advertiser requesting ad space from different publishers, x i t would denote the cost-per-click (CPC). Based on the performance of each individual asset (e.g., the number of clicks), the investor pays a total cost as a function of x i t and a performance parameter p i t of the i-th asset, and concurrently collects a corresponding reward w t from their investment portfolio.

In our running example of online ad placement, the agent's utility u t (x t ; p t ) would be typically assumed concave in the agent's investment vector (to model diminishing returns), but otherwise stage-dependent, reflecting the variability of the performance parameter p i t of each investment. As such, utility maximization in this setting leads to an online optimization problem with the goal of maximizing the total reward T t=1 u t (x t ) accrued over T stages. A considerable complication arises in this problem when the agent also needs to balance their total investment against an allotted budget (daily, monthly, or otherwise). In more detail, assume that the agent must meet a long-term budget constraint of the form T t=1 c t ≤ b T , where c t = p t , x t denotes the total expenditure of the consumer at time t. Since the performance parameters p t are not known ahead of time (nor can they be assumed to follow a stationary probability law), techniques based on dynamic programming and optimal control cannot be applied in this context.

More generally, long-term budget constraints of this type can be formulated as T t=1 g t (x t ) ≤ 0 (1), where g t is a convex function representing the impact to the budget at time t. For instance, in our previous example, we have g t (x t ) = p t , x t -b T /T , so it simply represents the target T t=1 p t , x t ≤ b T . Importantly, these constraint functions are not only a priori unknown, but their evolution could even be adversarial: for instance, in online ad markets, competitors may click on ads to deplete their rivals' advertising budget, fraudulent publishers may attempt to manufacture revenue by increasing the click-through-rate (CTR) without legitimate buying intent, as shown in The Economist (2005).

In this way, we obtain the following archetype of an online optimization problem with long-term budget constraints: minimize T t=1 f t (x t ), subject to T t=1 g t (x t ) ≤ 0.

(2)

In the above, the problem's loss and constraint functions (f t and g t respectively) are assumed convex and Lipschitz

Paper

Constraint Benchmark window Regret Residual (a) Parameter Assumption [START_REF] Yuan | Online Convex Optimization for Cumulative Constraints[END_REF] Fixed on their definition domain, but are otherwise arbitrary. Our aim in the rest of this paper will thus be to a) quantify the trade-offs between regret minimization and budget violations in this setting; and b) propose online algorithms capable of achieving the problem's minimization objective while exceeding the allotted budget by a minimal amount.

T O( √ T + T /V ) O( √ V T ) V ∈ (1, T ) - Yu et al. (2017) Stochastic T O( √ T ) O( √ T ) St. Slater (b) Neely & Yu (2017) Adversarial 1 O( √ T ) O( √ T ) Slater (c) Sun et al. (2017) Adversarial 1 O( √ T ) O(T 3/4 ) - Mannor et al. (2009) Adversarial T Ω(T ) o(T ) - This paper Adversarial K O( √ T + KT /V ) O( √ V T ) V ∈ (K, T ) -

Related work

When the agent's action are constrained to lie on a fixed convex set X -i.e., in the absence of long-term constraints -standard methods based on online gradient/mirror descent enjoy an O( √ T ) bound on the incurred regret, as in [START_REF] Zinkevich | Online Convex Programming and Generalized Infinitesimal Gradient Ascent[END_REF]; Shalev-Shwartz (2012), which is well-known to be optimal in this setting, see [START_REF] Abernethy | Optimal Strategies and Minimax Lower Bounds for Online Convex Games[END_REF].

Beyond this classic regret minimization framework, the first work to examine online optimization problems with longterm budget constraints is [START_REF] Mahdavi | Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints[END_REF], where the constraint functions are the same for all t, i.e., the constraint is of the form t g(x t ) ≤ 0. For deterministic, non-adversarial constraints of this form, [START_REF] Mahdavi | Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints[END_REF] achieved O( √ T ) regret and an O(T 2/3 ) constraint residual (defined here as T t=1 g(x t )). These bounds were subsequently improved by [START_REF] Jenatton | Adaptive Algorithms for Online Convex Optimization with Long-Term Constraints[END_REF] to O(T max [β,1-β] ) and O(T 1-β/2 ) respectively, with β ∈ (0, 1) a free parameter, using varying stepsizes and regularization parameters. Finally, [START_REF] Yuan | Online Convex Optimization for Cumulative Constraints[END_REF] generalized these works by proving the same regret and O(T 1-β ) constraint residual for the tighter constraints

T t=1 ([g(x t )] + )
2 . All above works use roughly the same algorithm: at each round the dual variable of the long-term budget constraint is updated with g, and the algorithm takes a step along the (online) subgradient of the instantaneous augmented Lagrangian.

An alternative model to capture budget constraints (constraints on the resources consumed over time) is the framework of multi-armed bandits with concave rewards and convex knapsacks, presented in [START_REF] Agrawal | Bandits with Concave Rewards and Convex Knapsacks[END_REF]. In this framework, the decision space is a discrete set of arms and pulling an arm i t at round t generates a vector v t according to some fixed distribution. The objective is to satisfy a constraint on the average outcome vector vt = 1 T T t=1 v t while maximizing a reward function f (v T ). They extend the setting of [START_REF] Badanidiyuru | Bandits with Knapsacks[END_REF], where pulling an arm consumes some resource, stopping the process if the resource has been depleted, and prove near-optimal bounds for regret and constraint residual.

Moving on to time-varying constraint functions g t , [START_REF] Yu | Online Convex Optimization with Stochastic Constraints[END_REF] examined the case where the losses f t are adversarial but g t are stochastic (non-adversarial), drawn from some unknown (but otherwise stationary) distribution. They define the regret with respect to the best action that satisfies E [g t (x * )] < 0 at each round. Assuming such an action exists, a combination of OGD with a virtual queue playing the role of a dual relaxation variable guarantees a bound O( √ T ) on both regret and constraint residual.

In a concurrent line of work by [START_REF] Chen | An Online Convex Optimization Approach to Proactive Network Resource Allocation[END_REF] and [START_REF] Cao | Online Convex Optimization with Time-Varying Constraints and Bandit Feedback[END_REF], the performance of an online optimization algorithm is compared to that of an instantaneous minimizer of f t subject to g t (x) ≤ 0. As expected, regret guarantees against this dynamic comparator require very strong assumptions -for instance, that the variation of two consecutive constraint functions is bounded by the slack achieved by a static action over all constraint functions (the existence of such an action is already difficult to guarantee). 1

Our aim in this paper is to study online convex optimization problems with time-varying (and possibly adversarial) longterm budget constraints. In this general setting, prior work by [START_REF] Mannor | Online Learning with Sample Path Constraints[END_REF] provided a simple counterexample showing that the regret of any causal algorithm is lower bounded as Ω(T ); as such, achieving no regret is impossible if the functions defining the agent's budget are chosen by an adversary. More recently, Neely & Yu (2017) proved 1 We should mention here that our work can also be extended in this direction using the work of [START_REF] Besbes | Non-Stationary Stochastic Optimization[END_REF]. However, because we want to focus on regret minimization with minimal assumptions, we only use static comparators throughout. that a combination of OGD with a virtual queue can indeed provide no regret, compared to a static action that is strictly feasible for all functions g t , i.e., x * must satisfy g t (x * ) < 0 for all t = {1, . . . , T }. [START_REF] Sun | Safety-Aware Algorithms for Adversarial Contextual Bandit[END_REF] further proved that mirror descent on a properly augmented Lagrangian can achieve no regret even if the static action is just feasible. However, especially in an adversarial setting, this assumption might not be easy to achieve because, even a small degree of residual constraint violation injected by the adversary could disqualify any comparator action. More importantly, since x * is artificially constrained in this way, the obtained regret guarantee can be fairly loose.

A summary of the state of the art can be found in Table 1.

Our contributions

Our overarching objective is to examine the various tradeoffs between regret minimization and long-term budget constraint violations. Our first contribution in this direction is the introduction of a refined regret metric which compares the agent's incurred losses to those of a "K-benchmark", i.e., a comparator which meets the problem's allotted budget over any window of length K. In other words, a Kbenchmark comparator satisfies:

t+K-1 τ =t g τ (x) ≤ 0, ∀t ∈ {1, . . . , T -K + 1} (3)
and the "regret over a K-benchmark" compares the loss accrued by an online algorithm to that of the best Kbenchmark in hindsight.

By varying K, this refined regret metric provides sufficient flexibility to study the difficult question of adversarial longterm budget constraints. Specifically, letting K = T κ for some κ ∈ [0, 1], we recover the result of [START_REF] Mannor | Online Learning with Sample Path Constraints[END_REF] for κ = 1 (i.e., every causal algorithm is regretful in the long run). At the other end of the spectrum, for κ = 0i.e., K = Θ(1) -we recover the framework of Neely & Yu (2017), where no regret is achievable. In this way, we are led to the following fundamental questions: (i) What is the largest κ for which "no regret over K-benchmark" can be achieved? and (ii) For a given κ ∈ (0, 1), what is the regret guarantee for a given tolerance on the residual constraint violation?

Building on prior work by [START_REF] Jenatton | Adaptive Algorithms for Online Convex Optimization with Long-Term Constraints[END_REF], [START_REF] Yuan | Online Convex Optimization for Cumulative Constraints[END_REF], [START_REF] Yu | Online Convex Optimization with Stochastic Constraints[END_REF] and Neely & Yu (2017), we attack the first question by means of an online optimization policy which we call cautious online Lagrangian descent (COLD). As we show in the sequel, COLD achieves no regret over any benchmark of length K = T κ , for all κ ∈ [0, 1). Since no regret is impossible without further assumptions for κ = 1 , our result closes the gap with respect to achieving no regret with adversarial long-term budget con-straints. Finally, regarding the second question above, we show that the COLD algorithm can simultaneously achieve the tradeoffs

O(KT /V + √ T ) regret over K-benchmark and O( √ V T ) constraint residual
for any choice of V ∈ [K, T ). The "cautiousness parameter" V can be tuned by the optimizer and, in so doing, we derive the region of COLD relative to the trade-off between regret minimization and long-term residual constraint violation.

Our theoretical findings are also validated by a series of numerical experiments which suggest that increasing Kthat is, enlarging the window over which the budget must be balanced -makes the K-benchmark guarantee tighter. Hence, proving no regret for large K results in tighter performance guarantees -an observation which is not a priori obvious in a bona fide adversarial setting.

OCO with long-term budget constraints

To motivate the formal setup of the problem under study, we begin by discussing in more detail the online ad placement problem presented in Section 1.

Specifically, assume that, at every round, an advertiser chooses an investment vector of bid prices x t = (x 1 t , . . . , x d t ) over d different websites, with x i t denoting the cost-per-click (CPC) for the i-th website. It is implied that each website offers different deals for ad display with varying position prominence and frequency of display, and accordingly arranged prices per click. The ultimate cost of an investment in dollars is determined when the number of click(s) the ad receives (denoted here by p i t and measuring the performance of the corresponding investment) is revealed, and is equal to p t , x t . In this setting, the values of p i t fluctuate in an unpredictable manner -for instance, following website popularity, viewer interest, and/or possible attacks by competitors who click on an ad without a legitimate intent to buy, but only to increase the cost to the advertiser. As a result, satisfying the monthly budget given by t p t , x t ≤ b T is an adversarial long-term budget constraint of the form Eq.( 1).

The goal of the customer in this framework is to invest the available budget wisely. Specifically, the reward from ad display at site i also fluctuates unpredictably according to the website's popularity and the relation of the users to the advertised product (in some websites the value of a user click is higher since the user is more probable to become a customer). With these considerations in mind, the collected utility is given by an unknown concave function 2 u t (x t ) = i u i t (x i t ). The concavity of u t reflects the diminishing returns for a fixed website characteristic (e.g. making the ad more visible will attract proportionally less extra viewers). Needless to say, this task is very challenging because of the unpredictable fluctuations of price and reward, but also because an early aggressive choice might consume the budget resulting in missing out on opportunities towards the end of the horizon.

Problem formulation and assumptions

To state the above in a more formal framework, we will focus on the online optimization problem Eq.( 2) over a play horizon of t = 1, . . . , T rounds. In round t, the action x t ∈ X incurs f t (x t ) loss and impacts the budget by the amount g t (x t ). Here, functions f t and g t are not required to be differentiable and f t (x t ), g t (x t ) denote subgradients at x t . To analyze this problem we require the following basic assumptions.

(A1) The set X is convex and compact with diameter D. (A2) For all t = 1, . . . , T functions f t , g t : X → R are convex and Lipschitz, with f t 2 ≤ G and g t 2 ≤ G. (A3) For a given K ≤ T , consider the set of all actions that maintain a balanced budget within all windows of K rounds:

X K = x ∈ X : t+K-1 τ =t g τ (x) ≤ 0, 1 ≤ t ≤ T -K + 1
We assume that X K is non-empty.

Since X is compact and f t , g t Lipschitz, it follows that they are bounded, i.e., |f t (x)| ≤ F , |g t (x)| ≤ F , for all x ∈ X .

Assumptions A.1-A.2 are the blanket assumptions of all aforementioned OCO papers. A.3 is essential in order to define the regret metric that we use, and is significantly less stringent than the nonempty interior Slater assumption ∩ t {x : g t (x) < 0} of Neely & Yu (2017). For example, if g t are nonnegative the Slater assumption cannot hold. This case appears in problems where we want to ensure that a rate of failures does not cross a threshold, as in [START_REF] Yuan | Online Convex Optimization for Cumulative Constraints[END_REF].

Performance metric

We classify algorithms based on how they fare with respect to the constraint and the aggregate loss.

FEASIBILITY

Regarding the constraint Eq.(1), we take the common approach in the OCO literature, that of a relaxed notion of feasibility.

Definition 1 (Asymptotic feasibility). An algorithm is asymptotically feasible if it satisfies:

Ctr(T ) T t=1 g t (x t ) = o(T ).
An asymptotically feasible algorithm has the desirable property that it learns to produce a vanishingly small constraint residual T t=1 g t (x t ) over a large horizon T , i.e., we have T t=1 g t (x t )/T → 0 as T → ∞, and hence produces an asymptotically feasible solution of Eq.(2).

REGRET OVER K-BENCHMARK

The algorithmic efficiency is measured in OCO with the static regret: the aggregate loss difference between the algorithm and that of a benchmark action with hindsight. In our work, however, we encounter a further complication that does not appear in the literature. The appropriate regret definition must clarify how the benchmark action will behave with respect to the long-term budget constraint. To this end, we introduce the following family of benchmarks. Definition 2 (K-benchmark). Fix a K ∈ {1, . . . , T }. The K-benchmark x K * is an action that satisfies:

x K * ∈ argmin x∈X K T t=1 f t (x), (4)
where X K is defined in A.3.

This allows us to extend the definition of regret in the following manner. Definition 3 (Regret of x t over x K * ). Fix K ∈ {1, . . . , T }, and suppose x K * is a K-benchmark. The regret of x t over x K * is defined to be:

R K (T ) T t=1 f t (x t ) - T t=1 f t (x K * ).
Remark 1: If an asymptotically feasible online algorithm has no regret over x K * , it follows that the average losses R K (T )/T → 0 as T → ∞, which implies that our policy approximates the benchmark x K * under any sequence of functions, while additionally asymptotically satisfying the long-term budget constraint.

Remark 2: The actual guarantee provided by the novel regret criterion depends on K. As K increases, actions in X K must balance the budget in longer periods, and therefore become more aggressive. In fact, it can be checked that X 1 ⊆ X K , hence x 1 * ≤ x K * for all K. Consequently, a no regret guarantee over x K * is tighter than a no regret guarantee over x 1 * ; section 5 illustrates this with a numerical example. We are, therefore, motivated to prove no regret for as large K as possible.

Interestingly, however, for K > 1 the K-benchmarks are not necessarily monotonic in K as the next example shows.

Example 1 (Non-monotonicity of K-benchmark). Consider the ad display example with only one website. The Kbenchmark is the largest action x constrained to the use of Kb T /T budget within every K-round window. Given hindsight and prices p 1 , . . . , p T , and assuming non-increasing f t (i.e. more investment means larger utility and smaller loss), we have

x K * = Kb T T max t=0,...,T -K-1 t+K τ =t+1 p τ .
Consider the instance where T = 3, p = (10, 0, 8), and b T = 30. We have x 1 * = 1, x 2 * = 2, x 3 * = 5/3, and surprisingly x 2 * > x 3 * . The latter is due to that the window of size 3 has higher values than the mean at the two extremes.

The lack of monotonicity is indicative of a powerful adversary who can tweak functions g t to disturb the agent's algorithm in non-trivial ways. In spite of this complication, we present next a general algorithm that establishes no regret over x K * for any K = o(T ). Additionally, although a strong monotonicity result can not be established, in the numerical section we observe an improvement trend with increasing K, verifying the intuition that a larger window allows the agent to handle its budget in a better manner.

The algorithm

The main idea behind handling the long-term budget constraints is to weigh their importance against the loss in a Lagrangian fashion. Specifically, consider a regularized instantaneous Lagrangian for problem Eq.( 2) that takes the following form in round t:

L t (x, Q(t)) = V f t (x) + Q(t)g t (x) + α x -x t-1 2 , (5)
where a) V is a configurable cautiousness parameter; b) Q(t) is a virtual queue that plays the role of the Lagrangian multiplier; c) the term x -x t-1 2 is a L 2 regularizer that smoothens the differences between consecutive actions; and d) α is the strength of the regularization.

The main difference between Eq.( 5) and traditional Lagrangian relaxations is that the cautiousness parameter V can be used to control the tradeoff between regret and constraint residual (smaller V makes the algorithm more cautious); likewise, the regularization parameter α can be tuned to enhance the algorithm's robustness to fluctuations.

To estimate the value of the (otherwise unknown) functions f t and g t , we will employ their linear surrogates:

ft (x) f t-1 (x t-1 ) + f t-1 (x t-1 ), x -x t-1 , (6) ĝt (x) g t-1 (x t-1 ) + g t-1 (x t-1 ), x -x t-1 . (7) Let L t (x, Q) denote the subgradient of L t (x, Q(t)) at x.
Plugging the above surrogate terms in Eq.( 5) and using basic subgradient algebra, we get:

L t (x, Q) = V f t-1 (x t-1 )+Q(t)g t-1 (x t-1 )+2α(x-x t-1 )
Our algorithm is designed to compute a stationary point of L t in round t, and then project it on X , while updating queue Q(t + 1) with the surrogate ĝt (x t ). The latter is in fact the subgradient of L t (x, Q) with respect to Q.

Cautious Online Lagrangian Descent (COLD)

For t = 1, . . . , T :

xt = ΠX xt-1 - V f t-1 (xt-1) + Q(t)g t-1 (xt-1) 2α (8)
Q(t + 1) = [Q(t) + ĝt(xt)] + . ( 9
)
with initialization Q(1) = 0, x 0 ∈ X , and where:

• Π X [.] denotes the Euclidean projection on set X , • V is the configurable cautiousness parameter,

• f t-1 , g t-1 are the subgradient vectors in round t -1,

• Q(t) is a virtual queue that is updated according to Eq.( 9), and it is called the predictor queue, • α is the configurable regularization strength parameter, • ĝt (x t ) is the surrogate of g t (x t ) from Eq.( 7),

• [.] + is max{., 0},
We remark that if we fix Q(t) = 0, ∀t, COLD reduces to the OGD of [START_REF] Zinkevich | Online Convex Programming and Generalized Infinitesimal Gradient Ascent[END_REF] with stepsize V /2α, which however would fail to address the long-term budget constraints. In what follows, we provide the logical steps that are used in the design of COLD, as well as to prove its performance guarantees. The same steps can be used to derive variations of COLD for different problems.

Regularized drift plus loss framework

The framework is inspired by the unification of two theories, namely the theory of stochastic network optimization, explained in Neely (2010a), that handles time-average constraints by stabilizing virtual queues; and the standard framework of OCO, described in [START_REF] Zinkevich | Online Convex Programming and Generalized Infinitesimal Gradient Ascent[END_REF]; Shalev-Shwartz (2012); [START_REF] Belmega | Online Convex Optimization and No-Regret Learning: Algorithms, Guarantees and Applications[END_REF].

Our mathematical analysis is based on an instantaneous metric called drift plus loss plus smoothness (DPLPS), which at each round measures the quality of an action by weighing three competing factors: (i) the quadratic Lyapunov drift of the predictor queue (which reflects the urgency of the constraint), (ii) the predicted instantaneous loss, and (iii) the L 2 regularizer to smoothen the changes in the sequence of actions. The values of all three above depend on the action x t , and we will show that our algorithm arises as the action that minimizes an upper bound of the DPLPS. The remaining of this subsection provides further detail.

We first define the quadratic Lyapunov drift as the change in the quadratic predictor queue length after action x t is taken:

∆(xt) 1 2 [Q 2 (t + 1) -Q 2 (t)]. (10)
Since x t determines ĝt (x t ), it implicitly affects ∆(x t ) via Q(t + 1), see Eq.( 9). By taking actions to minimize the drift ∆(x t ) we may keep the queue length small at the end of the horizon. We will then show that a bound on Q(T ) can be manipulated into proving asymptotic feasibility. In summary, the minimization of ∆(x t ) at each round pushes towards actions that satisfy the long-term budget constraint.

From the literature of stochastic network optimization (Neely (2010a)), the drift can be combined with the instantaneous loss (here adapted to its surrogate from Eq.( 6)): ∆(x t ) + V ft (x t ). Minimizing this weighted metric pushes towards actions that simultaneously satisfy the long-term budget constraints and achieve low aggregate loss in the stochastic setting, see Neely (2010b). However, such algorithms have a bang-bang behavior, oscillating between extreme actions, which is inappropriate for many real applications. Therefore, in this work we further add the L 2 regularizer (following the methodology of Neely & Yu (2017)), which brings us to the DPLPS metric:

DP LP S(x t ) ∆(x t )+V ft (x t )+α||x t -x t-1 || 2 2 . (11)
With some work on the definition of the Lyapunov drift (see also Lemma 4.2 in Georgiadis et al. ( 2006)), we have:

∆(x t ) ≤ B + Q(t)ĝ t (x),
where B (F + GD) 2 /2 is a constant. Therefore, we get

DP LP S(x) ≤ B + V ft(x) + Q(t)ĝt(x) + α||x -xt-1|| 2 2 r t (x)
.

Observe that the term r t (x) equals Eq.( 5), plus a constant B. The following Lemma proves formally that r t (x) is minimized by COLD at each round.

Lemma 1 (DPLPS bound minimizer). COLD minimizes r t (x) at each round.

Proof. First, observe that by definition our policy is:

x t Π X x t-1 + H t 2α ,
where H t is the following constant:

H t V f t-1 (x t-1 ) + Q(t)g t-1 (x t-1 ).
It suffices to show that this projection actually returns a minimizer of r t (x).

We have that, H t , x t -x t-1 = Q(t) g t-1 (x t-1 ), (x tx t-1 ) + V f t-1 (x t-1 ), (x t -x t-1 ) . Hence:

xt = argmin x∈X {rt(x)} (a) = argmin x∈X { Ht, x -xt-1 + α||x -xt-1|| 2 2 } (b) = argmin x∈X Ht, x -xt-1 + α||x -xt-1|| 2 2 + H 2 t 4α = argmin x∈X Ht 2 √ α + √ α(x -xt-1) 2 2 = argmin x∈X x -xt-1 - Ht 2α 2 2 (c) = ΠX xt-1 - Ht 2α .
In (a) we discard the terms that do not depend on x. In (b) we add a constant term that completes the square norm but does not change the minimizer. Finally, (c) is the definition of Euclidean projection on set X completing the proof.

This methodology constitutes a powerful framework, where for a new problem we may define appropriate virtual queues for the constraints, determine the corresponding DPLPS metric, and then extract asymptotically feasible online algorithms by minimizing a bound on the DPLPS. In the technical proofs, we show how this bound minimization can be used to derive the performance guarantees of our algorithm.

Performance analysis

In this section we provide our main theoretical results, which characterize the performance of COLD algorithm. Recall that T is the horizon, V, α are configurable parameters, F, G are universal constants (see section 2.1), D is the diameter of set X , and B = (F + GD) 2 /2. Proposition 1 (COLD performance). If the assumptions in Sec. (2.1) are satisfied, and actions are taken according to the COLD algorithm, the constraint residual is bounded by:

Ctr(T ) T t=1 gt(xt) ≤ 2BKT + 4F V T + V 2 G 2 T α + 2αD 2 + 2BK 2 + 2(T + 1)BK 1 2 + GV T 2α + G 2 √ 2BK + √ 4F V + V 2 G 2 α + √ 2BK T 3 2 +T √ 2 2α + G 2 √ 2αD 2 + √ 2BK 2 + √ 2BK T 2α (12)
and the regret over the K-benchmark is bounded by: Based on the above fundamental bounds, we optimize the parameters V, α to get a region of achievable asymptotic laws, such that both the constraint residual and the regret are o(T ). In general, we may choose the value of parameter V in the range (K, T ) and different choices provide different tradeoffs. For instance, choosing V close to K makes the algorithm cautious and provides the best guarantees on the constraint residual, while choosing it close to T makes the algorithm to aggressively pursue the best regret. Theorem 1 (Achievable tradeoffs). Fix K ≥ 1 such that K = o(T ) (higher K makes the K-benchmark tighter). Choose some V ∈ (K, T ), and α = max{T, V √ T }. Then, Eq.( 12)-( 13) simplify to:

RK (T ) T t=1 ft(xt) - T t=1 ft(x K * ) ≤ BKT V + G 2 V T 2α + (13)
+ B (K + 1)(2K + 1) 6V + D 2 α V + 2F (K -1). k = 1 k = 0.8 k = 0.6 k = 0.4 k = 0.2 k = 0 T T 1- T 1- √ T √ T RK (
O(KT /V + √ T ) regret over K-benchmark and O( √ V T ) constraint residual
Furthermore, suppose K = T 1-for some small > 0 and choose V = T 1-2 , and α = V √ T . Then, Eq.( 12)-( 13) simplify to: /4 ). The blue dotted line shows the tradeoffs achieved by [START_REF] Yuan | Online Convex Optimization for Cumulative Constraints[END_REF], which interestingly coincide with our case of K = 1, though we mention that they address fixed (non-adversarial) constraints. Finally, note that for = 1, we retrieve the result of [START_REF] Sun | Safety-Aware Algorithms for Adversarial Contextual Bandit[END_REF]. On the other hand, the point O( √ T ), O( √ T ) achieved by Neely & Yu (2017) for K = 1 is not part of our achievable guarantees; we attribute this gap to the stricter Slater assumption studied by Neely & Yu (2017).

O(T 1-2 ) regret over T 1--benchmark

Outline of the proofs

The technical proofs of Prop.(1) and Th.(1) are deferred to the appendix (in supplemental material) due to space limitations. Here, we provide a brief outline.

The COLD algorithm is designed to minimize the DPLPS, hence one can directly compare it to the 1-benchmark, as for example in Neely & Yu (2017). The novel element in our analysis is that we compare K steps of DPLPS of COLD to the DPLPS of the K-benchmark (Def.( 2)). This comparison forms the basis of our analysis, and it is given in Lem.( 8) and Cor.(2) in the appendix (in supplemental material).

First, based on the feasibility of the K-benchmark in windows of size K, we establish a bound on Q(t) of COLD for any t ∈ {1, . . . , T + 1}. The bound builds on the above-explained comparison between COLD and the K-benchmark. Then, the bound on Q(t) is manipulated into proving the upper bound on the constraint residual Eq.( 12). We note that an important part of the proof is to obtain a good upper bound of T t=1 Q(t). A similar strategy is used in comparing the losses of COLD to those of the K-benchmark and proving the regret bound Eq.( 13).

We mention that the bound on Q(t) can be strengthened if we make the Slater assumption, i.e., assume the existence of a vector x * such that g t (x * ) < -η, ∀t. In particular, this is the approach taken by Neely & Yu (2017) achieving the point (O( √ T ), O( √ T )) for K = 1. In our case, we would assume the existence of actions satisfying t+K-1 τ =t g τ (x) < -η, ∀t, with which we could improve further the bounds on Q(t), T t=1 Q(t) and eventually our Proposition. In this work, we chose to present the most general bounds, and left this direction for future research.

Finally, regarding the proofs of Th.(1), our strategy is to restrict progressively the values of K, α, and V , such that both Ctr(T ) and R K (T ) are o(T ). An optimization over parameters α, V provides the presented trade-offs.

Numerical results

In this section we test COLD and the performance guarantees given by K-benchmarks on an instance of our example application of online ad placement. We also showcase the effect of the cautiousness parameter V on COLD's utility and constraint residual.

Accuracy of performance guarantee

We simulate a scenario with one website, where x t ∈ [0, ∞), f t (x t ) = -w t x t , and g t (x t ) = p t x t -b T /T , where w t , p t are generated by exponential distributions w t ∼ Exp(11) and p t ∼ Exp(10). We run the experiment for different horizons T = {2000, 4000, . . . , 10000}, budget b T = 300T , and parameters set to α = max{T, V √ T } and V = T 0.99 for each of the experiments. Fig. (2(a)) shows the utility (minus the loss) for the 1-benchmark (Neely & Yu (2017)), the T 0.9 -benchmark (an instance of this paper) and finally the utility achieved by the COLD algorithm.

In Fig.

(2(a)) we observe that COLD's utility is approximated much more accurately by the T 0.9 -benchmark than by 1-benchmark. In fact, the approximation by the 1- benchmark becomes even worse as T increases. Since proving no regret over K-benchmark essentially bounds the algorithm's losses, we conclude that the importance of the regret guarantee lies with how large K is.

In a similar experiment, Fig.

(2(b)) presents the relative excess loss of the K-benchmark with respect to the Tbenchmark, for all values of K = 1, . . . , T . This relative excess loss is depictive of the approximation error of a Kbenchmark with respect to the T -benchmark. We remind the reader that the excess loss is due to constraining the benchmark action to be feasible on a window that is K < T , and that the regret guarantees can be established for K = o(T ) only. The points are averages over 150 sample paths. Due to averaging over sample paths we observe a monotonous decrease of excess loss as K increases and more importantly that the 1-benchmark can have as much as 85% excess loss.

On Fig.

(2(c)), we observe that a K-benchmark that scales sublinearly with the horizon (K = o(T )) has a much better approximation compared to a constant K, like K = 1, which is very pessimistic even for moderate values of T . All the above experiments support that intuition that taking K large produces a tighter regret guarantee.

Impact of the Cautiousness Parameter V

In this subsection we explore the effect of the cautiousness parameter V on the performance of COLD algorithm. On the same example as before, we choose K = T 3/4 and V = {T 1/2 , T 3/4 , T 0.99 , T 5/4 }. In our theoretical analysis, we have proven that V has to be greater than K to achieve no regret. On ) that, for V > T , the constraint residual is not sub-linear to the horizon T , which is in accordance to our bounds.

On the other hand when K < V < T , indeed the constraint residuals are sub-linear and the average utility approximates the utility of the K-benchmark. Increasing V up to T , one can observe in Fig.

(3) the different tradeoffs between the regret and the constraint residual.

Conclusion

In this paper we study OCO with long-term budget constraints. In particular, we deal with the case where the constraints are adversarial, which captures the scenario where the long-term budget constraint must be addressed in the presence of poor prediction quality. We introduce the Kbenchmark, which allows us to refine the regret metric used to provide performance guarantees for online algorithms.

Although for K = T prior work has established that no algorithm can provide no regret, we prove that the COLD algorithm achieves no regret for any K = o(T ). Our numerical results suggest that a K-benchmark with K large can provide a more accurate performance guarantee than the previous state of the art K = 1. Finally, we provide a new region of regret-constraint residual tradeoffs that characterize the performance of COLD in the general setting.

  (a) Residual refers to the long-term budget constraint violation. (b) Stochastic Slater assumes there exists an action x * ∈ X such that E [gt(x * )] < 0 for all t. (c) Slater assumes there exists an action x * ∈ X such that gt(x * ) < 0 for all t.

Figure 1 .

 1 Figure 1. Achievable bounds for K = T k , k = 0 : 1 : 0.2.

  we illustrate the results of Th.(1): the black curves indicate the Pareto frontier for different values of K = T k so all the values north-east of the frontier are achievable. As K → T , the Pareto frontier vanishes to the north-east corner point O(T 1-/2 ), O(T 1-

Figure 2 .

 2 Figure 2. Simulations of the example of online ad placement. (a) COLD utility comparison versus 1-benchmark and T 0.9 -benchmark. (b) Relative excess loss of K-benchmark compared to T -benchmark. (c) Utilities of K-benchmark for different values of K.

  Fig.(3(b)) the running average utility for V = T 1/2 indeed fails to reach the benchmark. Furthermore, we can deduce from Fig.(3(a)

Figure 3 .

 3 Figure 3. Running averages of constraint residual and utility performance of COLD for different values of parameter V .

Table 1 .

 1 State of the art results in OCO with long-term budget constraints. All papers assume ft, gt are convex and Lipschitz continuous.

The DR-submodular reward functions[START_REF] Chen | Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity[END_REF] could be an interesting generalization capturing diminishing returns, but incorporating constraints is still an open problem.