The subdifferential calculus for the expectation of nonsmooth random integrands involves many fundamental and challenging problems in stochastic optimization. It is known that for Clarke regular integrands, the Clarke subdifferential of the expectation equals the expectation of their Clarke subdifferential. In particular, this holds for convex integrands. However, little is known about the calculation of Clarke subgradients for the expectation of non-regular integrands. The focus of this contribution is to approximate Clarke subgradients for the expectation of random integrands by smoothing methods applied to the integrand. A framework for how to proceed along this path is developed and then applied to a class ofmeasurable composite max integrands. This class contains non-regular integrands from stochastic complementarity problems as well as stochastic optimization problems arising in statistical learning.

We would like to thank Associate Editor and two referees for their helpful comments.

Authors and Affiliations

1. Department of Applied Mathematics, University of Washington, Seattle, USA

   James V. Burke

2. Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong, China

   Xiaojun Chen

3. Jiangsu Key Lab for NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, 210023, China

   Hailin Sun

Corresponding author

Correspondence toXiaojun Chen.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work is support by NSF Grant No. DMS-1908890, Hong Kong Research Grant Council Grant 153000/17P, and NSFC Grant Nos. 11871276 and 11571178.

Appendix: Background

1.1Finite-dimensional variational analysis

Since we allow mappings to have infinite values, it is convenient to define the extended reals\({{\overline{{\mathbb {R}}}}}:={\mathbb {R}}\cup {\{+\infty \}}\). Theeffective domain of\(f:\,{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\), denoted\({\text{ dom }\,}f\subseteq {\mathbb {R}}^n\), is the set on whichf is finite. To avoid certain pathological mappings the discussion is restricted toproper not everywhere infinite)lower semi-continuous (lsc) functions. Of particular importance is theepigraph of such functions:\({\text{ epi }\, f}:=\left\{ (x,\mu )\,\left| \,f(x)\le \mu \right. \right\} \). We have thatf is lsc if and only if\({\text{ epi }\, f}\) is closed, andf is convex if and only if\({\text{ epi }\, f}\) is convex.

Definition 8

