Matthias Jean

Régis Emmanuel Georges

This thesis deals with optimization under uncertainty, which has a long history in operations research and mathematical optimization. This field is currently challenged by applications in artificial intelligence and data science, where risk management has become a crucial issue. In this thesis, we consider nonsmooth optimization problems involving risk measures and coming from statistical learning applications. We pay a special attention to the risk measure called the superquantile (also known as the "Conditional Value at Risk") and we show how, in various contexts, it may enforce robustness for decision-making under uncertainty.

First, we consider convex risk measures admitting a representation in terms of superquantiles. We derive first-order oracles with optimal computational complexity. These approximate oracles involve different smoothing techniques for which we propose a unified analysis. We also propose an efficient implementation of these oracles, coupled with a series of classical optimization methods, in an open-source software in python. We show empirically, on classification and regression tasks, that the predictions obtained are robust to data shifts.

We then consider chance-constrained optimization problems. We propose a reformulation of these problems in the form of bilevel programs that involve the superquantile. We propose a (semi-) exact penalization for this reformulation, which we treat with a bundle method. We implement our bilevel approach in an open-source python software, which we illustrate on non-convex problems.

Finally, we investigate the use of the superquantile for federated learning. We consider the case of users with heterogeneous data distributions and we show how the superquantile allows for better performances on non-conforming users. We propose an algorithm adapted to the constraints of federated learning, in terms of communications and data privacy. We prove its theoretical convergence in the convex case by controlling the drift induced by the local stochastic gradient method and the dynamic reweighting induced by superquantiles. We also propose an in-depth numerical study of our algorithm and compare its performance with several established baselines, including FedAvg, FedProx and Tilted-ERM and Agnostic Federated Learning.

iii RÉSUMÉ Cette thèse s'inscrit dans le cadre de l'optimisation sous incertitude, qui a une longue tradition en recherche opérationnelle et en optimisation mathématique. Ce domaine trouve aujourd'hui de nouvelles applications en intelligence artificielle et science des données, où la prise en compte du risque est devenu une question cruciale. Dans cette thèse, nous considérons des problèmes d'optimisation, issus d'applications en apprentissage statistique, mettant en jeu des mesures de risque. Nous accordons une attention particulière à la mesure de risque appelée superquantile (également connue sous le nom de "Conditional Value at Risk") et montrons comment, dans divers contextes, elle permet d'obtenir de la robustesse dans la prise de décision.

Dans un premier temps, nous nous intéressons aux mesures de risque convexes admettant une représentation en termes de superquantiles. Nous dérivons des oracles du premier ordre avec une complexité de calcul optimale. Ces oracles approchés font intervenir différentes techniques de lissage pour lesquelles nous proposons une analyse unifiée. Nous proposons aussi une implémentation efficace de ces oracles, couplée à une série de méthodes classiques d'optimisation, dans un logiciel open-source en python. Nous montrons empiriquement, sur des problèmes de classifications et de régression, que les prédictions obtenues sont robustes aux perturbations des données.

Nous nous penchons ensuite sur les problèmes d'optimisation avec contraintes en probabilités. Nous proposons une reformulation de ces problèmes sous la forme de problèmes bi-niveaux qui font apparaître le superquantile. Nous proposons une pénalisation (semi-)exacte pour cette reformulation, que nous traitons avec une méthode de faisceaux. Nous implémentons notre approche bi-niveau, dans un logiciel open-source, que nous illustrons sur des problèmes non-convexes.

Enfin, nous nous penchons sur l'utilisation du superquantile dans le cadre de l'apprentissage fédéré. Nous considérons le cas d'utilisateurs aux distributions de données hétérogènes et montrons comment le superquantile permet d'obtenir de meilleurs performances sur les utilisateurs les moins privilégiés. Notre algorithme est adapté aux contraintes réelles, en terme de communications et de protection des données. Nous en démontrons la convergence théorique dans le cas convexe en contrôlant simultanément la dérive des modèles locaux induite par la méthode de descente du gradient stochastique locale, ainsi que la redistribution de poids induite par le superquantile. Nous proposons aussi une étude numérique approfondie de notre algorithme en le comparant à un ensemble d'algorithmes constituant l'état de l'art en apprentissage fédéré, incluant notemment FedAvg, FedProx, Tilted-ERM et Agnostic Federated Learning. v REMERCIEMENTS Je souhaite tout d'abord exprimer mes plus chaleureux remerciements à mon directeur de thèse, Jérôme Malick, pour la bienveillance avec laquelle il a su me conseiller et me guider toutes ces années. J'ai découvert l'optimisation numérique à travers ses cours de Master 1, et ma passion pour le sujet n'a cessé de croître depuis. Son attention, sa générosité et sa patience ont sublimé mes années de thèse et décuplé mon enthousiasme pour la recherche. Merci pour tout.

Je tiens aussi à remercier chaleureusement Claudia Sagastizàbal et Joseph Salmon d'avoir accepté de rapporter cette thèse, et pour leur commentaires enthousiastes. Je remercie également Nadia Brauner, Alexandre d'Aspremont, Mert Gürbüzbalaban et Panayotis Mertikopoulos, pour m'avoir fait l'honneur d'être membre de mon jury de thèse.

Je tiens également à témoigner toute ma gratitude à Zaid Harchaoui pour la collaboration qu'il m'a offerte pendant cette thèse. Sa vision et son sens de l'exigence ont imprégné une part importante de mes travaux, pour lesquels je souhaite lui rendre hommage. Je souhaite également remercier Wim Van Ackooij et Franck Iutzeler pour les collaborations que nous avons eues, pour leur expertise, pour leur patience. Je souhaite remercier et saluer mes plus jeunes collaborateurs Gilles, Yu-Guan, Mitya and a special thanks for Krishna dont j'ai beaucoup appris et à qui je souhaite une grande réussite.

Mon expérience à Grenoble est aussi le fruit d'un environnement scientifique et humain fabuleux. Je souhaite en ce sens remercier les membres du petit groupe de lecture que nous avons monté: merci à Roland, Kimon, Anastasia, Sofiane, Panayotis, Waïss, Anatoli, Dima et Sergeï. Je salue aussi tous les autres membres du laboratoire et visiteurs que j'ai eu le plaisir de connaître durant ces trois dernières années. Je pense à vous Thibault, Anya, Modibo, Hubert, Nils, Anatole et bien d'autres. Merci aux chercheurs permanents du département pour leur bienveillance avec une pensée particulière pour Vincent et Adeline. Je souhaite enfin remercier mes co-bureaux Guillaume et Simon pour tout le soutien qu'ils m'ont apporté.

J'ai une pensée pour tous les enseignants que j'ai eu la chance d'avoir dans ma scolarité et une pensée particulière pour mon professeur de classe spéciales Hervé Gianella qui continue de m'inspirer aujourd'hui.

Je souhaite

CONTENTS

This section serves as an overview of the content of this manuscript. We first briefly introduce the topic of optimization under uncertainty with an emphasis on probabilistic approaches and convex risk measure theory. We then lay down the philosophy we adopt for the writing of this manuscript. We finally give a detailed summary of our contributions.

1.1

The proliferation of mobile phones, wearables and edge devices has led to an unprecedented growth in the generation of user interaction data. Simultaneously, we observe in various branches of sciences (e.g. biology, astrophysics, behavioural sciences, etc.) a steady commitment in the acquisition of massive datasets to better address contemporary questions. Tapping into the power of this rich data promises to greatly improve the next generation of intelligent applications, devices, and decision-making systems. However, this upheaval comes with a number of challenges, stemming either from technical limitations (upscaling the learning processes, heterogenous data, dealing with communication constraints) or societal concerns (safety, privacy, fairness, carbon footprint). The data involved is thus for decision-makers an important source of uncertainty but also a great opportunity to tailor their strategy in accordance. Such uncertainty is typically framed as a random variable ⇢ : ⌦ ! R m that is Stochastic optimization liable to affect a cost function 5 (F, ⇢) (or a constraint 6(F, ⇢)0) for a given decision F. In many cases, the random function 5 : R 3

