I am currently looking for literature discussing the computational complexity of CVaR calculation. At this point the only work I have found is the following.

Mavronicolas, Marios, and Burkhard Monien. "Conditional Value-at-Risk: Structure and complexity of equilibria." Theoretical Computer Science 807 (2020): 266-283.

Any other pointer would be greatly appreciated. TIA

  • 1
    $\begingroup$ Have you tried doing a literature search, starting from that paper, and seeing what it cites, and looking on Google Scholar to check out the papers that cite it? $\endgroup$
    – D.W.
    Commented Nov 29, 2022 at 5:19
  • $\begingroup$ @D.W., it is cited by 3 papers and probably the most relevant one is Georgiou, Chryssis, Marios Mavronicolas, and Burkhard Monien. "The complexity of (E+ Var)-equilibria, ESR-equilibria, and SuperE-equilibria for 2-players games with few cost values." Theoretical Computer Science 860 (2021): 84-97.. $\endgroup$ Commented Nov 29, 2022 at 14:10
  • $\begingroup$ @D.W., I have also found Mhammedi, Zakaria, Benjamin Guedj, and Robert C. Williamson. "Pac-bayesian bound for the conditional value at risk." Advances in Neural Information Processing Systems 33 (2020): 17919-17930. $\endgroup$ Commented Nov 29, 2022 at 14:25
  • 1
    $\begingroup$ Great. Please incorporate this into your post, by editing your post, rather than by adding comments here. $\endgroup$
    – D.W.
    Commented Nov 29, 2022 at 16:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.