(Subderivatives) [27, Exercise 9.15] For a locally Lipschitz function\(f:\,{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\) near a point\({{u}_*}\in {\mathbb {R}}^n\) with\(f({{u}_*})\) finite,

1. (i)

   thesubderivative\(df({{u}_*}):{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\) is defined by

   $$\begin{aligned} df({{u}_*})(w):= \underset{\tau \downarrow 0}{\lim \inf ~} \frac{f({{u}_*}+\tau w) - f({{u}_*})}{\tau }; \end{aligned}$$
2. (ii)

   theregular subderivative (or the Clarke generalized directional derivative whenf is locally Lipschitz)\(~{\widehat{d}}f({{u}_*}):{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}~\) is defined by

   $$\begin{aligned} {{{\widehat{d}}}}f({{u}_*})(w):= \underset{u\rightarrow {{u}_*},\,\tau \downarrow 0}{\lim \sup }\frac{f(u+\tau w)-f(u)}{\tau }. \end{aligned}$$

Definition 9

(Subgradients, subdifferentials and subdifferential regularity) Consider a locally Lipschitz function\(f:{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\), a point\(v\in {\mathbb {R}}^n\), and a point\({{u}_*}\in {\mathbb {R}}^n\) with\(f({{u}_*})\) finite.

1. (i)

   [27, Theorem 8.49] The vectorv is aClarke subgradient off at\({{u}_*}\) ifv satisfies

   $$\begin{aligned} {{{\widehat{d}}}}f({{u}_*})(w)\ge \left\langle v\, ,\, w\right\rangle ~\forall ~w\in {\mathbb {R}}^n. \end{aligned}$$

   We call the set of Clarke subgradientsv theClarke subdifferential off at\({{u}_*}\) and denote this set by\(\partial f({{u}_*})\).

2. (ii)

   [27, Corollary 8.19]\(f:\,{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\) is said to besubdifferentially regular (or Clarke regular) at\({{u}_*}\in {\text{ dom }\,}f\) with\(\partial f({{u}_*})\ne \emptyset \) if

   $$\begin{aligned} df({{u}_*})(w) = {{{\widehat{d}}}}f({{u}_*})(w)\quad \forall \, w\in {\mathbb {R}}^n. \end{aligned}$$
3. (iii)

   [14, Definition 2.6.1] [12] The vectorv is aB-subgradient off at\({{u}_*}\) if

   $$\begin{aligned} v=\lim _{u^k\rightarrow {{u}_*}} \nabla f(u^k), \quad \mathrm{where }\,\, f \,\, \text{ is } \text{ differentiable } \text{ at }\,\, u^k. \end{aligned}$$

   We call the set ofB-subgradientsv off at\({{u}_*}\) theB-subdifferential off at\({{u}_*}\) and denote this set by\(\partial ^B f({{u}_*})\).

4. (iv)

   [27, Definition 8.3] The vectorv is anM-subgradient off at\({{u}_*}\) if there are sequences\( u^k\rightarrow {{u}_*}\) and\(v^k \rightarrow v\) with

   $$\begin{aligned} \underset{u\rightarrow u^k}{\lim \inf ~}\frac{f(u)-f(u^k) - \left\langle v^k\, ,\, u-u^k\right\rangle }{\Vert u-u^k\Vert }\ge 0. \end{aligned}$$

   We call the set ofM-subgradientsv off at\({{u}_*}\) theM-subdifferential off at\({{u}_*}\) and denote this set by\(\partial ^M f({{u}_*})\).

Remark 6

In [27], the notion of subdifferential regularity is defined in [27, Definition 7.25]. In the definition given above we employ characterizations of this notion given by the cited results. Note that subdifferential mappings are multi-functions.

Definition 10

(Strict continuity and strict differentiability) Let\(H:\,D\rightarrow {\mathbb {R}}^m\,\),\(D\subseteq {\mathbb {R}}^n\), and\(h:\,{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\).

1. (i)

   [Strict Continuity [27, Definition 9.1]] We say thatH is strictly continuous at\({\bar{x}}\in {\text{ int }\left( D\right) }\) if

   $$\begin{aligned} \mathrm {lip}\, H({\bar{x}}):=\limsup _{{\mathop {x\ne x'}\limits ^{x,x'\rightarrow {\bar{x}}}}} \frac{\left\| H(x')-H(x)\right\| }{\left\| x'-x\right\| }<\infty \, . \end{aligned}$$
2. (ii)

   [Strict Differentiability [27, Definition 9.17]] We say thath is strictly differentiable at a point\({\bar{x}}\in {\text{ dom }\,}{h}\) ifh is differentiable at\({\bar{x}}\) and

   $$\begin{aligned} \lim _{{\mathop {x\ne x'}\limits ^{x,x'\rightarrow {\bar{x}}}}} \frac{h(x')-h(x)-\left\langle \nabla h({\bar{x}})\, ,\, x'-x\right\rangle }{\left\| x'-x\right\| }=0\, . \end{aligned}$$

It is easily seen that ifh is continuously differentiable on an open setU, thenh is strictly differentiable and subdifferentially regular onU with\(\partial h(x)=\{\nabla h(x)\}\) for all\(x\in U\) ([27, Theorem 9.18 and Exercise 9.64]).

The notion of strict continuity off at a point\({\bar{x}}\) implies the existence of a neighborhood of\({\bar{x}}\) on whichf is Lipschitz continuous, that is,f is locally Lipschitz continuous at\({\bar{x}}\) where the local Lipschitz modulus is lower bounded by\(\mathrm {lip}\, H({\bar{x}})\). In this light, Definition8 and Definition 9(ii) combine to tell us that

whereverf is strictly continuous and subdifferentially regular at\({{u}_*}\). Moreover, in this case, [27, Theorem 8.30] tells us that

Remark 7

(Subdifferentials of Compositions) If\(g:\,X\subset {\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\) is given as the composition of two functions\(f:\,Y\subset {\mathbb {R}}^m\rightarrow {{\overline{{\mathbb {R}}}}}\,\) and\(h:\,X\rightarrow Y\,\), i.e. \(g(x)=(f\circ h)(x)=f(h(x))\), then we write\(\partial g(x)=\partial (f\circ h)(x).\) On the other hand, we write\(\partial f(h(x))\) to denote the subdifferential off evaluated ath(x).

Theorem 9

(Strict differentiability and the subdifferential) [27, Theorem 9.18] [14, Proposition 2.2.4] Let\(h:\,{\mathbb {R}}^n\rightarrow {{\overline{{\mathbb {R}}}}}\,\) with\({\bar{x}}\in {\text{ dom }\,}{h}\). Thenh is strictly differentiable at\({\bar{x}}\) if and only ifh is strictly continuous at\({\bar{x}}\) and\(\partial h({\bar{x}})=\{\nabla h({\bar{x}})\}\).

1.2Measurable multi-functions

We now review some of the properties of measurable multi-functions used in this paper [2,15,18,27]. For more information on this topic, we refer the interested reader to [27, Chapter 14] and [25].

A multi-function, or multi-valued mapping,S from\({\mathbb {R}}^k\) to\({\mathbb {R}}^s\) is a mapping that takes points in\({\mathbb {R}}^k\) to sets in\({\mathbb {R}}^s\), and is denoted by\(S: {\mathbb {R}}^k \rightrightarrows {\mathbb {R}}^s\). Theouter limit ofS at\({{\bar{x}}}\in {\mathbb {R}}^k\)relative to\(X\subseteq {\mathbb {R}}^k\) is

and theinner limit ofS at\({{\bar{x}}}\)relative toX is

Here the notation\(\{x^k\}\rightarrow _X {{\bar{x}}}\) means that\(\{x^k\}\subseteq X\) with\(x^k\rightarrow {{\bar{x}}}\). If\(X={\mathbb {R}}^k\), we write\(x\rightarrow {{\bar{x}}}\) instead of\(x\rightarrow _{{\mathbb {R}}^k}{{\bar{x}}}\). We say thatS isouter semicontinuous (osc) at\({{\bar{x}}}\)relative toX if

When the outer and inner limits coincide, we write

and say thatS iscontiuous at\({{\bar{x}}}\)relative toX.

Let\(\varXi \) be a nonempty subset of\({\mathbb {R}}^\ell \) and let\({{\mathcal {A}}}\) be a\(\sigma \)-field of subsets of\(\varXi \), called themeasurable subsets of\(\varXi \) or the\({{\mathcal {A}}}\)-measurable subsets. Let\(\rho :\,{{\mathcal {A}}}\rightarrow [0,1]\,\) be a\(\sigma \)-finite Borel regular, complete, non-atomic, probability measure on\({{\mathcal {A}}}\). The corresponding measure space is denoted\((\varXi ,{{\mathcal {A}}}, \rho )\). A multi-function\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) is said to be\({{\mathcal {A}}}\)-measurable, or simply measurable, if for all open sets the set is in\({{\mathcal {A}}}.\) The multi-function\(\varPsi \) is said to be\({{\mathcal {A}}}\otimes {{\mathcal {B}}}^n\)-measurable if\({{\,\mathrm{gph}\,}}(\varPsi ) = \left\{ (\xi ,v)\,\left| \,v\in \varPsi (\xi )\right. \right\} \in {{\mathcal {A}}}\otimes {{\mathcal {B}}}^n\), where\({{\mathcal {B}}}^n\) denotes the Borel\(\sigma \)-field on\({\mathbb {R}}^n\) and\({{\mathcal {A}}}\otimes {{\mathcal {B}}}^n\) is the\(\sigma \)-field on\(\varXi \times {\mathbb {R}}^n\) generated by all sets\(A\times D\) with\(A\in {{\mathcal {A}}}\) and\(D\in {{\mathcal {B}}}^n\). If\(\varPsi (\xi )\) is closed for each\(\xi \) then\(\varPsi \) isclosed-valued. Similarly,\(\varPsi \) is said to beconvex-valued if\(\varPsi (\xi )\) is convex for each\(\xi \). Finally, we note that the completeness of the measure space guarantees the measurability of subsets of\(\varXi \) obtained as the projections of measurable subsets of\(\varXi \times {\mathbb {R}}^n\):

In particular, this implies that the multi-function\(\varPsi \) is\({{\mathcal {A}}}\)-measurable if and only if\({{\,\mathrm{gph}\,}}(\varPsi )\) is\({{\mathcal {A}}}\otimes {{{\mathcal {B}}}}^n\)-measurable [27, Theorem 14.8].

Let\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\), and denote by\(~{{\mathcal {S}}}(\varPsi )~\) the set of\(\rho \)-measurable functions\(f:\,\varXi \rightarrow {\mathbb {R}}^n\,\) that satisfy\(f(\xi )\in \varPsi (\xi )\) for a.e.\(\xi \in \varXi \). We call\(~{{\mathcal {S}}}(\varPsi )~\) theset of measurable selections of\(\varPsi \).

Theorem 10

(Measurable selections) [27, Corollary 14.6] A closed-valued measurable map\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) always admits a measurable selection.

We say that the measurable multi-function\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) isintegrably bounded, or for emphasis\(\rho \)-integrably bounded, if there is a\(\rho \)-integrable function\(a:\,\varXi \rightarrow {\mathbb {R}}^n_+\,\) such that

for all pairs\((\xi ,v)\in \varXi \times {\mathbb {R}}^n\) satisfying\(v\in \varPsi (\xi ).\) Here and elsewhere we interpret vector inequalities as element-wise inequalities. Let\(1\le p\le \infty \). When\(\varXi = {\mathbb {R}}^{\ell }\), we let\(L^p_m({\mathbb {R}}^{\ell },{{\mathcal {A}}},\rho )\) denote the Banach space of functions mapping\({\mathbb {R}}^{\ell }\) to\({\mathbb {R}}^m\). When\(p=2\),\(L^2_m({\mathbb {R}}^{\ell },{{\mathcal {A}}},\rho )\) is a Hilbert space with the inner product on the measure space\(({\mathbb {R}}^{\ell },{{\mathcal {A}}},\rho )\) given by

where\(\left\langle \cdot \, ,\, \cdot \right\rangle \) denotes the Euclidean inner product. If\(\rho ({\mathbb {R}}^{\ell })<\infty \), then

If the functiona in (58) is such that\(\left\| a(\xi )\right\| _{\scriptscriptstyle p}\) is integrable with respect to the measure\(\rho \) on the measure space\((\varXi ,{{\mathcal {A}}},\rho )\), then the multi-function\(\varPsi \) is said to be\(L^p\)-bounded, where\(\left\| \cdot \right\| _{\scriptscriptstyle p}\) denotes the p-norm of vectors.

Proposition 2

[7, Proposition 2.2] and [16, Corollary IV.8.4](Weak compactness of measurable selections) Let the multi-function\(\varPsi :{\mathbb {R}}^{\ell }\rightrightarrows {\mathbb {R}}^m\) be closed- and convex-valued, and\(L^2\)-bounded on\(L^2_m({\mathbb {R}}^{\ell },{{\mathcal {M}}}^n,\lambda _n)\), where\({{\mathcal {M}}}^n\) is the Lebesgue field on\({\mathbb {R}}^n\) and\(\lambda _n\) isn-dimensional Lebesgue measure. Then the set of measurable selections\({{\mathcal {S}}}(\varPsi )\) is a weakly compact, convex set in\(L^2_m({\mathbb {R}}^{\ell },{{\mathcal {M}}}^n,\lambda _n)\).

We now develop some properties of integrals of multi-valued mappings. Given a measurable multi-function\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\), we define the integral of\(\varPsi \) over\(\varXi \) with respect to the measure\(\rho \) by

The next theorem, due to Hildenbrand [18], is a restatement of Theorems 3 and 4 of Aumann [2] for multi-functions on the non-atomic measure space\((\varXi ,{{\mathcal {A}}},\rho )\). These results are central to the theory of integrals of multi-valued functions.

Theorem 11

(Integrals of multi-functions) [18, Theorem 4 and Proposition 7] The following properties hold for integrably bounded multi-functions\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) on non-atomic measure spaces\((\varXi ,{{\mathcal {A}}},\rho )\).

1. (a)

   If\(\varPsi \) is\({{\mathcal {A}}}\otimes {{\mathcal {B}}}^n\)-measurable, then\(\int \varPsi d\rho = \int {{\,\mathrm{conv\,}\,}}\varPsi d\rho \).

2. (b)

   If\(\varPsi \) is closed valued (not necessarily\({{\mathcal {A}}}\otimes {{\mathcal {B}}}^n\)-measurable), then\(\int \varPsi d\rho \) is compact.

We conclude this section with a very elementary, but useful lemma on measurabletubes, i.e. multi-valued mappings\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) of the form

where\({\mathbb {B}}:=\left\{ x\,\left| \,\left\| x\right\| _2\le 1\right. \right\} \) is the closed unit ball in\({\mathbb {R}}^n\) and\(\kappa :\,\varXi \rightarrow {\mathbb {R}}_+\,\) is measurable.

Lemma 11

(Tubes) Let\(\varPsi : \varXi \rightrightarrows {\mathbb {R}}^n\) be a measurable tube as in (59) with\(\kappa \in L^2_1(\varXi ,{{\mathcal {A}}},\rho )\) non-negative a.e. on\(\varXi \). Then, for every\(E\in {{\mathcal {A}}}\),\(\int _E\varPsi (\xi ) d\rho \subseteq \left[ \int _E\kappa (\xi ) d\rho \right] {\mathbb {B}}\subseteq \left\| {{\kappa }}\right\| _2\rho (E){\mathbb {B}}\).

Proof

The mapping\(\varPsi \) in (59) is obviously closed valued and measurable. Therefore, Theorem 10 tells us that\({{\mathcal {S}}}(\varPsi )\) is non-empty. Let\(E\in {{\mathcal {A}}}\) and\(s\in {{\mathcal {S}}}(\varPsi )\). Then

so that\(\int _Es(\xi ) d\rho \in \left[ \int _E\kappa (\xi ) d\rho \right] {\mathbb {B}}\). This proves the lemma since\( \int _E \kappa (\xi ) d\rho =\left\langle {{\kappa }}\, ,\, {{\mathcal {X}}}_E\right\rangle \le \left\| {{\kappa }}\right\| _2\rho (E).\)

Reprints and permissions