⇥ R m ! R [ {+1} (resp. 6
) is evaluated in expectation and the decision maker has the task to find an optimal solution F 8 of the associated stochastic optimization problem

min F2R 3 E ⇥ 5 (F, ⇢) ⇤ . (1.1)
This approach has proved its relevance and efficiency in a number of applications; see for instance the references in the textbook [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF]. However, when high stakes are involved, an estimation in expectation is unlikely to hedge decision makers against risky outcomes. Fortunately, various options may be considered to better handle these worst-case events.

Robust Optimization. Robust optimization (see e.g. the textbook [START_REF] Ben-Tal | Robust Optimization[END_REF]) has

Robust optimization played a significant role in the management of risk for a large portion of optimization problems under uncertainty. The idea is to consider worst-case possible outcomes in a specific uncertainty set and design conservative solution in accordance with them. Formally, assuming that ⇢ lies almost surely in a subset ⇤ ⇢ R m , one typically removes all the stochasticity from (1.1) by considering the minimax variant min

E[-]

& ? (-) the superquantile ( ? (-) is defined as the mean of quantiles greater than the ?-quantile, ( ? (-) = 1 1 ? π 1 ? 0 =? & ? 0 (-)d? 0 .

( ? (-) = E[-| -> & ? (-)]
(1.4)

Superquantiles can be therefore interpreted as a measure of the upper tail of

Link with quantiles and cumulative distribution function

the distribution ofwith the parameter ? controlling the sensitivity to high losses. One easily deduces from the above definition that the superquantile is a continuous, non-decreasing function of ? and that it is a continuous, positively homogeneous function of -. For a given random variable -, as a consequence of [START_REF] Tyrrell | Random variables, monotone relations, and convex analysis[END_REF]Th. 2], one can recover from the cumulative distribution function - ofboth the ?-quantile and the ?-superquantile functions as functions of ?. Reciprocally, knowing either the ?-quantile or the ?-superquantile for all ? 2[0, 1] suffices to recover -. From a statistical viewpoint, these three notions are also equally consistent [START_REF] Tyrrell | Superquantiles and their applications to risk, random variables, and regression[END_REF]Th. 4] in the sense that convergence in distribution for a sequence of random variables (-= ) = 0 is equivalent to the pointwise convergence of the two sequences of functions ? 7 ! & ? (-= ), ? 7 ! ( ? (-= ). This is particularly relevant when the distributions are observed through data sampling. We can use the empirical cumulative distribution functions, quantiles and superquantiles all while upholding asymptotic convergence as the sample size grows.

In this thesis, we will exploit the properties of the superquantile under various angles to tackle challenging data-driven applications.

1.2

Before diving into the contributions I made during my PhD time, I would like to share with the reader the philosophy I adopted for this writing work. The few remarks below clarify the perspective with which I introduced my work as well as the scientific approach I adopted in each chapter of the contributions.

At the beginning of the writing of this thesis, I asked myself which coloration I wanted this work to have. The last three years had indeed given me the opportunity to work on different fields of research related to optimization which could not all be gathered in this manuscript without compromising its unity. Thus, I decided to select three research projects centered around the same topic of interest: the practical minimization of risk measures.

Chapters 2 and 3 of this thesis serve as a preliminary introduction to this work. First, I sought to stress the broad number of applications that probabilistic constraint and convex risk measures may encompass. Although my PhD work was not directly tied to industrial applications, I found important to illustrate their relevance in various contexts and this led me to focus in Chapter 2 on this task. Second, I wanted to emphasize in Chapter 3 the interplay between convex analysis and (distributional) robustness for the design and study of risk measures. Besides building upon the foundational works of A. Ruszczyński, A. Shapiro, and T. Rockafellar to provide such interpretation in a general and abstract context, I wished to showcase on a key class of risk measures, with elementary proofs, how dual reasoning could yield a geometric interpretation of risk aversion.

Such geometric considerations are the cornerstone of many rationales in my own contributions. This is why a consistent effort has been put into illustrating the concepts involved in each development of this thesis with figures, examples, and numerical experiments. I genuinely hope those will facilitate the reading of the more technical developments.

The personal contributions are contained in Chapters 4, 5, and 6. In each chapter, I sought to keep an operational approach with a balance between theoretical and practical contributions. Specifically, whenever this was possible, the situation considered was tied to an existing concept of mathematical optimization. In this sense, the titles of my sections are chosen to highlight the different concepts in optimization and convex analysis that come into play in this thesis. The practical implementation of these ideas and concepts stands also as an important contribution of this work. This is reflected in particular in Sections 4.3 and 5.4 with the short presentations of my software packages and in Section 6.5 where the experimental setting for the large-scale experiments in federated learning is presented.

1.3

Chapters 2 and 3 are preliminary chapters that gather a number of definitions, properties, examples, and illustrations to introduce the main concepts of this thesis. The remaining chapters 4, 5, and 6 contain our personal contributions. We provide now an overview of these results with two levels of presentation. We start with a short high-level picture of them. Then, we specify for each chapter how they are organized and give some context.

Contributions

We first lay down a brief summary of our contributions.

• Managing risk has become a central issue in machine learning.

Minimizing superquantile-based risk measures

Superquantile-based risk measures offer a convenient way to model risk-aversion by focusing on worst-case scenarios. In this thesis, we consider the problem of minimizing such risk measures. We advocate for the use of first-order methods with a special focus on the derivation of efficient oracles. More precisely, we analyze the possible nonsmoothness induced by superquantiles and provide a generic smoothing procedure. We also extend our smoothing approaches to the class of law-invariant comonotone risk measures. Finally, we release a companion software, SPQR, which implements in python the algorithms described and allows practitioners to easily experiments with superquantile-based supervised learning.

• In contrast with convex risk measures, chance-constrained programs

Solving chance-constrained problems

present specific challenges due to the non-convexity induced by the chance constraint. We propose an algorithm for the solving of a general chance-constrained problem. We first propose a reformulation as a bi-level program. We then propose an approach to solve these problems mixing a variety of techniques and concepts coming from different subdomains of optimization (penalization, weak sharpness, error bounds, DC programming, bundle algorithms, etc.). We finally release an open-source python toolbox implementing the approach, with a special emphasis on fast computational subroutines.

• The emergence of privacy and fairness concerns in distributed optimiza-

Handling heterogeneity in federated learning

tion has spurred significant interest in the machine learning community. Federated learning is a nascent privacy-friendly paradigm for large-scale networks. In Federated learning, many devices (e.g. mobile phones) collaboratively train a model under the orchestration of a central server (e.g. a service provider), while keeping the data on device throughout the training and coordination processes. We propose a federated learning framework that operates on heterogeneous devices. The approach hinges upon a superquantile-based learning objective to stress the impact of disadvantaged users in the training process. We present a stochastic training algorithm compatible with the privacy concerns of federated frameworks. We analyze its convergence and we support it with extensive numerical experiments.

We move now to a more in-depth overview of our contributions, that we break down by chapters.

: -.

In Chapter 4, we aim at providing efficient minimization procedures for a prac-This chapter is mostly based on our papers , , .

tical class of convex risk measures provided by the Kusuoka representation [START_REF] Kusuoka | On law invariant coherent risk measures[END_REF]. That is, we aim at solving problems of the form min F ⇢ 5 (F, ⇢) (1.5) where ⌧ a risk measure of the form

⇢(-) = π 1 ?=0
(?)( ? 0 (-)d? 0 , with : [0, 1]!R + an arbitrary weight function and ( ? 0 the superquantile (1.4) at level ? 0 .

Context. The superquantile can be traced back to the paper [START_REF] Ben | Expected utility, penalty functions, and duality in stochastic nonlinear programming[END_REF]. It stands out as one of prominent examples of risk measures, well established in economics and finance [START_REF] Ben | An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent[END_REF][START_REF] Tyrrell Rockafellar | Optimization of conditional valueat-risk[END_REF]. Superquantiles have been extensively studied from a convex analysis perspective: we refer for instance to [START_REF] Tyrrell Rockafellar | Optimization of conditional valueat-risk[END_REF] for a variational formulation of the superquantile, to [START_REF] Ben | An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent[END_REF][START_REF] Chouzenoux | General risk measures for robust machine learning[END_REF] for its generalization to a larger class of risk measures, to [START_REF] Föllmer | Convex measures of risk and trading constraints[END_REF] for a dual formulation (also later generalized in [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF] or [START_REF] Tyrrell | Conditional value-at-risk for general loss distributions[END_REF]) and [START_REF] Tyrrell | Random variables, monotone relations, and convex analysis[END_REF] for additional convex results: for a thorough discussion and many references, we refer to the seminal work [START_REF] Tyrrell Rockafellar | Optimization of conditional valueat-risk[END_REF], the classical textbook [START_REF] Shapiro | Lectures on Stochastic Programming: Modeling and Theory, Second Edition[END_REF]Chap. 6], or the tutorial paper [START_REF] Tyrrell | Superquantiles and their applications to risk, random variables, and regression[END_REF]. We will come back to these results in Chapter 3. These nice theoretical properties have given interesting results in various domains, including fair learning [START_REF] Williamson | Fairness risk measures[END_REF], adversarial classification [START_REF] Ho-Nguyen | Adversarial classification via distributional robustness with Wasserstein ambiguity[END_REF] and reinforcement learning [START_REF] Tamar | Policy gradient for coherent risk measures[END_REF]. We will come back to some of these applications in Chapter 2. Regarding computational solving, the idea of using first-order for superquantile-based learning.This toolbox is built off the popular software library scikit-learn. We provide computational experiments illustrating (i) the interest of using quasi-Newton algorithms for minimizing superquantile-based objective and (ii) the robustness of superquantilebased models compared to the standard models obtained from empirical risk minimization.

: -.

In Chapter 5, we consider the solving of chance-constrained problems in

This chapter is based on our paper data-driven contexts. Specifically, we study problems of the form

> > <

> > :

and assume 5 : R d ! R and ( ⇢ R d to be convex, 6 : R d ⇥R < ! R to be convex with respect to G and ⇢ : ⌦ ! R < to be observable through data sampling.

Context. Solving (non-convex) chance-constrained problems is notoriously difficult. Several computational methods have been proposed, regardless of any considerations of convexity and smoothness, and under various assumptions on uncertainty, see e.g. [START_REF] Van Ackooij | A discussion of probability functions and constraints from a variational perspective[END_REF] for an overview. We note that when distributions are observed through data sampling, two main approaches have been considered. First, mixed-integer approaches [3] were considered to encode the probability constraints via binary activation variables; we refer to [START_REF] Luedtke | An integer programming and decomposition approach to general chance-constrained mathematical programs[END_REF][START_REF] Luedtke | A branch-and-cut decomposition algorithm for solving chanceconstrained mathematical programs with finite support[END_REF][START_REF] Luedtke | An integer programming approach for linear programs with probabilistic constraints[END_REF] for a deeper dive into this topic. Second, a considerable interest has been given to approximations of the probabilistic constraints , e.g. via convolutions [4] or by a difference of convex functions [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF][START_REF] Hong | Sequential convex approximations to joint chance constrained programs: A monte carlo approach[END_REF].

In chapter 5, we propose a third approach based on a reformulation of chance-constrained problems into bilevel programs. In recent years, bilevel programming has received considerable interests in the field of machine learning, where it is used for hyperparameter selection procedures [START_REF] Bertrand | Implicit differentiation of lasso-type models for hyperparameter optimization[END_REF]. The solving of general bilevel programs via exact penalization was historically proposed in [START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF] but still remains difficult due to the eventual non-convexity of the induced penalization. In our case, we point out the "Difference of Convex" structure of the obtained penalization and propose to use a bundle method to solve it. While bundle methods [START_REF] Bacaud | Bundle methods in stochastic optimal power management: A disaggregated approach using preconditioners[END_REF][START_REF] De | Bundle methods in the xxist century: A bird's-eye view[END_REF] were initially considered for convex problems, their relevance on difference of convex objectives was recently showcased in [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF][START_REF] Wim Van Ackooij | A bundle method for nonsmooth dc programming with application to chance-constrained problems[END_REF].

Contributions.

In this chapter, we present a new reformulation of chanceconstrained programs as bilevel programs. We turn this reformulation into a single-level problem with a Difference of Convex (DC) objective via a semi-exact penalization. More specifically: fitting, in average, a model to the data distribution of the devices available for training. Formally, given a stochastic objective (F, ⇢) and # training devices with respective data distributions @ 8 , FedAvg aims at minimizing the aggregated objective:

min F2R d E ⇢⇠ @ [ (F, ⇢)] + ⌫ 2 kFk 2 , (1.7)
where

@ = 1 # # ' 8=1 @ 8 (1.8)
denotes the aggregated distribution of data-points over the whole set of training devices. While this approach works for users who conform to the aggregated distribution @, it is liable to fail on non-conforming individuals, leading to poor user experience (e.g. next word prediction on mobile phones). In Chapter 6, we provide a new federated framework to address the statistical heterogeneity among the devices of the network.

Context. Addressing statistical heterogeneity in federated learning has led to two lines of work. The first develops algorithmic techniques to alleviate the effect of heterogeneity on convergence rates while still minimizing the classical expectation-based objective function (1.7). These techniques include the use of proximal terms [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF], control variates [START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF] or augmenting the server updates [START_REF] Sashank | Adaptive Federated Optimization[END_REF][START_REF] Wang | Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization[END_REF]; we refer to the recent survey [START_REF] Wang | A field guide to federated optimization[END_REF] for details. The second line of work addressing heterogeneity involves designing new objective functions by modeling statistical heterogeneity. The AFL framework minimizes the worstcase error across all training devices [START_REF] Mohri | Agnostic Federated Learning[END_REF]. @-FFL framework [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF] draws from fair resource allocation literature and proposes to minimize the ! ? norm of the per-device losses. A federated optimization algorithm for AFL was proposed and its convergence was analyzed in [START_REF] Deng | Distributionally Robust Federated Averaging[END_REF]. Finally, a classical risk measure, namely the entropic risk measure, was considered in [START_REF] Li | Tilted Empirical Risk Minimization[END_REF]. We note that no Only step 1 0 is specific to -FL and can be interpreted as an additional filtering step among selected device to choose which device will run the local updates. Mathematically, this filtering steps interpret as a composition with the superquantile -see more in Chapter 6.

convergence guarantees are currently known for the stochastic optimization algorithms developed for these non-usual frameworks.

Contributions.

In this chapter, we design a practical and theory-backed framework for the handling of non-conforming users in statistically heterogeneous federated environments.

1. We introduce the -FL framework which seeks to provide a minimal -FL framework level of predictive performance on nonconforming devices. The framework relies on a superquantile-based objective to minimize the tail statistics of the prediction errors on the client data distributions. Specifically, given a scalar parameter ? 2[0, 1], we propose to replace the standard objective in (1.7)by min F2R 3 ( ? ⇢⇠ @ ( (F; ⇢))

+ ⌫ 2 kF k 2 , (1.9)
with @ as defined in (1.8).

We propose a new federated algorithm to solve this problem. Our

Theory-backed algorithm algorithm, illustrated in Figure 1.4 builds off the baseline FedAvg with an additional filtering step over training devices with poorest performances. We provide a convergence analysis in the strongly convex case.

3. We present extensive numerical results to support our framework. We

Extensive numerical experiments use linear models and neural networks, on tasks including image classification and sentiment analysis based on public datasets. The simulations demonstrate superior performances of -FL over state-of-the-art baselines on the upper quantiles of the error on test devices, with particular improvements on data-poor devices, while being competitive on the mean error.

Further works non included in this thesis

During my time as a PhD student, I also had the opportunity to work on two other projects that will not be developed in this thesis. I provide below a brief summary of each. Further information can be found in my webpage -. Probabilistic constraints result from taking the probability measure of a given set This project led to the paper of random inequalities depending on the decision vector. Even if the original set of inequalities is convex, this favourable property is not immediately transferred to the probabilistically constrained feasible set and may in particular depend on the chosen safety level. In this project, we provided results guaranteeing the convexity of feasible sets to probabilistic constraints when the safety level is greater than a computable threshold. This is often referred to as a situation of "eventual convexity". The key idea in our approach is to reveal the level of underlying convexity in the nominal problem data (e.g., log-concavity of the probability function) by auxiliary transforming functions. We provided several examples illustrating our theoretical developments.

. Progressive Hedging is a popular decomposition algorithm for solving multistage stochastic optimization problems. A computational bottleneck of this algorithm is that all scenario subproblems have to be solved at each iteration. In this project, we introduced randomized versions of the algorithm able to produce new iterates as soon as a single scenario subproblem is solved. Building on its relation with monotone operators, we leveraged recent results on randomized fixed point methods to derive and analyze the proposed methods. Finally, we released the corresponding code as an easy-to-use Julia toolbox and report computational experiments showing the practical interest of randomized algorithms, notably in a parallel context.

List of publications

We end up this introduction with a list of our published/submitted papers during our time as PhD candidate.

SELECTED APPLICATIONS

In this section, we review a number of applications where probabilistic and superquantile-based decision problems appears. We first start with traditional applications in operation research (portfolio optimization and energy management). We then move to the field of in machine learning. For each example, we keep a high-level point of view: we insist only on the main elements of the modeling process and we omit the technical details. This chapter has only an illustrative purpose. It can be skipped without harming the understanding of our contributions.

2.1

In this section, we review two applications of optimization under uncertainty in operations research. We start with a classical portfolio optimization problem. We introduce then the problem of reservoir-planning in hydro-management.

Portfolio optimization

Since the pioneering work of Markowitz [START_REF] Markowitz | Portfolio selection[END_REF], portfolio selection has much

Portfolio management evolved, stemming from both the development of risk models and the derivation of efficient computational methods. The objective of a typical asset allocation problem is to maximize the expected return of a portfolio optimization problem while hedging against potential losses. Formally, given a random vector of returns ' = (A 1 , ..., A = ), one wishes to find an allocation solution of

( max F E[F > '] s.t. ⇢ ( F > ')  ⌘
where ⇢ : L 1 (⌦)!R denotes a risk measure aimed at upper-bounding the level risk exposition of the investment F > '.

Financial regulations on risk have often been set in terms of quantiles of

Value at Risk a distribution of losses or rewards. For instance, given a random variable * that quantifies the losses of an investment, and a safety threshold ? 2( 0, 1), the Value at Risk is defined as the ?-quantile & ? (*) of *. It is commonly considered for high levels of probability: ? 2{0.95, 0.98, 0.99}. Asset allocation problems involving the Value at Risk -see e.g. [START_REF] Lucas | Extreme returns, downside risk, and optimal asset allocation[END_REF] -are commonly framed as

( max F E ( [F > '] s.t. & ? ( F > ')⇣ (2.1)
where ⇣ denotes an arbitrary threshold to be set by the risk modeler and & ? (.) denotes the quantile function as defined in (1.3). While very popular across the banking institutions, such measures of risk remain hard to optimize due to their non-convex properties (as showcased in Figure 1.3). Over the past two decades, the superquantile, introduced in Section 1.1, has become a powerful alternative, thanks to its nice convex and regular properties. For a distribution of losses * and a probability threshold ? close to 1, the associated superquantile ( ? (*) returns the average of the quantiles that are greater than the ?-quantile. Hence, for similar probability levels, the superquantile offers a more conservative estimation of risk than the Value at Risk. One may then reconsider problem (2.1) with the superquantile in place of the quantile or even a penalization of this problem yielding for some ⇠>0 max

F E ( [F > '] ⇠( ? ( F > ')
Owing to the seminal work of Rockafellar and Uryasev [START_REF] Tyrrell Rockafellar | Optimization of conditional valueat-risk[END_REF], the practical solving of such problems may be achieved by various methods including linear programming and subgradient-based methods. In this thesis, special efforts have been made for the use of the superquantiles in large-scale contexts.

Reservoir planning

Dealing with uncertainty is a recurrent challenge in energy planning. For

Hydro valley management

instance, when considering the management of a hydro valley, one has to deal with meteorological constraints of the surrounding environment. Such constraints can be prone to unpredictable variations over a short time scale. The hydro valley is composed of a network of hydro powers plants with their associated turbines. Schematically, the aim of a reservoir planning problem is to optimize the usage of the turbines to meet the power demand while ensuring the feasibility of the operations, under the uncertainty of the inflows. Such problems can be modeled as:

min G 0,G2R n 2 > G s.t G  1 D + ⇠G  ⇢ 8  E + ⇠G. (2.2)
In the above problem, the variable G denotes the controls on the set of turbines at stake, for instance in terms of cubic meters, per hour of turbined outflow. The objective h2,.i encodes the amount of water processed together with the quantity of electricity power generated. The first affine constraint encodes the modeling of the flow within the network, the bounds on the turbining and the global use of water. The second constraint involves the uncertain amount of water stemming from uncertain inflows modeled by the realization ⇢ 8 of the random vector ⇢ : ⌦ ! R < (< 2 N). This constraint is present to ensure that no overrun of the maximal reservoir capacity is observed. For more details on the modeling of reservoir planning problems, we orient the reader to the paper [START_REF] Wim Van Ackooij | Joint chance constrained programming for hydro reservoir management[END_REF] and the thesis [START_REF] Van Ackooij | Chance constrained programming: with applications in Energy Management[END_REF]. Satisfaction of the stochastic constraint (2.2) can either be required in expecta-

Modeling via chance constraints

tion or with high probability. For the latter option, one thus needs to fix a safety threshold ? close to 1 and consider the probabilistic constraint:

P [D + ⇠G  ⇢  E + ⇠G] ?.
Modeling of reservoir planning problems via probabilistic constraints has received considerable interest, e.g. [START_REF] Ncp Edirisinghe | Capacity planning model for a multipurpose water reservoir with target-priority operation[END_REF][START_REF] Daniel P Loucks | Water resource systems planning and analysis[END_REF][START_REF] Zorgati | Supply shortage hedging: estimating the electrical power margin for optimizing financial and[END_REF] with use of various methods to solve it including penalty methods [START_REF] Prékopa | Serially linked reservoir system design using stochastic programing[END_REF], supporting hyperplane methods [START_REF] Prékopa | Flood control reservoir system design using stochastic programming[END_REF] or bundle methods [START_REF] De | Bundle methods in the xxist century: A bird's-eye view[END_REF]. In the chapter 5 of this thesis, we will consider the solving of a general class of chance-constrained problems.

2.2

We move now to a selection of more recent topics in machine learning where superquantiles may be useful. The application from Section 2.2.2, in particular, has motivated the developments of the whole Chapter 6.

Safe machine learning

Classical supervised learning via empirical risk minimization hinges upon the ERM limitations assumption that the testing distribution coincides with the training distribution. This assumption can be challenged in domain applications of machine learning such as visual systems or dialog systems [START_REF] Recht | Do imagenet classifiers generalize to imagenet?[END_REF]. Learning machines may indeed operate at prediction time with testing data whose distribution departs from the one of the training data. Thus, in the face of prevalence of worst-case scenarios or unexpected distributions at prediction time, ensuring robust behavior becomes a relevant strategy. This highlights the importance of reconsidering the learning objective used to train learning machines.

Formally, consider a data-driven setting where a random function 5 (F, ⇢) Data-driven setting can be estimated through a sample of data-points ⇢ 1 , ..., ⇢ = , (= 2 N). This is a standard situation in classical supervised learning where, in the training phase, we have access to = data-points: each data-point is a pair (0, 1), where 0 2 is a feature vector and 1 2 ⌫ is its corresponding target. For instance, for a binary image classification task, 1 is a boolean encoding the membership of the image 0 to one of the two classes. From this training data, the aim is to learn a parameter F 2 , ⇢ R d (as "weights") of a given prediction function !(F, •) that produces, for an input 0 2 , a prediction I = !(F, 0)2/ of the associated target 1 2 ⌫. Typical examples of prediction functions include simple linear models !(F, 0) = F > 0, polynomial models (as in Example 2.1 below), or artificial neural networks

!(F, 0) = F > B B (• • • 1 (F > 1 0)) , (2.3)
which are successive compositions of linear models F 9 and non-linear activations . The prediction error is then measured by a loss function

✓ : ⌫ ⇥ / ! R.
Typical examples of loss functions include the least-squares loss (⌫ = R, / = R) or the logistic loss (⌫ = { 1, 1}, / = R), defined respectively as In the risk-neutral setting, assuming1 that the training data are generated from a given distribution % over ⇥ ⌫, the "best" model parameter F solves the optimization problem

✓ (1, I) = 1 2 (1 I)
min F2, ⇥ '(F) = E (0,1)⇠% ⇥ ✓ (1, !(F, 0) ⇤⇤ . (2.5)
This framework is currently challenged by important domain applications [e.g., [START_REF] Kairouz | Advances and open problems in federated learning[END_REF][START_REF] Recht | Do imagenet classifiers generalize to imagenet?[END_REF], in which several of the standard assumptions turn out to be limiting. Indeed classical supervised learning assumes that, at training time, the sampled examples (0 1 , 1 1 ), ..., (0 = , 1 = ) are drawn i.i.d. from a given distribution %, and that, at testing time, we face a new example 0 0 , also drawn from the same distribution %. However, recent failures of learning systems when operating in unknown environments [START_REF] Knight | A self-driving Uber has killed a pedestrian in Arizona[END_REF][START_REF] Metz | Microsoft's neo-Nazi sexbot was a great lesson for makers of AI assistants[END_REF] emphasized the importance of taking into account that we may not face the same distribution at test/prediction time.

A simple way to enforce robustness is to replace the expectation in (2.5) by a

Safe machine learning

convex risk measure ⇢. The resulting objective is:

min F2, h R(F) =⇢ (0,1)⇠% ⇥ ✓ (1, !(F, 0) ⇤ i . ( 2.6)
In this thesis, we focus on a particular class of risk measures that we will introduce in Section 3.2. A special attention will be given to superquantiles, defined in (1.4), for their fundamental role among such risk measures. We provide a short illustrative example below.

Example 2.1. We illustrate the interest of superquantile learning in presence Superquantile least-square regression of heterogeneous data, on an elementary regression task. Consider a dataset gathering two different subgroups: for two unknown models F1 and F2 in ' 3 we assume 80% of the points are generated according to

H 8 = F1 0 + F1 1 G 8 + F1 2 G 2 8 + ⌘ 8 where ⌘ 8 ⇠ N (0, 2 ) , (2.7)
and the remaining 20% are generated according to

H 8 = F2 0 + F2 1 G 8 + F2 2 G 2 8 + ⌘ 9 where ⌘ 9 ⇠ N (0, 2 ) . (2.8)
Then we can compare the usual approach using ordinary least-squares

min F2R 3 E (G,H)⇠P = ⇥ (H (F 2 F 2 + F 1 G + F 0 )) 2 ⇤ , (2.9)
with its superquantile counterpart of the form:

min F2R 3 [( ? ] (G,H)⇠P = ⇥ (H (F 2 F 2 + F 1 G + F 0 )) 2 ⇤
(2.10) using ⇢=( ? for ? = 0.9.

We report on Figure 2.1 the distribution of residuals

A 8 = |H 8 (F 2 G 2 8 + F 1 G 8 + F 0 )
| for both models. The superquantile model (2.10) shows an improvement of 90/95th quantiles of the distribution of residuals, which appears on histograms as a shift of the upper tail to the left. This comes at the price of a degraded performances on average, which appears on the figure as the shift of the peak of residuals to the right. ⇤

Federated optimization

Federated learning is an emerging framework in machine learning where many clients collaboratively train a common model under the orchestration of a central server, while keeping their data decentralized [START_REF] Gafni | Federated learning: A signal processing perspective[END_REF][START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF][START_REF] Yang | Applied federated learning: Improving google keyboard query suggestions[END_REF]. In a standard federated learning setting, we wish to optimize the performances of a single model F 2 R d deployed over a large population of clients. We assume that each client has data, drawn i.i.d. from a distribution @. The loss incurred on this device is (F; @) := E ⇢⇠@ [ 5 (F; ⇢)], where 5 (F; ⇢) is the chosen loss function (such as the logistic loss) on input-output pair ⇢ under the model F. The expectation above is assumed to be well-defined and finite. For a given distribution @, smaller values of (•; @) denote a better fit of the model to the data.

Given # client devices available for training, we denote the loss on device :

Vanilla Federated learning by : (F) := (F; @ : ). Vanilla Federated learning aims at minimizing a weighted average of the losses attached to training devices,

min F2R d # ' 8=1 8 8 (F) (2.11)
where the weights 8 are typically set to be proportional to the size of the local dataset in each device. While the minimization of such sums are ubiquitous in machine learning, federated learning comes with a number of specific challenges that we outline below. For detailed explanations, we point the reader to the recent reviews [START_REF] Kairouz | Advances and open problems in federated learning[END_REF][START_REF] Li | Federated Learning: Challenges, Methods, and Future Directions[END_REF][START_REF] Wang | A field guide to federated optimization[END_REF].

Privacy constraints. The protection of user's data is a critical issue in federated

Federated learning challenges learning. This is achieved by keeping the processing of the data local to the devices while the server coordinates with the devices for a secure aggregation(see e.g. [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF]) of model updates.

Communication constraints.

In federated learning, the central server is responsible for the orchestration of a huge network with possibly unreliable transmissions. Thus, communications rapidly become a bottleneck calling for the design of communication-efficient algorithms. Efficiency can either be performed through the development of compression algorithms [START_REF] Chraibi | Distributed fixed point methods with compressed iterates[END_REF][START_REF] Philippenko | Preserved central model for faster bidirectional compression in distributed settings[END_REF][START_REF] Vogels | Powersgd: Practical low-rank gradient compression for distributed optimization[END_REF] or the reduction of communications via the execution of several local steps within devices [START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF][START_REF] Khaled | Tighter theory for local sgd on identical and heterogeneous data[END_REF][START_REF] Stich | Local SGD Converges Fast and Communicates Little[END_REF]. In addition, only a small random proportion of the training clients is likely to be available at each stage of the training process.

Statistical heterogeneity.

Statistical heterogeneity is also key feature of federated learning: client data distributions are not identical. Each user has unique characteristics which are reflected in the data they generate. These characteristics are influenced by personal, cultural, and geographical factors. For instance, the varied use of language contributes to data heterogeneity in a next word prediction task. In this context, the satisfaction of users that do not conform to the average training data distribution and underlying fairness concerns have attracted considerable interest in recent years. Such limitations have motivated the development of new frameworks to serve more fairly the entire population of users [START_REF] Laguel | A Superquantile Approach to Federated Learning with Heterogeneous Devices[END_REF][START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF][START_REF] Mohri | Agnostic Federated Learning[END_REF]. All aforementioned references share the common feature of replacing the weighted average in the objective (2.11) by a risk-aware function ⇢ : R # ! R meant to better capture non-conforming users. The objective considered becomes:

min F2R d ⇢ [ K (F)]
(2.12)

where K : ~1, # ! R is a random variable satisfying P[K = :]/ : . Example 2.2. Consider a specific instance of Example 2.1 in a federated setting.

Federated regression

We consider that 80% of the data corresponds to four devices having the same data distribution following (2.7), while the remaining 20% corresponds to a fifth device having its own distribution following (2.8). In this example, for : 2 ~1, 5, the loss : corresponds to the regression objective on the dataset owned by the : C⌘ user. Figure 2.3 shows this bivalent dataset: blue points correspond to the data of the four first devices, and red points correspond to the last device. We want a regression that captures worst-cases for both behaviours. We plot on Figure 2.3 the regression models given by the classical leastsquares regression (2.9), the superquantile least-squares regression (2.10), and a federated variant of the superquantile least-squares that operates at a user level, i.e. by using the superquantile as ⇢ in (2.12) . We can make three observations. First the standard model (2.9) (in purple) tends to follow the trend imposed by the first four devices. Second, the superquantile model (2.10) (in orange) has better regression on worst-case data, irrespective of the group of the data point. Finally the federated superquantile model (2.12) finds, in contrast, a compromise between the two trends. Thus, federated superquantile regression better captures the (red) data points of the non-conforming user. We want commensurate performances among users, which means, graphically, a curve at the same distance from the data-points of the conforming users (in blue) and the non-conforming user (red).

⇤

Fairness in AI

Algorithmic fairness has received much attention over the past decade due to the fairness issues raised in a number of machine learning applications (e.g. the pre-screening of job applications). The objective of a fair algorithm is to reduce the bias that standard algorithms are prone to stress on one or several subgroups of users while still maintaining reasonable estimation performances.

As recalled in Section 2.2.1, in classical supervised machine learning, we consider problems of the form

min F E 0,1 [✓ (1, !(F, 0)]
where 0, 1 are drawn from a distribution over the input-output space , ⌫, !(F, •) :

! / is a predictor function parametrized by the weights vector F 2 R d and ✓ : ⌫ ⇥ / ! R is a given error function. In a fair machine learning Fair machine learning context, one has to deal in addition with the presence of a sensitive feature B 2 ( (e.g. gender or race) calling for the satisfaction of a fairness constraint. Formally, one first needs to design map F : ⌫ ⇥ / ⇥ ( ! R that permits to gauge the level of unfairness of a given predictor !(F, •) over the extended dataset (0, 1, B).A fair formulation of the above problem is then to solve for a given ⌘>0:

( min F E 0,1 [✓ (1, !(F, 0)] s.t. F(1, !(F, 0), B)⌘ (2.13)
The fairness constraint may be designed in various ways that are not systematically coherent with each other -see e.g. the discussion [START_REF] Kleinberg | Inherent trade-offs in algorithmic fairness[END_REF]. While many works have investigated the practical handling of fairness constraints for specific learning tasks [1] such as classification or regression [2,[START_REF] Chzhen | Fair regression with wasserstein barycenters[END_REF], we limit this brief introduction to a general supervised learning context. We adopt below the perspective laid down in [START_REF] Williamson | Fairness risk measures[END_REF] to introduce several popular examples of fairness constraints.

Perfect and approximate fairness. Situations of perfect fairness often allude to a Given weights F 2 R d , demographic parity [START_REF] Dwork | Fairness through awareness[END_REF] denotes complete statistical independence between the predictor !(F, •) and the sensitive attributes B, !(F, 0)? ?B

where ?? denotes the statistical independance. Alternatively, the concept of equality of opportunity [START_REF] Hardt | Equality of opportunity in supervised learning[END_REF] allows for the prior knowledge of the outputs

!(F, 0)? ?B | 1.
Such assumptions, considered as ideal, often lead to singularly difficult optimiza-

Approximate fairness

tion problems [1]. Instead one may consider approximate variants by bounding for instance the level of dependence between B and !(F, •). In [START_REF] Kamishima | Fairness-Aware Classifier with Prejudice Remover Regularizer[END_REF], the authors consider the Kullback-Leibler divergence to measure such independence:

F(1, !(F, 0), B) = ! ⇣ P !(F,0),B | P !(F,0) ⇥ P B ⌘ .
Solving such problems remains difficult in general due to the non-convexity induced by the fairness constraint as a function of F.

Fairness via Subgroup Losses. The notion of subgroup risk, introduced

Subgroup risk in [START_REF] Williamson | Fairness risk measures[END_REF], consists in measuring the fairness of a given predictor with respect to the sequence of losses evaluated among the subgroups defined by the sensitive feature B. Specifically, given a sensitive attribute B 2 ( and a predictor !(F, •), the subgroup risk of !(F, •) is defined by

! B (F) := E 0,1|B=B ✓ (1, !(F, 0)).
The fairness constraint is then defined in terms of deviations of the conditional expectation ! B (F), turning (2.13) into

( min F E B [! B (F)] s.t. D(! B (F))  ⌘
where D : ! 1 (⌦)!R denotes an arbitrary measure of deviation. Penalization of the above deviation constraint amounts to the minimization of a single objective that holds as a composition of a risk measure ⇢ : ! 1 (⌦)!R with the subgroup risks involved min

F2R d ⇢ (! B (F)) .
In this context, [START_REF] Williamson | Fairness risk measures[END_REF] advocate for the use of the superquantile and show empirically how it may enforce fairness on illustrative examples. We will show in Chapters 4 and 6 of this thesis that such approach may be extended to large-scale situations thanks to the nice properties of the superquantile.

Example 2.3. Let us come back to the toy Example 2.2. We look at it with the

Fair regression perspective of fairness between the predominant group (the four blue users) and the minority group (the fifth "red" user). Table 2.1 compares (i) the average performance over the predominant group and (ii) the average performance on the minority group. We observe that the difference between these performance is minimal for the user-level superquantile model provided by (2.12), achieving better approximate group fairness.

⇤ TECHNICAL PRELIMINARIES

In this chapter, we formally introduce some of the main concepts involved in this thesis. We first provide a general framework for the measurement of random losses with a particular focus on the role that convexity plays to enforce distributional robustness. We then present the class of law-invariant comonotone risk measures and lay out their nice geometric and functional properties. We make a special emphasis on the superquantile which is at the core of this thesis, especially in Chapters 4 and 6. We finally move to chance-constrained problems and present some of their specific challenges that will be addressed in Chapter 5. Experienced readers may skip this chapter: next chapters provide precise pointers to the results below if needed.

-

We present in this section a general framework to model risk aversion in a stochastic environment. We draw on the setup laid down in [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF] and the general topological and convexity results from the textbooks [START_REF] Ruszczynski | Stochastic programming[END_REF][START_REF] Walter | Real and complex analysis[END_REF][START_REF] Zalinescu | Convex analysis in general vector spaces[END_REF]. To lighten the presentation, we will give precise pointers to references only for the fundamental results. We will implicitly refer to these general textbooks for intermediate or secondary results and developments.

Duality in probability spaces

We start this section with brief reminders on duality in probability spaces through a rather abstract setting that will be specialized later in this chapter.

Pairing random variables and measures. Let (Ω, F) be a fixed measurable Topological dual of a set of random variables space and consider a linear space X of random variables from Ω to R. We pair X with an arbitrary linear space Y of finite signed measures satisfying:

π Ω |-| d|⇠| < 18 -2 X , 8⇠ 2 Y
where |⇠| := ⇠ + + ⇠ and (⇠ + , ⇠ ) denotes the Jordan decomposition of ⇠.

Furthermore, we assume that X and Y are locally convex topological vector spaces such that the scalar product is compatible with the respective topologies on X and Y. That is, Y is the topological dual of X and no linear functional of the form h., ⇠i nor h-,.i is identically null for any -2 X and ⇠ 2 Y.

Example 3.1 (Basic examples of pairings)

. A standard setting is to have, for any -finite measure on (Ω, F) and ? 2[1, 1), X as the quotient space R ? (Ω, F, ).

A natural choice for Y is then the set of absolutely continuous measures ⇠ with respect to admitting a Radon-Nikodym derivative in R @ , where

functional ⇢ : X ! R [ {+1} the Fenchel conjugate of ⇢, denoted ⇢ ⇤ : Y ! R [ {+1} as: ⇢ ⇤ (⇠) = sup -2X h-, ⇠i ⇢(-)
and the Fenchel biconjugate

⇢ ⇤⇤ : X ! R [{1}of ⌧ as ⇢ ⇤⇤ (-) = sup ⇠2Y h-, ⇠i ⇢ ⇤ (⇠).
As the maximum of linear functions, the fenchel biconjugate is a convex function with respect to -. Note that we always have ⇢ ⇤⇤ (-) = (⇢ ⇤ ) ⇤ (-) for all -2 X but the equality ⇢ ⇤⇤ = (⇢ ⇤ ) ⇤ does not necessarily hold, since X is not necessarily equal to its bidual. It is however valid whenever X is a reflexive Banach space (e.g. X = R ? for ? > 1).

From random variables to random losses. In many applications, the random

Measuring random losses

variableis of the form 5 (F, ⇢) and characterizes the cost of a given model F 2 R d while exposed to a random variable ⇢ : Ω ! R m . Thus, a straightforward way to measure the loss incurred by F is to fix a measure 2 Y and consider:

(F) :=⇢( 5 (F, ⇢)) = π Ω 5 (F, ⇢($)) d ($). (3.1)
Under suitable conditions, the expected value function : R d ! R may inherit the properties satisfied by the integrand F 7 ! 5 (F, ⇢). For instance, if (8) 5 is lower semi-continuous with respect to F and (88) for F 0 locally around F, 5 (F 0 , •) can be uniformly dominated by an integrable random variable, then is known to be lower semi-continuous as well (see for instance proposition 14 from [144, Chapter 1]). If one assumes in addition 5 to be convex with respect to F, then one may subdifferentiate by interchanging the integral and the subdifferential:

% (F) = π Ω % 5 (F, $) d ($) := ⇢π Ω 6 d , B.C. 6:Ω!R 3 measurable 6($)2% 5 (F,$), 8$2⌦ . (3.2)
According to the terminology of [START_REF] Rockafellar | Variational Analysis[END_REF], such functions F 7 ! 5 (F, ⇢) are called normal convex integrands. For a proof of such standard result, see for instance Theorem 9 of [144, Chapter 2].

Convex risk measures and Fenchel-Moreau's theorem

Relying only on a single measure to evaluate the cost of a given model F Convex risk measures via (3.1) may be insufficient to hedge against risky events. Instead, we are looking for some risk functional ⌧ : X ! R that can stress the impact of worstcase possible outcomes under various distributional shifts. With this in mind, one may note that convex risk measures, i.e, functionals satisfying

⇢(⌫-+(1 ⌫).)⌫ ⇢(-)+(1 ⌫) ⇢(.), 8-, . 2 X , 8⌫ 2[0, 1],
offer a natural interpretation of robustness. This a consequence of the Fenchel-Moreau theorem:

Proposition 3.1. Let X be a locally compact Haussdorf space, paired with its topological

The Fenchel-Moreau theorem dual X ⇤ , and ⇢ : X ! R a proper, convex, lower-semi-continuous functional. Then, for all -2 X , we have:

⇢(-) =⇢ ⇤⇤ (-) = sup ⇠2X ⇤ h-, ⇠i ⇢ ⇤ (⇠). (3.3)
As a consequence, proper l.s.c. convex risk measures are pointwise solutions of robust optimization problems over the space of measures X ⇤ .

A proof of this standard result can be found in [START_REF] Zalinescu | Convex analysis in general vector spaces[END_REF]Theorem 2.3.3]. This duality result has been the cornerstone of many works seeking to model riskaversion (see in particular [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF]): the correspondence between ⇢ and ⇢ ⇤ enables to characterize robustness via desirable properties on ⇢ ⇤ . In this thesis, we will mostly focus on the cases where ⇢ ⇤ is the indicator of a convex set of measures.

Supporting distributionally robust optimization

When the Fenchel conjugate ⇢ ⇤ of ⇢ is the indicator of a closed convex set Support functions on X A ⇢ Y, ⇢ is a support function and satisfies two additional properties:

(Sub-additivity) ⇢(-+ -0 )⇢(-)+⇢(-0 ), for all -, -0 2 X (H1)

(Positive homogeneity) ⇢(⌫-) = ⌫ ⇢(-), for all -2 X , ⌫ 0. ( H2
)
Additional desirable properties may be set on ⇢ to model risk aversion. Among such, the monotonicity property defined as:

(Monotonicity) ⇢(-)⇢(-0 ), for all - -0 (0.B.). (H3)

ensures that the risk decreases when -:= 5 (F, ⇢) gets decreased for almost all values of ⇢. It is also convenient whenever F 7 ! 5 (F, I) is convex for all fixed I 2 R m as the composition F 7 ! ⇢( 5 (F, ⇢) becomes also convex. From a dual perspective, this translates into A ⇢{ ⇠, ⇠ 0}. We will provide an elementary proof of this statement in Proposition 3.4 of this chapter.

One last property we also wish to mention is the translation invariance, set as:

(Translation Invariance) ⇢(-+ 2) =⇢(-)+2, for all -2 X , 2 2 R. (H4)
Intuitively, this means that the risk functional ⇢ should not be perturbed by Distributionally robust optimization deterministic outcomes. Interestingly, we will observe soon in Proposition 3.6 that support functions satisfying this property necessarily have their support included in the hyperplan {⇠ 2 Y, s.t. ⇠(⌦) = 1}. Hence, combined with (H3), this property ensures that all measures in the support A are necessarily probability measures. In such case, the support A is often called an ambiguity set and the problem of minimizing the composition F 7 ! ⇢( 5 (F, ⇢)) is referred to as a distributionally robust optimization (DRO) problem:

⇢(-) = sup ⇠2A E ⇠ [-]. (3.4)
Example 3.2. A popular approach for the modeling of a support goes through

Divergence-based ambiguity sets

the design of a divergence function [START_REF] Ben | An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent[END_REF][START_REF] Csiszár | Information-type measures of difference of probability distributions and indirect observation[END_REF]. A closed proper convex map

! : R + ! R + [ {+1} is called a divergence function if 1 2 int dom ! and min ! = !(1) = 0.
Then given some ground measure 2 Y, the !-divergence of a measure ⇡ ⌧ that is absolutely continuous with respect to , is defined as:

D ! (⇡, ) = π ⌦ ! ✓ 3⇡ 3 ◆ d .
where 3⇡ 3 denotes the Radon-Nikodym derivative of ⇡ with respect to . For a fixed threshold A > 0 designed to model the level of aversion to risk of the decision maker, the associated distributionally robust optimization problem writes: min

F2R d sup ⇡⌧ D ! (⇡, )A E ⇡ [ 5 (F, ⇢)]
Example 3.3. The support A in (3.4) can also be a ball with respect to a given Wasserstein ambiguity sets metric in the space of measures. For example, Wasserstein ambiguity sets have been receiving much attention, e.g. [START_REF] Ho-Nguyen | Adversarial classification via distributional robustness with Wasserstein ambiguity[END_REF][START_REF] Kuhn | Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning[END_REF][START_REF] Shafieezadeh-Abadeh | Regularization via mass transportation[END_REF]. For any couple of measures ⇠, ⇡ 2 Y, the Wasserstein distance between ⇠ and ⇡ is defined for ? 1 as:

W(⇠, ⇡) := inf 2⇧(⇠,⇡) ✓π Ω 2 G H ? d (G, H) ◆ 1/?
.

where ⇧(⇠, ⇡) denotes the set of product measures having marginals ⇠ and ⇡. Given a sample of values ⇢ 1 , ..., ⇢ = and the associated empirical distribution P = , for a safety radius A > 0, the data-driven Wassertein DRO problem writes min

F2R d sup ⇠2Y W(⇠,P = )A E ⇠ [ 5 (G, ⇢)].
Support functions satisfying the properties (H1) to (H4) are called coherent risk measures and were introduced in [5]. A growing body of literature has examined their properties from various angles, including structural properties [START_REF] Tyrrell | The Fundamental Risk Quadrangle in Risk Management, Optimization and Statistical Estimation[END_REF][START_REF] Shapiro | On Kusuoka representation of law invariant risk measures[END_REF], statistical properties [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF][START_REF] Mhammedi | PAC-Bayesian Bound for the Conditional Value at Risk[END_REF] and applications [START_REF] Chow | Risk-constrained reinforcement learning with percentile risk criteria[END_REF][START_REF] Laguel | A Superquantile Approach to Federated Learning with Heterogeneous Devices[END_REF][START_REF] Pablo | An approximation scheme for a class of risk-averse stochastic equilibrium problems[END_REF]. This thesis may be seen as following the same line of works, with a focus on a particular class of coherent risk measures that will be specified in the forthcoming Section 3.2.

Subdifferential formula

Given a random loss F 7 ! 5 (F, ⇢) and coherent risk measure ⇢ : X ! R,w e consider min Various methods may be used for the minimization of such functions, depending on the regularity properties of 5 , the statistical properties of ⇢, and the geometry of the ambiguity set A. When 5 is a convex normal integrand, one may solve (3.5) via subgradient-based methods [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF]. Let us first recall the subdifferentiation rules for ⇢.

We define an algebraic subgradient of a proper convex l.s.c. risk functional Subdifferential of a risk measure ⇢ : X ! R atas any linear functional ✓ satisfying:

⇢(-0 ) ⇢(-)+✓ (-0 -), 8-0 2 X . (3.6)
While such linear functionals need not be continuous, we call the subset of those that are continuous the subdifferential of ⇢ and we denote it %⇢(-). Since Y is assumed to be the topological dual of X , any element of this set is of the form h⇠,.i for some ⇠ 2 Y.

For ⇠ 2 % ⇢(-), we have by definition of the Fenchel conjugate:

⇢ ⇤ (⇠) h ⇠, -i ⇢(-). Since relation (3.6) is equivalent to h-, ⇠i ⇢(-) h-0 , ⇠i ⇢(-0 ), 8-0 2 X ,
taking the supremum on the right-hand side yields:

h-, ⇠i ⇢(-) =⇢ ⇤ (⇠)
By Fenchel-Moreau's theorem, we thus have:

sup ⇡2Y h-, ⇡i ⇢ ⇤ (⇡) =⇢(-) = h-, ⇠i ⇢ ⇤ (⇠) which means ⇠ 2 arg max ⇡2Y h-, ⇡i ⇢ ⇤ (⇡)
Conversely, if ⇠ 2 arg max ⇡2Y h-, ⇡i ⇢ ⇤ (⇡), then using again Fenchel-Moreau's theorem yields for any -0 2 X :

( ⌧(-) = h-, ⇠i ⇢ ⇤ (⇠) ⌧(-0 ) h -0 , ⇠i ⇢ ⇤ (⇠) which implies ⌧(-0 ) h-0 , ⇠i+ ⌧(-) h-, ⇠i .
which yields arg max ⇡2Y h-, ⇡i ⇢ ⇤ (⇡)⇢%⇢(-). Hence, we obtain a description of the subdifferential of ⇢ as:

%⌧ (-) = arg max ⇡2Y h-, ⇡i ⇢ ⇤ (⇡).
Finally, we may then invoke the chain formula [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF] to subdifferentiate the composition.

Proposition 3.2. Let F 7 ! 5 (F, ⇢) be a finite-valued convex normal integrand that is

The subdifferential formula continuous at F. Then F 7 ! (F) =⇢( 5 (F, ⇢)) is subdifferentiable at F with

% ( F) = conv ( sup ⇠2% ⇢( 5 ( F,⇢)) π Ω % F 5 ( F, ⇢) d ⇠ ) . (3.7)
In Section 4.2.1, we will focus on the special case where ⇢ is the superquantile risk measure. We will extend (3.7), to the case where is not convex together with an explicit reformulation.

3.2

We present now a special class of risk measures that will be central in this thesis. We first precise the concept of coherency for risk measures on finite support. We consider then the class of risk measures of interest by introducing the concepts of law-invariance and comonotonicity. We provide then a brief overview of the superquantile risk measures. We finally explain how the superquantile enables to recover any risk measures of interest via Kusuoka's representation.

In this section, we provide proofs of all the results, lemmas and propositions, though these results are known and actually hold in general setups (see e.g. [START_REF] Noyan | Kusuoka representations of coherent risk measures in general probability spaces[END_REF][START_REF] Shapiro | On Kusuoka representation of law invariant risk measures[END_REF]). Our proofs rely on basic results from linear algebra and convex analysis that we highlight along the developments.

Coherency in Risk-averse Optimization. To simplify the presentation, assume the universe to be finite Ω = {⇢ 1 , ..., ⇢ = }. The sigma-algebra is fixed as F = 2 Ω , and the probability measure is set to be the empirical distribution P = (⇢ 8 ) = 1/= for all 8 2 ~1, =. Random variables -2 X and measures ⇠ 2 Y can both be identified with vectors G, @ in R n :

G 8 = -(⇢ 8 ), @ 8 = ⇠({⇢ 8 }), 8 1  8  =,
and the pairing reduces to the usual dot product:

E ⇠ [-] = @ > G = = ' 8=1 -(⇢ 8 )⇠({⇢ 8 }), 8-2 X , 8⇠ 2 Y .
In the previous section, we saw with Fenchel-Moreau's theorem 3.1 that any closed proper convex risk measure ⇢ may be written as the solution of a robust problem (3.3). When the Fenchel conjugate ⇢ ⇤ of ⇢ is the indicator of a convex compact subset C ⇢ R n , ⇢ turns out to be a support function:

⇢(G) = sup @2C @ > G.
(3.8)

We actually have the following correspondence.

(@ = ) = 0 2(C\{0}) N such that |@ = | ! +1 and G = = @ =
k@ = k . Since R n has finite dimension, its unit ball is compact we may extract a converging sequence (G #(=) ) = 0 ! Ḡ of (G = ) = 0 . Thus, for all = 2 N, we have:

⇢(G #(=) ) @ > #(=) G #(=) = k@ #(=) k!1which brings the contradiction.

⇤

In this section, we investigate the relationship between additional properties on the support function ⇢ and the geometry of the corresponding support C. Proposition 3.4. Let ⇢ be a function defined as in (3.8). Then, the following assertions )⇢(0),inf @2C @ 8 0 which yields C ⇢ R = + . (88) =)( 8): Let G, H satisfying assumption [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF]. Then, since C ⇢ R = + , we have: (ii) The support belongs to the hyperplane {@ 2 R n ,

@ > (H G) 0, 8@ 2 C =) @ > G  @ > H, 8@ 2 C =) ⇢(G) = max @2C @ > G  max @2C @ > H =⇢(H).
Õ = 8=1 @ 8 = 1}.
Proof. The implication (8) =)( 88) goes as follows. Note that

⇢(4) = sup @2C Õ = 8=1 @ 8 =⇢ (0)+1 = 1 and ⇢( 4) = inf @2C Õ = 8=1 @ 8 =⇢ (0) 1 = 1. Hence C ⇢{@ 2 R n , Õ = 8=1 @ 8 = 1}. The reverse implication is immediate.

⇤

Hence, if we assume our support function ⇢ to satisfy both the growth and the translation invariance properties, its support belongs then to the unit simplex ∆ := {@ 2 R n , Õ = 8=1 @ 8 = 1, 0  @ 8 88 2{ 1, ..., =}}, which spans the space of probability measures @ on the discrete space Ω = {⇢ 1 , ..., ⇢ = }. We recover in this discrete setting the concept of coherent risk measure introduced in Section 3.2.

Law-invariant risk measures.

We propose now to focus, in this discrete setting, Law-invariance on risk measures that only depends on the cumulative distribution function of the input random variables G 2 R n . Such risk measures are called law invariant. As shown in the next lemma, law invariance is directly linked to the symmetry properties of the support. Throughout, we will denote S n the permutation set of ~1, =.

Proposition 3.6. Let ⇢ be defined as in (3.8). The two following assertions are then Law invariance and symmetries of the support equivalent:

(i) The function ⇢ is invariant with respect to symmetries, i.e.:

⇢(G) =⇢ (G)8 2 S n , 8G 2 R n (ii)
The support C is invariant with respect to symmetries: C = (C) for any 2 S n .

Proof. For any 2 S n , let us denote by ) , the associated permutation matrix defined by: ) 8,9 = 1 if 9 = (8) and 0 otherwise. We note then for any G 2 R n , 2 S n that:

⇢( (G)) = max @2C h@, ) Gi = max @2C h) > @, Gi = max @ 0 2) > (C) h@ 0 , Gi = max @ 0 2 1 (C) h@ 0 , Gi , (3.9)
since any permutation matrix is orthogonal. Hence ⇢ is the support function of the set 1 (C). This gives (88) =) [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF]. Conversely, we know from [START_REF] Hiriart-Urruty | Fundamentals of convex analysis[END_REF] that two closed convex sets are equal if and only if their support functions are equal, which yields with (3.9) the result.

⇤

We can actually leverage the symmetry properties of the support of lawinvariant risk measures to recover information the distribution @ 2 C which achieves the maximum of the support function for a given input G 2 R n .T o do so, we define for any distribution @ 2 C the orbit of @, denoted O(@) as: O(@) = { (@), 2 S n }. The relation @ 0 2 O(@) defines then an equivalence relation on C. For any @ 2 C, we will denote @ = O(@) its associated equivalence class. For any D 2 R n , we call sorting permutation any permutation D 2 S n , such that:

D D (1) •••D D (=)
Lemma 3.7. Let G 2 R n and @ 2 C be fixed. Let G and @ be two associated sorting

Law invariance and the rearrangement inequality

permutations:

G G (1) •••G G (=) and @ @ (1) •••@ @ (=)
Then, for any @ 0 2 O(@), we have:

@ 0> G  1 G ( @ (@)) > G
Proof. By the rearrangement inequality, we have, for any @ 0 2 O(@) :

@ 0> G  = ' 8=1 @ @ (8)G G (8)h ) @ @, ) G Gih ) 1 G ) @ @, Gi
which yields the result.

⇤

Comonotonicity and generation of the support. We note that for a supporting Comonotonicity set C that is generated by a single distribution, i.e. C = conv(O(@)) for some @ 2 ∆, the extreme points of C constitute the orbit O(@). Subsequently, this last lemma ensures that evaluating the support function at G boils down to a sorting of the elements of G. Let us now characterize risk measures supported on such sets. For any G, H 2 R n , we say that G and H are comonotone if:

G 8  G 9 () H 8  H 9 88, 9 2 ~1, =
Comonotonicity yields a second equivalence relation. We note from lemma 3.7, that for any law-invariant support function and for any G 2 R n , arg max @2C @ > G is comonotone to G.

A risk measure ⇢ is said to be comonotone if for all G, H 2 R n that are comonotone, ⇢ satisfies ⇢(G + H) =⇢ (G)+⇢(H). As next Proposition shows, comonotonicity can also be tied to the geometry of the support C. (ii) The support C is generated by a single distribution, i.e. there exists @ 2 C such that C = conv(O(@)).

This well-known results was first established in atomless spaces within the seminal paper [START_REF] Kusuoka | On law invariant coherent risk measures[END_REF]. Its extension to finite probability spaces was proposed in [START_REF] Bertsimas | Constructing uncertainty sets for robust linear optimization[END_REF] with a proof relying on submodularity considerations. Here we provide a different proof based on elementary results from convex analysis.

Proof. (8) =)( 88): Let @ 2 C be an exposed point of C. By law-invariance of ⇢, we have O(@)⇢C and thus convexity of ⇠ ensures conv(O(@)) = C. We want to show that conv(O(@)) = C. Let us assume by contradiction that there exists an extreme point @ of C such that @ 8 conv(O(@)). By Straszewicz's theorem [START_REF] Straszewicz | Über exponierte punkte abgeschlossener punktmengen[END_REF] and closedness of conv(O(@)), we may actually assume @ to be an exposed point of C. It is then clear that O( @)\O(@) = ;. Let then @ 1 , @ 2 2 O(@)⇥O( @) such that @ 1 and @ 2 are comonotone. Let G 1 and G 2 two arbitrary points respectively in N C (@ 1 ) and N C (@ 2 ). By the proposition 3.1.4 of the chapter C of [START_REF] Hiriart-Urruty | Fundamentals of convex analysis[END_REF],

⇢(G 1 ) = @ > 1 G 1 and ⇢(G 2 ) = @ > 2 G 2 .
Hence by lemma 3.7 and transitivity of the comonotone equivalence relation G 1 is comonotone to G 2 . However, for any @ 2 C, since @ 1 and @ 2 are exposed, if @ < @ 1 , @ > G 1 < ⇢(G 1 ) and if @ < @ 2 , @ > G 2 < ⇢(G 2 ). Since @ 1 < @ 2 , we have:

@ > (G 1 + G 2 ) < ⇢(G 1 )+⇢(G 2 )8 @ 2 C) By compactness of C, we get ⇢((G 1 + G 2 ) < ⇢(G 1 )+⇢(G 2 ) which yields the contradiction. (88) =)( 8): By definition of support functions, G, H 2 R n , ⇢(G + H) ⇢(G)+⇢(H). Let G, H 2 R n be comonotone.
Then the permutation G 2 S n that sorts the coordinates of G is also a sorting permutation for H, i.e. we have:

G G (1) •••G G (=) and H G (1) •••H G (=)
Let @ 2 C such that C = conv(O(@)). Then by lemma 3.7, we have for any @ 0 2 O(@), @ 0> G  1 G @ (@) > G and @ 0> H  1 G @ (@) > H. Now since arg max @ 0 2C @ 0> G and arg max @ 0 2C @ 0> H both lie in the set of extreme points of C which is by assumption the orbit of @, we have:

⇢(G) = 1 G @ (@) > G and ⇢(H) = 1 G @ (@) > H.
Hence, we have:

⇢(G)+⇢(H) = 1 G @ (@) > (G + H)sup @ 0 2C @ 0> (G + H) =⇢(G + H)
which finishes the proof.

⇤

Combining the two previous lemmas yields the following corollary. Corollary 3.9. Let ⌧ be defined as in 3.8, law-invariant and comonotone. Let @ 2 C Risk profile such that C = conv(O(@)). Then, for any G 2 R n , we have:

⌧(G) = h @ (@), G (G)i = h 1 G ( @ (@)), Gi
In other words, this result shows that when the support function ⌧ satisfies the law-invariance and comonotonicity properties (and assuming that we know an extreme point @ of the support C), evaluating ⌧ at a given G 2 R n boils down to a sorting of the coordinates of G. This is much less demanding than solving the linear program (3.8) in general. Moreover, we note that designing a law-invariant and comonotone support function amounts to designing a risk profile, i.e. an increasing sequence @ 8 that sums to one. The support is then recovered through the formula C = conv(O(@ 8 )).

3.3

In this section, we present in detail the superquantile, which is a special example of law-invariant comonotone risk measure. This risk measure was introduced in the introductory Section 1.1 of this thesis. We insist here on its convex and geometric properties, based on the above coherent framework.

The superquantile risk measure

In the discrete setting described in Section 3.2, the general formula (1.4) defining the superquantile reduces to a sum that can be further split as

( ? (G) = 1 =(1 ?) ' 82 > G 8 + ⇣ 1 ? & ? (G) with > = {8 : G 8 > & ? (G)}. (3.10)
This expression involves the distance from ? to the next discontinuity point of the quantile function:

⇣ = G (& ? (G)) ? = 1 = (= | > |)
?,that we illustrate in Figure 3.2. Hence, (3.10) gives an efficient way to compute superquantiles from the following three step procedure: (a) compute the ?-quantile with the specialized algorithm (called quickfind [START_REF] Charles Ar Hoare | Algorithm 65: find[END_REF]) of complexity O(=); (b) select all values greater or equal than the quantile; (c) average values along (3.10). We note also that for probability values ? in 8 = ,1  8  = , this expression simplifies even more. Lemma 3.10. Let G 2 R n be a fixed vector and G a sorting permutation for G. For Quantiles, superquantiles, and coordinates of a vector any 8 2 ~1, ..., = 1, we have: [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF] , it is also clear that: the first result. It is in addition clear that for any 8 2 ~1, = 1, and for any

& 8 = (G) = G G (8) ( 8 = (G) = 1 = 8 = ' :=8+1 G G (:) Proof. Let 8 2{ 1, ..., = 1} be fixed. Then, 1 = Õ = :=1 1 G : G G (8) 8 = so G G (8) & 8 = (G). But for any C < G G
1 = Õ = :=1 1 G : C < 8 = which yields
? 2( 8 = , 8+1 = ], & ? (G) = & 8+1 = (G) = G G (8+1)
. Hence,

( 8 = (G) = 1 1 8 = π 1 ? 0 = 8 = & ? 0 (G)d? 0 = = = 8 = 1 ' :=8 π :+1 = ? 0 = : = & ? 0 (G)d? = = = 8 = 1 ' :=8 1 = & :+1 = (G)d? 0 = 1 = 8 = ' :=8+1 G G (8+1)
which ends the proof.

( ? (G) = max @2 ? @ > G with ? = ( @ 2 R = + : = ' 8=1 @ 8 = 1, @ 8  1 =(1 ?)
)

. (3.11) This problem corresponds to a classical optimization problem, called the fractional knapsack problem, which is solved, after sorting the G 8 's, by a simple greedy strategy of the associated @ 8 's [START_REF] Dantzig | Discrete-variable extremum problems[END_REF], yielding back the discrete formulation (3.10).

• Another expression, which initially appeared in [START_REF] Tyrrell | Conditional value-at-risk for general loss distributions[END_REF], is Variational representation

( ? (G) = inf ◆2R ( ◆ + 1 =(1 ?) = ' 8=1 max(G 8 ◆,0) ) . (3.12)
This formulation can be derived through Lagrangian duality from (3.11) (see. e.g [START_REF] Ben | An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent[END_REF]): it suffices to dualize the simplex constraint Õ = 8=1 @ 8 = 1. It will be central in the developments of Chapter 5 of this thesis.

As a support function given in (3.11), we see that the superquantile is a Extreme points of the support coherent risk measure. Moreover, we note that the support ? is the convex hull of the orbit O(@ ? ) with

@ ? := 8 > > > > > > < > > > > > > : 0, ..., 0, ⇣, 1 =(1 ?) , ..., 1 =(1 ?) | {z } =⇥(1 ? ⇣) times 9 > > > > > > = > > > > > > ;
.

We therefore deduce from Propositions 3.6 and 3.8 that the superquantile is law-invariant and comonotone. In practice, superquantiles have been shown experimentally to produce models more robust to distributional shifts in various contexts; we refer to [START_REF] Curi | Adaptive sampling for stochastic risk-averse learning[END_REF][START_REF] Kawaguchi | Ordered sgd: A new stochastic optimization framework for empirical risk minimization[END_REF][START_REF] Laguel | First-order optimization for superquantile-based supervised learning[END_REF][START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF]]. We will provide numerical illustrations in Section 4.4.

The Kusuoka representation

As we have seen with Corollary 3.9, any law-invariant comonotone risk measures can be written as a convex combination of quantiles of the input vector G. However, quantiles are known to be non-convex and nonsmooth functions. In this section, we present a standard representation of law-invariant comonotone risk measures known as the Kusuoka representation [START_REF] Kusuoka | On law invariant coherent risk measures[END_REF][START_REF] Noyan | Kusuoka representations of coherent risk measures in general probability spaces[END_REF]. We will leverage this representation in Section 4.2 to produce efficient first-order oracles for the minimization of such risk measures.

Proposition 3.11. Let ⌧ be defined as in (3.8), law-invariant and comonotone. Let

Kusuoka Representation

@ 2 C such that C = conv(O(@)) and := @ (@). Then for any G 2 R n , we have:

⌧(G) = = ' :=1 : ( : 1 = (G) (3.13)
where ( : ) 1:= satisfies :

1 = = 1 , 8 = (= + 1 8)( 8 8 1
) for 8 2{2, ..., =}.

Proof. Let G 2 R n be fixed. For any 8 2 ~1, ..., = 1, let -8

:= Õ = :=8 G G (:) = (= 8 + 1)( 8 1 = (G)
. By corollary 3.9, we have:

⌧(G) = = ' 8=1 8 G G (8) = = ' 8=1 8 = ' :=8 G G (:) = ' : 0 =8+1 G G (: 0 ) ! = = ' 8=1 8 ( -8 -8+1 ) with convention -=+1 = 0 = = ' 8=1 8 -8 = ' 8=2 8 1 -8 = 1 -1 + = ' 8=2 ( 8 8 1 ) -8 = = 1 ( 0 (G)+ = ' 8=2 (= + 1 8)( 8 8 1 )( 8 1 = (G)
which yields the result.

⇤

One may observe from the above proof that the Kusuoka representation stems from an elementary "integration by part" technique. In particular, we did not assume ⌧ to satisfy the growth condition from Proposition 3.4. Hence the Kusuoka representation, usually given for coherent risk measures, holds de facto for any linear combination of quantiles functions. In particular, the developments of Section 4.2 will remain valid for other classes of functions alike such as cardinality-based submodular functions.

-

Minimization of superquantile-based objective functions comes with a number of technical challenges on the structure of the problem tackled, the size of the dataset or the nonsmoothness of the objective. Standard works on minimizing superquantiles considered linear programming or convex programming techniques, including interior point algorithms; see the review of [START_REF] Terry Rockafellar | Superquantile regression with applications to buffered reliability, uncertainty quantification, and conditional value-at-risk[END_REF]. Surprisingly, the use of first-order algorithm for superquantile-based optimization is quite recent and seems to be driven by applications in machine learning.

In this section, we provide an overview of the range of first-order methods to minimize superquantile-based objective functions. Precisely, we consider problems of the form: min

F2R d ( ? [ 5 (F, ⇢)] (3.14)
where ⇢ :

⌦ ! R is uniform over a a batch of training samples D = {⇢ 1 , ..., ⇢ = }.
Our discussion focuses on practical considerations; we give pointers to references presenting more details and theoretical analysis.

Batch algorithms. The first approach for minimizing superquantile-based objective functions is to use standard subgradient-based methods (subgradient and dual averaging) or gradient-based methods (gradient, accelerated gradient, Quasi-Newton). More precisely, we have two cases:

• If F 7 ! 5 (F, I)
is convex for all I, then composition 3.14 is convex and we

Convex case

may compute a subgradient according to (3.7) (we will make this more concrete in the forthcoming Proposition 4.1) with the same complexity as the one for computing a quantile. We can use standard convex nonsmooth optimization methods, such as subgradient methods and dual averaging. These algorithms satisfy ergodic convergence guarantees in objective values [START_REF] Bertsekas | Convex Optimization Algorithms[END_REF].

• If F 7 ! 5 (F, I) is smooth for all I, then we can smooth the superquantile

Smooth case

(see forthcoming Section 4.2.2) to get a gradient oracle that approximates the composition 3.14. We can use standard methods for smooth optimization: gradient method, accelerated gradient method, and quasi-Newton (L-BFGS). If furthermore we have convexity, these algorithms satisfy convergence guarantees in objective values [START_REF] Bertsekas | Convex Optimization Algorithms[END_REF][START_REF] Bertsekas | Nonlinear Programming[END_REF].

For small to medium-size datasets, such batch methods are shown to be simple and efficient; see [START_REF] Laguel | First-order optimization for superquantile-based supervised learning[END_REF]Sec. 4] and forthcoming developments of Chapter 4. For large-scale problems though, the oracles become too costly as they require sorting loss values on the whole data set. We turn to the other formulations to introduce stochastic and mini-batch algorithms, that usually are the methods of choice for the case of standard learning using empirical risk minimization.

Mini-batch algorithms. Mini-batch algorithms for the minimization of the superquantile have received much attention in recent years. Given the diverse formulations of the superquantile, several approaches have been considered.

From the perspective of the formulation (3.12) of the objective, the

Smoothing the variational representation (3.12) superquantile-based learning problem writes min

F2R d min ◆2R ( 1 =(1 ?) = ' 8=1 max{ 5 (F, ⇢ 8 ) ◆,0}+◆
) .

(3.15)

When the loss is assumed to be smooth, one may again smooth the inner max{•,0} term to get a smooth approximation of this joint objective. One can then perform a joint minimization with respect to the model F and the dual variable ◆. In other words, superquantile learning reduces to a standard empirical risk minimization with a modified loss function truncated by the max-term. In practice batch methods may not be interesting here, since they would not leverage the fact that the minimization over ◆ can be performed explicitly. Thus [START_REF] Laguel | A Superquantile Approach to Federated Learning with Heterogeneous Devices[END_REF] proposes, in a context of federated learning, to rather perform independent minimization over G and ◆ alternatively. The min-min approach paves the way to stochastic and mini-batch algorithms. Several works , including [START_REF] Soma | Statistical learning with conditional value at risk[END_REF] and [START_REF] Williamson | Fairness risk measures[END_REF] (as well as [START_REF] Fan | Learning with average top-k loss[END_REF] without mentioning Stochastic approaches to (3.12) superquantile), use successfully standard stochastic optimization algorithms on this modified objective. Observe though that, if a mini-batch of data is sampled uniformly at random from the data, only a fraction (1 ?) carry (sub)gradient information. Furthermore, the (sub)gradients of these examples are scaled by 1 1 ? , leading to exploding directions. Thus mini-batch estimates of (sub)gradients of superquantile-based objectives may suffer from high variance. A solution proposed by [START_REF] Curi | Adaptive sampling for stochastic risk-averse learning[END_REF] is to perform an adaptive sampling rather than a uniform one. This algorithm gradually adjusts its sampling distribution to increasingly sample tail events, until it eventually minimizes the superquantile. This approach has a nice two-player interpretation related to the third formulation, recalled below.

The DRO expression (3.11) of 5 leads to the following formulation Mini-batch approaches for the DRO formulation (3.11) min

F2R d max @2 = ( = ' 8=1 @ 8 5 (F, ⇢ 8 ) : 0  @ 8  1 =(1 ?) ) . (3.16)
This min-max formulation offers several ways to solve the superquantilebased learning. A first approach would consist in considering it as a generic saddle point problem and using standard (extra-)gradient algorithms or recent extensions exploiting some aspects of the problem (see e.g. [START_REF] Luo | Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems[END_REF] for a variance-reduced min-max with strongly concave max). In our specific case, computing the max can be done systematically by a greedy algorithm with quasi-linear time complexity (see Section 4.2). This key feature is exploited by the stochastic algorithm of [START_REF] John | Variance-based Regularization with Convex Objectives[END_REF], and also by the one of [START_REF] Kawaguchi | Ordered sgd: A new stochastic optimization framework for empirical risk minimization[END_REF] without relating it to superquantile. This algorithm uses a biased sampling approximation to 5 or 5 ⇠ which has nice guarantees. We briefly describe below this approach. We sample a mini-batch S of size B, uniformly in D and we consider the Mini-batch stochastic estimator of the superquantile restriction e 5 (F) = [( ? ] (0,1)⇠S 5 (F, ⇢)

= max @2 B ( ' 82S @ 8 5 (F, ⇢ 8 ) : 0  @ 8  1 B(1 ?) ) .
Alternatively, one may smooth this stochastic estimator. We will discuss possible smoothing procedures in the upcoming Section 4.2.2. Specialized here for a given smoothing parameter ⇡>0 and a strongly convex function ⇡, this gives

e 5 ⇡ (F) = max @2 B ( ' 82S @ 8 5 (F, ⇢ 8 ) ⇡⇡(@) : 0  @ 8  1 B(1 ?) ) .
(3.17)

Using the (sub)gradient oracles that will be presented in Section 4.2 on e 5 (⇡) , we can run stochastic gradient methods. These methods require a number of gradient evaluations independent of training set size and number of parameters, making them suitable for large-scale applications. However, one should note that e 5 happens to be a biased estimator of 5 , in view of the two following results [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF]. We will use them in Chapter 6.

E S⇠* B [ e 5 (F)] 5 (F)  ⌫ p (1 ?)B
Under similar assumptions, one may also bound the bias of the smoothed stochastic estimator (3.17) as well as the variance of its gradient.

(F, ⇢ 8 ) 5 (F 0 , ⇢ 8 )|  ⌧, 8F, F 0 2 R d . Then, for any F 2 R d , we have E S⇠* B [ e 5 ⇡ (F)] 5 (F)  ⌫ p (1 ?)B + 2⇡ log B , E (⇠* < r e 5 ⇡ (F) rE S⇠* B e 5 ⇡ (F) 2  8⌧ 2 (1 ?)B .
A comparison between batch and stochastic methods will be presented in the Section 4.4 of this thesis.

-

We end this chapter with a related topic that will be explored in Chapter 5. Chance constraints appear as a versatile way to model the exposure to uncertainty in optimization. Introduced in [START_REF] Charnes | Chance-constrained programming[END_REF], they have been used in many applications, such as in energy [START_REF] Prékopa | Flood control reservoir system design using stochastic programming[END_REF][START_REF] Van Ackooij | Joint chance constrained programming for hydro reservoir management[END_REF] and telecommunications [START_REF] Medova | Chance-constrained stochastic programming forintegrated services network management[END_REF]. We refer to the seminal paper [START_REF] Prékopa | Stochastic Programming[END_REF], the book chapter [START_REF] Dentcheva | Optimisation models with probabilistic constraints[END_REF] for an introduction to the theory, and to the recent article [START_REF] Van Ackooij | A discussion of probability functions and constraints from a variational perspective[END_REF] for a discussion covering recent developments.

Chance constraints result from taking the probability measure of a given set

Chance constraints

of random inequalities depending on the decision vector. Formally speaking, given a map 6 : ⇢ ⇥ R < ! R : , where ⇢ is a (reflexive) Banach space and a random vector ⇢ 2 R < defined on an appropriate probability space, we first define the probabilistic constraint function ! : -![0, 1] as:

!(F) := P[6(F, ⇢)0] . (3.18)
As its name suggests, a chance-constrained problem is an optimization problem

Chance-constrained problems of the form:

8 > > < > > : min F2( 5 (F) s.t. !(F) ? (3.19)
where 5 : R d ! R is a given objective function, ( ⇢ ⇢ is an arbitrary set of deterministic constraints and ? 2( 0, 1) a user-defined safety level. The interpretation of (3.19) is simple: one requires the decision F to minimize the cost function 5 while satisfying both the deterministic constraint F 2 (, and, the random inequality system 6(F, ⇢)0 with a probability at least greater than ?.

Letting "(?) be the set of admissible points for the probabilistic constraint,

"(?) = F, !(F) ? ,
this problem rewrites min F2(\"(?)

(F).

From now on, we will assume 5 , 6, and ( to be convex in order to bring to light the inherent difficulties of chance constraints. Indeed, such problems are still designated as especially difficult for two reasons in particular, that we summarize below.

Nonsmoothness. When considering a parametric distribution in place of the

Nonsmoothness of chance constraints

random variable ⇢, one may deal with the above chance constraint through the (generalized) differentiation of the probabilistic function !. Indeed, the development of readily implementable oracles for probability functions has been studied in a growing body of literature [START_REF] Royset | Extensions of stochastic optimization results to problems with system failure probability functions[END_REF][START_REF] Uryas'ev | Derivatives of probability functions and some applications[END_REF][START_REF] Van Ackooij | Sub-) Gradient formulae for probability functions of random inequality systems under Gaussian distribution[END_REF]. Nonetheless, when ⇢ follows a discrete distribution, which typically occurs with sample-based approximations approaches, working through the subdifferentiation of ! becomes impracticable and alternative methods may be considered. Popular numerical methods for dealing with such constraints may be boolean approaches, e.g., [START_REF] Kogan | Threshold boolean form for joint probabilistic constraints with random technology matrix[END_REF][START_REF] Kogan | Erratum to: Threshold boolean form for joint probabilistic constraints with random technology matrix[END_REF], ?-efficient point based concepts, e.g., [START_REF] Dentcheva | Regularization methods for optimization problems with probabilistic constraints[END_REF][START_REF] Dentcheva | Concavity and efficient points for discrete distributions in stochastic programming[END_REF][START_REF] Van Ackooij | Probabilistic optimization via approximate p-efficient points and bundle methods[END_REF], robust optimization [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], penalty approach [START_REF] Ermoliev | Stochastic optimization of insurance portfolios for managing exposure to catastrophic risk[END_REF], scenario approximation [START_REF] Calafiore | The scenario approach to robust control design[END_REF][START_REF] Ramponi | Consistency of the scenario approach[END_REF], convex approximation [START_REF] Nemirovski | Convex approximations of chance constrained programs[END_REF], or yet other approximations [START_REF] Geletu | A tractable approximation of non-convex chance constrained optimization with non-gaussian uncertainties[END_REF][START_REF] Hong | Sequential convex approximations to joint chance constrained programed: A monte carlo approach[END_REF].

Non-convexity. The possible non-convexity induced by the chance constraint

Non-convexity of chance constraints can considerably complicate the handling of the problem. Understanding when "(?) is a convex set is important for the point of view of optimization, to guarantee that local solutions are also globally optimal and to use numerical solution methods that exploit this convexity. A first result of the convexity of "(?) follows from Prékopa's celebrated log-concavity theorem (see [START_REF] Farshbaf-Shaker | Properties of chance constraints in infinite dimensions with an application to pde constrained optimization[END_REF]Proposition 4] for its infinite dimensional version and [START_REF] Diniz | On probabilistic constraints with multivariate truncated Gaussian and lognormal distributions[END_REF] for generalizations): Even in the simple Gaussian case, chance constraints are not garanteed to be convex for all values of ?.

the convexity of "(?) is guaranteed for all ? 2[0, 1], when 6 is jointly quasiconcave in both arguments and ⇢ an appropriate random vector. However, jointquasi-concavity of 6 is rather exceptional and fails in many basic situations.

Example 3.4. Take 6(G, ⇢) = G > ⇢ and ⇢ to be a multi-variate Gaussian with

Kataoka's example See e.g.
mean ⇠ 2 R n and covariance matrix ⌃ 2 R =⇥= . Then "(?) is known to be convex only whenever ? 1 2 . Indeed, denoting I an arbitrary 1-dimensional standard Gaussian variable and ) its cumulative distribution function, we observe that for any G 2 R n , one has

P[G > ⇢] = P h G > ⇠ + p G > ⌃GI  0 i = ) ✓ G > ⇠ p G > ⌃G ◆ .
Hence,

P[G > ⇢] ? , ) ✓ G > ⇠ p G > ⌃G ◆ ? , G > ⇠ + p G > ⌃G) 1 (?)0
Thus, in this example, the comvexity of the set "(?) boils down to quasiconvexity of the function G 7 ! G > ⇠ + p G > ⌃G) 1 (?) which clearly occurs only when ) 1 (?) 0, that is when ? is greater than 0.5.

⇤

In the above example, we thus observe that if the convexity of "(?) does not hold for all ?, there still exists a (computable) threshold ? ⇤ 2[ 0, 1] such that the set "(?) is convex for all ? ? ⇤ . This property is called eventual convexity as observed by [START_REF] Prékopa | On the concavity of multivariate probability distributions functions[END_REF] and coined by [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF] (which studies the case where 6 is separable and ⇢ has independent components). Eventual convexity results are further generalized in [START_REF] Henrion | Convexity of chance constraints with dependent random variables: the use of copulae[END_REF] by allowing for the components of ⇢ to be coupled through a copulae dependency structure. These results are refined, by allowing for more copulae and with sharper bounds for ? ⇤ in [START_REF] Van Ackooij | Eventual convexity of chance constrained feasible sets[END_REF], and extended to all Archimedian copulae in [START_REF] Van Ackooij | Convexity and optimization with copulae structured probabilistic constraints[END_REF], where also an appropriate solution algorithm is provided. When the mapping 6 is non-separable, eventual convexity results are provided in [START_REF] Van Ackooij | Eventual convexity of probability constraints with elliptical distributions[END_REF] for the special case where ⇢ is elliptically symmetrically distributed and generalized in [START_REF] Laguel | On the convexity of level-sets of probability functions[END_REF].

In Chapter 5, we will focus on the practical solving of such chance-constrained problems in the case where ⇢ is observable through data sampling.

MINIMIZING SUPERQUANTILE-BASED RISK MEASURES

This chapter is devoted to the practical minimization of a given class of convex risk measures and their applications in machine learning. Namely, we consider law-invariant comonotone convex risk measures and we show how they can be efficiently minimized via first-order methods. An important focus is given to the superquantile risk measures for its central role within the class. The developments laid down below build upon the following works: • Y. Laguel, J. Malick, and Z. Harchaoui. Superquantile-based learning: a direct approach using gradient-based optimization. Under review.

• Y.

4.1

In view of the recalls of chapter 3 and the Fenchel-Moreau Theorem 3.1, convexity is a natural assumption for the design of risk measures to enforce robustness in uncertain environments. When the risk measure considered is coherent, (i.e. sub-additive, positively homogeneous, monotone and translation-invariant), it may be represented as the support function of a set in the space of measures, called the ambiguity set. The study of the correspondence between the functional properties of a given coherent risk measure and the associated ambiguity set has drawn much attention, see [START_REF] Rahimian | Distributionally robust optimization: A review[END_REF] for an recent overview.

In this chapter, we focus on the practical solving of problems of the form:

General problem min F2R d ⇢( 5 (F, ⇢)) (4.1)
where ⇢ denotes a law-invariant coherent comonotone risk measures -see Section 3.2 for a brief overview. A special attention is given to the superquantile risk measure which was first introduced in Section 1.1 of this thesis and further developed in Section 3.3. Our developments rely on a careful analysis of the dual properties of superquantile functions to produce first-order oracles with optimal computational complexity. We also present our open-source python software SPQR for the minimization of such risk measures and show how it enforces (distributional) robustness in a sequence of numerical experiments. In Section 4.

()-

We propose to solve problems of the form (4.1) by first-order methods. We first focus on superquantile-based learning objectives for which we provide easy-to-implement expressions of subgradients in Section 4.2.1, and of gradients of smoothed approximations of them in Section 4.2.2. For both oracles, we provide efficient subroutines to implement them in linear time. We make connections between several smoothing procedures of the superquantile in Section 4.2.3. We finally generalize in section 4.2.4 these procedures to lawinvariant comonotone risk measures with a special care on maintaining the optimal linear time complexity.

Subdifferentiation via the chain rule

In this section, we provide explicit and implementable expressions of the

Superquantile-based losses

subdifferential of a general superquantile-based loss:

5 (F) = ( ? (!(F)). (4.2)
where ( ? denotes the p-superquantile defined in (1.4) and ! : F 7 ! ! (F, ⇢ 8 ) 18# denotes a differentiable loss. In this chapter, we do not assume the components of !, i.e. the terms ! 8 (F) := !(F, ⇢ 8 ) to be convex.

Expressions for the (convex) subdifferential of superquantiles are well-known in general settings; see e.g., [START_REF] Ruszczyński | Optimization of convex risk functions[END_REF] for a thorough study and Proposition 3.2 for a general result. Here we study non-convex subdifferentials and derive concrete expressions in the data-driven context; we give direct proofs as applications of basic definitions and properties of nonsmooth analysis.

We start by recalling the standard notions of subgradients for nonsmooth functions (in finite dimension), following the terminology of [START_REF] Tyrrell | Variational analysis[END_REF]. For a function # :

R d ! R [ {+1}, the regular (or Fréchet) subdifferential of # at F Fréchet subdifferential (such that #( F) < +1) is defined by % ' #( F) = B 2 R 3 : #(F) #( F)+B > (F F)+o(kF F k) .
The regular subdifferential thus corresponds to the set of gradients of smooth functions that are below # and coincide with it at F. The limiting subdifferential Limiting subdifferential is the set of all limits produced by regular subgradients

% ! #( F) = lim sup F! F,#(F)!#( F) % ' #(F).
These notions generalize (sub)gradients of both smooth and convex functions: for these functions indeed, the two subdifferentials coincide, and they reduce to {r#( F)} when # is smooth and to the standard subdifferential from convex analysis when # is convex. For the function (4.2), which is the composition of a convex function and a continuously differentiable function, we get from basic chain rules that the two subdifferentials coincide; we simply denote it by % 5 (F). Moreover the dual representation (3.11) expressing ( ? as a support function allows us to obtain readily an expression of the subdifferential of %( ? and, as a result, of the one of 5 . We formalize all this in the following proposition. differentiable. We have

% 5 ( F) = ⇣ % ! 5 ( F) = % ' 5 ( F) = ⌘ r!( F) ⇤ % ( ? (!( F)) (4.3)
where r!( F) ⇤ is the adjoint of the Jacobian of ! at F and % ( ? (!( F)) the (convex) subdifferential of ( ? taken at !( F). Moreover, for

F 2 R 3 , compute !(F)2R n and & ? (!(F)) 2 R. Consider > the set of indices such that ! 8 (F) > & ? (!(F)) and = the set of indices such that ! 8 (F) = & ? (!(F))
. Then the subdifferential of 5 at F can be written with the gradients r! 8 (F) for 8 2 > [ = , as follows

% 5 (F) = 1 =(1 ?) ' 82 > r! 8 (F)+ ⇣ 1 ? conv {r! 8 (F) : 8 2 = } . (4.4)
Proof. We apply the chain rule of [140, 10.6] to the composition ( ? !: we have that ( ? is convex with full domain, which implies that the two subdifferentials1 of 5 coincide (i.e., 5 is regular in the terminology of [START_REF] Tyrrell | Variational analysis[END_REF]) and we have (4.3). Since ( ? is the support function of the set ? , standard subdifferential calculus [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF]Cor. 4.4.4] gives that %( ? (!(F)) is the set of optimal solutions of (3.11) with !(F) = (! 8 (F)) 18= . Knowing > and = , the so-called fractional knapsack problem (3.11) can be solved by the simple greedy strategy [START_REF] Dantzig | Discrete-variable extremum problems[END_REF] of taking the largest @ 8 for 8 2 > and completing to 1 with the @ 8 for 8 2 = . Thus @ solution of (3.11) ()

8 > > > > < > > > > : @ 8 = 1 =(1 ?) if 8 2 > 0  @ 8  1 =(1 ?) if 8 2 = s.t. Õ 82 = @ 8 = ⇣ 1 ? @ 8 = 0 otherwise.
By (4.3), this gives:

% 5 (F) = 1 =(1 ?) ' 82 > r! 8 (F)+ ( ' 82 = @ 8 r! 8 (F), s.t. ( 0  @ 8 88 2 = Õ 82 = @ 8 = ⇣ 1 ? ) .
Finally, introducing weights 8 = @ 8 (1 ?) ⇣ for 8 2 = , the right-hand term can be written as the convex hull of r! 8 (F) for 8 2 = , which gives the expression. ⇤

We observe that the expression of % 5 (F) does not involve the gradients of all the ! 8 's, but only of those associated to the largest values. We also see that 5 is differentiable at F if and only if = is reduced to a singleton. The objective function is not differentiable in general, which poses a problem for a direct application of machine-learning gradient-based algorithms.

Efficient Smoothing

In this paragraph, we study a smoothing of nonsmooth superquantile-based functions (4.2). We propose to use the infimal convolution smoothing of [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF]; the comparison to other smoothing approaches is postponed to the next section. We follow the guidelines of [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF] : we smooth only the superquantile ( ? rather than the whole function 5 . Thus we consider 5 ⇡ (F) = ( ?,⇡ (!(F)) for ( ?,⇡ a smooth approximation of ( ? .

(4.5)

Regularizing the dual representation (3.11) of superquantile, we consider the Inf-convolution of the superquantile function, parameterized by the smoothing parameter ⇡,

( ?,⇡ (G) = max @2 ? @ > G ⇡⇡(@) , 8G 2 R n , (4.6)
for a given strongly convex function ⇡.

5 ⇡ (F) 5 (F) 5 ⇡ (F)+ ⇡ 2 for all F 2 R 3 .
Moreover ( ?,⇡ is differentiable, with r( ?,⇡ (G) being the argmax of (4.6), unique by strong convexity of ⇡. When ! is differentiable, 5 ⇡ is differentiable as well, with

r 5 ⇡ (F) = r !(F) ⇤ r( ?,⇡ (!(F)). (4.7)
In our quest for simple and implementable expressions, we study in the rest

Strongly convex regularization

of this section the case of separable strongly functions of the form:

⇡(@) = = ' 8=1 3(@ 8 )
given a strongly convex function 3

: [0, 1]!R. (4.8)
We provide in Corollary 4.4 a general scheme to compute the gradient with explicit expressions in Examples 4.1 and 4.2 for special choices of 3. Finally we discuss the role of the smoothing parameter ⇡ on a numerical illustration.

We start with a lemma gathering the nice duality properties of (4.6).A one-dimensional convex function plays a special role: it is the convex conjugate

⇤ 6 ⇡ (B) = ✓ ⇡3 + 8 h 0, 1 =(1 ?) i ◆ ⇤ (B) = max 0C 1 =(1 ?) {BC ⇡ 3(C)} . (4.9)
Since 3 is strongly convex, standard (one-dimensional) convex analysis gives (see e.g., [61, Prop.I.6.2.2]) that 6 ⇡ is continuously differentiable with derivative 6 0 ⇡ (B) being the (unique) C achieving the above max. Simple calculus yields

6 0 ⇡ (B) = 8 > > > > < > > > > : 0 if B  ⇡ 3 0 + (0) 1 =(1 ?) if B ⇡ 3 0 (1/(=(1 ?))) (3 ⇤ ) 0 B ⇡ otherwise.
min ◆ (◆) = ◆ + = ' 8=1 6 ⇡ (G 8 ◆). (4.11)
Moreover, there is no duality gap between (4.6) and (4.11). There exists a primaldual solution (@ 8 ⇡ , ◆ 8 ) and the unique primal solution can be written @ 8 ⇡ = (6 0 ⇡ (G 8 ◆ 8 )) 8=1,...,= with the help of (4.10).

Proof. This lemma could be proved by applying a sequence of results from abstract Lagrangian duality [61, Chap. XII]. Instead, we provide a simple proof from the direct calculus developed so far. Consider the dualization of the constraint

Õ = 8=1 @ 8 1 = 0 in ? . For a primal variable @ 2 ⌫ ? = h 0, 1 =(1 ?) i = and a dual variable ◆ 2 R, we write the Lagrangian !(@, ◆) = = ' 8=1 @ 8 G 8 ⇡3 8 (@ 8 ) ◆ ⇣ = ' 8=1 @ 8 1 ⌘ = ◆ + = ' 8=1 @ 8 (G 8 ◆) ⇡3 8 (@ 8 ) ,
and the associated dual function

(◆) = max @2⌫ ? !(@, ◆) = ◆ + = ' 8=1 max 0@ 8  1 =(1 ?) @ 8 (G 8 ◆) ⇡ 3 8 (@ 8 ) ,
which gives the expression of the dual function (4.11) from (4.9). Note for later that we have, by construction, the so-called weak duality inequality

(◆) !(@, ◆) = = ' 8=1 @ 8 G 8 ⇡3 8 (@ 8
) for all ◆ and all feasible @ 2 ? . (4.12) Now recall that 6 ⇡ in (4.9) is differentiable and so is the dual function with

 0 (◆) = 1 = ' 8=1 6 0 ⇡ (G 8 ◆) . (4.13)
The above expression also shows that

lim ◆!+1  0 (◆) = 1 and lim ◆! 1  0 (◆) = 1 = ' 8=1 1 =(1 ?) = ? 1 ?
.

By continuity of 6 0 ⇡ and  0 , this implies that there exists ◆ 8 such that  0 (◆ 8 ) = 0, i.e., there exists a dual solution ◆ 8 . On the primal side, the compactness of ⌫ ? and strong convexity of 3 gives existence and uniqueness of the primal solution, denoted @ 8 ⇡ . Observe now that (4.13) means that the vector (6 0 ⇡ (G 8 ◆ 8 )) 8=1,...,= , which lies in ⌫ ? by construction, is in fact primal feasible. From (4.12) and uniqueness of the primal solution, this implies that Primal solution of (4.6)

@ 8 ⇡ = (6 0 ⇡ (G 8 ◆ 8 )) 8=1,...,= (4.14)
and that there is no duality gap.

5 ⇡ (F) = ◆ 8 + = ' 8=1 6 ⇡ (! 8 (F) ◆ 8 ) , (4.15)
r 5 ⇡ (F) = = ' 8=1 6 0 ⇡ (! 8 (F) ◆ 8 )r! 8 (F) (4.16)
where 6 ⇡ and 6 0 ⇡ are given by (4.9) and (4.10).

Proof. The no-gap result of Lemma 4.3 gives that ( ?,⇡ (G) is equal to the optimal value of (4.11). This gives directly the above expression of 5 ⇡ (F) = ( ?,⇡ (!(F)) with ◆ 8 an optimal solution of (4.11) with G 8 = ! 8 (F). Regarding the expression of the gradient, Proposition 4.2 states that r( ?,⇡ (G) is the optimal solution of (4.6), and Lemma 4.3 expresses it as (6 0 ⇡ (G 8 ◆ 8 )) 8=1,...,= . We then get the expression of r 5 ⇡ (F) from (4.7).

⇤

Thus the computation of the first-order oracle of 5 ⇡ boils down to solving the one-dimensional convex problem (4.11) with G 8 = ! 8 (F). This easy task can be done in general by bisection or higher-order schemes. Here Lemma 4.3 allows us to make an additional simplification with an initial interval tightening. We can indeed shrink the segment where to find ◆ 8 to two consecutive points in

# = ⇢ G 8 ⇡ 3 0 + (0), G 8 ⇡ 3 0 ⇣ 1 (=(1 ?) ⌘ 8 = 1, ..., = (4.17)
which is a set of special points regarding the structure of the dual function (recall (4.10) and (4.11)). Denoting ◆ and ◆, defined respectively as the largest point in # such that  0 (◆)0 and the smallest point in # such that  0 ( ◆) 0, we get ◆ 8 by testing three cases:

• if  0 (◆) = 0, take ◆ 8 = ◆ ; if  0 ( ◆) = 0, take ◆ 8 = ◆ ; • otherwise, compute ◆ 8 in the small interval [◆, ◆].
The initial interval tightening thus boils down to having sorted points in #, which is obtained directly from sorting the given data.

Finally we emphasize that we can sometimes go one step further ahead and obtain explicit expressions of ◆ 8 and thus, readily implementable expressions of r 5 ⇡ (F). In the next two examples, we illustrate this for two cases of interest, when we smooth the superquantile by a divergence to the uniform probability (which is at the center of ? ; recall Figure 3.3). In particular the smoothing detailed in the forthcoming Example 4.1 was used in the numerical illustrations of Examples 2.1, 2.2, and 2.3 (where the resulting smoothed superquantile optimization problems were solved by L-BFGS).

⇡(@) = 1 2 k@ @ k 2 with @ = ✓ 1 = , ..., 1 = ◆ , (4.18)
which consists in taking in (4.8)

3(C) = 1 2 ✓ C 1 = ◆ 2 .
In this case, elementary calculus gives

3 0 (0) = 1 = , 3 0 + ✓ 1 =(1 ?) ◆ = ? =(1 ?)
, and

(3 ⇤ ) 0 ✓ C ⇡ ◆ = C ⇡ + 1 =
so that we get from (4.10) the following expression

6 0 ⇡ (G 8 ◆) = 8 > > > < > > > : 0 if ◆ G 8 + ⇡ = 1 =(1 ?) if ◆  G 8 ⇡ = ? 1 ? G 8 ◆ ⇡ + 1 = otherwise. (4.19)
We also have that  0 is piecewise linear in this case and that

# = ⇢ G 8 + ⇡ = , G 8 ⇡ = ? 1 ? 8 = 1, ..., = .
Therefore from ◆ and ◆ in #, finding ◆ 8 in the interval [◆, ◆] simply reduces to Linear interpolation interpolating linearly as

◆ 8 = ◆  0 (◆)( ◆ ◆)  0 ( ◆)  0 (◆) . (4.20)
We can apply

3 0 + (0) = 1, 3 0 ✓ 1 =(1 ?) ◆ = 1 log(=(1 ?)), and (3 ⇤ ) 0 ✓ C ⇡ ◆ = exp ✓ C ⇡ 1
◆ which in turn yields

6 0 ⇡ (G 8 ◆) = ( 1 =(1 ?) if ◆  G 8 + ⇡ log(=(1 ?)) 1 exp ( G 8 ◆ ⇡ 1) otherwise # = G 8 + ⇡ log(=(1 ?)) 1 8 = 1, ..., = .
On the interval [◆, ◆], we have that

 0 (◆) = 1 ' 82 1 =(1 ?) ' 88 exp ⇣ G 8 ◆ ⇡ 1
⌘ Algorithm 1: Fast subroutine for smoothed oracle in the Euclidean setting

Initialization: 4 = (1, ...,1) > , G = !(F), ✓ = 1 =(1 ?) , @ ⇠ = 0 2 R = 1 Find

⇤

We conclude this section on the infimal-smoothing of the superquantile with two remarks illustrating the impact of the smoothing parameter ⇡.

Remark 4.1. We illustrate the impact of the smoothing parameter ⇡ on the relative Impact of the smoothing parameter on the weights weights given to the data. We consider the Euclidean smoothing of Example 4.1 with ? = 0.5; we sample = = 500 points from a Gaussian distribution; and we compute, for different values of ⇡, the distribution of weights @ 8 of (4.19), solutions to smoothed problem (4.6). The right-hand side of Figure 4.1 displays the impact of ⇡ of the obtained weights. In particular, we note that as ⇡ grows, the distribution @ 8 tends to spread uniformly over all data-points, so that the smoothed superquantile acts like the expectation. In contrast, when ⇡ is close to 0, the distribution approximates the uniform distribution over the interval [?,1], so that the smoothed superquantile acts like the superquantile. This approximation is further discussed in the next remark.

⇤

Remark 4.2. We briefly illustrate here the impact of the smoothing parameter Impact of the smoothing parameter on the approximation ⇡: we fix a vector F and we observe the values of smoothed approximations of a superquantile-based function for different values of ⇡. More precisely, we consider a logistic regression problem on the Australian credit dataset from the UCI ML repository. We use the quadratic smoothing of Example 4.1 with ⇡ = 0.1; and we solve the problem by L-BFGS to get the reference point F. Then we compute, at this point, the values of:

• the underlying superquantile-based objective (4.2) which corresponds to the case ⇡ = 0;

• the smoothed approximations (which corresponds to (4.5) with ( ?,⇡ replacing ( ? ) for a sequence of ⇡ evenly spread on a log scale;

• the usual empirical risk minimization objective, which corresponds to the case ⇡ = +1. Indeed, in this regime ⇡ ! +1, the impact of the quadratic penalization term (@ @) increases so that the solution of (4.6) eventually becomes the uniform distribution @, in which case ( ?,⇡ coincides with the expectation.

We observe on Figure 4.2 what is expected: for small values of ⇡, the difference between the superquantile-based objective and its smooth approximations vanishes; for large values of ⇡, the smoothed superquantile loss tends to the average loss and does not approximate the nonsmooth superquantile loss well.

A key benefit of smoothing the superquantile is to leverage efficient smooth optimization algorithms, such as L-BFGS, for superquantile learning. When ⇡ is too small, the problem is almost nonsmooth, which leads to numerical issues with convergence (on this instance, L-BGFS fails to converge when ⇡ is too small or when used with the nonsmooth oracle of Proposition 4.1 due to a line search failure). When ⇡ is too large, the smoothed superquantile gets close to the expectation and the interest of using a superquantile approach disappears. This illustrates the interest of having a moderate ⇡ for superquantile learning, where the smoothed objective is a reasonable approximation of the nonsmooth superquantile, while still being smooth enough to leverage fast optimization algorithms.

⇤

Comparison to other smoothing schemes

We compare the proposed infimal convolution smoothing of the superquantile (4.6) to other possible smoothing schemes. Classical smoothing techniques are based either on convolution or infimal convolution. For superquantile, one could either smooth the dual representation (3.11) or the variational representation (3.12). Together, this yields four natural ways to smooth the superquantile.

We first formalize the equivalence between the two infimal convolution smoothings: indeed, smoothing the dual representation considered in the preceding section corresponds to a smoothing of max{•,0} in the variational formulation.

Corollary 4.5. The infimal convolution smoothing of ( ? with a separable strongly

Equivalence of smoothings with infimal convolution

convex function (4.8) is equivalent to the infimal convolution smoothing of the positive part max{•,0} as

< ⇡ (◆) = max 0C1 ◆ C ⇡ 3(C) with 3(C) = =(1 ?)3 ✓ C =(1 ?) ◆ . (4.22)
More precisely, we have the following equality (to be compared with (3.12))

( ?,⇡ (G) = min ◆ ( ◆ + 1 =(1 ?) = ' 8=1 < ⇡ (G 8 ◆)
<⇡ (◆) = 1 ⇡ π 1 1 max{◆ B,0}⌘ B ⇡ dB = 1 ⇡ π ◆ 1 (◆ B)⌘ B ⇡ dB . (4.23)
The function <⇡ is convex and smooth, with derivative

<0 ⇡ (◆) = 1 ⇡ π ◆ 1 ⌘ B ⇡ dB . (4.24)
2 Applied to max{G, •}, the general smoothing by convolution as defined in (4.23) coincides with the double integral representation used in [START_REF] Chen | A class of smoothing functions for nonlinear and mixed complementarity problems[END_REF][START_REF] Pablo | An approximation scheme for a class of risk-averse stochastic equilibrium problems[END_REF]. Indeed, integrating (4.24) yields

<⇡ (◆) = 1 ⇡ π ◆ 1 π ◆ 0 1 ⌘ B ⇡ dB d◆ 0 .
The next proposition, relating this smoothing to the previous one, involves & C (⌘) the quantile function of a random variable with density ⌘.

Proposition 4.6. With the above notation, the convolution smoothing <⇡ of (4.23) for

Equivalence of convolution/infconvolution smoothings

⇡ = 1 can be written as the infimal-convolution smoothing (to be compared with (4.22))

<1 (◆) = max 0C1 ◆ C 3(C) where 3(C) = C& C (⌘) <1 (& C (⌘)). (4.25)
Conversely, the infimal convolution smoothing < ⇡ of (4.22) for ⇡ = 1 can be written as the convolution smoothing (to be compared with (4.23))

< 1 (◆) = lim B! 1 < 1 (B)+ π ◆ 1 (◆ B) ⌘(B)dB where ⌘(B) = < 00 1 (B) a.e. ( 4

.26)

Proof. For the first part, we consider the convex conjugate of

<1 <⇤ 1 (C) = sup ◆2R ◆ C <1 (◆) . If C 8 [0, 1], the supremum is +1 since | <1 (◆) max{◆,
C = <0 1 (◆ 8 ) = π ◆ 8 1 ⌘(B)dB.
Since the latter is the cumulative distribution function, ◆ 8 = & C (⌘) is the corresponding quantile function (well-defined since ⌘ is continuous). This yields

<⇤ 1 = 3 + 8 [0,1] , (4.27)
which in turn gives (4.25). Finally to establish the strong convexity of 3, we use again (4.27) together with the smoothness of <1 . Thus <1 corresponds to the infimal-convolution smoothing with 3.

For the second part, we start by noting that since < 0 1 is Lipschitz, < 00 1 exists almost everywhere, and ⌘ is well-defined. Since < 1 is convex, it also holds that < 00 1 (B) 0, and then that we have the normalization

π 1 1 ⌘(B)dB = π 1 1 <00 1 (B)dB = lim ◆!1 < 0 1 (◆) lim ◆! 1 < 0 1 (◆) = 1 0 = 1,
where we use < 0 (◆) is the (unique) optimal solution of (4.22). Then the proof follows from the next two claims.

Claim 1: < 1 admits a limit at 1. Convexity of < 1 gives that < 0 1 is nondecreasing. Since lim B! 1 < 0 1 (B) = 0, we get that < 0 1 is non-negative. Thus, < 1 is non-decreasing and, since it is bounded from below, this implies that < 1 admits a limit at 1 (that we denote < 1 ( 1)).

Claim 2: lim

B! 1 B< 0 1 (B) = 0.
For a given B, we write:

B< 0 1 (2B) π B 2B < 0 1 (C)dC = < 1 (B) < 1 (2B),
where the inequality comes from the fact that < 0 1 is non-decreasing. Using that < 1 admits a limit at 1 (Claim 1), we then get Claim 2.

Finally, we can conclude the proof with integrating by parts:

< 1 (◆) = < 1 ( 1) + π ◆ 1 < 0 1 (B)dB = < 1 ( 1) + [(B ◆)< 0 1 (B)] ◆ 1 + π ◆ 1 (◆ B) ⌘(B)dB = < 1 ( 1) + π ◆ 1 (◆ B) ⌘(B)dB.
This establishes (4.26) and ends the proof.

⇤

Finally, we mention the smoothing of the dual representation (3.11) using convolution, which would write:

(⇡ ? (G) = 1 ⇡ π R = ( ? (G I)⌘ I ⇡ dI = E /⇠⌘ [( ? (G ⇡/)] ,
for the density ⌘ : R = ! R and the parameter ⇡>0. We do not consider this smoothing approach because it suffers from two drawbacks in view of practical implementation. First, it usually cannot be computed in closed form, unlike the other smoothing approaches considered here. Second, the Lipschitz constant of the gradient (appearing in condition numbers, constant scalings, and rates of convergence of first-order methods [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]) scales badly: as $( p =/⇡) for the Lipschitz constant of r (⇡ ? [START_REF] Nesterov | Random gradient-free minimization of convex functions[END_REF]Lemma 2], as opposed to the dimensionindependent $(1/⇡) for r( ⇡ ? [117, Theorem 1].

Generalization to law-invariant comonotone risk-measures

In this section, we provide fast smoothing procedures for the class of lawinvariant comonotone risk measures. These results generalize Section 4.2.2 while maintaining (up to a log factor) the linear time complexity of oracle computations. In order to achieve this optimal complexity, we leverage the Kusuoka representation recalled in Section 3.3.2 and extend the dual properties of the superquantile given in Section 4.2.2. The developments of this section are of algorithmic nature. We consider the Euclidean smoothing (see Example 4.1) for its specific properties that we highlight thereafter.

-.

Consider a discrete risk measure ⇢ : R n ! R as in (3.8) satisfying the lawinvariant and comonotone properties. Let ( : ) 1:= be the sequence yielding the Kusuoka representation (3.13) of ⇢. We propose to approximate ⇢ via a smoothing of the sequence of terms : ( : 1 = (G). For a fixed parameter ⇡>0,we thus consider the smooth counterpart ⇢ ⇡ defined as:

⇢ ⇡ (G) = = ' :=1 : ( : 1 = ,⇡ (G). ( 4
| ⇢ ⇡ (G) ⇢(G)|  ⇡ 2 = ' :=2 ( : 1 ). (4.29)
where the sequence ( 8 ) is as defined in Proposition 3.11.

Proof. Let ⇡>0 be fixed and be defined as in Proposition (3.11). For any G 2 R d , since 0 is reduced to the singleton {1/=, ...,1/=}, we have

( 0,⇡ (G) = ( 0 (G).
Thus,

| ⇢ ⇡ (G) ⇢(G)|  = ' :=2 : ( : 1 = ,⇡ (G) ( : 1 = (G)  = ' :=2 : ( : 1 = ,⇡ (G) ( : 1 = (G)  ⇡ 2 = ' :=2 :  ⇡ 2 = ' :=2 (= + 1 :) ( : : 1 )  ⇡ 2 = ' :=2 ( : 1 ),
where the last inequality resulted from an integration by part and the previous one from the non-decrease of the sequence ( 8 ). Smoothness is a direct consequence of the smoothness of the terms ( :

1 = ,⇡ given in Proposition 4.2. ⇤
In particular, we know from Proposition 3.5 that if the support C is included in the simplex, then we necessarily have:

| ⇢ ⇡ (G) ⇢(G)|  ⇡ 2 .
Computation of the smoothed gradient r ⇢ . (x). Let the parameter ⇡>0 be fixed. Let us assume for the moment that we have at our disposal the whole sequence of dual solutions (◆ 8 : ) 0:= 1 of the problem (4.11) for the values of ? in : = ,0  :  = 1 . Then we have a gradient of ⇢ ⇡ :

Smoothed gradient of ⇢ r ⇢ ⇡ (G) = = ' :=1 : @ : 1 (4.30)
where @ : denotes the associated primal solution given by (4.14). Let us explicit this expression.

For : 2 ~0, = 1, let us denote  : the objective of the dual problem (4.11)

with probability value ? = : = :

 : (◆) = ◆ + = ' 8=1 6 ⇡,: (G 8 ◆)
where 6 ⇡,: :

B 7 ! max 0C 1 =(1 : = ) {BC ⇡3(C)} with 3 : C 7 ! 1 2 C 1 = 2 .
Recall that by strong convexity of 3, the functions 6 ⇡,: , : 2 ~0, = 1), are all continuously differentiable and convex. Thus, for all : 2 ~0, = 1,  : is continuously differentiable and  0 : admits everywhere left and right derivatives. We denote  00+ : (◆) the second-order right-derivative at ◆. Finally, we also recall from Example 4.1 and the equation (4.10) that 6 ⇡,: has for derivative:

6 0 ⇡,: (B) = 8 > > > > < > > > > : 0 if B  ⇡ = 1 = : if B > ⇡: =(= :) B ⇡ + 1 = otherwise. (4.31)
We note that for any : 2 ~2, = 1, we have by (4.19):

@ : = = ' 8=1 1 = : 1 ◆ 8 : <G 8 ⇡: =(= :) + ✓ G 8 ◆ 8 : ⇡ + 1 = ◆ 1 G 8 ⇡: =(= :) ◆ 8 : <G 8 + ⇡ = ⌘ 8 (4.32)
which yields:

Decomposition of the smoothed gradient r ⇢ ⇡ (G) = = ' :=1 : @ : 1 = = ' :=1 : = ' 8=1 1 = (: 1) 1 ◆ 8 : 1 <G 8 ⇡(: 1) = (: 1) ⌘ 8 | {z } + = ' :=1 : = ' 8=1 G 8 ◆ 8 : 1 ⇡ + 1 = ! 1 G 8 ⇡(: 1) =(= :+1) ◆ 8 : 1 <G 8 + ⇡ = ⌘ 8 | {z } ⌫ (4.33)
Note that if one computes naively for a given G 2 R n , r ⇢ ⇡ (G) by computing separately the primal solutions @ : from (4.32), it would boil down to a O(= 2 ) complexity. That would compromise the quasi-linear time complexity we aim to achieve. In the rest of this section, we show how to compute r ⇢ ⇡ (G) in quasi-linear time via the expression (4.33). More precisely, we show in the following order:

1. how to compute the whole sequence of (◆ 8 : ) 0:= 1 in quasi-linear time. 2. how to compute the term from (4.33) in linear time.

3. how to compute the term ⌫ from (4.33) in linear time.

We denote by (G (8) ) 18= be the sequence of coordinates of the input vector G 2 R = ranged in an (arbitrary) non-decreasing order.

( † k .
We saw in Lemma 4.3 that finding the minimizer ◆ 8

: of  : can be done in linear time. In this paragraph, we show the stronger claim that finding the complete sequence of roots (◆ 8 : ) 0:= 1 can be done in at most O(= log =) operations. We start with two simple observations formalized as lemmas.

Lemma 4.8. ◆ 8 0 := G (0) 1 is a minimizer of  0 and  00+ : (G (0) 1) = 0.

First root

Proof. Noting that for all B  G (0) and 9 2 ~1, = we have G 9 B 0, we have in view of (4.31)

 0 0 (B) = 1 = ' 8=1 6 0 ⇡,0 (G 8 B) = 0.
In particular,  0 0 (B) =  00+ 0 (B) = 0 ⇤ Lemma 4.9. The sequence ( 0 : ) 0:= 1 is non-increasing on R.

Non-increase of the sequence ( : ) 0:= 1

Proof. For any : 2 ~0, = 1, we note that = :)

 0 : (◆) = 1 = ' 8=1 6 0 ⇡,: (G 8 ◆) , 8◆ 2
+ 1 = = 1 ⇡ ⇡: =(= :) + 1 =  B ⇡ + 1 = = 6 ⇡,:+1 (B),
which ends the proof.

⇤

Browsing through ) 0 k . Let : 2 ~0, = 1 be fixed and ◆ 2 R be such that

 0 : (◆)0.
As a specificity of the Euclidean prox function 3, we obtain that  0 : is a piece-wise affine non-decreasing function. The discontinuity points of  00 : all

Set of discontinuity points # :

belong to the set

# : := ⇢ G (8) ⇡: =(= :) , G (8) + ⇡ = , 8 2 ~1, = .
Assume for now that we know the values of  0 : (◆),  00+ : (◆) and the two following indices:

8 (◆, :) := ( min{8, G (8) + ⇡ = >◆} if ◆<G (=) + ⇡ = = + 1 otherwise, 8 + (◆, :) := ( min{8, G (8)
⇡:

=(= :) >◆} if ◆<G (=) ⇡: =(= :) = + 1 otherwise. (4.34)
Intuitively, 8 (◆, :) and 8 + (◆, :) are the indices of the first points in # : that are strictly greater than ◆.

Let us then set ⌫ to be the first point in # : that is strictly greater than ◆ 3 ⌫ := min : has no discontinuity point on the interval [◆, ⌫). Thus,

 0 : (⌫) =  0 : (◆)+(⌫ ◆) 00+ : (◆). (4.37)
Finally, noting that (3 ⇤ ) 00 = 1, simple derivations of the function  : yield . Assuming now that we know  0 : (◆),  00+ : (◆), 8 (◆, :) and 8 + (◆, :) as defined in 4.34, we can compute efficiently these indices at : + 1 -8 (◆, : + 1), 8 + (◆, : + 1) -as well as  0 :+1 (◆) as well  00+ :+1 (◆).

 00+ : (⌫) = 1 ⇡ 8 + (⌫,:) ' 8=8 (⌫,:) (3 ⇤ ) 00 ✓ G (8) ⌫ ⇡ ◆ = 1 ⇡ (8 + (⌫, :) 8 (⌫, :)) . ( 4
Indeed, we first note by definition of 8 (◆, : + 1) and since :+1 =(= : 1) > : =(= :) that, 8 (◆, : + 1) = 8 (◆, :) ,

8 + (◆, : + 1) = 1 + = ' 8=1 1 ◆ G 8 ⇡(:+1) =(= : 1) = 8 + (◆, :)+ = ' 8=8 + (◆,:) 1 G (8) ⇡: =(= :) >◆ G (8) ⇡(:+1) =(= : 1) . (4.39)
We also note in view of (4.10) that

 0 : (◆) = 1 = ' 8=1 6 0 ⇡,: (G 8 ◆) = 1 = ' 8=1 1 = :
1 ◆<G 8 ⇡:

=(= :) +(3 ⇤ ) 0 ⇣ G 8 ◆ ⇡ ⌘ 1 G 8 ⇡: =(= :) ◆<G 8 + ⇡ = = 1 8 + (◆,:) 1 ' 8=8 (◆,:) (3 ⇤ ) 0 ⇣ G (8) ◆ ⇡ ⌘ ' 8 8 + (◆,:) 1 = :
.

 0 : (◆)  0 :+1 (◆) = 8 + (◆,:+1) 1 ' 8=8 + (◆,:) ✓ G (8) ◆ ⇡ + 1 = 1 = : ◆ + = + 1 8 + (◆, : + 1) ✓ 1 = (: + 1) 1 = : ◆ . (4.40)
Finally, we also have by (4.38): : ) 0:= 1 in quasi-linear time. We begin with several intermediate lemmas to bound the complexity of a single iteration : of our Algorithm 2. 4 We first note that for each rank : 2 ~0, = 1, running lines 2 to 3 clearly requires at most 2 operations.

 00+ :+1 (◆) = 1 ⇡ 8 + (◆, : + 1) 8 (◆, : + 1) . ( 4
Let us now bound the complexity for running lines 5 to 16. We introduce for : 2 ~1, = 1, the sets

" : = (◆ 8 : 1 , ◆ 8 : )\# : + : = ⇢ 8 2 ~1, =, G (8)
⇡: =(= :)

2 " :

: = n 8 2 ~1, =, G (8) + ⇡ = 2 " :
o Lemma 4.11. For any :, : 0 2 ~1, = 1 such that : < : 0 , we have:

The sets : do not intersect : \ : 0 = ; and + : \ + : 0 = ;.

Proof. In view of Lemma 4.9 the sequence (◆ 8 : ) 0:= 1 is non-decreasing. Hence, for any :, : 0 2 ~1, = 1 such that : < : 0 , we have

" : \ " : 0 = ;.
Thus, it is clear that the sets : , : 2 ~1, = 2 do not intersect each other. Let us fix now : 2 ~1, = 2 and 8 2 ~1, =. If 8 2 + : , then since the sequence (⇡:/(=(= :))) 0:= 1 is increasing, we have

G (8) ⇡(: + 1) =(= : 1) < G (

⇤

We can bound then the number of operations required to run the lines 5 to 16 in Algorithm 2. Lemma 4.12. There exists a constant C 1 such that for all : 2 ~1, = 1, the number ⇡ :

Upper bound on the complexity of lines to

of operations required to run the lines 5 to 16 in Algorithm 2 satisfies

⇡ :  C 1 (card(" : )+1). (4.42)
Proof. Observe that during the execution of the lines 5 to 16, we visit only points in " : and the first point in # : (according to the sorting of the G 8 established) that is greater or equal to ◆ 8 : . Using the sorting of the G 8 's previously computed we can visit these points a single time in an increasing order if we rely on the indices 8 (•, :) and 8 + (•, :) and formula (4.35) during this visit. The price of visiting each point is constant: it is either a single equality test (which happens in (4.36) when several points in " : are equal to ⌫), or a finite number of operations, in view of formulas (4.37), (4.38) and the inequality tests in lines 7, 10 and 13. Letting C 1 be an upper bound of this finite number, which is independent of :, we obtain (4.42).

⇤

We note that for each rank : 2 ~0, = 1, running lines 17 to 24 clearly requires at most constant number of operations, independant of :, that we will denote C 2 . Finally we can upper-bound the number of operations required to run lines 26 to 29 with the following lemma. Let us now introduce for

: 2 ~0, = 2, : = ~8+ (◆ 8 : , :)8 + (◆ 8 : , : + 1) 1 = ⇢ 8 2 ~1, =, G (8)
⇡: =(= :) >◆ G (8) ⇡(: + 1) =(= : 1) Lemma 4.13. For any :, : 0 2 ~0, = 1 such that : < : 0 , we have : \ : 0 = ;. ' : ( 7 + C 3 )=.

= 0 8 (◆,0) := 1, 8 + (◆,0) = 1,  0 0 (◆) = 0,  00+ 0 (◆) = 0; 1 while :  = 1 do 2 if  0 : (◆) =
Thus,

T = ( 9 + 3C 1 + C 2 + C 3 ))=
which finishes the proof.

⇤ (4.33).

Let us show now how the terms and ⌫ from (4.33) may be computed in linear time.

Let (⌘ 1 , ..., ⌘ = ) denote the canonical basis of R n . Let (G (8) ) 18= be again the sequence of coordinates of G sorted in an arbitrary non-decreasing order. If denotes the permutation that sorts the coordinates of G (i.e. G (8) = G (8) ), we will accordingly transpose the notation by defining for 8 2 ~1, =, ⌘ (8) := ⌘ (8) , etc... We show in the next two paragraphs how the expressions and ⌫ from (4.33) may be computed in linear time.

Computing G from (4.33). We first show how the computation of may be performed in linear time. Indeed, observe that RiskOptimizer inherits from scikit-learn's estimators: we use the fit method to run the optimization algorithm on the provided data, to get a minimizer of (4.2).

= = ' :=1 : = ' 8=8 + (◆ 8 : 1 ,: 1) 1 = (: 1) ⌘ 8 = 1 1 = = ' 8=8 0 ◆ 8 0 ⌘ (8) + 2 1 = 1 = ' 8=8 1 ◆ 8 1 ⌘ (8) +•••+ = = ' 8=8 = 1 ◆ 8 = 1 ⌘ (8) = = ' :=1 : ' B=1 B 1 = (B
# Running the algorithm optimizer.fit(A,B) sol = optimizer.solution : spqr .

Options and parameters. The customizable parameters are stored in a

Customization python dictionary, called params, which is designed as an attribute of the RiskOptimizer class. The main parameters to tune are: the choice of the oracle, the choice of the algorithm, the safety probability level p, the starting point of the algorithm w_start, the maximum number of iterations max_iter.

The user can specify some of these parameters as an input and the others will be filled with defaults values when instantiating a RiskOptimizer. For example: custom_params = {'algorithm': 'dualaveraging', # selected algorithm 'p': 0.2 } # safety probability level custom_optimizer = RiskOptimizer(loss, loss_prime, params=custom_params)

Some important parameters (such as the safety probability level, the algorithm chosen, or the smoothing parameter ⇠) can be given directly to the constructor of the class RiskOptimizer when instantiating the object. For example: other_custom_optimizer = RiskOptimizer(loss, loss_prime, p=0.95, algorithm='bfgs', mu=0.1) Each algorithm is implemented as a python class that stores the oracle, together with relevant parameters for the optimization process. The main method of each implemented algorithm class is run, which is run when RiskOptimizer.fit is called. The parameters of the algorithm selected are stored in the dictionary params that is an input of the class RiskOptimizer. Hence, in a standard usage, there is no need to interact with the algorithm python object.

Oracle classes. The selection of the oracle is automatically done when the

4.4

We report two types of numerical experiments:

• In the first paragraph, we consider "Optimization" experiments. There are many algorithmic options within the toolbox SPQR; we provide here a comparison of batch vs. mini-batch algorithms and a discussion of the tuning of the smoothness parameter.

• In the second paragraph, we consider "Learning" experiments. The interest of using superquantile in learning has been shown empirically in several recent papers, including [START_REF] Curi | Adaptive sampling for stochastic risk-averse learning[END_REF][START_REF] Laguel | A Superquantile Approach to Federated Learning with Heterogeneous Devices[END_REF][START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF][START_REF] Soma | Statistical learning with conditional value at risk[END_REF][START_REF] Williamson | Fairness risk measures[END_REF]. We provide here complementary experiments highlighting the robustness of superquantilelearnt models.

All experiments are run using SPQR. The optimization algorithms are initialized at F = 0 2 R d . For these experiments, we use a bunch of standard datasets from the UCI repository, which scale from 352 to 94644 datapoints. For each dataset, categorical features were one-hot encoded so that the total number of features ranges from 3 to 287. For one experiment, we report the agreggated results for all the datasets. For the other experiments, we report in the main text the detailed results for one representative dataset, and we provide in appendix complementary results for others datasets.

Solving superquantile-based learning

In this section, we illustrate two different aspects of the optimization methods available in SPQR. First, we compare the two families of algorithms available batch vs. mini-batch (more precisely SGD with momentum and L-BFGS) showing the interest of using batch algorithms for superquantile-based learning within scikitlearn/SPQR. Second, we experiment with all the range of the smoothing parameter, advocating to avoid extreme values.

Batch vs. mini-batch. We compare on a standard problem stochastic gradient optimization (denoted SGD) and batch quasi-Newton optimization using lowmemory BFGS [START_REF] Nocedal | Numerical optimization[END_REF] (denoted BFGS). For this experiment, the set-up is similar to the one of [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF]. We consider a Setup supervised multi-class classification task with the superquantile multinomial logistic loss on the MNIST dataset. We perform feature extraction from the images using a pre-trained convolutional network similarly to [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF]. For a fixed probability threshold set to ? = 0.8, we then train a logistic regression on top of the transformed data. For SGD, we use a momentum term of 0.9 and we use a step decay scheme ◆ C = ◆ 0 3 bC/C 0 c , where ◆ 0 is tuned with respect to the size of the mini-batch <, and where 3 = 0.5 and C 0 = 10 epochs are fixed throughout all the experiments. For each mini-batch size < 2{10, 100, 1000}, we tune ◆ 0 via a grid-search and take the highest initial value yielding a non-diverging sequence of iterates. In constrast with SGD, the quasi-Newton algorithm does not require specific tuning as it automatically calibrates stepsizes by line-searches at each iteration.

On the left part of Figure 4.4, we compare the performance of SGD for

Comparison between L-BFGS and SGD

the different mini-batch sizes. Each color corresponds to a mini batch size < 2{10, 100, 1000}. Along iterates, the bold line represents the mean value over the five seeds of the functions and the shaded region represent the difference between the min and max values across the seeds. We observe that there is no substantial difference among the sizes of the mini-batches: all curves show a noisy behaviour (caused by the stochastic approximation of the gradient at each step) and eventually converge to a suboptimal value. Unlike SGD, L-BFGS (right part of Figure 4.4) presents a stable convergence. We observe also that a large number of epochs is necessary for SGD to catch up with BFGS for superquantile-based training. This is to be contrasted with the usually small number of epochs necessary for SGD to catch with BFGS for expectation-based training or ERM. Note that a a final bias remains visible between the stochastic methods and the deterministic BFGS, as expected by the theory laid down in [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF].

Impact of the smoothing parameter on L-BFGS. We consider a logistic re-

Impact of the smoothing parameter on L-BFGS

gression on the Australian Credit dataset. For a sequence of smoothing parameters ⇡ evenly spread on a log scale, we train F 8 ⇡ by solving the superquantile learning objective with L-BFGS and ? = .99.

On Figure 4.5, we report both the value of the smoothed .99-superquantile (purple) and the nonsmoothed .99-superquantile (dashed green) at the F 8 ⇡ . We also train the standard empirical risk minimizer F 8 and we report both the average loss (solid black line) and the nonsmoothed .99-superquantile loss (dashed black line) at F 8 .

For very small values of ⇡ (< 10 3 ), we observe unsuccessful termination of the L-BFGS algorithm, due to the failure of the line-search. For medium values of ⇡ (< 1), the value of smooth superquantile-based function at F 8 ⇡ roughly coincides the nonsmooth one. Finally for high values of ⇡(> 10 3 ), we observe that the smooth superquantile tends to the same optimal function value of the empirical risk minimizer F 8 , as expected from Section 4.2.

Superquantile brings robustness against distributional shifts

In the second part of the numerical experiments, we show the interest of superquantile for worst-case learning by comparing superquantile-based minimization vs empirical risk minimization, similarly to [START_REF] Curi | Adaptive sampling for stochastic risk-averse learning[END_REF]. For the three next standard regression or classification tasks, we proceed as follows. For each dataset, we first perform a 80%-20% train-test split. Second, we minimize with respect to the train set a regularized objective, both in expectation and with respect to the superquantile:

min F2R d E (G,H)⇠⇡ train ✓ (H, F > G)+ ⌫ 2 kF k 2 2 min F2R d [( ? ] (G,H)⇠⇡ train ✓ (H, F > G)+ ⌫ 2 kF k 2 2 (4.48)
We set the regularization parameter ⌫ to be the inverse of the number of training data-points: ⌫ = 1/= train . The above problems are solved with SPQR using L-BGFS. Then we perform three different types of distributional shifts on the testing set and we compare the behaviour of the superquantile-based models and the ERM models. We develop this approach in the next three experiments.

Superquantile ridge-regression. We consider a ridge regression problem, that

Setup is (4.48) with ✓ (H,

F > G) = (H F > G) 2
, on the dataset Cpu-small. We minimize the two problems in expectation and (ii) with respect to the superquantile with several safety thresholds ? 2{0.3, 0.5, 0.7, 0.8, 0.9, 0.95, 0.99}.

We report in Figure 4.6 the histogram of losses on the test set and compare

Superquantiles reduce worst-case losses

each trained superquantile model (in red) with the ERM model (in blue). We observe that as the probability threshold ? grows, the right tail distribution of losses on the test set gets shifted to the left. In particular, a drastic decrease of the 90 th quantile of the losses can be observed. Thus superquantile learning allows us to reduce worst-case losses. This comes with the price of lower performances on the left tail distribution.

Superquantile logistic regression.We consider a regularized logistic regression

Setup problem, that is (4.48) with ✓ (H,

F > G) = H (F > G) (1 H) (F > G)
(where (I) := 1 1+4 I denotes the sigmoid function). We use 10 classification datasets from the UCI repository library and we perform a distributional shift on the train sets: we subsample the majority class so that it accounts for only 10% of the minority class. Then we train a ERM and superquantile models. The safety parameter ? is tuned via a cross validation procedure on the shifted train set. We finally compute, for the best parameter obtained, the test accuracy and the test loss.

We report our results in Table 4.1. For most datasets, we note a significant

Robustness of superquantile for a given distributional shifts

decrease of the test loss with the superquantile model, when compared to ERM model. In terms of accuracy, the superquantile model offers better performance for this particular distributional shift.

Robustness to all possible distributional shifts. We take the same setting as Setup before, focusing on the splice dataset, and now we perform a sequence of distributional shifts on the training set by rebalancing all the proportions of the two classes. More precisely, for a fixed 2(0, 1), we compute the number = min of sample from the minority class; we randomly select d = min e points from the majority class and d( 1)= min e from the minority class. We train on the shifted train set the two logistic regression models of (4.48). We repeat this experiment for 5 different seeds and we compute the average test loss and test accuracies of both models. The experiment is conducted for 100 values of evenly spread on (0, 1). The histograms of Figure 4.7 depicts the performances, as varies, of ERM

Robustness of superquantiles to adversarial distributional shifts

against the superquantile for a fixed probability threshold ?. In terms of losses, the superquantile model brings better performances for almost all values of ?. In particular, the 90 th quantile of the losses over all considered shifts gets notably decreased for ?. In terms of accuracy, the superquantile models brings better performance with respect to distributional shifts for all values of ?.

4.5

In this chapter, we addressed the problem of minimizing superquantile-based risk measures by first-order methods. We provided explicit expressions of (sub)gradients of (smoothed) superquantiles where we went down to the details of computations in order to get efficient first-order oracles for superquantilebased functions. We provided a generalization of such smoothing procedures to coherent law-invariant comonotone risk measures with a special care on maintaining a minimal complexity. We released an open-source python toolbox for the minimization of superquantile-based objectives. The first one, built on top of scikit-learn aims at tackling general convex problems of low or middle size. We finally provided an overview of the recent applications of superquantiles in machine learning and illustrated on real datasets, the performances of our methods through several numerical experiments.

SOLVING CHANCE-CONSTRAINED PROBLEMS

This chapter is devoted to a new algorithm for solving chance-constrained (convex) programs.

The developments laid down below build upon the following work:

• Y. Laguel, W. Van Ackooij and J. Malick. Chance constrained convex problems: a bilevel convex optimization perspective. Preprint: https: //arxiv.org/pdf/2103.10832.pdf, 2021.

5.1

In this chapter, we address the solving of the general chance-constrained optimization problem introduced in Section 3.5. That is, for a fixed safety

General chance-constrained problem

probability level ? 2[0, 1), we consider:

min G2C 5 (F) s.t. P[6(F, ⇢)0] ?, (5.1)
where 5 : R d ! R and 6 : R d ⇥ R m ! R are two given functions, ⇢ is a random vector valued in R m and C ⇢ R d is a (deterministic) closed constraint set. We consider the case of underlying convexity: we assume that 5 and 6 are convex (with respect to F). For our practical developments, we also assume that we have first-order oracles for 5 and 6 and that the C is a box constraint on the decision variable G. As discussed in Section 3.5, even with underlying convexity, chance-constrained problems remain difficult to solve: the chance constraint feasible can remain non-convex even in simple standard cases as illustrated in Example 3.4.

We propose an original approach for solving chance-constrained optimization problems. First, we present an exact reformulation of (nonconvex) chanceconstrained problems as (convex) bilevel optimization problems. This reformulation is simple and natural, involving superquantiles. Second, exploiting this bilevel reformulation, we propose a general algorithm for solving chance-constrained problems, and we release an open-source python toolbox implementation. In the case where we make no assumption on the underlying uncertainty and have only samples of ⇢, we propose and analyse a double penalization method, leading to an unconstrained single level DC (Difference of Convex) program. Our approach enables to deal with a fairly large sample of data-points in comparison with state-of-the-art methods based on mixed-integer reformulations, e.g. [3]. Thus our work mixes a variety of techniques coming from different subdomains of optimization: penalization, error bounds, DC programming, bundle algorithm, Nesterov's smoothing; relevant references are given along the discussion.

This chapter is structured as follows. In Section 5.2, we leverage the known Outline Theorem 5.

Problem (5.1) is equivalent to the bilevel problem:

Bi-level reformulation of chance constraints

> > > < > > > :

min F2C,◆2R 5 (F)

s.t. ◆  0 ◆ 2 ((F) = arg min B2R ⌧ ? (F, B).
(5.4)

More precisely, if F 8 is an optimal solution of (5.1), then (F 8 , & ? (6(F 8 , ⇢))) is an optimal solution of the above bilevel problem, and conversely.

Proof. It is clear with Lemma 5.1 that problem (5.1) is equivalent to The first constraint ◆  0 is an easy one-dimensional bound constraint which does not involve the decision variable F. The second constraint, which constitutes the lower level problem is more difficult; when this constraint is satisfied, ◆ is an upper-bound on the ?-quantile of 6(F, ⇢). We readily see the joint convexity of the objective function of the lower level problem in (5.4) with respect to B and F. Note finally that the extension to joint chance-constrained programs is straightforward: if 6 : R 3 ⇥ R < ! R : has all its components 6 8 , (1  8  :) convex with respect to F, we have:

8 > > > > < > > > > : min F2C,◆2R 5 (F) s.t. ◆  0 ◆ = & ? (6(F, ⇢)) . ( 5
P ⇥ 6(F, ⇢)0 ⇤ ? , P  max 18: 6 8 (F, ⇢)0 ? , & ? ✓ max 18: 6 8 (F, ⇢) ◆  0 ,9 ◆  0 s.t. ◆ 2 arg min B2R B + 1 1 ? E  max 08: 6 8 (F, ⇢) (with 6 0 := 0)
and the lower-level problem remains convex. This bilevel reformulation is nice, natural and seemingly new; we believe that it opens the door to new approaches for solving chance-constrained convex problems. In the next section, we propose such an approach based on the reformulation.

5.3

In this section, we explore one possibility offered by the bilevel formulation of chance-constrained problems, presented in the previous section. We propose a (double) penalization approach for solving the bilevel optimization problem, with a different treatment of the two constraints: a basic penalization of the easy constraint together with an exact penalization of the hard constraint formalized as the lower problem.

We first exhibit and analyze in Section 5.3.1, the weak sharpness properties of the lower-level problem in (5.4). We show then in Section 5.3.2 to what extent these properties help to provide an exact penalization of the "hard" constraint. We finally present the double penalty scheme in section 5.3.3.

From the bilevel problem (5.4), we derive the two following penalized problems, associated with two penalization parameters ⇠, ⌫>0 and

(% ⌫,⇠ ) min (F,◆)2C⇥R 5 (F)+⌫ ✓ ⌧ ? (F, ◆) min B2R ⌧ ? (F, B) ◆ + ⇠ max(◆,0). (5.7)
We consider a general data-driven situation where the uncertainty ⇢ is just known through a sample (or, said alternatively, follows an equiprobable discrete distribution over = 2 N arbitrary values): we assume that there exists

⇢ 1 , ⇢ 2 , ..., ⇢ = 2 R m such that P[⇢ = ⇢ 8 ] = 1
= for all 8 2{ 1, ..., =}. The set I = defined as

I = = ⇢ 8 = , 8 2{0, ..., = 1} (5.8)
plays a special role in our developments. In particular, we denote by dist I = (?) := inf{k? 8 < k,0  8  = 1}, the distance to I = , to define a key quantity appearing in the variational results of this section: we introduce

⇣ ? = 8 > > > > < > > > > : 1 =(1 ?) if ? 2 I = dist I = (?) (1 ?) otherwise, (5.9)
which depends implicitly on the number of samples = and the fixed safety parameter ?.

Weak sharpness and analysis of the value function

In Chapter 4 of this thesis, we uncovered the nonsmoothness of the superquantile function based on a study of its distributionally robust formulation (3.11).W e extend here the analysis by bringing to light the weak sharpness properties of the superquantile, based on the variational formulation (5.2). Given an optimization problem min

F2X !(F),
we recall that its solution set X 8 is said to be weakly sharp (or equivalently that it satisfies the first-order growth condition) if there exists a constant ⇣>0 such that

Weak sharpness !(G) !(H)+⇣ dist X 8 (G), 8G 2 X , 8H 2 X 8 .
The constant ⇣, specific to each problem is often called the weak-sharpness modulus of this problem. Now, one may observe that weak sharpness of the problem (5.2) is a direct consequence of its linearity, in view of the next Proposition.

(P ⌘ ) 8 > > > > < > > > > : min (G,H)2R 2 ! & (G, H) = G (1 + ⌘) H s.t. H  0 H G  0 (5.10)
This problem is illustrated in Figure 5.1. Note that for any ⌘>0 the solution set of (% ⌘ ) is reduced to the singleton 0. Observe now that the point ( 1, 1) is feasible for all ⌘>0 and ! ⌘ ( 1, 1) = ⌘ while dist X 8 = p 2 does not depend on ⌘. Hence taking ⌘ arbitrarily small lead to a problem P ⌘ with arbitrarily small weak sharp modulus.

⇤

Fortunately, the superquantile problem (5.2) admits for any ? 2[0, 1) a weaksharpness modulus which will be key in the forthcoming exact penalization procedure. We study here the value function ⌘ : C ⇥ R ! R defined, from ⌧ ? in (5.3), as ⌘(F, ◆) = ⌧ ? (F, ◆) min B2R ⌧ ? (F, B).

(5.11)

The next result relates ⌘ to dist ((F) (•), the distance function to ((F), the solution set of the lower level problems in (5.4). This is our main technical result, on which next propositions are based.

Theorem 5.5. Let ? 2[ 0, 1) be fixed but arbitrary. The function ⌘ defined in (5.11) Weak sharpness of the superquantile

satisfies for any (F, ◆)2C ⇥ R ⌘(F, ◆) ⇣ ? dist ((F) (◆)
with ((F) and ⇣ ? defined respectively in (5.4) and (5.9). In other words, the variational problem (5.2) is weakly sharp with a weak-sharpness modulus larger than ⇣ ? .

Proof. Let us fix F 2 C and denote by @ ? the ?-quantile of 6(F, ⇢). We first note that by the arguments in the proof of Lemma 5.1, we have

?  P[6(F, ⇢)@ ? ],
with equality holding in the left inequality, if and only if ? belongs to I = .

For any fixed but arbitrary ◆ 2 R, we have the following identity:

⌘(F, ◆) = ◆ + 1 1 ? E[max(6(F, ⇢) ◆,0)] ✓ @ ? + 1 1 ? E[max(6(F, ⇢) @ ? ,0)] ◆ = (◆ @ ? )+ 1 1 ? E ⇥ max(6(F, ⇢), ◆) ◆ (max(6(F, ⇢), @ ? ) @ ? ) ⇤ = (◆ @ ? )(1 1 1 ? )+ 1 1 ? E ⇥ max(6(F, ⇢), ◆) max(6(F, ⇢), @ ? ) ⇤ .
Now, by employing a case distinction on the location of ◆ with respect to @ ? , we will derive the desired inequalities. Let us first consider that ◆>@ ? , then we have:

⌘(F, ◆) = (◆ @ ? )(1 1 1 ? )+ 1 1 ? E h (◆ 6(F, ⇢)) 1 @ ? <6(F,⇢)◆ +(◆ @ ? ) 1 6(F,⇢)@ ? i = (◆ @ ? )(1 1 1 ? + 1 1 ? P[6(F, ⇢)@ ? ]) + 1 1 ? E[(◆ 6(F, ⇢)) 1 @ ? <6(F,⇢)◆ ]
which finally gives:

⌘(F, ◆) = (◆ @ ? ) 1 ? ✓ P[6(F, ⇢)@ ? ] ? + E  ◆ 6(F, ⇢) ◆ @ ? 1 @ ? <6(F,⇢)◆ ◆ . (5.12)
Now if ? 8 I = , since P[6(F, ⇢)@ ? ]2I = , we have:

⌘(F, ◆) ( ◆ @ ? ) 1 1 ? P[6(F, ⇢)@ ? ] ? dist I = (?) 1 ? dist ((F) (◆).
Here we use that clearly |◆ @ ? | dist ((F) (◆), since @ ? 2 ((F) as already recalled.

If ? 2 I = , we have two cases. First, if P[6(F, ⇢)@ ? ] > ?, then since P[6(F, ⇢)@ ? ]2I = , we have by definition of I = , P[6(F, ⇢)] ?

1 = and consequently ⌘(F, ◆) ( ◆ @ ? ) 1 1 ? P[6(F, ⇢)@ ? ] ? 1 =(1 ?) dist ((F) (◆). Second, if P[6(F, ⇢)@ ? ] = ?, then ⌘(F, ◆) = 1 1 ? E[(◆ 6(F, ⇢)) 1 @ ? <6(F,⇢)◆ ].
We let @ + ? be the successor quantile, i.e.,

@ + ? = inf{C R : P[6(F, ⇢)C] > ?}. Now if ◆ 2(@ ? , @ + ? ), we have ⌘(F, ◆) = 0. If ◆ @ + ? , then ⌘(F, ◆) = 1 1 ? E h (◆ 6(F, ⇢)) 1 @ + ?  6(F,⇢)◆ i ( ◆ @ + ? ) P[6(F, ⇢) = @ + ? ] 1 ? 1 =(1 ?) dist ((F) (◆)
where the last inequality results from our earlier estimates.

The second case to consider involves the situation ◆<@ ? . Here, we have:

⌘(F, ◆) = (◆ @ ? )(1 1 1 ? )+ 1 1 ? E h (6(F, ⇢) @ ? ) 1 ◆<6(F,⇢)@ ? +(◆ @ ? ) 1 6(F,⇢)◆ i = (◆ @ ? ) ✓ 1 1 1 ? + 1 1 ? P[6(F, ⇢)◆] ◆ + 1 1 ? E h (6(F, ⇢) @ ? ) 1 ◆<6(F,⇢)@ ? i which leads us to ⌘(F, ◆) = (@ ? ◆)
1 ?

✓

? P[6(F, ⇢)◆] E  @ ? 6(F, ⇢)

@ ? ◆ 1 ◆<6(F,⇢)@ ? ◆ . (5.13)
Let us define the antecessor quantile @ ? as

@ ? = max sup{C R : P[6(F, ⇢)C] < ?}, min{6(F, ⇢ 8 )} = 8=1 1 .
and note that: P[6(F, ⇢)@ ? ] < ?  P[6(F, ⇢)@ ? ]. Hence, we have:

⌘(F, ◆) = (@ ? ◆) 1 ? ✓ ? P[6(F, ⇢)◆] E  @ ? 6(F, ⇢) @ ? ◆ 1 ◆<6(F,⇢)@ ? ◆ .
(@ ? ◆)

1 ?

⇣

? P[6(F, ⇢)max(◆, @ ? )] ⌘ .

If ? 8 I = , we get, since P[6(F, ⇢)max(◆, @ ? )] 2 I = :

⌘(F, ◆) dist I = (?) 1 ? dist ((F) (◆).
If ? 2 I = we note subsequently that P[6(F, ⇢)max(@ ? , ◆)] = P[6(F, ⇢)@ ? ] since 1 @ ?  6(F, ⇢)◆ = 0 under the assumption ◆  @ ? . Thus, since ? > P[6(F, ⇢)@ ? ]2I = we have necessarily ? P[6(F, ⇢)@ ? ] 1 = which gives:

⌘(F, ◆) 1 =(1 ?) dist ((F) (◆).

⇤

Following the terminology of [START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF], this theorem shows that ⌘ is a uniform parametric error bound. We note that the quality of this bound is altered by the number = of data points considered. This drawback actually passes to the limit in the sense that (F, ◆) 7 ! ⌘(F, ◆) fails to be a uniform parametric error bound when ⇢ follows a continuous distribution; this is an interesting but secondary result that we prove in Section 5.3.4.

Exact penalization for the hard constraint

We show here that (% ⌫,⇠ ) is an exact penalization of (% ⇠ ), when ⌫ is large enough. The proof of this result follows usual rationale (see e.g., [START_REF] Frank | Optimization and Nonsmooth Analysis[END_REF]Prop. 2.4.3]); the main technicality is the sharp growth of ⌘ established in Theorem 5.5. Proposition 5.6. Let ⇠>0 be given and assume that there is a solution to (% ⇠ ) defined Exact Penalization of the hard constraint in (5.6). Then for any ⌫>⇠ /⇣ ? with ⇣ ? defined in (5.9), the solution set of (% ⇠ ) coincides with the one of (% ⌫,⇠ ) defined in (5.7).

Proof. Take ⇠>0, define ⌫ ⇠ = ⇠/⇣ ? , and take ⌫>⌫ ⇠ arbitrary but fixed. Let us first take a solution (F 8 , ◆ 8 )2C ⇥ R of (% ⇠ ) and show by contradiction that it is also a solution of (% ⌫,⇠ ). Indeed, to the contrary, assume there exists some ⌘>0 and (F 0 , ◆ 0 )2C ⇥ R such that:

5 (F 0 )+⇠ max(0, ◆ 0 )+⌫⌘ F 0 (◆ 0 ) 5 (F 8 )+⇠ max(0, ◆ 8 )+⌫ ⌘ F 8 (◆ 8 ) ⌘.
Let then ◆ 0 ? 2 ((F 0 ) be such that :

|◆ 0 ? ◆ 0 |dist ((F 0 ) (◆ 0 )+ ⌘ 2⇠ .
Then the point (F 0 , ◆ 0 ? ) is feasible for % ⇠ (recall ◆ 0 ? 2 ((F 0 )) and since ◆ 7 ! ⇠ max(0, ◆) is ⇠-Lipschitz, we first have

5 (F 0 )+⇠ max(0, ◆ 0 ? ) 5 (F 0 )+⇠ max(◆ 0 ,0)+⇠|◆ 0 ? ◆ 0 |  5 (F 0 )+⇠ max(◆ 0 ,0)+⇠ ✓ dist ((F 0 ) (◆ 0 )+ ⌘ 2⇠ ◆ .
Using Theorem 5.5, we then have

5 (F 0 )+⇠ max(0, ◆ 0 ? ) 5 (F 0 )+⇠ max(◆ 0 ,0)+⇠ ✓ 1 ⇣ ? ⌘(F 0 , ◆ 0 )+ ⌘ 2⇠ ◆  5 (F 0 )+⇠ max(◆ 0 ,0)+⌫ ⇠ ⌘(F 0 , ◆ 0 )+ ⌘ 2  5 (F 8 )+⇠ max(◆ 8 ,0) ⌘ 2
which gives the contradiction. Hence any solution of (% ⇠ ) is also a solution to problem (% ⌫,⇠ ).

Let now ( F, ◆) be a solution of (% ⌫,⇠ ) and let us show that it is actually a solution for % ⇠ . Let again (F 8 , ◆ 8 ) be an arbitrary solution of (% ⇠ ). We first note that, by the optimality result of ( Ḡ, ◆) for (% ⌫,⇠ ), we have:

5 ( F)+⇠ max(0, ◆)+⌫ ⌘( F ◆) |{z} 0  5 (F 8 )+⇠ max(0, ◆ 8 )+⌫ ⌘(F 8 , ◆ 8 ) | {z } =0 ,
which by positivity of the function ⌘ and feasibility for (% ⇠ ), i.e., ⌘(F 8 , ◆ 8 ) = 0 of (F 8 , ◆ 8 ) yields:

5 ( F)+⇠ max(0, ◆) 5 (F 8 )+⇠ max(0, ◆ 8 ).
It remains to show that ( F ◆) is a feasible point for (% ⇠ ). By the first point, (F 8 , ◆ 8 ) is both a solution of (% ⌫,⇠ ) and (% ⌫+⌫⇠

,⇠

). Hence, we have:

5 ( F)+⇠ max(0, ◆)+⌫⌘( F, ◆) 5 (F 8 )+⇠ max(0, ◆ 8 ) = 5 (F 8 )+⇠ max(0, ◆ 8 )+ ⌫ + ⌫ ⇠ 2 ⌘(F 8 , ◆ 8 )  5 ( F)+⇠ max(0, ◆)+ ⌫ + ⌫ ⇠ 2 ⌘( F, ◆)
But since ⌫>⌫ ⇠ we necessarily have: ⌘( F, ◆) = 0 which implies by the properties of the value function that ( F, ◆) is a feasible point for (% ⇠ ).

⇤

We note that the above result is a special case of theorem [175, Theorem 2.6] which is meant for generalized bilevel programs. Based on the terminology of [START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF], we have shown that % ⇠ satisfies the partial calmness property, as the value function ⌘ was shown to be a uniform parametric error bound.

Double penalization scheme

From the previous results, we get that solving the sequence of penalized problems gives approximations of the solution of the initial problem. We formalize this in the next proposition suited for our context of double penalization. The proof of this result follows standard arguments; see e.g. [START_REF] David | Linear and nonlinear programming[END_REF]Ch. 13.1]. Proposition 5.7. Assume that Problem (5.4) has a non-empty feasible set. Let (⇠ : ) : 0 Penalization of the easy constraint be an increasing sequence such that ⇠ : %1, and (⌫ : ) : 0 be taken such that ⌫ : > ⇠ : ⇣ ? with ⇣ ? as defined in (5.9). If, for all :, there exists a solution of (% ⌫ : ,⇠ : ) (denoted by (F : , ◆ : )), then any cluster point of the sequence (F : , ◆ : ) is an optimal solution of (5.1).

Proof. The fact that (F : , ◆ : ) is an optimal solution of (% ⌫ : ,⇠ : ) implies that 5 (F : )+⇠ : max(0, ◆ : )+⌫ : ⌘(F : , ◆ : )

(5. Using this last inequality with (5.14) gives:

5 (F : ) 5 (F :+1 )⇠ : max(◆ :+1 ,0) max(◆ : ,0)  0, and as a consequence the sequence { 5 (F : )} : 0 increases. Let (F 0 , ◆ 0 ) be an arbitrary feasible solution for (%). By definition of the sequence (F : , ◆ : ), for any : 2 N, we have:

5 (F : ) 5 (F : )+⇠ : max(◆ : ,0) 5 (F 0 )+⇠ : max(◆ 0 ,0) 5 (F 0 ). (5.15)
Therefore for any cluster point ( F, ◆) of the sequence {(F : , ◆ : )} : 0 , we have 5 ( F) 5 (F 0 ). In order to show that ( F, ◆) is a a solution of (5.4), it remains to show its feasibility. With the right hand side inequality of (5.15), we obtain

max(◆ : ,0) 5 (F 0 ) 5 (F : ) ⇠ :  5 (F 0 ) 5 (F 0 ) ⇠ : ! :!1 0,
so that we may deduce that, ◆  0. Moreover, continuity of ⌘ ensures that ⌘( Ḡ, ◆) = 0 which completes the proof.

⇤

In words, cluster points of a sequence of solutions obtained as ⇠ grows to +1 are feasible solutions of the initial chance-constrained problem. In practice though, we empirically observed that taking a fixed ⇠ is enough for reaching good approximations of the solution with increasing ⌫'s; see in particular the numerical experiments of Section 5.5. In the next section, we discuss further the practical implementation of the conceptual double penalization scheme.

Uniform bound at the limit

We show here that the uniform error bound derived in Section 5.3.1 vanishes at the limiting case of continuous distributions. We assume that, for a fixed G 2 R d , the random variable 6(F, ⇢) has a continuous density 5 F,⇢ : R ! R denoted by 5 F,⇢ : we have, for all 0  1,

P[0  6(F, ⇢)1] = π 1 0 5 F,⇢ (C) d C.
Proposition 5.8. Fix G 2 R 3 and denote by @ ? the ?-quantile of the distribution Weak sharpness vanishes with sample size followed by the random variable 6(F, ⇢). If 6(F, ⇢) has a continuous density, then the value function ◆ 7 ! ⌘(F, ◆) defined in (5.11) is differentiable at ◆ = @ ? (with ⌘ 0 (F, @ ? ) = 0).

Proof. We first note that the existence of a density ensures the continuity of the cumulative distribution function of 6(F, ⇢), which in turns implies P[6(F, ⇢)@ ? ] = ?. Let us now come back to expressions established in the proof of Theorem 5.5. From (5.12), we have, for ◆>@ ? ,

⌘(F, ◆) = (◆ @ ? ) 1 1 ? ✓ P[6(F, ⇢)@ ? ] ? + E  ◆ 6(F, ⇢) ◆ @ ? 1 @ ? <6(F,⇢)◆ ◆ = 1 1 ? E h (◆ 6(F, ⇢)) 1 @ ? <6(F,⇢)◆ i = 1 1 ? π ◆ @ ? (◆ C) 5 F,⇢ (C) d C = 1 1 ? ◆ π ◆ @ ? 5 F,⇢ (C) d C π ◆ @ ? C5 F,⇢ (C) d C ! .
By continuity of the above integrands, we can use the fundamental theorem of calculus to get that ⌘(F, •) admits a right derivative at ◆ = @ ? such that

⌘ 0 + (F, ◆) = lim ◆!@ ? ◆>@ ? ⌘(F, ◆) ⌘(F, @ ? ) ◆ @ ? = lim ◆!@ ? ◆>@ ? 1 1 ? © ≠ ´◆ Ø ◆ @ ? 5 F,⇢ (C) d C ◆ @ ? Ø ◆ @ ? C5 F,⇢ (C) d C ◆ @ ? ™ AE = lim ◆!@ ? ◆>@ ? 1 1 ?
◆ 5 F,⇢ (@ ? ) @ ? 5 F,⇢ (@ ? ) = 0.

For the case ◆<@ ? , we have from (5.13), together with P[6(F, ⇢) = @ ? ] = 0:

⌘(F, ◆) = (@ ? ◆) 1 1 ? ✓ E  1 (@ ? 6(F, ⇢)) @ ? ◆ 1 ◆<6(F,⇢)<@ ? + P[6(F, ⇢) = @ ? ] ◆ = 1 1 ? ✓ (◆ @ ? ) π @ ? ◆ 5 F,⇢ (C) d C π @ ? ◆ (@ ? C) 5 F,⇢ (C)) d C ◆ .
Using again to the fundamental theorem of calculus, we get that ⌘(F, •) admits a left derivative at ◆ = @ ? with:

⌘ 0 (F, ◆) = lim ◆!@ ? ◆<@ ? ⌘(F, ◆) ⌘(F, @ ? ) ◆ @ ? = lim ◆!@ ? ◆<@ ? 1 1 ? © ≠ ´(◆ @ ? ) Ø @ ? ◆ 5 F,⇢ (C) d C ◆ @ ? Ø @ ? ◆ (@ ? C) 5 F,⇢ (C) d C ◆ @ ? ™ AE ¨= 0.
We can conclude that ⌘(F, •) is differentiable at @ ? with zero as derivative. ⇤

5.4

In this section, we propose a practical version of the double penalization scheme for solving chance-constrained optimization problems. First, we present in Section 5.4.1 how to tackle the inner penalized problem (% ⌫,⇠ ) by leveraging its difference-of-convex (DC) structure. Then we quickly describe, in Section 5.4.2, the python toolbox that we release, implementing this bundle algorithm and efficient oracles within the double penalization method.

Solving penalized problems by a bundle algorithm

We discuss here an algorithm for solving (% ⌫,⇠ ) by revealing the DC structure of the objective function. Notice indeed that, introducing the two convex functions

! 1 (F, ◆) = 5 (F)+⌫⌧ ? (F, ◆)+⇠ max(◆,0) and ! 2 (F, ◆) = ⌫ min B2R ⌧ ? (F, B)
we can write (% ⌫,⇠ ) as the DC problem

min (F,◆)2C⇥R !(F, ◆) = ! 1 (F, ◆) ! 2 (F, ◆). (5.16)
We then propose to solve this problem by the bundle algorithm of [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF], which showed to be a method of choice for DC problems. This bundle algorithm interacts with first-order oracles for ! 1 and ! 2 ; in our situation, there exist computational procedures to compute subgradients of ! 1 and ! 2 from output of oracles of 5 and 6, as formalized in the next proposition. Note that at the price of more heavy expressions, we could derive the whole subdifferential. . Then, B ! 1 and B ! 2 2 R 3+1 defined as:

B ! 1 = © ≠ ´B 5 + ⌫ =(1 ?) = ' 82 >◆ B 6 8 ,1+ ⇠ 1 ◆>0 ⌫ #( >◆ ) =(1 ?) ™ AE B! 2 = © ≠ ´⌫ =(1 ?) © ≠
´' 82 >&? (6(F,⇢))

B 6 8 + ' 82 =&? (6(F,⇢)) B 6 8 ™ AE ¨,0 ™ AE ¨
are respectively subgradients of ! 1 and ! 2 at (F, ◆).

Notice now that the convergence result for the bundle algorithm [36, Th. 1] guarantees convergence towards a point D = ( Ḡ, ◆) satisfying

%! 2 ( D)\%! 1 ( D) < ;, (5.17)
which is a weak notion of criticality. Thus, we propose to furthermore replace ! 2 in (5.16) by a smooth approximation of it, denoted by e ! 2 . The reason is that the bundle method minimizing e ! = ! 1 e ! 2 then reaches a Clarkestationary point: indeed, (5.17) reads re ! 2 ( D)⇢%! 1 ( D), which gives 0 2 %!( D) = %! 1 ( D)+re ! 2 ( D), i.e., that D is Clarke-stationary (for the smoothed problem). To smooth ! 2 , we use the efficient smoothing procedure provided in the Section 4.2.2 of this thesis with the Euclidean smoothing. This yields a smooth approximation e

! 2 of the form, e ! 2 (F, ◆) = ⌫ sup 0@ 8  1 =(1 ?) @ 1 +•••+@ = =1 = ' 8=1 n @ 8 6(F, ⇢ 8 ) ⌧ 2 (@ 8 1 = ) 2 o (5.18)
We provide now a direct proof of the subgradient expressions of Proposition 5.9.

Oracles subgradient computations. Let (F, ◆)2C ⇥ R be fixed, and consider first the oracle of ! 1 . For 8 2{1, ..., =}, by successive applications of Theorems 4.1.1 and 4.4.2 from [63, Chap. D] to the functions

! (8) 1 : (F, ◆) 7 ! 1 =  5 (F)+⇠ max(◆,0)+⌫ ✓ ◆ + 1 1 ? max(6(F, ⇢ 8 ) ◆,0)
◆ we get for any 8 2{1, ..., =}

1 = B 5 + ⌫ =(1 ?) 1 6(F,⇢ 8 )>◆ B 6 2 % F ! 8 1 (F, ◆) ⇠ = 1 ◆>0 + ⌫ = ⌫ =(1 ?) 1 6(F,⇢ 8 )>◆ 2 % ◆ ! 8 1 (F, ◆). Since ! 1 = Õ = 8=1 ! (8)
1 , we thus have

© ≠ ´B 5 + ⌫ =(1 ?) ' 82 >◆ B 6 8 , ⇠ 1 ◆>0 +⌫ ⌫ #( >◆ ) =(1 ?) ™ AE ¨2 %! 1 (F, ◆)
For ! 2 we need first the whole subdifferential of the function ⌧ ? , which, using above mentioned properties, writes

%⌧ ? (F, ◆) = ( 1 1 ? = ' 8=1 B 6 8 = (1 6(F,⇢ 8 )>◆ + 8 1 6(F,⇢ 8 )=◆ ), 1 1 1 ?
= ' 8=1 1 = (1 6(F,⇢ 8 )>◆ + 8 1 6(F,⇢ 8 )=◆ ) ! , 8 2[0, 1], 88 2{1, ..., =}
)

.

By taking 8 = (for all 8 2{1, ..., =}) with the specific given in the statement, we can zero the second term in the above expression. TACO is an open-source python toolbox for solving chance-constrained optimization problems (5.1). The toolbox implements the penalization approach outlined in Section 5.3 together with the bundle method [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF] for the inner penalized subproblems. TACO routines rely on just-in-time compilation supported by Numba [START_REF] Siu Kwan Lam | Numba: A llvm-based python jit compiler[END_REF]. The routines are optimized to provide fast performance on reasonably large datasets. Documentation is available at https://yassine-laguel.github.io/taco.

We provide here basic information on TACO; for further information, we refer to the online documentation.

The python class Problem wraps up all information about the problem to be solved. This class possesses an attribute data which contains the values of ⇢ and is formatted as a numpy array in 64-bit float precision. The class also implements two methods giving first-order oracles: objective_func and objective_grad for the objective function 5 , and constraint_func and constraint_grad for the constraint function 6.

Let us take a simple quadratic problem in R 2 to illustrate the instantiation of Input format a problem. We consider

min F2R 2 kF 0 k 2 0 = [1.0, 2.0] > s.t. P[F > ⇢  0] 0.9,
with 1000 samples of ⇢ ⇠ N (0, 1).

The instance of Problem is in this case:

The Optimizer object

Given an instance of Problem and hyper-parameters provided by the user, the Finally we underline that TACO subroutines rely on just-in-time compilation supported by Numba, which consistently improves the running time. Further improvements can be achieved when the instance considered can be cast as a Numba jitclass. The parameter 'numba' in the input dictionnary of the associated Optimizer object should then be set to True.

On the bundle algorithm. We give now some information on our implementation of the bundle algorithm of [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF] to tackle the double penalized problem (% ⌫,⇠ ) written as a DC problem. We discuss the parameters used at various steps of the procedure. We refer to [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF] for more details.

• Overall run: The starting point, the maximum number of iterations as well as the precision tolerance for termination may be set by the user.

• Subproblems: Each iteration of the bundle algorithm requires solving a quadratic subproblem (see [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF]Equation (9)]), for which we use the solver cvxopt [START_REF] Vandenberghe | The cvxopt linear and quadratic cone program solvers[END_REF] by simplicity.

• Stabilization center: Whenever the solution of a subproblem satisfies a sufficient decrease in terms a function value, it is considered as a new stability center. The condition to qualify sufficient decrease is given in [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF]Equation (12)]. It involves a constant which may be tuned by the user.

• Proximal parameters: The initial value of the proximal parameter involved in quadratic subproblems can be set by the user. The user can also specify upper and lower acceptance bounds for it. After each iteration, the proxparameter is updated: it is increased by a constant factor in case of serious step, and decreased otherwise. Both factors can be tuned by the user.

• Bundle information: The bundle of cutting-planes is augmented after each null step with new linearization, and emptied after each serious step. We fix a maximum size for the bundle: above this parameter, the bundle is emptied and proximal parameter is restarted to a specified restarting value. When the bundle is emptied, we have the chance of a specific improvement: if the stability center is feasible in the chance-constraint, we replace the coordinate playing the role of ◆ by the ?-quantile of 6(F, ⇢), thus decrease the objective function.

• Termination Criteria: We use a simple stopping criteria: we stop when the Euclidean distance between the current iterate and the current stability center falls below a certain threshold specified by the user.

5.5

We illustrate our double penalisation approach implemented in the toolbox TACO on two problems: a 2-dimensional quadratic problem with a non-convex chance constraint (in Section 5.5.1), and a family of problems with explicit solutions (in Section 5.5.2). These proof-of-concept experiments are not meant to be extensive but to show that our approach is viable. These experiments are reproducible: the experimental framework is available on the toolbox's website.

Visualization of convergence on a 2D problem

We consider a two-dimensional toy quadratic problem in order to track the

Instance of eventually convex problem

convergence of the iterates on the sublevel sets. We take [START_REF] Laguel | On the convexity of level-sets of probability functions[END_REF]Ex. 4.1] which considers an instance of problem (5.1) with

5 (F) = 1 2 (F 0) > &(F 0) with 0 = 2.
2.

!

, & = 5.5 4.5 For this example, [START_REF] Laguel | On the convexity of level-sets of probability functions[END_REF] shows that the chance constraint is convex for sufficiently large probability levels, but here we take a low probability level ? = 0.008 to have a non-convex chance-constraint. We can see this on Figure 5.2, plotting the level sets of the objective function and the constraint function: the chance-constrained region for ? = 0.008 is delimited by a black dashed line; the optimal value of this problem is located at the star. Results. We plot on the sublevel sets of Figure 5.

the path (in deep blue) taken

Visualization of the convergence by the sequence of iterates starting from the point [0.5, 1.5] moving towards the solution. We observe that the sequence of iterates, after an exploration of the functions landscape, gets rapidly close to the optimal solution. At the end of the convergence, we also see a zigzagging behaviour around the frontier of the chance constraint.This can be explained by the penalization term which is activated asymptotically whenever the sequence violates of the chance constraint.

Experiments on a family of problems

We consider the family of 3-dimensional norm problems of [67, section 5.1]. For

Problems in larger dimension

a given dimension 3, the problem writes as an instance of (5.1) with

5 (F) = kG k 1 and 6(F, /) = max 82{1,...,10} 3 ' 9=1 / 2 8,9 F 2 9 100 (5.20)
and ⇢ is random matrix of dimensions 10 ⇥ 3 statisfying for all 8, 9, ⇢ 8,9 ⇠ N (0, 1). The interest of this family of problems is that they have explicit solutions: for given 3, the optimal value is

5 8 = 10 3 r ( 1) " 2 3
(?

1 10 )
where

" 2 3
is " 2 cumulative distribution with 3 degrees of freedom. We consider four instances of this problems with dimension 3 from 2 to 200 and the safety probability threshold ? set to 0.8. We consider the case of the rich information on uncertainty: ⇢ is sampled 10000 times. In this case, a direct approach consisting in solving the standard mixed-integer quadratic reformulations (see e.g. [3]) with efficient MINLP solvers (we used Juniper [START_REF] Kröger | Juniper: An open-source nonlinear branch-and-bound solver in Julia[END_REF]) does not provide reasonable solutions; see basic information in forthcoming Section 5.5.3. The starting penalization parameter ⇠, constant for the 4 instances, is set to ⇠ = 10.0. We tuned the second penalization parameter ⌫ along problems: we observed that ⌫ = {1.75, 1.5, 1.5, 2.0} give good performances for the considered problems. The starting proximal parameters is fixed to 60.0 with lower and upper acceptance bounds set to 10 4 and 10 5 respectively. Increasing and decreasing factors for the proximal parameter are fixed to 1.01 and 0.99. The classification rule parameter is set to 10 4 . The maximal size of the information bundle is set to 300.

Results. Figure 5.3 plots the relative suboptimality

Analysis of the convergence

( 5 (F : ) 5 8 )/| 5 8 |
along iterations. The green (resp. red) regions represent iterates that, respectively, satisfy (resp. do not satisfy) the chance constraint.

In the four instances, we take a first iterate well inside the feasible region. We observe an initial decrease of the objective function down to optimal value. Then the chance constraint starts to be violated only when this threshold is reached, and the last part of convergence deals with local improvement of precision and feasibility.

Table 5.1 reports the final suboptimality and satisfaction of the probabilistic constraint. The probability constraint is evaluated for 100 sampled points from of the total # = 10000 points. We give the resulting probability; the standard deviation is 0.004 for the four instances. We observe that the algorithm reaches an accuracy of order of 10 3 . Regarding satisfaction of the constraint P[6(F, ⇢)0] 0.8, it is achieved to a 10 4 precision for 3 = 2 but it slightly degrades as the dimension grows.

Dimension Suboptimality P[6(F, ⇢)0]

Limitations of MINLP approach

We finish this chapter with a remark on Mixed Integer Non-Linear Programming

Standard MINLP reformulation

(MINLP) approaches. Mixed-integer reformulation approaches (see e.g. [3]) are often considered as the state-of-the-art to solve chance-constrained optimization problems by sample average approximation. Applying directly such a reformulation to Problem (5.20) in Section 5.5.2 leads to the equivalent mixed integer quadratic program: where " is a large "big-M" constant. In our setting, such formulation involves 10 ⇥ # = 100000 quadratic constraint involving binary variables. We were not able to solve the resulting mixed-integer problem in reasonable times using the MINLP solver Juniper [START_REF] Kröger | Juniper: An open-source nonlinear branch-and-bound solver in Julia[END_REF] (that is based on Ipopt and JuMP). This shows that a direct application of reformulation techniques combined with reliable software failed on this problem -in contrast with our approach.

min F2R 3 , I2{0,1} # 3 ' 8=1 F 8 s.t.

5.6

In this chapter, we uncovered a new formulation of chance-constrained problems based on the variational formulation of the superquantile. This reformulation takes the form of a bilevel program with convex upper-level and lower-level problems. We proposed a double penalization procedure to solve this bilevel program. We analyzed and exploited the weak sharpness property of the superquantile to show that exact penalization may be achieved for the hard constraint of this problem. The objective of the penalized problem being a Difference of Convex (DC) function, we proposed to address it with a recent proximal bundle method. In order to ensure better convergence properties of the method, we proposed to smooth the superquantile term involved in the DC objective. We made available an open-source python toolbox with fast computational procedures to solve chance-constrained problems with this approach together with numerical illustrations showing the interest of the approach.

the -FL algorithm and show how to implement it in a way that is compatible with basic federated learning ingredients. In Section 6.2, we start with a formal description of the vanilla federated Outline framework and introduce the concept of conformity to capture its potential statistical heterogeneity. Section 6.3 describes -FL, the new framework we propose to better handle non-conforming users together with a practical privacycompliant algorithm. In Section 6.4, we provide a convergence analysis of our algorithm with a convergence rate in the strongly convex setting. Section 6.5 presents experimental results, comparing our proposed approach to existing ones, on benchmark datasets for federated learning.

6.2

The federated learning paradigm, calls for optimization methods that are compliant with the specific constraints aforementioned in Section 2.2.2.W e begin this Section with a brief presentation of FedAvg, the standard baseline in federated learning. We introduce then in Section 6.2.2 the concept of conformity to describe the statistical heterogeneity of a given federated framework. where the weight : of training device : is chosen and ⌫>0 is a regularization parameter. As mentioned in Section 2.2.2, each loss : :

Vanilla federated learning and FedAvg

F 7 ! E ⇢⇠⇢ : ⇥ 5 (F, ⇢)
⇤ evaluates the performance of the model F on the device :, hosting the distribution @ : . We assume that Õ # :=1 : = 1 w.l.o.g. We call this objective the vanilla FL objective.

The standard training algorithm to solve (6.1) is FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. We illustrate it FedAvg addresses the communication bottleneck by using >1 local computation steps as opposed to = 1 local steps in minibatch stochastic gradient descent (SGD). It also performs the averaging step (c) securely to enhance data privacy. However, the vanilla FL objective places a limit on how well statistical heterogeneity can be addressed. By minimizing the average training loss, the resulting model F can sacrifice performance on "difficult" devices in order to perform well on average. In other words, it is not guaranteed to perform well on individual test devices, whose distribution ? might be quite different from the average training distribution Õ # :=1 : @ : . Our goal in this work is to design an objective function, different from the vanilla FL objective (6.1) to better handle statistical heterogeneity, and design a federated optimization algorithm similar to FedAvg.

Problem formulation: conformity and heterogeneity

In this work, we consider test devices whose distribution ? can be written as a mixture ? := Õ # :=1 : @ : of the training distribution @ : of the devices with weights 2 # 1 . Here, # 1 denotes the probability simplex in R # . The test distribution ? is different from the average training distribution ? = Õ # :=1 : @ : if the mixture weights are different from the training weights = ( 1 , ..., # ).

We now define the conformity of a mixture ? to the training distribution ? , as a measure of the degree of similarity between ? and ? . Definition 6.1. The conformity conf(? )2( 0, 1] of a mixture ? with weights Conformity is defined as min :2~1,# : / : . The conformity of a device refers to the conformity of its data distribution.

A mixture distribution ? with conf(? ) =  must satisfy :  : / for each :. Since Õ : : = 1, we also get that : max{0, : (1 )}/2 . Assuming that the training devices are a representative sample of the pop-Interpretation ulation of devices, every device's distribution can be well-approximated by a mixture ? for some 2 # 1 . The conformity of a device is a scalar summary of how close it is to the trend, modeled by the aggregated distribution ? = Õ : : @ : . A test device with conformity  ⇡ 1 closely conforms to the trend. For such device, a model trained on ? is expected to have a high predictive power. In contrast, a test device with  ⇡ 0 can have a distribution that vastly differ from ? , and the predictive power of a model trained on ? can be poor.

There is a trade-off between fitting to the trend and supporting nonconforming test devices. The conformity  presents a natural way to encapsulate this tradeoff in a scalar parameter. That is, given a conformity  2( 0, 1),w e choose to only support test distributions ? with conf(? ) .

-

In this section, we define the -FL framework in Section 6.3.1, and propose an algorithm to optimize in the federated setting in Section 6.3.2. Finally, we illustrate our approach on a toy example in Section 6.3.3.

The framework

The -FL framework aims to supply each test device with a model appropriate to its conformity. Given a discretization { 1 , ...,  A } of (0, 1], -FL maintains A models, one for each conformity level  9 . The local data is not allowed to leave a device due to privacy restrictions; hence, the conformity of a test device cannot be measured. Instead, we allow each test device to tune their conformity. See the schematic in Figure 6.1 for an illustration.

To train a model for a conformity level , we aim to do well on all distributions -FL's objective ? with conf(? ) . Thus, we propose to solve:

min F2R 3   (F) := max 2P  (F; ? )+ ⌫ 2 kFk 2 ,
where,

P  := 2 # 1 : conf(? )  . (6.2)
In contrast, the vanilla FL objective optimizes (F; ? ), which is defined on the basis of the training distribution ? . We observe that -FL is designed to be robust on all test devices with conformity greater than .

Noting that for any 2 # 1 , we have by definition

Connection to the Superquantile ) for ? drawn uniformly from the set of all mixtures of @ 1 , @ 2 , @ 3 with conformity at least  = 2/3.

6.4

The principal result of this section is Theorem 6.1 which establishes a convergence rate in the strongly convex setting. The main difficulties raised concern the extension of the recent local SGD framework [START_REF] Dieuleveut | Communication Trade-offs for Local-SGD with Large Step Size[END_REF][START_REF] Haddadpour | Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization[END_REF][START_REF] Koloskova | A unified theory of decentralized SGD with changing topology and local updates[END_REF][START_REF] Li | On the Convergence of FedAvg on Non-IID Data[END_REF][START_REF] Stich | Local SGD Converges Fast and Communicates Little[END_REF] to the dynamic reweighting that the superquantile induces in line (3) of our Algorithm 5. Alternatively, this analysis can be seen as an extension of the stochastic gradient descent method [START_REF] Levy | Large-scale methods for distributionally robust optimization[END_REF] for superquantiles to federated frameworks.

Assumptions and main result

First, we assume without loss of generality that the weight of each training device is : = 1/# 3 . For each device : 2[#], the objective : is (a) ⌫-bounded, i.e., 0  : (F)⌫ for all F 2 R 3 , (b) ⌧-Lipschitz, i.e., | : (F)

: (F 0 )|  ⌧ kF F 0 k for all F, F 0 2 R 3 , and, (c) !-smooth, i.e., : is continuously differentiable and its gradient r : is !-Lipschitz.

Theorem 6.1. Suppose each function : is convex and that the three above assumptions

Convergence result for -FL hold. Fix a time horizon ) and consider the sequence (F (C) ) ) C=0 of iterates produced by the -FL algorithm with smoothing. Define ! 0 = ⌫ + ! + ⌧ 2 p ) and assume that the learning rate ✏ satisfies

✏  min ⇢ 1 4 ! 0 , p ⌫ 18 (! + ⌫) p ! 0 .
Define the averaged iterate

F (C) = Õ C 8=0 8 F (8) Õ C 8=0 8
, where

8 = ✓ 1 ✏⌫ 2 ◆ (1+8)
.

Then, letting F 8 = arg min F2R 3 ⇡  (F), we have the bound

E h  (F ()) )  (F 8 ) i  4 exp( ✏ ⌫)) F (0) F 8 2 + 2 T , 3
This assumption is made to avoid technicalities with random sums Õ :2( : . We can extend the convergence analysis to the case of unequal : 's by performing a standard reduction of replacing : (F) with 0 : (F) := # : : (F). The proofs hold in this case if ⌫, ⌧, ! are multiplied by a factor of # max : : . where 2 is a universal constant and

T = ⌧ 2 ! 2 ✏ 2 ( 1) ⌫ + ⌫ p < + ⌧ 2 ✏ < + log < p ) .
The first term in T is called client drift [START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF][START_REF] Li | On the Convergence of FedAvg on Non-IID Data[END_REF]. It decays as $(✏ 2 ) and vanishes if = 1. The second and third terms stem from the bias and variance from sampling devices in each round, and vanish if < = #. See Proposition 3.13 for further details. The final term appears due to considering smoothed objective ⇡  for the minimization of the nonsmooth  . These terms can be balanced by taking ✏ = $(1/ p 2 )) to get $(1/ p )) convergence up to the bias term. Finally, the bias and variance due to partial participation encourage having < large enough for the bound to be meaningful.

Proof Synopsis.

• In Section 6.4.2, we first recall and adapt the bias and variance of the stochastic estimator of the superquantile from Section 3.4 together with a few basic convex inequalities.

• In Section 6.4.3, we show how to bound the gradient dissimilarity within the robust selection of devices performed in Lines 2-3 of Algorithm 5 and the client drift caused by the local steps.

• In Section 6.4.4, we provide a descent lemma for one complete round of communication and gather all the results to finish the proof.

Preliminary results

We first recall a few standard inequalities:

• Rob Peter to pay Paul: For any G, H 2 R 3 and >0 we have:

G + H 2 ( 1
+ ) kGk 2 + ✓ 1 + 1 ◆ H 2 .
(6.4)

• Pythagoras theorem: For any R 3 -valued random vectorsuch that

E k-k 2 < 1, E kDk 2 = E kD E [D]k 2 + kE [D]k 2 . (6.5)
• Strong convexity: Let : R d ! R be ⇠-strongly convex. Then for any G, H 2 R d , we have:

⌦ r (G), G H ↵ (G) (H)+ ⇠ 2 G H 2 .
(6.6)

• Smoothness: Let : R d ! R be !-smooth and let 8 be the minimum value of (assuming it exists). Then for any G 2 R d , we have:

kr (G)k 2  2! (G) 8 . (6.7)
We handle the nonsmoothness of the objective due to the superquantile with We simply write ⇡( ) when ( = [#]. We define the smooth counterpart to (6.2) as [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF][START_REF] Devolder | First-order methods of smooth convex optimization with inexact oracle[END_REF][START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF]]

⇡  (F) = max 2P  ( # ' :=1 : : (F) ⇡⇡( ) ) + ⌫ 2 kFk 2 , (6.8)
where ⇡>0 is a fixed smoothing parameter. We have that | ⇡  (F)  (F)|  2⇡ log #. We modify Line 3 of Algorithm 5 as In view of the assumptions on the losses : , the following result falls from standard [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF]Theorem 4

(C) = arg max 2P ,(
! 0 = ! + ⌫ + ⌧ 2 ⇡ .

Adversarial gradient dissimilarity and client drift

In this section, we show how to bound the client drift that is accumulated during the local steps of our Algorithm 5. We first analyze the client dissimilarity among the training clients in our specific risk-averse setting. We derive then Bounding gradient dissimilarity. Bounding of the variance of gradient estimators is a key assumption in the analysis of stochastic gradients methods (see e.g. the textbook [START_REF] Bottou | Optimization Methods for Large-Scale Machine Learning[END_REF]). In the centralized setting, when considering a stochastic objective E ⇢ [ 5 (F, ⇢)], it is standard to assume for a given estimator

6 F of r F E ⇥ 5 (F, ⇢
⇤ that there exists some constants " 1 , " 2 > 0 such that for all

F 2 R d , E h 6 F 2 i  " 1 or E h 6 F 2 i  " 1 + " 2 r F E ⇥ 5 (F, ⇢ ⇤ 2
In the federated setting, the use of a subset ( ⇢[#] of devices in each round

Bounded on gradient dissimilarity assumption in federated learning

induces noise on the estimation of the average gradient over the whole network.

r ⇡ ,( (F (C) ) 2  4 ⌧ 2 + r ⇡ ,( (F (C) ) 2 .
Thus, taking an expectation over ( ⇠ * < gives E " '

:2( (C) : r ˜ 9 (F (C) ) 2 F C #  4 ⌧ 2 + E (⇠* <  r ⇡ ,( (F (C) ) 2 .
By Pythagoras theorem (6.5), we get, E " '

:2( (C) : r ˜ : (F (C) ) 2 F C #  4 ⌧ 2 + E  r ⇡ ,( (F (C) ) r ⇡  (F (C) ) 2 F C + r ⇡  (F (C) ) 2 .
(6.10)

Finally, substituting the variance bound from Lemma 3.13 into (6.10) yields the stated result.

⇤

Bounding the Client Drift. During federated learning, each device takes multiple local steps. This causes the resulting update to be a biased estimator of a descent direction for the global objective. This phenomenon has been referred to as "client drift" [START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF][START_REF] Li | On the Convergence of FedAvg on Non-IID Data[END_REF]. Current proof techniques rely on treating this as a "noise" term which is to be controlled. In the context of this work, the reweighting by (C) requires us to adapt this typical definition of client drift to our setting. We thus define the client drift 3

3 (C)  2 ( 1)✏ 2 4 2 ✓✓ 4 + 8 < ◆ ⌧ 2 + ⇡  (F (C) ) 2 ◆
and,

3 (C)  2 ( 1)✏ 2 4 2 ✓✓ 4 + 8 < ◆ ⌧ 2 + 2! 0 ⇣ ⇡  (F (C) ) ⇡  (F 8 ) ⌘ ◆ . Proof. If = 1,
F (C) 2  ✓ 1 + 1 1 ◆ F (C) :,9 1
F (C) 2 + ✏ 2 r ˜ : (F (C) :, 9 1 ) 2 .
Using(6.4) and the smoothness of the local losses, this gives:

F (C) :,9 F (C) 2  ✓ 1 + 1 1 ◆ F (C) :,9 1
F (C) 2 + 2 ✏ 2 ✓ r ˜ : (F (C) :,9 1 ) r ˜ : (F (C) ) 2 + r ˜ : (F (C) ) 2 ◆  ✓ 1 + 1 1 ◆ F (C) :,9 1
F (C) 2 + 2 ✏ 2 (! + ⌫) 2 F (C) :,9 1
F (C) 2 + 2 ✏ 2 r ˜ : (F (C) ) 2 .
Hence, for ✏  1 4 (!+⌫) , we get:

F (C) :,9 F (C) 2  ✓ 1 + 1 1 + 2 ✏ 2 (! + ⌫) 2 ◆ F (C) :,9 1
F (C) 2 + 2 ✏ 2 r ˜ : (F (C) ) 2  ✓ 1 + 2 1 ◆ F (C) :,9 1
F (C) 2 + 2 ✏ 2 r ˜ : (F (C) ) 2 .
For the first term, we invoke (! + ⌫)-smoothness of ˜ : and take the expectation to get 2 (! + ⌫) 2 3 (C) . For the second term, we use (6.5) followed by the variance bound of Proposition 3.13 to get:

E  r ⇡ ,( (F (C) ) 2 F C = E 2 6 6 6 6 4
'

:2( (C) : r ˜ : (F (C) ) r ⇡  (F (C) ) 2 F C 3 7 7 7 7 5 + r ⇡  (F (C) ) 2  8⌧ 2 < + r ⇡  (F (C) ) 2 .
This gives

✏
 2✏ 2 (! + ⌫) 2 3 (C) + 16 2 ✏ 2 ⌧ 2 < + 2 2 ✏ 2 r ⇡  (F (C) ) 2 .
The stated result follows by smoothness (6.7). ⇤

Effect of one round

The crux for proving Theorem 6.1 is the following statement. global models generated by Algorithm 5. For any C 0, we have:

⇡  (F (C) ) ⇡  (F 8 ) 1 ✏ ✓ 1 ⌫✏ 2 ◆ F (C) F 8 2 1 ✏ F (C+1) F 8 2 + 16 ⌧ 2 ✏ < + 9 (! + ⌫) 2 ⌫ 3 (C) ,
where 3 (C) denotes the client drift, defined in (6.11).

Proof. We denote

E C [•] := E[•|F C ].
We expand the update 6.12 to get

E C kF (C+1) F 8 k 2 = F (C) F 8 2 2✏E C
2✏ ⇣ ⇡  (F (C) ) ⇡  (F 8 ) ⌘ + ⌫✏ 2 F (C) F 8 2 8✏ (! + ⌫) 2 ⌫ 3 (C) ,
where we use the definition of 3 (C) from (6.11). We bound ⌫ using Proposition 6.5.

Putting these together, we get,

E C F (C+1) F 8 2  ✓ 1 ⌫✏ 2 ◆ F (C) F 8 2 (2✏ 4✏ 2 2 ! 0 )( ⇡  (F (C) ) ⇡  (F 8 )) + 16 2 ⌧ 2 ✏ 2 < + 2 ✓ ✏ 2 (! + ⌫) 2 + 4✏ (! + ⌫) 2 ⌫ ◆ 3 (C) .
With ✏ ( 4 ! 0 ) 1 we have 2✏ 4✏ 2 2 ! 0 ✏ . Likewise, the same condition on ✏ also implies 2(✏ (! + ⌫) 2 + 4(! + ⌫) 2 /( ⌫))  9 (! + ⌫) 2 /( ⌫). Rearranging terms completes the proof.

⇤

We have now all the ingredients to establish the proof of Theorem 6.1.

Time for a conclusion

Proof of Theorem 6.1. Plugging in the client drift bound of Proposition 6.4 into the bound of Proposition 6.6 and rearranging, we get

1 18! 0 (! + ⌫) 2 2 ✏ 2 4 2 ⌫ ! ⇣ ⇡  (F (C) ) ⇡  (F 8 ) ⌘  1 ✏ ✓ 1 ⌫✏ 2 ◆ F (C) F 8 2 1 ✏ E C F (C+1) F 8 2 + 16 ⌧ 2 ✏ < + 9⌧ 2 (! + ⌫) 2 2 ✏ 2 4 2 ⌫ ✓ 4 + 8 < ◆ . Since 364 2  18 2 for ✏  p ⌫(18 (! + ⌫) p ! 0 ) 1 , we have 18! 0 (! + ⌫) 2 2 ✏ 2 4 2 /⌫  1 2 which implies: ⇡  (F (C) ) ⇡  (F 8 ) 2 ✏ ✓ 1 ⌫✏ 2 ◆ F (C) F 8 2 2 ✏ E C F (C+1) F 8 2 + 32 ⌧ 2 ✏ < + 18⌧ 2 (! + ⌫) 2 2 ✏ 2 4 2 ⌫ ✓ 4 + 8 < ◆ | {z } =:T 1 .
Next, we use convexity to get

E h ⇡  (F ()) ) ⇡  (F 8 ) i  1 Õ ) C=0 ⇣ 1 ⌫✏ 2 ⌘ (1+C) ) ' C=0 ✓ 1 ⌫✏ 2 ◆ (1+C) E h ⇡  (F (C) ) ⇡  (F 8 ) i  2 Õ ) C=0 ⇣ 1 ⌫✏ 2 ⌘ C E h F (C) F 8 2 i ⇣ 1 ⌫✏ 2 ⌘ (1+C) E h F (C+1) F 8 2 i ✏ Õ ) C=0 ⇣ 1 ⌫✏ 2 ⌘ (1+C) + T 1 ,
so that telescoping the sum yields

E h ⇡  (F ()) ) ⇡  (F 8 ) i  2 F (0) F 8 2 ✏ Õ ) C=0 ⇣ 1 ⌫✏ 2 ⌘ (1+C) + T 1 .
Now, we can lower bound the denominator with

) ' C=0 ✓ 1 ⌫✏ 2 ◆ (1+C) 1 ✏ ⌫ 4 )✏ ⌫ , to get the bound E h ⇡  (F ()) ) ⇡  (F 8 ) i  2⌫4 )✏ ⌫ F (0) F 8 2 + T 1 . (6.13)
It remains to translate the results on ⇡  into  . For the left hand side, we use the bias bound of Property 3.13. For the right hand side, we use the ⌫-strong convexity of  and Property 3.13 we have:

F (0) F 8 2  2 F (0) F 8 2 + 2 F 8 F 8 2  2 F (0) F 8 2 + 4 ⌫  (F 8 )  (F 8 )  2 F (0) F 8 2 + 4 ⌫ ⇣  (F 8 ) ⇡  (F 8 )+ ⇡  (F 8 ) ⇡  (F 8 )+ ⇡  (F 8 )  (F 8 ) ⌘  2 F (0) F 8 2 + 4 ⌫ ✓ 2⌫ p < + 4⇡ log < ◆ since ⇡  (F 8 ) ⇡  (F 8 )0.
Plugging this into (6.13) completes the proof. ⇤ 6.5

In this section, we describe in details the experimental setup and the results.

Here is its outline:

• Section 6.5.1 describes the datasets and tasks.

• Section 6.5.2 gives a detailed description of the hyperparameters used and the evaluation methodology.

• Section 6.5.3 details the experimental results we obtain for our algorithm -FL in comparison to a broad selection of baselines.

The code and the scripts to reproduce results are made publicly available at https://github.com/krishnap25/simplicial-fl.

Datasets and tasks

We conduct our experiments on two datasets from computer vision and natural language processing, described in detail below. These datasets contain a natural, non-iid split of data which is reflective of data heterogeneity encountered in federated learning. In these two examples, each device has a finite number of datapoints. Thus, we let its probability distribution @ : to be the empirical distribution over the available examples, and the weight : to be proportional to the number of datapoints available on the device. The data was preprocessed using LEAF [START_REF] Caldas | LEAF: A benchmark for federated settings[END_REF].

-.

Dataset. EMNIST [START_REF] Cohen | EMNIST: extending MNIST to handwritten letters[END_REF] is a character recognition dataset. This dataset contains images of handwritten digits or letters, labeled with their identification (a-z,A-Z, 0-9). The images are grey-scaled pictures of 28 ⇥ 28 = 784 pixels.

Train and Test Devices. Each image is also annotated with the "writer" of the image, i.e., the human subject who hand-wrote the digit/letter during the data collection process. A device consists in all the images supplied by the same writer. From this set of devices, we discard all devices containing less than 100 images. The remaining devices were partitioned into two groups -1730 training and 1730 testing devices. For each experiment we subsampled 865 training and 865 testing devices for computational tractability.

Model. We consider the following models for this task.

• Linear Model: We use a linear softmax regression model. In this case each : is convex. We train parameters F 2 R 62⇥784 . Given an input image G 2 R 784 , the score of each class 2 2 ~1, 62 is the dot product hF 2 , Gi.

The probability ? 2 assigned to each class is then computed as a softmax: ? 2 = exp hF 2 , Gi/ Õ 2 0 exp hF 2 0 , Gi. The prediction for a given image is then the class with the highest probability.

• ConvNet: We also consider a convolutional neural network. Its architecture satisfies the following scheme:

Input 784 ! Conv 2D filter = 32 kernel = 5 ⇥ 5 ! ReLU ! Max Pool kernel = 2 ⇥ 2 stride = 2 ! Conv 2D filter = 64 kernel = 5 ⇥ 5 ! ReLU ! Max Pool kernel = 2 ⇥ 2 stride = 2 ! F.C. units = 62
! score

In other words, it contains two convolutional layers with max-pooling and one fully connected layer (F.C) which outputs a vector in R 62 . The outputs of the ConvNet are scores with respect to each class. They are also used with a softmax operation to compute probabilities.

The loss used to train both models is the multinomial logistic loss !(?, H) = log ? H , where ? denotes the vector of probabilities computed by the model, and ? H denotes its H th component. In the convex case we add a quadratic regularization term of the form (⌫/2)kFk 2 2 .

.

Dataset. Sent140 [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF] is a text dataset of 1,600,498 tweets produced by 660,120 Twitter accounts. Each tweet is represented by a character string with emojis. Each tweet is labeled with a binary sentiment reaction (i.e., positive or negative), which is inferred based on the emojis in the original tweet.

Train and Test Devices. Each device represents a twitter account and contains only tweets published by this account. From this set of devices we discarded all devices containing less that 50 tweets, and split the 877 remaining devices into a train set and a test set of sizes 438 and 439 respectively. This split was held fixed for all experiments. Each word in the tweet is encoded by its 50-dimensional GloVe embedding [START_REF] Pennington | GloVe: Global Vectors for Word Representation[END_REF].

Model. We consider the following models.

• Linear Model: We consider a ; 2 -regularized linear logistic regression model where the parameter vector F is of dimension 50. In this case, each : is convex. We summarize each tweet by the average of the GloVe embeddings of the words of the tweet.

• RNN: The nonconvex model is a Long Short Term Memory (LSTM) model [START_REF] Hochreiter | Long Short-Term Memory[END_REF] built on the GloVe embeddings of the words of the tweet. The hidden dimension of the LSTM is same as the embedding dimension, i.e., 50. We refer to it as "RNN".

The loss function is the binary logistic loss. In the convex case, we also add a quadratic regularization term of the form (⌫/2)kFk 2 because the latter experiments were run using on a GPU, as we describe in the forthcoming paragraph on the hardware.

Learning rate scheme. We now describe the learning rate ✏ C used during LocalUpdate. For the linear model we used a constant fixed learning rate ✏ C ⌘ ✏ 0 , while for the neural network models, we used a step decay scheme ✏ C = ✏ 0 2 bC/C 0 c where ✏ 0 and 0 < 2  1 are tuned. We tuned these parameters only for the baseline FedAvg and used the same learning rate for the other baselines and -FL at all values of .

For the neural network models, we fixed C 0 so that the learning rate was decayed once or twice during the fixed time horizon ). In particular, we used C 0 = 400 for EMNIST ConvNet (where ) = 1000), and C 0 = 200 for Sent140 RNN (where ) = 600). We tuned 2 from the set {2 3 ,2 2 ,2 1 ,1}, while the choice of the range of ✏ 0 depended on the dataset-model pair. The tuning criterion we used was the mean of the loss distribution over the training devices (with device : weighted by : ) at the end of the time horizon. That is, we chose the ✏ 0 , 2 which gave the best terminal training loss.

Tuning of the regularization parameter. The regularization parameter ⌫ for linear models was tuned with cross validation from the set {10 : : : 2 {3, ••• ,8}}. This was performed as described below.

For each dataset, we held out half the training devices as validation devices. Then, for different values of the regularization parameter, we trained a model with the (smaller subset of) training devices and evaluate its performance on the validation devices. We selected the value of the regularization parameter as the one which gave the smallest 90 th percentile of the misclassification error on the validation devices.

Baseline Parameters. We tune the proximal parameter of FedProx with cross validation. The procedure we followed is identical to the procedure we described above for the regularization parameter ⌫. The set of parameters tested is {10 9 , 9 2{ 0, ...,3}}. We adopt the same strategy for @-FFL, where the set of parameters @ tested is {10 9 , 9 2{ 3, ••• ,1}}, and Tilted-ERM, where the set of temperatures C tested is {0.1, 0.5, 1., 5., 10., 50., 100., 200}}.

. Evaluation metrics. We record the loss of each training device and the misclassification error of each testing device, as measured on its local data.

The evaluation metrics noted in Section 6.5.3 are the following : the weighted mean of the loss distribution over the training devices, the (unweighted) mean misclassification error over the testing devices, the weighted ?-percentile of the loss over the training device and the (unweighted) ?-percentile of the misclassification error over the testing devices for values of ? among {20%, 50%, 60%, 80%, 90%, 95%}. The weight : used for training device : was set proportional to the number of datapoints on the device. Hardware. We run each experiment as a simulation as a single process. The linear models were trained on m5.8xlarge AWS instances, each with an Intel Xeon Platinum 8000 series processor with 128 GB of memory running at most 3.1 GHz. The neural network experiments were trained on workstation with an Intel i9 processor with 128 GB of memory at 1.2 GHz, and two Nvidia Titan Xp GPUs. The Sent140 RNN experiments were run on a CPU while the other neural network experiments were run using GPUs. Software Packages. Our implementation is based on NumPy using the python language. In the neural network experiments, we use PyTorch to implement the LocalUpdate procedure, i.e., the model itself and the automatic differentiation routines provided by PyTorch to make SGD updates.

Randomness. Since several sampling routines appear in the procedures such as the selection of devices or the local stochastic gradient, we carry our experiments with five different seeds and plot the average metric value over these seeds. Each simulation is run on a single process. Where appropriate, we report one standard deviation from the mean.

Experimental results

We now present the experimental results of the paper.

• We present different metrics on the distribution of test misclassification error over the devices, comparing -FL to baselines.

• We study the convergence of Algorithm 5 for -FL over the course of the optimization, and compare it with FedAvg.

• We plot the histograms of the distribution of losses over train devices as well as the test misclassification errors over test devices at the end of the training process.

• We present in the form of scatter plots the training loss and test misclassification error across devices achieved at the end of training, versus the number of local data points on the device.

• We present the number of devices selected at each communication round for -FL (after device filtering).

• We finally present the impact of the number of local epochs on the convergence of -FL.

Comparison to Baselines. In Tables 6 FL objective on EMNIST-ConvNet. Among the heterogeneity aware objectives, -FL achieves 1.8% improvement over the next best objective, which is Tilted-ERM. We note that @-FFL marginally outperforms -FL on Sent140-Linear, but the difference 0.05% is much smaller than the standard deviation across runs.

For EMNIST-ConvNet, -FL with  2{ 0.5, 0.8} is better in 90 th percentile -FL is competitive at multiple values of  error than all other methods we compare to, and -FL with  = 0.1 is tied with Tilted-ERM, the next best method. We also empirically confirm that -FL interpolates between FedAvg ( ! 1) and AFL ( ! 0). We observe that -FL with  = 0.1 is unstable for Sent140-RNN. This is -FL works best for larger values of conformity levels consistent with our discussion following Theorem 6.1, where we advocate for values < larger than 1/. Indeed, this can be explained by -FL's sparse re-weighting, which only gives non-zero weights to < = 5 devices on average in each round.

Perhaps surprisingly, -FL actually gets the best test error performance on -FL is yet competitive in terms of average error EMNIST-ConvNet and Sent140-Linear. This suggests that the average test distribution is shifted relative to the average training distribution ? . In the other cases, we find that the reduction in mean error is small relative to the gains in the 90 th percentile error compared to Vanilla FL methods.

Specifically, AFL which aims to minimize the worst error among all devices, Minimizing superquantile loss over all devices performs better than minimizing worst error over all devices as well as other objectives which approximate it ( -FL with  ! 0, @-FFL with @ !1, Tilted-ERM with ⇡ ! 0) tend to achieve poor performance. We find that AFL achieves the highest error both in terms of 90 th percentile and the mean.

-FL offers a more nuanced and more effective approach via the constraint set conf(? )  than the straight pessimistic approach minimizing the worst error among all devices. Performance Across Iterations. We present our results only for the EMNIST dataset. For the other datasets, we point the reader to our papers [START_REF] Laguel | Device heterogeneity in federated learning: A superquantile approach[END_REF][START_REF] Laguel | Superquantile-based learning: a direct approach using gradient-based optimization[END_REF]. We group plots by models and datasets. The G axis of the plots below represents the number of communication rounds along the simulation. The H-axis represents either the training loss or the testing accuracy (either the mean or some percentile). Overall, -FL exhibits better convergence properties for the high percentiles of the distribution of test misclassification errors over the devices: see for instance the 99 C⌘ , 95 C⌘ and 90 C⌘ percentiles in figure 6.5. This comes with the price of lower performance than the baseline FedAvg on low percentiles of the distribution.

Histograms of Loss and Test Misclassification Error over Devices.

Here, we plot in Figure 6.6 the histograms of the loss distribution over training devices and in Figure 6.7 the histograms of the misclassification error distribution over testing devices for the dataset EMNIST (for other datasets, see [START_REF] Laguel | Device heterogeneity in federated learning: A superquantile approach[END_REF]). We report the losses and errors obtained at the end of the training process. Each metric is averaged per device over 5 runs of the random seed. We note that -FL tends to exhibit thinner upper tails at at multiple values of  and a lower variance of the distribution in most of the cases. This is also confirmed by the figures in Tables 6.1 to 6.4. This shows the benefit of using -FL over vanilla FedAvg. Performance compared to local data size. Next, we plot the loss on training devices versus the amount of local data on the device and the misclassification error on the test devices versus the amount of local data on the device. See Figures 6.8 and 6.9 for EMNIST and Figure 6.10 for Sent140.

Observe firstly that improvement over the worst cases is achieved regardless of the local data size of the devices. Indeed, the device filtering step operates a sorting of the loss of the devices which does not prevent small devices from being selected. In contrary, FedAvg, by averaging with respect to the weights of the devices is likely to put more the accent on the devices with larger local data size. Secondly, -FL appears to reduce the variance of the losses on the train devices. Lastly, note that amongst test devices with a small number of data points (e.g., < 200 for EMNIST or < 100 for Sent140), -FL reduces the variance of the misclassification error. Both effects are more pronounced on the neural network models. Next, we plot the number of devices selected per round (after device filtering, if applicable). The shaded area denotes the maximum and minimum over 5 random runs. We see from Figure 6.11 that device-filtering is stable in the number of devices filtered out. Effect of number of local epochs. We present in Figure 6.12, the effect of the number of epochs in FedAvg, on the overall convergence of -FL. We observe for EMNIST ConvNet that a large number of local epochs leads to poor convergence. A similar behaviour was observed in [109, Figure 3] for FedAvg. On Sent140 linear model, we see a minor improvement for a larger number of local epochs.

Performing secure aggregation

In this final section, we show how -FL can address privacy concerns in Section 6.5.4.

Recall that Algorithm 5 as stated, requires each selected client device to send its loss to the server for the client filtering step (see line 3). We now present a way to perform this step without any reduction in privacy from directly sending client losses to the server. As noted earlier, line 3 consists in the computation of the superquantile of the sequence of losses : (F (C) ). We saw in the Section 3.3 of this thesis that such computation boils down to computing the (1 )-quantile of theses losses. We show now how to implement this quantile computation using secure aggregation.

Setup. Suppose we wish to find the ?-quantile of G 1 , ••• , G < 2 R with respective weights 1 , ••• , < > 0. It is known [79, e.g.,] that @ ? is a ?-quantile iff it it ? is often referred to as the "pinball" loss minimizes ? : R ! R defined as ? (@) := < ' :=1

: ! ? (G : @) , where, ! ? (⌧) :=

> > < > > :

?⌧ , if ⌧ 0,

(1 ?)⌧ , if ⌧<0.

Algorithm. Recall that secure aggregation can find a weighted mean of vectors (and hence, scalars) distributed across < devices without revealing each device's vector to other devices or the server. We now show how to compute a quantile as an iterative weighted mean, making it amenable to implementation via secure aggregation. The underlying algorithm, based on the principle of majorization-minimization was used, e.g., in [START_REF] David | Quantile Regression via an MM Algorithm[END_REF]. (6.14). The first row denotes the error in the quantile estimate @ C of (6.14), while the second wrong row gives the error in filtering, i.e., difference in the number G : @ C of devices filtered out @ C vs. the same number G : @ ⇤ for @ ⇤ . exact quantile. Moreover, it can find an estimate with zero filtering errors in 10 50 updates.

6.6

We presented the -FL framework that operates with heterogeneous client devices while still guaranteeing a minimal level of predictive performance to each individual device. We modeled the similarity between client data distributions using the conformity, which is a scalar summary of how closely a client device conforms to the population. -FL relies on a superquantile-based objective, parameterized by the conformity, to minimize the tail statistics of the prediction errors on the client data distributions. We presented a federated optimization algorithm compatible with secure aggregation, which interleaves device reweighting steps with local stochastic gradient methods. We derived finite time convergence guarantees in the convex setting. Experimental results on federated learning benchmarks demonstrate superior performances of -FL over state-of-the-art baselines on the upper quantiles of the error on test devices, with particular improvements on data-poor devices, while being competitive on the mean error.

CONCLUSION AND PERSPECTIVES

We considered two related topics, in optimization with (super)quantiles. The Conclusion first topic is the minimization of superquantile-based objectives for machine learning in both centralized and federated settings. The second topic is the solving of non-convex problems with quantile constraints, for which we proposed a bilevel reformulation. Our work leverages the strong interplay between convex analysis and risk aversion to derive new optimization procedures in practical data-driven contexts.

In Chapter 4, we highlighted the benefits of using the superquantile in machine learning. Our software offers the possibility to seamlessly optimize a learning loss with the superquantile in place of the expectation, for classical learning tasks. We provided various numerical experiments that illustrate two features of superquantile-based learning: its impact on worst-case scenarios and its robustness to adversarial distributional shifts. Our procedures are based on a thorough analysis of the smoothing techniques applied to the superquantile. We also proposed an extension of such smoothing to law-invariant coherent comonotone risk measures to provide decision makers with a broader set of risk modeling tools without computational overhead.

In Chapter 5, we considered solving chance-constrained problems. We leveraged the dual properties of the superquantile to propose a bilevel reformulation with convex upper and lower levels. In this second line of work (and contrary to the previous contribution) we exploited the nonsmoothness of the superquantile to derive a (semi-)exact penalisation procedure for our bilevel reformulation. Our numerical experiments show that this approach can scale on datasets which are difficulet to solve by direct (MINLP) approaches.

Finally, in Chapter 6, we proposed a new federated learning framework to address statistical heterogeneity among users. We provided a theoretical analysis that puts into perspective the properties of stochastic estimators of the superquantile and their impact on the convergence of local gradient schemes. We produced extensive numerical experiences showing the benefits of a superquantile approach over other state of the art methods, for handling of non-conforming users. Each project presented above is just one step ahead and calls for further Further Perspectives developments. They indeed open to some fundamental problems as well as practical incremental developments. Here are a few interesting research questions that triggered my attention.

How to fix the safety parameter ? in superquantile-based learning ? Knowing how to set the parameter p in the definition of the superquantile is a question that I have often seen myself asked when presenting my work. First I want to say that this is essentially a modeling problem. In federated learning, for example, setting a parameter p amounts to focus training only on the (1 ?)-proportion of worst-performing users. Should we focus only on the worst 5% ? the worst 10% ? Should this be decided based on the proportion of each user's community in the network? One could thus argue that the choice of p is mainly a political issue. For now, state-of-the-art works run a cross-validation on a grid of values of ?, typically between 0.8 and 0.99 and select the value giving the best accuracy on the validation set. However, with the rise of quantitative methods to measure the fairness of a given prediction models, it may be interesting to propose automatic tuning procedures for tuning ?. This is the main question I would like to tackle over the next months.

Can superquantiles help to model risk-aversion beyond law-invariant comonotone risk measures ? Actually, this question has already been partially answered in [START_REF] Blanchet | Quantifying distributional model risk via optimal transport[END_REF], where the authors propose a duality result which links Wasserstein ambiguity on the probability of misclassification for a given model to the superquantile of a computable associated quantity. Based on the dual properties of the superquantiles which were exposed in Chapter 3, I believe this could help to develop tractable approaches for a broad class of adversarial problems based on Wasserstein ambiguity.

Can we derive better convergence guarantees for chance-constrained problems ?

The bilevel reformulation of chance-constrained programs I proposed in this thesis paves the way for several future directions. First the characterization of optimality of the solutions of our algorithm may be further investigated. For now, we are able only to build a sequence of critical points of the penalized problems that we derived based on our (semi)-exact penalization procedures. Whether or not cluster points of this sequence exhibit some notions of criticality for the initial chance-constrained program remains an intriguing question to solve. Second, the procedure for the partial update of the penalization parameters of such problems remains hard in practice since no prior information (beyond the lower bound of Theorem 5.5) is available. In other words, our algorithm is primal only. If we managed to turn it into a primal-dual procedure with an automatic update of the penalization (i.e. dual) parameters, we could hope for a better convergence in practice. Finally, the derivation of (local) convergence rate for chance-constrained programs is a direction I'd like to think of in medium term.

How to extend federated learning to decentralized frameworks ? The challenges raised by federated learning (see Section 2.2.2) have given rise to a number of works in the distributed optimization community. I would be interested in addressing these challenges in a fully decentralized setting, i.e. in the absence of a central server. On top of the existing theoretical challenges of federated optimization, the establishment of a consensus among the nodes of the network raises additional questions which may be tackled with a unified analysis. This would open the door to more resilient frameworks for a number of applications where communication possibilities between the nodes are scarce and cannot be handled by a central entity (e.g., for wireless sensor networks, IoT-enabled edge devices, etc.). Comparative diagram between the baseline FedAvg and our algorithm -FL which handles heterogenous devices.

Steps 1, 2 and 3 are identical and hold as fundamental components of any practical federated framework: broadcast of server models to a random subselection of devices -running of local stochastic gradient updates -secure aggregation of the selected models. Only step 1 0 is specific to -FL and can be interpreted as an additional filtering step among selected device to choose which device will run the local updates. Mathematically, this filtering steps interpret as a composition with the superquantile -see more in Chapter 6. 9 Figure 2 The superquantile is obtained by averaging the quantiles greater than the ?-quantile (red section on graph on the right). 33 Reshaping of the histogram of testing losses for superquantile regression models (in red) as ? grows. We observe a shift to the left of the 90 th quantile of losses, at the price of degrading the average value. 68 Left: Positions in R 2 of the means ⇠ 1 , ⇠ 2 , ⇠ 3 of Gaussians @ 1 , @ 2 , @ 3 resp., the vanilla federated learning model F 1 , and the -FL model F 2/3 at conformity  = 2/3. Center: Comparison of the loss (• ; ? ) for each possible mixture ? with weights = ( 1 , 2 , 3 ). Right: Histogram of losses (•; ? ) for ? drawn uniformly from the set of all mixtures of @ 1 , @ 2 , @ 3 with conformity at least  = 2/3. 97 Effect of the number of local epochs. 116 Figure 6. [START_REF] Berrada | Smooth loss functions for deep top-k classification[END_REF] Convergence of Secure (1 )-Quantile using Iteration (6.14). The first row denotes the error in the quantile estimate @ C of (6.14), while the second wrong row gives the error in filtering, i.e., difference in the number G : @ C of devices filtered out @ C vs. the same number G : @ ⇤ for @ ⇤ . 118

LIST OF TABLES Metrics for the test misclassification error for Sent140 (Linear Model). 111 Table 6. 4 Metrics for the test misclassification error for Sent140 (RNN Model). 112 Table 6.5

Comparison of communication cost of (i) secure aggregation for quantile of < scalars with = rounds of (6. The monospaced text (hyperlinks, etc.) was typeset in Bera Mono, originally developed by Bitstream, Inc. as "Bitstream Vera" (with Type 1 PostScript fonts by Malte Rosenau and Ulrich Dirr).

The typographic style of this dissertation was inspired by the authoritative genius of Bringhurst's Elements of Typographic Style, ported to L A T E X by André Miede, the original designer of the classicthesis template. Any unsightly deviations from these works should be attributed solely to the author's (not always successful) efforts to conform to the awkward A4 paper size.

Risk-averse Optimization: Models, Algorithms, and Applications in Machine Learning

© Yassine Laguel 2021

Yassine Laguel

3 23 3. 1 1 . 1 23 3. 1 . 2 1 . 3 25 3. 1 . 4 formula 27 3. 2 28 3. 3 32 3. 3 . 1 34 3. 4

 32311123121325142722833231344 Risk-averse optimization through the lens of duality theory 23 3.Duality in probability spaces Convex risk measures and Fenchel-Moreau's theorem 24 3.Supporting distributionally robust optimization Subdifferential Coherency of a class of support functions Superquantiles and the Kusuoka representation The superquantile risk measure 32 3.3.2 The Kusuoka representation Minimization by first-order methods 1 INTRODUCTION

F2R d max I2⇤ 5 (

 5 F, I).

Figure 1 . 1 :

 11 Figure 1.1: For a continuous random variable -, drawing of ?-quantile & ? (-), and?-superquantile ( ? (-), defined as an expectation.

Figure 1 . 2 :

 12 Figure 1.2: Illustration of a dual formulation of the superquantile as the support function of a particular ambiguity set (in red).

Figure 1 . 3 :

 13 Figure 1.3: Trajectory of the iterates (in blue) of our bundle algorithm on a 2-dimensional chance-constrained problem investigated in Chapter 5.

Figure 1 . 4 :

 14 Figure 1.4: Comparative diagram between the baseline FedAvg and our algorithm -FL which handles heterogenous devices. Steps 1, 2 and 3 are identical and hold as fundamental components of any practical federated framework: broadcast of server models to a random subselection of devices -running of local stochastic gradient updates -secure aggregation of the selected models.Only step 1 0 is specific to -FL and can be interpreted as an additional filtering step among selected device to choose which device will run the local updates. Mathematically, this filtering steps interpret as a composition with the superquantile -see more in Chapter 6.

Figure 2 . 2 :

 22 Figure 2.2: Statistical Heterogeneity is a key feature of federated learning where clients with heterogeneous distributions collaborate to learn a single model.

Figure 2 . 3 :

 23 Figure 2.3: Comparison of the three regressions for the toy federated learning setting of Example 2.2. We want commensurate performances among users, which means, graphically, a curve at the same distance from the data-points of the conforming users (in blue) and the non-conforming user (red).

Figure 3 . 1 :

 31 Figure 3.1: The Fenchel conjugate and the bi-conjugate of a real function 5 . The Fenchel conjugate is always convex. The Fenchel biconjugate 5 ⇤⇤ satisfies epi 5 ⇤⇤ = conv epi 5 .

⇤ Proposition 3 . 5 .

 35 Let ⇢ be a function defined as in(3.8). Then, the following assertions Translation invariance and inclusion in the simplex are equivalent: (i) The function ⇢ is translation invariant: ⇢(G + ⌫4) =⇢ (G)+⌫ for any ⌫ 2 R, where 4 = (1, ...,1) >

Proposition 3 . 8 .

 38 Let ⇢ be defined as in(3.8) and law-invariant. Then, the two Comonotonicity and generation of the support following assertions are equivalent: (i) The support function ⇢ is comonotone.

Figure 3 . 2 :

 32 Figure 3.2: Illustration of the integral expression of the superquantile. Cumulative distribution function (on the left) and quantile function (on the right) are each other's inverse. The superquantile is obtained by averaging the quantiles greater than the ?-quantile (red section on graph on the right).

⇤.

  On top of expression(3.10), the superquantile offers two other useful formulations dual of each other:• The superquantile is the support function of the intersection of the simplexDistributionally robust representationwith a box (see Figure3.3).

Figure 3 . 3 :

 33 Figure 3.3: Illustration of the dual expression of the superquantile (recall of Figure 1.2 from Section 1.1). G 7 ! ( ? (G) is the support function of the red polytope. The red point at the center represents the uniform distribution.

Proposition 3 . 12 .

 312 Let * B denote the uniform distribution over all subsets of [=] of Bias of e 5 size B. Assume that loss 5 is bounded: 5 (F, ⇢ 8 )⌫, 8F 2 R d , 88 2 ~1, =. Then, for any F 2 R d , we have

Proposition 3 . 13 .

 313 Let * B denote the uniform distribution over all subsets of [=] of Bias and variance of r e 5 ⇡ size B. Assume that loss 5 is Lipschitz with respect to F: 5

Figure 3 . 4 :

 34 Figure 3.4: Kataoka's example of eventually convex chance constraint. Here ⇢ follows a 2-dimensional Gaussian distribution with parameters ⇠ = (1, 1) and ⌃= 2 .Even in the simple Gaussian case, chance constraints are not garanteed to be convex for all values of ?.

Proposition 4 . 1 .

 41 Consider the superquantile-based function (4.2) with ! continuously Explicit subdifferential of superquantile-based functions

  A special conjugate functionof the sum of ⇡3 and the indicator of the segment ⇥ 0, 1/=(1 ?)

Lemma 4 . 3 .

 43 (4.10) where 3 0 + (0)2[ 1, +1) and 3 0 (1/(=(1 ?))) 2 [ 1, +1) are respectively the right-derivative of 3 at 0 and the left-derivative of 3 at 1/(=(1 ?)). Note finally that 6 ⇡ 0 is a non-decreasing function. The dual problem of (4.6) can be expressed as the (smooth convex) Duality one-dimensional problem:

Example 4 . 1 .

 41 We suggest to smooth the superquantile with the Euclidean Euclidean smoothing distance to the uniform distribution

Example 4 . 2 ..

 42 Corollary 4.4 to get an efficiently implemented expression of the gradient. Note that the obtained expression of r 5 ⇡ (F) involves only the gradients r! 8 (F) for largest values of ! 8 (F) (comparable to the expression of %!(F) in Proposition 4.1). The overall procedure is laid down in Algorithm 1 ⇤ We use here the Kullback-Lieber divergence to the uniform which consists in taking 3(C) = C log(C) in (4.8). Elementary calculus then gives

2 3 4 for 1  :  = do 5 ifFigure 4 . 1 :

 2341541 Figure 4.1: Impact of the smoothing parameter ⇡ on the relative weighing between datapoints. Left: empirical cumulative distribution of = = 500 points sampled from a standard Gaussian distribution. Right: distribution of weights, i.e., the optimal solution of (4.6) for ? = 0.5, with respect to sorted data points (i.e., value at abscissa C is the weight attached to the C-quantile). Different colours correspond to different values of ⇡.

Figure 4 . 2 :

 42 Figure 4.2: Impact of the smoothing parameter ⇡ solving a superquantile logistic regression on a classical dataset (Australian Credit dataset).

). 1 1

 1 Proof. A direct change of variable in (4.9) gives 6 ⇡ (G 8 ◆) = 1 =(1 ?) < ⇡ (G 8 ◆). The proof is direct from the expression of the dual problem (4.11) and the no-gap result stated in Lemma 4.3.⇤Next, we show an equivalence between the smoothing by infimal convolu-Smoothing by convolution tion (4.22), and by convolution, as considered in[START_REF] Chen | A class of smoothing functions for nonlinear and mixed complementarity problems[END_REF][START_REF] Pablo | An approximation scheme for a class of risk-averse stochastic equilibrium problems[END_REF]. Given a continuous probability density ⌘ : R ! R + , (such that Ø |B| ⌘(B)dB is finite) the smoothing by convolution of the function max{•,0} with smoothing parameter ⇡>0 is defined by2

2 .

 2 R, so it suffices to show the non-decrease of (6 0 ⇡,: ) 0:= 1 . Let us fix : 2 ~0, = For all B  ⇡: =(= :) , we have by (4.31) 6 ⇡,: (B) = 6 ⇡,: (B). If B ⇡(:+1) =(= : 1) , we also have 6 ⇡,: (B) = 1 = : < 1 = : 1 = 6 ⇡,:+1 (B). Finally, if B 2[ ⇡: =(= :) ,

8 #3

 8 It is well defined since(4.31) ensures  0 : (G (=) + ⇡ = ) = 1 Õ = 8=1 6 0 ⇡,: (G (8) G (=) ⇡ = ) = 1 >(◆) ensures that G (=) + ⇡ = >◆by non-decrease of  0 : .One can get efficiently as follows the quantities  0 : (⌫),  00+ : (⌫), 8 + (⌫, :) and 8 (⌫, :). First observe that since ⌫>◆implies 8 (⌫, :) 8 (◆, :) and 8 + (⌫, :) 8 + (◆, :), we have: 8 (⌫, :) = 8 (◆, :)+ = ' 8=8 (◆,:) 1 ⌫=G (8) + ⇡ = and 8 + (⌫, :) = 8 + (◆, definition of ⌫, the function  00+

Figure 4 . 3 : 1 Since 8

 4318 Figure 4.3: Illustration of the roots of the dual functions  : . Once the G 8 's are sorted, a single pass over them suffices to compute the whole sequence (◆ 8 : ) 0:= 1

. 41 ) 4 . 4 .⇤) 0kn 1 Theorem 4 . 10 .

 41441410 Remark We observe that the computation of 8 (◆, : + 1) is immediate andSecond Complexity remarkthe computation of 8 + (◆, : + 1) requires a single pass on the points G (8) such that 8 2 ~8+ (◆, :), 8 + (◆, : + 1). Similarly, the computation of  0 :+1 (◆) requires a single pass on the points G (8) such that 8 2 ~8+ (◆, :), 8 + (◆, : + 1). Finally, still in view of (4.38), one may compute  00+ : (⌫) in constant time.Getting the whole sequence (( † k in quasi-linear time. Previous observations offer a guideline for the computation of the sequence (◆ 8 : ) 0:= 1 . We explain it here, we detail it Algorithm 2, and we illustrate it in Figure 4.3. Assuming the data points (G (8) ) 18= are sorted, Algorithm 2 computes Getting (◆ 8 : ) 0:= 1 in O(= log =) operations the sequence of dual solutions (◆ 8

The sets : do not intersect Algorithm 2 :

 2 Computation of the sequence (◆ 8 : ) 0:= 1 in O(= log =) Require : (G (8) ) 18= : sorted sequence of coordinates of G Initialize : ◆ := G (0) 1, : :

27 if : < = then 28 Compute 8 1 Proof. Let 8 2 8 :which implies 8 < 8 :

 2728812888 (◆, :), 8 + (◆, :),  0 : (◆) and  00+ : (◆) according to (4.39), (4.40) and (4.41); The sequence (◆ 8 : ) 0:= ~1, = be fixed. If 8 2 : , then since the sequence (◆ ) 0:= 1 is nondecreasing (in view of Lemma 4.9) and since the sequence (⇡:/(=(= :))) 0:= 1 increases, we have G min :+1 . Reciprocally, using the same properties, if 8 2 and we cannot have 8 > max : .

Figure 4 . 4 :

 44 Figure 4.4: A comparison between batch/mini-batch algorithms in SPQR on a superquantile logistic regression problem with MNIST. Left: comparison of the runs of SGD with different batch sizes. Right: best SGD vs. batch quasi-Newton.

Figure 4 . 5 :

 45 Figure 4.5: Impact of the smoothing parameter ⇡ on the results obtained by the quasi-Newton algorithm solving a superquantile logistic regression on the Australian Credit dataset. Medium values are preferable: small values compromise convergence and large values give solutions close to the standard ERM.

Figure 4 . 6 :

 46 Figure 4.6: Reshaping of the histogram of testing losses for superquantile regression models (in red) as ? grows. We observe a shift to the left of the 90 th quantile of losses, at the price of degrading the average value.

Figure 4 . 7 :

 47 Figure 4.7: Reshaping of histograms of test losses (top) and test accuracies (bottom) over all class imbalances (for a classification task with logistic regression and the splice dataset).

Figure 5 . 1 :Proposition 5 . 4 .Example 5 . 1 .

 515451 Figure 5.1: Illustration of Example 5.1. A linear problem with a vanishing weak sharpness modulus.

14 ) 5

 145 (F :+1 )+⇠ : max(0, ◆ :+1 )+⌫ : ⌘(F :+1 , ◆ :+1 )Similarly for (F :+1 , ◆ :+1 ), we get 5 (F :+1 )+⇠ :+1 max(0, ◆ :+1 )+⌫ :+1 ⌘(F :+1 , ◆ :+1 )  5 (F : )+⇠ :+1 max(0, ◆ : )+⌫ :+1 ⌘(F : , ◆ : ).By Proposition 5.6, ◆ : (resp. ◆ :+1 ) is feasible for (% ⇠ : ) (resp. (% ⇠ :+1 )); in other words, we have ⌘(F : , ◆ : ) = ⌘(F :+1 , ◆ :+1 ) = 0. Hence summing up these two inequalities yields max(◆ : ,0) max(◆ :+1 ,0).

Proposition 5 . 9 .

 59 Let (F, ◆)2C ⇥ R be fixed. Let B 5 be a subgradient of f at F and Oracle derivations B 6 1 , ..., B 6 = be respective subgradients of 6(•, ⇢ 1 ), ..., 6(•, ⇢ = ) at F. For a given C 2 R, denote by >C the set of indices such that 6(F, ⇢ 8 ) > C and by =C the set of indices such that 6(F, ⇢ 8 ) = C. Let finally = P[6(F,⇢)& ? (6(F,⇢)] ? #( =&? (6(F,⇢)) )

Now since ! 2 (⇤ 5 . 4 . 2

 2542 F, ◆) = ⌫ min B2R ⌧ ? (F, B) with & ? (6(F, ⇢)) 2 arg min B2R ⌧ ? (F, B), we apply Corollary 4.5.3 of [63, Chap. D] to obtain a subgradient of ! 2 : TACO: A python toolbox for chance-constrained problems

  import numpy as np class Problem: def __init__(self, dim=2, sample_size=1000): self.data = np.random.normal(size=(sample_size, dim), dtype=np.float64) self.a = np.array([1.0, 2.0], dtypte=np.float64) def objective_fun(self,\variablemodel): return np.dot(\variablemodel-self.a,x-self.a) def objective_grad(self, \variablemodel): return \variablemodel def constraint_func(self, \variablemodel, z): return np.dot(\variablemodel,z) def constraint_grad(self, \variablemodel, z) return z problem = Problem() TACO handles the optimization process with a python class named Optimizer.

4.5 5. 5 ! 6 (

 56 F, I) = I > ,(F)I + F > I with ,(F)

Figure 5 . 2 :

 52 Figure 5.2: Trajectory of the iterates (in blue) on the plot of the level sets of the chanceconstraint and the objective for the 2d problem with data (5.19).

Figure 5 . 3 :

 53 Figure 5.3: Convergence of our penalization algorithm on four norm problems (5.20) with 3 = 2, 10.50, 200.

Table 5 . 1 :

 51 Final suboptimality and feasibility for (5.20) (where ? = 0.8).

2 : 100 8=1I 8 

 21008 "I 8 , 88 2 ~1, # , 89 2 ~1, 10 # ' ?#, F 0.

Federated learning consists of

  heterogeneous client devices which collaboratively train a machine learning model under the orchestration of a central server. The model is then deployed on all devices, including those not seen during training.Analogous to the classical expectation-based objective function in empiricalVanilla federated learning objective risk minimization approach, the standard objective in federated learning is to minimize the average loss on the training devices min

FedAvg in Figure 6 . 2 . 1 -F

 621 Each round of the algorithm consists in following steps: The server samples a set ( of < devices from ~1, # and broadcasts the current model F (C) to these devices.2-Starting from F (C):,0 = F (C) , each device : 2 ( makes local gradient or stochastic gradient descent steps 1 with a learning rate ✏:

3 -F. 1 1 F 2 F 3 F 4 F0InFigure 6 . 1 :

 31123461 Figure 6.1: Schematic summary of the -FL framework. Left: The server maintains multiple models F  9 , one for each level of conformity  9 . Middle: During training, selected devices participate in training each model F  9 . Individual updates are securely aggregated to update the server model. Right: Each test user is allowed to select their level of conformity , and are served the corresponding model F  .

Figure 6 . 2 :

 62 Figure 6.2: Comparative diagram between the baseline FedAvg and our algorithm -FL (recall of Figure 1.4). Both algorithms consist of the following steps (note difference in step 1'). Step 1: Server selects < client devices and broadcasts the model to each selected device. Step 1' ( -FL only): Each selected device computes the loss (a scalar) incurred by the model on its local data and sends it to the server. Based on these losses, the server computes a threshold loss. It only keeps devices whose losses are larger than this threshold, and un-selects the other devices. Step 2: Each selected device computes an update to the server model based on its local data. Step 3: Updates from selected devices are securely aggregated to update the server model.

Figure 6 . 3 :

 63 Figure 6.3: Illustration of -FL with a uniform mixture of Gaussians. Left: Positions in R 2 of the means ⇠ 1 , ⇠ 2 , ⇠ 3 of Gaussians @ 1 , @ 2 , @ 3 resp., the vanilla federated learning model F 1 , and the -FL model F 2/3 at conformity  = 2/3. Center: Comparison of the loss (• ; ? ) for each possible mixture ? with weights = ( 1 , 2 , 3 ). Right: Histogram of losses (•; ?) for ? drawn uniformly from the set of all mixtures of @ 1 , @ 2 , @ 3 with conformity at least  = 2/3.

Smoothing

  the smoothing procedure from Section 4.2.2. More precisely, we consider the entropic smoothing from Example 4.2 on the sequence of losses over the set ( ⇢[#] of selected devices:

. 8 ::

 8 As pointed out in the Section 4.2.2 of this thesis, for any ( ⇢[ #] of size <, the partial superquantile is differentiable at F with :r ⇡ ,( (F) = ' r ˜ : (F) (6.9)where ˜ : , introduced to lighten the notations, denotes ˜ : (F) = : (F)+ (⌫/2) kFk 2 , and 8 denotes the solution to the maximization problem ˜ : (F) ⇡⇡ ( ( ).

2 (

 2 there is nothing to prove as both sides of the inequality are 0.W e assume now that >1. Let us first fix ( ⇢[#] of size |(| = <. For any :

Proposition 6 . 6 .

 66 Consider the setting of Theorem 6.1. Let (F (C) ) C 0 the sequence of Descent Lemma

4 F'

 4 (C) F 8 2 4 (! + ⌫) 2 ⌫

Evaluation times.

  We evaluate the model during training process for once every ; communication rounds. The value of ; used was ; = 50 for EMNIST linear model, ; = 10 for EMNIST ConvNet, ; = 20 for Sent140 linear model and ; = 25 for Sent140 RNN.

Figure 6 . 4 :

 64 Figure 6.4: Performance across iterations of EMNIST linear model.

Figure 6 . 5 :

 65 Figure 6.5: Performance across iterations of EMNIST ConvNet model.

Figure 6 . 6 :

 66 Figure 6.6: Histogram of loss distribution over training devices from EMNIST. Top:linear -Bottom:ConNet).

Figure 6 . 7 :

 67 Figure 6.7: Histogram of misclassification error distribution over testing devices for EMNIST Top:linear -Bottom:ConNet).

Figure 6 . 8 :

 68 Figure 6.8: For FedAvg and -FL with values of  in {0.1, 0.5, 0.8}, scatter plot of (left) loss on training device vs. amount of local data, and (right) misclassification error on testing device vs. amount of local data for EMNIST (Linear Model)

Figure 6 . 9 :Figure 6 . 10 :

 69610 Figure 6.9: For FedAvg and -FL with values of  in {0.1, 0.5, 0.8}, scatter plot of (left) loss on training device vs. amount of local data, and (right) misclassification error on testing device vs. amount of local data for EMNIST (ConvNet Model)

Figure 6 . 11 :

 611 Figure 6.11: Number of devices selected per round (after device filtering) for the EMNIST dataset. The shaded region denotes the maximum and minimum over 5 random runs.

Figure 6 . 12 :

 612 Figure 6.12: Effect of the number of local epochs.

( b )

 b Sent140 Linear Model.

Figure 6 . 13 :

 613 Figure 6.13: Convergence of Secure (1 )-Quantile using Iteration(6.14). The first row denotes the error in the quantile estimate @ C of (6.14), while the second wrong row gives the error in filtering, i.e., difference in the number G : @ C of devices filtered out @ C vs. the same number G : @ ⇤ for @ ⇤ .

Figure 1 . 1 For 3 Figure 1 . 2 6 Figure 1 . 3 7 Figure 1 . 4

 11312613714 Figure 1.1

Figure 3 . 1 25 Figure 3 . 2

 312532 The Fenchel conjugate and the bi-conjugate of a real function 5 . The Fenchel conjugate is always convex. The Fenchel biconjugate 5 ⇤⇤ satisfies epi 5 ⇤⇤ = conv epi 5 . Illustration of the integral expression of the superquantile. Cumulative distribution function (on the left) and quantile function (on the right) are each other's inverse.

Figure 3 . 3

 33 Figure 3.3 Illustration of the dual expression of the superquantile (recall of Figure 1.2 from Section 1.1). G 7 ! ( ? (G) is the support function of the red polytope. The red point at the center represents the uniform distribution. 34 Figure 3.4 Kataoka's example of eventually convex chance constraint. Here ⇢ follows a 2-dimensional Gaussian distribution with parameters ⇠ = (1, 1) and ⌃= 2 . Even in the simple Gaussian case, chance constraints are not garanteed to be convex for all values of ?. 39

Figure 4 . 1 50 Figure 4 . 3 57 Figure 4 . 4 A 66 Figure 4 . 5 67 Figure 4 . 6

 415043574466456746 Figure 4.1 Impact of the smoothing parameter ⇡ on the relative weighing between data points. Left: empirical cumulative distribution of = = 500 points sampled from a standard Gaussian distribution. Right: distribution of weights, i.e., the optimal solution of (4.6) for ? = 0.5, with respect to sorted data points (i.e., value at abscissa C is the weight attached to the C-quantile). Different colours correspond to different values of ⇡. 48 Figure 4.2 Impact of the smoothing parameter ⇡ solving a superquantile logistic regression on a classical dataset (Australian Credit dataset). 50 Figure 4.3 Illustration of the roots of the dual functions  : . Once the G 8 's are sorted, a single pass over them suffices to compute the whole sequence (◆ 8 : ) 0:= 1 57 Figure 4.4 A comparison between batch/mini-batch algorithms in SPQR on a superquantile logistic regression problem with MNIST. Left: comparison of the runs of SGD with different batch sizes. Right: best SGD vs. batch quasi-Newton. 66 Figure 4.5 Impact of the smoothing parameter ⇡ on the results obtained by the quasi-Newton algorithm solving a superquantile logistic regression on the Australian Credit dataset. Medium values are preferable: small values compromise convergence and large values give solutions close to the standard ERM. 67 Figure 4.6Reshaping of the histogram of testing losses for superquantile regression models (in red) as ? grows. We observe a shift to the left of the 90 th quantile of losses, at the price of degrading the average value. 68

Figure 4 . 7 . 70 Figure 5 . 1 75 Figure 5 . 2 86 Figure 5 . 3

 47705175528653 Figure 4.7 Reshaping of histograms of test losses (top) and test accuracies (bottom) over all class imbalances (for a classification task with logistic regression and the splice dataset). 70 Figure 5.1 Illustration of Example 5.1. A linear problem with a vanishing weak sharpness modulus. 75 Figure 5.2 Trajectory of the iterates (in blue) on the plot of the level sets of the chance-constraint and the objective for the 2d problem with data (5.19). 86 Figure 5.3 Convergence of our penalization algorithm on four norm problems (5.20) with 3 = 2, 10.50, 200. 87

Figure 6 . 1 93 Figure 6 . 2 1 : 94 Figure 6 . 3

 61936219463 Figure 6.1 Schematic summary of the -FL framework. Left: The server maintains multiple models F  9 , one for each level of conformity  9 . Middle: During training, selected devices participate in training each model F  9 . Individual updates are securely aggregated to update the server model. Right: Each test user is allowed to select their level of conformity , and are served the corresponding model F  . 93 Figure 6.2 Comparative diagram between the baseline FedAvg and our algorithm -FL (recall of Figure 1.4). Both algorithms consist of the following steps (note difference in step 1'). Step 1: Server selects < client devices and broadcasts the model to each selected device. Step 1' ( -FL only): Each selected device computes the loss (a scalar) incurred by the model on its local data and sends it to the server. Based on these losses, the server computes a threshold loss. It only keeps devices whose losses are larger than this threshold, and un-selects the other devices. Step 2: Each selected device computes an update to the server model based on its local data. Step 3: Updates from selected devices are securely aggregated to update the server model. 94 Figure 6.3 Illustration of -FL with a uniform mixture of Gaussians.Left: Positions in R 2 of the means ⇠ 1 , ⇠ 2 , ⇠ 3 of Gaussians @ 1 , @ 2 , @ 3 resp., the vanilla federated learning model F 1 , and the -FL model F 2/3 at conformity  = 2/3. Center: Comparison of the loss (• ; ? ) for each possible mixture ? with weights = ( 1 , 2 , 3 ). Right: Histogram of losses (•; ? ) for ? drawn uniformly from the set of all mixtures of @ 1 , @ 2 , @ 3 with conformity at least  = 2/3. 97

Figure 6 . 4 112 Figure 6 . 5 113 Figure 6 . 6 113 Figure 6 . 7 114 Figure 6 . 8 For 114 Figure 6 . 9 For 115 Figure 6 . 10 For

 641126511366113671146811469115610 Figure 6.4 Performance across iterations of EMNIST linear model. 112 Figure 6.5 Performance across iterations of EMNIST ConvNet model. 113 Figure 6.6 Histogram of loss distribution over training devices from EMNIST. Top:linear -Bottom:ConNet). 113 Figure 6.7 Histogram of misclassification error distribution over testing devices for EMNIST Top:linear -Bottom:ConNet). 114 Figure 6.8 For FedAvg and -FL with values of  in {0.1, 0.5, 0.8}, scatter plot of (left) loss on training device vs. amount of local data, and (right) misclassification error on testing device vs. amount of local data for EMNIST (Linear Model) 114 Figure 6.9 For FedAvg and -FL with values of  in {0.1, 0.5, 0.8}, scatter plot of (left) loss on training device vs. amount of local data, and (right) misclassification error on testing device vs. amount of local data for EMNIST (ConvNet Model) 115

62 4

 62 14), versus, (ii) secure aggregation of < weight vectors in 3 dimension. Typical values used are < 2{ 100, 500}, = 2{10, 50} and 3 ⇠ 10 6 . 118 LIST OF ALGORITHMS 1 Fast subroutine for smoothed oracle in the Euclidean setting 48 2 Computation of the sequence (◆ 8 : ) 0:= 1 in O(= log =) 59 3 Computation of the term from (4.33) Computation of the term ⌫ from (4typeset with L A T E X2 ⌘ using Hermann Zapf's Palatino type face (the actual Type 1 PostScript fonts used were URW Palladio L and FPL).

  6. Y. Laguel, J. Malick, and W. Van Ackooij. Chance constrained problems: a bilevel convex optimization perspective. Submitted to Computational Optimization and Applications, 2021. 7. Y. Laguel ⇤ , K. Pillutla ⇤ , J. Malick, and Z. Harchaoui. Federated Learning with Heterogeneous Devices:A Superquantile Optimization Approach. Submitted to the Journal of Selected Topics in Signal Processing, 2021.

  Superquantile regression improves over worst-case datapoints. Left figure: histograms of residuals A 8 = |H 8 (F 2 G 2 8 + F 1 G 8 + F 0 )| for model (2.9) (in violet) and model (2.10) (in orange). Right table: G th perc. stands for G-th percentile of final distribution of the residuals A 8 .

	Metric	model (2.9) model (2.10)
	Mean	7.23	10.62
	80 th perc.	9.73	13.94
	90 th perc.	17.29	15.93
	95 th perc.	24.00	17.83
	Figure 2.1:
		(2.4)

2

, and, ✓ (1, I) = log(1 + exp( 1I)) .

Table 2 . 1 :

 21 Average performances of each model over both subgroups.

  : Let (4 1 , ..., 4 = ) denote the canonical basis of R n . For any 8 2{ 1, ..., =}, we have: ⇢( 4 8

		Growth and inclusion in
	are equivalent:	the positive cone
	(i) The function ⇢ is increasing, i.e.: for any, G, H 2 R n such that G 8  H 8 for all 8 2{1, ..., =} we have ⇢(G)⇢(H) (ii) The support C belongs to the positive cone R = + .
	Proof. (8) =)( 88)

  Laguel, J. Malick, and Z. Harchaoui. First-order optimization for superquantile-based learning. Proceedings of the IEEE International Workshop on Machine learning for signal processing (MLSP), 2020.

• Y. Laguel, K. Pillutla, J. Malick, and Z. Harchaoui. Superquantiles at work: machine learning applications and efficient subgradient computation.

Accepted in Set-Valued and Variational Analysis.

  it to the case of non-convex losses. Section 4.2.2 considers gradients of smooth approximations of the superquantile by inf-convolution. We establish an equivalence result between smoothing various smoothing procedures of superquantiles in Section 4.2.3. We generalize these smoothing procedures to law-invariant comonotone risk measures in 4.2.4. We provide in Section 4.3 a short presentation of the toolbox SPQR. Finally, we present in Section 4.4 numerical experiments showing the interest of superquantile-based risk measures.

2, we study the (sub)-gradient calculus of superquantile-based

Outline functions with a focus on computational efficiency. In particular, Section 4.2.1 specifies the general subgradient formula from Eq. (3.7) for superquantile-based functions and extend

  The following proposition establishes that the resulting function 5 ⇡ as (4.5) is a smooth approximation of 5 , as a direct application of e.

g., [8, Theorem 4.1, Lemma 4.2], or [117, Theorem 1]. Proposition 4.2. In the above setting, the function 5 ⇡ provides a global approximation Smoothed approximation of 5 , i.e.

⇤

  From Lemma 4.3, we get an almost explicit expressions of values and gradients of the smooth approximation 5 ⇡ . Consider 5 ⇡ defined by (4.5) with ! differentiable. With ◆ 8 an optimal

	Corollary 4.4. Oracle for smooth
	approximation	solution of (4.11) with G 8 = ! 8 (F),

  0}| is bounded by an absolute constant. For C 2[ 0, 1], the concave function ◆ 7 ! ◆C <1 (◆) is maximized at ◆ 8 if and only if it satisfies the first-order optimality condition

  For any ⇡>0, the function ⇢ ⇡ defined in (4.28) is a ⇠ 1 approximation

	of ⇢:
	.28)
	with ( : 1 = ,⇡ the smooth approximation (4.6) of the superquantile provided with Example 4.1. The following proposition is a direct generalization of
	Proposition 4.2.
	Proposition 4.7. Smoothing of ⇢

  The algorithm chosen is a parameter for the instantiation Available algorithms of the RiskOptimizer class. This parameter can either be given in the input dictionary params or directly to the constructor of RiskOptimizer.

	# Recovery of the oracle
	smooth_oracle = custom_optimizer.oracle
	Algorithms class. The user has
	the choice among 'subgradient', 'dual_averaging, 'gradient', 'nesterov',
	'bfgs' and 'sgd'.
	# Risk Optimizer class with nesterov accelerated gradient algorithm
	custom_optimizer = RiskOptimizer(loss, loss_prime,
	algorithm='nesterov')
	OracleStochasticSubgradient and OracleStochasticGradient To avoid
	having to deal with of optional parameters when instantiating an oracle, we
	advise to go through the instantiation of a RiskOptimizer first.
	custom_params = {'algorithm': 'nesterov', # selected algorithm
	'p': 0.5 # safety probability level
	}
	# Instantiation of the Risk Optimizer
	custom_optimizer = RiskOptimizer(loss, loss_prime,
	params=custom_params)

Available oracles

user instantiates the RiskOptimizer object. Four different oracles are implemented as python objects. The first two oracles, OracleSubgradient and OracleSmoothGradient are designed for batch methods. The subgradient oracle OracleSubgradient is the one instantiated when the algorithm chosen by the user is 'subgradient' or 'dual_averaging. The smoothed oracle is instantiated when the algorithm chosen is 'gradient', 'nesterov' or 'bfgs'. The last two oracles are designed for mini-batch methods:

Table 4 . 1 :

 41 Comparison of performances between a superquantile model and a riskneutral model for a logistic regression on a distributionally shifted dataset.

		Superquantile	Expectation
	Dataset	Accuracy	Loss	Accuracy	Loss
	Adult	53.2 ± 0.67 0.693 ± 0.00 55.4 ± 0.48 1.072 ± 0.01
	Monks	64.4 ± 2.65 0.714 ± 0.05 54.0 ± 1.57 1.207 ± 0.08
	Splice	82.7 ± 0.62 0.681 ± 0.05 81.7 ± 0.78 0.557 ± 0.04
	Diabetes	42.5 ± 4.72 0.694 ± 0.00 45.1 ± 4.51 1.325 ± 0.12
	Spambase	78.4 ± 1.23 0.761 ± 0.15 77.1 ± 0.87 0.635 ± 0.07
	Mammography	39.1 ± 7.59 0.730 ± 0.01 39.1 ± 6.90 1.293 ± 0.09
	Electricity	42.8 ± 0.40 0.693 ± 0.00 47.5 ± 0.63 1.060 ± 0.01
	Phoneme	37.3 ± 5.38 0.737 ± 0.01 50.5 ± 3.10 1.292 ± 0.04
	Nomao	87.5 ± 0.22 0.413 ± 0.03 87.4 ± 0.23 0.394 ± 0.02
	Skin-segmentation 92.1 ± 0.11 0.420 ± 0.00 91.9 ± 0.05 0.537 ± 0.01

  .1, Lemma 4.2].

	Proposition 6.2. For every ⇡>0, we have that ⇡ ,( and	⇡ ,( are ! 0 -smooth with	Smoothing and smoothness constants

  (C) in outer iteration C of the

														Client drift
	algorithm as
	3 (C) := E (⇠* <	2 6 6 6 6 4	' :2(	(C) :	1 ' 9=0	F	(C) :,9	F (C)	2	F C	3 7 7 7 7 5	.	(6.11)
	Proposition 6.4. If ✏ 	1 4 (!+⌫) , we have the following bounds for any C 0:	Upper bound on client drift

  .1 to 6.4, we present a comparison of various statistics of the test misclassification error distribution for different methods. For each column, the smallest mean over five random runs is highlighted in bold. Further, if no other method is within one standard deviation of this method, the entire entry (i.e., mean ± std) is highlighted in bold. Our main findings are summarized below.-FL achieves a 3.3% absolute (12% relative) improvement over any vanilla

	-FL consistently
	achieves the smallest 90 th
	percentile error

Table 6 . 1 :

 61 Metrics for the test misclassification error for EMNIST (Linear Model).

	Method	Mean	Standard Deviation 10 C⌘ Percentile	Median	90 C⌘ Percentile
	FedAvg	16.63 ± 0.50	4.94 ± 0.14	6.43 ± 0.24	15.34 ± 0.37	28.46 ± 1.07
	FedAvg  = 0.5	16.22 ± 0.23	5.06 ± 0.17	6.47 ± 0.28	15.05 ± 0.25	27.56 ± 0.81
	FedProx	16.01 ± 0.54	5.16 ± 0.32	6.68 ± 0.44	14.88 ± 0.29	27.01 ± 1.86
	@-FFL (Best @ = 0.001)	16.58 ± 0.30	5.05 ± 0.21	6.53 ± 0.20	15.40 ± 0.43	28.02 ± 0.80
	Tilted-ERM (Best C = 1.0) 15.69 ± 0.38	7.31 ± 0.68	7.26 ± 0.51	14.66 ± 0.16	25.46 ± 1.49
	AFL	33.00 ± 0.37	20.38 ± 0.23	22.92 ± 0.23	31.58 ± 0.27	45.07 ± 1.00
	-FL  = 0.8	16.08 ± 0.40	5.60 ± 0.14	7.31 ± 0.29	14.85 ± 0.48	26.23 ± 1.15
	-FL  = 0.5	15.48 ± 0.30	6.13 ± 0.15	8.08 ± 0.16	14.73 ± 0.22	23.69 ± 0.94
	-FL  = 0.1	16.37 ± 1.03	6.61 ± 0.42	8.28 ± 0.65	15.49 ± 1.03	25.45 ± 2.77

Table 6 . 2 :

 62 Metrics for the test misclassification error for EMNIST (ConvNet Model).

	Method	Mean	Standard Deviation 10 C⌘ Percentile	Median	90 C⌘ Percentile
	FedAvg	34.74 ± 0.31	12.16 ± 0.15	21.89 ± 0.24	34.81 ± 0.38	46.83 ± 0.54
	FedAvg  = 0.8	34.47 ± 0.03	12.08 ± 0.16	21.69 ± 0.26	34.62 ± 0.17	46.59 ± 0.38
	FedProx	34.74 ± 0.31	12.16 ± 0.15	21.89 ± 0.24	34.82 ± 0.39	46.83 ± 0.54
	@-FFL (Best @ = 1.0)	34.48 ± 0.06	11.96 ± 0.14	21.61 ± 0.24	34.57 ± 0.16	46.38 ± 0.40
	Tilted-ERM (Best C = 1.0) 34.71 ± 0.31	12.00 ± 0.14	21.83 ± 0.34	34.91 ± 0.39	46.70 ± 0.50
	AFL	35.97 ± 0.08	11.83 ± 0.09	23.58 ± 0.28	36.09 ± 0.17	47.51 ± 0.32
	-FL  = 0.8	34.41 ± 0.22	12.17 ± 0.11	21.77 ± 0.34	34.64 ± 0.25	46.44 ± 0.38
	-FL  = 0.5	35.28 ± 0.25	11.68 ± 0.40	23.03 ± 0.38	35.55 ± 0.53	46.64 ± 0.41
	-FL  = 0.1	37.78 ± 0.89	12.86 ± 0.52	23.93 ± 0.99	37.80 ± 1.30	51.38 ± 1.07

Table 6 . 3 :

 63 Metrics for the test misclassification error for Sent140 (Linear Model).

	Method	Mean	Standard Deviation 10 C⌘ Percentile	Median	90 C⌘ Percentile
	FedAvg	30.16 ± 0.44	4.36 ± 1.26	10.06 ± 2.06	29.51 ± 0.33	49.66 ± 3.95 1
	FedAvg  = 0.8	29.85 ± 0.46	5.39 ± 1.32	11.90 ± 2.27	29.57 ± 0.31	46.93 ± 3.84 1
	FedProx	30.20 ± 0.48	4.35 ± 1.23	10.37 ± 2.08	29.51 ± 0.32	49.85 ± 4.07
	@-FFL (Best @ = 0.01)	29.99 ± 0.56	4.90 ± 1.66	10.98 ± 2.88	29.56 ± 0.39	48.65 ± 4.68
	Tilted-ERM (Best C = 1.0) 30.13 ± 0.49	14.17 ± 2.10	13.18 ± 3.33	29.96 ± 0.84	46.54 ± 3.27
	AFL	37.74 ± 0.65	9.90 ± 1.46	18.19 ± 1.99	36.95 ± 1.03	57.78 ± 1.19
	-FL  = 0.8	30.30 ± 0.33	6.75 ± 2.68	13.05 ± 3.87	29.92 ± 0.38	46.46 ± 4.39
	-FL  = 0.5	33.58 ± 2.44	8.74 ± 3.98	16.77 ± 6.62	33.28 ± 2.27	50.47 ± 8.24
	-FL  = 0.1	51.97 ± 11.81	9.11 ± 5.47	16.67 ± 9.15	52.44 ± 13.21	86.44 ± 10.95

Table 6 . 4 :

 64 Metrics for the test misclassification error for Sent140 (RNN Model).

Table 6 . 5 :

 65 Comparison of communication cost of (i) secure aggregation for quantile of < scalars with = rounds of (6.14), versus, (ii) secure aggregation of < weight vectors in 3 dimension. Typical values used are < 2{100, 500}, = 2{10, 50} and 3 ⇠ 10 6 .

	Sec.Agg. Protocol	Comm. Cost of quantile, ⇠ @	Comm. Cost of weight vector, ⇠ F	Ratio ⇠ @ /⇠ F	Range of ⇠ @ /⇠ F
	[20]	=< 2 + =<	= 2 + 3<	=</3	0.1% to 2.5%
	[151]	=< log << log < + 3< log <= /3	0.01% to 0.05%
			(a) EMNIST ConvNet.

  .1 Superquantile regression improves over worst-case datapoints. Left figure: histograms of residuals A 8 = |H 8 (F 2 G 2 8 + F 1 G 8 + F 0 )| for model (2.9) (in violet) and model (2.10) (in orange). Right table: G th perc. stands for G-th percentile of final distribution of the residuals A 8 . 16 Figure 2.2 Statistical Heterogeneity is a key feature of federated learning where clients with heterogeneous distributions collaborate to learn a single model. 18 Figure 2.3 Comparison of the three regressions for the toy federated learning setting of Example 2.2. We want commensurate performances among users, which means, graphically, a curve at the same distance from the data-points of the conforming users (in blue) and the non-conforming user (red). 19

Table 2

 2

	.1	Average performances of each model over both sub-
		groups.	20
	Table 4.1	Comparison of performances between a superquantile
		model and a risk-neutral model for a logistic regression
		on a distributionally shifted dataset.	69
	Table 5.1	Final suboptimality and feasibility for (5.20) (where ? =
		0.8).	88
	Table 6.1	Metrics for the test misclassification error for EMNIST
		(Linear Model). 111
	Table 6.2	Metrics for the test misclassification error for EMNIST
		(ConvNet Model). 111

Table 6 . 3

 63

This project led to the paper

When the assumption of the existence of an underlying distribution % is not realistic, the usual approach is to still use the empirical risk minimization principal based on the given training dataset P = = {(0 8 , 1 8 )} 18= .

Remark on the Clarke subdifferential: As another by-product of the chain rule[140, 10.6], the set of horizon subgradients of 5 is reduced to 0 since so is the one of ( ? (convex and defined on R n ). As a consequence, the Clarke subdifferential is the convex hull of the limiting subdifferential[140, 8.49]. Thus we have, in our case, that the three subdifferentials (regular, limiting and Clarke) coincide.

We count as unitary operations any elementary operation between two float numbers (addition, subtraction, multiplication, division, equality, inequality) and the reading or writing of a float variable.

We do not directly impose a lower bound on : , apart from the implied bound : max{0, : (1 )}/, because it is not realistic to assume that the distribution on a test device must necessarily contain a component of every training distribution @ : .

-Lemma 4.14. There exists a constant C 3 such that for any rank : 2 ~0, = 1, the Upper bound on the complexity of lines to number ' : of operations required to run the lines 26 to 29 in Algorithm 2 satisfies ' :  C 3 card( : )+6.

(4.43)

Proof. Line 26 and 27 both require 1 operation. Computing 8 (◆ 8 : , : + 1) according to (4.39) also requires 1 operation. Computation of 8 + (◆ 8 : , : + 1) using (4.39) clearly requires 2 card : + 1 iterations (2 inequalities per term in : + 1 inequality for the term indexed by 8 + (◆ 8 : , : + 1)). Computation of  0 :+1 (◆) using (4.40) also requires at most a constant multiple < of card : operations (in view of (4.40), < < 10). Finally once 8 + (◆ 8 : , : + 1) is known, computing  00+ :+1 (◆ 8 : ) using (4.41) requires 3 operations. Overall, we obtain that ' : (< + 2) card : + 3 + 1 + 1 + 1 + 1 = (< + 2) card : + 7 which gives (4.43).

⇤

We can finally prove Theorem 4.10, which is the main result of this section.

Proof. Initialization of Algorithm 2 can clearly be done in constant time (as-Proof of Theorem (4.10) suming the G 8 's are already sorted). Let T = denotes the number of operations required to run lines 1 to 30 of Algorithm 2. For the stage : = 0, we know that the initial value of ◆, ◆ 8 0 1 is already a root of  0 by Lemma 4.8, which implies that lines 4 to 25 are not run during this iteration. Thus, the total number of iterations T = satisfies where for 8 2 ~1, =, we introduced

Algorithm 4 uses this formulation to reach a linear time complexity for the computation of ⌫. We introduce there the sequence (C 8 ) 183= which is a concatenation the sequences

in an non-decreasing order. We assume also without harming the time complexity of such sorting that in case of equality between any terms of these three sequences, the terms in ( 0 always appear before the ones in ( SPQR routines rely on just-in-time compilation [START_REF] Siu Kwan Lam | Numba: A llvm-based python jit compiler[END_REF] to ensure efficient running times. The software package is publicly available at https://github.com/yassine-laguel/spqr.

We now walk the reader through the toolbox SPQR.

: .

The user provides a dataset modeled as a couple ( , ⌫)2R The two python functions L and L_prime are assumed to be functions of the triplet (w,a,b) where w is the variable and (a,b) a datapoint. For instance, the oracle for superquantile linear regression are the following one. Before minimizing (4.2), we instantiate the RiskOptimizer object with the

The RiskOptimizer object link with (super)quantiles and chance-constraint to establish a novel bilevel reformulation of general chance-constrained problems. In Section 5.3,w e propose and analyse a penalty approach revealing the underlying DC structure. In Section 5.4, we discuss implementation of this approach in our publicly available toolbox. In Section 5.5, we provide illustrative numerical experiments, as a proof of concept, showing the interest of the method. Technical details on secondary theoretical points and on implementation issues are postponed to appendices.

5.2

In this section, we derive the reformulation of a chance constraint as a bilevel program wherein both the upper and lower level problems, when taken individually, are convex. By definition, the chance constraint in (5.1) involves the cumulative distribution function: we have for any fixed F 2 R d , P[6(F, ⇢)0] ? , 6(F,⇢) (0) ?. We rewrite this constraint using quantiles, as formalized in the next lemma.

⇤

Such reformulation has already been investigated in previous works (see e.g. [START_REF] Peña-Ordieres | Solving chanceconstrained problems via a smooth sample-based nonlinear approximation[END_REF]). Compared to the empirical cumulative distribution function, the ?-quantile benefits from more regularity: F 7 ! & ? (6(F, ⇢)) is continuous whenever 6 is continuous with respect to F. However, the quantile remains a non-convex and nonsmooth function. We propose to reformulate once again this problem in terms of superquantiles. To that end, we build upon the variational formulation (3.12) of the superquantile in its general form.

Lemma 5.2. For an integrable random variableand a probability level ?, the

Quantile are solution to the variational problem (3.12) superquantile ( ? (-) is the optimal value of the convex one-dimensional problem

Moreover, the quantile & ? (-) is the left end-point of the solution interval of this problem

Together with (5.2), we obtain from the previous easy lemma a bilevel formulation of the general chance-constrained problem (5.4). The idea is simple: introducing an auxiliary variable ◆ 2 R d to recast the potentially non-convex chance constraint of (5.1) as two constraints, a simple bound constraint and a difficult optimality constraint, forming a lower subproblem. Introducing the lower objective function

we have the following exact reformulation of chance-constrained problems.

class Optimizer runs an implementation of the bundle method of [START_REF] De | Proximal bundle methods for nonsmooth DC programming[END_REF] on the penalized problem (5.7). The toolbox gives the option to update the penalization parameters ⇠, ⌫ along the running process to escape possible stationary points for the DC objective that are non-feasible for the chance constraint.

from taco import Optimizer problem = Problem() optimizer = Optimizer(problem, p=0.9, starting_point=np.zeros(2, dtype=np.float64), pen1=1.0, pen2=10.0) sol = optimizer.run() Customizable parameters are stored in a python dictionary, called params, Customization and designed as an attribute of the class Optimizer. The main parameters to tune are: the safety level of probability p, the starting penalization parameters ⇠ = pen1 and ⌫ = pen2, the starting point of the algorithm and the starting value for the proximal parameter of the bundle method. We note that often a tuning of both starting penalization parameters may be required to get a satisfying solution for the problem considered. See for instance the experimental setup of our numerical illustations in 5.5.2. Others parameters are filled with default values when instantiating an Optimizer; for instance: custom_options = { 'p': 0.9, 'pen1': 1.0, 'pen2': 10.0, 'bund_mu_start': 50.0, 'bund_max_size_bundle_set': 30, } custom_optimizer = Optimizer(problem, params=custom_options) Some important parameters (such as the safety probability level, or the starting penalization parameters) may also be given directly to the constructor of the class Optimizer, when instantiating the object; as in the first example.

.

Further customization. TACO relies on a set of hyperparameters to be provided

Penalization procedure by the user and specified in a single dictionnary passed as an argument of the class Optimizer. There are two families of parameters to be specified. First, the parameters concerning the oracles ! 1 and ! 2 . These are the starting penalization parameters ⌫ and ⇠, the multiplicative factors to increment them along the penalization process, and the smoothing parameter of !2 .

The second family of parameters concerns the bundle method. It gathers

Parameters of the bundle method

the proximal parameters of the bundle method, the precision targeted, the starting point of the algorithm, the maximal size of the bundle information, and parameters related used when restarting the bundle method (see more in the following section). Overall the most important parameters to specify are the starting penalization parameters ⇠ and ⌫ with respective keys 'pen1' and 'pen2' and the starting proximal parameter of the bundle algorithm. In the toolbox, we provide the set of parameters used in our numerical experiments.

In addition of the final solution, it is possible to log the iterates, function values and time values, by calling the method with the option logs=True. The verbose=True option also allows the user to observe in real time the progression of the algorithm along the iterations.

HANDLING HETEROGENEITY IN FEDERATED LEARNING

This chapter is devoted to the learning of models in heterogeneous distributed environments.

The developments laid down below build upon the following work:

6.1

Federated learning is a distributed optimization paradigm with a central server and a large number of clients. An introduction and references are provided in the Section 2.2.2 of this thesis.

In federated learning statistical heterogeneity is a key feature: client data distributions are not identical. Each user has unique characteristics which are reflected in the data they generate. These characteristics are influenced by personal, cultural, and geographical factors. For instance, the varied use of language contributes to data heterogeneity in a next word prediction task.

We present in this chapter a robust approach to federated learning that guarantees a minimal level of predictive performance to all devices even in situations where the population is heterogeneous. Usual algorithms for federated learning such as FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] seek to minimize the prediction error on average over the population of devices available for training. While this approach can be effective in terms of predictive performance for each device whose local data is close to the average distribution, it is liable to fail on devices which are far from this distribution. The approach we develop addresses these issues by minimizing a learning objective based on the superquantile, which was introduced in the Section 3.3 of this thesis.

This approach, coined -FL, allows one to control higher percentiles of the distribution of errors over the (possibly heterogeneous) population of devices. We shall show in the experiments that our approach is more efficient than a direct approach simply seeking to minimize the worst error over the population of devices. Compared to FedAvg, -FL delivers improved prediction to data-poor or non-conforming devices. We present theoretical convergence guarantees for

Thus, given the definition of conformity, problem (6.2) boils down to minimizing with respect to F (

0  :  :



One may recognize in the above problem the dual formulation (3.11) of the (1 )-superquantile over the distribution of losses ( : (F)) :2~1,# , weighted with respective probabilities ( : ) :2~1,# . Thus, the -FL framework enforces robustness at the scale of the network by dynamically re-weighting the importance of the devices involved in the training process.

Federated optimization for -FL

We consider algorithms similar to FedAvg because of their ability to avoid communication bottlenecks and preserve the privacy of user data. A practical federated learning algorithm cannot assume that all the devices are always available; it must be able to work with a subset of devices in each round. To this end, we define the counterpart of the constraint set P  from (6.2) defined on a subset ( ⇢ ~1, # of < devices as: the selected devices (line 3) requires the per-device losses : (F (C) ) to be sent visible to the server. We show in Section 6.5.4 how to compute the weights (C) using a secure aggregation oracle.

Illustration on a toy example

We now illustrate the -FL objective on a simple example of a mixture of

A mean estimation problem

Gaussians. Consider a mixture of # = 3 Gaussian distributions in R 2 , with uniform weights ( : = 1/#), identity covariance and respective means ⇠ 1 , ⇠ 2 , ⇠ 3 which form a scalene triangle -see Figure 6.3. We assume that each distribution represents a training device. Consider the task of mean estimation where 5 (F; ⇢) = k⇢ Fk 2 2 so that (F; ?) is minimized by the mean of the mixture ? . Suppose in our toy federated learning scenario that a model F is trained on the 3 available training devices before being deployed on a test device with distribution ? . Vanilla federated learning, which is a special case of the -FL framework with conformity  = 1, aims to minimize (• ; ? ) over the training distribution ? . The minimizer F 1 of the loss (• ; ? ) on the training distribution is simply the mean

Now consider a conformity level of  = 2/3. In this case, a simple calculation

Performance on test clients

shows that the -FL objective is a piecewise quadratic, which is minimized at the midpoint of the longest side of the triangle formed by ⇠ 1 , ⇠ 2 , ⇠ 3 . In the example of Figure 6.3, this is

Next, consider the set P 2/3 of all mixture weights such that conf(? ) 2/3. We see from Figure 6.3 (middle) that there are mixtures for which F 2/3 is better than F 1 and vice-versa. However, from the histogram of losses in Figure 6.3,we see that the worst loss (• ; ? ) over all such mixtures is lower for the -FL model F 2/3 . In practical terms, -FL presents an improvement on devices with the worst user experience. Moreover, by optimizing the superquantile, -FL aims for good performance on all test devices with a given conformity, irrespective of their distribution. Note that while we use a uniform distribution in the illustration of Figure 6.3 (right), this distribution is unknown in practice. Thus, such assumption translates into a bound on the gradient dissimilarity among the agents [START_REF] Sai | Scaffold: Stochastic controlled averaging for federated learning[END_REF][START_REF] Wang | Adaptive federated learning in resource constrained edge computing systems[END_REF]:

Here, we also consider the minimization of the global loss ⇡  by a stochastic algorithm based on a partial participation of the devices in the network, with the additional difficulties that we only have access to a biased estimator ⇡  of the loss ⇡  and its gradient. In particular, the adaptive reweighting of the clients selected at each round does not permit the direct use of such assumption. We show instead in the next lemma that the variance of stochastic gradient estimator can also be bounded, thanks to the Lipschitz assumption. Proposition 6.3. Consider the quantities (C) , F (C) from Algorithm 5. We have,

Proof. By (6.5), we have:

Now since the weights (C)

: sum to one, we may use the convexity of k•k 2 to get:

:

The squared triangle inequality (cf. (6.4)) together with the Lipschitz assumption on the functions : yields:

:

Unrolling this recursion yields for any 9  1

.

Thus, for any 9  1,

where we use (1 + 1/G) G  4 for any G > 0. Therefore, by Lemma 6.3, we get

This gives the first bound. The second bound follows by smoothness (6.7). ⇤

Bound on the Norm of Each Update. We bound the expected squared norm of each update F (C+1) F (C) , which has the closed form expression:

⌘

, where 3 (C) is the client drift term defined in (6.11).

Proof. Using (6.4) together with the gradient formula (6.9), we get:

Finally, using 2|01|0 2 /2 2 + 2 2 1 2 and the convexity of

6.5.2 Algorithms, hyperparameters and evaluation strategy . The proposed -FL is run for three values of  2{0.8, 0.5, 0.1}. We compare it to the following baselines:

• FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]: It is the de facto standard for the vanilla federated learning objective.

• FedAvg, : We also consider FedAvg with a random device filtering step: local updates are run on a fraction of the initial number of devices randomly selected per round. For each dataset, we try three fraction values, corresponding to the average number of devices selected by -FL for the three values of  used (cf. Figure 6.11). We report as FedAvg-Sub the performance of FedAvg,  with  2{0.8, 0.5, 0.1} which gives the best performance on -FL (i.e., lowest 90 th percentile of test misclassification error).

• FedProx [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF]: It augments FedAvg with a proximal term but still minimizes the vanilla federated learning objective.

• @-FFL [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF]: It raises the per-device losses to the power (1 + @), where @ 0 is a parameter, in order to focus on devices with higher loss.

• AFL [START_REF] Mohri | Agnostic Federated Learning[END_REF]: It aims at minimizing the worst per-device loss. We implement it as an asymptotic version of @-FFL, using a large value of as this was found to yield better convergence with comparable performance [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF]. In the experiments we take @ = 10.0.

• Tilted-ERM [START_REF] Li | Tilted Empirical Risk Minimization[END_REF]: It aims at minimizing a parameterized variant of logsumexp function over the per-device losses.

The experiments are conducted on the datasets described in Section 6.5.1.

.

Rounds.

We measure the progress of each algorithm by the number of calls to secure aggregation routine for weight vectors, i.e., the number of communication rounds.

For the experiments, we choose the number of communication rounds depending on the convergence of the optimization for FedAvg. For the EMNIST dataset, we run the algorithm for 3000 communication rounds with the linear model and 1000 for the ConvNet. For the Sent140 dataset, we run the 1000 communication rounds for the linear model and 600 for the RNN. Devices per Round. We choose the same number of devices per round for each method, with the exception of FedAvg, . All devices are assumed to be available and selections are made uniformly at random. In particular, we select 100 devices per round for all experiments with the exception of Sent140 RNN for which we used 50 devices per round.

Local Updates and Minibatch Size. Each selected device locally runs 1 epoch of mini-batch stochastic gradient descent. The effect of this choice of local epochs is explored further at the end of Section 6.5. We used the default mini-batch of 10 for all experiments [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF], except for 16 for EMNIST ConvNet. This is For any e @ 8 {G 1 , ••• , G < } , define e ? (@; e @) := |G : e @| +(4? 2)(G : @)+|G : e @| , as a majorizing surrogate for ? at e @, i.e., e ? (• ; e @) ? and e ? (e @; e @) = ? (e @). Note that e ? (@; e @) is an isotropic quadratic in @.

A majorization-minimization algorithm to minimize and hence find the ?-quantile can thus be given as

> > < > > :

arg min @ e ? (@; @ C ) if

if @ C = G : for some : Communication Cost of Secure Aggregation For Quantile. Here we show in regular cases that the communication cost of secure aggregation of quantile is typically in the range 0.1 2.5% of the cost of secure aggregation of weight vectors (table 6.5 contains a summary of the following discussion). The asymptotic total communication cost of securely aggregating < vectors in R 3 is O(< 2 + 3<) bits [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF] or O(< log < + 3< log <) bits [START_REF] So | Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning[END_REF]. In typical cross-device federated learning applications, < ⇠ 100 500, while the model dimension is 3 ⇠ 10 6 [START_REF] Hard | Federated learning for mobile keyboard prediction[END_REF][START_REF] Yang | Applied federated learning: Improving google keyboard query suggestions[END_REF]. Typically, = ⇠ 10 50 iterations of (6.14) will suffice to recover exact filtering (see benchmarking below).

We now quantify the ratio ⇠ @ /⇠ F of the communication cost of secure Overhead of secure quantile computation aggregation for quantile ⇠ @ to that of secure aggregation of weight vectors ⇠ F .

In the case of [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF], this ratio is

while for the case of [START_REF] So | Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning[END_REF], it is

Thus, the additional overhead of secure aggregation of the quantile is in the range 0.1 2.5% under typical range of values for the protocol of [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF], while it is in the range 0.01 0.05% for the protocol of [START_REF] So | Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning[END_REF].

Secure Quantile Computation on Real Data. We now plot the convergence of the secure quantile iterations in (6.14). We follow the experimental setup that will be detailed in the forthcoming Section 6.5 and compute the (1 )-quantile with (6.14). We repeat this experiment for  2{0.2, 0.5, 0.9} at the 100 C⌘ iteration ("initial") of Algorithm 5 as well as the the last iteration ("converged"). We plot the difference of the iteration @ C of (6.14) to the quantile @ ⇤ as well as the error in filtering, i.e., | Õ : I(G : @ C )

Õ

: I(G : @ ⇤ )|. See Figure 6.13 for plots. We see that the secure update(6.14) converges rapidly and sometimes even finds an