title: Stochastic approximation of CVaR-based variational inequalities
authors: Jasper Verbree Ashish Cherukuri
text: 
  
  CMB-S4: Forecasting Constraints on Primordial Gravitational Waves
      
  
  
  CMBSFourAffiliationCount
  
  UCIrvine
  JohnsHopkinsUniversity
  UniversityofIllinoisatUrbana-Champaign
  SLAC
  UCBerkeley
  StanfordUniversity
  OxfordUniversity
  LawrenceBerkeleyNationalLaboratory
  RiceUniversity
  Fermilab
  UCSanDiego
  SISSA
  IFPU
  INFN
  HarvardUniversityCFA
  UniversityofNewMexico
  ArgonneNationalLaboratory
  AstroParticleandCosmologyLaboratory
  Caltech
  CornellUniversity
  KICP
  UniversityofChicago
  UniversityofMelbourne
  UniversityofCincinnati
  JPL
  LMUMunich
  UTAustin
  CITA
  InstitutdAstrophysiquedeParis
  StonyBrookUniversity
  UniversityofManchester
  ArizonaStateUniversity
  FloridaStateUniversity
  CardiffUniversity
  DartmouthCollege
  UniversityofGeneva
  UniversityofSussex
  UniversityofCambridge
  KavliInstituteforCosmologyCambridge
  IoA
  UniversityofTokyo
  UniversityofGroningen
  UniversityofToronto
  Dunlap
  KEK
  CEASaclay
  USTCH
  UniversityofPennsylvania
  McGillUniversity
  NIST
  PrincetonUniversity
  HarvardUniversity
  NASAGoddardSpaceFlightCenter
  SimonFraserUniversity
  UniversityofSouthernCalifornia
  HaverfordCollege
  StockholmUniversity
  CaseWesternReserveUniversity
  UniversityofBritishColumbia
  UniversityofColoradoBoulder
  UniversityofMinnesota
  UniversityofMichigan
  FlatironInstitute
  Columbia
  UniversityofVirginia
  KavliIPMU
  UCDavis
  YaleUniversity
  UniversityofPittsburgh
  BenGurionUniversity
  AaltoUniversity
  UCSantaBarbara
  PerimiterInstitue
  SouthernMethodistUniversity
  BerkeleyCenterforCosmologicalPhysics
  EuropeanSouthernObservatory
  GRAPPA
  WashingtonUniversitySt.Louis
  McDonnellCenterfortheSpaceSciencesWashingtonUniversity
  UniversityofMilano-Bicocca
  CentredePhysiquedesParticulesdeMarseille
  KIPAC
  InstituteforAdvancedStudy
  PennsylvaniaStateUniversity
  BrookhavenNationalLaboratory
  KyotoUniversity
  UniversityofWisconsinMadison
  UniversitedegliStudidiMilan
  ICJLab
  BrownUniversity
  SyracuseUniversity
  UCLosAngeles
  MSU
  The CMB-S4 Collaboration:
  Kevork Abazajian,<ref>
  Graeme E. Addison,<ref>
  Peter Adshead,<ref>
  Zeeshan Ahmed,<ref>
  Daniel Akerib,<ref>
  Aamir Ali,<ref>
  Steven W. Allen,<ref>
  David Alonso,<ref>
  Marcelo Alvarez,<ref>,<ref>
  Mustafa A. Amin,<ref>
  Adam Anderson,<ref>
  Kam S. Arnold,<ref>
  Peter Ashton,<ref>
  Carlo Baccigalupi,<ref>,<ref>,<ref>
  Debbie Bard,<ref>
  Denis Barkats,<ref>
  Darcy Barron,<ref>
  Peter S. Barry,<ref>
  James G. Bartlett,<ref>
  Ritoban Basu Thakur,<ref>
  Nicholas Battaglia,<ref>
  Rachel Bean,<ref>
  Chris Bebek,<ref>
  Amy N. Bender,<ref>,<ref>
  Bradford A. Benson,<ref>,<ref>,<ref>
  Federico  Bianchini,<ref>
  Colin A. Bischoff,<ref>
  Lindsey Bleem,<ref>,<ref>
  James J. Bock,<ref>,<ref>
  Sebastian Bocquet,<ref>
  Kimberly K. Boddy,<ref>,<ref>
  J. Richard Bond,<ref>
  Julian Borrill,<ref>,<ref>
  François R. Bouchet,<ref>
  Thejs Brinckmann,<ref>
  Michael L. Brown,<ref>
  Sean Bryan,<ref>
  Victor Buza,<ref>,<ref>
  Karen Byrum,<ref>
  Carlos Hervias  Caimapo,<ref>
  Erminia Calabrese,<ref>
  Victoria  Calafut,<ref>
  Robert Caldwell,<ref>
  John E. Carlstrom,<ref>,<ref>,<ref>
  Julien Carron,<ref>,<ref>
  Thomas Cecil,<ref>
  Anthony Challinor,<ref>,<ref>,<ref>
  Clarence L. Chang,<ref>,<ref>,<ref>
  Yuji Chinone,<ref>
  Hsiao-Mei Sherry Cho,<ref>
  Asantha Cooray,<ref>
  Will Coulton,<ref>
  Thomas M. Crawford,<ref>,<ref>
  Abigail Crites,<ref>,<ref>,<ref>
  Ari  Cukierman,<ref>,<ref>
  Francis-Yan Cyr-Racine,<ref>
  Tijmen de Haan,<ref>
  Jacques Delabrouille,<ref>,<ref>,<ref>
  Mark Devlin,<ref>
  Eleonora Di Valentino,<ref>
  Marion Dierickx,<ref>
  Matt Dobbs,<ref>
  Shannon Duff,<ref>
  Jo Dunkley,<ref>
  Cora Dvorkin,<ref>
  Joseph Eimer,<ref>
  Tucker Elleflot,<ref>
  Josquin Errard,<ref>
  Thomas Essinger-Hileman,<ref>
  Giulio Fabbian,<ref>
  Chang Feng,<ref>
  Simone Ferraro,<ref>
  Jeffrey P. Filippini,<ref>
  Raphael Flauger,<ref>
  Brenna Flaugher,<ref>
  Aurelien A. Fraisse,<ref>
  Andrei Frolov,<ref>
  Nicholas Galitzki,<ref>
  Patricio A. Gallardo,<ref>
  Silvia Galli,<ref>
  Ken Ganga,<ref>
  Martina Gerbino,<ref>
  Vera Gluscevic,<ref>,<ref>
  Neil Goeckner-Wald,<ref>
  Daniel Green,<ref>
  Daniel Grin,<ref>
  Evan Grohs,<ref>
  Riccardo Gualtieri,<ref>
  Jon E. Gudmundsson,<ref>
  Ian Gullett,<ref>
  Nikhel  Gupta,<ref>
  Salman Habib,<ref>
  Mark Halpern,<ref>
  Nils W. Halverson,<ref>
  Shaul Hanany,<ref>
  Kathleen Harrington,<ref>
  Masaya Hasegawa,<ref>
  Matthew Hasselfield,<ref>
  Masashi Hazumi,<ref>
  Katrin Heitmann,<ref>
  Shawn Henderson,<ref>
  Brandon Hensley,<ref>
  Charles Hill,<ref>
  J. Colin Hill,<ref>
  Renée Hložek,<ref>,<ref>
  Shuay-Pwu Patty Ho,<ref>
  Thuong Hoang,<ref>
  Gil Holder,<ref>
  William Holzapfel,<ref>
  John Hood,<ref>,<ref>
  Johannes Hubmayr,<ref>
  Kevin M. Huffenberger,<ref>
  Howard Hui,<ref>
  Kent Irwin,<ref>
  Oliver Jeong,<ref>
  Bradley R. Johnson,<ref>
  William C. Jones,<ref>
  Jae Hwan  Kang,<ref>
  Kirit S. Karkare,<ref>,<ref>
  Nobuhiko Katayama,<ref>
  Reijo Keskitalo,<ref>,<ref>
  Theodore Kisner,<ref>,<ref>
  Lloyd Knox,<ref>
  Brian J. Koopman,<ref>
  Arthur Kosowsky,<ref>
  John Kovac,<ref>,<ref>
  Ely D. Kovetz,<ref>
  Steve Kuhlmann,<ref>
  Chao-lin Kuo,<ref>
  Akito Kusaka,<ref>
  Anne Lähteenmäki,<ref>
  Charles R. Lawrence,<ref>
  Adrian T. Lee,<ref>,<ref>
  Antony Lewis,<ref>
  Dale Li,<ref>
  Eric Linder,<ref>
  Marilena Loverde,<ref>
  Amy Lowitz,<ref>,<ref>
  Phil Lubin,<ref>
  Mathew S. Madhavacheril,<ref>
  Adam Mantz,<ref>
  Gabriela Marques,<ref>
  Frederick Matsuda,<ref>
  Philip Mauskopf,<ref>
  Heather McCarrick,<ref>
  Jeffrey McMahon,<ref>,<ref>
  P. Daniel Meerburg,<ref>
  Jean-Baptiste Melin,<ref>
  Felipe Menanteau,<ref>
  Joel Meyers,<ref>
  Marius Millea,<ref>
  Joseph Mohr,<ref>
  Lorenzo Moncelsi,<ref>
  Maria Monzani,<ref>
  Tony Mroczkowski,<ref>
  Suvodip Mukherjee,<ref>,<ref>
  Johanna Nagy,<ref>,<ref>
  Toshiya  Namikawa,<ref>
  Federico Nati,<ref>
  Tyler Natoli,<ref>,<ref>
  Laura Newburgh,<ref>
  Michael D. Niemack,<ref>
  Haruki Nishino,<ref>
  Brian Nord,<ref>
  Valentine Novosad,<ref>
  Roger O'Brient,<ref>,<ref>
  Stephen Padin,<ref>
  Steven Palladino,<ref>
  Bruce Partridge,<ref>
  Don Petravick,<ref>
  Elena Pierpaoli,<ref>
  Levon Pogosian,<ref>
  Karthik Prabhu,<ref>
  Clement Pryke,<ref>
  Giuseppe Puglisi,<ref>,<ref>
  Benjamin Racine,<ref>,<ref>
  Alexandra Rahlin,<ref>
  Mayuri Sathyanarayana Rao,<ref>
  Marco Raveri,<ref>
  Christian L. Reichardt,<ref>
  Mathieu Remazeilles,<ref>
  Graca Rocha,<ref>
  Natalie A. Roe,<ref>
  Anirban Roy,<ref>
  John E. Ruhl,<ref>
  Maria Salatino,<ref>,<ref>
  Benjamin Saliwanchik,<ref>
  Emmanuel Schaan,<ref>
  Alessandro Schillaci,<ref>
  Benjamin Schmitt,<ref>
  Marcel M. Schmittfull,<ref>
  Douglas Scott,<ref>
  Neelima Sehgal,<ref>
  Sarah Shandera,<ref>
  Blake D. Sherwin,<ref>
  Erik Shirokoff,<ref>,<ref>
  Sara M. Simon,<ref>
  Anže Slosar,<ref>
  David Spergel,<ref>
  Tyler St. Germaine,<ref>
  Suzanne T. Staggs,<ref>
  Antony Stark,<ref>
  Glenn D. Starkman,<ref>
  Radek Stompor,<ref>
  Chris Stoughton,<ref>
  Aritoki Suzuki,<ref>
  Osamu Tajima,<ref>
  Grant P. Teply,<ref>
  Keith Thompson,<ref>
  Ben Thorne,<ref>
  Peter Timbie,<ref>
  Maurizio Tomasi,<ref>
  Matthieu Tristram,<ref>
  Gregory Tucker,<ref>
  Caterina Umiltà,<ref>
  Alexander van Engelen,<ref>
  Eve M. Vavagiakis,<ref>
  Joaquin D. Vieira,<ref>
  Abigail G. Vieregg,<ref>,<ref>
  Kasey Wagoner,<ref>
  Benjamin Wallisch,<ref>,<ref>
  Gensheng Wang,<ref>
  Scott Watson,<ref>
  Ben Westbrook,<ref>
  Nathan Whitehorn,<ref>,<ref>
  Edward J. Wollack,<ref>
  W. L. Kimmy Wu,<ref>
  Zhilei Xu,<ref>
  H. Y. Eric Yang,<ref>
  Siavash Yasini,<ref>
  Volodymyr G. Yefremenko,<ref>
  Ki Won Yoon,<ref>
  Edward Young,<ref>
  Cyndia Yu,<ref>
  Andrea Zonca<ref>
  
  
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  <ref>
  
  
  
      December 30, 2023
  ===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  
  In this paper we study variational inequalities (VI) defined by the conditional value-at-risk (CVaR) of uncertain functions. We introduce stochastic approximation schemes that employ an empirical estimate of the CVaR at each iteration to solve these VIs. We investigate convergence of these algorithms under various assumptions on the monotonicity of the VI and accuracy of the CVaR estimate. Our first algorithm is shown to converge to the exact solution of the VI when the estimation error of the CVaR becomes progressively smaller along any execution of the algorithm. When the estimation error is nonvanishing, we provide two algorithms that provably converge to a neighborhood of the solution of the VI. For these schemes, under strong monotonicity, we provide an explicit relationship between sample size, estimation error, and the size of the neighborhood to which convergence is achieved. A simulation example illustrates our theoretical findings.
  
  
  
  
  
  § INTRODUCTION
   
  Variational inequality (VI) problems find application in a broad range of areas <cit.>, e.g., in game theory, under mild conditions, solutions to a VI correspond to Nash equilibria of a game. Similarly, in routing games, the Wardrop equilibria are solutions to the VI formed using the costs of each path.
  In real-life, utilities or costs of players involved in a game may be uncertain and decisions must be made under this uncertainty. The behavior of the players may then depend on their risk-preferences and the involved cost functions are then risk measures of uncertain costs. Equilibrium in such scenarios corresponds to the solution of a VI, where each component of the map defining the VI is the risk associated to an appropriately defined function. Motivated by this setup, we consider VIs defined by the conditional value-at-risk (CVaR) of uncertain costs and develop stochastic approximation (SA) schemes to solve them. 
  
  
  
    §.§.§ Literature review
  
  General risk-based VIs, including CVaR-based VIs, and their potential applications are discussed in <cit.>. SA schemes are quite popular for solving stochastic variational inequality (SVI) problems, see e.g. <cit.> and references therein. In an SVI, the map associated to the VI is usually the expectation of an uncertain function and hence, an unbiased estimator of the map is available using a single sample of the uncertainty. As a result, the associated SA scheme enjoys strong convergence guarantees under fairly mild assumptions. However, this property does not hold in general for CVaR-based VIs. Instead, in our work, we use a finite number of samples to determine an empirical estimate of the CVaR. Such an estimator is biased but consistent and we use results from <cit.> to bound the deviation of the estimator from the true value of the CVaR. Recent works <cit.> generalize such bounds for more general distributions.
  
  Closely related to our work, <cit.> provides a sample average approximation (SAA) method for computing the solutions of the CVaR-based VI. In the SAA method, the CVaR is replaced with its empirical estimate and the solution of the VI formed using these empirical estimates is used to approximate the solution of the original problem. 
  Our approach to analyze the convergence of the SA schemes proposed here involves approximating the asymptotic behaviour of a scheme by a trajectory of a continuous-time dynamical system and inferring convergence from the stability properties of the dynamical system <cit.>, <cit.>. 
  In other related works, <cit.> and <cit.> provide sample-based schemes for optimizing the CVaR and other general risk measures, respectively.
  
  
  
    §.§.§ Statement of Contributions
  
  We start by defining the CVaR-based variational inequality (VI) where the map defining the VI consists of components that are the CVaR of uncertain functions. Our first contribution is the design of a “vanilla” stochastic approximation algorithm that, under strict monotonicity, asymptotically converges to a solution of the VI problem. The algorithm employs a sample-based estimator of the CVaR at each iteration. For convergence, the algorithm requires unbounded growth of the sample size as the iterations proceed.
  To handle this limitation, our second and third contributions are the design of two stochastic approximation schemes, termed penalty-driven and multiplier-driven algorithms, that use the same estimator of the CVaR but use a bounded number of samples at each iteration. Under strict monotonicity, these algorithms are shown to converge asymptotically to a neighborhood of the solution set, the size of which can be tuned. The penalty-driven algorithm allows iterates to venture outside the set defining the VI but controls the deviation using a penalty term. On the other hand, the multiplier-driven algorithm, akin to primal-dual methods in optimization, ensures convergence of iterates to the set using multiplier variables. Our final contribution investigates the dependence of the size of the neighborhood that the iterates converge to on the empirical estimation error, the sample-size at each iteration, and the strong monotonicity parameter. 
  A simulation example illustrates our result. 
  
  
  
    §.§.§ Organization
  
  The paper is organized as follows. Section <ref> presents the notation and basic concepts on variational inequalities and the conditional value-at-risk. Section <ref> describes the problem setup and provides a motivating example. Section <ref> proposes three stochastic approximation algorithms for solving the CVaR-based VI and provides, for two algorithms, the relationship between the estimation error, the sample size, and the accuracy. Section <ref> presents a simulation example. Finally, Section <ref> describes our conclusions and ideas for future work.
  
  
  § PRELIMINARIES
   
  Throughout this paper we use the following notation. Let ℝ and ℕ denote the real and natural numbers, respectively. For N ∈, we let N := {1, 2, …, N}. For given x ∈ℝ, we use the notation [x]_+ := max(x,0). For x ∈^n, we let x_i denote the i-th element of x, and the i-th element of the vector [x]_+ is [x_i]_+. The Euclidean 2-norm of x is given by x. For scalars x, y ∈, the operator [x]_y^+ equals x if y > 0 and it equals max{0,x} if y = 0. 
  For vectors x,y ∈^n, [x]_y^+ denotes the vector whose i-th element is [x_i]_y_i^+. The open ϵ neigborhood of x is defined as _ϵ(x) = y ∈^ny-x < ϵ. The Euclidean projection of x onto the set  is denoted Π_(x):=_y ∈x-y. The closure of a set ⊂^n is denoted by ().
  
  
   §.§ Variational inequalities, monotonicity, and KKT points
  
  For a given map F: ℝ^n →ℝ^n and a closed set ⊆ℝ^n, the associated variational inequality (VI) problem, (F,), is to find h^* ∈ solving
  
      (h - h^*)^⊤ F(h^*) ≥ 0  for all  h ∈.
  
  The set of all points that solve (F,) is denoted (F,). An important concept in the context of VI's is monotonicity of the map F. The map F
  is called monotone if
  
      (F(x)  -  F(y))^⊤  (x  -  y)  ≥  0
  
  holds for all x,y ∈ℝ^n. If the inequality is strict for x ≠ y, then F is strictly monotone. Similarly, we call F strongly monotone with constant c_F  >  0 if 
  
      (F(x) - F(y))^⊤  (x-y)  ≥  c_Fx - y^2
  
  holds for all x, y ∈ℝ^n. 
  If  is nonempty, compact, and F 
  is continuous, then (F,) is nonempty.
  If F is strictly monotone, then (F,) has at most one solution <cit.>.
  Under the linear independence constraint qualification (LICQ), we next characterize (F,) as the set of Karush-Kuhn-Tucker (KKT) points of (F,).
  KKT points of (F,)
  Let 
      
      := h ∈^n q^j(h) ≤ 0,   l^k(h)  =  0,  ∀ j ∈ [s],   k ∈ [t],
  
      where the functions q^j, l^k: ℝ^n →ℝ, j ∈s, k ∈t, are convex and affine, respectively, and continuously differentiable. 
      For q(h)  :=  (q_1(h), …, q_s(h))^⊤∈^s, let Dq(h) ∈^s × n be its Jacobian at h, and similarly Dl(h). For any h^* ∈^n, if there exists a multiplier (λ^*, μ^*) ∈^s ×^t satisfying 
      
      F(h^*) + (Dq(h^*))^⊤λ^* + (Dl(h^*))^⊤μ^* = 0, 
      
                   l(h^*   ) = 0,    q(h^*) ≤ 0,   λ^*≥ 0,   λ^*⊤q(h^*) = 0,
  
      then we have h^* ∈(F,). Such a point (h^*,λ^*, μ^*) is referred to as a KKT point of the (F,). Conversely, for h^* ∈(F,), let _h^* = jq^j(h^*) = 0.
      If the vectors {∇ q^j(h^*)}_j ∈_h^* and {∇ l^k(h^*)}_k ∈ [t] are linearly independent, or in other words, the LICQ holds at h^*, then there exists a multiplier (λ^*, μ^*) satisfying (<ref>).
  
  The above result is well-known in the context of convex optimization. The extension to the VI setting is forthright: the proof that the existence of a triplet (λ^*,μ^*,h^*) satisfying (<ref>) is sufficient to guarantee h^* ∈(F,) can be found in <cit.>. That the same condition is also necessary can be deduced from the result in the context of convex optimization (e.g. <cit.>) and noting that if h^* ∈(F,), then it is also a minimizer of the function y ↦ y^⊤ F(h^*) subject to y ∈. 
  
  
   §.§ Conditional Value-at-Risk
  
  The Conditional Value-at-Risk (CVaR) at level α∈ (0,1] of a real-valued random variable Z, defined on a probability space (Ω, , ℙ), is given by
  
      _α[Z] := inf_t ∈ℝ{t + α^-1𝔼[Z - t]_+},
  
  where the expectation is with respect to .  The value α is a constant that characterizes risk-averseness, with smaller values of α giving a more risk-averse measure on Z. 
  Given N independent and identically distributed (i.i.d) samples {Z_j}_j ∈ [N] of the random variable Z, one can approximate _α[Z] using the following empirical estimate
  
      ^N_α[Z] = inf_t ∈ℝ{ t + (N α)^-1∑_j=1^N[Z_j - t]_+ }.
  
  This estimator is biased, but consistent <cit.>. That is, the expected value of ^N_α[Z] is not necessarily equal to _α[Z] and lim_N →∞^N_α[Z] = _α[Z] with probability one.
  
  
  
  § PROBLEM STATEMENT AND MOTIVATING EXAMPLE
   
  Consider a set of functions C_i: ℝ^n ×ℝ^m →ℝ, i ∈n, (h,u) ↦ C_i(h,u), where u represents a random variable with distribution . For a fixed h, C_i(h,u) is therefore a real-valued random variable. Define the map F_i^n as the CVaR of C_i at level α∈ (0,1],
  
      F_i(h) := _α[C_i(h,u)],  for all  i ∈n.
  
   For notational convenience, let C: ℝ^n ×ℝ^m →ℝ^n and F^n^n be the element-wise concatenation of the maps {C_i}_i ∈n and {F_i}_i ∈n, respectively. Let ⊆^n be a nonempty closed set.
  The objective of this paper is to provide stochastic approximation (SA) algorithms to solve the variational inequality problem (F,). Our strategy is to use an empirical estimator, derived from samples of C(h,u), of the map F at each iteration of the algorithm. Before we introduce the schemes, we will discuss a motivating example.
  
  
  
    §.§.§ CVaR-based routing games <cit.>
   
  Consider a directed graph = (,), where = n̅ is the set of vertices, and ⊆× is the set edges. To such a graph we associate a set ⊆× of origin-destination (OD) pairs. An OD-pair w is given by an ordered pair (v^w_o,v^w_d), where v^w_o, v^w_d ∈ are called the origin and the destination of w, respectively. The set of all paths in  from the origin to the destination of w is denoted _w. The set of all paths
  is given by = ∪_w ∈_w. Each of the participants, or agents, of the routing game is associated to an OD-pair, and can choose a path to travel from its origin to its destination. The choices of all agents give rise to a flow vector h ∈ℝ^||. A common assumption in this context, which we will adopt here as well, is that the flow is non-atomic, meaning that each traffic participant controls an infinitesimal part of the flow. As a consequence, the flow h is a continuous variable.
  
  For each (OD)-pair w, a real value d_w ≥ 0 defines the amount of traffic, or demand, associated to it.
  The feasible set ⊂^||, containing all possible flows is then given by 
  
      = h∑_p ∈_wh_p = d_w,  ∀ w ∈,   h_p ≥ 0  ∀ p ∈.
  
  To each of the paths p ∈, we associate a cost function C_p: ℝ^||×ℝ^m→ℝ, (h,u) ↦ C_p(h,u), which depends on the flow h, as well as on the uncertainty u ∈ℝ^m.
  Each agent chooses a path p ∈_w that minimizes _α[C_p(h,u)]. These elements define the CVaR-based routing game to which we assign the following notion of equilibrium:
      the flow h^* ∈ is said to be a CVaR-based Wardrop equilibrium (CWE) of the CVaR-based routing game if the following hold for all w ∈:
      
          
    * ∑_p ∈_w h^*_p = d_w,
          
    * h^*_p > 0 for p ∈_w only if
          
      _α[C_p(h^*,u)] ≤_α[C_q(h^*,u)]  ∀ q ∈_w.
  
      
  The intuition behind this definition is that at equilibrium, for each agent, there is no path for which the CVaR of the cost is less than the CVaR of the cost on the selected path. Thus there is no incentive for the traffic participants to change their route choices. 
  Under continuity of C_p, the set of CWE is equal to the set of solutions of (F,), where F: ℝ^||→ℝ^|| takes the form of (<ref>).
  
  
  
  § STOCHASTIC APPROXIMATION ALGORITHMS FOR SOLVING (F,)
    
  In this section, we introduce the SA algorithms along with their convergence analysis. Then we establish results relating the accuracy of the algorithms to the size of the estimation error and the sample size in each iteration. All introduced schemes approximate F with the estimator given in (<ref>). Given N independently and identically distributed samples {(C_i(h,u) )_j}_j=1^N of the random variable C_i(h,u), let 
  
      ^N_i(h) := inf_t ∈ℝ{ t + 1/Nα∑_j=1^N[(C_i(h,u))_j - t]_+ }
  
  stand for the estimator of F_i(h). We occasionally use _α^N [C_i(h,u)] to denote ^N_i(h).
  Analogously, the estimator of F(h) formed using the element-wise concatenation of ^N_i(h), i ∈n, is denoted by ^N(h) or ^N_α[C(h,u)]. We assume that the N samples of each cost function are a result of the same set of N events, that is, the distribution of ^N(h) depends on ^N.
   All algorithms introduced in this section depend on a sequence of step-sizes {γ^k}_k^∞, where γ^k > 0 for all k ∈. Common assumptions for this sequence are
   
      ∑_k = 0^∞γ^k = ∞,        ∑_k = 0^∞ (γ^k)^2 < ∞.
  
  For all upcoming algorithms, we will assume that the sequence {γ^k}_k^∞ satisfies these assumptions.
   
   For a given sequence {N_k}_k=0^∞⊂, and an initial vector h^0 ∈, the first algorithm under consideration, which we will refer to as the projected algorithm is given by
  
      h^k+1 = Π_( h^k - γ^k^N_k(h^k)),
  
  where Π_ is the projection operator (cf. Section <ref>) and h^k is the k-th iterate of h produced by the algorithm. The above algorithm is inspired by the SA schemes for solving a stochastic VI problem, see <cit.> for details on other SA schemes. The key difference from the setup in <cit.> is the fact that there the map F is the expected value of a random variable for which an unbiased estimator F is available. In our case, the estimator is biased posing limitations on the sample requirements for convergence of the algorithms. 
  
  For analysis, it is convenient to write the projected algorithm (<ref>) equivalently as
  
      h^k+1 = Π_( h^k - γ^k(F(h^k) + β^N_k) ),
  
  where β^N_k is used to denote the error introduced by estimation, and is given by
  
      β^N_k := F^N_k(h^k) - F(h^k).
  
  
  The following result on the convergence of (<ref>) is then a direct consequence of <cit.>.
   Convergence of (<ref>) to a solution of (F,) 
  Let F, as defined in (<ref>), be a strictly monotone, continuous function, and let  be a compact convex set. 
  For the algorithm (<ref>), assume that the sequence of step-sizes {γ^k} satisfies (<ref>) and the sequence {N_k} is such that {β^N_k} is bounded with probability one and N_k →∞ as k →∞. Then, the iterates {h^k} generated by (<ref>) satisfy
  
      lim_k →∞h^k - h^* = 0,
  
   for h^* ∈(F,), with probability one.
  
  The proof proceeds in two steps: (a) showing that the iterative scheme asymptotically approaches a trajectory of a continuous-time dynamical system; and (b) establishing asymptotic stability of the system. We will use this reasoning for analyzing the other algorithms presented in this work.
  
  Note that since the CVaR estimator is biased, Proposition <ref> requires the number of samples to grow unboundedly as the algorithm progresses. In order to address this tractability issue, we propose two algorithms which achieve convergence to an ϵ neighborhood of (F,) using a finite number of samples in each iteration. Unlike (<ref>), both algorithms allow the iterates to take values outside the set . This limitation is a result of our analysis approach. With projections and a biased estimator, the analysis of (<ref>) with finite samples at each iteration would involve studying the input-to-state stability of a continuous-time projected dynamical system <cit.>, the theory for which is not yet available in the literature. 
  
   As in Proposition <ref>, we will impose continuity and monotonicity assumptions on F in the upcoming results. Sufficient conditions for the Lipschitz continuity of F are given in <cit.>.
   We provide the following general result on the continuity and monotonicity properties of F. 
  Sufficient conditions for monotonicity and continuity of F
      The following hold:
      
          
    * Assume that for all i ∈ [n], there exist functions f_i:^n → and g_i: ^m → such that C_i(h,u) ≡ f_i(h) + g_i(u).
          Let f(h):= (f_1(h), …, f_n(h)). Then, F is monotone (resp. strictly or strongly monotone) if f is monotone (resp. strictly or strongly monotone).
          
    * If for any ϵ > 0 there exist a δ > 0 such that h - h'≤δ implies C_i(h,u) - C_i(h',u)≤ϵ for all i ∈n and all u, then F is continuous.
      
  
  The proof of the first part of this statement makes use of the coherence of the CVaR as a risk measure <cit.>. This, together with the made assumptions, implies
  
      _α[C_i(h,u)] = f_i(h) + _α[g_i(u)].
  
  As a consequence, we have F(h) - F(h^*) = f(h) - f(h^*), and the result follows.
  The part of this statement pertaining to continuity can be derived by arguments similar to those of the proof of <cit.>. Note that the given conditions for continuity may be difficult to check in practice. However, they hold when  is compact, u has a compact support, and for any fixed u, the functions C_i are continuous with respect to h.
  We now proceed to introduce two more algorithms. 
  
  
  
   §.§ Penalty-driven algorithm
   
  We define the
  penalty-driven algorithm as
  
      h^k+1 = h^k -γ^k(F(h^k) + c(h^k - Π_(h^k)) + β^N_k).
  
  Here c > 0 is a constant and the error sequence {β^N_k} is as defined in (<ref>). This algorithm allows the iterates {h^k} to take values outside of . However, the term h^k - Π_(h^k) controls this drift; the higher the value of the design parameter c, the closer the limit of {h^k} is to . In this sense, the constant c determines the penalty for moving out of the set.
  Now we state the convergence properties of (<ref>).
    Convergence of the penalty-driven algorithm (<ref>)
  Let F, as defined in (<ref>), be a strictly monotone, continuous function, and let  be a compact convex set. For the algorithm (<ref>) and h^* ∈(F,), let c = dF(h^*) for some d > 0. Assume that the sequence of step-sizes {γ^k} satisfies (<ref>) and that the sequence {N^k} is such that {β^N_k} and {h^k} are bounded with probability one. 
  Then, for any ϵ > 0, there exist d_ϵ > 0 and N_ϵ∈ℕ such that d ≥ d_ϵ and N_k ≥ N_ϵ for all k imply, with probability one, 
  
      lim_k →∞h^k - h^*≤ϵ.
  
  
  
  For convenience, we split the error as β^N_k = b^N_k + ξ^N_k, where b^N_k = 𝔼[ β^N_k]. By definition, 𝔼[ξ^N_k] = 0 and by the boundedness assumption, there exists a constant B > 0 such that b^N_k≤ B for all k. As mentioned before, the proof proceeds in two steps. First, the sequence {h^k} is shown to converge to a trajectory of the following continuous-time system
  
      ḣ̅̇ (t) = -F(h̅(t)) - c(h̅(t) - Π_(h̅(t))) - b̅(t).
  
  Here, b̅(·) is a uniformly bounded map satisfying b̅(t)≤ B for all t.
  The proof of the above fact is analogous to that of <cit.> and we avoid repeating these arguments for space reasons. To be more precise, the sequence {h^k} converges to a trajectory of (<ref>) if there exists a map t ↦h̅(t) with h̅(0) ∈^n satisfying (<ref>) for all t and 
  
      lim_k →∞sup_j ≥ kh^j - h̅(∑_r=k^j-1γ^r) = 0.
  
  That is, the discrete-time trajectory formed by the linear interpolation of the iterates {h^k} approaches a continuous-time trajectory t ↦h̅(t). Convergence of the sequence {h^k} can then be analyzed by studying the asymptotic stability of (<ref>). 
  To this end, define the Lyapunov function
      
      V(h̅) = h̅ - h^*^2,
  
   where h^* is the unique solution to (F,), that follows from strict monotonicity. For readability, we introduce the notation h̃ = Π_(h̅). We first analyze the evolution of V along (<ref>) when b̅≡ 0. For notational convenience, define the right-hand side of (<ref>) in such a case by the map X_b≡0^n^n. The Lie derivative of V along X_b≡0 is
     
      ∇ V(h̅)^⊤ X_b≡0(h̅) = -2(h̅ - h^*)^⊤(F(h̅) + c(h̅ - h̃)).
  
     Our next step is to show that the Lie derivative is upper bounded by a negative quantity whenever the trajectory is at least ϵ > 0 away from h^*. To this end, let Δ_ϵ :=h̅h̅∉_ϵ(h^*),  h̅≤ B_h, where _ϵ(h^*) is an (open) ϵ neighborhood of h^* and B_h is a bound on the trajectory h̅ (·) where the iterates converge to. Such a bound exists due to <cit.>. Note that Δ_ϵ is a compact set.
     We will show that there exists δ_1> 0 such that ∇ V(h̅)^⊤ X_b≡0(h̅)  < - δ_1 for all h̅∈Δ_ϵ. Note that we have (h̅ - h^*)^⊤ F(h̅) > (h̅ - h^*)^⊤ F(h^*) due to strict monotonicity of F. Using this fact in (<ref>), gives for all h̅∈Δ_ϵ,
     
      ∇ V(h̅)   ^⊤ X_b≡0(h̅) < -2(h̅ - h^*)^⊤(F(h^*) + c(h̅ - h̃)) 
         = -2(h̅ - h̃)^⊤ F(h^*) -2(h̃ - h^*)^⊤ F(h^*) 
              -2c(h̅ - h̃)^⊤ (h̅ - h̃) -2c(h̃ - h^*)^⊤(h̅ - h̃),
  
     where we recall that h̃ = Π_(h̅). Since h^* ∈(F,), we have (h̃ - h^*)^⊤ F(h^*) ≥ 0. Further, since  is convex, the projection property implies that (h̃ - h^*)^⊤ (h̅ - h̃) ≥ 0. Using these two facts and applying the Cauchy-Schwartz inequality in the above derived inequality, we obtain, for all h̅∈Δ_ϵ,
      
      ∇ V(h̅)^⊤ X_b≡0(h̅)  <  2h̅ - h̃(F(h^*) -dF(h^*)h̅ - h̃).
  
     Since Δ_ϵ is compact, there exists δ_0 > 0 such that
     
      ∇ V(h̅)^⊤    X_b≡0(h̅) ≤
         2h̅ - h̃F(h^*) -2dF(h^*)h̅ - h̃^2 - δ_0
  
      holds for all h̅∈Δ_ϵ. The right-hand side as a function of h̅ - h̃ attains a maximum at h̅- h̃ = 1/2d. Thus, we have 
      
  
      ∇ V(h̅)^⊤ X_b≡0(h̅) ≤1/2dF(h^*) -δ_0.
  
      It follows that if we set
      
      d = F(h^*)/2 δ_0(1 - δ_1/δ_0)^-1
  
      for some δ_1 < δ_0, then ∇ V(h̅)^⊤ X_b≡0(h̅) ≤ -δ_1 for all h̅∈Δ_ϵ. At this point, we drop the earlier made restriction b ≡ 0. Denote the right-hand side of (<ref>) by the map X. From the above reasoning, the Lie derivative of V along (<ref>) satisfies 
      
      ∇ V(h̅)^⊤ X(h̅) ≤ - δ_1 + 2 (h̅ - h^*)^⊤ b
  
      for all h̅∈Δ_ϵ.
  Note that as stated before, the bound on the norm of the map b is the same as the bound on the iterates {b^N_k}. Since h̅(·) is bounded and for any k, b^N_k→ 0 as N_k →∞ (as the empirical estimate of the CVaR is consistent), we conclude that selecting large enough N_k for all k, implies 2(h̅ - h^*)^⊤ b < δ_1. Plugging this inequality in (<ref>) yields, for all h̅∈Δ_ϵ,
  
      ∇ V(h̅)^⊤ X(h̅) ≤ - δ
  
   for some δ∈ (0,δ_1). This implies that the trajectory h̅(·) of (<ref>) reaches the closure of _ϵ(h^*) in finite time. 
  Additionally, once the trajectory reaches (_ϵ(h^*)), it stays there. 
  Thus, (<ref>) holds with probability one, concluding the proof.
  
  Practical considerations of (<ref>)
  In Proposition <ref>, for small values of ϵ, one would require a large value of d to ensure convergence. This may result in large oscillations of h^k when the term γ^k d remains large. Such behaviour can be prevented by either starting with small values of γ^k or increasing d along iterations, until it reaches a predetermined size. The result is then still valid but the convergence can only be guaranteed once d reaches the required size. 
  Generalizations of Proposition <ref> 
  For all our convergence results, we require {h^k} to be bounded. This is however not very restrictive. The results remain valid if the sequence {h^k} is projected onto a hyper-rectangle containing  (cf. <cit.>). 
  
  
  
   §.§ Multiplier-driven algorithm
  
  Algorithms (<ref>) and (<ref>) involve projection onto the set  at each iteration. This can be computationally burdensome.
  Our next algorithm overcomes this limitation. Inspired by the Lagrangian method, we assume  to be of the form (<ref>) and introduce a multiplier variable (λ, μ) ∈^s ×^t that enforces constraint satisfaction as the algorithm progresses. In order to simplify the coming equations, we write
  
      H(h,λ,μ) := F(h) + Dq(h)^⊤λ + Dl(h)^⊤μ,
   
  
  where Dq(h) and Dl(h) are the Jacobians of q and l at h, respectively. The multiplier-driven algorithm is given by 
  
      h^k + 1   = h^k - γ^k (H(h^k,λ^k,μ^k) + β^N_k),  
      λ^k+1   = [λ^k + γ^k q(h^k) ]_+, 
              
      μ^k+1    = μ^k + γ^k l(h^k).
   
  Recall that β^N_k is the error due to empirical estimation of F.
   The next result states the convergence properties of (<ref>) to a KKT point of the VI (see Section <ref> for definitions).
    Convergence of the multiplier-driven algorithm (<ref>) 
      Let F, as defined in (<ref>), be a strictly monotone, continuous function, and let  be a compact set given by (<ref>), where the functions q^j, j ∈s, are affine. Assume that the LICQ holds for h^* ∈(F,), and let (h^*,λ^*, μ^*) be an associated KKT point. 
      For algorithm (<ref>), assume that the sequence of step-sizes {γ^k} satisfies (<ref>) and let {N_k} be such that {β^N_k}, {h^k}, {λ^k} and {μ^k} are bounded with probability one.
      Then, for any ϵ > 0, there exists an N_ϵ∈ℕ such that if N_k ≥ N_ϵ for all k, then, with probability one,
      
      lim_k →∞h^k - h^*≤ϵ.
   
   
   
    Analogous to the proof of Proposition <ref>, the first step establishes convergence with probability one of 
    the sequence {(h^k, λ^k, μ^k)}, in the sense of (<ref>), to a trajectory (h̅(·),λ̅(·),μ̅(·)) of the following dynamics 
    
    
      ḣ̅̇(t)    = -H(h̅(t), λ̅(t), μ̅(t))  - b̅(t)    
      λ̇̅̇(t)    = [q(h̅(t))]_λ̅(t)^+,   μ̇̅̇(t) = l(h̅(t)),
  
   
   where λ̅(·) is contained in the nonnegative orthant due to the projection. 
   The map b̅(·) is uniformly bounded. Specifically, since {β^N_k} is bounded, there exists a B > 0 such that b^N_k≤ B for all k, where b^N_k = 𝔼[ β^N_k]. We then have b̅(t)≤ B for all t. 
  The proof of convergence of the iterates to a continuous trajectory is similar to that of <cit.> and is not repeated here for brevity. Next, we analyze the convergence of (<ref>). We will occasionally use x̅ as shorthand for (h̅,λ̅,μ̅).
       Define the Lyapunov function
      
      V(h̅,λ̅, μ̅) := h̅ - h^*^2 + λ̅ - λ^*^2 + μ̅ - μ^*^2,
  
      where h^* is the unique solution of (F,) and (h^*,λ^*, μ^*) is an associated KKT point.
   We analyze the evolution of (<ref>) for the case b̅≡ 0. Denoting the right-hand side of (<ref>) by the map X_b ≡ 0, we get the Lie derivative of V along (<ref>) as
      
      ∇ V(x̅)^⊤  X_b ≡ 0(x̅) = -2(h̅ - h^*)^⊤ H(h̅,λ̅, μ̅)  
      + 2(   λ̅ - λ^*)^⊤(q(h̅)  +  [q(h̅)]_λ̅^+  -  q(h̅))  +  2(μ̅ - μ^*)^⊤ l(h̅).
  
      Note that for any j, ([q(h̅)]_λ̅^+)_j = (q(h̅))_j if λ̅_j > 0. Further, if λ̅_j = 0, then λ̅_j - λ^*_j ≤ 0. Thus we see that (λ̅ - λ^*)^⊤([q(h̅)]_λ̅^+  -  q(h̅)) ≤ 0. Since q and l are affine, we have Dq(h̅) = Dq(h^*) and Dl(h̅) = Dl(h^*) for all h̅∈^n. Combining this with strict monotonicity we get for h̅≠ h^*
      
      0   <(h̅ - h^*)^⊤(H(h̅,λ̅, μ̅)
                  - H(h^*,λ̅, μ̅) ) 
         =(h̅ - h^*)^⊤(H(h̅,λ̅, μ̅)
                   - H(h^*,λ^*, μ^*)
         + Dq(h^*)^⊤λ^* - Dq(h^*)^⊤λ̅ + Dl(h^*)^⊤μ^* - Dl(h^*)^⊤μ̅).
  
      Using (<ref>), and the assumption that functions are affine gives
      
      - (h̅  -  h^*)^⊤ H(h̅,λ̅, μ̅)    
         <  
              (λ^* - λ̅)^⊤(q(h̅) - q(h^*)) + (μ^* - μ̅)^⊤(l(h̅) - l(h^*) ).
  
      Combining these derivations, we get that for h̅≠ h^*,
      
      ∇ V(x̅)  X_b ≡ 0(x̅)  <  2(λ̅ -λ^* )^⊤  q(h^*)  +  2(μ̅ -μ^*)^⊤  l(h^*).
  
      From (<ref>) we have 2λ^*⊤q(h^*) = 0, 2λ̅^⊤ q(h^*) ≤ 0 and l(h^*) = 0, which implies ∇ V(h̅,λ̅,μ̅)  X_b ≡ 0(h̅,λ̅,μ̅) < 0 whenever h̅≠ h^*. The rest of the proof is analogous to the corresponding section of the proof of Proposition <ref>.
   
    Generalizations of Proposition <ref> 
      In Proposition <ref> we require boundedness of {h^k}, {λ^k} and {μ^k}. 
      Similar to the case in Remark <ref>, when upper bounds on λ^* and μ^* are known beforehand,
      projection onto hyper-rectangles can be used to ensure boundedness, while the result remains valid, (cf. <cit.>).
      
  
  
   §.§ Estimation error, sample sizes, and accuracy
  
  For both algorithms (<ref>) and (<ref>), the convergence depends on the bias of the used estimator, given by b_N_k := 𝔼[β^N_k]. When F is assumed to be strongly monotone, we can give an explicit bound on b^N_k sufficient for ensuring convergence.
    Estimation error bounds under strong monotonicity
      Assume that F is strongly monotone with constant c_F. For given sequences {h^k} and {N^k}, define 
      
      h_+ := max_h ∈{h^k},h' ∈h - h',    b_N_k = 𝔼[β^N_k].
  
      The following then hold for any ϵ > 0:
      
          
    * Assume the conditions of Proposition <ref> and consider {h^k} generated by (<ref>). Let h_+ and b_N_k be given by (<ref>) and let d = c_dF(h^*)/2, with c_d > 1. Then
          
      b^N_k < (1 - 1/c_d)c_Fϵ^2/h_+ for all  k ∈
  
          implies lim_k →∞h^k - h^*≤ϵ with probability one.
          
    * Assume the conditions of Proposition <ref> and consider {h^k} generated by (<ref>). Let h_+ and b_N_k be given by (<ref>). Then
          
      b^N_k < c_Fϵ^2/h_+ for all  k ∈
  
           implies lim_k →∞h^k - h^*≤ϵ with probability one. 
      
  
  
   For the first statement the proof is analogous to that of Proposition <ref>. Due to strong monotonicity, we have
    
      -2(h̅ - h^*)^⊤ F(h̅) ≤ -2c_Fh̅ - h^*^2.
  
      Setting δ_0 = 2c_Fϵ^2 in the proof of Proposition <ref>, we get δ_1 = (1 - 1/c_d)2c_Fϵ^2. Since {h^k} is bounded by assumption, we have h_+ < ∞. The result then follows. 
      Similar reasoning holds for (<ref>).
  
  
  We would now like to translate the condition imposed in the above result on b^N_k into a condition on the sample requirement N_ϵ. To this end, under compactness, we give a result supplying a bound on b^N_k depending on N^k. 
   Relation between estimation error and sample size 
  Let F be as defined in (<ref>), where C_i(h,u) ∈ [z_1, z_2], z_2 ≥ z_1, for all h,u and i. Then,
  for b^N_k = 𝔼[F(h^k) - F^N_k(h^k)], we have
  
      b^N_k≤3/2√(5 n π/N_k α)(z_2 - z_1).
  
  
  
  We will proof the result for the case n = 1. The generalization to n > 1 is straightforward. For a scalar random variable Z, we have 𝔼[_α[Z]] ≤_α[Z] <cit.>. Therefore, 
  
      | 𝔼[_α[Z]    - _α[Z]  ] | 
          = 𝔼[_α[Z] - _α[Z]  ]    
         ≤𝔼[_α[Z] - _α[Z] ]_+.
  
  From <cit.>, we have the concentration bound
  
      ℙ[_α[Z] - _α[Z] ≥ z ] ≤ 3 e^-1/5α(z/z_2 - z_1)^2 N.
  
  Thus we have
  
      𝔼[_α[Z] - _α[Z] ]_+  
         = ∫_0^∞ℙ[_α[Z] - _α[Z]] ≥ z]dz 
         ≤3/2√(5 π/N_k α)(z_2 - z_1).
  
  The last inequality can be obtained by calculating the integral of the right-hand side of (<ref>) using polar coordinates. The details of this derivation are omitted. The result then follows.
  
  
  
   The above result leads to a lower bound on N_k, for both algorithms (<ref>) and (<ref>), that ensures convergence to _ϵ(h^*).
   Sample size bounds under strong monotonicity
  Let F be strongly monotone with constanct c_F, and assume the conditions of Proposition <ref> (resp. Proposition <ref>) and Lemma <ref> hold. For {h^k} generated by (<ref>) (resp. (<ref>)) define h_+, b_N_k, and c_d as in Corollary <ref>. For ϵ > 0
  
      N_k     > 45 n π/4α(h_+ (z_2 - z_1)/ϵ^2 c_F  (1 - 1/c_d))^2   for all  k ∈,
          
      
          (resp.  N_k     >  45 n π/4α(h_+ (z_2 - z_1)/ϵ^2 c_F )^2  for all  k ∈,)
  
  implies lim_k →∞h^k - h^*≤ϵ with probability one.
  
  
  
  § SIMULATIONS
   
  
  
  
  Here we demonstrate the application of the stochastic approximation algorithms for finding the solutions of a CVaR-based variational inequality. The example is an instance of a -based routing game as introduced in Section <ref>. The example discussed is taken from <cit.>, where it was adapted from <cit.>. It consists of a simple network of two nodes = {A,B}, and five edges. The edges {1,2,3} go from A to B, and edges {4,5} go from B to A. Then = {1,2,3,4,5}. The demand equals 260 from A to B, and 170 from B to A, giving us the feasisble set
  
      = h ∈^5h_1 + h_2 + h_3 = 260,   h_4 + h_5 = 170.
  
  The cost functions are given by
  
      C(h,u) = ([ 40h_1 + 20h_4 + 1000 + 3000u_1;            60h_2 + 20h_5 + 950;                   80h_3 + 3000;  8h_1 + 80h_4 + 1000 + 4000u_2;           4h_2 + 100h_5 + 1300 ]),
  
  where the variables u_1 and u_2 model the uncertainty in the system, and are independent and uniformly distributed random variables on [0,1]. Setting α = 0.2, we have defined the considered -based routing game. From <cit.>, the CWE (see Section <ref>) of this routing game is given by h^* = (89.52,98.39,72.09,74.32,95.68).
  
  Figure <ref> shows the evolution of the error of the considered algorithms for a single run. Different step-size sequence were used, in order to avoid unstable behaviour. The figure shows that all algorithms converge to a neighborhood of the solution of the VI, albeit with a different number of iterations.
  Using the same step-size sequences as for Figure <ref>, Figure <ref> shows the empirical cumulative distribution function (CDF) of the distance of the last iterate of the algorithm to the solution. We infer that as the number of samples used per iteration increases, the last iterates gets closer to the solution. Note that even though N_k does not grow unboundedly, the projected algorithm still converges. 
  
  
  § CONCLUSIONS
   
  We have considered variational inequalities defined by the CVaR of cost functions and provided two stochastic approximation algorithms for solving them. We have analyzed the asymptotic convergence of these algorithms when, at each iteration, only finite number of samples are used to estimate the CVaR. We have carefully specified the trade-off between the sample requirement and the accuracy of the algorithms.
  
  Future work will focus on analyzing the finite-time properties of the introduced algorithms. We wish to also explore input-to-state stability of projected dynamical systems. 
  
  ieeetr
  